Page 51 - Discrete Mathematics and Its Applications

30 1 / The Foundations: Logic and Proofs

logical equivalences, using one of the equivalences in Table 6 at a time, starting with ¬(p → q)
and ending with p ∧¬q. We have the following equivalences.

¬(p → q) ≡¬(¬p ∨ q) by Example 3
≡¬(¬p) ∧¬q by the second De Morgan law
≡ p ∧¬q by the double negation law
▲

EXAMPLE 7 Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧¬q are logically equivalent by developing a series of
logical equivalences.

Solution:We will use one of the equivalences in Table 6 at a time, starting with ¬(p ∨ (¬p ∧ q))
and ending with ¬p ∧¬q.(Note: we could also easily establish this equivalence using a truth
table.) We have the following equivalences.

¬(p ∨ (¬p ∧ q)) ≡¬p ∧¬(¬p ∧ q) by the second De Morgan law
≡¬p ∧[¬(¬p) ∨¬q] by the first De Morgan law
≡¬p ∧ (p ∨¬q) by the double negation law
≡ (¬p ∧ p) ∨ (¬p ∧¬q) by the second distributive law
≡ F ∨ (¬p ∧¬q) because ¬p ∧ p ≡ F
≡ (¬p ∧¬q) ∨ F by the commutative law for disjunction
≡¬p ∧¬q by the identity law for F

Consequently ¬(p ∨ (¬p ∧ q)) and ¬p ∧¬q are logically equivalent. ▲

EXAMPLE 8 Show that (p ∧ q) → (p ∨ q) is a tautology.

Solution: To show that this statement is a tautology, we will use logical equivalences to demon-
strate that it is logically equivalent to T.(Note: This could also be done using a truth table.)

(p ∧ q) → (p ∨ q) ≡¬(p ∧ q) ∨ (p ∨ q) by Example 3
≡ (¬p ∨¬q) ∨ (p ∨ q) by the first De Morgan law
≡ (¬p ∨ p) ∨ (¬q ∨ q) by the associative and commutative
laws for disjunction
≡ T ∨ T by Example 1 and the commutative
law for disjunction
≡ T by the domination law
▲

Propositional Satisfiability

A compound proposition is satisfiable if there is an assignment of truth values to its variables that
makes it true. When no such assignments exists, that is, when the compound proposition is false
for all assignments of truth values to its variables, the compound proposition is unsatisfiable.
Note that a compound proposition is unsatisfiable if and only if its negation is true for all
assignments of truth values to the variables, that is, if and only if its negation is a tautology.
When we find a particular assignment of truth values that makes a compound proposition
true, we have shown that it is satisfiable; such an assignment is called a solution of this particular