DNF AND CNF

By Maria Ramila Jimenez

 Two formulas may be logically
equivalent, but one may be
easier for someone to
understand or manipulate

Normal Forms
Two special forms disjunctive
for formulas normal form
logically equivalent conjunctive
to a given formula normal form

CSCC 11 Discrete Structures 2

 Disjunctive Normal
Form (DNF)
◦ Consider the following formulas

A: (p→(q˅r)) ↔ (q→p)

and

B: (p˄q) ˅ (p˄¬q˄r) ˅ (¬p˄¬q)

CSCC 11 Discrete Structures 3

 Truth tables for A and B will show
that they are logically equivalent

Disjunctive By some measures, B may look

Normal Form more complicated

(DNF) • A has four logical connectives; B has

nine

However, B may be easier to

understand

CSCC 11 Discrete Structures 4

 B: (p˄q) ˅ (p˄¬q˄r) ˅ (¬p˄¬q)

Explicitly lists three cases to make B

true
Disjunctive • p and q are both T
Normal Form • p and r are T and q is F
• p and q are both F
(DNF) Other combinations of p, q and r, B
is F

Although A is shorter, it is more

complex
CSCC 11 Discrete Structures 5
 B: (p˄q) ˅ (p˄¬q˄r) ˅ (¬p˄¬q)

A formula like B that lists cases that make

Disjunctive the formula have a truth value of T is
called a disjunctive normal form
Normal Form
(DNF) Each of the cases is called a term

DNF is a disjunct of terms that make the

formula T

CSCC 11 Discrete Structures 6

 Let p be a proposition
Disjunctive • p is a positive literal
Normal Form • ¬p is a negative literal
(DNF)
A term is a conjunction
of n literals

CSCC 11 Discrete Structures 7

 Disjunctive Normal Form (DNF)

◦ C: (¬(p→q))→(q˄¬r)

◦ Determine the DNF for C.

CSCC 11 Discrete Structures 8

 ◦ C: (¬(p→q))→(q˄¬r)

Disjunctive
Normal ◦ A formula may have several equivalent
formulas in DNF, but we need a
Form (DNF) systematic way to find one.

CSCC 11 Discrete Structures 9

 ◦ C: (¬(p→q))→(q˄¬r)
Disjunctive
Normal ◦ Solution: First, we need to find the truth

Form (DNF)
table for all interpretations of C.

CSCC 11 Discrete Structures 10

Disjunctive Normal Form (DNF)
C: (¬(p→q))→(q˄¬r)

Interpretation p q r C
I0 T T T T
I1 T T F T
I2 T F T F
I3 T F F F
I4 F T T T
I5 F T F T
I6 F F T T
I7 F F F T

CSCC 11 Discrete Structures 11

 Disjunctive ◦ Next, we construct a term for each
interpretation that is T in that
Normal interpretation and F in all other
interpretations.
Form (DNF)

CSCC 11 Discrete Structures 12

Disjunctive Normal Form (DNF)
C: (¬(p→q))→(q˄¬r)

Interpretation p q r C Matching Term

I0 T T T T p˄q˄r
I1 T T F T p˄q˄¬r
I2 T F T F p˄¬q˄r
I3 T F F F p˄¬q˄¬r
I4 F T T T ¬p˄q˄r
I5 F T F T ¬p˄q˄¬r
I6 F F T T ¬p˄¬q˄r
I7 F F F T ¬p˄¬q˄¬r
CSCC 11 Discrete Structures 13
 ◦ C: (¬(p→q))→(q˄¬r)
Disjunctive
Normal ◦ Now, we construct a disjunction of
terms with one corresponding to each
Form (DNF) interpretation where C is T.

CSCC 11 Discrete Structures 14

Disjunctive Normal Form (DNF)
C: (¬(p→q))→(q˄¬r)

Interpretation p q r C Matching Term

I0 T T T T p˄q˄r
I1 T T F T p˄q˄¬r
I2 T F T F p˄¬q˄r
I3 T F F F p˄¬q˄¬r
I4 F T T T ¬p˄q˄r
I5 F T F T ¬p˄q˄¬r
I6 F F T T ¬p˄¬q˄r
I7 F F F T ¬p˄¬q˄¬r
CSCC 11 Discrete Structures 15
 ◦ C: (¬(p→q))→(q˄¬r)
Disjunctive
Normal ◦ CDNF: (p˄q˄r) ˅ (p˄q˄¬r)
˅ (¬p˄q˄r) ˅ (¬p˄q˄¬r)
Form (DNF) ˅ (¬p˄¬q˄r) ˅ (¬p˄¬q˄¬r)

CSCC 11 Discrete Structures 16

 Conjunctive
Normal Form (CNF)
◦ Consider again the formula A.

A: (p→(q˅r)) ↔ (q→p)

◦ A is logically equivalent to D.

D: (p˅¬q) ˄ (¬p˅q˅r)

CSCC 11 Discrete Structures 17

 ◦ A: (p→(q˅r)) ↔ (q→p)
◦ D: (p˅¬q) ˄ (¬p˅q˅r)

Conjunctive
Normal Form ◦ D is in conjunctive normal form (CNF).
◦ It consists of a conjunction of two formulas that
(CNF) are disjunctions of literals
◦ (p˅¬q)
◦ (¬p˅q˅r)

CSCC 11 Discrete Structures 18

 A clause is a p˅¬q
disjunction of n ¬p˅q˅r
Conjunctive literals

Normal Form
(CNF) Every formula is logically
equivalent to a formula
in CNF

CSCC 11 Discrete Structures 19

 Conjunctive Normal Form (CNF)

E: (¬(P→Q)) → (Q˄¬R) FIND THE CNF FOR E.

CSCC 11 Discrete Structures 20

 Conjunctive
Normal Form (CNF)
◦ Solution: We start by finding a formula in DNF that
is equivalent to ¬E

CSCC 11 Discrete Structures 21

Conjunctive Normal Form (CNF)
E: (¬(p→q)) → (q˄¬r)

Interpretation p q r E
I0 T T T F
I1 T T F F
I2 T F T T
I3 T F F T
I4 F T T F
I5 F T F F
I6 F F T F
I7 F F F F
CSCC 11 Discrete Structures 22
Conjunctive Normal Form (CNF)
E: (¬(p→q)) → (q˄¬r)

Interpretation p q r E Matching term

I0 T T T F p˄q˄r
I1 T T F F p˄q˄¬r
I2 T F T T p˄¬q˄r
I3 T F F T p˄¬q˄¬r
I4 F T T F ¬p˄q˄r
I5 F T F F ¬p˄q˄¬r
I6 F F T F ¬p˄¬q˄r
I7 F F F F ¬p˄¬q˄¬r
CSCC 11 Discrete Structures 23
Conjunctive ◦ E¬DNF: (p˄¬q˄r) ˅ (p˄¬q˄¬r)

Normal Form ◦ E: ¬((p˄¬q˄r) ˅ (p˄¬q˄¬r))

(CNF)
◦ E: ¬(p˄¬q˄r) ˄ ¬(p˄¬q˄¬r)

◦ ECNF: (¬p˅q˅¬r) ˄ (¬p˅q˅r)

CSCC 11 Discrete Structures 24

 Exercises

G: (P↔Q) ↔ R FIND THE DNF AND CNF

FOR G

CSCC 11 Discrete Structures 25

END

CSCC 11 Discrete Structures 26