#### 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" |

*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 P ==> Q P <==> 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 |

____ T T F F | ____ T F T F | ______ T F F F | ______ T T T F | ______ F F T T | _________ T F T T | _________ T F F T |

A mathematical example will make you more comfortable. Consider the proposition

*x*in

**R**, if

*x*> 1, then

*x*

^{2}>

*x*.

*x*> 1 false can result in either

*x*

^{2}>

*x*true or

*x*

^{2}>

*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/\F = F

F/\T = F

F/\F = F

____ T T F F | ____ T F T F | ______ T F F F | ______ T F F F |

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

____ T T F F | ____ T F T F | ______ T T T F | ______ T T T F |

DEFINITION: Let P

_{1}, P

_{2}, ..., P

_{n}be propositions and let A and B be two propositions formed from P

_{1}, P

_{2}, ..., 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

_{1}, P

_{2}, ..., 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:

____ T T F F | ____ T F T F | ______ T T T F | _______ F F F T | ______ F F T T | ______ F T F T | _________ 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:

____ T T F F | ____ T F T F | ______ T F F F | _______ F T T T | ______ F F T T | ______ F T F T | _________ 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:

____ T T F F | ____ T F T F | _________ T F T T | ______ F T F T | ______ F F T T | _________ 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.

____ T T F F | ____ T F T F | _________ T F T T | _________ T T F T |

*x*= 5 ==>

*x*

^{2}= 25) has the converse (

*x*

^{2}= 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 iff Q"

"P is a necessary and sufficient condition for Q"

"P and Q are equivalent"