Mathematical Foundation of Computer Science

DHARM

140 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

· Similarly, the truth value of the expression

(∀x) (∃y) [E(y) ∧ G(y, x)] : where E(y) stands “y is a even number” and

G(x, y) stands “y > x”

will also be false.

· If set D = {1, 2, 3, ..........}

Then the truth value of the predicate expression

(∀x) G(x, y) : where G(x, y) stands for “y = x”

will be true, because every number is successor to their predecessor. The same expression will

have the truth value false if the set D = {1, 2, 3, 4}.

Therefore we shall conclude that the governing factors to determine the truth value of

the predicate expression are the domain set and the predicate.

5.7.3 Free and Bound Variables.................................................................................

The occurrence of free variables and bound variables are true for every object. The variable
occurring just after the quantifier symbol is a bound variable and the variable lying in the
scope of the quantifier is bounded by that quantifier.
Consider the predicate expression,
(∀∨xx x) (P( ) Q( ))

bounded byx

Here the variable x in P as well as in Q is a bound variable due to the variable lies in the

scope of the quantifier. Consider another expression,

()P() Q()∀∨xx x

bounded byx

xis not bounded

Here, the variable x in P is a bound variable that is lying in the scope of the universal

quantifier but x in Q is not a bound variable.

Any variable which is not bound is a free variable. A predicate formula may have both

free and bound variables.

In order to determine the scope of the quantifier involving in the predicate formula is

the smallest formula that follows the quantifier.

i.e. ● (∀∧→xx y z) ((P( ) Q( )) R( )

scope of the quantifier

● (∀∨→xx y z) ((P( ) Q( )) R( )

scope of the quantifier

Conversely, the variables lies in the scope of the quantifier “∀” or “∃” are bound vari-

ables. i.e.,