Group C — Long / Numerical Questions (15 Marks Each)

Resolution Refutation: Marcus is Dead

Part (a) FOL Conversion and Resolution Proof:

1. Axioms in First-Order Logic (FOL):

1. Marcus was a man: \(\text{Man(Marcus)}\)
2. Marcus was a Pompeian: \(\text{Pompeian(Marcus)}\)
3. All Pompeians were Romans: \(\forall x (\text{Pompeian}(x) \implies \text{Roman}(x))\)
4. Caesar was a ruler: \(\text{Ruler(Caesar)}\)
5. All Romans were either loyal to Caesar or hated him: \(\forall x (\text{Roman}(x) \implies (\text{LoyalTo}(x, Caesar) \lor \text{Hate}(x, Caesar)))\)
6. Everyone is loyal to someone: \(\forall x \exists y (\text{LoyalTo}(x, y))\)
7. People only try to assassinate rulers they are not loyal to: \(\forall x \forall y ((\text{Person}(x) \land \text{Ruler}(y) \land \text{TryAssassinate}(x, y)) \implies \neg \text{LoyalTo}(x, y))\)
8. Marcus tried to assassinate Caesar: \(\text{TryAssassinate(Marcus, Caesar)}\)
9. All men are persons: \(\forall x (\text{Man}(x) \implies \text{Person}(x))\) (Implicit axiom required for chaining)
10. All men are mortal: \(\forall x (\text{Man}(x) \implies \text{Mortal}(x))\) (Given, but 'dead' relies on hate in this specific historical problem variant. We prove 'Marcus hated Caesar' as requested by standard PYQ).

2. Conversion to CNF (Clause Form):

• C1: \(\text{Man(Marcus)}\)
• C2: \(\text{Pompeian(Marcus)}\)
• C3: \(\neg \text{Pompeian}(x_1) \lor \text{Roman}(x_1)\)
• C4: \(\text{Ruler(Caesar)}\)
• C5: \(\neg \text{Roman}(x_2) \lor \text{LoyalTo}(x_2, Caesar) \lor \text{Hate}(x_2, Caesar)\)
• C6: \(\neg \text{Person}(x_3) \lor \neg \text{Ruler}(y_1) \lor \neg \text{TryAssassinate}(x_3, y_1) \lor \neg \text{LoyalTo}(x_3, y_1)\)
• C7: \(\text{TryAssassinate(Marcus, Caesar)}\)
• C8: \(\neg \text{Man}(x_4) \lor \text{Person}(x_4)\)

3. Resolution Steps (Proving Marcus hated Caesar):

• Negate Goal: \(\neg \text{Hate(Marcus, Caesar)}\) (Clause 9)
• Resolve C2 and C3 \(\{x_1 / Marcus\}\) \(\implies\) \(\text{Roman(Marcus)}\) (Clause 10)
• Resolve C10 and C5 \(\{x_2 / Marcus\}\) \(\implies\) \(\text{LoyalTo}(Marcus, Caesar) \lor \text{Hate}(Marcus, Caesar)\) (Clause 11)
• Resolve C11 and C9 \(\implies\) \(\text{LoyalTo(Marcus, Caesar)}\) (Clause 12)
• Resolve C1 and C8 \(\{x_4 / Marcus\}\) \(\implies\) \(\text{Person(Marcus)}\) (Clause 13)
• Resolve C6, C13, C4, and C7 \(\{x_3 / Marcus, y_1 / Caesar\}\) \(\implies\) \(\neg \text{LoyalTo(Marcus, Caesar)}\) (Clause 14)
• Resolve C12 and C14 \(\implies\) \(\emptyset\) (Contradiction!)

Part (b) Unification Algorithm:

Unification is a recursive algorithm that takes two literals as input and returns a substitution (Most General Unifier, MGU) that makes them identical, or reports FAILURE.

• If they are identical constants/variables, return empty substitution \(\{\}\).
• If one is a variable \(x\) and the other is a term \(t\):
  - Check if \(x\) occurs inside \(t\) (Occurs Check). If yes, return FAILURE.
  - Else, return substitution \(\{x/t\}\).
• If they are predicates (e.g., \(P(a,b)\) and \(P(x,y)\)), ensure the predicate names match and arity (number of arguments) match. Recursively unify each argument pair, composing the substitutions.

Alpha-Beta Pruning and Minimax Properties

Part (a) Alpha-Beta Pruning Execution Trace:

Given leaf nodes (L to R): 3, 5, 6, 9, 1, 2, 0, -1.

• Bottom-Up Evaluation:
  - MAXL1 evaluates to \(\max(3, 5) = 5\).
  - MAXL2 evaluates to \(\max(6, 9) = 9\).
  - MIN1 receives 5 and 9. It evaluates to \(\min(5, 9) = 5\).
  - Root MAX receives 5 from the left branch. It updates its \(\alpha = 5\).
  - MAXR1 evaluates to \(\max(1, 2) = 2\).
  - MIN2 evaluates its first child (MAXR1) and gets 2. MIN2's provisional value is now \(\le 2\). Thus, MIN2's \(\beta = 2\).
• Pruning Trigger: At MIN2, \(\alpha = 5\) (from Root) and \(\beta = 2\). Since \(\alpha \ge \beta\) (\(5 \ge 2\)), the remaining children of MIN2 (the MAXR2 branch) are completely pruned. Root MAX ultimately chooses the left branch with a value of 5.

Part (b) Minimax Algorithm Properties:

• Completeness: Yes, it is complete if the game tree is finite (e.g., maximum depth \(m\) is bounded).
• Optimality: Yes, it is optimal against an optimal opponent. If the opponent plays sub-optimally, Minimax still guarantees at least the computed score.
• Time Complexity: \(O(b^m)\), where \(b\) is the legal moves (branching factor) and \(m\) is the maximum depth.
• Space Complexity: \(O(bm)\) if generating all successors at once, or \(O(m)\) if generating them one at a time (like DFS).

