I'm trying to solve the following exercise:
Let $A_1,...,A_n$ be propositions, $n \in \mathbb N$. Show that every $n$-ary logical connective $J(A_1,...,A_n)$ considered as a function $J:\{t,f\}^n \to \{t,f\}$ ($t$ is true, $f$ is false) has a disjunctive normal form, in other words can be represented as a disjunction $Y_1,...Y_k$ of a suitable amount of $k\in \mathbb N_0$ propositions $Y_i$ of the form $a_{i,1} \land ... \land a_{i,n}$, where each $a_{i,j}$ stands for either $A_j$ or $\lnot A_j$. The empty disjunction ($k=0$) is identified with $false$.
My idea is proving this with induction over $n$. I think I have the right idea, the base case is obvious and the $n \to n+1$ part is not hard either (I think), I just have trouble writing this down in a formally, mathematically correct way. Can you help me out?
If you were to put the function on a truth-table, you can always find an expression (that is automatically in DNF) that is equivalent to that function: for every row where the function value is true, generate a conjunction of the truth or falsity of the propositions as represented by that row (e.g. if you have 3 propositions involved, $P$, $Q$, and $R$, and if in the row where $P$ is true, $Q$ is false, and $R$ is true, the function-value is true, then generate the conjunction $P \wedge \neg Q \wedge R$.
Do this for all rows (so you have a bunch of conjunctions like that), and disjunct all those conjunctions together. A moment's reflection will reveal that this statement (which is in DNF, since it is a disjunction of conjunctions of literals (a literal is an atomic statement or a negation of an atomic statement) will indeed capture exactly the truth-function as desired.
One edge case as you mention: if there are no rows where the function is true, then you can of course use the $false$ expression.
Of course, you don't have to use a truth-table to do this, and you can directly talk about 'Consider all $2^n$ possible truth-value assignments to the $n$ propositions, and generate a conjunctive statement for all those assignments for which the function is true. ...'.
And finally, no, I don't think induction makes this any easier.