04[Pick the date]
MAT1003 Discrete Mathematical Structures
Dr. Varunkumar Merugu
Assistant Professor
Department of Mathematics
School of Advanced Sciences
VIT-AP University, Amaravati
Andhra Pradesh, India
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
Statement/Propositional Logic
• Statements/Propositions
• Truth values
• Truth Tables
• Connectives
• Negation
• Conjunction
• Disjunction
• Conditional(Implication); contrapositive, inverse, converse
• Biconditional
• Exclusive disjunction
• NAND
• NOR
• Problems
• Well formed Formulas
• Examples of WFF's and non WFF's
• Problems
• Tautology, Contradiction, Contingency
• Equivalence Implications
• Logical Equivalences
• Equivalent Formulas
• Problems
• Normal Forms
• DNF
• CNF
• PDNF
• PCNF
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
Conditional Statement [If…Then] [→]
If p and q are any 2 statements/propositions, then the statement p →q which is read as “if p,
then q ” is a conditional statement or implication.
Here, p is called antecedent and q is called consequence. The p →q is defined by the truth
table shown below.
p q p →q q →p
T T T T
T F F T
F T T F
F F T T
Example:
p : It is hot.
q : 2+3=5.
p → q : If it is hot, then 2+3=5.
For example, let us consider the statement.
“If I get up at 5 A.M., I will go for a walk”, which may be represented as p → q and
considered as a contract.
If p is true and q is also true, the contract is not violated and so ‘p → q’ is true.
If p is true and q is false (viz., I get up at 5 A.M., but I do not go for a walk), the contract is
violated and so ‘p → q’ is false.
If p is false and whether q is true or false (viz., when I have not got up at 5 A.M; I may or may
not go for a walk), the contract is not violated and so ‘p → q’ is true.
Different ways of expressing p →q
• if p, then q
• if p, q
• q unless ┐p
• q if p
• q whenever p
• q follows from p
• p implies q
• p only if q
• q when p
• p is sufficient for q
• q is necessary for p
• a necessary condition for p is q
• a sufficient condition for q is p
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
Converse, Contrapositive, and Inverse
Given an if-then statement "if p , then q (p →q )," we can create three related statements:
Statement If p , then q (p →q )
Converse If q, then p
Inverse If not p, then not q
Contrapositive If not q, then not p
A conditional statement consists of two parts, a hypothesis in the “if” clause and a conclusion
in the “then” clause.
For example, “If it rains, then they cancel school.” "It rains" is the hypothesis. "They cancel
school" is the conclusion.
To form the converse of the conditional statement, interchange the hypothesis and the
conclusion.
The converse of "If it rains, then they cancel school" is "If they cancel school, then it rains."
To form the inverse of the conditional statement, take the negation of both the hypothesis
and the conclusion.
The inverse of “If it rains, then they cancel school” is “If it does not rain, then they do not
cancel school.”
To form the contrapositive of the conditional statement, interchange the hypothesis and the
conclusion of the inverse statement.
The contrapositive of "If it rains, then they cancel school" is "If they do not cancel school,
then it does not rain.”
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
Biconditional Statement [If and only if or Iff ] [↔]
If p and q are any 2 statements/propositions, then the statement p ↔q which is read as “p if
and only if q ” is a biconditional statement.
The p ↔q is defined by the truth table shown below.
p q p ↔q
T T T
T F F
F T F
F F T
Example:
(i) p : Shiva is rich.
q : Shiva is happy.
p ↔ q : Shiva is rich if and only if Shiva is happy.
The symbol ↔ is a combination of → and ⟵.
Biconditional proposition, which is true when p and q have the same truth values and is
false otherwise.
It is easily verified that ‘p ↔ q’ is true when both the conditionals p ↔ q and q ↔ p are true.
This is the reason for the symbol ↔ which is a combination of → and ⟵.
Alternatively, ‘p ↔ q’ is also expressed as ‘p iff q’ and ‘p is necessary and sufficient for q’.
Some alternative ways “p if and only if q” is expressed in English:
• p is necessary and sufficient for q
• if p then q , and conversely
• p iff q
Problems:
1. Construct the truth table for p→ ┐q OR p→ ~q OR P→ ┐Q.
Sol: Rows=2^2=4
p q ┐q p→ ┐q
T T F F
T F T T
F T F T
F F T T
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
2. Construct the truth table for compound proposition: (p → q) ↔(┐p→ ┐q).
p q ┐p ┐q p→ q ┐p→ ┐q (p → q) ↔(┐p→ ┐q)
T T F F T T T
T F F T F T F
F T T F T F F
F F T T T T T
3. Give the contrapositive statement of the statement, “If there is rain,
then I buy an umbrella".
Sol:
Let p: “There is rain”
and q: “I buy an umbrella".
Then the given statement is p → q.
Its contrapositive is : ┐q→ ┐p.
4. What are the contrapositive, the converse, and the inverse of the
following conditional statement?
“If you work hard, then you will be rewarded".
Sol: p: You work hard.
q: You will be rewarded.
┐p: You will not work hard.
┐q : You will not be rewarded.
Converse: q → p: If you will be rewarded, then you work hard.
Inverse: ┐p→ ┐q : If you will not work hard, then you will not
be rewarded.
Contrapositive: ┐q→ ┐p : If you will not be rewarded, then you
will not work hard.
Then the given statement is p → q.
Its contrapositive is : ┐q→ ┐p.
5. Construct a truth table for the compound proposition
(p →q) ↔(q → p).
p q p→ q q→ p (p → q) ↔ (q→ p).
T T T T T
T F F T F
F T T F F
F F T T T
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
6. Construct a truth table for the compound proposition
(p →q) →(p → r).
Sol. Rows=2^3=8
p q r p→ q p→ r (p → q) ↔ (p→ r).
T T T T T
T T F T F
T F T F T
T F F F F
F T T T T
F T F T T
F F T T T
F F F T T
Problems on truth tables:
Construct a truth tables for the compound propositions
1. (p ∨ q) ∧ ~(p ∧ q)
2. (p ∧ q) → q
3. ~p ↔ (q ∧ (~ (r ∨ ~p)))
4. (p ∧ q) → ~r
5. (p → q) ↔ (~p → ~q)
6. (p →q) →(p → r).
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
7. Construct a truth table for each of the following compound propositions:
Dr. Varunkumar Merugu VIT-AP University Andhra Pradesh
