Discrete Mathematics for Computer Science

94 CHAPTER 2 Formal Logic

The theorem that follows is included because it is an example of an easy application of

the Principle of Induction on Formulas: It may look rather uninteresting and technical: It

deals only with counting the parentheses in a formula. Suppose, however, you were writing

a computer program to check something about logical formulas. In this case, you would

need to pay close attention to the parentheses. (Of course, you would have to worry about

more sophisticated issues than just counting the parentheses.) Or, consider the job of a

person writing a compiler for a computer language. The compiler code will have to pay

close attention to )'s, I's, and }'s, because having them misplaced causes difficulties for the

program.

Theorem 2. Every formula has an equal number of right and left parentheses.

Proof. Let .F be the set of formulas that have an equal number of right and left parenthe-

ses. Prove by induction on formulas that F is the set of all formulas.

(Base cases) Each proposition letter is in F7, since it is a formula with no left parentheses

and no right parentheses. Similarly, T, F E F-.

(Closure rules) Let 4, V1 E T. Let ) have n left parentheses and n right parentheses and

* have m left parentheses and m right parentheses. Then:

(a) (-4') has n + 1 left parentheses (n in 0 plus one more in front) and n + 1 right paren-

theses (n in 40 plus one more following), so (-0) E F.

(b) (40 A *,) has m + n + 1 left parentheses (m in 4,, n in 4', and one more in front)

and m + n + 1 right parentheses (m in *, n in 4', and one more following), so

(0 A E) eF.

(c) (0 v 4,), (40 - 4,), and (4' - 4,) each have m + n + 1 left parentheses and m + n +

1 right parentheses, so each is in F7.

Therefore, by the Principle of Induction on Formulas, it follows that F7 is the set of all

formulas. U

2.1.2 Expression Trees for Formulas

An expression tree is simply a visual representation for the way that a formula is built

from propositions and logical operators. A proposition is represented by a single node,

simply a filled-in circle, as shown in Figure 2.1.

P0p

Figure 2.1 Representation for p.

For an expression involving two propositions and a logical operator, the propositions

are represented by nodes at the same level, and then at a higher level, a node represents

the result of applying the operator to the two propositions. The nodes representing the

propositions and the node representing the result of the operation are joined by lines. For

example, the final picture for p V q is shown in Figure 2.2.