Interpretation and Multi-valued Logics

The logical system (the propositional calculus) which was studied in the first few lectures can be completely described by truth tables, and all of the theorems (tautologies) can be arrived at by a completely mechanical process.

This system can also be described with a collection of axioms and rules of inference. This axiomatic description (called L in the text) does not add much to our understanding of the propositional calculus. Rather, the purpose is to use it as a ``toy example'' so that we can understand axiomatizations when we are forced to use them, in situations where truth tables cannot work.

I would like to point out, however, that the axiomatic approach does not require us to assign meaning to the symbols we use, or the theorems we derive. We work solely with their properties, as described in the axioms and rules of inference. Of course, ignoring all meaning makes it hard to keep track of what we have and where we are going. Still, the theorems we prove are valid for any interpretation which is consistent with the axioms. The point of this note is to give some alternative interpretations.

Recall that the system L has the following 3 axioms:

(A1)

$\mbox{$\cal A$ }\mbox{$\Rightarrow$ }( \mbox{$\cal B$ }\mbox{$\Rightarrow$ }\mbox{$\cal A$ })$

(A2)

$(\mbox{$\cal A$ }\mbox{$\Rightarrow$ }( \mbox{$\cal B$ }\mbox{$\Rightarrow$ }\m... ...) \mbox{$\Rightarrow$ }(\mbox{$\cal A$ }\mbox{$\Rightarrow$ }\mbox{$\cal C$ }))$

(A3)

$(\mbox{$\neg$ }\mbox{$\cal B$ }\mbox{$\Rightarrow$ }\mbox{$\neg$ }\mbox{$\cal A... ... }\mbox{$\Rightarrow$ }\mbox{$\cal A$ }) \mbox{$\Rightarrow$ }\mbox{$\cal B$ })$

and the rule of inference modus ponens: $\mbox{$\cal A$ }, \mbox{$\cal A$ }\mbox{$\Rightarrow$ }\mbox{$\cal B$ }\mbox{$\thinspace \vdash \thinspace$ }\mbox{$\cal B$ }$.

It is easy to check that the only valid truth-table interpretation for L in a two-valued logical system (every statement takes on the value T or F) is the usual one. By the ``usual one'', we mean a truth table as follows:

A	$\mbox{$\neg$ }$A	$\mbox{\phantom{lotsaspace}}$	A	B	A $\mbox{$\Rightarrow$ }$ B
T	F		T	T	T
F	T		T	F	T
			F	T	F
			F	F	T

One way to check this claim is to just try every possible truth table (that is, a choice of T and F for every possible input to $\mbox{$\neg$ }$ and $\mbox{$\Rightarrow$ }$), and ensure that the axioms and the rules of inference hold for these choices. For the two-valued logic, there are 4 choices for $\mbox{$\neg$ }$ and 16 choices for $\mbox{$\Rightarrow$ }$, giving 64 possible truth tables. However, one of the first theorems proven is that $\mbox{$\cal A$ }\mbox{$\Rightarrow$ }\mbox{$\cal A$ }$, so we can easily rule out two of the lines for $\mbox{$\Rightarrow$ }$, leaving a total of only 16 possible truth tables.