Decision Trees: Information Gain and Pruning

Part (a) Information Gain Calculation:

Given Dataset \(S\) with 14 total samples: 9 'Yes' and 5 'No'.

1. Calculate Entropy of the Root Dataset \(H(S)\):
   \(H(S) = - \left(\frac{9}{14}\right) \log_2\left(\frac{9}{14}\right) - \left(\frac{5}{14}\right) \log_2\left(\frac{5}{14}\right) = 0.940 \text{ bits}\)
2. Calculate Expected Entropy after splitting on an Attribute (e.g., 'Wind'):
   Assume 'Wind' splits the data into 8 'Weak' (6 Yes, 2 No) and 6 'Strong' (3 Yes, 3 No).
   \(H(S_{\text{Weak}}) = -\left(\frac{6}{8}\right)\log_2\left(\frac{6}{8}\right) - \left(\frac{2}{8}\right)\log_2\left(\frac{2}{8}\right) = 0.811\)
   \(H(S_{\text{Strong}}) = -\left(\frac{3}{6}\right)\log_2\left(\frac{3}{6}\right) - \left(\frac{3}{6}\right)\log_2\left(\frac{3}{6}\right) = 1.0\)
   \(H(S | \text{Wind}) = \left(\frac{8}{14} \times 0.811\right) + \left(\frac{6}{14} \times 1.0\right) = 0.892\)
3. Calculate Information Gain:
   \(IG(S, \text{Wind}) = H(S) - H(S | \text{Wind}) = 0.940 - 0.892 = 0.048 \text{ bits}\)

The ID3 algorithm calculates the Information Gain for every attribute (Outlook, Temp, Humidity, Wind) and selects the one with the highest IG as the root node. It then recursively applies this process to the child subsets.

Part (b) Overfitting and Pruning:

• Overfitting: Occurs when a decision tree grows too deep and complex, memorizing the noise and outliers in the training data rather than generalizing the underlying pattern. An overfitted tree performs perfectly on training data but poorly on unseen test data.
• Pruning: The solution to overfitting. It reduces the size of decision trees by removing sections of the tree that provide little power to classify instances.
  • Pre-pruning: Halts tree construction early (e.g., stopping when a node has fewer than \(N\) samples, or when Information Gain falls below a threshold).
  • Post-pruning: Grows the tree to its maximum depth, then works bottom-up, collapsing leaf nodes into their parents if the removal does not decrease classification accuracy on a validation set.

Bayesian Networks and Naive Bayes

Part (a) Bayesian Network Joint Probability:

Given a Burglar Alarm network with variables: Burglary (\(B\)), Earthquake (\(E\)), Alarm (\(A\)), JohnCalls (\(J\)), MaryCalls (\(M\)).

Network topology: \(B\) and \(E\) are independent root nodes pointing to \(A\). \(A\) points to both \(J\) and \(M\).

Goal: Calculate the joint probability \(P(B \land \neg E \land A \land J \land \neg M)\).

Using the chain rule parameterized by the BBN topology, the joint probability factors as:

Assuming standard Pearl's network CPT values:

• \(P(B) = 0.001\)
• \(P(\neg E) = 1 - P(E) = 1 - 0.002 = 0.998\)
• \(P(A | B, \neg E) = 0.94\)
• \(P(J | A) = 0.90\)
• \(P(\neg M | A) = 1 - P(M | A) = 1 - 0.70 = 0.30\)

Calculation: \(0.001 \times 0.998 \times 0.94 \times 0.90 \times 0.30 = 0.0002532924 \approx 0.000253\)

Part (b) Naive Bayes Classifier for Text Classification:

The Naive Bayes Classifier is based on applying Bayes' theorem with a strong (naive) assumption of conditional independence between the features (words) given the class label (e.g., Spam or Ham).

• It calculates the prior probability of each class \(P(\text{Class})\) from the training data frequency.
• It calculates the likelihood of each word occurring in that class \(P(\text{Word}_i | \text{Class})\). Laplace Smoothing is often used to prevent zero probabilities for unseen words.
• To classify a new email, it multiplies these probabilities together and selects the class with the highest posterior probability (Maximum A Posteriori - MAP).

A* Search Trace and Optimality Proof

Part (a) Tracing A* Search:

A* evaluates nodes using \(f(n) = g(n) + h(n)\).

• Initialization: Open List = \([S (f = 0 + h(S))]\), Closed List = \([]\)
• Step 1: Pop \(S\) from Open. Generate successors. Calculate \(g\), \(h\), and \(f\) for each. Add successors to Open. Add \(S\) to Closed.
• Step 2: Sort Open List by lowest \(f(n)\). Pop the node with the lowest \(f(n)\). If it's a Goal, terminate and retrace path.
• Step 3: If not a goal, generate its successors. If a successor is already in Open or Closed with a higher \(g(n)\) cost, update its parent pointer and lower its \(g(n)\) (and \(f(n)\)). Re-push to Open.

Part (b) Proof of Optimality for A* (Tree Search):

Theorem: A* search is optimal if the heuristic \(h(n)\) is admissible (i.e., \(h(n) \le h^*(n)\) for all \(n\), where \(h^*(n)\) is the true optimal cost).

Proof by Contradiction:

1. Assume A* returns a suboptimal goal node \(G_2\) with path cost \(f(G_2) = g(G_2) > C^*\) (where \(C^*\) is the optimal cost). Since it's a goal, \(h(G_2) = 0\).
2. Let \(G_1\) be the true optimal goal node, so \(f(G_1) = g(G_1) = C^*\).
3. Before \(G_2\) was chosen for expansion, there must have been an unexpanded node \(n\) on the Open list that is on the optimal path to \(G_1\).
4. Because \(h(n)\) is admissible, \(f(n) = g(n) + h(n) \le C^*\).
5. From step 1, we know \(f(G_2) > C^*\).
6. Therefore, \(f(n) < f(G_2)\).
7. Since A* always expands the node with the lowest \(f\)-value, it should have expanded \(n\) before \(G_2\).
8. This contradicts the assumption that A* selected \(G_2\) while \(n\) was on the Open list. Thus, A* must never return a suboptimal goal. \(\blacksquare\)

