Scribd
Upload
31 views

DM 2

This document provides an overview of topics in discrete mathematics including propositional logic, translations of English sentences to propositional logic, applications of propositional logic such as reasoning and circuit design, and propositional equivalences including tautologies, contradictions, contingencies, and logically equivalent statements. Examples are provided to demonstrate different propositional logic concepts such as translations, implications, distributions, De Morgan's laws, and showing a statement is a tautology.

Uploaded by

MUHAMMAD MUSTAFA AWAN
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views

DM 2

This document provides an overview of topics in discrete mathematics including propositional logic, translations of English sentences to propositional logic, applications of propositional logic such as reasoning and circuit design, and propositional equivalences including tautologies, contradictions, contingencies, and logically equivalent statements. Examples are provided to demonstrate different propositional logic concepts such as translations, implications, distributions, De Morgan's laws, and showing a statement is a tautology.

Uploaded by

MUHAMMAD MUSTAFA AWAN
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

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

You might also like