COS3751 ASSIGNMENT 3 ANS 2023

QUESTION 1

To convert the given FOL sentence to Conjunctive Normal Form (CNF), we need to follow these steps:



Step 1: Move the quantifiers to the leftmost position:

∀x(∀y(¬P(y) ∨ Q(x, y)) ⇒ (¬∀yQ(y, x)))



Step 2: Eliminate the implication (⇒) using the equivalence A ⇒ B ≡ ¬A ∨ B:

∀x(∀y(¬P(y) ∨ Q(x, y)) ⇒ (¬∀yQ(y, x))) is equivalent to

∀x(∀y(¬(¬P(y) ∨ Q(x, y)) ∨ (¬∀yQ(y, x))))



Step 3: Apply De Morgan's law to eliminate the negation inside:

∀x(∀y((P(y) ∧ ¬Q(x, y)) ∨ (∃y¬Q(y, x))))



Step 4: Distribute the quantifiers over the disjunction (∨):

, ∀x∀y((P(y) ∧ ¬Q(x, y)) ∨ (∃y¬Q(y, x)))



Step 5: Convert the sentence to Conjunctive Normal Form (CNF):

∀x∀y(P(y) ∨ ¬Q(x, y)) ∧ ∀x∀y(∃y¬Q(y, x))



Therefore, the given FOL sentence has been converted to CNF as:

∀x∀y(P(y) ∨ ¬Q(x, y)) ∧ ∀x∀y(∃y¬Q(y, x))



QUESTION 2

2.1) Vocabulary for the statements:

- AI exam: AI_exam(x)

- Passes exams: Passes_exams(x)

- Wins the lottery: Wins_lottery(x)

- Is happy: Is_happy(x)

- Studies hard: Studies_hard(x)

- Is lucky: Is_lucky(x)

- Jack: jack



2.2) Translation of English sentences to FOL statements:

1. ∀x (AI_exam(x) ∧ Wins_lottery(x)) ⇒ Is_happy(x)

2. ∀x (Studies_hard(x) ∨ Is_lucky(x)) ⇒ Passes_exams(x)

3. ¬Studies_hard(jack)

4. Is_lucky(jack)

5. ∀x (Is_lucky(x) ⇒ Wins_lottery(x))



2.3) Conversion of FOL statements to CNF:

1. ¬(AI_exam(x) ∧ Wins_lottery(x)) ∨ Is_happy(x)

2. ¬(Studies_hard(x) ∨ Is_lucky(x)) ∨ Passes_exams(x)

3. ¬Studies_hard(jack)

4. Is_lucky(jack)

5. ¬Is_lucky(x) ∨ Wins_lottery(x)