Mathematical Foundation of Computer Science

DHARM

142 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

e.g.
l (∀x) P(x) ∨ (∃x) ~ P (x); is a valid predicate formula (VPF) and so a tautology. To
discuss the fact, let domain set D = {a, b, c} and arbitrary set P = {a, c}; also assume
P(a), P(b) and P(c) are all true then the formula
A ⇔ (∀x) P(x) is false (F)
and B ⇔ (∃x) ~ P(x) is true (T) [the in universe there exists at least one item
for which ~ P(x) is true]
Therefore, F ∨ T ⇒ T; Hence formula is a tautology.
l (∃x) P(x) ∨ ~ (∃x) P(x); is a valid predicate formula and also tautology due to the fact
that A ∨ ~ A is a tautology [where A is (∃x) P(x)].

5.8 Inference Theory of Predicate Logic...............................................................................

Continuation to the section 5.6 where we were discussed the inference theory of symbolic logic
in this section we shall cover-up the inference theory of predicate logic or predicate calculus.
The importance fact to discuss inference theory is to check the validity of an argument that
symbolizes by using predicate logic. Since, we know from the inference theory of symbolic logic
that natural method of deduction is an important tool to justify the validity of an argument.
We can extend the deduction approach used earlier as in case of natural method of deduction
for the predicate logic also. As like the previous study for the validity of an argument we have
successfully applied method of deduction using following set of rules,
· 9-Rules if Inferences
· 10-Rules of Replacement
· 1-Rule of Conditional Proof
· 1-Rule of Indirect proof
To check the validity of the predicate formula we required few more rules, now we
discuss those additional rules.

Rule I. Universal Instantiation (UI)

Let (∀x) A be any predicate formula (premise), then it can conclude to a specific predicate
expression A(y) where variable x is replaced by y such that we can drop the quantifier in the
derivation. For example,

1. 
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   :
   :
   k. (∀x) A
   :
   n. Axy
   Or, (∀x) A

   
   

/∴ Ayx

where, Ayx : in the predicate formula A whenever x occurs, replace x with y where y is any
variable/constant.