CS2209A 2017
Applied Logic for Computer Science
Lecture 8, 9 Propositional Logic:
Conjunctive Normal Form & Disjunctive Normal Form
Instructor: Xie
1
Conjunctive Normal Form (CNF)
• Resolutionworksbestwhentheformulaisofthe special form: it is an ∧ of ∨s of (possibly negated, ¬) variables (called literals).
• This form is called a Conjunctive Normal Form, or CNF. – ∨¬ ∧ ¬ ∧ ∨ isaCNF
– (∨¬∨) isaCNF.Sois ∧¬∧ .
– ∨ ¬∧ isnotaCNF
• 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
• Whatistherelationbetweenpropositionallogic 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 twooutof,,aretrue,and falseotherwise.
– 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 ∧ ∨ ∧ ∨ ∧
xy z
AND
AND OR AND
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.
• DNFisan∨of∧s;an∧ofliteralsiscalleda term.
6
Notations
• ¬ , , are examples of literals
• Neither¬¬ nor(∨)isaliteral
• ∨¬∨ ,(¬ )areclause
• ∧¬∧ ,(¬ )areterms
• ∨¬∨ ∧(¬∨¬)∧ ¬ isaCNF
• ∧ ∨ ¬∧∧ ∨(¬∧)isaDNF
• ∧¬(∨)∨ isneitheraCNFnorDNF, butisequivalenttoDNF( ∧¬∧¬)∨
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
• Amintermisaconjunctionofliteralsinwhich each variable is represented exactly once
– If a Boolean function (truth table) has the variables ,$, then ∧¬$∧ isamintermbut ∧¬$is
not.
• Each minterm is true for exactly one assignment.
– ∧¬$∧istrue ifpistrue(1), qisfalse(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.
pqr F
• Consequently, we can select the minterms that make the function true and form the disjunction of these minterms.
110 0
• Fistrueforthreeassignments: o p, q, r are all true, ( ∧ $ ∧ )
100 0 011 0 010 0 001 1 000 09,
o p, ¬q, r are all true, ( ∧ ¬$ ∧ )
o ¬p, ¬q, r are all true, (¬ ∧ ¬$ ∧ )
• DNFofF:( ∧$∧)∨( ∧¬$∧)∨ (¬ ∧ ¬$ ∧ )
111 1
101 1
11
From truth table to CNF
• Complementationcanbeusedtoobtainconjunctive normal forms from truth tables.
• IfAisaformulacontainingonlytheconnectives¬, ∨ 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:¬Gistrueforthe following assignments.
pqr G 111 1 110 1 101 0 100 0 011 1 010 1 001 0 000 1
p=1; q=0; r=1 p=1; q=0; r=0 p=0; q=0; r=1
• The DNF of ¬G is therefore: (%∧¬&∧’)∨(%∧¬&∧¬’)∨(¬%∧¬&∧’)
• The formula has the complement: (¬%∨&∨¬’)∧ (¬%∨&∨’)∧(%∨&∨¬’)
It is the desired CNF of G
13
Canonical CNF and DNF
• Soforeveryformula,thereisauniquecanonical 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,tomakeacanonicalDNFfromatruthtable: – 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 ¬,∧ .
• ByDeMorgan, ∨ ≡¬(¬ ∧¬)Noneedfor∨!
– 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 |
ABA|B
–¬≡|
True True False True False True False True True False False True
– ∨≡¬(¬ ∧¬) ≡¬ ¬)
≡ | ( |))
– In practice, most often stick to ∧,∨, ¬
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