[SL04] Complex truth-tables


§1. What are we doing?

In this tutorial you will learn how to draw full (or complete) truth-tables for more complex WFFs. What we want to do is to use a truth-table to tell us when a WFF is true and when it is false. Here is an analogy to help you understand what it is that we want to do.

Suppose we have two arrows and they can only point either up or down. Then there are only four different possible ways they can be aligned:

Now consider the sentence "the left arrow is pointing up and the right arrow is pointing up". Obviously, the sentence is true in the first situation, and false in the other three situations. If we consider a different sentence, such as "the right arrow is pointing down", then it is true in the second and fourth situation. Finally, what about a sentence such as "the left arrow is pointing up and the left arrow is pointing down"? This is an inconsistent statement, and clearly it is false in all four situations.

Similarly, when we draw a truth-table for a WFF in SL, we are trying to list a set of possible situations to determine when the WFF is true (if ever) and when it is false (if ever).

§2. Drawing a truth-table

To draw a truth-table for a WFF, follow the following procedure. First, remember that there are four regions in a full truth-table:

Region #1
Region #2

 

Region #3

 

 

Region #4

 

To complete the truth-table for a WFF, you need to fill in the four regions according to this procedure:

Step 1

Write down the WFF in region #2.

Step 2

Identify the sentence letters that appear in the WFF, and write them down one after the other on a single row in region #1. You only need to write down a sentence letter once even if it has more than one occurrences in the WFF.

So for example, given the WFF "(P→(PvQ))", the truth-table would look like this after the first two steps:

 P   Q 
 (P→(PvQ))

 

Region #3

 

 

Region #4

 

Step 3

Region 3 is a list of all possible combination of truth-values that the sentence letters in region #1 can take. Each row in region #3 specifies a combination, and each combination is called an assignment of truth-values. These assignments correspond to the different possible situations in the arrow example at the top.

If there are n sentence letters in region #1, each of which can have the truth-value T or F, then we know that there are 2n possible assignments of truth-values (21=2, 22=4, 23=8, 24=16, etc.). So in the truth-table above, there should be four assignments. We write them down one on each row in region #3:

 P   Q 
 (P→(PvQ))
 T   T 
 T   F 
 F   T 
 F   F 
Region #4

On each row, we write down under each sentence letter a truth-value which is the truth-value that the sentence letter receives under that assignment. So "T F" on the second row indicates an assignment where "P" is T and "Q" is F, and "F T" on the third row indicates an assignment where "P" is F and "Q" is T.

In writing down the assignments it is important to use a systematic method to list all of them. Without such a method it is easy to miss some of them if there are many rows in the truth-table. When you compare the truth-tables of two or more WFFs, it is important to use the same method to list the truth-value assignments in the same order.

The standard method is as follows: Start with the rightmost sentence letter in region #1. Write "T" down under the letter on the first row of region #3, and then "F" on the second row, alternating for every row until the last row. Then move on to the second sentence letter, and again start with "T". But this time alternate the truth-value only every two rows. If there is a third sentence letter, alternate between "T"s and "F"s every four rows. In general then, for the nth sentence letter (starting from the right hand side), alternate between "T"s and "F"s every 2n-1 row.

Step 4

The remaining task in completing the truth-table is to fill in region #4 by calculating the truth-value of the WFF under each assignment.

First, let us define the length of a WFF as the number of symbols of SL it contains. Each occurrence of a connective or sentence letter counts as a single symbol, and the open and close brackets are different symbols. So "P" has length 1, "~~Q" has length 3, and "((P&Q)→R)" has length 9 (not 10).

We then apply this procedure. First, write down beneath each sentence letter of the WFF the truth-value it has under each assignment:

 P   Q 
(P→(PvQ))
 T   T 
 T   F 
 F   T 
 F   F 
 T     T  T  
 T     T  F  
 F     F  T  
 F     F  F  

Sentence letters are of course WFFs of length 1. We then look for the next shortest WFFs which are part of the whole WFF, and calculate their truth-values under each assignment. The next shortest WFFs should be of length 2, such as "~Q", but since there are no such WFFs, the next shortest WFF is "(PvQ)" of length 5. We write down its truth-value for each assignment under its main operator. Remember that the main operator of a WFF is the occurrence of a connective that has the widest scope.

 P   Q 
(P→(PvQ))
 T   T 
 T   F 
 F   T 
 F   F 
 T     TTT  
 T     TTF  
 F     FTT  
 F     FFF  

We then repeat this procedure with the next shortest WFF until we are finished with the whole WFF:

 P   Q 
(P→(PvQ))
 T   T 
 T   F 
 F   T 
 F   F 
 T  T  TTT  
 T  T  TTF  
 F  T  FTT  
 F  T  FFF  

The last column of truth-value we write down indicates the truth-values of the whole WFF under each of the assignments. This particular truth-table we have completed shows that the WFF is true under all the four possible assignments.

If you can mentally carry out calculations of truth-values quickly, you can leave out writing the truth-values of the parts of WFF and just write down the truth-value of the whole WFF under each assignment. Then you will end up with this truth-table.

 P   Q 
(P→(PvQ))
 T   T 
 T   F 
 F   T 
 F   F 
T      
T      
T      
T      

Draw the following full truth-tables, and then click the WFFs to check if you have done it correctly.

  1. (P&~Q)
  2. ((P&Q)→R)
  3. (~(P∨Q)→R)
  4. ~(~(P↔(~P∨Q))→~R)
  5. ~(S↔(~(P&Q)→R))

§3. Brackets

Now that you know how to construct complex truth-tables, you can see why brackets are necessary. For example, “(A&B→C)” is ambiguous as between “((A&B)→C)” and “(A&(B→C))”. The truth-tables of the two WFFs are very different though :

ABC((A&B)→C)
TTTT
TTFF
TFTT
TFFT
FTTT
FTFT
FFTT
FFFT
ABC(A&(B→C))
TTTT
TTFF
TFTT
TFFT
FTTF
FTFF
FFTF
FFFF

Of course there are cases where the brackets do not matter. For example, it should be obvious that with “P&Q&R&S”, no matter where you place the brackets to turn it into a WFF, the resulting truth-table is always the same.

previous tutorial next tutorial

homepagetopcontactsitemap

© 2004-2024 Joe Lau & Jonathan Chan