CSP Map Coloring and Arc Consistency (AC-3)

Part (a) CSP Map Coloring Formulation:

Suppose we have 4 adjacent regions: \(A, B, C, D\) (e.g., \(A\) neighbors \(B, C, D\); \(B\) neighbors \(A, C\); \(C\) neighbors \(A, B, D\); \(D\) neighbors \(A, C\)). We must color them using 3 colors: Red, Green, Blue.

• Variables (\(X\)): \(\{A, B, C, D\}\)
• Domain (\(D\)): \(\{R, G, B\}\) for all variables.
• Constraints (\(C\)): Adjacent regions must have different colors. \(\{A \neq B, A \neq C, A \neq D, B \neq C, C \neq D\}\)

Part (b) Tracing AC-3 Algorithm:

AC-3 enforces arc consistency by ensuring that for every directed arc \((X_i, X_j)\), every value in \(D_i\) has a valid corresponding value in \(D_j\).

1. Initialization: Insert all arcs into a Queue: \((A,B), (B,A), (A,C), (C,A), (A,D), (D,A), (B,C), (C,B), (C,D), (D,C)\).
2. Initial Check: All domains are \(\{R, G, B\}\). For any arc, say \((A,B)\), if \(A=R\), \(B\) can be \(G\) or \(B\). Thus, no values violate the constraints initially. The graph is initially arc-consistent.
3. Constraint Propagation (During Search): Assume we assign \(A = Red\).
4. The domain of \(A\) becomes \(\{R\}\).
5. Queue contains \((B,A)\). To make \(B\) consistent with \(A\), we must remove \(R\) from \(B\)'s domain. \(D_B\) becomes \(\{G, B\}\).
6. Queue contains \((C,A)\). Remove \(R\) from \(C\)'s domain. \(D_C\) becomes \(\{G, B\}\).
7. Queue contains \((D,A)\). Remove \(R\) from \(D\)'s domain. \(D_D\) becomes \(\{G, B\}\).
8. Because \(D_B, D_C, D_D\) changed, we re-evaluate their arcs. e.g., Arc \((B,C)\). If \(B=G\), \(C\) can be \(B\). If \(B=B\), \(C\) can be \(G\). No further domain reductions occur yet until another assignment is made.

Simulated Annealing in Detail

Part (a) Simulated Annealing Algorithm:

Simulated Annealing avoids local maxima by probabilistically accepting worse states. The probability of acceptance decreases as the system "cools" down.

Part (b) Calculating Acceptance Probability \(P = e^{\frac{\Delta E}{T}}\):

Assume a "bad move" where the new state is worse by an energy difference of \(\Delta E = -5\).

• At high temperature (\(T = 100\)):
  \(P = e^{-5 / 100} = e^{-0.05} \approx 0.9512\) (95.12% chance to accept the bad move). The algorithm explores freely.
• At medium temperature (\(T = 10\)):
  \(P = e^{-5 / 10} = e^{-0.5} \approx 0.6065\) (60.65% chance to accept). Exploration decreases.
• At low temperature (\(T = 1\)):
  \(P = e^{-5 / 1} = e^{-5} \approx 0.0067\) (0.67% chance to accept). The algorithm has essentially converged into a greedy hill-climbing search.

Resolution Refutation: John is a Criminal

Part (a) FOL Conversion:

1. It is a crime for an American to sell weapons to hostile nations:
   \(\forall x \forall y \forall z ((\text{American}(x) \land \text{Weapon}(y) \land \text{Sells}(x, y, z) \land \text{Hostile}(z)) \implies \text{Criminal}(x))\)
2. Country Nono has some missiles:
   \(\exists x (\text{Owns}(Nono, x) \land \text{Missile}(x))\). Skolemized to: \(\text{Owns}(Nono, M_1)\) and \(\text{Missile}(M_1)\).
3. All of Nono's missiles were sold to it by John:
   \(\forall x ((\text{Missile}(x) \land \text{Owns}(Nono, x)) \implies \text{Sells}(John, x, Nono))\)
4. Missiles are weapons:
   \(\forall x (\text{Missile}(x) \implies \text{Weapon}(x))\) (Implicit domain knowledge)
5. An enemy of America counts as "hostile":
   \(\forall x (\text{Enemy}(x, America) \implies \text{Hostile}(x))\) (Implicit domain knowledge)
6. Nono is an enemy of America:
   \(\text{Enemy}(Nono, America)\)
7. John is an American:
   \(\text{American}(John)\)

Part (b) Resolution Tree Derivation:

• Negated Goal: \(\neg \text{Criminal}(John)\)
• From (1) and \(\neg \text{Criminal}(John)\) \(\{x/John\}\): We need to prove he is an American, sells a weapon, to a hostile nation. \(\implies \neg \text{American}(John) \lor \neg \text{Weapon}(y) \lor \neg \text{Sells}(John, y, z) \lor \neg \text{Hostile}(z)\)
• Resolve with (7) \(\text{American}(John)\): \(\implies \neg \text{Weapon}(y) \lor \neg \text{Sells}(John, y, z) \lor \neg \text{Hostile}(z)\)
• Resolve with (5) and (6) \(\implies \text{Hostile}(Nono)\) \(\{z/Nono\}\): \(\implies \neg \text{Weapon}(y) \lor \neg \text{Sells}(John, y, Nono)\)
• Resolve with (3) \(\{x/y\}\): \(\implies \neg \text{Weapon}(y) \lor \neg \text{Missile}(y) \lor \neg \text{Owns}(Nono, y)\)
• Resolve with (4): \(\implies \neg \text{Missile}(y) \lor \neg \text{Owns}(Nono, y)\)
• Resolve with (2) \(\{y/M_1\}\): \(\implies \text{Empty Clause} (\emptyset)\). Contradiction found, John is a Criminal.

