Transcript Equivalence
MATH 224 – Discrete Mathematics Logical Equivalence Two propositions are called equivalent if they have exactly the same truth values. For example p q is logically equivalent to (p ^ ¬q) v (¬p ^ q). Can you construct a truth table for each of these compound propositions? Another way of stating that two propositions are equivalent is to say that the proposition formed by connecting the two with the bi-conditional connective is a tautology. In other words, for the example above, the proposition (p q) ↔ [(p ^ ¬q) v (¬p ^ q)] is a tautology. What is a tautology? 4/7/2016 1 MATH 224 – Discrete Mathematics Common Logical Equivalence Some equivalences are given names for historical reasons or because they are often used in logical arguments. See Table 6 on Page 27 in our textbook. Two of the most famous are called De Morgan’s laws. They provide a mechanism for converting between conjunctions (and) and disjunctions (or). Our textbook gives several examples. In the text, the conversion from and to or is given as: ¬(p ^ q) ≡ (¬p v ¬q). A second variation would be (p ^ q) ≡ ¬(¬p v ¬q). Note that the ≡ symbol is read as equivalent. Its meaning is essentially the same as ↔. To be precise, the ≡ symbol is used in the meta-language for the propositional calculus. Do you know what a meta-language is? So it would have been equally correct to say that ¬(p ^ q) ↔ (¬p v ¬q) and (p ^ q) ↔ ¬(¬p v ¬q) are tautologies. 4/7/2016 2 MATH 224 – Discrete Mathematics Logical Equivalences Corresponding to Algebraic Laws Note that the names of several of the equivalences in Table 6 correspond to rules in algebra, for example, associate, commutative, distributive, and identity laws. What is the identity for addition; for multiplication? What is the identity for the or operator; for and? Note that the associative and commutative laws apply to both addition and multiplication. Can you give an example of each of these? As shown in Table 6 both of these laws apply to disjunction and conjunction. From the distributive law in Table 6, do any of the propositional connectives correspond to addition, or multiplication? In algebra, does addition distribute over multiplication? 4/7/2016 3 MATH 224 – Discrete Mathematics Logical Equivalences 4/7/2016 4 MATH 224 – Discrete Mathematics Logical Equivalences 4/7/2016 5 MATH 224 – Discrete Mathematics 4/7/2016 6