Manuel Kauers Hagenberg, November 26, 2002 RISC-Linz

Thinking, Speaking, Writing

Exercises

Exercise 1

Prove

((A ∨ B) → C) → (A → C) ∧ (B → C)  (G)

in propositional logic. Proof. In order to prove the goal (G) we assume the left hand side

(A ∨ B) → C  (1)

and try to deduce the right hand side

(A → C) ∧ (B → C)  (G0)

We proceed by case distinction.

• Case 1. We want to prove

A → C,  (G1)

so assuming

A  (2)

it remains to show

C.  (G2)

To do this, by (1) it is sufficient to show

A ∨ B  (G3)

for which in turn it is sufficient to prove

A  (G4)

which is asserted by (2).

• Case 2. We have to prove

B → C  (G5)

which can be done completely analogous to Case 1 (exchange the roles of A and B), so we ommit this part of the prove.

Then we are done.

Exercise 2

Prove

(∀_{x} p[x] → Q) → ∃_{x}(p[x] → Q)  (G)

in first order logic. Proof. In order to prove (G) we assume the left hand side

∀_{x} p[x] → Q  (1)

and try to deduce the right hand side

∃_{x}(p[x] → Q).  (G1)

This means we have to find some X with the property

p[X] → Q.  (G2)

which in turn means that X should have the property that

Q  (G3)

follows from

p[X].  (2)

But in order to show Q it is by (1) sufficient to prove

∀_{x} p[x]  (G4)

instead of Q. Now for some arbitrary but fixed x_{0} it is it remains to show

p[x_{0}]  (G5)

which is asserted by (2) by using X = x_{0} there.

This completes the proof.