Fuzzy Logic Controller: Automatic Washing Machine

Part (a) Controller Design:

The goal is to map two crisp inputs (Dirtiness, Fabric Type) to a single crisp output (Wash Time) using a Mamdani Fuzzy Inference System.

• Input 1 (Dirtiness %): Fuzzy sets \(\{Low, Medium, High\}\)
• Input 2 (Fabric Type): Fuzzy sets \(\{Silk (Delicate), Cotton, Jeans (Strong)\}\)
• Output (Wash Time mins): Fuzzy sets \(\{Short, Normal, Long, Very Long\}\)

Part (b) Execution Pipeline:

1. Fuzzification: Assume sensor inputs: Dirtiness = 80%, Fabric = Jeans. By projecting 80% onto the Dirtiness membership functions, we get \(\mu_{High}(Dirt) = 0.8\), \(\mu_{Medium}(Dirt) = 0.2\). For Jeans, \(\mu_{Strong}(Fabric) = 0.9\).
2. Fuzzy Rules Matrix (IF-THEN):
   • IF Dirt is High AND Fabric is Strong THEN Wash Time is Very Long.
   • IF Dirt is Medium AND Fabric is Strong THEN Wash Time is Long.
   • IF Dirt is High AND Fabric is Delicate THEN Wash Time is Normal (to prevent damage).
3. Rule Evaluation (MIN Operator for AND):
   Rule 1 firing strength: \(\min(0.8, 0.9) = 0.8\). Output fuzzy set 'Very Long' is clipped at height 0.8.
   Rule 2 firing strength: \(\min(0.2, 0.9) = 0.2\). Output fuzzy set 'Long' is clipped at height 0.2.
4. Aggregation & Defuzzification (Centroid Method):
   The clipped output sets are unioned together (MAX operator) to form an irregular geometric shape on the Wash Time axis. The crisp wash time is computed by finding the geometric Center of Gravity (Centroid) of this shape on the X-axis: \[ Z = \frac{\sum \mu(z) \cdot z}{\sum \mu(z)} \]
   The result is a precise numerical output (e.g., 55.4 minutes).

Backpropagation Learning Algorithm

Part (a) Overview of Backpropagation:

Backpropagation trains Multi-Layer Perceptrons (MLPs) by propagating the output error backward through the network to update the weights, minimizing the loss function over time.

1. Forward Pass: Inputs are multiplied by weights, passed through activation functions (e.g., Sigmoid), and generate a predicted output \(\hat{y}\).
2. Error Calculation: The Loss \(E\) is calculated. Using Sum of Squared Errors: \(E = \frac{1}{2} (\text{target} - \hat{y})^2\).
3. Backward Pass: Gradients of the loss with respect to every weight are computed using the Calculus Chain Rule.
4. Weight Update: Weights are adjusted against the gradient: \(w_{ij} = w_{ij} - \eta \frac{\partial E}{\partial w_{ij}}\).

Part (b) Derivation using Gradient Descent and Chain Rule:

Let's find the gradient for a weight \(w_{jk}\) connecting a hidden node \(j\) to an output node \(k\).

We need \(\frac{\partial E}{\partial w_{jk}}\). Using the Chain Rule, we expand this across the output node's operations:

• 1. Derivative of Error w.r.t output: \(\frac{\partial (\frac{1}{2}(t_k - \text{out}_k)^2)}{\partial \text{out}_k} = - (t_k - \text{out}_k)\)
• 2. Derivative of output w.r.t net sum (Sigmoid derivative): \(\frac{\partial \sigma(\text{net}_k)}{\partial \text{net}_k} = \text{out}_k (1 - \text{out}_k)\)
• 3. Derivative of net sum w.r.t weight: \(\frac{\partial (\sum w_{jk} \cdot \text{out}_j)}{\partial w_{jk}} = \text{out}_j\) (the input from the previous hidden node)

Multiplying these together yields the local gradient (often denoted as \(\delta_k\)):

The weight is updated as: \(w_{jk}^{\text{new}} = w_{jk}^{\text{old}} + \eta \cdot (t_k - \text{out}_k) \cdot \text{out}_k (1 - \text{out}_k) \cdot \text{out}_j\).

Genetic Algorithm Trace: Optimizing \(f(x) = x^2\)

Part (a) GA Execution Example:

Goal: Maximize \(f(x) = x^2\) for \(0 \le x \le 31\). We represent \(x\) as a 5-bit binary string (chromosome).

1. Initialization: Randomly generate 4 chromosomes.
   C1: 01101 (13) \(\implies f(13) = 169\)
   C2: 11000 (24) \(\implies f(24) = 576\)
   C3: 01000 (8) \(\implies f(8) = 64\)
   C4: 10011 (19) \(\implies f(19) = 361\)
2. Fitness Calculation & Roulette Wheel Selection:
   Total Fitness = \(169 + 576 + 64 + 361 = 1170\).
   Probabilities: \(P(C1)=14\%\), \(P(C2)=49\%\), \(P(C3)=5\%\), \(P(C4)=31\%\).
   Assume the Roulette wheel spins 4 times and selects: C2, C4, C2, C1 (fitter chromosomes are selected more often).
3. 1-Point Crossover:
   Pair 1: C2 (110|00) and C4 (100|11). Crossover point = 3.
   Offspring 1: 11011 (27) \(\implies f = 729\) (Improvement!)
   Offspring 2: 10000 (16) \(\implies f = 256\)
   Pair 2: C2 and C1...
4. Mutation: Randomly flip a bit with low probability (e.g., 0.01). Suppose Offspring 1 mutates at bit 1: 11011 \(\rightarrow\) 11111 (31) \(\implies f=961\).

