03+04. Chapter-1.3

Discrete Mathematics and Its Applications
Chapter 1: The Foundations:

Logic and Proofs
1.3 Propositional Equivalences
1
Introduction
DEFINITION 1
A compound proposition that is always true, no matter what the truth
values of the propositions that occurs 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 or a contradiction is
called a contingency.
Examples of a Tautology and a Contradiction.

p ¬p p ν ¬p p Λ ¬p
T F T F
F T T F
2
Logical Equivalences
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.
 Compound propositions that have the same truth values in all
possible cases are called logically equivalent.
 Example: Show that ¬p ν q and p → q are logically equivalent.
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
3
F F T T T
 Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent.
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
4
 Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent.
5
NA, NO
X 1, + 0
biporit connective
+ 1, X 0
On, An
same jinis +, X
not(not)
OR, ACD
AND
bracket odolbodol
OA, AO man agpich
bracket distribute
OA, AO
6
1,2 1,3 = 1 2,3
1,3 2,3 = 1,2 3

7
Constructing New Logical Equivalences
 Example: Show that ¬(p → q ) and p Λ ¬q are logically equivalent.
Solution:
¬(p → q ) ≡ ¬(¬p ν q) by p → q ≡ ¬p ∨ q
≡ ¬(¬p) Λ ¬q by the second De Morgan law
≡ p Λ ¬q by the double negation law
 Note: The above example can also be done using truth tables.
8
 Example: Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent.
Solution:
¬(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
9
 Example: 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.
(p Λ q) → (p ν q) ≡ ¬(p Λ q) ν (p ν q) by p → q ≡ ¬p ∨ q
≡ (¬ p ν ¬q) ν (p ν q) by the first De Morgan law
≡ (¬ p ν p) ν (¬ q ν q) by the associative and
communicative law for disjunction
≡TνT
≡T
 Note: The above example can also be done using truth tables.
10
Satisfiability
 A compound proposition is satisfiable if there is at least one value that is
true in the truth table.
 A compound proposition is unsatisfiable when there is not even a single
value in the truth table that is true.
 Example: Determine whether the compound propositions (p ∨ ¬q) ∧ (q ∨

¬r) ∧ (r ∨ ¬p) is satisfiable.
 Solution: Due to the V (disjunction) within each individual proposition,
having same truth values ensures that at least one of the propositional
variable within each individual compound proposition will be true.
Therefore, the compound proposition propositions (p ∨ ¬q) ∧ (q ∨ ¬r) ∧
(r ∨ ¬p) will be true and hence, satisfiable as there is at least one
assignment of truth values for p, q, and r that makes it true.
11
Satisfiability
 Example: Determine whether the compound propositions (p ∨ q ∨ r) ∧
(¬p ∨ ¬q ∨ ¬r) is satisfiable.
 Solution: 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 (see Exercise 43 of Section
1.1). 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.
12

03+04. Chapter-1.3

Uploaded by

Copyright:

Available Formats

03+04. Chapter-1.3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

03+04. Chapter-1.3

Uploaded by

Copyright:

Available Formats

Discrete Mathematics and Its Applications

Chapter 1: The Foundations:

1.3 Propositional Equivalences

Examples of a Tautology and a Contradiction.

Truth Tables for ¬p ν q and p → q .

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

1,2 1,3 = 1 2,3

1,3 2,3 = 1,2 3

Solution: To show that this statement is a tautology, we will use logical

 Example: Determine whether the compound propositions (p ∨ ¬q) ∧ (q ∨

 Solution: Note that (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is true when at least one

You might also like