CUTM
1004
Discrete Mathematics
Module-1
PRESENTED BY:
DIBYANSU SEKHAR DAS(230101120147)
SANJAYA KUMAR PANDA(230101120155)
RUDRA LENKA(230101120156)
YAJNADATTA PATTANAYAK(230101120157)
ASHU KUMAR(230101120161)
Table of contents
Connectives
Propositional
0 and truth
Logic 02
1 values
Truth table of
compound Propositional
03 04
propositions Equivalence
01
Propositional
Logic
• Propositional logic is the study of propositions (true or false statements) and
the ways of combining them (logical operators) to get new propositions.
It is effectively an algebra of propositions.
• A proposition is a declarative sentence (a sentence that declares a fact) that is
either true or false, but not both.
Propositions
1. Riyadh is the capital of Saudi Arabia.
2. 1+1=2
Not Propositions
1. What time is it?
2. Answer this question
02
Connectives and
their Truth
values
Conjunction TRUTH TABLE :
Suppose p and q are propositions p q pq
The conjunction of p and q is written as
pq F F F
The proposition pq is read “p and q”
F T F
T F F
p is the proposition “Today is Friday”
q is the proposition “It is raining today” T T T
The conjunction of p and q is
proposition *If at least one truth value is
false then it is false otherwise
“ Today is Friday and it is raining true.
today”
Disjunction TRUTH TABLE :
Suppose p and q are propositions p q pq
The disjunction of p and q is written as
pq F F F
The proposition pq is read “p or q”
F T T
T F T
p is the proposition “He may go to
gym.” T T T
q is the proposition “He may go to
market.”
*If at least one truth value is
The disjunction of p and q is true then it is true otherwise
proposition false.
Exclusive OR TRUTH TABLE :
Suppose p and q are propositions
The disjunction of p and q is written as p q p⊕q
p⊕q
F F F
The proposition p ⊕ q is read as “p F T T
xor q”
T F T
p is the proposition “You have to do.”
q is the proposition “You have to die.” T T F
The XOR of p and q is proposition *If both truth values are same
“You have to do or you have to die.” then it is false otherwise true.
Negation
Let p is a proposition TRUTH TABLE :
The negation of p is written as p
and
has meaning: “It is not the case P p
that p.”
F T
The proposition p is read as “not P”
T F
“I am good.”
“ It is not the case that I am good.” *It gives the opposite of the
or input truth value.
“I am not good.”
Implication
TRUTH TABLE :
Suppose p and q are propositions
The conditional statement of p and q is pq
written as p q p q
p is the Hypothesis and q is the
conclusion F F T
The proposition p q is read “If p then
F T T
q”
T F F
p is the proposition “You will come” T T T
q is the proposition “I will also come”
The conditional statement of p and q is *If hypothesis is true and
proposition conclusion is false then it is
false otherwise true.
“ If you will come then I will also
Bi-implication
Suppose p and q are propositions TRUTH TABLE :
the biconditional statement of p and q
is written as pq p q pq
The proposition pq is read as “p if
and only if q” F F T
p q is true if both pq and qp are true
F T F
p is the proposition “You can take the
flight.” T F F
q is the proposition “You buy ticket.”
T T T
The biconditional statement of p and q
is proposition
*If both truth values are same
“You can take the flight if and only if
then it is true otherwise false.
You buy ticket .”
03
Truth table of
compound
propositions
Truth table of compound
propositions
Precedence of logical operators :
Construct the Truth table of compound propositions (p q) (p q)
p q q pq pq (pq) (pq)
F F T T F F
F T F F F T
T F T T F F
T T F T T T
04
Proposition
al
Equivalence
Propositional Equivalences
Classification of compound propositions
A compound proposition that is always true is called a tautology. (p p)
A compound proposition that is always false is called a contradiction. (p p)
A compound proposition that is neither a tautology nor a contradiction is called a
contingency.
Logical equivalences :
compound propositions that have the same truth values in all possible
cases are called Logically equivalent.
Compound propositions p and q are Logically equivalent if pq is a
tautology.
logical equivalence :
Propositional Equivalences
Identity laws pTp pFp
Domination laws pFF pTT
Idempotent laws ppp ppp
Double negation law (p) p
Negation laws p p T p p F
Absorption laws p(pq) p p(p q) p
Commutative laws p q q p pqqp
Associative laws (pq)r p(qr) (pq)r p(qr)
De Morgan’s laws (pq) pq (pq) pq
Distributive laws p(qr) (pq)(pr)
p(qr) (pq)(pr)
T denotes the compound proposition that is always true
F denotes the compound proposition that is always false
Thanks!
