Aims & Procedure

One aim of this assignment is to improve and test your understanding of propositional logic and first-order predicate logic, including their use in mechanised reasoning. A second aim is to develop your skills in analysis and formal reasoning about complex concepts, and to practise writing down formal arguments with clarity.

This document is the assignment spec.  There are six questions which you will find in the re- mainder of this document. Your answers to questions 1–5 are to be submitted through Gradescope, for which there is a menu item on Canvas.

Your answers to question 6 will be submitted on Grok, where you will find a module called “Assignment 1”.  This module will become available on August 31.  It will explain the submission formats in detail, and contain detailed instructions for submission.

You are required to solve the challenges individually.  You will probably find them to be of varying difficulty, but each is worth 20 marks, for a total of 120.

The marks listed on each question do not always reflect the difficulty.  We aim to ensure that anyone with a basic comprehension of the subject matter receives a passing mark.  Getting full marks is intended to be considerably more difficult; the harder questions provide an opportunity for students to distinguish themselves.

Q1 – Propositional Logic: Island Puzzle

The Island of Truth-Tellers and Liars has gained some newcomers.  Whereas truth-tellers always tell the truth and liars always lie, the newcomers sometimes lie and other times tell the truth. In the following scenario, we have three inhabitants of the island, named A, B, and C. They make the following statements:

1. A says: “C is a truth-teller and B is a truth-teller.”

2.  B says: “C is a liar or A is a truth-teller.”

3.  C says: “If B is a liar, then A is a truth-teller.”

Task 1A.    (6 marks, 2 each) Translate (1)–(3) into formulas of propositional logic. Remember to explain your translation!

Task  1B.    (14 marks) Assuming there is at  least one truth-teller and at  least one  liar, identify (2 marks) and prove (12 marks) which of A, B and C is a truth-teller, liar or newcomer.

Q2 – Propositional Logic: Validity and Satisfiability

(20 marks, 5 marks each) For each of the following propositional formulas, determine whether it is valid, unsatisfiable, or neither.  If it is valid or unsatisfiable, prove it using resolution.  If it is neither, demonstrate this with two appropriate truth assignments, one for which the formula is true and one for which it is false.

1.  (P → P) → ¬P

2.  ¬(P ↔ Q) ↔ ((P ∨ Q) ∧ ¬(P ∧ Q))

3.  ¬(((P → Q) → P) → P)

4.  ((P → Q) → (Q → R)) → (P → R)

Hint:   If you are unsure, you can use a truth table to help you decide!

Q3 – Predicate Logic: Equivalence Proofs

In the lectures, we introduced the following propositional equivalences:

P ∧ Q ≡ Q ∧ P

P ∨ Q ≡ Q ∨ P

P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R

P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

P ≡ ¬¬P

P → Q ≡ ¬P ∨ Q

¬P → ¬Q ≡ Q → P

(3.1)  (3.2)  (3.3)  (3.4)  (3.5)  (3.6)  (3.7)  (3.8)  (3.9) (3.10) (3.11)

We also introduced the following predicate logic equivalences, which hold for any formulas F and G:

∃x(¬F) ≡ ¬∀x F                                  (3.12)

∀x(¬F) ≡ ¬∃x F                                  (3.13)

∃x(F ∨ G) ≡ (∃x F) ∨ (∃x G)                          (3.14)

∀x(F ∧ G) ≡ (∀x F) ∧ (∀x G)                         (3.15)

Additionally, the following equivalences hold whenever 从 is not free in G:

∃x G ≡ G

∀x G ≡ G

∃x(F ∧ G) ≡ (∃x F) ∧ G

∀x(F ∨ G) ≡ (∀x F) ∨ G

∀x(F → G) ≡ (∃x F) → G

∀x(G → F) ≡ G → (∀x F)

(3.16) (3.17) (3.18) (3.19) (3.20) (3.21)