Propositional Logic

Snehal Kamalapur
Department of Computer Engineering
K K Wagh Institute of Engineering Education and Research ,
Nashik
Lecture 6

Topic Name: Normal Form

Disjunctive Normal Form(DNF)
&
Conjunctive Normal Form (CNF)

2
Normal Form

There are four kinds of Normal forms

1. Disjunctive Normal Form
2. Conjunctive Normal Form
3. Principal Disjunctive Normal Form
4. Principal Conjunctive Normal Form

3
Disjunctive Normal Form

▪ A formula is in disjunctive normal form (DNF) if it is a disjunction of

conjunction of literals.
▪ A propositional variable or its negation is called a literal
▪ A term containing a conjunction of literals is also known as minterms or
product term
▪ Example of minterms:
1. x
2. X ^ y
3.~ x ^ y
4.~ x ^ ~y
In disjunctive normal form, minterms are separated by v (disjunction)

4
 ▪ The following are in disjunctive normal form
1. (p^q) v (~p^~q)
2.(~p^q) v (p^~r) v (~q^~r^~s)

5
Conjunctive Normal Form

▪ A formula is in conjunctive normal form (CNF) if it is a conjunction of

disjunction of literals.
▪ A term containing a disjunction of literals is also known as maxterm .
▪ Example of maxterms:
1. x
2. X v y
3.~ x v y
4.~ x v~y
In conjunctive normal form, maxterms are separated by ^ (conjunction)

6
 ▪ The following are in conjunctive normal form
1. (pvq) ^ (~pv~q)
2.(~pvq) ^ (pv~r) ^ (~qv~rv~s)

7
METHODS FOR FINDING DNF

▪ Truth table method

▪ Using algebraic manipulation

8
Truth table method

Let p be a statement formula containing n variable x1, x2 ...xn. .We can

find its DNF form its truth table :
1. For each row of the truth table for which P is true , we construct a
minterm(y1 ^ y2 ^ yn) where we take
yk = xk If kth position in that row contains T
yk= ~xk If kth position in that row contains F
2.The disjunction of the minterm is the required formula

9
Example 1

▪ Express p 🡨(q ^ r) in disjunctive normal form.

Solution:-
▪ Step 1: we construct a truth table.

10
Example 1

▪ Express p →(q ^ r) in disjunctive normal form.

Solution:-
▪ Step 1: we construct a truth table.
p q r q^r P🡪(q^r)
F F F F T
F F T F T
F T F F T
F T T T T
T F F F F
T F T F F
T T F F F
T T T T T

11
Step 2:
Rows for which above statement is true are 1,2,3,4,8
▪ In row 1 p,q,r are all F, so ~p^~q^~r is required minterm
▪ row 2 p,q are F and r is T, so ~p^~q^r is required minterm
▪ row 3 p,r are F and q is T, so ~p^q^~r is required minterm
▪ row 4 p is F, q, r are T, so ~p^q^r is required minterm
▪ row 8 p,q,r are all T, so p^q^r is required minterm

12
Step 3:
We can find DNF of p→(q ^ r) by taking disjunction of minterms, i.e.
(~p^~q^~r) v (~p^~q^r) v (~p^q^~r) v (~p^q^r) v (p^q^r)

13
Example 1

▪ Express p →(q ^ r) in conjunctive normal form.

Solution:-
▪ Step 1: we construct a truth table.

14
Example 1
▪ Express p 🡨(q ^ r) in conjunctive normal form.
Solution:-
▪ Step 1: we construct a truth table.

p q r q^r P🡪(q^r)
F F F F T
F F T F T
F T F F T
F T T T T
T F F F F
T F T F F
T T F F F
T T T T T 15
Step 2:
Rows for which above statement is false are 5,6,7
▪ In row 5 p is T and q,r are F, so (~p v q v r) is required maxterm
▪ row 6 p is T, Qis F and r is T, so (~p v q v ~r) is required maxterm
▪ row 7 p,q are T and r is F , so(~p v ~q v r) is required maxterm

16
Step 3:
We can find CNF of p→(q ^ r) by taking conjunction of maxterms, i.e.
(~p v q v r) ^(~p v q v ~r)^ (~p v ~q v r)

17
Using algebraic manipulation

Find conjunctive and disjunctive normal forms for the following without
using truth table :
1. (p^q) ^(q→p) 2. ((p^(p→q))→q)

Solution :

18
Using algebraic manipulation

Find conjunctive and disjunctive normal forms for the following without using
truth table :
1. (p^q) ^(q🡨p) 2. ((p^(p🡨q))🡨q)

Solution :
1. (p^q) ^ (q 🡨p)
q 🡨p is logically equivalent to ~ q v p
therefore (p ^q) ^ (q🡨p) = (p^q) ^ (~q v p)
=((p^q)^ ~ q) v ((p ^ q) ^ p) //Distributive
= (p^f) v (p^q)
= F v (p^ q)
= p ^q
= (p^q) //DNF
= (p)^(q) //CNF

