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 Theorems
2.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
proposition
THEoREMs
Principle of Induction on Formulas
2.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