Artificial Intelligence

\(p \to q\) is false only when \(p\) is true and \(q\) is false, and \(\neg p \vee q\) is false in exactly the same case, so \(S_{1} \equiv S_{3}\).

Every other pair differs on at least one row of the truth table:

• \(S_{2}\) and \(S_{3}\): with \(p\) and \(q\) both true, \(S_{2}\) is false but \(S_{3}\) is true.
• \(S_{2}\) and \(S_{4}\): with both false, \(S_{2}\) is false but \(S_{4}\) is true.
• \(S_{1}\) and \(S_{4}\): with both true, \(S_{1}\) is true but \(S_{4}\) is false.

Answer: A

• Variable elimination is an exact method. It multiplies the relevant conditional probability tables and sums out the hidden variables one at a time, so A is false.
• What it returns is a conditional probability such as \(P(Q \mid e)\) for a query \(Q\) given evidence \(e\), so C is true.
• Gibbs sampling and rejection sampling both estimate probabilities from random samples. Their answers are approximate and improve as more samples are drawn, so B is false and D is true.

Answer: C, D

Alpha-beta pruning skips the remaining children of a MIN node once its value \(\beta\) can no longer beat the value \(\alpha\) that MAX is already sure of, that is, once \(\beta \le \alpha\).

• Tree-1: after the leaf 2, MAX at A has \(\alpha = 2\). At B, the leaf \(x\) gives \(\beta = x\). The leaf 1 is pruned when \(x \le 2\), because B is then worth at most 2 and cannot raise A above 2. So \(x \in (-\infty, 2]\).
• Tree-2: D is searched fully, so \(\alpha = \min(5, y)\) at C. At E, the leaf 2 gives \(\beta = 2\), and the triangle is pruned when \(2 \le \min(5, y)\), i.e. \(y \ge 2\). So \(y \in [2, \infty)\).

Only option C has both ranges.

Answer: C

A* always expands the frontier node with the smallest \(f = g + h\), where \(g\) is the path cost from S.

• Expand S: frontier A (\(4 + 2 = 6\)) and E (\(1 + 6 = 7\)).
• Expand A (6): add B (\(6 + 2 = 8\)).
• Expand E (7): add C (\(3 + 6 = 9\)).
• Expand B (8): reaching C through B costs 8, worse than 3, so C keeps \(f = 9\).
• Expand C (9): add D (\(6 + 2 = 8\)).
• Expand D (8): add G (\(9 + 0 = 9\)), and finally expand G.

The order is S, A, E, B, C, D, G. Option A expands C (9) before B (8), and ordering by \(h\) alone would put B before E, as in option D.

Answer: C

A heuristic is admissible when \(0 \leq h(n) \leq h^{*}(n)\) for every node \(n\), where \(h^{*}(n)\) is the true cost of reaching the goal. Because both values are non-negative,

\[|h_{1}(n) - h_{2}(n)| \leq \max(h_{1}(n), h_{2}(n)) \leq h^{*}(n),\]

so option D never overestimates.

The other expressions can overestimate. With \(h^{*}(n) = 5\) and \(h_{1}(n) = h_{2}(n) = 5\), both admissible, the sum is 10 and the product is 25. With \(h_{1}(n) = 5\) and \(h_{2}(n) = 0.1\), the ratio is 50.

Answer: D

The factorisation is the Bayesian network \(U \rightarrow W \leftarrow V\), \(W \rightarrow X\), \(W \rightarrow Y\).

• A and B: \(U\) and \(V\) reach \(X\) and \(Y\) only through chains such as \(V \rightarrow W \rightarrow Y\), and observing \(W\) blocks a chain. Both are true.
• D: \(X \leftarrow W \rightarrow Y\) has \(W\) as a common cause, so \(X\) and \(Y\) are independent once \(W\) is known. True.
• C: \(U\) and \(V\) are independent on their own (the factor \(P(U)P(V)\)), but \(W\) is their common effect. Observing a common effect couples its causes (explaining away): once \(W\) is known, learning \(U\) changes what \(V\) is likely to be. So C does not hold in general.

Answer: C

Alpha–beta pruning carries two bounds down the game tree:

• \(\alpha\) is the value MAX can already guarantee along the path. MAX wants large values, so \(\alpha\) is the highest value found so far.
• \(\beta\) is the value MIN can already guarantee. MIN wants small values, so \(\beta\) is the lowest value found so far.

A branch is pruned as soon as \(\alpha \geq \beta\), because the player choosing above it already has a better alternative and would never let play reach it. The other options give MAX, MIN or both the preference of the opponent, so the bounds would no longer be values that player can guarantee.

Answer: C

An implication is false only when its premise is true and its conclusion is false. Each premise here is true in exactly one row of the truth table, so check the conclusion in that row.

• A: \(\neg x \land y\) needs \(x\) false and \(y\) true. Then \(y \Longrightarrow x\) is true \(\Longrightarrow\) false, which is false. Not a tautology.
• B: \(x \land \neg y\) needs \(x\) true and \(y\) false. Then \(\neg x\) is false, so \(\neg x \Longrightarrow y\) is true. Tautology.
• C: \(x\) false and \(y\) true make \(\neg x \Longrightarrow y\) true \(\Longrightarrow\) true, which is true. Tautology.
• D: \(x\) true and \(y\) false make \(y \Longrightarrow x\) false \(\Longrightarrow\) true, which is true. Tautology.

Answer: B, C, D

Successors come out as \(n+1\) and then \(n+2\), and the smaller number always goes first.

• BFS: expanding 1 queues 2 and 3; expanding 2 adds 4 (3 is already waiting); expanding 3 adds 5; expanding 4 adds 6; expanding 5 adds 7. Then 6 leaves the queue. Expanded: 1, 2, 3, 4, 5.
• DFS: it always dives into the smaller child \(n+1\), so it expands 1, 2, 3, 4, 5 and then reaches 6.

Both searches expand the same five states before reaching the goal (or four each if the goal is tested when it is generated, since both then stop while expanding 4). State 6 is reachable, so option D is false.

Answer: C

The assertion says two things about every ball: a ball not used in rugby is round, and a ball used in rugby is not round.

• s1 states the first part, and s2 is its contrapositive (a ball that is not round is used in rugby), so s1 and s2 say the same thing.
• s3 states the second part, and s4 is its contrapositive, so s3 and s4 say the same thing.

A correct representation needs one sentence from each pair, so \(s1 \wedge s3\) (A) and \(s2 \wedge s3\) (C) both work. Option B repeats the first part and would still allow a round rugby ball; option D repeats the second part and would allow a non-rugby ball that is not round.

Answer: A, C