Truth values give unique answer

Question

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!

Answer 1

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.