Due date: Thur, 25 Sep 2025  (23:55).

Evaluation: 100 marks = 15%.

Submission: Moodle.

Submission instructions and late subimssion policy: In Moodle.

For this assignment, there are no restrictions on the use of generative AI technologies. However, whenever used, generative AI must be acknowledged.  For further informa- tion, please, refer to the current university policy on the use of generative AI.

And we don't accept handwritten.

Q1: Propositional Logic — Advanced Validity and CNF Transformation

Given the formulas:

ϕ₁ = ((A V (B → C)) Λ (¬C V D)) → ((A → D) V (C ↔ E))

ϕ₂ = (((¬A Λ B) V (C → D)) Λ (¬E V A)) → ((¬D V F) ↔ (A Λ B))

ϕ₃ = ((A ↔ B) V (C → D)) Λ ((¬A V ¬D) → (F Λ ¬G))

(a) For each formula:                                                                                                (9 marks)

Determine whether the clause is valid, satisfiable but not valid, or unsatisfiable. Justify using truth assignments, or semantic arguments.

(b) Convert each formula into CNF. Identify Horn clauses where applicable.               (12 marks)

(c) For ϕ₂, assume F is always false:

(i) What is the effect on satisfiability?                                                                       (4 marks)

(ii) Can you infer anything about A or B? Justify.                                                     (5 marks)

Q2: Enhanced Forward/Backward Reasoning — Deceptive Rules and Sparse Inference

Q2.1: Logic Translation with Mixed Relevance (10 marks)

Convert the following 10 statements into propositional logic, using the symbol key:

S: is Sick

V: likely to Vomit

P: looks Pale

T: is Thirsty

H: has High Temperature

NS: has Not Slept well

NF: does Not Feel well

F: has Fever

W: drinks Water

E: is Exhausted

A: has Allergy

M: has Muscle Pain

If the knowledge base does not have the symbol key, it means that you can ignore it.

R1. If a person looks pale, is thirsty, and has not slept well, then they are sick.

R2. If a person has a fever, then they have a high temperature.

R3. If a person has a high temperature, then they are thirsty.

R4. If a person is exhausted, then they have not slept well.

R5. If a person has not slept well, then they look pale.

R6. If a person looks pale, then they should drink water.

R7. If a person has muscle pain, then they are not feeling well.

R8. A person has an allergy if they sneeze in spring.

R9. If a person is not thirsty and has slept well, then they either will not vomit or will drink water.

R10. If a person is not exhausted and not thirsty, then they might either feel well or drink water.

Initial facts (observations):

•    The person has a fever.