COMP9414: Artificial Intelligence Tutorial Week 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)