Republic of the Philippines

City of Olongapo

GORDON COLLEGE
Olongapo City Sports Complex, East Tapinac, Olongapo City
Tel. No. (047) 224-2089 loc. 314
www.gordoncollege.edu.ph

DISCRETE STRUCTURES 2
Title: PROPOSITIONAL EQUIVALENCES Module No. 2

I. INTRODUCTION
An important type of step used in a mathematical argument is the replacement of a
statement with another statement with the same truth value. Because of this, methods
that produce propositions with the same truth value as a given compound proposition are
used extensively in the construction of mathematical arguments. Note that we will use the
term “compound proposition” to refer to an expression formed from propositional
variables using logical operators, such as p ∧ q.

II. LEARNING OBJECTIVES

After studying this module, you should be able to:
 Differentiate the compound propositions according to possible truth vales;
 Determine whether two compound propositions are logically equivalent;
 Establish equivalence by developing a series of logical equivalences.

III. TOPICS AND KEY CONCEPT

A. COMPOUND PROPOSITIONS ACCORDING TO POSSIBLE TRUTH VALUES
We begin our discussion with a classification of compound propositions.

DEFINITION 1 A compound proposition that is always true, no matter what the

truth values of the propositional variables that occur in it, is called a
tautology. A compound proposition that is always false is called a
contradiction. A compound proposition that is neither a tautology
nor a contradiction is called a contingency.

Tautologies and contradictions are often important in mathematical reasoning.

Example 1 illustrates these types of compound propositions.

EXAMPLE 1
We can construct examples of tautologies and contradictions using one propositional
variable. Consider the truth tables of p ∨ ¬p and p ∧ ¬p shown below. Because p ∨ ¬p
is always true, it is a tautology. Because p ∧ ¬p is always false, it is a contradiction.

TABLE 1 Examples of a Tautology and a Contradiction.

p ¬p p ∨ ¬p p ∧ ¬p

T F T F

F T T F

Prepared by: Mr. Kenneth V. Bautista 1 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

B. LOGICAL EQUIVALENCES
Compound propositions that have the same truth values in all possible cases are
called logically equivalent. We can also define this notion as follows.

DEFINITION 2 The compound propositions p and q are called logically equivalent

if p ↔ q is a tautology. The notation p ≡ q denotes that p and q are
logically equivalent.

Remark: The symbol ≡ is not a logical connective, and p ≡ q is not a compound

proposition but rather is the statement that p ↔ q is a tautology. The symbol ⇔ is
sometimes used instead of ≡ to denote logical equivalence.

One way to determine whether two compound propositions are equivalent is to use a
truth table. In particular, the compound propositions p and q are equivalent if and
only if the columns giving their truth values agree. Example 2 illustrates this method
to establish an extremely important and useful logical equivalence, namely, that of
¬(p ∨ q) with ¬p ∧ ¬q.

This logical equivalence is one of the two De Morgan laws, shown in Table 2, named
after the English mathematician Augustus De Morgan, of the mid-nineteenth century.

TABLE 2 De Morgan’s Laws.

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

EXAMPLE 2
Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent.

Solution: The truth tables for these compound propositions are displayed in Table 3.
Because the truth values of the compound propositions ¬(p ∨ q) and ¬p ∧ ¬q agree
for all possible combinations of the truth values of p and q, it follows that ¬(p ∨ q) ↔
(¬p ∧ ¬q) is a tautology and that these compound propositions are logically
equivalent.

TABLE 3 Truth Tables for ¬(p ∨ q) and ¬p ∧ ¬q.

p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q

T T T F F F F

T F T F F T F

F T T F T F F

F F F T T T T

Prepared by: Mr. Kenneth V. Bautista 2 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

EXAMPLE 3
Show that p → q and ¬p ∨ q are logically equivalent.

Solution: We construct the truth table for these compound propositions in Table 4.
Because the truth values of ¬p ∨ q and p → q agree, they are logically equivalent.

TABLE 4 Truth Tables for ¬p ∨ q and p → q.

p q ¬p ¬p ∨ q p→q

T T F T T

T F F F F

F T T T T

F F T T T

We will now establish a logical equivalence of two compound propositions involving

three different propositional variables p, q, and r. To use a truth table to establish such
a logical equivalence, we need eight rows, one for each possible combination of truth
values of these three variables. We symbolically represent these combinations by
listing the truth values of p, q, and r, respectively. These eight combinations of truth
values are TTT, TTF, TFT, TFF, FTT, FTF, FFT, and FFF; we use this order when we
display the rows of the truth table. Note that we need to double the number of rows
in the truth tables we use to show that compound propositions are equivalent for each
additional propositional variable, so that 16 rows are needed to establish the logical
equivalence of two compound propositions involving four propositional variables,
and so on. In general, 2n rows are required if a compound proposition involves n
propositional variables.

TABLE 5 A Demonstration That p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) Are Logically

Equivalent.

p q r q∧r p ∨ (q ∧ r) p∨q p∨r (p ∨ q) ∧ (p ∨ r)

T T T T T T T T

T T F F T T T T

T F T F T T T T

T F F F T T T T