Below is the output of a computer program that checks each of these 16 possibilities. When it finds an axiom or rule of inference that fails, it prints which axiom it was and what line in the table is a counterexample. (Note that for brevity, we represent each table horizontaly, with the assignments for $\mbox{$\neg$ }$ first, followed by those for $\mbox{$\Rightarrow$ }$. The sixth line of the table (labeled as 1,1)¹ is the usual interpretation described above.

table   Not    Implies
number          TF TF        comments
______  TF      TT FF   ---------------------

0,0     TT      TT TT   MP(F) fails
1,0     FT      TT TT   MP(F) fails
2,0     TF      TT TT   MP(F) fails
3,0     FF      TT TT   MP(F) fails
0,1     TT      TT FT   A3 fails for a=T b=F
1,1     FT      TT FT    
2,1     TF      TT FT   A3 fails for a=T b=F
3,1     FF      TT FT   A3 fails for a=T b=F
0,2     TT      TF TT   A1 fails for a=F b=T
1,2     FT      TF TT   A1 fails for a=F b=T
2,2     TF      TF TT   A3 fails for a=T b=F
3,2     FF      TF TT   A1 fails for a=F b=T
0,3     TT      TF FT   A1 fails for a=T b=F
1,3     FT      TF FT   A3 fails for a=T b=T
2,3     TF      TF FT   A1 fails for a=T b=F
3,3     FF      TF FT   A3 fails for a=T b=T

However, the two-valued propositional calculus is not the only possible interpretation we can assign to these axioms. Note that any theorem we prove using these axioms (such as $\mbox{$\neg$ }\mbox{$\neg$ }\mbox{$\cal B$ }\mbox{$\Leftrightarrow$ }\mbox{$\cal B$ }$) must be valid for these alternate interpretations, provided that we understand the meaning of $\mbox{$\neg$ }$ and $\mbox{$\Rightarrow$ }$ correctly.

For example, we might consider a three-valued logic, adding an additional symbol M (for ``maybe''). Running this same program for this new logical system, showing only the successes,² gives us the truth tables below:

        Not       Implies
table           TFM TFM TFM 
_____   TFM     TTT FFF MMM 

1,4     FTT     TTT FTT FTT    
2,4     MTT     TTT FTT FTT    
1,5     FTT     TTT MTT FTT    
2,5     MTT     TTT MTT FTT    
1,7     FTT     TTT FTT MTT    
2,7     MTT     TTT FTT MTT    
1,8     FTT     TTT MTT MTT    
2,8     MTT     TTT MTT MTT

If you look over this table, you'll see that the only place we have some choice is in the values of $\mbox{$\neg$ }\mbox{\bf T}$, $\mbox{\bf T}\mbox{$\Rightarrow$ }\mbox{\bf F}$, and $\mbox{\bf T}\mbox{$\Rightarrow$ }\mbox{\bf M}$; to each of these we can assign either M or F but not T. It is especially informative to note that we have to be careful in interpreting the theorem $\mbox{$\neg$ }\mbox{$\neg$ }\mbox{$\cal B$ }\mbox{$\Leftrightarrow$ }\mbox{$\cal B$ }$. This does not state that $\mbox{$\neg$ }\mbox{$\neg$ }\mbox{$\cal B$ }$and $\mbox{$\cal B$ }$ must take on the same truth value (as it does in the two-valued logic), but only that $\mbox{$\neg$ }\mbox{$\neg$ }\mbox{$\cal B$ }\mbox{$\Rightarrow$ }\mbox{$\cal B$ }$ and $\mbox{$\cal B$ }\mbox{$\Rightarrow$ }\mbox{$\neg$ }\mbox{$\neg$ }\mbox{$\cal B$ }$ must always take on the value T. For example, in the first line above, we have $NOT\mbox{$\neg$ }\mbox{\bf M}$ taking the value F, but $\mbox{\bf F}\mbox{$\Rightarrow$ }\mbox{\bf M}$ and $\mbox{\bf M}\mbox{$\Rightarrow$ }\mbox{\bf F}$ are both T.

Perhaps more interesting (but harder to understand, and to find) are the following two 4-valued logics:

                Not            Implies
table                   TFmp TFmp TFmp TFmp 
_____           TFmp    TTTT FFFF mmmm pppp 

27,84537        pmFT    TTTT FTFT mmTT pmFT
177,10731577    FTpm    TTTT FTpm mTmT pTpT

Note that the second line has the usual meanings of $\mbox{$\neg$ }$ and $\mbox{$\Rightarrow$ }$ if the inputs are Tor F, but adds additional meanings for the values p and m. There are many other possible 4-valued logics consistent with the axioms of L. However, the brute-force approach taken to find the valid two- and three-valued logics is much too inefficient to find all possible four-valued logics in a reasonable period of time. This is because even after discarding the trivial cases, there are still 4⁴ = 256 possible tables for $\mbox{$\neg$ }$, and 4¹² = 16777216 nontrivial tables for $\mbox{$\Rightarrow$ }$, leaving nearly 4.3 billion truth tables to check. Of course, with a little work, we can trim down the possibilities quite a bit.

Finally, we should remark that it is also possible to consider logics that take on countably many values (for example, rationals between 0 and 1), or a continuous range of values (any real number $0\le x \le 1$). Such logics cannot be represented readily by truth tables.