Transcript Logical 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/11/2017
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 24 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/11/2017
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/11/2017
3