Mathematical Foundation of Computer Science

DHARM

PROPOSITIONAL LOGIC 145

For example, consider an argument,

I. “All dogs are barking. Some animals are dogs. Therefore, some animals are barking”.

Then corresponding predicate expressions are,

1.(∀x) (D(x) → B(x))

2.(∃x) (A(x) ∧ D(x)) /∴ (∃x) (A(x) ∧ B(x))

3.A(k) ∧ D(k) 2, EI

4.D(k) → B(k) 1, UI

5.D(k) ∧ A(k) 3, Comm

6.D(k) 5, Simp

7.B(k) 4 & 6, MP

8.A(k) 3, Simp

9.A(k) ∧ B(k) 8 & 7, Conj

10.(∃x) A(x) ∧ B(x) 9, EG

It concludes that argument is valid.

II. “Some cats are animals. Some dogs are animals. Therefore, some cats are dogs”.

The statement can be translated into corresponding predicate premises and conclusion,

1. (∃x) (C(x) ∧ D(x))


2. (∃x) (D(x) ∧ A(x)) / ∴ (∃x) (C(x) ∧ D(x))


3. C(k) ∧ A(k) 1, EI


4. D(k) ∧ A(k) 2, EI × [wrong, because k is used earlier
   so, this violates the restriction of
   rule EI]


5. D(k) 4, Simp


6. C(k) 3, Simp


7. C(k) ∧ D(k) 6 & 5, Simp


8. (∃x) (C(x) ∧ D(x)) 7, EG
   It proves valid, but truly given argument is invalid due to violation of Rule IV.
   Therefore, now we have following set of rules -
   · 9-Rules of Inferences
   · 10-Rules of Replacement
   · 1-Generalized Conditional Proof (CP/IP)
   · Rules of UG, UI, EG and EI
   These set of rules are essentially followed by a valid argument.
   Some equivalence predicate formulas
   (i)~ (∀x) P(x) ⇔ (∃x) ~ P(x)
   (ii)~ (∃x) P(x) ⇔ (∀x) ~ P(x)
   (iii)(∀x) P(x) ⇔ ~ (∃x) ~ P(x)
   (iv)(∀x) (∃y) [P(x) ∨ Q(y)] ⇔ (∃y) (∀x) P(x) ∨ Q(y)(∃y) [P(x) ∨ Q(y)] ⇔ [P(x) ∨ (∃y) Q(y)]
   (vi)(∀x) [P(x) ∨ Q(y)] ⇔ [ (∀x) P(x) ∨ Q(y)]