Discrete Mathematics for Computer Science

Truth and Logical Truth 115

Since the subformula 41 = -p -- q is logically equivalent to 42 = p V q (see Example

9 in Section 2.3.1) by the Second Substitution Principle, we can transform the formula as

follows:

1 - r

2- r

(p V q) - r

Many people would find the last formula easier to understand than the original one. We
shall not prove the Second Substitution Principle; the reader is invited to prove it.

2.3.6 Simplifying Negations

When given a formula, it is often useful to find a simpler formula that is logically equivalent
to the first. Here, simpler has no fixed meaning; it just means simpler to use in some
application. For example, in programming, we write conditions saying when a loop should
continue for another pass and when a loop should stop. One equivalent way of writing that
condition may be easier than another for someone reading the program to understand. In
the context of boolean networks, simpler can mean smaller, such as having fewer gates or
taking up less area on a chip. A standard, though obviously imprecise, meaning of simpler
is "easier for people to understand." This latter notion of simpler comes up often.
Consider a piece of a program:
while (not((x < 3) or (x > 5)))

A complex formula that is negated is usually difficult to understand. Consequently,
programmers look for logically equivalent formulas where the operator not is "pushed
inside" and applied to simpler formulas. Unfortunately, in this example, one might think
the negation is logically equivalent to

while ((x > 3) or (x < 5))

{...)

which turns out to be an infinite loop. The problem, of course, is that DeMorgan's Law was
not applied correctly.
Let us rewrite the condition by letting the proposition letter p stand for x < 3 and q
for x > 5. Hence, -p is true just in the case x > 3, and -q is true just in the case x < 5.

The condition at the top of the while loop can be rewritten -'(p V q). By DeMorgan's Law,

this formula is equivalent to -p A --q. So, the proper translation would have been

while ((x > 3) and (x < 5))

f ... }I

In fact, for any formula 0, it is possible to find an equivalent formula in which nega-
tions are applied only to proposition letters. The technique can be thought of as "moving
negations inward." This technique is done in two steps.

Step 1. Find an equivalent formula containing no *-'s or --.'s. First, replace each sub-

formula of the form 4' 4- with the logically equivalent subformula

(0 -* ) A (* -* )