# Show that truth function $f(T,T,...T)=T$ can be represented by using $\{\land,\lor,\to\}$

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!

• Induction on the number of arguments?
– user123641
Commented Feb 6, 2018 at 5:05
• @Robert I am sorry but I am not sure what you mean...what would we need to prove? That a formula composed solely of $\land$ can express $f$ of $n$ arguments? But I am pretty sure we would need more than $\land$, I just don't know why (which is what confuses me the most) Commented Feb 6, 2018 at 5:14
• You need to show that if you know that $f(T,...,T) = T$ then you can express $f$ using the given connectives (that is you don't need $\lnot$). Commented Feb 6, 2018 at 5:17
• @copper.hat You're right... $2^{2n-1}$ should be $2^{2^n-1}$. Commented Feb 6, 2018 at 5:30

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.

• Thank you so much for your answer! Sorry it took me a few days to try and understand what has been explained; would you mind elaborating where do $f(X_1,...,X_n,Y) = (\lnot Y \lor f(X_1,...,X_n,T)) \land (Y \lor f(X_1,...,X_n,F))$ and $(X_1,...,X_n) \to f(X_1,...,X_n,T)$ come from please? Is $Y$ the $n+1$th variable? Commented Feb 8, 2018 at 5:17
• @DanielMak: The first is just Boole's (or Shannon's) expansion. Yes, $Y$ is the $n+1$st variable. The terminology $(X_1,...,X_n) \to f(X_1,...,X_n,T)$ just means the function that maps the first $n$ variables to the value $f(X_1,...,X_n,T)$. I guess I could have written something like $f(\cdot,...,\cdot,T)$? Commented Feb 8, 2018 at 6:18
• Frankly, using the $\to$ connective is always non intuitive for me except for the normal $P \to Q$ sort of thing. Commented Feb 8, 2018 at 6:22

You say

The function only takes true arguments,


but that is not true. The function $f$ takes $n$ arbitrary arguments $(T/F)$, but it is given that if you apply $f$ to $(T, T, \dots, T)$, the result is $T$.

As for part 2, there are $2^{2^n}$ truth functions of $n$ arguments and half of them, $2^{2^n-1}$, satisfy $f(T, T, \dots, T) = T$. In part 1 you've proven that those function are expressible using $\{\land, \lor, \to\}$; now you still have to argue that every function that is expressible using $\{\land, \lor, \to\}$ maps $(T, T, \dots, T)$ to $T$.