Discrete Mathematics

48 DISCRETE MATHEMATIC..._

________________________

_

0

Fig.

1.1:

The three forms

of

a Boolean expression tree

Definition A boolean expression tree is either

1.

a single node containing a Boolean variable,

or

2.

a tree, whose root contains

--,

and which only has one subtree (labelled T). This subtree is also a

Boolean expression tree,

or

3. a tree, whose root contains one

of

{A,

v,

~.

H}

and has two subtrees (labelled T

1

and T

2

),

each

of

which are Boolean expression trees.

Notice this definition is same as the definition

of

a Boolean expression. We can show the Boolean

expression tree for the Boolean expression ((p

A q) v

-.r).

Fig.

1.2: ...