MODULE: Sentential logic

TUTORIAL SL04: More complicated truth-tables

SL04.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 someone says "John and Mary are both in the black room." Call this statement "Q". When is Q true and when is Q false? We might classify all possible states of the universe into five types :

Here the red figure represents Mary and the blue figure represents John. The black enclosure represents the black room. The fifth situation is one where the black room does not exist. Naturally, Q is true only in the first situation, and false in the other four situations. This is in a way a kind of truth-table for Q : a table that tells us when Q is true and when Q is false.

Now suppose Q is the statement "John is in the black room and John is not in the black room." This is an inconsistent statement, and it is obvious that it is false in all five situations.

Similarly, when we draw a truth-table for a WFF in SL, we are trying to determine when the WFF is true (if ever) and when it is false (if ever). What you need to do is to remember the steps involved in the procedure, and practice on a few WFFs yourself.

SL04.2 Drawing a truth-table

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 room example above.

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 2ⁿ possible assignments of truth-values (2¹=2, 2²=4, 2³=8, 2⁴=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 2^n-1 row.

Here are some flash animations to show how you should write down the assignments:

Before continuing, make sure that you can do the same thing.

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

SL04.3 Exercises

? Question 1 - Now you should be able to draw full truth-tables on your own. Here are a few more examples. Try to draw the truth-tables yourself first, and then compare your answers with the solutions.

? Question 2 - Look at the circuit diagram below, and identify the combinations of switch positions which would enable the light to turn on.

If "P" means switch 1 is up, "Q" means switch 2 is up, and "R" means switch 3 is up, which complex WFF can be used to describe all conditions under which the light is on?
[Show answer]

((P&~R)∨(Q&~P))

SL04.4 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 :

A	B	C	((A&B)→C)
T	T	T	T
T	T	F	F
T	F	T	T
T	F	F	T
F	T	T	T
F	T	F	T
F	F	T	T
F	F	F	T

A	B	C	(A&(B→C))
T	T	T	T
T	T	F	F
T	F	T	T
T	F	F	T
F	T	T	F
F	T	F	F
F	F	T	F
F	F	F	F

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 page