Tuesday, April 13, 2010

Truth Tables

BCC Logic
Eric Gerlach
12/10/2009

(NOTE: This is a companion to the lecture below, and the tabs do not line up below)

Truth Tables

There are three types of truth tables that you need to know for this Logic class. First, there are the basic truth tables (NOT, AND, OR, IF-THEN). These are the tables you have to understand to do the other two types of truth tables because each step of solving a truth table uses a particular case of these basic truth tables as a rule.

NOT
p ~ p
T F
F T

NOT is the most basic truth table with one variable (p)
and two cases (p is true, and p is false).

Notice that NOT takes a T and makes it an F or takes an F and makes it a T.
NOT does this to variables like ~ p {NOT P} and propositions like ~(p v q) {NOT (P OR Q)}.

All the other truth tables we will do involve two variables (p, q) and four cases.

The truth tables for AND, OR and IF-THEN:

AND
pq p ^ q
TT T
TF F
FT F
FF F

OR
pq p v q
TT T
TF T
FT T
FF F

IF>THEN
pq p > q
TT T
TF F
FT T
FF T

Notice that the four cases are always the same four cases in the same order, that AND is only true when p and q are both true (case 1), that OR is only false when p and q are both false (case 4), and that IF>THEN is only false when p is true and q is false (case 2).

IF>THEN is the tricky one. We all know that “p and q” is only true when both are true. If I tell you “I have an apple and I have a pear”, the whole proposition is true only if it is true that I have an apple and it is true that I have a pear. It is also fairly obvious that if I tell you “I have an apple or I have a pear”, the whole proposition is false only if I have neither an apple nor a pear. It is not so obvious why IF>THEN is TRUE in case 3 and case 4.

Many people make the mistake of thinking that case 3 and 4 are false because p is false. In fact, whenever p is false (p > q) is always true no matter whether q is true or false. Think about it as if it is a promise and the promise remains true unless it is broken. If I promise you, “If I bring you an apple, I will bring you a pear”, the only way I can break my promise is if I bring you an apple but I do not bring you a pear (case 2). If I do not bring you an apple, I have not broken my promise to you whether or not I bring you a pear. If I do not bring you an apple and I bring a pear or I do not bring you either an apple or a pear it cannot be breaking the promise because I said “IF I bring you an apple…”.

The second type of truth table uses the basic truth tables and their cases as rules to evaluate a proposition that contains p and q to see when it is true and when it is false.

Let us take the proposition ~ (p v q). We have to do two steps because there are two operators, NOT and OR. Just like algebra, we must do the order of operations correctly. First we do the inner OR, and then we do the outer NOT.

pq ~ (p v q)
TT F T
TF F T
FT F T
FF T F

Notice that the final answer or evaluation is in bold (FFFT). First you figure out the OR on the inside using the basic OR table, then you take those four values and invert them with the NOT as the second and final step.


pq (~ p v q)
TT F T T
TF F F F
FT T T T
FF T T F

Let us now look at the proposition (~p v q). Notice the NOT is now inside the brackets, and that the values for q stay the same while the values for p are changed by the NOT. Once you have written the values for each case under NOT p and q, you can then use the OR rule (the four cases of the basic OR table) to figure out the four truth values that go under the OR as the final answer.

Case one is now (F v T), which is case 3 of the basic OR table, so the value for case 1 is true because OR is always true whenever either side of the OR is true. Notice that only case 2 is false because in case 2 ~ p and q are both false. Notice also that (~ p v q) has the same four truth values as (p > q), and so the two propositions are said to be equivalent.

The third type of truth table is a proof that two expressions are equivalent (have the same four truth values in the same order). We use an equals sign (=) between two propositions, and if the truth values for one proposition are the same as the other, we can put four T’s down the middle.

Let us evaluate the equivalence of the propositions ~ (p ^ q) and (~ p v ~ q), the equivalence known as De Morgan’s Theorem A. When we evaluate the equivalence, it goes like this:

pq ~(p ^ q) = (~ p v ~ q)
TT F T T F F F
TF T F T F T T
FT T F T T T F
FF T F T T T T

Notice that the values underneath the NOT on the left side and the OR on the right side are equivalent, and so there are four T’s underneath the equals sign as the final answer. This means that by the truth table method we have proved De Morgan’s Theorem A! This is why Wittgenstein’s truth tables replaced Aristotle’s syllogisms as the central tool of modern Logic.