Q1

A) Translate the following statements into predicate logic

Mary loves everyone
Every student except George smiles.
Every student who walks talks
Every boy who loves Mary hates every other boy who Mary loves
No one who runs walks
There is a person who writes computer class

Sol

$L o v e s (x, y)$ : $x$ loves $y$
$S t u d e n t (x)$ : $x$ is a student
$S m i l e s (x)$ : $x$ smiles
$W a l k s (x)$ : $x$ walks
$T a l k s (x)$ : $x$ talks
$B o y (x)$ : $x$ is a boy
$H a t e s (x, y)$ : $x$ hates $y$
$R u n s (x)$ : $x$ runs
$P e r s o n (x)$ : $x$ is a person
$W r i t e s (x, y)$ : $x$ writes $y$

1. Mary loves everyone

\forall x L o v e s (M a r y, x)

2. Every student except George smiles.

\forall x ((S t u d e n t (x) \land x \neq G e o r g e) \to S m i l e s (x)) \land \neg S m i l e s (G e o r g e)

3. Every student who walks talks

\forall x ((S t u d e n t (x) \land W a l k s (x)) \to T a l k s (x))

4. Every boy who loves Mary hates every other boy who Mary loves

\forall x \forall y ((B o y (x) \land L o v e s (x, M a r y) \land B o y (y) \land L o v e s (M a r y, y) \land x \neq y) \to H a t e s (x, y))

5. No one who runs walks

\forall x (R u n s (x) \to \neg W a l k s (x))

(Alternatively: $\neg \exists x (R u n s (x) \land W a l k s (x))$ )

6. There is a person who writes computer class

\exists x (P e r s o n (x) \land W r i t e s (x, C o m p u t e r C l a s s))

B) Using the resolution algorithm (Forward and backward) prove that: John likes peanuts.

John likes all kind of food.
Apple and vegetable are food
Anything anyone eats and not killed is food.
Anil eats peanuts and still alive
Harry eats everything that Anil eats.

Sol

1. Define Predicates and Translate to First-Order Logic:

$F o o d (x)$ : $x$ is food
$L i k e s (x, y)$ : $x$ likes $y$
$E a t s (x, y)$ : $x$ eats $y$
$K i l l e d (x)$ : $x$ is killed (Note: "still alive" will be represented as $\neg K i l l e d (x)$ to match the wording of premise 3).

Premises:

John likes all kind of food: $\forall x (F o o d (x) \to L i k e s (J o h n, x))$
Apple and vegetable are food: $F o o d (A p p l e) \land F o o d (V e g e t a b l e)$
Anything anyone eats and not killed is food: $\forall x \forall y ((E a t s (x, y) \land \neg K i l l e d (x)) \to F o o d (y))$
Anil eats peanuts and still alive: $E a t s (A n i l, P e a n u t s) \land \neg K i l l e d (A n i l)$
Harry eats everything that Anil eats: $\forall x (E a t s (A n i l, x) \to E a t s (H a r r y, x))$

Goal: $L i k e s (J o h n, P e a n u t s)$

2. Convert to Conjunctive Normal Form (CNF) Clauses:

C1: $\neg F o o d (x) \lor L i k e s (J o h n, x)$
C2a: $F o o d (A p p l e)$
C2b: $F o o d (V e g e t a b l e)$
C3: $\neg E a t s (x, y) \lor K i l l e d (x) \lor F o o d (y)$
C4a: $E a t s (A n i l, P e a n u t s)$
C4b: $\neg K i l l e d (A n i l)$
C5: $\neg E a t s (A n i l, x) \lor E a t s (H a r r y, x)$

Method 1: Forward Resolution (Fact-Driven)

In forward resolution, we start with our known facts and continuously resolve them with implications to derive new facts until we reach the goal: $L i k e s (J o h n, P e a n u t s)$ .

Resolve C3 ( $\neg E a t s (x, y) \lor K i l l e d (x) \lor F o o d (y)$ ) with fact C4b ( $\neg K i l l e d (A n i l)$ ) by substituting $x = A n i l$ :
- Result: $\neg E a t s (A n i l, y) \lor F o o d (y)$
Resolve the Result ( $\neg E a t s (A n i l, y) \lor F o o d (y)$ ) with fact C4a ( $E a t s (A n i l, P e a n u t s)$ ) by substituting $y = P e a n u t s$ :
- Result: $F o o d (P e a n u t s)$ (We have now proven peanuts are food)
Resolve C1 ( $\neg F o o d (x) \lor L i k e s (J o h n, x)$ ) with the new fact $F o o d (P e a n u t s)$ by substituting $x = P e a n u t s$ :
- Result: $L i k e s (J o h n, P e a n u t s)$
  
  Goal Derived!

في اللاب مشروح ان في ال forward برضو ضيف ال negated goal to the facts and start from the facts فا الحل حرفيا هتضيف زيادة بس بعد ما توصل لستيب 3 فوق انك ناخد resolution with negated goal و توصل لل contradiction

Method 2: Backward Resolution (Goal-Driven / Refutation)

In backward resolution, we negate the goal and resolve it against the clauses to find a logical contradiction (the empty clause, $◻$ ).

Negated Goal (C6): $\neg L i k e s (J o h n, P e a n u t s)$

