Mathematical Foundation of Computer Science

DHARM

146 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

We can prove above equivalence formulas. For example, to prove the (iii) equivalence
formula,we will prove that both of the following formulas be valid,
I. (∀x) P(x) → ~ (∃x) ~ P(x) and,
II. ~ (∃x) ~ P(x) → (∀x) P(x)
/∴ (∀x) P(x) ⇔ ~ (∃x) ~ P(x)
Proof.
1.( ) ~ P( )∃xx Premise (Assumed)
2.~ P( )y ,, (Assumed)
3.(∀xx) P( ) ,, (Assumed)
4.F( )y 3, UI

5.()P() P()∀→xx y 3-4,CP

6.~( )P( )∀xx 2&5,MT

7.~( )P( )∀xx 1,2-6,EI

8.( )~P( )∃→∀xx~( )P( )xx 1-7,CP

9.~(~ (∀→∃xx) P( )) ~ (( ) ~ P( ))x x 8, Trans

10.(∀→∃xx) P( ) ~ ( ) ~P( )x x 9, Dem

Hence equivalence formula is valid.

Alternatively, above equivalence can also be proved as follows,

/∴ ~ (∃x) ~ P(x) → (∀x) P(x)

Proof,

1.~ ( ) ~ P( )∃xx Premise (assumed)

2.~ P( )y ,, ,,

3.( )~P( )∃xx 2, EG

4.~P( )yxx→∃( )~P( ) 2-3,CP

5.~ ~ P( )y 1&4,MT

6.P( )y 5, Dem

7.(∀xx) P( ) 6, UG

8.~( )~P( )∃→∀xx xx( )P( ) 1-7,CP

Hence, equivalence formula is valid.

EXERCISES

5.1 Let A be “It is cloudy” and let B be “It is raining”. Give a simple verbal sentence which describes

each of the following statements :

(i)~ A (v) (A ∧ ~ B) → B

(ii)A → ~ B (vi)B ↔ A

(iii)~ ~ B (vii)A ↔ ~ B

(iv)~ A ∧ ~ B (viii) (A → B) ↔ A.