Lecture 8, 9
Propositional Logic:
Conjunctive Normal Form & Disjunctive Normal Form
CS2209A 2017
Applied Logic for Computer Science
Instructor: Yu Zhen Xie
1
Conjunctive Normal Form (CNF)
• Resolution works best when the formula is of the
special form: it is an ∧ of ∨s of (possibly negated, ¬)
variables (called literals).
• This form is called a Conjunctive Normal Form, or CNF.
– ∨ ¬ ∧ ¬ ∧ ∨ is a CNF
– ( ∨ ¬ ∨ ) is a CNF. So is ∧ ¬ ∧ .
– ∨¬ ∧ is not a CNF
• An AND (∧) of CNF formulas is a CNF formula.
– So if all premises are CNF and the negation of the
conclusion is a CNF, then AND of premises AND NOT
conclusion is a CNF.
2
CNF
• To convert a formula into a CNF.
– Open up the implications to get ORs.
– Get rid of double negations.
– Convert ∨ ∧ to ∨ ∧ ∨
//distributivity
• Example: → ( ∧ )
≡ ¬ ∨ ( ∧ )
≡ ¬ ∨ ∧ ¬ ∨
• In general, CNF can become quite big, especially
when have
↔
.
There are tricks to avoid that ...
3
Boolean functions and circuits
• What is the relation between propositional logic
and logic circuits?
– View a formula as computing a function (called a
Boolean function),
• inputs are values of variables,
• output is either true (1) or false (0).
– For example, , , = when at least
two out of , , are true, and false otherwise.
– Such a function is fully described by a truth table of its
formula (or its circuit: circuits have truth tables too).
4
Boolean functions and circuits
• What is the relation between propositional
logic and logic circuits?
– So both formulas and circuits “compute” Boolean
functions – that is, truth tables.
– In a circuit, can “reuse” a piece in several places,
so a circuit can be smaller than a formula.
• Still, most circuits are big!
– , , is ∧ ∨ ∧ ∨ ∧
AND
AND
AND
OR
x
y
z
5
CNF and DNF
• Every truth table (Boolean function) can be
written as either a conjunctive normal form
(CNF) or disjunctive normal form (DNF)
• CNF is an ∧ of ∨s, where ∨ is over variables or
their negations (literals); an ∨ of literals is also
called a clause.
• DNF is an ∨ of ∧s; an∧ of literals is called a
term.
6
Notations
• ¬, , are examples of literals
• Neither ¬¬nor( ∨ ) is a literal
• ∨ ¬ ∨ , (¬) are clause
• ∧ ¬ ∧ , (¬) are terms
• ∨ ¬ ∨ ∧ (¬ ∨ ¬) ∧ ¬ is a CNF
• ∧ ∨ ¬ ∧ ∧ ∨ (¬ ∧ ) is a DNF
• ∧ ¬( ∨ ) ∨ is neither a CNF nor DNF,
but is equivalent to DNF ( ∧ ¬ ∧ ¬) ∨
7
Facts about CNF and DNF
• Any propositional formula is tautologically
equivalent to some formula in disjunctive
normal form.
• Any propositional formula is tautologically
equivalent to some formula in conjunctive
normal form.
8
Why CNF and DNF?
• Convenient normal forms
• Resolution works best for formulas in CNF
• Useful for constructing formulas given a
truth table
– DNF: take a disjunction (that is, ∨) of all
satisfying truth assignments
– CNF: take a conjunction (∧) of negations of
falsifying truth assignments
9
From truth table to DNF and CNF
• A minterm is a conjunction of literals in which
each variable is represented exactly once
– If a Boolean function (truth table) has the variables
, $, then ∧ ¬$ ∧ is a minterm but ∧ ¬$ is
not.
• Each minterm is true for exactly one assignment.
– ∧ ¬$ ∧ is true if p is true (1) , q is false (0) and r
is true (1).
– Any deviation from this assignment would make this
particular minterm false.
• A disjunction of minterms is true only if at least
one of its constituents minterms is true.
10
From truth table to DNF
• If a function, e.g. F, is given by a truth
table, we know exactly for which
assignments it is true.
• Consequently, we can select the
minterms that make the function true
and form the disjunction of these
minterms.
• F is true for three assignments:
o p, q, r are all true, ( ∧ $ ∧ )
o p, ¬q, r are all true, ( ∧ ¬$ ∧ )
o ¬p, ¬q, r are all true, (¬ ∧ ¬$ ∧ )
• DNF of F: ( ∧ $ ∧ ) ∨ ( ∧ ¬$ ∧ ) ∨
(¬ ∧ ¬$ ∧ )
p q r F
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 0 9,
11
From truth table to CNF
• Complementation can be used to obtain conjunctive
normal forms from truth tables.
• If A is a formula containing only the connectives¬,
∨and ∧, then its complement is formed by
– replacing all ∨ by ∧
– replacing all∧by ∨
– replacing all atoms by their complements.
• The complement of q is ¬q
• The complement of ¬q is q
• Example: Find the complement of the formula
• (p ∧q)∨ ¬r
(
¬
p
∨
¬
q)
∧
r
12
From truth table to CNF
• Solution: ¬G is true for the
following assignments.
p q r G
1 1 1 1
1 1 0 1
1 0 1 0
1 0 0 0
0 1 1 1
0 1 0 1
0 0 1 0
0 0 0 1
p = 1; q = 0; r = 1
p = 1; q = 0; r = 0
p = 0; q = 0; r = 1
13
• The DNF of ¬G is therefore:
(% ∧ ¬& ∧ ') ∨ (% ∧ ¬& ∧ ¬') ∨ (¬% ∧ ¬& ∧ ')
• The formula has the complement:
(¬% ∨ & ∨ ¬') ∧(¬% ∨ & ∨ ') ∧ (% ∨ & ∨ ¬')
It is the desired CNF of G
Canonical CNF and DNF
• So for every formula, there is a unique canonical
CNF (and a truth table, and a Boolean function).
• And for every possible truth table (a Boolean
function), there is a formula (the canonical CNF).
• Recall, to make a canonical DNF from a truth table:
– Take all satisfying assignments.
– Write each as an AND of literals, as before.
– Then take an OR of these ANDs.
14
Complete set of connectives
• CNFs only have ¬,∨,∧, yet any formula can be
converted into a CNF
– Any truth table can be coded as a CNF
• Call a set of connectives which can be used to
express any formula a complete set of
connectives.
– In fact, ¬,∨ is already complete. So is ¬,∧.
• By DeMorgan, ∨ ≡ ¬(¬ ∧ ¬) No need for ∨!
– But ∧,∨ is not: cannot do ¬ with just ∧,∨.
• Because when both inputs have the same value, both ∧,∨
leave them unchanged.
15
Complete set of connectives
• How many connectives is enough?
– Just one: NAND (NotAND), also called the Sheffer
stroke, written as |
– ¬ ≡ |
– ∨ ≡ ¬(¬ ∧ ¬)
≡ ¬ ¬)
≡ |(|))
– In practice, most often stick to
∧
,
∨
,
¬
A B A | B
True True False
True False True
False True True
False False True
16
Puzzle
• Susan is 28 years old, single, outspoken, and very bright. She
majored in philosophy. As a student she was deeply concerned with
issues of discrimination and social justice and also participated in
anti-nuke demonstrations.
Please rank the following possibilities by how likely they are. List
them from least likely to most likely. Susan is:
1. a kindergarden teacher
2. works in a bookstore and takes yoga classes
3. an active feminist
4. a psychiatric social worker
5. a member of an outdoors club
6. a bank teller
7. an insurance salesperson
8. a bank teller and an active feminist
17
