Chapter Review
149
THEOREMS
First Substitution Principle
Second Substitution Principle
2.5 and 2.6 Summary
TERMS
2-CNF
excess literals
resolution refutation
3-CNF
k-DNF
resolution rule
3-satisfiability problem
k-term
resolvant
clause
literal
sound
complete
negative literal
term
conjunctive normal form
A'NP-complete
(CNF)
positive literal
disjunctive normal form
resolution
(DNF)
resolution derivation
THEOREMS
Every Formula Is Logically Equivalent to
Every Formula Is Logically Equivalent to
a Formula in CNF
a Formula in DNF
ALGORITHMS
BubbleSort
MergeSort
Outer Loop Variant
2.7 Summary
TERMS
array
loop invariant
quantification
atomic formula
loop invariant assertion
scope
binary
n-ary
universal quantification
constant
negation normal form
variable
existential quantification
nested quantifiers
variable symbols
formula
predicate
2.9.2 Starting to Review
1. Which of the following are propositions?
i: "The moon is visible."
ii: "The property tax rate will increase next year."
iii: "No one under 18 may buy cigarettes."
iv: "Please help me with the assignment."
(a) i and iii
(b) i and ii
(c) ii and iii
(d) All of the above