Through successive generations, the population's average and maximum fitness will converge towards the global optimum (31 in this constrained example).

Q-Learning Manual Trace

Part (a) Environment Setup:

Assume a simple 3x3 grid. The agent starts at (1,1). The Goal is at (3,3) with reward +100. Pits at (2,2) with reward -100. Every regular move has a reward of -1. Discount factor \(\gamma = 0.9\). Learning Rate \(\alpha = 1.0\) (replaces old values entirely).

Part (b) Tracing an Episode:

• All \(Q(s, a)\) in the Q-table are initialized to 0.
• Step 1: Agent in (1,1). Moves Right to (2,1). Receives \(r = -1\). Next state is (2,1).
  \(Q((1,1), R) = -1 + 0.9 \times \max_a Q((2,1), a) = -1 + 0 = -1\).
• Step 2: Agent in (2,1). Moves Up to (2,2) [PIT!]. Receives \(r = -100\). Episode ends.
  \(Q((2,1), U) = -100 + 0 = -100\).
• Next Episode Step 1: Agent in (1,1). Chooses to move Right to (2,1). Receives \(r = -1\).
  \(Q((1,1), R) = -1 + 0.9 \times \max(Q((2,1), R)=0, Q((2,1), U)=-100, \dots)\).
  The max is 0 (moving right from 2,1). So \(Q((1,1), R)\) remains -1. However, the agent has learned to avoid moving Up from (2,1).

Over thousands of episodes, the +100 reward from (3,3) propagates backward through the grid, creating a gradient of Q-values that acts as an optimal policy path.

Converting FOL to Conjunctive Normal Form (CNF)

Let's trace the conversion of the sentence: "Everyone who loves all animals is loved by someone."

1. Initial FOL: \(\forall x (\forall y (\text{Animal}(y) \implies \text{Loves}(x, y)) \implies \exists z \text{Loves}(z, x))\)

2. Eliminate Implications (\(A \implies B \equiv \neg A \lor B\)):

\(\forall x (\neg (\forall y (\neg \text{Animal}(y) \lor \text{Loves}(x, y))) \lor \exists z \text{Loves}(z, x))\)

