I am currently reading this book on mathematical logic from Delft University (I have to admit that I am disappointed with the quality of the book). I don't understand some things from the book. For example, at the end of the second chapter (page 18) there is problem 10. which says:
For our proof that {¬,∨} is functionally complete, we need to show that all formulas in propositional logic can be expressed in an equivalent form using only {¬, ∧, ∨, →, ↔}.
a) How many unique truth tables exist for formulas containing two atoms?
b) Create a function for each of the possible truth tables that uses only the 5 operators listed above.
c) Give an (informal) argument why this means all formulas in propositional logic can be expressed using only these five operators.
Without going into the fact that the author did not define anywhere in the book before this problem what a formula of propositional logic actually is (so it is unclear what we actually need to show), I, (confused) go to the end of the book (page 188), where the author gives a "solution" to this problem, where first in parts a) and b) it is shown that, if we have only two variables, each table from the set of 2^4 = 16 possible truth tables can be represented using some formula consisting solely of two atoms and logical operations from the set {¬, ∧, ∨, →, ↔}.
But now, for the proof of c), the author writes:
Given that we can create a formula for each of the possible truth table using these 5 operators. Furthermore, we know that there are only 2^(2^n) possible truth tables, where n is the number of unique atoms. Given that every one of these truth tables has a corresponding formula using only the 5 operators, which we denote as f_i, where 1 ≤ i ≤ 2^(2^n) − 1. Now take a formula, f′, that uses the same unique atoms, but not necessarily the same operators from the set of 5 operators stated in the description. The truth table for the formula f′ will be equal to one of the 2^2^n possible truth tables, which also means that there is a f_i that is equivalent to f′, so we can rewrite f′
And while parts a) and b) are clear to me, the argument the author used in the proof of c) is not clear to me at all. Can someone explain to me what the author is trying to say there? The part where it says "Given that every one of these truth tables has a corresponding formula using only the 5 operators..." is particularly unclear to me. Isn't that exactly what we have to prove? Please, help - I'm really confused!
Long comment. You are right.
The point
is exactly what you have to prove.
The "formal" answer is Conjunctive Normal Form: "every propositional formula can be converted into an equivalent formula that is in CNF. This transformation is based on rules about logical equivalences: double negation elimination, De Morgan's laws, and the distributive law."
What we can do with the hint in the textbook: it is a sort of intuitive approach to an inductive proof.
The author shows (writing it in full) that there is a solution to the two atoms case: "we can create a formula for each of the [$2^{2^2}$] possible truth table using the [basic] 5 operators."
The claim for the general case [$2^{2^n}$] can be inductively proved considering that we can split the truth table in two parts: one with the atoms $p_1, \ldots, p_{n-1}$ and a second one for the atom $p_n$.
But if we assume (induction hypotheses) that we can solve the problem for the case with $(n-1)$ atoms, then we have reduced the problem to the two atoms case.