I wanted to ask the proof for uniqueness of answer given by truth tables. I am reading Kleene's "Introduction to Metamathematics" Chapter 6 Section 28 on evaluation and consistency. There he introduces truth tables for operations and, implies, or and not. Then he defines the value of the propositional letter formula $A$ that has $P_1, ..., P_m$ as distinct propositional letters with chosen values of $t$ or $f$ for each of them as the result of applying truth tables to each pair of $t$'s and $f$'s. But nowhere does it say that such evaluation yields only one, unique result.

My attempt:

Proof by induction. From the definition of formula by Kleene there are always $2n$ parentheses in a propositional letter formula (which can also be proved by induction on $n$). We want to prove that for each formula $A$ having $2n$ parentheses it is true that the evaluation procedure yields a unique answer, and that is true for all $n$, and therefore for all formulas.

Basis: $n=0$. Then, the formulas have the form $P$ where $P$ is some propositional letter. Then, if $P$ is $t$ then the formula has value $t$, and if $P$ is $f$ then the formula has value $f$. So, in all cases the result is unique.

Step: Assume that it is true for $n=k$. Then, consider formula $A$ which has $2k+2$ parentheses. It means that it was formed from $M$ and $N$ by an operator implies, and,or or not. Both $M$ and $N$ each have at most $2k$ parentheses, which means that by induction hypothesis their truth value is unique. Then, because truth tables give unique answer given two values, then the formula $A$ has its truth value determined uniquely.

Is this proof correct?

I would appreciate any advice and suggestions!


In your step: When the $\neg$ operator is the main operator of formula $A$, then it is not built up from two formulas $M$ and $N$ plus one operator.

Now, that issue seems easily repaired by saying that $A$ can also be built up from one smaller formula $M$ and any unary operator like the $\neg$.

However, you could still be in trouble: if your syntax is defined in such a way that the result of applying a binary operator will result in an expression that starts and ends with parentheses (that is, if your syntax is such that $A \lor B$ is not synatactically correct, for it demands it to be $(A \lor B)$), then note that the formula $\neg (A \lor B)$ is built up from formula $(A \lor B)$ and the $\neg$ operator, and note that $(A \lor B)$ does not have less parentheses than $\neg (A \lor B)$.

So, I would suggest that in your proof you deal with the $\neg$ case separately. Otherwise, it works.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.