Natural Deduction for Propositional Logic
Give a natural deduction proof of validity for each of the following propositional logic arguments. You
should only use the 8 inference rules that you have been using in earlier exercises (shown overleaf).
Present your proofs in the style shown in the module, i.e., where lines of the proof are annotated with
the inference rules used and their dependencies, and sub-proofs are clearly marked.
1. (R ∧ Q) → S : (P ∧ R) → (Q → (S ∧ P)) [7 marks]
2. R → (S ∧ P), ¬S → P, Q, ¬P ∨ (Q → R) : S [7 marks]
3. : (Q ∧ (P → (Q → R))) → (¬P ∨ R) [8 marks]
4. ¬(P ∧ (Q ∨ R)) : ¬P ∨ (¬Q ∧ ¬R) [8 marks]
Dave Parker 1/2 Assignment 2, 2017/18
Language & Logic 2017/18
Inference Rules
Conjunction (∧) Disjunction (∨)
A B
A ∧ B
∧-introduction
A ∧ B
A
∧-elimination
A ∧ B
B
∧-elimination
A
A ∨ B
∨-introduction
A
B ∨ A
∨-introduction
A ∨ B A ` C B ` C
C
∨-elimination
Implication (→) Negation (¬)
A ` B
A → B
→-introduction
A → B A
B
→-elimination
A ` ⊥
¬A
¬-introduction
¬¬A
A
¬¬-elimination
Dave Parker 2/2 Assignment 2, 2017/18