Discrete Mathematics for Computer Science

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