Mathematical Foundation of Computer Science

DHARM

144 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Hence argument is valid.

Consider another argument,

II. “India is democratic. Therefore, anything is democratic”.

Thus, the corresponding predicate argument is,

1. D(i)/∴ (∀x)D(x)


2. (∀x) D(x) 1, UG ×
   Although, it proved valid but it violates the first restriction, hence argument is invalid.
   III. “Not everything is edible, therefore nothing is edible”.
   Thus we have the predicate expressions,


3. ~( )E( )∀∃∴xxor, ( )~E( )x x / ( )~E( )∀x x


4. E( )y Assume the predicate formula


5. (∀xx) E( ) 2, UG × (violates the second restriction)


6. E( )yxx→∀( ) E( ) 2 & 3, CP (Conditional Proof )


7. ~E( )y 4 & 1, MT


8. ( )~E( )∀xx 5, UG
   It seems that argument is valid but at step 3 it violates the restriction second, hence
   argument is invalid.

Rule III. Existential Generalization (EG)

Let A by any predicate formula then it can conclude to (∃x) Axy. The rule existential generali-
zation denoted as EG will permit us that when A be any premise found at any step of deduc-
tion, then add A with existential quantifier in the conclusion and whenever y occurs put x;
where y is a variable/ constant; without imposing any other additional restrictions. This rule is
called existential generalization or EG.
e.g., :
:
A
:
/∴ (∃x) Axy [whenever y (variable/constant) occurrs put x]

Rule IV. Existential Instantiation (EI)

According to rule existential instantiation or EI, from the predicate formula (∃x) A, we can
conclude Akx, such that variable x is replaced by a new constant k with restriction that k
doesn’t appeared in any of the previous derivation step.
e.g., :
:
(∃x) A
/∴ Akx