CS262 Logic and Verification Lecture 4: Normal forms
CS262 Logic and Verification 1 / 8
Complete sets of connectives
Copyright By PowCoder代写 加微信 powcoder
A set of connectives is said to be complete if we can represent every truth function {T , F }n → {T , F } using only these connectives (there are 22n such functions).
Example: Is {¬, ∧, ∨} complete?
First look at all unary functions, i.e., the case n = 1:
p f1 f2 f3 f4 TF FTFTF
This is not too difficult: f1 = ⊤
CS262 Logic and Verification
What about binary functions?
For n = 2 there are 16 possible functions:
p q f1 f2 f3 f4 f5 f6 f7 … f16 TTF TFF FTF FFTFTTTFT…F
How about the following: f1 = ⊤
f2 = p ∨ q
But there is still plenty to do and then there are the cases n = 3, n = 4, etc.
CS262 Logic and Verification
Proof by construction
To create a formula that is logically equivalent to any function f on variables x1, . . . xn given by its truth table, do the following:
for every valuation which maps to T construct the conjunction
L1 ∧…∧Ln where Lj is xj if xj is assigned T under the valuation and Lj is ¬xj if xj is assigned F under the valuation
take the disjunction of all conjunctions from the previous step for the function that is everywhere F, by convention take ⊥
This shows that {¬, ∧, ∨} is indeed complete.
The resulting formula is called a disjunctive normal form (DNF) of f .
CS262 Logic and Verification
pqrf TTTT TTFT TFTF TFFF FTTF FTFF FFTF FFFT
f (p, q, r ) = (p ∧ q ∧ r ) ∨ (p ∧ q ∧ ¬r ) ∨ (¬p ∧ ¬q ∧ ¬r ) = (p ∧ q) ∨ (¬p ∧ ¬q ∧ ¬r)
The disjunctive normal form of a function f is not unique.
CS262 Logic and Verification 5 / 8
Conjunctive normal form
A formula in disjunctive normal form (DNF) is a disjunction of conjunctions of literals. A literal is a variable or its negation, or ⊥ or ⊤.
A formula in conjunctive normal form (CNF) is a conjunction of disjunctions of literals.
DNF: (p∧¬q)∨(¬p∧q∧¬r) CNF: (¬p∨¬q∨r)∧(¬p∨q∨¬r) (these are two different functions)
Theorem: Every Boolean function has a DNF. Theorem: Every Boolean function has a CNF.
First theorem follows from our construction before. Proof of second theorem in the exercises.
CS262 Logic and Verification
Further questions (see the exercises)
What other sets of connectives are complete?
How can you tell/prove that a set of connectives is not complete? What is the minimum number of connectives needed?
CS262 Logic and Verification 7 / 8
Normal form algorithms
Problem: Given a formula, can we derive its DNF or CNF in a systematic way, other than by writing down the entire truth table?
This can be achieved by normal form algorithms:
The input is any propositional formula, the output is a semantically equivalent formula in DNF or CNF.
In every step, the algorithm applies a single rewriting rule given by one of the laws of Boolean algebra.
CS262 Logic and Verification 8 / 8
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com