Mathematical Foundation of Computer Science

DHARM

PROPOSITIONAL LOGIC 141

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

xis bounded

●(∀∧yxy y) (G( , ) Q( ))

xis free

yis bounded

zis free

yis free

A statement could not have any free variable. For example,

l “Everything is P” : (∀x) P(x)

l “Everything is P or Q” : (∀x) (P(x) ∨ Q(x))

l “For every number x there must exist another even number y s.t. y > x”:

x is bounded

(∀∃xy y yx) ( ) [E( )∧G( , )]; where E( ) stands “ is a even number” andy y

G( , ) stands “ > ”xy y x

yis bounded

Example 5.30. Consider the predicate expression
(∀z) [ (∀x) [Q(x, y) → (∃y) {P(x, y,z) ∧ ~ Q(y, z)}]]
determine the free and bound variables.

Sol.
yis free

(∀∀z) [( x) [Q( , )x y→∃( ) {P( , , )y xyz∧∼Q( , )}]]yz

Here dashed lines shows the boundness of the variables.
l Variable z in P and in Q is bounded due to lying in the scope of the quantifier i.e.,
“(∀z)”
l Variable x in Q and in P is bounded due to lying in the scope of quantifier i.e., “(∀x)”
but another variable y of same Q is free.
l Variable y in P and in Q is bounded due to lying in the scope of quantifier i.e., “(∃y)”.
A statement can be expressed by a predicate formula. A predicate formula is a valid
predicate formula (VPF) if and only if the truth value of the formula is true for all possible
interpretations. The possible interpretations for a predicate formula may be infinite. On the
other hand, if the predicate formula gets the truth value true for at least one interpretation
then formula is a satisfiable predicate formula (SPF). Thus, a VPF is also a SPF. Conversely, a
VPF be a tautology. For example,