##
This **preview** shows page *1-2-3-4*
out of 12 **pages**.

*View Full Document*

End of preview. Want to read all 12 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

2. PROPOSITIONAL EQUIVALENCES 332. Propositional Equivalences2.1. Tautology/Contradiction/Contingency.Definition 2.1.1. A tautology is a proposition that is always true.Example 2.1.1. p ∨ ¬pDefinition 2.1.2. A contradiction is a proposition that is always false.Example 2.1.2. p ∧ ¬pDefinition 2.1.3. A contingency is a proposition that is neither a tautologynor a contradiction.Example 2.1.3. p ∨ q → ¬rDiscussionOne of the important techniques used in proving theorems is to replace, or sub-stitute, one proposition by another one that is equivalent to it. In this section we willlist some of the basic propositional equivalences and show how they can be used toprove other equivalences.Let us look at the classic example of a tautology, p ∨ ¬p. The truth tablep ¬p p ∨ ¬pT F TF T Tshows that p ∨ ¬p is true no matter the truth value of p.[Side Note. This tautology, called the law of excluded middle, is adirect consequence of our basic assumption that a proposition is astatement that is either true or false. Thus, the logic we will discusshere, so-called Aristotelian logic, might be described as a “2-valued”logic, and it is the logical basis for most of the theory of modernmathematics, at least as it has developed in western culture. Thereis, however, a consistent logical system, known as constructivist,or intuitionistic, logic which does not assume the law of excludedmiddle. This results in a 3-valued logic in which one allows for2. PROPOSITIONAL EQUIVALENCES 34a third possibility, namely, “other.” In this system proving that astatement is “not true” is not the same as proving that it is “false,”so that indirect proofs, which we shall soon discuss, would not bevalid. If you are tempted to dismiss this concept, you should beaware that there are those who believe that in many ways this typeof logic is much closer to the logic used in computer science thanAristotelian logic. You are encouraged to explore this idea: thereis plenty of material to be found in your library or through theworldwide web.]The proposition p ∨ ¬(p ∧ q) is also a tautology as the following the truth tableillustrates.p q (p ∧ q) ¬(p ∧ q) p ∨ ¬(p ∧ q)T T T F TT F F T TF T F T TF F F T TExercise 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 statementr ↔ s is a tautology.Notation: If r and s are logically equivalent, we writer ⇔ s.DiscussionA second notation often used to mean statements r and s are logically equivalentis r ≡ s. You can determine whether compound propositions r and s are logicallyequivalent by building a single truth table for both propositions and checking to seethat they have exactly the same truth values.Notice the new symbol r ⇔ s, which is used to denote that r and s are logicallyequivalent, is defined to mean the statement r ↔ s is a tautology. In a sense the2. PROPOSITIONAL EQUIVALENCES 35symbols ↔ 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 thestatement r ↔ s alone does not imply any particular truth value. The symbol ⇔ isthe 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 ↔ qT T T T T TT F F T F FF T T F F FF F T T T TSolution 2. Examine every possible case in which the statement (p → q) ∧ (q → p)may not have the same truth value as p ↔ qCase 1. Suppose (p → q) ∧(q → p) is false and p ↔ q is true. There are two possiblecases where (p → q) ∧ (q → p) is false. Namely, p → q is false or q → pis false (note that this covers the possibility both are false since we use theinclusive “or” on logic).(a) Assume p → q is false. Then p is true and q is false. But if this is thecase, the p ↔ q is false.(b) Assume q → p is false. Then q is true and p is false. But if this is thecase, 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 possibleways this may occur that we address below.(a) Assume p is true and q is false. Then p → q is false, so the conjunctionalso must be false.(b) Assume p is false and q is true. Then q → p is false, so the conjunctionis also false.We exhausted all the possibilities, so the two propositions must be logically equivalent.2. PROPOSITIONAL EQUIVALENCES 36DiscussionThis example illustrates an alternative to using truth tables to establish the equiv-alence of two propositions. An alternative proof is obtained by excluding all possibleways 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 ∧ ¬qT T F T F FT F T F T TF T F T F FF F T T F FSince the truth values for ¬(p → q) and p∧¬q are exactly the same for all possiblecombinations 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. Thiscan 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 trueand 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) willbe true. So this case is not possible either.Since it is not possible for the two propositions to have different truth values, theymust 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 the method of Solution 2 in Example 2.3.2 to show that thepropositions p ↔ q and ¬(p ⊕ q) are equivalent.2. PROPOSITIONAL EQUIVALENCES 372.4. Important Logical Equivalences. The logical equivalences below are im-portant equivalences that should be memorized.Identity Laws: p ∧ T ⇔

View Full Document