tutorial4.dvi
COMP9414: Artificial Intelligence
Tutorial 4: Propositional Logic
1. Translate the following sentences into Propositional Logic.
(i) If Jane and John are not in town we will play tennis [do both of them have to be away?]
(ii) It will either rain today or it will be dry today [is “dry” the same as “not raining”?]
(iii) You will not pass this course unless you study [this means “if you do not study”]
To do the translation
(a) Identify a scheme of abbreviation for basic sentences
(b) Identify logical connectives between variables
2. Convert the following formulae into Conjunctive Normal Form (CNF).
(i) P → Q
(ii) (P → ¬Q) → R
(iii) ¬(P ∧ ¬Q) → (¬R ∨ ¬Q)
3. Show using the truth table method that the corresponding inferences are valid.
(i) P → Q,¬Q |= ¬P
(ii) P → Q |= ¬Q → ¬P
(iii) P → Q,Q → R |= P → R
Check your answers using the Python program tableau prover.py.
4. Repeat Question 3 using resolution. In this case, show
(i) P → Q,¬Q ⊢ ¬P
(ii) P → Q ⊢ ¬Q → ¬P
(iii) P → Q,Q → R ⊢ P → R
5. Determine whether the following sentences are valid (i.e. tautologies) using truth tables.
(i) ((P ∨Q) ∧ ¬P ) → Q
(ii) ((P → Q) ∧ ¬(P → R)) → (P → Q)
(iii) ¬(¬P ∧ P ) ∧ P
(iv) (P ∨Q) → ¬(¬P ∧ ¬Q)
Check your answers using the Python program tableau prover.py.
6. Repeat Question 5 using resolution. In this case, try to show
(i) ⊢ ((P ∨Q) ∧ ¬P ) → Q
(ii) ⊢ ((P → Q) ∧ ¬(P → R)) → (P → Q)
(iii) ⊢ ¬(¬P ∧ P ) ∧ P
(iv) ⊢ (P ∨Q) → ¬(¬P ∧ ¬Q)