Test 2010, questions and answers PDF

Preview

Summary

Test 2010, questions and answers...

Description

COSC 5P02 - Logic in Computer Science Term Test 1

Question 1: a. Show that p → (q → r) |= p ∧ q → r using a truth table (6 marks). b. Give a derivation p → (q → r) ⊢ p ∧ q → r in natural deduction (4 marks). Solution: a. p T T T T F F F F

q T T F F T T F F

r p → (q T T F F T T F T T T F T T T F T

→ r) p ∧q → r T T T F T F T F T T F T T F T F F T T F T T F T

The fourth and the seventh column are identical with shows p → (q → r) |= p ∧ q → r. b.

[p ∧ q ]1 ∧E1 [p ∧ q]1 p → (q → r) p → E ∧E2 q→r q → E r 1 p ∧ q → r →I

1

Question 2: a. Show that p ∨ q, ¬p |= q using a truth table (4 marks). b. Give a derivation of p ∨ q, ¬p ⊢ q in natural deduction (6 marks). Hint: Use the rules (∨E) and (PBC).

Solution: a. p T T F F

q p ∨ q ¬p T T F F T F T T T F F T

Only in row 3 both assumptions are true - here the conclusion is also true. b.

¬p p∨q

[p]1

¬E ⊥ PBC q q

2

[q]1 1 ∨E...