19
2. ((p ^ (p🡨q))🡨q
= ((p ^ (~p v q))) 🡨 q
= ((p^~p)v (p^ q)) 🡨 q
=(f v (p ^ q )) 🡨 q
=(p ^ q) 🡨 q
=~(p ^ q) v q
=~ p v ~q v q
= ~p v t
=T
=T //CNF
=T //DNF

20
Example

Obtain DNF of (p→ q) ^ (~p ^ q)

Solution: =(~p v q) ^(~p ^ q)
= (~p ^ q) ^ (~p V q)
=((~p ^ q) ^~p) v ((~p ^q) ^ q /distributive
=(~p ^ q) v (~p ^ q)
=(~p ^ q) /DNF , is a minterm

21
H.W

1.Obtain conjunctive normal form of

i) (~p→r) ^(p→q)
ii) (p^q) v (~p^q^r)

2. Obtain the conjunctive and disjunctive normal form of the

propositions given below :
i) (P^Q) v (~P^Q)
ii) (p v ~q) 🡨q

22
3. Obtain the disjunctive normal form of the following :
i) p v (~p 🡨(q v (q 🡨 ~r)))
ii) p ^ ( p🡨 q)

23
Find DNF of
((p 🡨 q) ^ ( q 🡨p)) v p
Solution: = (( ~p v q) ^ (~q v p)) v p
=(~p ^ ~q) v F v F v (p^ q) v p
= (~ p ^ ~ q) v ( p ^ q) v p
= (~ p ^ ~ q) v p /DNF

24
Find CNF of
p🡨>~(~p v ~q)
Solution: = p🡨> (~p v ~q)
=(~p v (~p v ~q)) ^ (p v ~(~p v q))
= (~p v ~ q) ^ ( p v ( p ^ q))
=(~ p v ~ q) ^ p // CNF

25
 Propositional Logic

Snehal Kamalapur
Department of Computer Engineering
K K Wagh Institute of Engineering Education and Research ,
Nashik

7th Sept 2021

Lecture 8

Topic: Mathematical Induction

27
Principle of Mathematical Induction

▪ Mathematical induction is an approach where we generalise a

particular solution
▪ It is used to establish correctness of a statement involving natural
number
▪ It is a mathematical technique which is used to prove a statement , a
formula or a theorem is true for every natural number

28
29
Mathematical induction proves that we can climb as high as we hike on
a ladder, by proving that we can climb onto the bottom rung (the
basis) and that from each rung we can climb up to the next one (the
step).

30
Proof by mathematical induction consists of three basic steps. If the
statement p is to be proven then:
1. Show that p is true for some particular integer n0, this is called the
basis.
2. Assume p is true for some particular integer k >= n0 this is called
induction hypothesis.
3. Prove p is true for n=k +1 ,this is called induction step.

31
EXAMPLE 1

Show that if n is a positive integer, then

1 + 2 +··· n = n(n+1) 2

32
EXAMPLE 1

Show that if n is a positive integer, then

1 + 2 +··· n = n(n+1) 2
Solution::
Let P (n) be the proposition that the sum of the first n positive integers,
1 + 2 +··· n = n(n+1) 2 , is n(n + 1)/2.
We must do two things to prove that P (n) is true for n = 1, 2, 3,....
Namely, we must show that P (1)is true and that the conditional
statement P (k)implies P (k + 1) is true for k = 1, 2, 3,....

33
BASIS STEP: P (1) is true, because 1 = 1(1 + 1)/2
(The left-hand side of this equation is 1 because 1 is the sum of the first
positive integer. The right-hand side is found by substituting 1 for n in
n(n + 1)/2.)

34
BASIS STEP: P (1) is true, because 1 = 1(1 + 1)/2
(The left-hand side of this equation is 1 because 1 is the sum of the first
positive integer. The right-hand side is found by substituting 1 for n in
n(n + 1)/2.)
INDUCTIVE STEP: For the inductive hypothesis we assume that P (k)
holds for an arbitrary positive integer k. That is, we assume that
1 + 2 +··· k = k(k+1) 2

35
36
37
1 + 3 + 5+· · ·+(2n − 1) = n2

38
 1 + 3 + 5+· · ·+(2n − 1) = n2
BASIS STEP: P(1) states that the sum of the first one odd positive integer
is 12. This is true
because the sum of the first odd positive integer is 1. The basis step is
complete.

39
INDUCTIVE STEP: To complete the inductive step we must show that the
proposition
P(k) → P(k + 1) is true for every positive integer k. To do this, we first
assume the inductive hypothesis. The inductive hypothesis is the
statement that P(k) is true for an arbitrary positive integer k, that is,
1 + 3 + 5+· · ·+(2k − 1) = k2
.1 + 3 + 5+· · ·+(2k − 1) + (2k + 1) =(k+1)2
.1 + 3 + 5+· · ·+(2k − 1) + (2k + 1) = [1 + 3+· · ·+(2k − 1)] + (2k + 1)
= k2 + (2k+1)
= k2 + 2k+1
= (k+1)2

40
41