3. Move Negations Inwards (De Morgan's):

\(\forall x (\exists y (\neg (\neg \text{Animal}(y) \lor \text{Loves}(x, y))) \lor \exists z \text{Loves}(z, x))\)

\(\forall x (\exists y (\text{Animal}(y) \land \neg \text{Loves}(x, y)) \lor \exists z \text{Loves}(z, x))\)

4. Standardize Variables: All variables are already distinct (\(x, y, z\)).

5. Skolemize (Eliminate \(\exists\)): \(y\) and \(z\) are existentially quantified inside the scope of \(\forall x\), so they depend on \(x\). Replace them with Skolem functions \(F(x)\) and \(G(x)\).

\(\forall x ((\text{Animal}(F(x)) \land \neg \text{Loves}(x, F(x))) \lor \text{Loves}(G(x), x))\)

6. Drop Universal Quantifiers:

\((\text{Animal}(F(x)) \land \neg \text{Loves}(x, F(x))) \lor \text{Loves}(G(x), x)\)

7. Distribute \(\lor\) over \(\land\):

\((\text{Animal}(F(x)) \lor \text{Loves}(G(x), x)) \land (\neg \text{Loves}(x, F(x)) \lor \text{Loves}(G(x), x))\)

8. Separate Clauses:

• C1: \(\text{Animal}(F(x)) \lor \text{Loves}(G(x), x)\)
• C2: \(\neg \text{Loves}(x, F(x)) \lor \text{Loves}(G(x), x)\)

PEAS and Environment for a Medical Diagnosis Agent

Part (a) PEAS Description:

• Performance Measure: Accuracy of disease diagnosis, speed of diagnosis, minimizing false positives/negatives, reducing cost of unnecessary tests, improving patient survival rates.
• Environment: Patient (symptoms, vital signs), medical history database, hospital laboratory (test results), medical staff.
• Actuators: Screen display (prescribing treatments, outputting diagnosis, requesting further tests), automated email/pager to doctors.
• Sensors: Keyboard/voice input for symptoms, direct digital feeds from medical equipment (ECG, blood pressure monitor, MRI scanners).

Part (b) Environment Properties:

• Partially Observable: The agent cannot 'see' the internal state of the patient directly; it relies on tests and symptoms which may not reveal everything immediately.
• Stochastic: Diseases and treatments are probabilistic. Administering a drug does not guarantee a 100% specific outcome.
• Sequential: Current decisions (ordering a blood test) affect future percepts and decisions.
• Static: The patient's underlying condition doesn't usually change in the few seconds the agent takes to compute a diagnosis (though it can be dynamic in an ICU setting).
• Continuous: Time, blood pressure, and drug dosages are continuous variables.

Iterative Deepening DFS (IDDFS) vs BFS and DFS

Part (a) Comparison:

Part (b) IDDFS Trace:

IDDFS repeatedly executes Depth-Limited Search (DLS), increasing the depth limit each time.

• Iteration 1 (Limit = 0): Explores only the Root node. If Root != Goal, discard.
• Iteration 2 (Limit = 1): Explores Root, then all nodes at Depth 1 using DFS memory. Discard.
• Iteration 3 (Limit = 2): Explores Root, Depth 1, and Depth 2 nodes. Discard.

Why is it not terribly wasteful? Although IDDFS regenerates the top nodes multiple times, in a tree where branching factor \(b > 1\), the vast majority of nodes are at the bottom layer. The overhead of regenerating the top levels is mathematically negligible compared to the memory savings (e.g., for \(b=10\), 90% of nodes are at the deepest level being searched).

4-Queens Problem as a CSP with Backtracking

Part (a) CSP Formulation for 4-Queens:

• Variables: \(\{Q_1, Q_2, Q_3, Q_4\}\) representing columns 1 to 4.
• Domains: \(\{1, 2, 3, 4\}\) representing the row placement.
• Constraints: No two queens share a row (\(Q_i \neq Q_j\)) or a diagonal (\(|Q_i - Q_j| \neq |i - j|\)).

Part (b) Backtracking Trace:

1. Step 1: Assign \(Q_1 = 1\) (Queen 1 at Row 1). Valid.
2. Step 2: Try \(Q_2 = 1\) (Conflict Row). Try \(Q_2 = 2\) (Conflict Diag). Try \(Q_2 = 3\). Valid.
3. Step 3: Try \(Q_3 = 1, 2, 3, 4\). All conflict! (1: Row, 2: Diag with Q2, 3: Row, 4: Diag with Q2).
4. Step 4 (Backtrack!): Un-assign \(Q_3\). Go back to \(Q_2\). Try the next value for \(Q_2\), which is \(Q_2 = 4\). Valid.
5. Step 5: Try \(Q_3 = 1\) (Conflict Diag), \(Q_3 = 2\). Valid.
6. Step 6: Try \(Q_4 = 1, 2, 3, 4\). All conflict!
7. Step 7 (Backtrack!): Un-assign \(Q_4, Q_3, Q_2\). Go back to \(Q_1\). Try \(Q_1 = 2\).
8. Step 8: Continue forward: \(Q_1 = 2 \implies Q_2 = 4 \implies Q_3 = 1 \implies Q_4 = 3\). Solution found!

Semantic Networks and Frames Representation

Part (a) Scenario: "Tweety is a Canary. Canaries are birds. Birds have wings. Birds can fly. Sylvester is a Cat. Cats eat birds."

Part (b) Semantic Network Construction:

Part (c) Equivalent Frame Representation:

Frame: Bird
  IS-A: Animal
  Has-Part: Wings
  Ability: Fly
Frame: Canary
  IS-A: Bird
  Color: Yellow
Frame: Tweety
  IS-A: Canary
Frame: Cat
  IS-A: Mammal
  Diet: (Eats Bird)
Frame: Sylvester
  IS-A: Cat

Conceptual Dependency (CD) Structure

Part (a) The Sentence: "John gave Mary a book."

Part (b) Conceptual Dependency Analysis:

The verb "gave" implies a transfer of possession. Therefore, the core primitive ACT is ATRANS.

• ACT: ATRANS (Transfer of abstract relationship/possession)
• Actor: John (The entity performing the ATRANS)
• Object: Book (The entity being transferred)
• Recipient (To): Mary
• Donor (From): John

Graphical CD Representation:

John \(\Leftrightarrow\) ATRANS \(\leftarrow \text{O}\) Book \(\leftarrow \text{R}\) (To: Mary, From: John)

(Where \(\Leftrightarrow\) denotes the actor-action relation, \(\leftarrow \text{O}\) denotes the object relation, and \(\leftarrow \text{R}\) denotes the recipient-donor relation).

Inference generated: Because of ATRANS, the system can logically deduce that Mary now possesses the book, and John no longer possesses it, without needing explicit rules for the English word "gave".

Resolution Refutation: Clue (Colonel Mustard)

Part (a) Knowledge Base (Propositional Logic):

1. The murder was committed in the Library or the Conservatory: \(L \lor C\)
2. If the murder was in the Library, then Colonel Mustard did it: \(L \implies M\) \(\equiv\) \(\neg L \lor M\)
3. If the murder was in the Conservatory, then Miss Scarlet did it: \(C \implies S\) \(\equiv\) \(\neg C \lor S\)
4. Miss Scarlet is innocent (she didn't do it): \(\neg S\)

Goal to prove: Colonel Mustard did it (\(M\)).

Part (b) Resolution Proof:

• Step 1: Negate the goal and add to KB. Goal clause: \(\neg M\).
• Step 2: Resolve \((\neg C \lor S)\) with \(\neg S\).
  Result: \(\neg C\) (The murder was not in the Conservatory).
• Step 3: Resolve \((\neg L \lor M)\) with \(\neg M\).
  Result: \(\neg L\) (The murder was not in the Library).
• Step 4: Resolve \((L \lor C)\) with \(\neg C\).
  Result: \(L\) (The murder was in the Library).
• Step 5: Resolve \(L\) (from Step 4) with \(\neg L\) (from Step 3).
  Result: \(\emptyset\) (Contradiction!).

Because the negated goal led to a contradiction, the original goal (\(M\)) must be true. Colonel Mustard did it.

Bayes' Theorem: Medical Test Calculation

Part (a) Problem Statement:

A disease affects 1% of the population. A test for the disease is 99% accurate (True Positive Rate = 0.99, True Negative Rate = 0.99). If a person tests positive, what is the probability they actually have the disease?

Part (b) Application of Bayes' Theorem:

Let \(D\) = Patient has Disease, \(\neg D\) = Patient is Healthy.
Let \(+\) = Test is Positive, \(-\) = Test is Negative.

• Priors: \(P(D) = 0.01\), \(P(\neg D) = 0.99\)
• Likelihoods: \(P(+ | D) = 0.99\) (True Positive), \(P(+ | \neg D) = 0.01\) (False Positive)

We need to find \(P(D | +)\):

First, calculate total probability of a positive test, \(P(+)\):

Now, calculate posterior:

Conclusion: Despite a 99% accurate test, because the disease is so rare (Base Rate Fallacy), a person testing positive only has a 50% chance of actually having the disease. Half of all positive tests are false positives.

Block World and Sussman Anomaly

Part (a) Block World Formulation:

The Block World is a domain where a robotic arm can move uniform blocks on a table.

• Predicates: \(\text{ON}(A, B)\), \(\text{ON}(A, \text{Table})\), \(\text{CLEAR}(A)\), \(\text{HOLDING}(A)\), \(\text{ARMEMPTY}\).
• Actions (STRIPS):
  - Unstack(A, B): Pre: \(\text{ON}(A, B), \text{CLEAR}(A), \text{ARMEMPTY}\). Add: \(\text{HOLDING}(A), \text{CLEAR}(B)\). Delete: \(\text{ON}(A, B), \text{ARMEMPTY}\).
  - Stack(A, B): Pre: \(\text{HOLDING}(A), \text{CLEAR}(B)\). Add: \(\text{ON}(A, B), \text{ARMEMPTY}\). Delete: \(\text{HOLDING}(A), \text{CLEAR}(B)\).

Part (b) Sussman Anomaly in Goal Stack Planning:

Suppose Initial State: \(C\) is on \(A\). \(A\) and \(B\) are on the Table. Goal State: \(A\) on \(B\), and \(B\) on \(C\) (\(\text{ON}(A, B) \land \text{ON}(B, C)\)).

• Goal Stack Planning attempts to solve sub-goals linearly.
• If it tries to achieve \(\text{ON}(A, B)\) first: It clears \(A\) by unstacking \(C\) and putting it on the table. Then it puts \(A\) on \(B\). Now it tries to achieve \(\text{ON}(B, C)\). But to move \(B\), it must unstack \(A\) again! It destroyed its previous progress.
• If it tries to achieve \(\text{ON}(B, C)\) first: It places \(B\) on \(C\). Then it tries to achieve \(\text{ON}(A, B)\). But \(A\) is trapped under \(C\) (which is under \(B\)). It must undo everything.

Resolution: Non-linear planning (like Plan-Space Planning) is required to interleave the steps: Clear \(A\) (put \(C\) on table), then put \(B\) on \(C\), then put \(A\) on \(B\).

Minimax Algorithm for Tic-Tac-Toe

Part (a) Game Representation:

Tic-Tac-Toe is a 2-player zero-sum game. Player X (MAX) aims for +1, Player O (MIN) aims for -1. A draw is 0. The state space contains \(3^9\) possible board configurations, but the actual reachable states are far fewer.

Part (b) Minimax Execution:

• Tree Generation: From an empty board, MAX (X) can place a mark in 9 positions (9 branches). For each branch, MIN (O) has 8 responses. This creates the game tree.
• Leaf Evaluation: The algorithm recursively reaches the end of the game (win, lose, or draw) and assigns a utility score (+1 for X win, -1 for O win, 0 for draw).
• Value Back-propagation:
  - If it is O's turn (MIN node), it looks at all its child board states and selects the minimum score (aiming for -1).
  - If it is X's turn (MAX node), it looks at its children and selects the maximum score (aiming for +1).
• Because Tic-Tac-Toe is perfectly solvable and has a small state space, Minimax can search the entire tree to depth 9. It proves mathematically that optimal play by both sides always results in a Draw (0).

Components of a Natural Language Processing (NLP) System

An NLP system requires several interacting components to map raw text to machine-understandable representations.

1. Lexicon (Dictionary): A database of words, their base forms (lemmas), syntactic categories (Noun, Verb), and semantic meanings.
2. Morphological Analyzer / Tokenizer: Splits text into sentences and words. It uses stemming/lemmatization to reduce words to their root (e.g., "running" \(\rightarrow\) "run").
3. Parser (Syntactic Analyzer): Uses grammar rules (like Context-Free Grammars) to validate sentence structure. Outputs a Parse Tree showing Subject, Verb, Object relationships.
4. Semantic Interpreter: Maps the parse tree to a logical meaning representation (e.g., First-Order Logic or Conceptual Dependency graphs). It handles word sense disambiguation (e.g., "bank" of a river vs financial "bank").
5. Context & Pragmatic Manager: Resolves pronouns across sentences (anaphora resolution) and infers intent based on real-world knowledge (e.g., recognizing that "Can you pass the salt?" is a request, not a yes/no question).
6. Natural Language Generator (NLG): The reverse pipeline. Takes a logical machine concept and translates it back into grammatically correct human text.

Forward vs Backward Chaining Trace

Part (a) Knowledge Base (KB):

R1: IF \(A \land B\) THEN \(C\)
R2: IF \(C\) THEN \(D\)
R3: IF \(A \land E\) THEN \(F\)
Facts: \(A\), \(B\).

Part (b) Forward Chaining (Data-Driven):

Goal: Find all conclusions.

1. Iteration 1: Known facts \(\{A, B\}\). Check rules. R1 condition (\(A \land B\)) is satisfied. Fire R1. Add \(C\) to known facts.
2. Iteration 2: Known facts \(\{A, B, C\}\). R2 condition (\(C\)) is satisfied. Fire R2. Add \(D\) to known facts.
3. Iteration 3: Known facts \(\{A, B, C, D\}\). No more rules can fire (R3 needs \(E\), which is missing). Terminate.

Part (c) Backward Chaining (Goal-Driven):

Goal: Prove \(D\) is true.

1. Check if \(D\) is a known fact. (No).
2. Find a rule that concludes \(D\). R2: IF \(C\) THEN \(D\). New sub-goal: Prove \(C\).
3. Check if \(C\) is a known fact. (No).
4. Find a rule that concludes \(C\). R1: IF \(A \land B\) THEN \(C\). New sub-goals: Prove \(A\), Prove \(B\).
5. Check \(A\). It is a known fact (True). Check \(B\). It is a known fact (True).
6. Since sub-goals \(A\) and \(B\) are true, \(C\) is true. Since \(C\) is true, \(D\) is true. Proof succeeds!

Propositional Logic and Truth Tables

Part (a) Converting English to Logic:

Sentence: "If it rains, the grass is wet. It is raining. Therefore, the grass is wet."

• Let \(R\) = "It rains"
• Let \(W\) = "The grass is wet"
• Premise 1: \(R \implies W\)
• Premise 2: \(R\)
• Conclusion (Theorem): \(W\)

We want to prove that the conclusion logically follows from the premises. This means the implication \(((R \implies W) \land R) \implies W\) must be a Tautology (True in all cases).

Part (b) Truth Table Proof:

Because the final column is entirely True, the argument is logically valid (This specific argument form is known as Modus Ponens).

Artificial Neural Networks (ANN): Architectures

An ANN is a biologically inspired computational model consisting of interconnected artificial neurons organized in layers: an Input layer, one or more Hidden layers, and an Output layer.

1. Feedforward Neural Networks (FNN)

• Architecture: Data strictly flows in one direction—from the input layer, through the hidden layers, directly to the output layer. There are no cycles or loops.
• Memory: They have no internal state or memory. The output for a given input is always the same, regardless of the sequence of previous inputs.
• Use Cases: Image classification, regression tasks, tabular data (e.g., standard Multi-Layer Perceptrons or Convolutional Neural Networks).

2. Recurrent Neural Networks (RNN)

• Architecture: RNNs contain directed cycles. The output of a neuron is fed back into itself or previous layers. This recurrent connection allows information to persist.
• Memory: RNNs maintain a "hidden state" that acts as internal memory, allowing them to process sequences of inputs where temporal context matters.
• Use Cases: Time-series forecasting, Natural Language Processing, Speech recognition (where the current word depends heavily on the previous words). Advanced variants include LSTMs and GRUs to handle long-term dependencies.

Support Vector Machines (SVM)

Support Vector Machine (SVM) is a powerful supervised machine learning algorithm used primarily for classification. Its fundamental objective is to find a line (or hyperplane in higher dimensions) that perfectly separates data points of different classes.

The Hyperplane and Margin

• In a 2D space, the separator is a line. In 3D, it's a plane. In N-D, it's an \((N-1)\)-dimensional Hyperplane.
• There could be infinite lines that separate two clusters of data. SVM doesn't just pick any line; it picks the Optimal Separating Hyperplane.
• Margin Maximization: The optimal hyperplane is the one that has the maximum distance (margin) from the nearest data points of both classes. A larger margin implies better generalization to unseen data.

Support Vectors

The Support Vectors are the specific, critical data points that lie closest to the hyperplane (exactly on the edges of the margin). These points "support" the construction of the hyperplane. If you remove all other data points in the dataset, the position of the hyperplane would not change. The algorithm is highly memory efficient because it only depends on these few support vectors.

Note: If data is not linearly separable, SVM uses the 'Kernel Trick' to map data into a higher-dimensional space where a linear hyperplane can separate them.

Hidden Markov Models (HMM) in AI

A Hidden Markov Model (HMM) is a statistical Markov model where the system being modeled is assumed to be a Markov process with unobserved (hidden) states. It is widely used for sequential data.

Core Components

• Hidden States (\(S\)): The underlying reality we want to discover, but cannot directly observe (e.g., the actual phonemes or words being spoken).
• Observations (\(O\)): The tangible data we can measure (e.g., the acoustic sound waves captured by a microphone).
• Transition Probabilities (\(A\)): The probability of moving from one hidden state to another (e.g., probability that the phoneme /b/ is followed by the phoneme /a/).
• Emission Probabilities (\(B\)): The probability of generating a specific observation given a specific hidden state (e.g., probability that the acoustic wave looks like this when the person is saying the phoneme /b/).

Use in Speech Recognition

In speech recognition, the system receives a sequence of acoustic observations. It uses the Viterbi Algorithm (a dynamic programming algorithm) applied to the HMM to calculate the most probable sequence of hidden states (words) that could have generated those observed sounds.

Unsupervised Learning: K-Means Clustering

Unsupervised Learning deals with unlabeled data. The algorithm must find hidden structure or patterns within the data on its own. The most common technique is clustering.

K-Means Algorithm

K-Means partitions \(N\) observations into \(K\) distinct, non-overlapping clusters. It minimizes the variance (squared distance) between data points and their cluster's center.

The Algorithm Steps:

1. Initialization: The user specifies \(K\) (the number of clusters). The algorithm randomly selects \(K\) data points to act as the initial cluster centers (centroids).
2. Assignment Step: Calculate the Euclidean distance from every data point to all \(K\) centroids. Assign each data point to the cluster of the centroid it is closest to.
3. Update Step: Recalculate the position of each centroid. The new centroid is the mathematical mean (average) of all the data points currently assigned to that cluster.
4. Convergence: Repeat steps 2 and 3 iteratively until the centroids stop moving (or movement is below a tolerance threshold), meaning the assignments are stable.

Drawback: It requires the user to guess the optimal \(K\) beforehand, and is sensitive to the initial random placement of centroids.

Expert Systems and MYCIN

Part (a) Expert System Architecture Recap:

Expert systems consist of a Knowledge Base (facts and heuristics extracted from experts), an Inference Engine (the logic processor using forward/backward chaining), and a User Interface.

Part (b) Case Study: MYCIN (1970s)

MYCIN was one of the earliest and most famous expert systems, developed at Stanford University to diagnose severe bacterial infections (like meningitis) and recommend antibiotic dosages.

• Knowledge Base: Contained around 600 IF-THEN rules representing the heuristic knowledge of expert physicians. (e.g., IF the infection is primary-bacteremia AND the site of culture is a sterile record THEN there is evidence that the organism is bacteroides).
• Inference Engine: Used Backward Chaining. It started with a hypothesis (the patient has a specific infection) and worked backward, asking the doctor via a text interface for lab results to prove the hypothesis.
• Certainty Factors: MYCIN pioneered the use of "Certainty Factors" (CF) ranging from -1.0 (definitely false) to +1.0 (definitely true) to handle the inherent uncertainty of medical diagnoses, long before Bayesian networks became standard.
• Performance: Studies showed MYCIN outperformed junior doctors and was on par with infectious disease experts, though it was never fully deployed in hospitals due to legal and ethical liability issues of the era.