Discrete Mathematics for Computer Science

96 CHAPTER 2 Formal Logic

If 0p is a formula with expression tree To, then an expression tree for T(-O) is

(0)

I

If 40 and * are formulas with expression trees To and Tk, respectively, then an expression

tree for T(O^*) is

()A

Expression trees for (40 v u), (4v - ), and (4' *- ) are defined analogously to the way

the expression trees is defined for (4 A 4'). The corresponding expression trees are

V W)^4 (-- ) (-^4 W)

It can be proved that each formula has exactly one expression tree. This principle

sometimes allows arguments that manipulate expression trees to be used as a replacement

for induction on formulas. Some examples can be found in writing formal proofs for the

theorems on substitution.

For any expression tree T and any node x in the expression tree, the portion T, of the

tree at or below x forms another expression tree-namely, the expression tree for x.

Definition 4. Let X be a formula with expression tree T, and let * be a formula with

expression tree U. Then, X is a subformula of *' if, for some node x of U, TX = Ux.

Example 4. For the expression tree T, determine the subformulas defined by p and

(-(p V q)).

(r A (-'(-(p v q))))

r (-(-'(p v q)))

(-(p v q))

S(p v

q)

p q

T