Resolve C6 ( $\neg L i k e s (J o h n, P e a n u t s)$ ) with C1 ( $\neg F o o d (x) \lor L i k e s (J o h n, x)$ ) using $x = P e a n u t s$ :
- Result: $\neg F o o d (P e a n u t s)$
Resolve $\neg F o o d (P e a n u t s)$ with C3 ( $\neg E a t s (x, y) \lor K i l l e d (x) \lor F o o d (y)$ ) using $y = P e a n u t s$ :
- Result: $\neg E a t s (x, P e a n u t s) \lor K i l l e d (x)$
Resolve the Result with C4a ( $E a t s (A n i l, P e a n u t s)$ ) using $x = A n i l$ :
- Result: $K i l l e d (A n i l)$
Resolve $K i l l e d (A n i l)$ with fact C4b ( $\neg K i l l e d (A n i l)$ ):
- Result: $◻$ (Contradiction)
  
  Contradiction reached! Therefore, the original un-negated goal, "John likes peanuts," must be true.

Q2

1) Establish by forward chaining that the pet is a dog.

Rule 1 IF the pet has hair THEN it is a mammal
Rule 2 IF the pet gives birth THEN it is a mammal
Rule 3 IF the pet has feathers THEN the pet is it is a bird
Rule 4 IF the pet flies AND the animal lays eggs THEN the pet is it is a bird
Rule 5 IF the pet is a mammal AND the pet eats meat THEN it is a carnivore
Rule 6 IF the pet is a mammal AND the pet has pointed teeth AND the pet has claws AND the pet's eyes point forward THEN it is a carnivore
Rule 7 IF the height is <10 cm THEN the size is small
Rule 8 IF the height is >10 cm AND the height is < 30 cm THEN the size is medium
Rule 9 IF the height is >50 cm THEN the size is big
Rule 10 IF the pet is a carnivore AND the pet barks AND the pet has long legs AND the animal is big size THEN the pet is a dog.
R11 IF the pet is a carnivore AND the pet has soft hair AND the pet size is medium THEN the pet is a cat
R12 IF the pet is small AND the pet has short legs AND the pet has soft hair THEN the pet is a mouse
R13 IF the pet has light hair AND the pet size is medium AND the pet is not carnivore THEN then the pet is Guinea pig

Sol

Initial Facts in Working Memory:

gives birth
long legs
height is 70 cm (في الامتحان مكتوبة size فا اعتبرتها غلطة لان ال size في ال rules كلها categorical)
eats meat
barks

Goal:

Prove: the pet is a dog.

Iteration 1:

Check Rule 2: IF the pet gives birth THEN it is a mammal
- Since we have the fact "gives birth", this rule fires.
- New Fact Derived: mammal
Check Rule 9: IF the height is > 50 cm THEN the size is big
- Since we have the fact "size is 70 cm" (which is > 50 cm), this rule fires.
- New Fact Derived: size is big
Current Working Memory: gives birth, long legs, height = 70 cm, eats meat, barks, mammal, size is big.

Iteration 2:

Check Rule 5: IF the pet is a mammal AND the pet eats meat THEN it is a carnivore
- We now have "mammal" and "eats meat" in our working memory. The rule fires.
- New Fact Derived: carnivore
Current Working Memory: [gives birth, long legs, height = 70 cm, eats meat, barks, mammal, size is big, carnivore].

Iteration 3:

Check Rule 10: IF the pet is a carnivore AND the pet barks AND the pet has long legs AND the animal is big size THEN the pet is a dog.
- We check our working memory for the required conditions:
  1. carnivore (Yes)
  2. barks (Yes)
  3. long legs (Yes)
  4. big size (Yes)
- Since all conditions are met, the rule fires.
- New Fact Derived: the pet is a dog

Conclusion: The goal that the pet is a dog has been successfully established using forward chaining.

B) Explain the difference between forward chaining and backward chaining.

Support your answer with an example of giving a good result using forward chaining than backward chaining.

Sol

The Differences

Feature	Forward Chaining	Backward Chaining
Fundamental Approach	Data-Driven: It moves from the bottom up.	Goal-Driven: It moves from the top down.
Starting Point	Starts with the initial facts (the data currently in the working memory).	Starts with a hypothesis or goal (what you want to prove).
Ending Point	Stops when a goal is reached or when no more rules can be fired.	Stops when all sub-goals are proven true by the initial facts.
Rule Matching	Matches the current facts against the IF part (antecedent/premise) of the rules.	Matches the current goal/sub-goal against the THEN part (consequent/conclusion) of the rules.
Action Taken	If a rule fires, it extracts the conclusion and adds it as a new fact to the database.	If a rule matches, it extracts the premises and sets them as new sub-goals to be proven.
Analogy	Like an investigator piecing together clues at a crime scene to figure out what happened and who did it.	Like a doctor starting with a suspected diagnosis (e.g., "flu") and checking if the patient has the specific symptoms to prove it.

When Forward Chaining is Better (The Example)

Forward chaining excels in situations where you have a small number of initial facts but a massive number of possible conclusions, such as in monitoring systems, event-driven systems, or synthesis/design tasks.

Example: A Smart Home Emergency System

Imagine a smart home system with hundreds of rules determining what to do in various situations (turn on sprinklers, call police, lock doors, adjust AC, etc.).

The Facts: The smoke detector in the kitchen triggers (a single new fact).
Using Forward Chaining: The system takes this new fact ("smoke detected"), finds the rule IF smoke detected THEN trigger alarm AND call fire department, and executes it immediately. It is fast and responsive because it only processes the rules relevant to the incoming data.
Using Backward Chaining (Poor Result): The system would have to start by guessing every possible goal. It would ask, "Should I call the police? Let's check the sub-goals... no. Should I turn down the AC? Let's check the sub-goals... no. Should I call the fire department? Let's check the sub-goals... yes, there is smoke." In this scenario, backward chaining is terribly inefficient because it forces the system to evaluate countless irrelevant goals just to figure out what to do with one piece of data, whereas forward chaining handles it instantly.