F T T T T T T T

F T F F F T F F

F F T F F F T F

F F F F F F F F

Prepared by: Mr. Kenneth V. Bautista 3 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

EXAMPLE 4
Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent. This is the
distributive law of disjunction over conjunction.

Solution: We construct the truth table for these compound propositions in Table 5.
Because the truth values of p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) agree, these compound
propositions are logically equivalent.

TABLE 6 Logical Equivalences.

Equivalence Name

p∧T≡p Identity laws

p∨F≡p

p∨T≡T Domination laws

p∧F≡F

p∨p≡p Idempotent laws

p∧p≡p

¬(¬p) ≡ p Double negation law

p∨q≡q∨p Commutative laws

p∧q≡q∧p

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan’s laws

¬(p ∨ q) ≡ ¬p ∧ ¬q

p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p

p ∨ ¬p ≡ T Negation laws
p ∧ ¬p ≡ F

Table 6 contains some important equivalences. In these equivalences, T denotes the

compound proposition that is always true and F denotes the compound proposition
that is always false. We also display some useful equivalences for compound
propositions involving conditional statements and biconditional statements in Tables
7 and 8, respectively.

The associative law for disjunction shows that the expression p ∨ q ∨ r is well defined,
in the sense that it does not matter whether we first take the disjunction of p with q
and then the disjunction of p ∨ q with r, or if we first take the disjunction of q and r
and then take the disjunction of p with q ∨ r. Similarly, the expression p ∧ q ∧ r is well

Prepared by: Mr. Kenneth V. Bautista 4 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

defined. By extending this reasoning, it follows that p1 ∨ p2 ∨ . . . ∨ pn and p1 ∧ p2 ∧ . . .

∧ pn are well defined whenever p1, p2, . . . ,pn are propositions.

Furthermore, note that De Morgan’s laws extend to

¬(p1 ∨ p2 ∨ . . . ∨ pn) ≡ (¬p1 ∧ ¬p2 ∧ . . . ∧¬pn)

and

¬(p1 ∧ p2 ∧ . . . ∧ pn) ≡ (¬p1 ∨ ¬p2 ∨ . . . ∨¬pn)

TABLE 7 Logical Equivalences

Involving Conditional Statements.

p → q ≡ ¬p ∨ q

p → q ≡ ¬q → ¬ p

p ∨ q ≡ ¬p → q

p ∧ q ≡ ¬(p → ¬q)

¬(p → q) ≡ p ∧ ¬q

(p → q) ∧ (p → r) ≡ p → (q ∧ r)

(p → r) ∧ (q → r) ≡ (p ∨ q) → r

(p → q) ∨ (p → r) ≡ p → (q ∨ r)

(p → r) ∨ (q → r) ≡ (p ∧ q) → r

TABLE 8 Logical Equivalences

Involving Biconditional Statements.

p ↔ q ≡ (p → q) ∧ (q → p)

p ↔ q ≡ ¬p ↔ ¬ q

p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)

¬(p → q) ≡ p ∧ ¬q

C. USING DE MORGAN’S LAWS

The two logical equivalences known as De Morgan’s laws are particularly important.
They tell us how to negate conjunctions and how to negate disjunctions. In particular,
the equivalence ¬(p ∨ q) ≡ ¬p ∧ ¬q tells us that the negation of a disjunction is
formed by taking the conjunction of the negations of the component propositions.
Similarly, the equivalence ¬(p ∧ q) ≡ ¬p ∨ ¬q tells us that the negation of a
conjunction is formed by taking the disjunction of the negations of the component
propositions. Example 5 illustrates the use of De Morgan’s laws.

Prepared by: Mr. Kenneth V. Bautista 5 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

EXAMPLE 5
Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has
a laptop computer” and “Heather will go to the concert or Steve will go to the concert.”

Solution: Let p be “Miguel has a cellphone” and q be “Miguel has a laptop computer.”
Then “Miguel has a cellphone and he has a laptop computer” can be represented by
p ∧ q. By the first of De Morgan’s laws, ¬(p ∧ q) is equivalent to ¬p ∨ ¬q.
Consequently, we can express the negation of our original statement as “Miguel does
not have a cellphone or he does not have a laptop computer.”

Let r be “Heather will go to the concert” and s be “Steve will go to the concert.” Then
“Heather will go to the concert or Steve will go to the concert” can be represented by
r ∨ s. By the second of De Morgan’s laws, ¬(r ∨ s) is equivalent to ¬r ∧ ¬s.
Consequently, we can express the negation of our original statement as “Heather will
not go to the concert and Steve will not go to the concert.”

AUGUSTUS DE MORGAN (1806–1871) De Morgan was a noted

teacher who stressed principles over techniques. His students
included many famous mathematicians, including Augusta Ada,
Countess of Lovelace, who was Charles Babbage’s collaborator in his
work on computing machines. (De Morgan cautioned the countess
of lovelace against studying too much mathematics, because it might
interfere with her childbearing abilities!)

D. CONSTRUCTING NEW LOGICAL EQUIVALENCES

