2 PROPOSITIONAL EQUIVALENCES 33 2 Propositional Equivalences 2 1 Tautology Contradiction Contingency Definition 2 1 1 A tautology is a proposition that is always true Example 2 1 1 p p Definition 2 1 2 A contradiction is a proposition that is always false Example 2 1 2 p p Definition 2 1 3 A contingency is a proposition that is neither a tautology nor a contradiction Example 2 1 3 p q r Discussion One of the important techniques used in proving theorems is to replace or substitute one proposition by another one that is equivalent to it In this section we will list some of the basic propositional equivalences and show how they can be used to prove other equivalences Let us look at the classic example of a tautology p p The truth table p p p p T F T F T T shows that p p is true no matter the truth value of p Side Note This tautology called the law of excluded middle is a direct consequence of our basic assumption that a proposition is a statement that is either true or false Thus the logic we will discuss here so called Aristotelian logic might be described as a 2 valued logic and it is the logical basis for most of the theory of modern mathematics at least as it has developed in western culture There is however a consistent logical system known as constructivist or intuitionistic logic which does not assume the law of excluded middle This results in a 3 valued logic in which one allows for 2 PROPOSITIONAL EQUIVALENCES 34 a third possibility namely other In this system proving that a statement is not true is not the same as proving that it is false so that indirect proofs which we shall soon discuss would not be valid If you are tempted to dismiss this concept you should be aware that there are those who believe that in many ways this type of logic is much closer to the logic used in computer science than Aristotelian logic You are encouraged to explore this idea there is plenty of material to be found in your library or through the worldwide web The proposition p p q is also a tautology as the following the truth table illustrates p q p q p q p p q T T T F T T F F T T F T F T T F F F T T Exercise 2 1 1 Build a truth table to verify that the proposition p q p q is a contradiction 2 2 Logically Equivalent Definition 2 2 1 Propositions r and s are logically equivalent if the statement r s is a tautology Notation If r and s are logically equivalent we write r s Discussion A second notation often used to mean statements r and s are logically equivalent is r s You can determine whether compound propositions r and s are logically equivalent by building a single truth table for both propositions and checking to see that they have exactly the same truth values Notice the new symbol r s which is used to denote that r and s are logically equivalent is defined to mean the statement r s is a tautology In a sense the 2 PROPOSITIONAL EQUIVALENCES 35 symbols and convey similar information when used in a sentence However r s is generally used to assert that the statement r s is in fact true while the statement r s alone does not imply any particular truth value The symbol is the preferred shorthand for is equivalent to 2 3 Examples Example 2 3 1 Show that p q q p is logically equivalent to p q Solution 1 Show the truth values of both propositions are identical Truth Table p q p q q p p q q p p q T T T T T T T F F T F F F T T F F F F F T T T T Solution 2 Examine every possible case in which the statement p q q p may not have the same truth value as p q Case 1 Suppose p q q p is false and p q is true There are two possible cases where p q q p is false Namely p q is false or q p is false note that this covers the possibility both are false since we use the inclusive or on logic a Assume p q is false Then p is true and q is false But if this is the case the p q is false b Assume q p is false Then q is true and p is false But if this is the case the p q is false Case 2 Suppose p q q p is true and p q is false If the latter is false the p and q do not have the same truth value and the there are two possible ways this may occur that we address below a Assume p is true and q is false Then p q is false so the conjunction also must be false b Assume p is false and q is true Then q p is false so the conjunction is also false We exhausted all the possibilities so the two propositions must be logically equivalent 2 PROPOSITIONAL EQUIVALENCES 36 Discussion This example illustrates an alternative to using truth tables to establish the equivalence of two propositions An alternative proof is obtained by excluding all possible ways in which the propositions may fail to be equivalent Here is another example Example 2 3 2 Show p q is equivalent to p q Solution 1 Build a truth table containing each of the statements p q q p q p q p q T T F T F F T F T F T T F T F T F F F F T T F F Since the truth values for p q and p q are exactly the same for all possible combinations of truth values of p and q the two propositions are equivalent Solution 2 We consider how the two propositions could fail to be equivalent This can happen only if the first is true and the second is false or vice versa Case 1 Suppose p q is true and p q is false p q would be true if p q is false Now this only occurs if p is true and q is false However if p is true and q is false then p q will be true Hence this case is not possible Case 2 Suppose p q is false and p q is true p q is true only if p is true and q is false But in this case p q will be true So this case is not possible either Since it is not possible for the two propositions to have different truth values they must be equivalent Exercise 2 3 1 Use a truth table to show that the propositions p q and p q are equivalent Exercise 2 3 2 Use …