114
CHAPTER 2 Formal Logic
Example 11. Use logic to show that (-,p A q) V (p A -'q) V (p A q) is logically equivalent to the formula p v q thus providing us with a one-gate equivalent to the circuit in
Figure 2.12.
Solution. We use the axioms for the Commutative Law, the Distributive Law, and the
basic properties of T to simplify this expression.
(-'p A q) V (p A --q) V (p A q)
=(pAq)V(-,pAq)V(pA-,q)V(pAq)
((pAq)=(pAq)V(pAq))
= ((p V -p) A q) V (p A (-'q V q))
(Distributive Law)
= (T A q) V (p A T)
(property of T)
=qVp
=pvq
(Commutative Law)
The simplified circuit is shown in Figure 2.13.
q
Figure 2.13 Equivalent, simpler circuit.
It is not always possible to have such clear reduction in the complexity of a combinatorial circuit. Example 11, however, shows how computer science can use different tools in
approaching a problem.
2.3.5 Substituting Equivalent Subformulas
In many respects, logically equivalent formulas are indistinguishable from each other. The
sense in which two logically equivalent formulas are indistinguishable is stated as the Second Substitution Principle.
Second Substitution Principle
Let 1h be logically equivalent to 02, and let *i be any formula containing t0l, possibly
several times, as a subformula. Form a new formula *' by replacing some (or possibly
all) of the occurrences of 01 in V with 02. Then, *' is logically equivalent to */'.
The Second Substitution Principle is really quite useful. Consider, for example, the
formula
0 = (--p -- q) -- r