148 CHAPTER 2 Formal Logic
satisfiable propositions, and logically equivalent propositions give a fuller understanding of
the propositional logic. Both CNFs and DNFs give a method for representing any formula
using a standard format from which information is easier to determine. The last section
deals with predicates and quantification. We define predicates as natural generalizations of
propositions and formulas. The interaction of predicates and quantification is explored, as
is the interaction of quantification with the operations that are defined on propositions.
Throughout the chapter, but independent of the core material about propositional logic,
is an introduction to boolean or combinatorial circuits. First, the correspondence between
logical formulas and a boolean circuit composed of gates is introduced. After showing the
correlations between boolean algebras and combinatorial circuits, the results about boolean
algebras become a tool for simplifying circuits. Finally, CNFs and DNFs are used to find
standard representations of combinatorial circuits.2.9.1 Terms and Theorems2.1 Summary
TERMS
AND gate expression tree proposition letter
base cases Expression Tree for a propositional connective
biconditional Formula propositional constant
boolean circuit FALSE (F) (T, F)
boolean value formula propositional logic
closure rules gate semantics
combinatorial circuit hypothesis subformula
combinatorial network implication syntax
conclusion inductive definition TRUE (T)
conditional mean truth table
conjunct logical value well-formed formula
conjunction negation (wff)
disjunct NOT gate
disjunction OR gate
equivalence propositionTHEoREMs
Principle of Induction on Formulas2.3 and 2.4 Summary
TERMS
alphabetic substitution interpretation semantics
alphabetic variant logically equivalent Sheffer stroke
complementation logically implies tautologically equivalent
contradiction logically valid tautologically implies
equivalent meaning tautology
exclusive or satisfiable true in
false in satisfies unsatisfiable