CMP-101
Discrete Mathematics Topics
Book
• Discrete Mathematics and Its Applications:
With Combinatory and Graph Theory
By Kenneth H. Rosen, Kamala Krithivasan
Chapter 1 Section 1.2 Propositional Equivalences
Applications of propositional logic
1. Translation of English sentences
2. Inference and reasoning:
– new true propositions are inferred from
existing ones
– Used in Artificial Intelligence:
• Rule based (expert) systems
3. Design of logic circuit
Translation
• Example: You can have free coffee if you are
senior citizen and it is a Tuesday
Step 1 : find logical connectives
Translation
• Example: You can have free coffee if you are
senior citizen and it is a Tuesday
Step 2: break the sentence into basic
propositions
Translation
• Example:
You can have free coffee if you are senior citizen
a b
and it is a Tuesday.
c
Step 3: rewrite the sentence in propositional
logic
bɅc→a
Translating English Sentences
Example:
“You can access the Internet from campus only if
you are a computer science major or you are not
a freshman.”
Translating English Sentences
Example:
“You can access the Internet from campus only if
you are a computer science major or you are not
a freshman.”
Translating English Sentences
Example:
“You can access the Internet from campus only if
a
you are a computer science major or you are
b c
not a freshman.”
a → (b V ¬c)
Propositional Equivalences
Equivalences can be used in proofs. A
proposition or its part can be replaced with
another proposition with the same truth value.
Tautology
• A compound proposition that is always true
for all possible truth values of the propositions
is called a tautology.
• p ∨ ¬p is always true, it is a tautology.
P ¬p p ∨ ¬p
T F T
F T T
Contradiction
• A compound proposition that is always false for
all possible truth values of the propositions is
called a contradiction.
• P Ʌ ¬p is always true, it is a contradiction.
• Use truth table to show P ¬p p Ʌ ¬p
that (p ∧ ~q) ∧(~p ∨ q)
T F F
is a contradiction.
F T F
Contingency
• A compound proposition that is neither a
tautology nor a contradiction is called a
contingency.
• Example: P v ¬q
Logically Equivalent
• If two compound statements always have same
truth values, then we say that they are logically
equivalent.
• The notation p ≡ q denotes that p and q are
logically equivalent.
• ≡ is logically equivalent sign
• The compound propositions p and q are called
logically equivalent if p ↔ q is a tautology.
• Large No. of variable as 220 = 1,048,576 rows
Example
• ~ (~ p ) is logically equivalent p
Double Negative Property ~(~p) ≡ p
P ~p ~(~p)
T F T
F T F
~(~p) ≡ p
Example:
• “It is not true that I am not happy.”
Solution:
• Let p = “I am happy”
• then ~ p = “I am not happy”
• and ~ ( ~ p) = “It is not true that I am not happy”
• Since ~ ( ~ p) ≡ p
• Hence the given statement is equivalent to “I am
happy”
Example
Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically
equivalent.
Example (Implication law.)
• Show that p → q and ¬p ∨ q are logically
equivalent.
Example
Show that ~ (p ∧ q) and ~ p ∧ ~ q are logically
equivalent
Example (Distributive laws.)
• Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are
logically equivalent. This is the distributive
law of disjunction over conjunction.
Example (Commutative)
P= Sam is rich.
Q= Sam is happy.
P∨Q≡Q∨P
“Sam is rich or happy” ≡ “Sam is happy or rich”.
P∧Q≡Q∧P
“Sam is rich and happy” ≡ “Sam is happy and rich”.
Example (De Morgan’s law)
P= Sam is rich.
Q= Sam is happy.
￢(P ∨ Q) ≡ ￢P ∧ ￢Q
“It is not the case that Sam is rich or happy” is
equivalent to “Sam is not rich and he is not happy”
￢(P ∧ Q) ≡ ￢P ∨ ￢Q
“It is not the case that Sam is rich and happy” is
equivalent to “Sam is not rich or he is not happy”
Example
Show that ￢(p → q) and p ∧￢q are logically
equivalent.
We have the following equivalences.
• ￢(p → q) ≡ ￢(￢p ∨ q) implication law
• ≡ ￢(￢p)∧￢q second De Morgan law
• ≡ p ∧￢q double negation law
Example
Example: Show (p Ʌ q) → p is a tautology.
Proof:
(p Ʌ q) → p ≡ ¬(p Ʌ q) V p implication
≡[¬p V ¬q] V p De Morgan
≡ [¬q V ¬p] V p Commutative
≡ ¬q V [ ¬p V p ] Associative
≡ ¬q V [ T ] negation
≡ T Domination
