Mathematical Foundation of Computer Science

DHARM

PROPOSITIONAL LOGIC 111

5.4.4 Formation Tree of a Formula............................................................................

Let A be a formula, then
(i) put A at the root of the tree.
(ii) If a node in the tree has formula B as its label, then put all immediate subformula of
B as the son of this node.

Example 5.4. Fig. 5.12 shows the formation tree of the formula ((A ∨ B) ∧ ~ C).

((AÚÙ~B) C)

(AÚB) ~C

A B C

Fig. 5.12

Example 5.6. Construct the formation tree of the formula ((P ∨ (~ Q ∧ (R → S))) → ~ Q).

Fig. 5.13
All formula appearing at node/leaf in the formation tree are subformula of formula as
root and every formula appearing at parent node will be the immediate subformula to their
children.
Formation tree provide convenient way to determine the truth value of the formula over
particular set of truth values of its propositional variables.