Truth Tables

Propositions

A proposition is a statement that is either true or false but is not both true and false. An example proposition is the statement "It is snowing outside", as it can either be snowing or be not snowing but not be both. Most of mathematics is expressed in mathematical sentences that are propositions, like 7 > 5. There are two special kinds of propositions that are important to the study of logic. A tautology is a proposition that is always true. An example is the proposition 3 = 3. A contradiction is a proposition that is always false. An example is the proposition 3 3. To understand these propositions, it is essential that you understand the grammar used to construct these mathematical statements.

Connectives

There are certain words that are being used with their proper English meaning but which clearly have a special role in the logical structure of a proposition. Words or phrases like there exists, for any, such that, and, or, implies, and if and only if have precise usage in the grammar of writing propositions. Before you are able to work comfortably with propositions, you will need to work with these phrases one at a time. One of the best ways to get fluid with these logical terms is to use elementary truth tables. A truth table is a way of looking at every possible truth outcome for one proposition, and is formed by making a column of all possible truth outcomes for every part of the proposition that has its own distinct truth value.

Let P and Q be propositions. There are five logical connectives which are used to form new propositions from P and Q.

Conjunction of P and Q. Disjunction of P and Q. Negation of P. Conditional from P to Q. Biconditional between P and Q.

"P and Q" "P or Q*" "not-P" "P implies Q" or "if P, then Q" "P if and only if Q"

(*Notice that the disjunction or is the inclusive or which is also true when both P and Q are true. In some statements in ordinary language an exclusive meaning of or is intended such as "bring him back dead or alive".)

There are shorthand notations for these connectives. The only ones that we will use regularily are ==> and <==> because their use sometimes makes the steps in a proof cleaner to write. Generally "and" and "or" are better written out (they are pretty short anyway). Here are the notational equivalents and meanings.

P /\ Q P \/ Q ~P P ==> Q P <==> Q

P and Q P or Q not-P if P, then Q P if and only if Q

True when P and Q are both true True when P or Q are true True when P is false Truth of P forces Q to be true The truth of P and Q are equivalent

The definitions in the right hand column seem almost useless because they are using connectives themselves. Things become much clearer if we form truth tables. T means true and F means false.

P ____ T T F F

Q ____ T F T F

P /\ Q ______ T F F F

P \/ Q ______ T T T F

~P ______ F F T T

P ==> Q _________ T F T T

P <==> Q _________ T F F T

The column under P ==> Q is disturbing to most people at first. In particular, P false and Q false make P ==> Q true. It means that you can conclude anything you want from a false proposition. An example like "if the moon is made of green cheese, then I am the richest person in the world" is sometime used to illustrate this. A more shocking form to students is the following true statement: "If I am an inch taller, then I play basketball as well as Michael Jordan." People tend to read more into a statement like that than just the logical content.

A mathematical example will make you more comfortable. Consider the proposition for x in R, if x > 1, then x² > x. Notice how x > 1 false can result in either x² > x true or x² > x false depending on x.

Logical Equivalence

Let us look closer at the "P and Q" column from the connectives truth table. The four entries are

T/\T = T
T/\F = F
F/\T = F
F/\F = F Notice the complete symmetry in T and F; to put it another way, interchanging the column under P with the column under Q does not change the column under P/\Q. Thus, "P and Q" means exactly the same as "Q and P". This could also be displayed in a truth table:

P ____ T T F F

Q ____ T F T F

P /\ Q ______ T F F F

Q /\ P ______ T F F F

For "P or Q" and "Q or P", we have a similar table:

P ____ T T F F

Q ____ T F T F

P \/ Q ______ T T T F

Q \/ P ______ T T T F

DEFINITION: Let P₁, P₂, ..., P_n be propositions and let A and B be two propositions formed from P₁, P₂, ..., P_n using the logical connectives /\, \/, ~, ==>, and <==> a finite number of times. We say A and B are logically equivalent if A and B have the same truth values for all possible truth values of P₁, P₂, ..., P_n.

Logical equivalence of A and B means that if we have established that statement A holds, then we immediately know that statement B holds, and vice versa. We have seen that the propositions P/\Q and Q/\P are logically equivalent and, also, P\/Q and Q\/P are logically equivalent.

You can often use truth tables to establish logical equivalence in cases that are not really obvious. We will now show three important examples, each involving the interplay between negation and the other connectives.

1. The propositions not-(P or Q) and (not-P) and (not-Q) are logically equivalent. This is established by the truth table:

P ____ T T F F

Q ____ T F T F

P \/ Q ______ T T T F

~(P \/ Q) _______ F F F T

~P ______ F F T T

~Q ______ F T F T

(~P) /\ (~Q) _________ F F F T

2. The propositions not-(P and Q) and (not-P) or (not-Q) are logically equivalent. This is established by the truth table:

P ____ T T F F

Q ____ T F T F

P /\ Q ______ T F F F

~(P /\ Q) _______ F T T T

~P ______ F F T T

~Q ______ F T F T

(~P) \/ (~Q) _________ F T T T

3. The propositions if P, then Q and if (not-Q), then (not-P) are logically equivalent. This is established by the truth table:

P ____ T T F F

Q ____ T F T F

P ==> Q _________ T F T T

~Q ______ F T F T

~P ______ F F T T

(~Q) ==> (~P) _________ T F T T

Contrapositive of a Proposition

The proposition (if (not-Q), then (not-P)) is called the contrapositive of (if P, then Q). In the struggle to find a proof of some implication, it is often easier to establish the contrapositive form of the implication and appeal to this logical equivalence to conclude the initial implication is true. Here is a quick example.

Converse of a Proposition

DEFINITION: Let (P ==> Q) be a given implication. The converse of (P ==> Q) is the implication (Q ==> P).

A mistake is often made in thinking that an implication and its converse mean the same thing. The following truth table shows that they are not logically equivalent.

P ____ T T F F

Q ____ T F T F

P ==> Q _________ T F T T

Q ==> P _________ T T F T

For example, (x = 5 ==> x² = 25) has the converse (x² = 25 ==> x = 5). A moment's thought shows that the truth of (P ==> Q) does not imply the truth of (Q ==> P).

For some true implications, the converse is also true and this is an important piece of information. Thus we often want to know "P implies Q and Q implies P". In logical symbols, "(P ==> Q) /\ (Q ==> P)", which is almost always written as "P <==> Q". There are several different ways in which this biconditional is expressed in words: "P if and only if Q"
"P iff Q"
"P is a necessary and sufficient condition for Q"
"P and Q are equivalent"

---