Intro to Logic- Use Natural Deduction to prove Dist E

Question

Hi everyone,

Can someone please help me. I have to use natural deduction to prove Dist E for both 'or' and 'and'

These are the two questions:

1: Dist E-

Ex(Px v Qx) premise

Conclusion: ExPx v ExQx

2: Dist E:

Ex(Px ^ Qx)

Conclusion: ExPx ^ ExQx

Thanks.

Answer 1

For the first:

We know that, universal quantifier distribute over conjunction so:

Ax [ ~P(x) ^ ~ Q(x)] if and only if [Ax ~P(x)] ^ [Ax ~Q(x)]

Negate both sides

~Ax [~P(x) ^ ~Q(x)] if and only if ~([~Ax P(x)] ^ [Ax ~Q(x)])

Quantifier Negate

Ex~[~ P(x) ^ ~Q(x)] if and only if ~ ([Ax ~ P(x)] ^ [Ax ~ Q(x)])

DeMorgan

Ex [P(x) v Q(x)] if and only if ~ ([Ax ~ P(x)] ^ [Ax ~ Q(x)])

Quanitifer Negate and Double Negation

Ex [P(x) v Q(x)] if and only if [Ex P(x)] v [Ex Q(x)]

then you can do biconditional exchange to get

Ex[P(x) v Q(x)] only if [Ex P(x)] v [Ex Q(x)]

if you have to include the Ex[P(x) v Q(x)] as premise 1 then do everything above starting on line 2.

When you get Ex[P(x) v Q(x)] only if [Ex P(x)] v [Ex Q(x)] you'll be able to apply modus ponens.

For the second one the proof could look like this

1. Ex(Px ^ Qx)
2. Pa ^ Qa (1)By EI (existential instantiation
3. Pa (2)By conjunction elimination
4. Qa (2)By conjunction elimination
5. ExPx (3) by EG (existential generalization)
6. ExQx (3) by EG
7. ExPx ^ ExQx (5) and (6) by conjunction introduction