COS3751 - Assignment 3 2023

UNISA
Assignment 3
COS3751
Title

, Question 1
FOL:
∀x (∀y (⌐P(y) V Q(x, y)) → (¬∀y Q(y, x)))

In CNF:
1. Eliminate the Implication (→):
¬(¬P(y) V Q(x, y)) V (¬∀y Q(y, x))

2. Apply De Morgan's Law:
(P(y) ∧ ¬Q(x, y)) V (¬∀y Q(y, x))

3. Apply Quantifier Negation:
(P(y) ∧ ¬Q(x, y)) V (∃y ¬Q(y, x))

4. Skolemization: Introduce Skolem constants for the existential quantifiers. Let's say we use
Skolem constants s1 and s2:
(P(y) ∧ ¬Q(x, y)) V ¬Q(s2, x)

5. Distribute the Disjunction (∨) over the Conjunction (∧):
(P(y) V ¬Q(s2, x)) ∧ (¬Q(x, y) V ¬Q(s2, x))

6. Apply Distribution again:
(P(y) V ¬Q(s2, x)) ∧ (¬Q(x, y) ∧ ¬Q(s2, x))

7. Apply Distribution one last time:
(P(y) ∧ ¬Q(x, y)) ∧ (P(y) ∧ ¬Q(s2, x)) ∧ (¬Q(x, y) ∧ ¬Q(s2, x))

Now the sentence is in Conjunctive Normal Form (CNF), which is a conjunction (AND) of clauses,
where each clause is a disjunction (OR) of literals.


Question 2
2.1)

• Predicates:
Passes(x, y): Person x passes exam y.
Happy(x): Person x is happy.
WinsLottery(x): Person x wins the lottery.
StudiesHard(x): Person x studies hard.
Lucky(x): Person x is lucky.
• Constants:
Jack: Refers to the person named Jack.
2.2)