Scribd
Upload
18 views6 pages

Proof Solutions 1

This document contains 6 exercises in propositional logic proofs. The first exercise proves ((P → Q) ∧ (Q → R)) → (P → R) using assumptions, subgoals, and inference rules. The second exercise proves ((P → R) ∧ (Q → ¬R)) → (Q → ¬P) using additional negation rules. The third exercise proves ((P → R) ∨ (Q → R)) → ((P ∧ Q) → R) using proof by cases.

Uploaded by

Martinho Moco Oel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views6 pages

Proof Solutions 1

This document contains 6 exercises in propositional logic proofs. The first exercise proves ((P → Q) ∧ (Q → R)) → (P → R) using assumptions, subgoals, and inference rules. The second exercise proves ((P → R) ∧ (Q → ¬R)) → (Q → ¬P) using additional negation rules. The third exercise proves ((P → R) ∨ (Q → R)) → ((P ∧ Q) → R) using proof by cases.

Uploaded by

Martinho Moco Oel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Solutions to propositional logic proof exercises

October 6, 2016

1 Exercises
1. Prove
((P → Q) ∧ (Q → R)) → (P → R)
using the style given here. This should be straightforward.

Assume (1): (P → Q) ∧ (Q → R)
Goal: P → R
Assume (2): P
Goal: R
(3): P → Q simplification, line 1
(4): Q → R simplification line 1
(5): Q modus ponens lines 2,3
(6): R modus ponens lines 5,4
(7): P → R deduction lines 2–6

(8): the exercise by deduction lines 1–7

1
2. Prove
((P → R) ∧ (Q → ¬R)) → (Q → ¬P ).
You will want to use the additional rules involving negation.

Assume (1): ((P → R) ∧ (Q → ¬R))


Goal: Q → ¬P
Assume(2): Q
Goal: ¬P Assume(3): P
Goal: ⊥ (a contradiction)
(4): P → R simplification 1
(5): Q → ¬R simplification 1
(6): R modus ponens 3,4
(7): ¬Q disjunctive syllogism 6,5
(8): ⊥ contradiction, 7,2
(9): ¬P negation introduction 3–8
(10): Q → ¬P deduction 2–9

(11): the exercise deduction lines 1–10

2
3. Prove
((P → R) ∨ (Q → R)) → ((P ∧ Q) → R).
This should be relatively straightforward – proof by cases is needed.

Assume(1): ((P → R) ∨ (Q → R))


Goal: (P ∧ Q) → R
Assume(2): P ∧ Q
Goal: R
(3): P simplification line 2
(4): Q simplifaction line 2
We start a proof by cases using line 1:

Case 1 (5): P → R
Goal: R
(6): R mp 3,5

Case 2 (7): Q → R
Goal: R
(8): R mp 4,7

(9): R proof by cases 1,5–6,7–8


(10): (P ∧ Q) → R deduction 2–9

(11): the exercise deduction 1–10

3
4. Prove
((P ∨ Q) ∧ (¬Q ∨ R)) → (P ∨ R)
I see one approach using excluded middle and proof by cases, but I
think there is a simpler way using the rules of alternative exclusion
and disjunctive syllogism.

Assume(1): ((P ∨ Q) ∧ (¬Q ∨ R))


Goal: P ∨ R
Assume(2): ¬R
Goal: P
(3): P ∨ Q simplification 1
(4): ¬Q ∨ R simplification 1
(5): ¬Q disjunctive syllogism lines 5,3
(6): P disjunctive syllogism lines 4,5
(7): P ∨ R alternative exclusion lines 2–6

(8): the exercise, deduction 1–7


Assuming ¬P as line 2 and reasoning to R goes about the same way.

4
5. Prove
((P ∧ Q) → R) → ((P → R) ∨ (Q → R)).
This is quite tricky. You should recognize this problem and a previous
one as the two directions of a biconditional you proved using truth
tables.
Not assigned

5
6. Prove
¬(P ∧ Q) ↔ (¬P ∨ ¬Q)
This is one of deMorgan’s laws. Notice that this is a biconditional
so you have two directions of argument to complete. You can’t use a
deMorgan law to prove it; just the rules in this handout.

Part I: Assume(1): ¬(P ∧ Q)


Goal: (¬P ∨ ¬Q)
Assume(2): ¬¬P
Goal: ¬Q
Assume(3): Q
Goal: ⊥ (a contradiction)
(4): P double negation 2
(5) P ∧ Q conjunction 4,3
(6): ⊥ contradiction, 1,5
(7): ¬Q negation introduction 3–6
(8): (¬P ∨ ¬Q) alternative exclusion 2–7

Part II: Assume(9): (¬P ∨ ¬Q)


Goal: ¬(P ∧ Q)
Assume(10): P ∧ Q
Goal: ⊥ (a contradiction)
(11): P simplification 10
(12): Q simplification 10
(13): ¬Q disjunctive syllogism 9, 12
(14): ⊥ contradiction 12,13
(15): ¬(P ∧ Q) negation introduction 10–14

(16): the exercise, biconditional introduction 1–8, 9–15.

You might also like