Mathematics for Computer Science

3.2. Propositional Logic in Computer Programs 47

equivalent. So we can simplify the code snippet without changing the program’s

behavior by replacing the complicated expression with an equivalent simpler one:

if ( x > 0 || y > 100 )

::

:

(further instructions)

The equivalence of (3.2) and (3.3) can also be confirmed reasoning by cases:

AisT. An expression of the form.TORanything/is equivalent toT. SinceAisT
both (3.2) and (3.3) in this case are of this form, so they have the same truth
value, namely,T.

AisF. An expression of the form.FORanything/will have same truth value as

anything. SinceAisF, (3.3) has the same truth value asB.

An expression of the form.TANDanything/is equivalent toanything, as is

any expression of the formFORanything. So in this caseAOR.NOT.A/AND

B/is equivalent to.NOT.A/ANDB/, which in turn is equivalent toB.

Therefore both (3.2) and (3.3) will have the same truth value in this case,

namely, the value ofB.

Simplifying logical expressions has real practical importance in computer sci-

ence. Expression simplification in programs like the one above can make a program

easier to read and understand. Simplified programs may also run faster, since they

require fewer operations. In hardware, simplifying expressions can decrease the

number of logic gates on a chip because digital circuits can be described by logical

formulas (see Problems 3.5 and 3.6). Minimizing the logical formulas corresponds

to reducing the number of gates in the circuit. The payoff of gate minimization is

potentially enormous: a chip with fewer gates is smaller, consumes less power, has

a lower defect rate, and is cheaper to manufacture.

3.2.2 Cryptic Notation

Java uses symbols like “&&” and “jj” in place ofANDandOR. Circuit designers

use “
” and “C,” and actually refer toANDas a product andORas a sum. Mathe-

maticians use still other symbols, given in the table below.