Propositional Equivalences
Course Code: CSC 1204 Course Title: Discrete Mathematics
Dept. of Computer Science
Faculty of Science and Technology
Lecturer No: 3 Week No: 2 Semester: FALL 23-24
Lecturer: MD SAJIDD BIN-FAISAL (sajid@[Link])
Lecture Outline
1.2 Propositional Equivalences
• Tautology
• Contradiction
• Contingence
• Logical Equivalences
Objectives and Outcomes
• Objectives: To understand the terms Tautology, Contradiction,
Contingence with examples, to understand the standard logical
equivalences, to determine whether a compound proposition is a
Tautology or Contradiction, to determine whether two compound
propositions are logically equivalent.
• Outcomes: Students are expected to be able to write the definitions
of Tautology, Contradiction and Contingency with examples, be able
to determine whether a compound proposition is a Tautology or
Contradiction using a Truth Table and standard logical equivalences,
be able to determine whether two compound propositions are
logically equivalent using a Truth Table and logical equivalences.
Tautology
Tautology: A compound proposition that is always
true is called a tautology.
Examples:
a) p ¬p
b) The professor is either a woman or a man
c) People either like watching TV or they don’t
Contradiction
Contradiction: A compound proposition that is always
false is called a contradiction.
Examples:
a) p ¬p
b) x is prime and x is an even integer greater than 8
c) All men are good and all men are bad
Examples of Tautology and
Contradiction
Contingency
Contingency: A compound proposition that is neither a
tautology nor a contradiction is called a contingency.
In other words, a compound proposition whose truth
value is not constant is called a contingency.
Examples:
a) p ¬p
b) p
c) ¬p
How to determine whether a compound
proposition is a Tautology or Contradiction?
• We can determine whether a compound
proposition is a Tautology or contradiction it in
two ways:
1) Using a truth table – The easiest way to see if a
compound proposition is a tautology or
contradiction is to use a truth table. Show that the
compound proposition is always true
2) Using (laws of) Logical Equivalences
Tautology : Example
Show that [¬p (p q )]q is a tautology using a
Truth Table
Solution
p q ¬p p q ¬p (p q ) [¬p (p q )]q
T T
T F
F T
F F
Solution
p q ¬p p q ¬p (p q ) [¬p (p q )]q
T T F
T F F
F T T
F F T
Solution
p q ¬p p q ¬p (p q ) [¬p (p q )]q
T T F T
T F F T
F T T T
F F T F
Solution
p q ¬p p q ¬p (p q ) [¬p (p q )]q
T T F T F
T F F T F
F T T T T
F F T F F
Solution
p q ¬p p q ¬p (p q ) [¬p (p q )]q
T T F T F T
T F F T F T
F T T T T T
F F T F F T
Since the truth table shows all the true values of compound proposition
[¬p (p q )]q are true(T), so it is a tautology.
Class Work
1) Determine whether ¬ (p q) p is a tautology or
contradiction.
2) Determine whether p (q ¬p) is a tautology or
contradiction.
Logical Equivalences
• Compound propositions that have the same truth
values in all possible cases are called logically
equivalent.
• Definition : Compound propositions p and q are
logically equivalent if p q is a tautology (denoted by
p q or p q )
How to determine whether two compound
propositions are logically equivalent?
• We can determine whether two compound
propositions are logically equivalent in two ways:
1) Using a Truth Table
2) Using (laws of ) Logical Equivalences
Using a Truth Table to determine whether two
compound propositions are logically equivalent
• Two compound propositions are logically equivalent if they
always have the same truth values in the corresponding rows.
• Construct a truth table for the given two compound propositions
[in one table]
• If the truth values of both of the compound propositions are
same in the corresponding rows, then they are logically
equivalent.
• If the true values of both of the compound propositions are
different in one or more rows, then they are NOT logically
equivalent.
Example 1
Show that p q is logically equivalent to (p q) (q p)
Since the truth values of both of the compound propositions are same in the
corresponding rows, they are logically equivalent.
Class Work
Show that p (q r ) and (p q ) (p r ) are logically
equivalent
Solution
Since the truth values of both of the compound propositions are same in the
corresponding rows, they are logically equivalent.
Logical Equivalences
Table 6 ( page 24 ) Rosen, 7th edition
A very Useful Logical Equivalence(ULE)
pq¬pq
Example 1
Show that ¬(p q) and p ¬ q are logically equivalent.
Solution:
by ULE
Example 7 (page 26)
Solution:
Exercise
Show that (¬p (p q ))q is a tautology using a
series of logical equivalences.
Solution
(¬p (p q ))q
( (¬p p)(¬p q) ) q Distributive Law
( F (¬p q))q Negation Law
(¬p q )q Identity Law
¬ (¬p q ) q ULE
(¬(¬p) ¬q ) q De Morgan’s Law
( p ¬q ) q Double Negation Law
p (¬q q ) Associative Law
pT Domination Law
T So, (¬p (p q ))q is a tautology.
Summary
• What is Tautology and Contradiction? What is Contingency?
• How to show/determine whether two compound propositions are logically
equivalent?
• Using a truth table
• Using logical equivalences
• How to show whether a compound proposition is a tautology?
• Using a truth table
• Using logical equivalences
• Note: Make sure you learn the important Logical Equivalences in Table 6 (page
24) & ULE ( p q ¬ p q )
• Practice @ Home: Relevant Odd-numbered Exercises (e.g. 1, 3, 7, 9, 11, 15, 17 )
Books
• Discrete Mathematics and its applications with combinatorics and graph
theory (7th edition) by Kenneth H. Rosen [Indian Adaptation by KAMALA
KRITHIVASAN], published by McGraw-Hill
References
1. Discrete Mathematics, Richard Johnsonbaugh, Pearson education, Inc.
2. Discrete Mathematical Structures, Bernard Kolman, Robert C. Busby,
Sharon Ross, Prentice-Hall, Inc.
3. SCHAUM’S outlines Discrete Mathematics(2nd edition), by Seymour
Lipschutz, Marc Lipson
