Q1

A) Consider the following production system:

• Rule 1: IF shape is long AND color is yellow THEN fruit is banana

• Rule 2: IF shape is round AND color is red AND size is medium THEN then fruit is apple

• Rule 3: IF shape is round AND color is red AND size is small THEN then fruit is cherry

• Rule 4: IF skin smell THEN perfumed

• Rule 5: IF fruit is lemon OR fruit is orange OR fruit is pomelo OR fruit is grapefruit THEN citrus fruit

• Rule 6: IF size is medium AND color is yellow AND perfumed THEN then fruit is lemon

• Rule 7: IF size is medium AND color is green THEN fruit is kiwi

• Rule 8: IF size is big AND perfumed AND color is orange AND citrus fruit THEN fruit is grapefruit

• Rule 9: IF perfumed AND color is orange AND size is medium THEN fruit is orange

• Rule 10: IF perfumed AND color is red AND size is small AND no seeds THEN fruit is strawberry

• Rule 11: IF diameter < 2 cm THEN size is small

• Rule 12: IF diameter > 10 cm THEN size is big

• Rule 13: IF diameter > 2 cm AND diameter < 10 cm THEN size is medium

The user inputs the facts: The fruit has no seed, a 7 cm diameter, smelling skin, orange color. Establish by forward chaining and backward chaining that the fruit is a citrus fruit.

Sol:

Initial Facts:

• no seed

• diameter = 7 cm

• skin smell

• color is orange

Goal:

• Prove: citrus fruit

1. Forward Chaining

In forward chaining, we start with the known facts and continuously apply the rules until we reach our goal.

Iteration 1:

• Check Rule 4: IF skin smell THEN perfumed

  • Since we have the fact "skin smell", this rule fires.

  • New Fact derived: perfumed

• Check Rule 13: IF diameter > 2 cm AND diameter < 10 cm THEN size is medium

  • Since our diameter is 7 cm (which is > 2 and < 10), this rule fires.

  • New Fact derived: size is medium

• Current Facts: [no seed, diameter = 7 cm, skin smell, color is orange, perfumed, size is medium].

Iteration 2:

• Check Rule 9: IF perfumed AND color is orange AND size is medium THEN fruit is orange

  • We now have all three facts in our working memory ("perfumed", "color is orange", and "size is medium"). The rule fires.

  • New Fact derived: fruit is orange

• Current Facts: [no seed, diameter = 7 cm, skin smell, color is orange, perfumed, size is medium, fruit is orange].

Iteration 3:

• Check Rule 5: IF fruit is lemon OR fruit is orange OR fruit is pomelo OR fruit is grapefruit THEN citrus fruit

  • Since we have derived "fruit is orange", the OR condition is satisfied. The rule fires.

  • New Fact derived: citrus fruit

Conclusion: The goal citrus fruit has been successfully established.

2. Backward Chaining

In backward chaining, we start with the goal and work backward, setting sub-goals to see if they can be supported by the initial facts.

Main Goal: Prove citrus fruit

• To prove "citrus fruit", we scan the rules for a conclusion that matches. We find Rule 5.

• Rule 5 requires proving at least one of the following sub-goals (OR condition): fruit is lemon, fruit is orange, fruit is pomelo, or fruit is grapefruit.

Attempt Sub-goal 1: Prove fruit is lemon

• We look at Rule 6, which concludes "fruit is lemon".

• It requires: size is medium AND color is yellow AND perfumed.

• Check Facts: Our known fact is "color is orange", not yellow.

• Result: Sub-goal fails. Move to the next OR condition.

Attempt Sub-goal 2: Prove fruit is orange

• We look at Rule 9, which concludes "fruit is orange".

• It requires three conditions: perfumed AND color is orange AND size is medium. We evaluate them one by one:

  1. Check color is orange: This is given as an initial fact. (True)

  2. Check perfumed: This is not an initial fact. Set as a new sub-goal.

     • Find a rule concluding "perfumed": Rule 4.

     • Rule 4 requires skin smell.

     • "skin smell" is an initial fact. (True) -> Therefore, perfumed is True.

  3. Check size is medium: This is not an initial fact. Set as a new sub-goal.

     • Find a rule concluding "size is medium": Rule 13.

     • Rule 13 requires diameter > 2 cm AND diameter < 10 cm.

     • Our initial fact is "diameter = 7 cm", which satisfies the math condition. (True) -> Therefore, size is medium is True.

Conclusion: Because all three prerequisites for Rule 9 (perfumed, color is orange, and size is medium) have been evaluated as True, the sub-goal fruit is orange is proven True. Because "fruit is orange" is True, it satisfies the OR condition in Rule 5, successfully proving the ultimate goal: citrus fruit.

B) Use the Resolution Algorithm to prove that "Alice is successful" based on the following story:

1. Everyone who works hard and gets a promotion is successful.

2. Everyone who is dedicated or talented can work hard.

3. Alice is talented but not dedicated.

4. Everyone who is talented gets a promotion.

5. Prove that Alice is successful.

Sol

To prove that "Alice is successful" using the Resolution Algorithm, we must first translate the story into First-Order Logic, convert those statements into Conjunctive Normal Form (CNF) clauses, negate our goal, and then resolve the clauses to find a contradiction (an empty clause).

1. Define the Predicates

• $W(x)$: $x$ works hard

• $P(x)$: $x$ gets a promotion

• $S(x)$: $x$ is successful

