Discrete Mathematics for Computer Science

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 equiv-

alent 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 combina-

torial 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 Sec-

ond 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