1) Let $f$ be a truth function of $n$ arguments such that $f(T, T, . . ., T) = T$ . Show that $f$ can be represented by a formula using connectives in the set $\{∧, ∨,→\}$. [Hints: $f$ can be represented by a formula $\phi$ using $\{¬, ∧, ∨\}$ in DNF (or CNF, whichever you prefer). The fact that $f(T, T, . . . , T) = T$ gives just enough information about $\phi$ to enable all the occurrences of $¬$ to be eliminated using $∧, ∨$ and $→$, with the aid of logical equivalences such as $(¬θ ∨ ψ) ≡ (θ → ψ)$.]
2) Hence, show that the number of truth functions of $n$ arguments representable using $\{∧, ∨,→\}$ is $2^{2n−1}$.
I am confused as to why we need, as the hint suggests, such a complicated procedure. The function only takes true arguments, so according to the construction of DNF we would just have one conjunction of literals; we wouldn't even need the negation because none of the argument is false!
In other words, if we have settled on using DNF to express $f$, then it would seem that all we need is $\land$ and can forget about $\lor$ and $\to$. While that perhaps still qualifies as having represented $f$ with the set of connectives given (though vacuously with regards to $\lor$ and $\to$), I am pretty sure I am colossally wrong, I just don't know where.
I also have no idea how to approach the 2nd question. I suspect the 1st question serves to lead the reader to a normal form, then one would count the number of truth functions expressible by that normal form. But I have absolutely no idea what such a normal form would look like; let aone counting the number.
Many thanks for any help offered!
Let $S_n$ be the set of formulae in $n$ variables that can be created using $\{\to, \land, \lor\}$. Let $T_n$ be the functions of $n$ variables such that $f(T,...,T) = T$.
For $n=1$ there are only two functions in $T_1$, $f(X) = X$ and $F(X) = T$ which can be represented by $A$ or $A \to A$ respectively. Hence every element of $T_1$ can be represented by a formula in $S_1$.
Suppose it is true for $n$ (that is, every function in $T_n$ can be represented by a formula in $S_n$).
We have $f(X_1,...,X_n,Y) = (\lnot Y \lor f(X_1,...,X_n,T)) \land (Y \lor f(X_1,...,X_n,F))$.
Note that the function $(X_1,...,X_n) \to f(X_1,...,X_n,T)$ is in $T_n$ and so can be expressed as a formula in $S_n$, and since $\lnot Y \lor f(X_1,...,Y_n,T)$ is equivalent to $Y \to f(X_1,...,Y_n,T)$, we see that the first clause can be written as a formula in $S_{n+1}$.
If $f(T,...,T,F) = T$, then the function $f(X_1,...,Y_n,F)$ is in $T_n$ and can be written as a formula in $S_n$ and hence the function $Y \lor f(X_1,...,Y_n,F)$ can be written as a formula in $S_{n+1}$ and hence the function can be expressed as a formula in $S_{n+1}$.
If $f(T,...,T,F) = F$, then the function $\lnot f(X_1,...,Y_n,F)$ is in $T_n$ and can be written as a formula in $S_n$ and since the function $Y \lor f(X_1,...,Y_n,F)$ is equivalent to $\lnot f(X_1,...,Y_n,F) \to Y$, we can express the function $f(X_1,...,X_n,Y)$ as a formula in $S_{n+1}$.
For the second part, note that if $f \in T_n$ then we must have $f(T,...,T) = T$, and so $f $ can be expressed as a formula in $S_n$. An argument by induction shows that if $f$ is a function represented by a formula in $S_n$ then we must have $f(T,...,T) = T$, hence $f \in T_n$.
Hence we see that $f \in T_n$ iff it can be written as a formula in $S_n$.
Since such an $f$ can take the values $F,T$ for the other $2^n -1$ parameter assignments, we see that there are $2^{(2^n-1)}$ such functions.