• $D(x)$: $x$ is dedicated

• $T(x)$: $x$ is talented

• $a$: Alice

2. Translate to First-Order Logic

1. Everyone who works hard and gets a promotion is successful:

   $\mathrm{\forall }x((W(x)\wedge P(x))\to S(x))$

2. Everyone who is dedicated or talented can work hard:

   $\mathrm{\forall }x((D(x)\vee T(x))\to W(x))$

3. Alice is talented but not dedicated:

   $T(a)\wedge \mathrm{\neg }D(a)$

4. Everyone who is talented gets a promotion:

   $\mathrm{\forall }x(T(x)\to P(x))$

Goal to prove: $S(a)$ (Alice is successful)

3. Convert to Conjunctive Normal Form (CNF)

We remove implications ($\to$) using the rule $A\to B\equiv \mathrm{\neg }A\vee B$, and distribute to form standalone clauses.

• From Premise 1:

  • $\mathrm{\neg }(W(x)\wedge P(x))\vee S(x)$

  • C1: $\mathrm{\neg }W(x)\vee \mathrm{\neg }P(x)\vee S(x)$

• From Premise 2:

  • $\mathrm{\neg }(D(x)\vee T(x))\vee W(x)$

  • Apply De Morgan's Law: $(\mathrm{\neg }D(x)\wedge \mathrm{\neg }T(x))\vee W(x)$

  • Distribute: $(\mathrm{\neg }D(x)\vee W(x))\wedge (\mathrm{\neg }T(x)\vee W(x))$

  • C2: $\mathrm{\neg }D(x)\vee W(x)$

  • C3: $\mathrm{\neg }T(x)\vee W(x)$

• From Premise 3:

  • C4: $T(a)$

  • C5: $\mathrm{\neg }D(a)$

• From Premise 4:

  • C6: $\mathrm{\neg }T(x)\vee P(x)$

• Negated Goal:

  • To use resolution by refutation, we negate what we want to prove.

  • C7: $\mathrm{\neg }S(a)$

4. Resolution Steps

Now we perform resolution on our set of clauses {C1, C2, C3, C4, C5, C6, C7} to derive a contradiction (an empty clause, often denoted as $◻$ or $\mathrm{\perp }$).

• Step 1: Resolve C6 ($\mathrm{\neg }T(x)\vee P(x)$) with C4 ($T(a)$)

  • Substitute $x=a$ into C6: $\mathrm{\neg }T(a)\vee P(a)$

  • $\mathrm{\neg }T(a)$ and $T(a)$ cancel out.

  • C8: $P(a)$ (Meaning: Alice gets a promotion)

• Step 2: Resolve C3 ($\mathrm{\neg }T(x)\vee W(x)$) with C4 ($T(a)$)

  • Substitute $x=a$ into C3: $\mathrm{\neg }T(a)\vee W(a)$

  • $\mathrm{\neg }T(a)$ and $T(a)$ cancel out.

  • C9: $W(a)$ (Meaning: Alice works hard)

• Step 3: Resolve C1 ($\mathrm{\neg }W(x)\vee \mathrm{\neg }P(x)\vee S(x)$) with C7 ($\mathrm{\neg }S(a)$)

  • Substitute $x=a$ into C1: $\mathrm{\neg }W(a)\vee \mathrm{\neg }P(a)\vee S(a)$

  • $S(a)$ and $\mathrm{\neg }S(a)$ cancel out.

  • C10: $\mathrm{\neg }W(a)\vee \mathrm{\neg }P(a)$

• Step 4: Resolve C10 ($\mathrm{\neg }W(a)\vee \mathrm{\neg }P(a)$) with C8 ($P(a)$)

  • $\mathrm{\neg }P(a)$ and $P(a)$ cancel out.

  • C11: $\mathrm{\neg }W(a)$

• Step 5: Resolve C11 ($\mathrm{\neg }W(a)$) with C9 ($W(a)$)

  • $\mathrm{\neg }W(a)$ and $W(a)$ cancel out, leaving nothing.

  • C12: $\perp$ (Contradiction)

Conclusion

By negating the goal ($\mathrm{\neg }S(a)$) and using the resolution algorithm, we reached a logical contradiction (the empty clause). Therefore, the original premise must be true. Alice is successful.

C) Translate the following statements into predicate logic:

a. Every student who studies passes the exam.

b. Mathematics and Physics are subjects.

c. Anything that is taught by a teacher is a subject.

d. Alice studies Mathematics and has passed the exam.

e. Bob studies everything that Alice studies.

Sol

Constants:

• $a$: Alice

• $b$: Bob

• $m$: Mathematics

• $p$: Physics

• $e$: the exam

Predicates:

• $Student(x)$: $x$ is a student

• $Studies(x)$: $x$ studies

• $Studies(x,y)$: $x$ studies subject $y$

• $Passes(x,y)$: $x$ passes $y$

• $Subject(x)$: $x$ is a subject

• $Teacher(x)$: $x$ is a teacher

• $Teaches(x,y)$: $x$ teaches $y$

a. Every student who studies passes the exam.

b. Mathematics and Physics are subjects.

c. Anything that is taught by a teacher is a subject.

(Alternatively: $\mathrm{\forall }x\mathrm{\forall }y((Teacher(y)\wedge Teaches(y,x))\to Subject(x))$)

d. Alice studies Mathematics and has passed the exam.

e. Bob studies everything that Alice studies.