Mathematical Foundation of Computer Science

DHARM

110 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

AB⊗ 1 ⊗ 2 ⊗ 3 ⊗ 4 ⊗ 5 ⊗ 6 ⊗ 7 ⊗ 8 ⊗ 9 ⊗ 10 ⊗ 11 ⊗ 12 ⊗ 13 ⊗ 14 ⊗ 15 ⊗ 16

FFFFFFTFFFTTTFTTTT

FTFFFTFTFTFTFTFTTT

TFFFTFFFTTTFFTTFTT

TTFTFFFTTFFFTTTTFT

Fig. 5.11

In general if set X has n statements then there are as many as 22

n

different combina-

tions or formulas can be seen.

5.4.1 Well Formed Formula (wff)

That valid statement that has following characteristic is called well formed formula.

· Every atomic statement is a wff.

· If A is a wff then ~ A is also wff.

· If A and B are wff then (A ⊗ B) is also wff. (where operator ⊗ : ~, ∧, ∨, →)

For example statement formula A ∧ B is not a wff while (A ∧ B) is a wff.

· Nothing else is a wff.

Example 5.3

(i) (A ∧ B) → C is not a wff (due to missing of parenthesis), while ((A ∧ B) → C) is a wff.

(ii) (A ∧) is not a wff, because A ∧ is not a wff.

(iii) ~ A ∨ B is not a wff, while (~ A ∨ B) is a wff.

5.4.2 Immediate Subformula......................................................................................

Let A & B are wff, then
(i) if A is a atomic statement then it has no immediate subformula.
(ii) the formula ~ A has A as its only immediate subformula i.e. ~ (A ∧ B) has (A ∧ B) is
immediate subformula.
(iii) the formula (A ⊗ B) (where ⊗ : ~, ∧, ∨ ) has A and B as its immediate subformula. For
example,
((A ∨ B) ∧ ~ C) has (A ∨ B) and ~ C are immediate subformula.

5.4.3 Subformula

(i) all immediate subformula of A are also subformula of A.
(ii) A is a subformula of itself.
(iii) if A is a subformula of B and B is a subformula of C then, A is also subformula of
C. For example,
Formula ((A ∨ B) ∧ ~ C) has (A ∨ B) and ~ C are immediate subformula.
Further, subformulas are:

A, B and C

((AÚÙ~B) C)

(AÚ~B), C

((AÚÙ~B) C)