The logical equivalences in Table 6, as well as any others that have been established
(such as those shown in Tables 7 and 8), can be used to construct additional logical
equivalences. The reason for this is that a proposition in a compound proposition can
be replaced by a compound proposition that is logically equivalent to it without
changing the truth value of the original compound proposition. This technique is
illustrated in Examples 6–8, where we also use the fact that if p and q are logically
equivalent and q and r are logically equivalent, then p and r are logically equivalent.

EXAMPLE 6
Show that ¬(p → q) and p ∧ ¬q are logically equivalent.

Solution: We could use a truth table to show that these compound propositions are
equivalent (similar to what we did in Example 4). Indeed, it would not be hard to do
so. However, we want to illustrate how to use logical identities that we already know
to establish new logical identities, something that is of practical importance for
establishing equivalences of compound propositions with a large number of variables.
So, we will establish this equivalence by developing a series of 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

Prepared by: Mr. Kenneth V. Bautista 6 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

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 demonstrate 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

A truth table can be used to determine whether a compound proposition is a

tautology. This can be done by hand for a compound proposition with a small number
of variables, but when the number of variables grows, this becomes impractical.

For instance, there are 220 = 1,048,576 rows in the truth value table for a compound
proposition with 20 variables. Clearly, you need a computer to help you determine, in
this way, whether a compound proposition in 20 variables is a tautology. But when
there are 1000 variables, can even a computer determine in a reasonable amount of
time whether a compound proposition is a tautology? Checking every one of the 21000
(a number with more than 300 decimal digits) possible combinations of truth values
simply cannot be done by a computer in even trillions of years.

Furthermore, no other procedures are known that a computer can follow to

determine in a reasonable amount of time whether a compound proposition in such a
large number of variables is a tautology.

We will study questions such as this in the next modules, when we study the
complexity of algorithms.

Prepared by: Mr. Kenneth V. Bautista 7 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

E. 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 satisfiability problem. However, to show that a compound
proposition is unsatisfiable, we need to show that every assignment of truth values to
its variables makes it false. Although we can always use a truth table to determine
whether a compound proposition is satisfiable, it is often more efficient not to, as
Example 9 demonstrates.

EXAMPLE 9
Determine whether each of the compound propositions (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨
¬p), (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r), and (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧
(¬p ∨ ¬q ∨ ¬r) is satisfiable.

Solution: Instead of using truth table to solve this problem, we will reason about truth
values. Note that (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) is true when the three variable p, q,
and r have the same truth value. Hence, it is satisfiable as there is at least one
assignment of truth values for p, q, and r that makes it true. Similarly, note that (p ∨ q
∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is true when at least one of p, q, and r is true and at least one is
false. Hence, (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is satisfiable, as there is at least one
assignment of truth values for p, q, and r that makes it true.

Finally, note that for (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) to

be true, (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) and (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) must both be
true. For the first to be true, the three variables must have the same truth values, and
for the second to be true, at least one of three variables must be true and at least one
must be false. However, these conditions are contradictory. From these observations
we conclude that no assignment of truth values to p, q, and r makes (p ∨ ¬q) ∧ (q ∨
¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) true. Hence, it is unsatisfiable.

F. APPICATIONS OF SATISFIABILITY
Many problems, in diverse areas such as robotics, software testing, artificial
intelligence planning, computer-aided design, machine vision, integrated circuit
design, scheduling, computer networking, and genetics, can be modeled in terms of
propositional satisfiability. Although most applications are quite complex, we can
illustrate how two puzzles can be modeled as satisfiability problems.

IV. TEACHING AND LEARNING MATERIALS RESOURCES

Hardware Device: Desktop Computer/ Laptop/ Mobile Phone
Application Software: GC-LAMP; Google Meet; Facebook

Prepared by: Mr. Kenneth V. Bautista 8 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

V. LEARNING TASKS
EXERCISES:
1. Use truth tables to verify these equivalences.
a. p ∧ T ≡ p
b. p ∨ F ≡ p
c. p ∧ F ≡ F
d. p ∨ T ≡ T
e. p ∨ p ≡ p
f. p ∧ p ≡ p

2. Show that ¬(¬p) and p are logically equivalent.

3. Use a truth table to verify the first De Morgan law.

¬(p ∧ q) ≡ ¬p ∨ ¬q

Prepared by: Mr. Kenneth V. Bautista 9 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.
 Discrete Structures 2: PROPOSITIONAL EQUIVALENCES | Module No. 2

4. Show that each of these conditional statements is a tautology by using truth tables.
a. p → (p ∨ q)
b. (p ∧ q) → (p → q)
c. ¬(p → q) → ¬q

5. Show that ¬(p ∨ ¬(p ∧ q)) is a contradiction without using a truth table.

RUBRIC:
3 2 1 0

Answers all parts of Answers part of the Attempts to answer

Does not answer the
the question correctly question or is the question but is
question
and thoroughly partially correct incorrect

VI. REFERENCE
 Rosen, K. H. (2018). Discrete Mathematics and Its Applications, Eighth Edition.
McGraw-Hill.

Prepared by: Mr. Kenneth V. Bautista 10 | 10

EXCLUSIVE FOR GORDON COLLEGE ONLY.