Disjunctive and Conjunctive
Normal Forms
Chapter 2, Section 8
Conjunction
Definition 3.8.1
(a) A conjunction of formulas is a formula
(3.59) (· · · (𝜙1 ∧ 𝜙2 ) ∧ · · · ) ∧ 𝜙𝑛 )
where 𝜙1 , ⋯ , 𝜙𝑛 are formulas; these 𝑛 formulas are called the conjuncts of
the conjunction. We allow 𝑛 to be 1, so that a single formula is a conjunction
of itself. We abbreviate (3.59) to
(𝜙1 ∧ · · · ∧ 𝜙𝑛 )
leaving out all but the outside parentheses.
Disjunction
Definition 3.8.1
(b) A disjunction of formulas is a formula
(3.60) (· · · (𝜙1 ∨ 𝜙2 ) ∨ · · · ) ∨ 𝜙𝑛 )
where 𝜙1 , ⋯ , 𝜙𝑛 are formulas; these 𝑛 formulas are called the disjuncts of
the disjunction. We allow 𝑛 to be 1, so that a single formula is a disjunction
of itself. We abbreviate (3.60) to
(𝜙1 ∨ · · · ∨ 𝜙𝑛 )
leaving out all but the outside parentheses.
Negation and Literal
Definition 3.8.1
(c) The negation of a formula 𝜙 is the formula
(3.61) ¬𝜙
We abbreviate (3.61) to
¬𝜙
A formula that is either an atomic formula or the negation of an atomic
formula is called a literal .
Generalization
Remark 3.8.2
It is easily checked that (d) and (e) of Definition 3.5.6 generalize as
follows :
(d) 𝐴∗ 𝜙1 ∧ · · · ∧ 𝜙𝑛 = T if and only if 𝐴∗ 𝜙1 = ⋯ = 𝐴∗ 𝜙𝑛 = T.
(e) 𝐴∗ 𝜙1 ∨ · · · ∨ 𝜙𝑛 = T if and only if 𝐴∗ 𝜙𝑖 = T for at least one 𝑖.
The Function 𝜙
Definition 3.8.3
Let 𝜎 be a signature and 𝜙 a formula of LP(𝜎). Then 𝜙 determines a
function 𝜙 from the set of all 𝜎-structures to the set T, F of truth
values, by :
𝜙 𝐴 = 𝐴∗ (𝜙) for each 𝜎-structure 𝐴.
This function 𝜙 is really the same thing as the head column of the
truth table of 𝜙, if you read a T or F in the 𝑖-th row as giving the value
of 𝜙 for the 𝜎-structure described by the 𝑖-th row of the table.
Post’s Theorem
The following theorem can be read as ‘Every truth table is the truth
table of some formula’.
Theorem 3.8.4 (Post’s Theorem)
Let 𝜎 be a finite non-empty signature and 𝑔 a function from the set of
𝜎-structures to {T, F}. Then there exits a formula 𝜓 of LP(𝜎) such that
𝑔= 𝜓.
Example
Example 3.8.5
We find a formula to complete the truth table
𝒑𝟏 𝒑𝟐 𝒑𝟑 ?
T T T F
T T F T
T F T T
T F F F
F T T T
F T F F
F F T F
F F F F
Example (continued)
Example 3.8.5
There are three rows with value T. The formula 𝜓𝐴1 is 𝑝1 ∧ 𝑝2 ∧ ¬𝑝3 .
The formula 𝜓𝐴2 is 𝑝1 ∧ ¬𝑝2 ∧ 𝑝3 . The formula 𝜓𝐴3 is ¬𝑝1 ∧ 𝑝2 ∧ 𝑝3 .
So the required formula is
(𝑝1 ∧ 𝑝2 ∧ ¬𝑝3 ) ∨ (𝑝1 ∧ ¬𝑝2 ∧ 𝑝3 ) ∨ (¬𝑝1 ∧ 𝑝2 ∧ 𝑝3 ).
Disjunctive and Conjunctive Normal Forms
Definition 3.8.6
• A basic conjunction is a conjunction of one or more literals, and a basic
disjunction is a disjunction of one or more literals. A single literal counts as
a basic conjunction and a basic disjunction.
• A formula is in disjunctive normal form (DNF) if it is a disjunction of one
or more basic conjunctions.
• A formula is in conjunctive normal form (CNF) if it is a conjunction of one
or more basic disjunctions.
Example
Example 3.8.7
(1)
𝑝1 ∧ ¬𝑝1
is a basic conjunction, so it is in DNF. But also 𝑝1 and ¬𝑝1 are basic
disjunctions, so the formula is in CNF too.
(2)
(𝑝1 ∧ ¬𝑝2 ) ∨ (¬𝑝1 ∧ 𝑝2 ∧ 𝑝3 )
is in DNF.
Example (continued)
Example 3.8.7
(3) Negating the formula in (2), applying the De Morgan Laws and
removing double negations gives
¬((𝑝1 ∧ ¬𝑝2 ) ∨ (¬𝑝1 ∧ 𝑝2 ∧ 𝑝3 ))
eq ¬(𝑝1 ∧ ¬𝑝2 ) ∧ ¬(¬𝑝1 ∧ 𝑝2 ∧ 𝑝3 )
eq (¬𝑝1 ∨ ¬¬𝑝2 ) ∧ (¬¬𝑝1 ∨ ¬𝑝2 ∨ ¬𝑝3 )
eq (¬𝑝1 ∨ 𝑝2 ) ∧ (𝑝1 ∨ ¬𝑝2 ∨ ¬𝑝3 )
This last formula is in CNF.
Existence of DNF and CNF
Theorem 3.8.8
Let 𝜎 be a non-empty finite signature. Every formula 𝜙 of LP(𝜎) is
logically equivalent to a formula 𝜙 𝐷𝑁𝐹 of LP(𝜎) in DNF, and to a
formula 𝜙 𝐶𝑁𝐹 of LP(𝜎) in CNF.
Corollary 3.8.9
Let 𝜎 be any signature (possibly empty). Every formula 𝜙 of LP(𝜎) is
logically equivalent to a formula of LP(𝜎) in which no truth function
symbols appear except ∧, ¬ and ⊥.
Satisfiability of Formulas in DNF
A formula in DNF is satisfiable if and only if at least one of its disjuncts is
satisfiable. Consider any one of these disjuncts; it is a basic conjunction
𝜙1 ∧ · · · ∧ 𝜙𝑚 ,
This conjunction is satisfiable if and only if there is a 𝜎-structure 𝐴 such that
𝐴∗ 𝜙1 = ⋯ = 𝐴∗ 𝜙𝑚 = T.
Since the 𝜙𝑖 are literals, we can find such an 𝐴 unless there are two literals
among 𝜙1 ,· · · , 𝜙𝑚 which are respectively 𝑝 and ¬𝑝 for the same
propositional symbol 𝑝. We can easily check this condition by inspecting the
formula. So checking the satisfiability of a formula in DNF and finding a
model, if there is one, are trivial. (See Exercise 3.8.3(b) for a test of this.)
Satisfiability of Formulas in CNF
The situation with formulas in CNF is completely different. Many
significant mathematical problems can be written as the problem of
finding a model for a formula in CNF. The general problem of
determining whether a formula in CNF is satisfiable is known as SAT.
Many people think that the question of finding a fast algorithm for
solving SAT, or proving that no fast algorithm solves this problem, is
one of the major unsolved problems of twenty-first century
mathematics. (It is the ‘P = NP’ problem.)
Coloring Problem
Example 3.8.10 A proper 𝑚-colouring of a map is a function assigning one
of 𝑚 colours to each country in the map, so that no two countries with a
common border have the same colour as each other. A map is 𝑚-colourable
if it has a proper 𝑚-colouring.
Suppose a map has countries 𝑐1 ,· · · , 𝑐𝑚 . Write 𝑝𝑖𝑗 for ‘Country 𝑐𝑖 has the 𝑗-
th colour’. Then finding a proper 𝑚-colouring of the map is equivalent to
finding a model of a certain formula 𝜃 in CNF. Namely, take 𝜃 to be the
conjunction of the following formulas :
𝑝𝑖1 ∨ 𝑝𝑖2 ∨ ⋯ ∨ 𝑝𝑖𝑚 (for 1 ≤ 𝑖 ≤ 𝑛);
¬𝑝𝑖𝑘 ∨ ¬𝑝𝑗𝑘 (for all 𝑖, 𝑗, 𝑘 where 𝑐𝑖 , 𝑐𝑗 have a common border).
More precisely, if 𝐴 is a model of 𝜃, then we can colour each country 𝑐𝑖 with
the first colour 𝑗 such that 𝐴∗ 𝑝𝑖𝑗 = T.
