COMPSCI 713 — AI Fundamentals: Exam Preparation

University of Auckland | Semester 1, 2026 | Instructor: Xinyu Zhang

About This Book

This knowledge base is built to help you learn and prepare for the COMPSCI 713 in-course test (Week 7, 60 minutes, 20 marks).

Every concept is explained using the Feynman method: first in plain language with analogies, then formally with math, then applied to real exam questions. The goal is not just memorisation — it’s understanding.

How to Use This Book

1. Start with Part 0 — read the exam analysis to understand what’s tested and with what weight
2. Work through modules in priority order — 🔴 modules first (A, B, G, F), then 🟠 (D, H), then 🟡 (C, E)
3. For each chapter: read the Feynman Draft first to build intuition, then study the formal definitions, then try the practice problems
4. Use the English Expression Guide before the test — practise the sentence templates
5. Attempt all 3 mock exams under timed conditions (55 min answering)
6. Check your cheat sheet — the frequency map chapter has recommendations for what to write on your handwritten A4 page

Exam Format (Sample Test S1 2026)

Coverage Map (Weeks 2-5)

Priority Legend

• 🔴 必考 (Must-Know): Appeared in sample test with high mark weight
• 🟠 高频 (High Frequency): Appeared in sample test with moderate weight
• 🟡 中频 (Medium): Full lecture topic, not in sample but likely in actual test

真题逐题分析 — Complete Exam Analysis

Course: COMPSCI 713: AI Fundamentals, University of Auckland Instructor: Xinyu Zhang (mid-semester) / Thomas (final exam, partial) Scope: ALL available exam papers — S1 2025 Sample, S1 2025 Actual, S1 2026 Sample, S1 2024 Final Purpose: Question-by-question breakdown for exam preparation

How to Use This Document（使用指南）

1. First pass: Skim the tables at the end of each exam section to see topic/mark distribution
2. Second pass: Read the Learning Points for your weakest topics
3. Third pass: Use the Common Mistakes as a self-check before the exam
4. Final review: Jump to Cross-Exam Patterns at the bottom

💡 核心发现: 每一份试卷都考了 Symbolic Logic, LNN, Knowledge Graphs, 和 Decision Trees/Ensembles。这四个是绝对必考项。

Exam Paper 1: S1 2025 Sample Test

Format: 15 marks, 6 questions, 60 minutes (5 reading + 55 answering) Allowed aids: One double-sided handwritten A4 page

Q1 — Symbolic Logic [3 marks]

Question Summary

(a) Propositional Logic — Modus Tollens [~1.5m]

Scenario: A secure facility grants entry only if a person has a valid ID ($I$) AND fingerprint matches ($F$). Rule: $(I \wedge F) \rightarrow E$. Observed: person was NOT granted entry ($\neg E$).

Task: Deduce what must be true about $I$ and $F$.

(b) First-Order Logic [~1.5m]

Task: Write “Not all birds can fly” in FOL using $\text{Fly}(x)$. Give a realistic example.

Expected Answer

(a):

• By Modus Tollens: $(I \wedge F) \rightarrow E$ and $\neg E$ implies $\neg(I \wedge F)$
• By De Morgan: $\neg I \vee \neg F$
• Conclusion: Either the person lacked a valid ID, or the fingerprint didn’t match (or both)

(b):

• FOL: $\neg \forall x , \text{Fly}(x)$, equivalently $\exists x , \neg \text{Fly}(x)$
• Example: “Penguins are birds but cannot fly”

Analysis

Learning Points（学习要点）

• Modus Tollens 是本课程考试的第一推理模式: $(P \rightarrow Q), \neg Q \vdash \neg P$。务必熟练到条件反射
• “Not all” = $\neg \forall x$: 注意不是 $\forall x , \neg$（后者意为“所有都不“，语义完全不同）
• De Morgan 定律: $\neg(A \wedge B) = \neg A \vee \neg B$，推导结论时经常用到

⚠️ Common Mistake: Writing $\forall x , \neg \text{Fly}(x)$ which means “NO bird can fly” — much stronger than “not all birds can fly.”

Q2 — Logic Neural Networks (LNN) [2 marks]

Question Summary

Scenario: Smart home LNN rule: HeatingOn $\leftarrow$ Cold $\otimes$ AtHome (differentiable AND).

(a) Interpret in natural language. How does it differ from Boolean? [1m]

(b) Compute with Cold = 0.9, AtHome = 0.4. Discuss whether heating activates. [1m]

Expected Answer

(a):

• Natural language: “If it is cold AND someone is at home, turn on the heating.”
• Difference: Boolean AND requires both inputs strictly TRUE (1). LNN’s $\otimes$ works with continuous truth values in $[0, 1]$, producing intermediate results that capture partial truth and enable gradient-based learning.

(b):

• Product t-norm: $0.9 \times 0.4 = 0.36$
• Lukasiewicz: $\max(0, 0.9 + 0.4 - 1) = 0.3$
• Whether heating activates depends on threshold: if $\alpha = 0.3$, yes; if $\alpha = 0.7$, no.

Analysis

Learning Points

• 必背三个 t-norm:
  • Product: $a \times b$
  • Lukasiewicz: $\max(0, a + b - 1)$
  • Godel/min: $\min(a, b)$
• Boolean vs LNN 的关键差异: Boolean 是离散的 {0,1}；LNN 是连续的 [0,1]，支持梯度下降

⚠️ Common Mistake: Forgetting to discuss the threshold. Computing 0.36 is not enough — you must state what activation decision follows.

Q3 — Knowledge Graph Embeddings [2 marks]

Question Summary

Explain the role of entity/relation embeddings in KG completion. Introduce a common KG inference task with an example.

Expected Answer

• Embeddings: Map entities and relations to dense vectors in continuous space, enabling mathematical operations for reasoning
• Inference task: Link prediction — given $(h, r, ?)$, predict tail entity
• Example: $(Einstein, bornIn, ?) \rightarrow Germany$

Analysis

Learning Points

• TransE 核心公式: $h + r \approx t$（头实体向量 + 关系向量 ≈ 尾实体向量）
• 三种推理任务: tail prediction $(h, r, ?)$, head prediction $(?, r, t)$, relation prediction $(h, ?, t)$

⚠️ Common Mistake: Confusing “embedding” with “one-hot encoding.” Embeddings are dense, low-dimensional, learned vectors — not sparse indicator vectors.

Exam tip（答题技巧）: 永远给具体例子。“(Einstein, bornIn, ?) → Germany” 远比 “it predicts missing links” 好。

Q4 — Embodied AI / Robot Soccer [2 marks]

Question Summary

Robot soccer league: overhead camera, 225 features per frame, team of 5 robots, no inter-robot communication. Describe strategies/collective behaviours.

Expected Answer

Any of (1 mark each, max 2):

• Collective behaviours: passing strategy, interception prediction, passing point value assessment
• Positioning strategies: formations for attack/defense
• Role-based strategies: dynamic role assignment based on game situation
• Centralized control: overhead camera acts as single controller for all 5 robots

Analysis

Learning Points

• 三大策略类别: (1) 集体行为 — passing, (2) 位置策略 — formation, (3) 角色分配 — dynamic assignment
• 关键细节: No communication → centralized control via overhead camera → single decision-maker

⚠️ Common Mistake: Being too vague. “They work together” = 0 marks. Name specific strategies.

Q5 — Random Forest / Bagging [3 marks]

Question Summary

Dataset with 225 features.

(a) How are features selected per tree? How many? [2m]

(b) Why is feature bagging a good idea? [1m]

Expected Answer

(a):

• Random subset of features sampled per tree (not all 225)
• Typical: $\sqrt{p} = \sqrt{225} = 15$ features per tree
• Different trees see different feature subsets

(b):

• Prevents trees from being highly correlated (e.g., same dominant feature always at root)
• Decorrelated trees → ensemble averaging reduces variance more effectively

Analysis

Learning Points

• $\sqrt{p}$ rule: For $p$ features, sample $\sqrt{p}$ per tree. For 225 features → 15.
• Bagging vs Boosting:
  • Bagging → parallel trees → reduces variance
  • Boosting → sequential trees → reduces bias
• 两层随机化: (1) Bootstrap sampling of data rows, (2) Random sampling of features. Both reduce correlation.

⚠️ Common Mistake: Confusing bootstrap sampling (random data points) with feature bagging (random features). Both happen in Random Forest; they serve different purposes.

Q6 — MYCIN / Expert Systems [3 marks]

Question Summary

Medical diagnosis scenario using backward chaining. Patient has a runny nose. Possible diagnoses: common cold, allergies, measles. Demonstrate backward chaining reasoning.

Expected Answer

• Backward chaining: Start from hypothesis, work backward to check conditions
  1. Hypothesis: Common Cold → needs runny nose ✓, fever ?, cough ?
  2. Hypothesis: Allergies → needs runny nose ✓, sneezing ?, itchy eyes ?
  3. Hypothesis: Measles → needs runny nose ✓, rash ?, high fever ?
• Ask additional questions to discriminate between hypotheses
• Contrast with forward chaining: start from facts, derive conclusions

Analysis

Learning Points

• Backward chaining 三步法: (1) Start with hypothesis, (2) Check conditions, (3) Ask for missing info
• Forward vs Backward: Forward = data-driven (fact → conclusion); Backward = goal-driven (hypothesis → verify)
• MYCIN 特色: Uses certainty factors (CF) instead of probabilities; backward chaining for diagnosis

⚠️ Common Mistake: Describing forward chaining when asked for backward chaining. Direction matters!

S1 2025 Sample Test — Summary Table

Exam Paper 2: S1 2025 Actual Test

Format: 15 marks, 6 questions, 60 minutes This is the REAL exam that was sat

Q1 — Symbolic Logic [2 marks]

Question Summary

(a) Given $(P \vee Q) \rightarrow R$ and $\neg R$. Apply Modus Tollens. [1m]

(b) Given $\forall x(\text{Cheat}(x) \rightarrow \text{Disqualified}(x))$ and Alice is not disqualified. Conclude about Alice. [1m]

Expected Answer

(a):

• Modus Tollens: $(P \vee Q) \rightarrow R$ and $\neg R$ implies $\neg(P \vee Q)$
• By De Morgan: $\neg P \wedge \neg Q$
• Both P and Q must be false

(b):

• Universal instantiation: $\text{Cheat}(\text{Alice}) \rightarrow \text{Disqualified}(\text{Alice})$
• Given $\neg \text{Disqualified}(\text{Alice})$, by Modus Tollens: $\neg \text{Cheat}(\text{Alice})$
• Conclusion: Alice did not cheat

Analysis

Learning Points

• 这道题和 Sample 的区别: Sample 用 $(I \wedge F) \rightarrow E$，Actual 用 $(P \vee Q) \rightarrow R$。结论不同！
  • $\neg(A \wedge B) = \neg A \vee \neg B$（至少一个为假）
  • $\neg(A \vee B) = \neg A \wedge \neg B$（两个都假）
• FOL + Modus Tollens 组合拳: Universal instantiation 先把 $\forall x$ 具体化为 Alice，再用 Modus Tollens

⚠️ Common Mistake: For $\neg(P \vee Q)$, some students write “$P$ or $Q$ is false” — this is WRONG. BOTH must be false. De Morgan on disjunction gives conjunction of negations.

🔑 关键对比: AND 的否定 → 至少一个假 (disjunction); OR 的否定 → 全部假 (conjunction). 这是必须刻在脑子里的。

Q2 — LNN with Truth Bounds [3 marks]

Question Summary

Scenario: Autonomous vehicle collision alert system. Two sensors:

• Pedestrian detector: $P$ with bounds $[L_P, U_P] = [0.8, 0.9]$
• Obstacle detector: $Q$ with bounds $[L_Q, U_Q] = [0.3, 0.6]$

Rule: Alert $\leftarrow P \vee Q$ (disjunction, not conjunction!)

Alert threshold: $\alpha = 0.7$

(a) Determine alert status [2m]

(b) Why are bounds (instead of point estimates) useful in safety-critical applications? [1m]

Expected Answer

(a):

• Co-norm for OR (using Lukasiewicz):

  • Lower bound: $\min(1, L_P + L_Q) = \min(1, 0.8 + 0.3) = 1.0$
  • Upper bound: $\min(1, U_P + U_Q) = \min(1, 0.9 + 0.6) = 1.0$

• OR result bounds: $[1.0, 1.0]$

• Since lower bound $1.0 \geq \alpha = 0.7$: Alert ACTIVATES

  Alternative (product-based co-norm):

  • $P \vee Q = P + Q - P \cdot Q$
  • Lower: $0.8 + 0.3 - 0.8 \times 0.3 = 0.86$
  • Upper: $0.9 + 0.6 - 0.9 \times 0.6 = 0.96$
  • Bounds: $[0.86, 0.96]$, both $\geq 0.7$: Alert ACTIVATES

(b):

• Bounds capture epistemic uncertainty — we know the truth value lies somewhere in the interval
• In safety-critical systems, we can make conservative decisions: if even the lower bound exceeds threshold, we act
• Point estimates hide uncertainty; bounds let us reason about worst-case scenarios

Analysis

Learning Points

• 这是 LNN 的升级版考法: Sample 考 AND 的点值计算，Actual 考 OR 的区间计算
• AND vs OR t-norm/co-norm:
  • AND (t-norm): Product → $a \times b$; Lukasiewicz → $\max(0, a + b - 1)$
  • OR (co-norm): Product → $a + b - a \times b$; Lukasiewicz → $\min(1, a + b)$
• Safety-critical reasoning: 用 lower bound 做决策 = 最保守策略

⚠️ Common Mistake: Using AND formula when the question says OR! Read the operator carefully: $\otimes$ = AND, $\oplus$ = OR, $\vee$ = OR.

⚠️ 另一个常见错误: 忘记 bounds 是区间运算。不能只算一个值，要算 [lower, upper]。

Q3 — Knowledge Graphs / TransE [2 marks]

Question Summary

(a) Explain the TransE embedding model [1m]

(b) Write the TransE scoring function [1m]

Expected Answer

(a):

• TransE represents entities and relations as vectors in the same space
• Core idea: for a true triple $(h, r, t)$, the head plus relation should approximate the tail: $h + r \approx t$

(b):

• Scoring function: $f(h, r, t) = |h + r - t|$ (L1 or L2 norm)
• Lower score = more likely to be true
• Training: minimize score for true triples, maximize for false (negative sampling)

Analysis

Learning Points

• TransE 必背: $f(h,r,t) = |h + r - t|$，越小越可能是真三元组
• 与 Sample 的区别: Sample 考概念层面（什么是 embedding），Actual 考公式层面（TransE 具体怎么算）
• 局限性: TransE 无法建模 1-to-N 关系（如一个国家有多个城市）

⚠️ Common Mistake: Writing $h + r = t$ (equality) instead of $h + r \approx t$ (approximation). The model learns to minimize the distance, not enforce exact equality.

Q4 — Decision Trees / CART [2 marks]

Question Summary

What does “greedy” mean in the context of CART (Classification and Regression Trees)?

Expected Answer

• Greedy = at each node, CART picks the locally optimal split (maximum information gain or minimum Gini impurity) without considering future splits
• It does not evaluate all possible tree structures to find the global optimum
• This makes it computationally efficient but potentially suboptimal
• Why greedy? Finding the optimal tree is NP-hard

Analysis

Learning Points

• “Greedy“三要素: (1) 每步选当前最优 (2) 不回溯 (3) 不保证全局最优
• 为什么接受 greedy?: 找最优树是 NP-hard；greedy 在实践中效果够好
• Ensemble 弥补 greedy: Random Forest 通过多棵 greedy tree 的聚合来逼近更好的解

⚠️ Common Mistake: Saying greedy means “fast.” Greedy is about the optimization strategy (local vs global), not speed.

Q5 — Fuzzy Logic [3 marks]

Question Summary

Contrast traditional (Boolean) logic vs fuzzy logic for the rule: IF athlete is STRONG AND athlete is HEAVY THEN athlete is HAMMER_THROWER

Expected Answer

Traditional Logic:

• STRONG = {yes, no}, HEAVY = {yes, no} → HAMMER_THROWER = {yes, no}
• Sharp boundaries: an athlete is either strong or not
• AND = Boolean AND: both must be true for conclusion to hold

Fuzzy Logic:

• STRONG(x) ∈ [0, 1], HEAVY(x) ∈ [0, 1] → HAMMER_THROWER(x) ∈ [0, 1]
• Gradual membership: “somewhat strong” = 0.6, “very heavy” = 0.9
• AND = t-norm (e.g., min): HAMMER_THROWER ≥ min(0.6, 0.9) = 0.6
• Captures vagueness — no sharp cutoff between “strong” and “not strong”

Analysis

Learning Points

• 对比答题模板: 分三行写 — (1) Traditional: binary, (2) Fuzzy: continuous, (3) WHY fuzzy is better for this case
• Fuzzy logic 解决 vagueness: “Strong” 没有明确边界 → 需要 membership function
• 给具体数字: 说 “STRONG(athlete) = 0.6” 比抽象描述好得多

⚠️ Common Mistake: Confusing fuzzy logic with probability. Fuzzy = degree of membership (to what extent is this athlete “strong”?). Probability = likelihood of an event (what’s the chance this athlete wins?).

Q6 — GA / Embodied AI [3 marks]

Question Summary

Design a fitness function for a BigDog walking robot using Genetic Algorithm optimization.

Expected Answer

Fitness function components:

1. Distance traveled (primary): $f_1 = d / d_{max}$ — further is better
2. Stability (constraint): $f_2 = 1 - \text{angular_deviation} / \text{max_deviation}$ — less wobble is better
3. Energy efficiency (secondary): $f_3 = 1 - E_{used} / E_{max}$ — less energy is better
4. Penalty: $f_{penalty} = -C$ if robot falls

Combined: $F = w_1 f_1 + w_2 f_2 + w_3 f_3 + f_{penalty}$

Key design considerations:

• Must balance multiple objectives
• Weights reflect priority (distance > stability > efficiency typically)
• Penalties for catastrophic failure (falling) should be large

Analysis

Learning Points

• Fitness function 设计万能框架: (1) 定义主目标, (2) 加约束, (3) 加惩罚项, (4) 用加权求和合并
• 开放题没有唯一答案: 关键是逻辑自洽 + 覆盖关键方面
• 必须提到权衡: 速度 vs 稳定性 vs 能耗

⚠️ Common Mistake: Only considering one objective (e.g., just distance). Real fitness functions must balance multiple competing goals.

S1 2025 Actual Test — Summary Table

Exam Paper 3: S1 2026 Sample Test

Format: 20 marks, 6 questions, 60 minutes (5 reading + 55 answering) Note: Marks increased from 15 → 20. Same topics, more depth required.

Q1 — Symbolic Logic [5 marks]

Question Summary

(a) Propositional Logic — with Truth Table [3m]

Same scenario as S1 2025 Sample: $(I \wedge F) \rightarrow E$, given $\neg E$. But now explicitly requires a truth table for full marks.

(b) FOL — Birds [2m]

Same “not all birds can fly” question.

Expected Answer

(a):

Step 1: Truth table for $X \rightarrow E$ where $X = I \wedge F$:

When $E = 0$ and implication is TRUE: $X$ must be 0. [1 mark]

Step 2: Truth table for $I \wedge F$:

$I \wedge F = 0$ when at least one is 0. [1 mark]

Step 3: Conclusion — person either lacked valid ID, or fingerprint didn’t match, or both. [1 mark]

(b):

• $\neg \forall x , \text{Fly}(x)$ [1 mark]
• Example: penguins, ostriches, kiwi (kiwi 特别适合 UoA 的语境!) [1 mark]

Analysis

Learning Points

• 2026 版本更重视过程: 3 marks for truth table vs 2025’s ~1.5 marks. Show ALL steps.
• 真值表是得分保障: 即使你能直接用 Modus Tollens 推出结论，画真值表拿更稳的分

💡 策略提示: 5 marks = 25% of total. Spend proportional time (~14 minutes). Don’t rush the truth table.

Q2 — LNN [4 marks]

Question Summary

Same HeatingOn scenario as S1 2025 Sample, but 4 marks (was 2).

(a) Interpret rule + compare with Boolean [2m]

(b) Compute with Cold = 0.9, AtHome = 0.4 [2m]

Expected Answer

Same as S1 2025 Sample Q2 but more detail expected for the extra marks:

• (a): Need deeper comparison — mention gradient-based learning, continuous optimization, partial truth
• (b): Show at least two t-norms, discuss threshold selection, explain practical implications

Analysis

Learning Points

• More marks = more depth expected:
  • 2m version: basic computation + brief threshold mention
  • 4m version: multiple t-norms + threshold discussion + why LNN matters for AI
• 安全策略: 写出所有你知道的 t-norm 计算结果，对比它们

Q3 — Knowledge Graph Embeddings [2 marks]

Question Summary

Same as S1 2025 Sample Q3: explain entity/relation embeddings + KG inference task + example.

Expected Answer

Identical to S1 2025 Sample Q3. (See above.)

Learning Points

• 三年不变: 这道题完全一样。说明 KG embedding 是必考的固定题型。

Q4 — Robot Soccer [2 marks]

Question Summary

Same as S1 2025 Sample Q4: overhead camera, 225 features, describe strategies.

Expected Answer

Identical to S1 2025 Sample Q4. (See above.)

Learning Points

• 同样三年不变: Robot Soccer 策略也是固定考点。

Q5 — Random Forest [3 marks]

Question Summary

Same as S1 2025 Sample Q5: feature selection + why feature bagging.

Expected Answer

Identical to S1 2025 Sample Q5. (See above.)

Q6 — Vagueness vs Uncertainty [4 marks]

Question Summary

New question type (not in S1 2025 Sample):

Classify 4 scenarios:

1. Patient described as “high risk” → Vagueness
2. Security system estimates burglary → Uncertainty
3. Student rated “almost excellent” → Vagueness
4. Spam filter classifies email → Uncertainty

Expected Answer

Analysis

Learning Points

• 万能判断法则:
  • Vagueness → “To what degree?” → Fuzzy Logic (membership functions)
  • Uncertainty → “How likely?” → Bayesian Reasoning (probabilities)
• 快速测试: 概念边界模糊 → vagueness; 世界状态未知 → uncertainty
• 语言线索: “high”, “almost”, “kind of” → vagueness; “estimate”, “predict”, “classify” → uncertainty

⚠️ Common Mistake: Thinking fuzzy logic handles uncertainty. NO — fuzzy handles vagueness; Bayes handles uncertainty. This is THE most important distinction in W5.

S1 2026 Sample Test — Summary Table

Exam Paper 4: S1 2024 Final Exam (Thomas’s Section)

Note: This is the final exam (not mid-semester), with questions from a different instructor (Thomas). These topics may or may not appear in 2026’s mid-semester, but they are useful for final exam preparation and general knowledge.

Q1 — Continual Learning [4 marks]

Question Summary

Concept drift, replay methods, Gaussian Mixture Models in continual learning.

Expected Answer

• Concept drift: Data distribution changes over time; model must adapt
• Replay methods: Store subset of old data; replay during training on new data to prevent catastrophic forgetting
• GMM: Can be used to model data distributions; detect drift by comparing distributions
• Stability-plasticity tradeoff: Too much stability → can’t learn new; too much plasticity → forgets old

Analysis

Q2 — BFS vs UCS [3 marks]

Question Summary

Compare Breadth-First Search and Uniform-Cost Search.

Expected Answer

• BFS: Expands shallowest node first; optimal when all edge costs equal; uses FIFO queue
• UCS: Expands lowest-cost node first; optimal for any non-negative costs; uses priority queue
• Key difference: BFS = optimal for unweighted; UCS = optimal for weighted graphs

Analysis

Q3 — MCTS / UCB1 [3 marks]

Question Summary

Explain the components of the UCB1 formula used in Monte Carlo Tree Search.

Expected Answer

$$UCB1 = \bar{X}_j + C \sqrt{\frac{\ln N}{n_j}}$$

• $\bar{X}_j$: average reward of node $j$ (exploitation term)
• $N$: total visits to parent
• $n_j$: visits to node $j$
• $C$: exploration constant
• $\sqrt{\ln N / n_j}$: exploration term — favors less-visited nodes
• Balances exploration vs exploitation

Analysis

Q4 — RL for Pac-Man [1 mark]

Question Summary

Define state, action, policy, reward for RL applied to Pac-Man.

Expected Answer

• State: Current game board configuration (ghost positions, pellet locations, Pac-Man position)
• Action: Move direction (up, down, left, right)
• Policy: Mapping from state to action (which direction to move in each situation)
• Reward: +10 eating pellet, +200 eating ghost, -500 dying, -1 per time step

Analysis

Q5 — GNN [2 marks]

Question Summary

Explain permutation invariance and permutation equivariance in Graph Neural Networks.

Expected Answer

• Permutation invariance: Output doesn’t change when node ordering changes (graph-level prediction)
• Permutation equivariance: Output permutes consistently with input permutation (node-level embeddings)

Analysis

Q6 — Self-Supervised Learning [2 marks]

Question Summary

Distinguish pretext tasks from downstream tasks in self-supervised learning.

Expected Answer

• Pretext task: Artificial task designed to learn representations without labels (e.g., predict rotation, fill masked words)
• Downstream task: Actual target task the representations are used for (e.g., classification, NER)
• Relationship: Pretext → learn general features; fine-tune on downstream task with few labels

Analysis

Additional Topics from S1 2024 Final (Answer Key)

The following topics appeared in the S1 2024 final exam answer key:

Cross-Exam Patterns（跨卷规律总结）

Pattern 1: Repeated Questions（原题重复出现）

以下题目在多份试卷中几乎一模一样地出现：

💡 核心发现: Xinyu 喜欢在 Sample Test 和 Actual Test 之间做微调而非大改。Sample 就是 Actual 的预告片！

Pattern 2: Question Evolution（题目进化路径）

每个核心考点在不同年份有“升级版“:

Symbolic Logic 进化链:

S1 2025 Sample: (I∧F)→E, ¬E → 推理（无真值表要求）
S1 2025 Actual: (P∨Q)→R, ¬R → 推理 + FOL 组合
S1 2026 Sample: 同 2025 Sample 但要求画真值表，5 marks

→ 趋势: 从 “能推理” → “能推理 + 证明过程” → “能推理 + 证明 + 变体”

LNN 进化链:

S1 2025 Sample: 点值计算 (AND), 2 marks
S1 2025 Actual: 区间计算 (OR) + safety reasoning, 3 marks
S1 2026 Sample: 点值计算 (AND), 4 marks (deeper explanation)

→ 趋势: AND 和 OR 交替考，区间 vs 点值交替考

KG 进化链:

S1 2025 Sample: "Explain embeddings" (概念)
S1 2025 Actual: "Write TransE formula" (公式)
S1 2026 Sample: "Explain embeddings" (概念, 同2025 Sample)

→ 趋势: 概念和公式交替考。两手都要准备。

Pattern 3: Mark Allocation Trends

Key insight: Symbolic Logic + LNN consistently take 35-45% of total marks. These two topics alone are worth nearly half the exam.

Pattern 4: Cognitive Level Distribution

Topic Priority Matrix for 2026 Mid-Semester（2026 期中复习优先级）

Based on cross-exam analysis, here is the definitive priority ranking:

Exam Strategy Recommendations（应试策略建议）

Time Management（时间分配）

For a 20-mark, 55-minute exam:

• ~2.75 minutes per mark
• Q1 (5m): ~14 minutes
• Q2 (4m): ~11 minutes
• Q3 (2m): ~5.5 minutes
• Q4 (2m): ~5.5 minutes
• Q5 (3m): ~8 minutes
• Q6 (4m): ~11 minutes

Cheatsheet Priorities（A4 速查表优先写什么）

Your double-sided A4 page should include (in order of priority):

1. Truth table templates — implication, AND, OR truth tables pre-drawn
2. Modus Tollens + De Morgan — write the formulas
3. T-norm / Co-norm formulas — all 3 variants for AND and OR
4. LNN bounds computation — interval arithmetic rules
5. TransE formula — $f(h,r,t) = |h + r - t|$
6. $\sqrt{p}$ formula — for Random Forest feature bagging
7. Vagueness vs Uncertainty — decision table with examples
8. Backward vs Forward chaining — one-line definitions
9. Fitness function template — multi-objective weighted sum
10. Key FOL patterns — $\neg \forall x = \exists x \neg$

Answer Writing Tips（答题技巧）

1. Show your work: 2026 version gives more marks for process (truth tables, step-by-step computation)
2. Give concrete examples: “(Einstein, bornIn, ?) → Germany” > “it predicts missing links”
3. Use the scenario: Refer back to the specific context (smart home, autonomous vehicle, etc.)
4. Label your steps: “Step 1: … Step 2: … Therefore: …”
5. Quality over quantity: The exam explicitly states this. Be concise and precise.
6. When asked “why”: Give the mechanism, not just the outcome. “Feature bagging decorrelates trees, making ensemble averaging more effective at reducing variance.”

Appendix: Complete Question Index（完整题目索引）

For quick reference, every question across all papers:

考点频率分布 — Topic Frequency Heat Map

基于全部可用考试卷的统计分析（S1 2025 Sample, S1 2025 Actual, S1 2026 Sample, S1 2024 Final）

📊 考点频率总览

🎯 按考题编号统计（Mid-term Test 模式）

每份试卷固定 6 道简答题，主题分布如下：

规律总结：

• Q1 永远是 Symbolic Logic（分值从 2→5 递增！）
• Q2 永远是 LNN（分值从 2→4 递增！）
• Q3 永远是 Knowledge Graphs / TransE
• Q4-Q6 在以下主题中轮换：Decision Trees/RF、Soft Computing/Fuzzy、NEAT/GA、Robot Soccer、MYCIN

📈 分值趋势分析

2025 Sample (15m):  Logic(3) + LNN(2) + KG(2) + Robot(2) + RF(3) + MYCIN(3)
2025 Actual (15m):  Logic(2) + LNN(3) + KG(2) + DT(2) + Fuzzy(3) + GA(3)
2026 Sample (20m):  Logic(5) + LNN(4) + KG(2) + Robot(2) + RF(3) + V/U(4)

关键发现：

1. 2026 总分从 15→20，额外的 5 分主要加在了 Logic (+2) 和 LNN (+2) 上
2. Symbolic Logic 要求从“代数推导“升级为“完整真值表“
3. Vagueness vs Uncertainty 是新增的高分考点（4分）

⏰ 建议复习时间分配（基于频率和分值）

🧩 考点共现分析

以下概念经常在同一道题或同一考卷中一起出现：

🎯 Cheatsheet 优先级排序

根据出题频率和分值，你的双面 A4 手写笔记应该包含以下内容（按重要性排序）：

必须写（占据 60% 空间）

1. Modus Tollens 公式 + De Morgan’s Laws + 两种 premise 结构的展开方式
2. 完整的 implication 真值表 (4 行)
3. LNN Soft Logic (Product-Sum): AND = A×B, OR = A+B-AB, NOT = 1-A
4. LNN Truth Bounds 分类规则 (L≥α → TRUE, U≤α → FALSE, etc.)
5. OR bounds: L=max(L₁,L₂), U=max(U₁,U₂)
6. TransE: h+r≈t, f(h,r,t) = ||h+r-t||
7. Entropy: H(X) = -Σp(x)log₂p(x), IG = H(Y) - H(Y|X)
8. Gini: G(D) = 1 - Σpᵢ²
9. Fuzzy: AND=min, OR=max, NOT=1-μ
10. Vagueness vs Uncertainty 判断流程图

建议写（占据 30% 空间）

11. Bayes’ Theorem: P(H|e) = P(e|H)P(H)/P(e)
12. Naïve Bayes: P(C|x) ∝ P(C)ΠP(xᵢ|C)
13. CART = greedy (no look-ahead)
14. RF = Bagging + Feature Bagging (√features)
15. CF(conclusion) = CF(premise) × CF(rule)
16. Forward vs Backward Chaining 对比
17. NEAT: speciation distance δ = c₁E/N + c₂D/N + c₃W̄
18. Flocking 3 rules: separation, cohesion, alignment

如果有空间（占据 10%）

19. FOL 量词否定: ¬∀x P(x) ≡ ∃x ¬P(x)
20. STEAM: Joint Persistent Goal (A/U/I)
21. Ontology vs KG 区别
22. RDF triple 格式

命题风格分析 — Teacher Style Analysis

Instructor: Xinyu Zhang | Course: COMPSCI 713 AI Fundamentals | S1 2026 基于全部可用考试卷分析（S1 2025 Sample, S1 2025 Actual, S1 2026 Sample, S1 2024 Final）

👤 教师信息

• Instructor: Xinyu Zhang (School of Computer Science, University of Auckland)
• Course: COMPSCI 713: AI Fundamentals, S1 2026
• Website: zhangxinyu-xyz.github.io
• 另一位出题者: Thomas (负责 Part 2 — 深度学习/RL/LLM 相关，与 Xinyu 的 Part 1 分开考)

🎯 出题风格总结

1. 偏好应用场景题（Application-Based Scenarios）

Xinyu 的题目几乎从不直接问定义。每道题都嵌入在一个具体场景中：

应对策略：不要死记硬背定义，要练习在新场景中应用概念。

2. 偏好“为什么“而非“是什么“

典型问法：

• “Why is feature bagging considered a good idea?” (不是 “What is feature bagging?”)
• “What exactly is meant by saying CART is ‘greedy’?” (不是 “Define CART”)
• “Why is using bounds beneficial in safety-critical applications?” (不是 “What are bounds?”)

应对策略：准备好每个概念的原因和动机，不仅仅是定义。

3. 重视对比分析（Contrast & Compare）

高频出题模式：

• Boolean logic vs LNN soft logic（每卷 Q2）
• Traditional logic vs Fuzzy logic（2025 Actual Q5）
• Vagueness vs Uncertainty（2026 Sample Q6）
• Decision tree vs Decision forest（2024 Final）
• Forward chaining vs Backward chaining（隐含在 MYCIN 题中）

应对策略：准备好两栏对比表格，考试时直接画表回答。

4. 计算题轻量但必须准确

• LNN: 0.9 × 0.4 = 0.36 这种简单乘法
• Entropy/Gini: 不会给太复杂的数据，但公式必须正确
• TransE: 概念性理解 h+r≈t 即可，不需要实际向量计算

应对策略：把公式写在 cheatsheet 上，考试时代入数字即可。

5. 评分标准：Quality over Quantity

考试说明明确写道：

“We privilege quality over quantity, i.e., you do not need to write very long answers. Be concise and clear.”

6. 常用句式模式

Xinyu 的题目经常使用以下句式：

• “Use propositional logic to deduce what must be true about X and Y.” → 用 Modus Tollens + De Morgan’s
• “What does this rule represent in natural language, and how is it different from…” → 翻译 + 对比
• “Explain how the LNN would likely compute…” → 写出计算步骤
• “Contrast how the above rule might work using traditional logic as compared to…” → 画对比表
• “For each of the following situations, state whether it is mainly…” → 分类 + 简短理由
• “Describe one strategy or collective behaviour…” → 从课堂内容中选一个，解释清楚
• “Name the elements that should be part of the fitness function…” → 列出 3-5 个关键要素

🔄 题目进化趋势（2025 → 2026）

关键发现：2026 时间更紧了！每分只有 2.75 分钟，比 2025 的 3.7 分钟少了约 25%。必须更加简洁高效。

⚠️ 常见陷阱与扣分点

📝 高分答题策略

1. 结构化回答

对于 2-3 分的题，使用：

[1句总结] + [关键点1 + 解释] + [关键点2 + 解释]

2. 对比题用表格

| Aspect | Method A | Method B |
|--------|---------|---------|
| ...    | ...     | ...     |

3. 计算题写出每一步

Given: Cold = 0.9, AtHome = 0.4
AND (Product-Sum) = 0.9 × 0.4 = 0.36
If threshold α = 0.5, then 0.36 < 0.5 → heating NOT activated

4. 推理题用链式推导

Given: ¬E
Rule: (I ∧ F) → E
By Modus Tollens: ¬E → ¬(I ∧ F)
By De Morgan's: ¬(I ∧ F) = ¬I ∨ ¬F
∴ Either ¬I or ¬F (or both)

5. 时间管理（2026 格式，20 marks / 55 min）

Symbolic Logic – Propositional & First-Order Logic

🎯 Exam Importance

🔴 GUARANTEED TO APPEAR | Every single test paper has a logic question as Q1

Key observation: The question has been worth 2–5 marks across papers, and the 2026 sample tripled the propositional logic marks by requiring a full truth table. Prepare for both approaches (algebraic deduction AND truth table verification).

📖 Core Concepts (Quick Reference Table)

🧠 Feynman Draft – Learning From Scratch

Part 1: Propositional Logic

Imagine you are a security guard at a building entrance. Your job manual has simple rules written as “if… then…” statements. Each fact is either TRUE or FALSE – no grey areas, no “maybe.” Your entire job is to follow the rules and figure out what must be true.

For example, your manual says:

“If the person has a valid ID and their fingerprint matches, then grant entry.”

In symbols: $(I \wedge F) \rightarrow E$

Now, suppose today the person was denied entry ($\neg E$). What can you figure out?

Think of it this way: the rule promises that having both ID and fingerprint match guarantees entry. The person was NOT granted entry. So the guarantee must not have kicked in – meaning they did NOT have both. Either no valid ID, or no fingerprint match, or both were missing.

This reasoning is called Modus Tollens（否定后件）: if the consequence didn’t happen, the premise couldn’t have been fully satisfied.

$$P \rightarrow Q, \quad \neg Q \quad \Longrightarrow \quad \neg P$$

But wait – what does “not both” mean precisely?

$\neg(I \wedge F)$ means “it’s not the case that BOTH are true.” By De Morgan’s Law, this equals $\neg I \vee \neg F$ – “at least one of them is false.”

This is exactly how every exam question on this topic works. Every. Single. One.

Part 2: The Implication Trap

Here is the single most confusing thing in propositional logic, and the lecture opens with it:

“If it rains today, I will bring an umbrella.” ($P \rightarrow Q$)

You see the person carrying an umbrella ($Q$ is true). Can you conclude it is raining ($P$)?

NO! $Q \rightarrow P$ is NOT the same as $P \rightarrow Q$. The person might just like carrying umbrellas. This mistake is called Affirming the Consequent（肯定后件谬误） – the lecture slide 4-5 opens with exactly this example.

Here is the full truth table for implication:

The key insight: $P \rightarrow Q$ is false ONLY when P is true and Q is false.

Why is $\text{false} \rightarrow \text{anything}$ true? Think of it as a promise: “If it rains, I’ll bring an umbrella.” If it doesn’t rain, I haven’t broken my promise regardless of whether I carry an umbrella. The promise is only broken when rain happens and no umbrella appears.

⚠️ Common Misconception: Students think $P \rightarrow Q$ means “P causes Q” or “P and Q are related.” It does NOT. Material implication is purely about truth values. “If pigs fly, then I am the Queen of England” is technically TRUE because the premise is false. This is called vacuous truth（空真）.

Part 3: First-Order Logic

Propositional logic treats facts as indivisible boxes – “it is raining” is one atomic unit. But what if you need to say something about many things at once?

Imagine you are a biologist studying birds. You want to express: “Not all birds in this region can fly.” In propositional logic, you would need a separate proposition for each bird – $\text{Fly}(\text{robin})$, $\text{Fly}(\text{kiwi})$, $\text{Fly}(\text{penguin})$, etc. If you have 1000 birds, you need 1000 propositions. This is the verbosity problem（冗余问题）.

First-order logic fixes this by introducing:

• Objects: things in your world (birds, people, squares in Wumpus World)
• Predicates (relations): properties of objects ($\text{Fly}(x)$, $\text{Pit}(x,y)$)
• Functions: mappings from objects to objects ($\text{left}(x,y)$, $\text{fatherOf}(x)$)
• Quantifiers: $\forall$ (“for all”) and $\exists$ (“there exists”)

So “Not all birds can fly” becomes simply: $\neg \forall x, \text{Fly}(x)$

Which is equivalent to: $\exists x, \neg\text{Fly}(x)$ – “there exists a bird that cannot fly.”

⚠️ Common Misconception: Students write $\forall x, \neg\text{Fly}(x)$ for “not all birds fly.” This is WRONG – it means “NO bird can fly” (way too strong). The negation must go OUTSIDE the quantifier: $\neg\forall x, \text{Fly}(x)$.

⚠️ Common Misconception: With $\forall$, use $\rightarrow$ (implication) not $\wedge$. “Every student cheats” is $\forall x (\text{Student}(x) \rightarrow \text{Cheat}(x))$, NOT $\forall x (\text{Student}(x) \wedge \text{Cheat}(x))$. The latter says “everything is both a student AND a cheater” – it claims your dog is a cheating student!

💡 Core Intuition: Propositional logic is about combining true/false statements with connectives; FOL adds the power to talk about “all” and “some” objects in a domain using quantifiers and predicates.

📐 Formal Definitions

Propositional Logic – Complete Syntax and Semantics

Syntax (from lecture slide 15):

• Atomic propositions (atoms): $\text{Atom} = {X_1, \ldots, X_k}$, each with domain ${\text{true}, \text{false}}$ (or ${0, 1}$).
• Compound propositions are built using connectives: $\neg A$, $(A \vee B)$, $(A \wedge B)$, $(A \rightarrow B)$, $(A \leftarrow B)$, $(A \leftrightarrow B)$

Semantics:

An interpretation $\pi : \text{Atom} \rightarrow {\text{true}, \text{false}}$ assigns truth values to all atoms. The truth value of any compound proposition is determined by the following table:

Master Truth Table (MEMORIZE THIS)

Key observations:

• $A \rightarrow B$ is false ONLY in row 2 (A true, B false)
• $A \leftrightarrow B$ is true when A and B have the SAME value
• $A \leftarrow B$ is the “reverse implication” ($B \rightarrow A$)

Complete Logical Equivalence Laws (from lecture slide 22)

These are your tools for algebraic manipulation. The exam requires you to cite which law you use.

Logical Implication vs. Material Implication

This distinction is subtle and important (lecture slide 21):

• Material implication ($A \rightarrow B$): a connective inside a formula. It has a truth value.
• Logical implication ($A \Rightarrow B$): a meta-statement about formulas. It means: for EVERY interpretation $\pi$, if $\pi(A) = \text{true}$ then $\pi(B) = \text{true}$.

Verification methods:

1. Truth table: check that every row where A is true also has B true
2. Equivalent test: $A \Rightarrow B$ if and only if $A \rightarrow B$ is a tautology

Key Inference Rules (from lecture slide 21)

$$\text{Modus Ponens: } ((A \rightarrow B) \wedge A) \Rightarrow B$$

$$\text{Modus Tollens: } ((A \rightarrow B) \wedge \neg B) \Rightarrow \neg A$$

$$\text{Syllogism: } ((A \rightarrow B) \wedge (B \rightarrow C)) \Rightarrow (A \rightarrow C)$$

First-Order Logic – Complete Syntax and Semantics

Three building blocks (lecture slide 25):

1. Objects: people, houses, numbers, grid squares, …
2. Relations (Predicates): properties or relationships – unary ($\text{Red}(x)$), binary ($\text{Adjacent}(x,y)$), n-ary
3. Functions: mappings that produce objects – $\text{fatherOf}(x)$, $\text{left}(x,y)$

Signature (lecture slide 29): the vocabulary $S = {R_1, \ldots, R_k, f_1, \ldots, f_\ell}$ – the set of relation and function symbols.

Terms (lecture slide 29):

• Every variable is a term: $x, y, z$
• Every constant is a term: $1, 2, \text{Alice}$ (a constant is a 0-ary function)
• If $f$ is a function of arity $r$ and $t_0, \ldots, t_{r-1}$ are terms, then $f(t_0, \ldots, t_{r-1})$ is a term
• A ground term has no variables (all constants/applied functions on constants)

Formulas (lecture slide 30):

• Atomic: $t_0 = t_1$ (equality) or $R(t_0, \ldots, t_{n-1})$ (predicate applied to terms)
• Compound: built from atomic formulas using $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$ and quantifiers $\forall x, \exists x$

Free vs. Bound Variables (lecture slide 32):

• A variable $x$ is bound if it appears within $\forall x : \varphi$ or $\exists x : \varphi$
• A variable $x$ is free if it is not within any quantifier’s scope
• A sentence is a formula with NO free variables

Satisfaction Relation (lecture slide 33): $I \vDash \varphi$ means interpretation $I$ satisfies formula $\varphi$:

• $I \vDash \forall x : \varphi$ iff for ALL $a \in D$, $I[x/a] \vDash \varphi$
• $I \vDash \exists x : \varphi$ iff there is SOME $a \in D$ such that $I[x/a] \vDash \varphi$

Quantifier Negation Laws (De Morgan’s for Quantifiers)

$$\neg \forall x, \varphi(x) \equiv \exists x, \neg\varphi(x)$$ $$\neg \exists x, \varphi(x) \equiv \forall x, \neg\varphi(x)$$

Additional FOL equivalences (lecture slide 34): $$\neg\neg\exists x : \varphi(x) \equiv \forall x : \neg\varphi(x) \quad [\text{Double negation + quantifier swap}]$$ $$\exists x : (\varphi_1(x) \vee \varphi_2(x)) \equiv (\exists x : \varphi_1(x)) \vee (\exists x : \varphi_2(x))$$ $$\forall x : (\varphi_1(x) \wedge \varphi_2(x)) \equiv (\forall x : \varphi_1(x)) \wedge (\forall x : \varphi_2(x))$$ $$\neg\forall x : (\varphi_1(x) \rightarrow \varphi_2(x)) \equiv \exists x : (\varphi_1(x) \wedge \neg\varphi_2(x))$$

🔄 Mechanisms & Derivations – The Exam Algorithms

Algorithm 1: Modus Tollens with De Morgan’s (The Core Exam Pattern)

This is the algorithm you will execute in 100% of logic exam questions. Master it completely.

Input: A rule $P \rightarrow Q$ and an observation $\neg Q$

Steps:

1. Identify the structure: What is $P$? What is $Q$? (P is often compound, e.g., $I \wedge F$ or $P \vee Q$)
2. Apply Modus Tollens: From $P \rightarrow Q$ and $\neg Q$, conclude $\neg P$
3. Simplify $\neg P$ using De Morgan’s Law:
   • If $P = (A \wedge B)$: $\neg(A \wedge B) = \neg A \vee \neg B$ (“at least one is false”)
   • If $P = (A \vee B)$: $\neg(A \vee B) = \neg A \wedge \neg B$ (“BOTH are false”)
4. State the conclusion in natural language

Algorithm 2: Truth Table Verification (Required in S1 2026 Sample)

The 2026 sample test explicitly asks “Show your steps (Truth Table) clearly” for 3 marks. Here is the exact procedure:

Step 1: Write the truth table for $X \rightarrow E$ where $X = I \wedge F$ (1 mark):

Step 2: Since $\neg E$ (E = 0) and $X \rightarrow E$ must be true, look at rows where E = 0. Only row 1 satisfies both conditions. Therefore $X = I \wedge F = 0$ (1 mark).

Step 3: Write the truth table for $I \wedge F$ to determine what $I \wedge F = 0$ means (1 mark):

Conclusion: At least one of I, F must be 0. The person either didn’t have valid ID, or fingerprint didn’t match (or both).

Algorithm 3: FOL Translation

Input: An English sentence

Steps:

1. Identify the domain: What set of objects are we talking about?
2. Define predicates: What properties/relations are relevant?
3. Identify the quantifier: “all”/“every” $\rightarrow$ $\forall$; “some”/“exists”/“not all” $\rightarrow$ involves $\exists$
4. Construct the formula:
   • “Every X that has property A also has property B” $\rightarrow$ $\forall x, (A(x) \rightarrow B(x))$
   • “Not all X have property A” $\rightarrow$ $\neg\forall x, A(x)$ or equivalently $\exists x, \neg A(x)$
   • “Some X has property A” $\rightarrow$ $\exists x, A(x)$
5. Verify: Read the formula back in English to check

Algorithm 4: FOL Modus Tollens (S1 2025 Actual Test Pattern)

Input: A universal rule $\forall x, (P(x) \rightarrow Q(x))$ and a fact $\neg Q(a)$ for a specific object $a$

Steps:

1. Universal Instantiation: From $\forall x, (P(x) \rightarrow Q(x))$, substitute $x = a$: $P(a) \rightarrow Q(a)$
2. Apply Modus Tollens: From $P(a) \rightarrow Q(a)$ and $\neg Q(a)$, conclude $\neg P(a)$
3. State conclusion: Object $a$ does not have property P

⚖️ Trade-offs & Comparisons

Propositional Logic vs First-Order Logic

Modus Ponens vs Modus Tollens vs Converse Error

De Morgan’s: $\wedge$ vs $\vee$ Negation

Memory trick: negation “flips” the connective ($\wedge \leftrightarrow \vee$) and negates each operand.

$\forall$ with $\rightarrow$ vs $\exists$ with $\wedge$ (Critical FOL Pattern)

Rule of thumb: $\forall$ pairs with $\rightarrow$; $\exists$ pairs with $\wedge$.

🏗️ Design Question Framework

If asked to model a scenario using symbolic logic:

WHAT: Define the propositions/predicates and their English meanings

• List each atomic proposition or predicate with a clear one-line definition
• Specify the domain for FOL

WHY: Why use formal logic here?

• Precise and unambiguous (unlike natural language)
• Machine-verifiable (automated reasoning)
• Supports inference: derive new facts from existing rules

HOW: Write the rules as logical formulas

• Express each rule using connectives and quantifiers
• Show at least one inference step (Modus Ponens or Modus Tollens)

TRADE-OFF: Discuss limitations

• Propositional logic: verbose, can’t express “for all”
• FOL: more expressive but semi-decidable
• Both: can’t handle uncertainty (need fuzzy logic / LNN for soft values)

EXAMPLE: Demonstrate with a concrete instance

• Show a specific inference with your rules

📝 Exam Questions – Complete Collection with Model Answers

===== EXAM Q1: S1 2025 Sample Test Q1(a) – 1 mark =====

Question: In a secure facility, $(I \wedge F) \rightarrow E$. The person was not granted entry ($\neg E$). Deduce what must be true about I and F.

Model Answer:

Given: $(I \wedge F) \rightarrow E$ and $\neg E$.

By Modus Tollens: $\neg E \Rightarrow \neg(I \wedge F)$.

By De Morgan’s Law: $\neg(I \wedge F) \equiv \neg I \vee \neg F$.

Conclusion: The person either did not have a valid ID ($\neg I$) or the fingerprint did not match ($\neg F$), or both.

Marking note: 1 mark for correct application of Modus Tollens + De Morgan’s + stating conclusion.

===== EXAM Q2: S1 2025 Sample Test Q1(b)(i) – 1 mark =====

Question: A biologist claims “Not all birds in this region can fly.” Domain: all birds in the region. $\text{Fly}(x)$ = bird x can fly. Write in FOL.

Model Answer:

$$\neg \forall x, \text{Fly}(x)$$

Equivalently: $\exists x, \neg\text{Fly}(x)$

Marking note: Either form accepted for full mark.

===== EXAM Q3: S1 2025 Sample Test Q1(b)(ii) – 1 mark =====

Question: Provide a realistic example (one sentence) that would make the statement true.

Model Answer:

“There is a penguin in this region, and penguins cannot fly.”

Marking note: Any concrete example naming a flightless bird (penguin, kiwi, ostrich, emu) is acceptable.

===== EXAM Q4: S1 2025 Actual Test Q1(a) – 1 mark =====

Question: In a smart office, $(P \vee Q) \rightarrow R$. The alarm did not sound ($\neg R$). Deduce what must be true about P and Q.

Where: P = door is open, Q = motion sensor triggered, R = alarm sounds.

Model Answer:

Given: $(P \vee Q) \rightarrow R$ and $\neg R$.

By Modus Tollens: $\neg R \Rightarrow \neg(P \vee Q)$.

By De Morgan’s Law: $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$.

Conclusion: The door was NOT open AND the motion sensor was NOT triggered. (Both must be false.)

Critical difference from the sample test: Here the premise uses $\vee$ (OR), so De Morgan’s produces $\wedge$ (AND). The conclusion is STRONGER: BOTH P and Q must be false (not just “at least one”).

===== EXAM Q5: S1 2025 Actual Test Q1(b) – 1 mark =====

Question: $\forall x, (\text{Cheat}(x) \rightarrow \text{Disqualified}(x))$. Alice is not disqualified. Did Alice cheat?

Model Answer:

From the universal rule: $\forall x, (\text{Cheat}(x) \rightarrow \text{Disqualified}(x))$

Instantiate for Alice: $\text{Cheat}(\text{Alice}) \rightarrow \text{Disqualified}(\text{Alice})$

Given: $\neg\text{Disqualified}(\text{Alice})$

By Modus Tollens: $\neg\text{Disqualified}(\text{Alice}) \Rightarrow \neg\text{Cheat}(\text{Alice})$

Conclusion: Alice did not cheat.

Key steps for marks: (1) Universal instantiation, (2) Modus Tollens, (3) Conclusion in English.

===== EXAM Q6: S1 2026 Sample Test Q1(a) – 3 marks =====

Question: SAME scenario as 2025 sample $(I \wedge F) \rightarrow E$, $\neg E$, but now explicitly requires truth table for 3 marks.

Model Answer:

Step 1 (1 mark): Let $X = I \wedge F$. Truth table for $X \rightarrow E$:

$X$ ($I \wedge F$)	$E$	$X \rightarrow E$
0	0	1
0	1	1
1	0	0
1	1	1

Step 2 (1 mark): Since $E = 0$ and $X \rightarrow E$ is true (given the rule holds), the only valid row is row 1 where $X = 0$. Therefore $I \wedge F = 0$.

Truth table for $I \wedge F$:

$I$	$F$	$I \wedge F$
0	0	0 ✓
0	1	0 ✓
1	0	0 ✓
1	1	1 ✗

Step 3 (1 mark): Since $I \wedge F = 0$, at least one of $I$ or $F$ must be 0.

Conclusion: The person either did not have a valid ID or the fingerprint did not match (or both).

===== EXAM Q7: S1 2026 Sample Test Q1(b) – 2 marks =====

Identical to S1 2025 Sample Q1(b). Same answers apply:

• (i) $\neg\forall x, \text{Fly}(x)$ [1 mark]
• (ii) “There is a penguin in this region, and penguins cannot fly.” [1 mark]

===== LECTURE MOTIVATION QUESTION (potential exam question) =====

Question (slide 4-5): “If it rains, I bring an umbrella” ($P \rightarrow Q$). You see the person with an umbrella ($Q$). Can you conclude it is raining ($P$)?

Answer: No. $Q \rightarrow P$ (converse) is NOT logically equivalent to $P \rightarrow Q$. Seeing $Q$ true does not let us conclude $P$. This is the fallacy of Affirming the Consequent.

To conclude $P$, you would need $Q \rightarrow P$ (the converse) as a separate rule, or equivalently $P \leftrightarrow Q$ (biconditional).

🔬 Additional Practice Problems (Exam-Style)

Practice 1: Combined Modus Tollens with Additional Information

Given: $(P \wedge A) \rightarrow C$; $\neg C$; $A$ is true.

Question: What can you conclude about P?

Practice 2: FOL Translation – University Scenario

Translate: “Every computer science student at Auckland takes at least one math course.”

Domain setup:

• $\text{CS}(x)$: x is a CS student
• $\text{Math}(y)$: y is a math course
• $\text{Takes}(x, y)$: student x takes course y

Practice 3: Identify the Fallacy

Given: $\forall x, (\text{Student}(x) \rightarrow \text{Enrolled}(x, \text{Uni}))$. David is enrolled at Uni. Conclusion: David is a student.

Practice 4: FOL with Negated Quantifiers

Translate: “No robot in the warehouse is idle.”

Practice 5: Truth Table for OR-based Implication

Given: $(A \vee B) \rightarrow C$, $\neg C$. Deduce what must be true.

🌍 Wumpus World – The Lecture’s Running Example

The Wumpus World (lecture slides 17-20) is used to illustrate how propositional logic represents knowledge and enables inference. You should understand this example for conceptual questions.

Setup: A $4 \times 4$ grid with pits, a Wumpus, and gold. The agent navigates from (1,1).

Key rules in propositional logic (slide 19):

• “Square (1,3) has a pit”: $P_{1,3}$
• “Square (2,2) has no wumpus”: $\neg W_{2,2}$
• “Either (2,2) has a pit or (1,3) has a pit”: $P_{2,2} \vee P_{1,3}$
• “Since (2,2) has no stench, (1,2) has no wumpus”: $\neg S_{2,2} \rightarrow \neg W_{1,2}$
• “(2,4) is safe iff no pit or wumpus”: $OK_{2,4} \leftrightarrow (\neg P_{2,4} \wedge \neg W_{2,4})$

Inference example (slide 20):

• $P1 = \neg S_{1,1} \wedge \neg B_{1,1}$ (no stench, no breeze at start)
• From P1, infer $P2 = \neg S_{1,1}$ (no stench at start)
• $P3$: if $(3,1)$ is a pit, at least one of $(2,1)$, $(3,2)$ has a breeze
• $P4$: if none of $(2,1)$, $(3,2)$ has a breeze, then $(3,1)$ is not a pit

This demonstrates how propositional logic enables forward chaining (derive new facts from known facts) and backward chaining (verify a hypothesis by checking its premises).

Why propositional logic is weak for Wumpus World (slide 24):

• “A breeze is sensed iff an adjacent location contains a pit” requires one formula per square:
  • $B_{1,1} \leftrightarrow (P_{1,2} \vee P_{2,1})$
  • $B_{1,2} \leftrightarrow (P_{1,3} \vee P_{2,2} \vee P_{1,1})$
  • … one for EACH square

In FOL, this becomes ONE formula: $\forall x, (\text{Breeze}(x) \leftrightarrow \exists y, (\text{Adjacent}(x,y) \wedge \text{Pit}(y)))$

🌐 English Expression Tips

Exam Answer Sentence Templates

For Modus Tollens questions:

• “Given the rule [formula] and the observation [negated conclusion], by Modus Tollens we can deduce [negated premise].”
• “Applying De Morgan’s Law, $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$, which means at least one of P, Q must be false.”
• “Applying De Morgan’s Law, $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$, which means both P and Q must be false.”

For FOL translation questions:

• “Let the domain be [X]. Define predicate name to mean [meaning].”
• “The statement translates to: [formula].”
• “This is equivalent to [alternative form] by [law name].”

For FOL reasoning:

• “From the universal rule $\forall x, (P(x) \rightarrow Q(x))$, we instantiate for [specific object]: $P(a) \rightarrow Q(a)$.”
• “Given $\neg Q(a)$, by Modus Tollens: $\neg P(a)$. Therefore, [conclusion in English].”

Commonly Confused Terms

Commonly Misspelled Words

• proposisional $\rightarrow$ propositional
• modus tolens $\rightarrow$ modus tollens (double-l)
• De Morgans $\rightarrow$ De Morgan’s (with apostrophe)
• equivelance $\rightarrow$ equivalence
• tautaology $\rightarrow$ tautology
• existensial $\rightarrow$ existential
• quantifer $\rightarrow$ quantifier

✅ Self-Test Checklist

Propositional Logic Fundamentals

• Can I write the truth table for ALL five connectives ($\neg, \wedge, \vee, \rightarrow, \leftrightarrow$) from memory?
• Can I explain why $P \rightarrow Q$ is TRUE when $P$ is false (vacuous truth)?
• Can I convert $P \rightarrow Q$ to $\neg P \vee Q$ and back?
• Do I know both De Morgan’s Laws and can I apply them correctly?
• Can I distinguish between $\neg(A \wedge B) = \neg A \vee \neg B$ and $\neg(A \vee B) = \neg A \wedge \neg B$?

Inference Rules

• Can I identify Modus Tollens in a word problem and apply it step by step?
• Can I explain why Affirming the Consequent ($P \rightarrow Q$, $Q$ $\therefore$ $P$) is INVALID?
• Can I state the difference between Modus Ponens and Modus Tollens?
• Can I perform the full truth-table-based deduction required by the 2026 sample?

First-Order Logic

• Can I translate “Not all X have property P” correctly as $\neg\forall x, P(x)$ (NOT $\forall x, \neg P(x)$)?
• Do I know the quantifier negation laws: $\neg\forall x = \exists x, \neg$ and $\neg\exists x = \forall x, \neg$?
• Can I apply Universal Instantiation followed by Modus Tollens (S1 2025 actual test pattern)?
• Do I know the rule of thumb: $\forall$ pairs with $\rightarrow$, $\exists$ pairs with $\wedge$?
• Can I distinguish free vs. bound variables and identify whether a formula is a sentence?

Exam Readiness

• Can I solve the AND-premise version: $(I \wedge F) \rightarrow E$, $\neg E$ $\therefore$ $\neg I \vee \neg F$?
• Can I solve the OR-premise version: $(P \vee Q) \rightarrow R$, $\neg R$ $\therefore$ $\neg P \wedge \neg Q$?
• Can I do both the algebraic AND the truth table method for the same problem?
• Can I provide a realistic example for $\neg\forall x, \text{Fly}(x)$ (e.g., penguins, kiwis)?
• Can I explain why “D is enrolled $\therefore$ D is a student” is a converse error?
• Have I practiced writing each answer within 3 minutes (time pressure)?

📋 Quick Reference Card (For Your Handwritten Cheat Sheet)

MODUS TOLLENS:  P->Q, ~Q  ==>  ~P

DE MORGAN'S:    ~(A^B) = ~Av~B    (AND becomes OR)
                ~(AvB) = ~A^~B    (OR becomes AND)

IMPLICATION:    P->Q  =  ~PvQ

QUANTIFIERS:    ~forall x P(x)  =  exists x ~P(x)
                ~exists x P(x)  =  forall x ~P(x)

FOL RULE:       forall uses ->    (forall x: P(x) -> Q(x))
                exists uses ^     (exists x: P(x) ^ Q(x))

CONVERSE ERROR: P->Q, Q  =/=>  P    (INVALID!)
CONTRAPOSITIVE: P->Q  =  ~Q->~P     (VALID equivalent)

EXAM PATTERN:
  1. Identify P->Q structure
  2. Apply Modus Tollens: ~Q ==> ~P
  3. Apply De Morgan's to simplify ~P
  4. State conclusion in English

Logic Neural Networks (LNN) & Differentiable Logic

🎯 Exam Importance

🔴 必考 — LNN appears as Question 2 in EVERY test paper

Pattern: LNN is always Q2, worth 2-4 marks (13-20% of the test). Two sub-patterns repeat:

1. Interpret an LNN rule in natural language and contrast with Boolean logic (every test)
2. Either compute a soft-logic value OR reason about truth bounds (every test)

📖 Core Concepts

🧠 Feynman Draft – From Zero to LNN

Part 1: Why Do We Need Logic in Neural Networks?

Imagine a doctor looking at an X-ray. A neural network might say “85% chance of cancer” – but the doctor asks why. The neural network shrugs. It is a black box（黑盒）: powerful at pattern recognition but terrible at explaining itself.

Now imagine a rule-based system: “IF the patient has a tumor larger than 2cm AND the margins are irregular THEN suspect malignancy.” This is transparent – you can see exactly why the decision was made. But writing thousands of such rules by hand is impractical, and rules cannot handle “maybe” situations.

LNN is the marriage of both: it keeps the logical structure (so you can read the rules) but makes the operators smooth and continuous (so gradient descent can learn the parameters from data).

Part 2: From Light Switches to Dimmer Switches

Classical Boolean logic is like a light switch – strictly ON (1) or OFF (0). But the real world is not binary. Is 12 degrees Celsius “cold”? It is somewhat cold – maybe 0.6 out of 1.0.

Soft logic replaces the light switch with a dimmer switch. Instead of {0, 1}, truth values live in the continuous interval [0, 1]. Every logical operator (AND, OR, NOT) becomes a smooth function.

Why does smoothness matter? Because neural networks learn by computing gradients. Boolean AND has zero gradient almost everywhere (it is a step function), so backpropagation cannot adjust weights. But if AND = $A \times B$, the gradient $\frac{\partial}{\partial A} = B$ exists everywhere. Now we can learn!

Part 3: The Dimmer Switch Operators (Product-Sum)

This is the specific soft logic system used in the exam. Memorize it.

Why does OR = $A + B - AB$? Think of probability. If you roll two dice, the chance of at least one six is $P(A) + P(B) - P(A \text{ and } B)$. The subtraction avoids double-counting the overlap. This is exactly the inclusion-exclusion principle.

Part 4: What Makes LNN Different from Plain Fuzzy Logic?

⚠️ Common Misconception: Students think LNN is just “fuzzy logic with a neural network.” This is WRONG. LNN has three features that fuzzy logic lacks:

1. Learnable weights – the operator parameters are tuned by gradient descent
2. Bidirectional inference – information flows both up (inputs to conclusion) AND down (conclusion to inputs), not just one direction
3. Logical soundness guarantees – LNN is mathematically proven to maintain consistency

Part 5: Truth Bounds – The Safety Net

Instead of a single number, LNN gives you a range [L, U] for each proposition. Think of it as a confidence interval:

• Cold = [0.8, 1.0] means “we are fairly sure it is cold – at least 0.8, possibly up to 1.0”
• AtHome = [0.3, 0.5] means “quite uncertain whether someone is home”

Given a threshold $\alpha$:

• If both L and U are above $\alpha$ ($L \ge \alpha$) – Definitely TRUE
• If both L and U are below $\alpha$ ($U \le \alpha$) – Definitely FALSE
• If L < $\alpha$ < U (bounds straddle the threshold) – UNCERTAIN
• If L > U – CONTRADICTION (should not happen in a well-formed LNN)

💡 Core Intuition: LNN replaces Boolean {0,1} switches with smooth [0,1] dimmers, adds confidence bounds [L,U], and uses bidirectional message passing – giving you learnable, explainable, uncertainty-aware reasoning.

📐 Formal Definitions

Soft Logic Operators (Product-Sum) – THE EXAM DEFAULT

These are the operators used in all exam questions unless stated otherwise:

$$\text{AND}(A, B) = A \times B$$

$$\text{OR}(A, B) = A + B - A \times B$$

$$\text{NOT}(A) = 1 - A$$

Three T-Norms You Must Know

Lukasiewicz-like Logic in LNN (from Slide 40)

The lecture defines a basis activation function（基础激活函数）:

$$f(x) = \max(0, \min(1, x))$$

This clamps the output to [0, 1]. Then:

Logical AND for inputs $x_1, x_2, …, x_n$:

$$\bigwedge_{i \in I} x_i = f\left(1 - \sum_i (1 - x_i)\right)$$

Logical OR for inputs $x_1, x_2, …, x_n$:

$$\bigvee_{i \in I} x_i = f\left(\sum_i x_i\right)$$

Truth Bounds Classification (from Slide 34)

Given bounds [L, U] and threshold $\alpha$:

Truth Bounds Visualization:

0                   α                   1
|===================|===================|
        L_____U                           → FALSE (both below α)
                        L_____U           → TRUE (both above α)
              L___________U               → UNCERTAIN (spans α)
                  U___L                   → CONTRADICTION (L > U)

Three-Valued Logic Truth Tables (from Slide 35)

AND ($\wedge$):

Key rule for AND: Any F makes the result F. Both must be T for T. Otherwise U.

OR ($\vee$):

Key rule for OR: Any T makes the result T. Both must be F for F. Otherwise U.

⚠️ Common Misconception: Students confuse which operator “dominates.” For AND, False dominates (one False makes everything False). For OR, True dominates (one True makes everything True). This is the key to Exercise 8 and the 2025 actual test question.

LNN Architecture – Syntax Tree as Network

In LNN, every logical formula is compiled into a computation graph where:

• Each node is a neuron representing a logical operator or proposition
• The structure follows the syntax tree of the formula
• Each edge passes truth bounds [L, U] (not just single values)

Example: (Whiskers ⊗ Tail ⊗ (Laser pointer → Chases)) → Cat
         (Cat ⊕ Dog) → Pet

                              Pet
                               |
                          [⊕ (OR)]
                          /       \
                        Cat       Dog
                         |
                    [→ (IMPLIES)]
                    /            \
            [⊗ (AND)]        (this is Cat)
           /    |     \
     Whiskers  Tail  [→ (IMPLIES)]
                      /          \
               Laser pointer   Chases

• $\otimes$ (circled multiply) = AND-like operation (soft conjunction)
• $\oplus$ (circled plus) = OR-like operation (soft disjunction)
• $\rightarrow$ (arrow) = Implication (if…then)

LNN Workflow (from Slides 33, 42)

Step 1: READ INPUTS
   - Known facts set bounds:
     e.g., cat is true → L_cat = 1, U_cat = 1
     e.g., ¬dog → L_dog = 0, U_dog = 0
   - Unknown propositions: L = 0, U = 1 (complete uncertainty)

Step 2: BIDIRECTIONAL MESSAGE PASSING (iterate until convergence)
   
   Upward Pass (children → parent):
   - "If dog and cat influence pet, compute pet's bounds from dog and cat"
   - Parent bounds are TIGHTENED based on children
   
   Downward Pass (parent → children):
   - "If pet is known to be true, what constraints does this put on dog and cat?"
   - Children bounds are TIGHTENED based on parent
   
   Repeat until bounds stop changing (convergence)

Step 3: READ FINAL BOUNDS
   - Inspect target neuron's [L, U]
   - Apply threshold α to classify as TRUE / FALSE / UNCERTAIN

🔄 Worked Examples – Every Computation Step

=== EXAM QUESTION TYPE 1: Interpret LNN Rule + Compute Soft AND ===

This is the most frequently tested pattern. It appears in the Sample Test 2025, Sample Test 2026, and closely matches the lecture exercises.

Worked Example 1: HeatingOn Rule (Sample Test 2025 Q2, Sample Test 2026 Q2)

Question: A smart home system uses an LNN with the rule:

$$\text{HeatingOn} \leftarrow \text{Cold} \otimes \text{AtHome}$$

(a) What does this rule represent in natural language? How is it different from a standard Boolean rule?

(b) Given Cold = 0.9, AtHome = 0.4, compute HeatingOn. Would the system activate?

Model Answer (a) – 1-2 marks:

This rule reads: “If it is cold AND someone is at home, then the heating system should be turned on.”

In standard Boolean logic, both Cold and AtHome must be strictly True (= 1) for HeatingOn to fire. The output is binary: heating is either fully ON or fully OFF.

In LNN, the $\otimes$ operator is a differentiable soft conjunction over continuous truth values in [0, 1]. It accepts partial inputs (like Cold = 0.9, AtHome = 0.4) and produces an intermediate activation (like 0.36), reflecting degrees of truth. This enables:

• Gradient-based learning of operator weights
• Nuanced outputs that reflect uncertainty
• Threshold-dependent decisions

Model Answer (b) – 1-2 marks:

Using the Product-Sum soft AND:

$$\text{HeatingOn} = \text{Cold} \times \text{AtHome} = 0.9 \times 0.4 = 0.36$$

Whether heating activates depends on the classification threshold:

• If threshold is low (e.g., $\alpha = 0.3$): HeatingOn = 0.36 > 0.3, so heating turns ON
• If threshold is high (e.g., $\alpha = 0.7$): HeatingOn = 0.36 < 0.7, so heating stays OFF

Scoring Notes from the official answer key:

• (a): 1 mark for natural language, 1 mark for explaining the difference with Boolean (the $\otimes$ operator supports continuous values and gradient learning)
• (b): 1 mark for computing the product correctly, 1 mark for mentioning threshold-dependent activation

=== EXAM QUESTION TYPE 2: LNN Bounds with OR (Safety-Critical) ===

This appeared in the Actual Mid-Semester Test S1 2025 Q2 (3 marks).

Worked Example 2: Autonomous Vehicle Alert (Actual Test 2025 Q2)

Question: An autonomous vehicle uses an LNN to decide whether to trigger a collision alert based on two conditions:

• P: “The object is very close” ($L_P = 0.8, U_P = 0.9$)
• Q: “The object is moving fast” ($L_Q = 0.3, U_Q = 0.6$)

Rule: Alert $\leftarrow$ P $\vee$ Q

Threshold $\alpha = 0.7$.

(a) Is the alert status: definitely true, definitely false, or uncertain? [1 mark]

(b) Why is using bounds (instead of a single probability) beneficial in safety-critical applications? [2 marks]

Model Answer (a):

For OR with truth bounds, we compute:

$$L_{\text{Alert}} = \max(L_P, L_Q) = \max(0.8, 0.3) = 0.8$$

$$U_{\text{Alert}} = \max(U_P, U_Q) = \max(0.9, 0.6) = 0.9$$

Now apply the threshold $\alpha = 0.7$:

$$L_{\text{Alert}} = 0.8 \ge 0.7 = \alpha$$

Since the lower bound is already above the threshold, the alert is A. Definitely True.

Why $\max$ for OR bounds? In three-valued logic, OR only needs one True input to be True. If P’s lower bound alone exceeds the threshold, then regardless of Q, the OR result must be at least that high.

Model Answer (b) – any two of the following earn full marks:

1. Expressing Uncertainty Explicitly: Bounds allow the system to represent how confident it is about a truth value. A single probability of 0.85 hides whether the system is very sure (bounds [0.84, 0.86]) or deeply uncertain (bounds [0.3, 1.0]).

2. Supporting Conservative Decision-Making: In safety-critical applications like autonomous driving, the system should err on the side of caution. If the lower bound is below the threshold, the system can choose to slow down or stop rather than take a risky action based on an overconfident point estimate.

3. Robustness to Noisy or Incomplete Data: Sensors may fail or provide noisy signals. Bounds propagate this uncertainty from inputs to outputs, letting the system know how unreliable the final decision is.

4. Better Interpretability: Engineers and operators can inspect the bounds to understand how certain the model is about its decision. This improves debugging, transparency, and trust in the AI system.

Worked Example 3: Lecture Exercise 5 – Product-Sum OR

Given: Fever (F) = 0.9, Cough (C) = 0.7

Compute: $F \vee C$ using Product-Sum

$$F \vee C = F + C - F \times C$$

$$= 0.9 + 0.7 - (0.9 \times 0.7)$$

$$= 1.6 - 0.63$$

$$= 0.97$$

Answer: A) 0.97

Worked Example 4: Lecture Exercise 6 – Nested AND then OR

Given: F = 0.9, C = 0.7, SOB = 0.5

Compute: $(C \wedge \text{SOB}) \vee F$

Step 1: Compute $C \wedge \text{SOB}$ (AND = product):

$$C \wedge \text{SOB} = 0.7 \times 0.5 = 0.35$$

Step 2: Compute $(C \wedge \text{SOB}) \vee F$ (OR = A+B-AB):

$$0.35 + 0.9 - (0.35 \times 0.9)$$

$$= 1.25 - 0.315$$

$$= 0.935$$

Answer: C) 0.935

Worked Example 5: Lecture Exercise 7 – Truth Bounds Classification

Given: $L = 0.3$, $U = 0.7$, $\alpha = 0.5$

Analysis:

• Is $L \ge \alpha$? $0.3 \ge 0.5$? No.
• Is $U \le \alpha$? $0.7 \le 0.5$? No.
• So $L < \alpha < U$ (0.3 < 0.5 < 0.7)

Answer: C) The neuron’s truth value is uncertain.

The bounds span both sides of the threshold, so we cannot classify it as definitely true or definitely false.

Worked Example 6: Lecture Exercise 8 – Three-Valued OR with Mixed Inputs

Given:

• Sharp: $L_{\text{sharp}} = 0.2$, $U_{\text{sharp}} = 0.8$
• Heavy: $L_{\text{heavy}} = 0.6$, $U_{\text{heavy}} = 1.0$
• $\alpha = 0.5$
• Rule: Dangerous $\leftarrow$ Sharp $\vee$ Heavy

Step 1: Classify each input

Heavy: $L = 0.6 \ge 0.5 = \alpha$ AND $U = 1.0 \ge 0.5 = \alpha$ $\Rightarrow$ Heavy is TRUE

Sharp: $L = 0.2 < 0.5 < 0.8 = U$ $\Rightarrow$ Sharp is UNCERTAIN

Step 2: Apply three-valued OR

From the truth table: $T \vee U = T$

Since Heavy is already TRUE, and OR only needs one True input, the result is:

Answer: A) The object is definitely dangerous.

This is a critical reasoning pattern: in OR, one TRUE input is enough to guarantee TRUE output, regardless of the other input’s uncertainty.

Worked Example 7: Lukasiewicz AND (from Slide 40)

Example 1: $x_1 = 1$, $x_2 = 0.5$

$$\text{AND}(x_1, x_2) = f\left(1 - \sum_i(1-x_i)\right) = f(1 - (0 + 0.5)) = f(0.5) = 0.5$$

Example 2: $x_1 = 0$, $x_2 = 0$

$$\text{AND}(x_1, x_2) = f(1 - (1 + 1)) = f(-1) = \max(0, -1) = 0$$

Example 3: Lukasiewicz OR from Slide 41: $x_1 = 1$, $x_2 = 0.5$

$$\text{OR}(x_1, x_2) = f\left(\sum_i x_i\right) = f(1 + 0.5) = f(1.5) = \min(1, 1.5) = 1$$

Example 4: Lukasiewicz OR: $x_1 = 0$, $x_2 = 0$

$$\text{OR}(x_1, x_2) = f(0 + 0) = f(0) = 0$$

Worked Example 8: Comparing All Three T-Norms

Given: $A = 0.9$, $B = 0.4$

Observations:

• Product AND gives the lowest value (multiplication shrinks things fast)
• Lukasiewicz AND can hit exactly zero even when inputs are positive (if $A + B < 1$)
• Godel AND is the simplest (just take the minimum) but is not fully smooth

⚖️ Trade-offs & Comparisons

Boolean Logic vs Fuzzy Logic vs LNN

Why Not Just Use a Regular Neural Network?

Product vs Lukasiewicz vs Godel T-Norms

🏗️ Design Question Framework

If the exam asks “Design an LNN-based system for [scenario]”:

WHAT

Define propositions and their meanings. Example:

• P: “The road is wet” (truth value from rain sensor)
• Q: “Visibility is low” (truth value from camera)
• Conclusion: SlowDown $\leftarrow$ P $\vee$ Q

WHY LNN?

• Inputs are uncertain/partial (sensor readings, not binary)
• Need explainability (safety-critical application)
• Want gradient-based learning to tune operator weights
• Bounds [L,U] allow conservative decision-making

HOW

1. Assign truth values or bounds to input propositions
2. Choose a t-norm (Product-Sum for exam purposes)
3. Build the syntax tree as a computation graph
4. Run bidirectional message passing
5. Read output bounds, apply threshold

TRADE-OFF

• Product t-norm: smooth but shrinks fast with many inputs
• Higher threshold $\alpha$ = more conservative (fewer false positives, more false negatives)
• Lower threshold $\alpha$ = more aggressive (fewer false negatives, more false positives)
• Bounds give safety guarantees but add computational cost

EXAMPLE

Plug in specific numbers and compute step-by-step.

📝 All Exam Questions with Full Model Answers

— Sample Test S1 2025, Question 2 [2 marks] —

(a) What does HeatingOn $\leftarrow$ Cold $\otimes$ AtHome represent in natural language, and how is it different from a standard Boolean rule? [1 mark]

Model Answer:

This rule reads: “If it is cold and someone is at home, then turn on the heating system.”

In standard Boolean logic, this would require both inputs to be strictly True (1) to turn on the heating. In an LNN, the $\otimes$ operator allows soft conjunction over continuous truth values. It supports partial inputs (like 0.4 or 0.9), yielding an intermediate activation that reflects uncertainty and permits gradient-based learning.

(b) Given Cold = 0.9, AtHome = 0.4, compute HeatingOn and discuss activation. [1 mark]

Model Answer:

Using soft-logic AND (Product-Sum), HeatingOn = Cold $\times$ AtHome = $0.9 \times 0.4 = 0.36$.

Depending on the classification threshold, the system may or may not trigger the heating. If the threshold is low (e.g., 0.3), heating will be turned on. If it is high (e.g., 0.7), it may stay off.

— Actual Mid-Semester Test S1 2025, Question 2 [3 marks] —

(a) P: $L_P = 0.8$, $U_P = 0.9$; Q: $L_Q = 0.3$, $U_Q = 0.6$. Alert $\leftarrow$ P $\vee$ Q. With $\alpha = 0.7$, is alert definitely true, definitely false, or uncertain? [1 mark]

Model Answer:

Lower Bound: $L_{\text{Alert}} = \max(L_P, L_Q) = \max(0.8, 0.3) = 0.8$

Upper Bound: $U_{\text{Alert}} = \max(U_P, U_Q) = \max(0.9, 0.6) = 0.9$

Since $\alpha = 0.7 < 0.8 = L_{\text{Alert}}$, both bounds are above the threshold.

Classification: A. Definitely true.

(b) Why are bounds beneficial in safety-critical applications? [2 marks]

Model Answer (any two for full marks):

1. Expressing Uncertainty Explicitly: Bounds represent how confident the system is in a truth value, unlike a single probability that hides uncertainty.

2. Supporting Conservative Decision-Making: In autonomous driving, if the lower bound is below the threshold, the system can slow down or stop rather than take risky action based on overconfident estimates.

3. Robustness to Noisy/Incomplete Data: Sensors may fail or provide noisy signals. Bounds propagate uncertainty from inputs to outputs, tracking how unreliable the final decision is.

4. Better Interpretability: Engineers can inspect bounds to understand model certainty, improving debugging, transparency, and trust.

— Sample Test S1 2026, Question 2 [4 marks] —

(a) What does HeatingOn $\leftarrow$ Cold $\otimes$ AtHome represent in natural language? How is it different from a standard Boolean rule? [2 marks]

Model Answer:

This rule reads: “If it is cold and someone is at home, then turn on the heating system.” [1 mark]

In standard Boolean logic, this would require both inputs to be strictly True (1) to turn on the heating. In an LNN, the $\otimes$ operator allows soft conjunction over continuous truth values. It supports partial inputs (like 0.4 or 0.9), yielding an intermediate activation that reflects uncertainty and permits gradient-based learning. [1 mark]

(b) Given Cold = 0.9, AtHome = 0.4, compute HeatingOn. Would the system activate heating? [2 marks]

Model Answer:

Using soft-logic AND (e.g., Product-Sum), the output HeatingOn will reflect the multiplication of the two values: $0.9 \times 0.4 = 0.36$. [1 mark]

Depending on the classification threshold, the system may or may not trigger the heating. If the threshold is low (e.g., 0.3), heating will be turned on. If it is high (e.g., 0.7), it may stay off. [1 mark]

— Actual Mid-Semester Test S1 2025, Question 5 [3 marks] —

(This tests fuzzy/soft logic, closely related to LNN)

Question: Consider the rule: IF STRONG AND HEAVY THEN HAMMER_THROWER. Contrast traditional logic vs fuzzy logic.

Model Answer:

With classic logic, both STRONG and HEAVY would be either True or False (by some criteria, like how much they can benchpress, or the athlete’s weight in kg). If, and only if, both criteria are true, then the individual is judged suitable for hammer throwing; else, not.

With Fuzzy Logic, membership functions map both STRONG and HEAVY to values in [0,1]. Some level of strength maps to $\mu_s$, and some bodyweight maps to $\mu_h$. The AND function might be implemented as $\min(\mu_s, \mu_h)$, or as the product $\mu_s \times \mu_h$. The THEN might have strength 1.0 or something less as a further multiplier. The final result is a suitability score anywhere in [0,1].

🔄 OR Bounds Computation – Deep Dive

This is the most likely new question type for the 2026 actual test, since it appeared in the 2025 actual test. Here is a complete reference.

Computing OR Bounds

For $C \leftarrow A \vee B$ with bounds $A = [L_A, U_A]$ and $B = [L_B, U_B]$:

$$L_C = \max(L_A, L_B)$$ $$U_C = \max(U_A, U_B)$$

Intuition: OR only needs ONE input to be true. The lower bound of the OR output is at least as high as the highest lower bound of any input.

Computing AND Bounds

For $C \leftarrow A \wedge B$ with bounds $A = [L_A, U_A]$ and $B = [L_B, U_B]$:

$$L_C = \max(0, L_A + L_B - 1) \quad \text{(Lukasiewicz)}$$ $$U_C = \min(U_A, U_B) \quad \text{(Godel)}$$

Intuition: AND needs ALL inputs to be true. The upper bound of the AND output cannot exceed the smallest upper bound of any input.

Practice: Multiple OR-Bound Scenarios

🌐 English Expression Tips

Key Phrases for LNN Questions

Explaining what LNN is:

• “A Logic Neural Network is a neural-symbolic approach where the network structure mirrors a logical syntax tree, with each neuron representing a logical connective.”
• “LNN combines the interpretability of symbolic logic with the learning capability of neural networks.”

Explaining the difference from Boolean:

• “Unlike Boolean logic, which requires inputs to be strictly 0 or 1, LNN operates over continuous truth values in the interval [0, 1].”
• “The $\otimes$ operator is a differentiable soft conjunction that supports partial truth values, enabling gradient-based learning.”

Explaining truth bounds:

• “Each proposition maintains a lower bound L and upper bound U, expressing the system’s confidence interval for that proposition’s truth value.”
• “Bounds allow the system to distinguish between ‘probably true’ and ‘definitely true,’ which is critical in safety-sensitive applications.”

Explaining why bounds matter in safety-critical systems:

• “In autonomous driving, an overconfident single-point estimate could lead to dangerous decisions; bounds explicitly quantify the system’s uncertainty.”
• “If the lower bound falls below the decision threshold, the system can choose a conservative action rather than risking an unsafe response.”

Commonly Confused Terms

✅ Self-Test Checklist

Computation Skills

• Can I compute Product-Sum AND for any two values? (e.g., $0.9 \times 0.4 = 0.36$)
• Can I compute Product-Sum OR for any two values? (e.g., $0.9 + 0.7 - 0.63 = 0.97$)
• Can I compute nested operations? (e.g., $(C \wedge \text{SOB}) \vee F$)
• Can I compute Lukasiewicz AND and OR? (e.g., $\max(0, 0.9+0.4-1) = 0.3$)
• Can I compute OR bounds from two [L,U] pairs? (e.g., $\max(L_P, L_Q)$)
• Can I classify truth bounds as TRUE/FALSE/UNCERTAIN given $\alpha$?

Conceptual Understanding

• Can I explain in 2 sentences why LNN uses differentiable operators instead of Boolean AND?
• Can I explain the difference between LNN and standard Boolean logic?
• Can I explain why truth bounds [L,U] are useful in safety-critical applications? (Name at least 2 reasons)
• Do I know the three-valued logic truth tables for AND and OR?
• Can I explain upward pass vs downward pass?
• Can I draw the LNN computation graph for a simple rule?
• Do I understand the difference between LNN and fuzzy logic? (Name 3 differences)

Exam Readiness

• Can I write a full answer for “interpret this LNN rule in natural language”?
• Can I write a full answer for “compute HeatingOn = Cold $\otimes$ AtHome with values”?
• Can I write a full answer for “compute OR bounds for autonomous vehicle alert”?
• Can I write a full answer for “why are bounds useful in safety-critical systems”?
• Have I memorized the Product-Sum formulas: AND = $A \times B$, OR = $A + B - AB$, NOT = $1 - A$?

🎯 Exam Strategy – Quick Reference Card

If the question asks “What does this LNN rule mean in natural language?”:

1. Translate the formula into an English sentence
2. State that Boolean requires strictly True/False inputs
3. State that LNN’s $\otimes$ operator uses differentiable soft conjunction over [0,1]
4. Mention that this enables gradient-based learning and handles uncertainty

If the question asks “Compute the truth value”:

1. Identify which t-norm to use (Product-Sum unless stated otherwise)
2. Show the formula: AND = $A \times B$ or OR = $A + B - AB$
3. Plug in numbers and compute step by step
4. Discuss how the threshold determines the final decision

If the question asks about truth bounds:

1. State the bounds for each input
2. Compute the output bounds using the appropriate rule (max for OR, min for AND upper)
3. Compare with threshold $\alpha$
4. Classify as TRUE ($L \ge \alpha$), FALSE ($U \le \alpha$), or UNCERTAIN ($L < \alpha < U$)

If the question asks “Why are bounds useful in safety-critical applications?”:

Pick two from: (1) express uncertainty explicitly, (2) support conservative decisions, (3) robust to noisy sensors, (4) better interpretability for engineers

Knowledge Representation Methods (W3L1)

🎯 考试重要度

🟡 中频 | Week 3 Lecture 1 (44 slides) | 为后续 KG Embeddings (Sample Test Q3)、MYCIN (W4L1) 的理论基础

Why study this? This lecture defines ALL five KR methods tested in this course: Symbolic Logic, Semantic Networks, Frames, Rule-Based Systems, and Knowledge Graphs. Comparison questions across these methods are a natural exam question type. Understanding each method’s strengths and weaknesses is essential for design-type questions. The exercises from this lecture test inference reasoning – a skill required across Q1 (logic), Q3 (KG embeddings), and Q5 (MYCIN).

📖 核心概念（Core Concepts）

🧠 费曼草稿（Feynman Draft）

The Filing Cabinet Analogy

Imagine you just got hired to organize ALL the knowledge in a hospital – every disease, every symptom, every treatment, every patient record. You need the knowledge organized so that a robot doctor can not only look things up but also reason about new patients it has never seen before. The question is: what filing system do you use?

It turns out there is no single best system. Different filing systems are good at different things. This lecture covers five of them.

System 1: Symbolic Logic – The Mathematician’s Notebook

You write everything as precise mathematical statements:

• “For all x, if x has flu, then x has a fever”: $\forall x\ (\text{Flu}(x) \rightarrow \text{HasSymptom}(x, \text{Fever}))$
• “If a patient has fever AND cough, then likely diagnosis is flu”: $\forall x\ (\text{HasSymptom}(x, \text{Fever}) \wedge \text{HasSymptom}(x, \text{Cough}) \rightarrow \text{LikelyDiagnosis}(x, \text{Flu}))$

Strengths: absolutely precise, supports formal proof. Weakness: extremely rigid – try expressing “70% chance of flu” in pure logic!

System 2: Semantic Networks – The Mind Map

Think of a giant mind map on a whiteboard. Each sticky note is a concept (Cat, Mammal, Animal, Fur), and you draw labeled arrows between them:

Cat ──is-a──► Mammal ──is-a──► Animal
Cat ──has──► Fur
Mammal ──has-property──► Warm-blooded

Now here’s the magic: because Cat is-a Mammal, and Mammal has-property Warm-blooded, the system can infer that Cat is Warm-blooded – even though you never wrote that explicitly. This is called transitive inheritance.

Toy example: Given these three facts:

1. “Dog is-a Mammal”
2. “Mammal is-a Animal”
3. “Mammal has-property Warm-blooded”

The system infers: “Dog is-a Animal” (transitive IS-A) and “Dog has-property Warm-blooded” (property inheritance).

System 3: Frames – The Object-Oriented Database

Imagine describing a car using a form you fill out:

Each frame is like an object in programming – it has attributes (slots) and values (fillers). Frames can do four clever things:

1. Default values: If you create a new “Dog” frame and don’t specify legs, it defaults to 4 (inherited from “Mammal” frame)
2. Inheritance: A “Dog” frame inherits “Has Hair = True” from the “Mammal” frame
3. Slot constraints: A “Student” frame requires Age > 5
4. Procedural attachment: Accessing the “Check-in Time” slot of a “Hotel Reservation” frame automatically triggers sending a confirmation email

System 4: Rule-Based Systems – The Decision Flowchart

You encode every decision as an IF-THEN rule:

R1: IF Fever AND Cough                    THEN Possible Diagnosis = Flu
R2: IF Fever AND Joint Pain AND Travel     THEN Possible Diagnosis = Dengue Fever
R3: IF Cough AND Difficulty Breathing      THEN Possible Diagnosis = Pneumonia

Patient comes in with Fever + Cough + Joint Pain + Recent Travel? R1 fires (Flu) and R2 fires (Dengue Fever). The system considers both.

This is the simplest form – it’s transparent (you can trace exactly which rules fired) but brittle (you need a rule for every possible situation, and they don’t generalize).

System 5: Knowledge Graphs – The Fact Encyclopedia

You store millions of specific facts as triples:

(Albert Einstein, Born In, Germany)
(Albert Einstein, Discovered, Theory of Relativity)
(Theory of Relativity, Related To, Physics)

The power is in graph traversal for inference: if you ask “Did Einstein contribute to Physics?”, the system walks the graph: Einstein → Discovered → Theory of Relativity → Related To → Physics. Yes!

⚠️ Common Misconception: Students often think these five methods are “versions” of the same thing (1.0, 2.0, etc.). They are NOT. They are five different paradigms – each stores knowledge in a fundamentally different way and supports different kinds of reasoning. The slide explicitly states: “They are different KR paradigms, not different types of Knowledge Graphs.”

⚠️ Common Misconception: Semantic Networks and Knowledge Graphs look similar (both are graphs), but they differ in standardization and scale. Semantic Networks have no unified standard and are typically small/domain-specific (1960s–1980s research). Knowledge Graphs use standardized RDF triples and are designed for web-scale (billions of facts, 2000s–present).

💡 Core Intuition: KR is about choosing which “filing system” to organize knowledge – as logic, mind maps, forms, rules, or fact graphs – so machines can reason, not just store.

📐 正式定义（Formal Definition）

What is Knowledge Representation?

Definition (from slides): Knowledge Representation (KR) refers to the methods used in AI to store, retrieve, and handle knowledge to enable intelligent reasoning.

Why do we need KR?

• Bridges raw data and intelligent decision-making
• Allows AI to reason logically and infer new facts
• Enables knowledge-driven applications (expert systems, search engines, autonomous robots, chatbots)

Five Key Requirements of KR

Case Study from slides: Self-Driving Car

• Expressiveness → represents road conditions, traffic signals, vehicle movement
• Computational Efficiency → processes sensor data in real-time for immediate decisions
• Scalability → expands knowledge of new routes and driving patterns
• Interpretability → AI must explain why it brakes or changes lanes
• Modifiability → updates driving models based on new road conditions

Structured vs Unstructured Knowledge

Examples of Structured: Relational databases (SQL), Knowledge Graphs (Google KG), Ontologies (medical taxonomy)

Examples of Unstructured: News articles, research papers, videos, images, audio recordings, conversations, emails

Symbolic Logic in KR

Definition: Represents knowledge using formal symbols and logical expressions. Used for reasoning, inference, and formal verification.

Two types used in KR:

• Propositional Logic (PL) – simple true/false statements
• First-Order Logic (FOL) – allows relationships between entities with quantifiers

FOL Rules Example (Medical Diagnosis):

• $\forall x\ (\text{Flu}(x) \rightarrow \text{HasSymptom}(x, \text{Fever}))$ – “If a patient has the flu, they will have a fever”
• $\forall x\ (\text{HasSymptom}(x, \text{Fever}) \wedge \text{HasSymptom}(x, \text{Cough}) \rightarrow \text{LikelyDiagnosis}(x, \text{Flu}))$ – AI can infer from known symptoms to diagnose patients

Semantic Networks – Formal Structure

A graph-based KR where:

• Nodes (Entities/Concepts): represent objects, ideas, or concepts (e.g., “Cat”, “Mammal”, “Animal”)
• Edges (Relationships/Connections): define how entities are related (e.g., “is-a”, “has-part”, “related-to”)

Two key inference mechanisms:

1. Hierarchical Reasoning (IS-A Inference): Given “Cat → is-a → Mammal” and “Mammal → is-a → Animal”, AI infers “Cat is an Animal” via transitive inheritance

2. Property Inheritance: Given “Mammal → has-property → Warm-blooded” and “Dog → is-a → Mammal”, AI infers “Dog is warm-blooded” (inherits properties from parent)

Strengths of Semantic Networks:

1. Natural Representation – mimics human thought; relationships are intuitive and visually clear
2. Supports Logical Inference – AI can deduce new facts through IS-A and HAS-PROPERTY relationships
3. Efficient Knowledge Retrieval – graph structures allow fast lookups using connected nodes

Weaknesses of Semantic Networks:

1. Can Become Too Complex – large networks with millions of nodes can be hard to manage
2. No Standardized Representation – different AI models use different graph structures; integration is difficult
3. Poor Handling of Uncertainty – assumes relationships are deterministic (e.g., “Birds can fly” – but what about penguins?)

Frames – Formal Structure

A frame is a structured representation that groups related information about an entity into a slot-filler structure.

• A frame = concept/object
• A slot = attribute/property
• A filler = value for that slot

Frame-Based Reasoning (four mechanisms):

1. Default Values: If a slot is empty, AI uses default knowledge. Example: Frame Dog, Slot Has legs → Default value = 4. AI infers a newly introduced dog has 4 legs unless specified otherwise.

2. Inheritance (Frame Hierarchies): Frames inherit attributes from higher-level frames (similar to OOP). Example: Frame Mammal → Has Hair = True; Frame Dog (inherits from Mammal) → Has Hair = True.

3. Slot Constraints & Conditions: Some slots have restrictions on valid values. Example: Frame Student, Slot Age → Constraint: Must be > 5 years old.

4. Procedural Attachment: Some slots trigger actions when accessed. Example: Frame Hotel Reservation, Slot Check-in Time → Action: Send confirmation email.

Strengths of Frames:

1. Structured & Organized – groups related knowledge into slot-filler structures for efficient retrieval
2. Inheritance and Default Reasoning – infers missing values using defaults and hierarchical inheritance
3. Procedural Knowledge – slots can trigger actions (procedural attachments)
4. Easy to Update & Modify – slots and fillers can be modified dynamically

Weaknesses of Frames:

1. Rigid Structure & Limited Flexibility – struggle with ambiguous or novel cases (e.g., a “Vehicle” frame might not account for futuristic self-driving cars)
2. Poor Handling of Uncertainty – assume knowledge is complete; difficult to reason with probabilities
3. Hard to Scale for Large Knowledge Bases – grow complex as entities and slots increase
4. Limited Logical Reasoning – do not perform deep logical deductions (can store “All birds can fly” but don’t automatically reason exceptions like penguins)

Rule-Based Systems – Formal Structure

A Rule-Based System (RBS) represents knowledge as a set of IF-THEN rules that trigger actions when conditions are met.

Structure: IF (Condition) → THEN (Action/Conclusion). AI checks facts and applies the appropriate rule.

Strengths:

1. Transparent and Explainable – every decision is based on clear, human-readable IF-THEN rules
2. Easy to Implement for Well-Defined Problems – works effectively in structured domains with known rules
3. Works Without Large Training Data – does not require massive datasets (unlike ML)

Weaknesses:

1. Hard to Scale with Complex Knowledge – managing thousands of IF-THEN rules becomes difficult
2. Poor Adaptability to New Situations – cannot generalize beyond predefined rules
3. Requires Expert Knowledge to Define Rules – rules must be handcrafted by domain experts

Knowledge Graphs – Formal Structure

A KG is a graph-based representation that connects entities (nodes) with relationships (edges) and properties.

Components:

• Nodes = Entities/Subjects (people, places, objects)
• Edges = Relationships/Predicates
• Properties = Attributes of entities or relations

RDF Triple format: (Subject, Predicate, Object) = (Head, Relation, Tail)

Four types of KG inference (from slides):

1. Transitive Inference: $(A \rightarrow B, B \rightarrow C) \Rightarrow (A \rightarrow C)$. Example: “Einstein discovered Theory of Relativity” + “Theory of Relativity is part of Physics” ⇒ “Einstein contributed to Physics”
2. Relationship Expansion: Identify hidden connections. Example: if two lectures are taught by the same professor, infer a collaboration link
3. Entity Disambiguation: Distinguish entities with similar names. Example: “Apple (Company)” vs. “Apple (Fruit)”
4. Question Answering: Retrieve structured answers. Example: “Who invented the telephone?” → Alexander Graham Bell (from graph relations)

Strengths of Knowledge Graphs:

1. Highly Structured & Interpretable – provides clearly defined relationships between entities
2. Enables Inference & Knowledge Discovery – infer missing knowledge based on known relationships
3. Scalable for Large-Scale KR – works well with millions of facts and relationships
4. Supports Multi-Domain Knowledge Integration – combine medical, scientific, business knowledge into one system

Weaknesses of Knowledge Graphs:

1. Incomplete Knowledge & Data Sparsity – if information is missing, AI cannot infer accurate answers
2. High Maintenance & Complexity – requires constant updates to add new entities and relationships

🔄 机制与推导（How It Works）

How Semantic Network Inference Works – Step by Step

Given knowledge:
  Cat ──is-a──► Mammal ──is-a──► Animal
  Mammal ──has-property──► Warm-blooded
  Cat ──has──► Fur

Step 1: Query "Is Cat an Animal?"
  Traverse: Cat → is-a → Mammal → is-a → Animal
  Answer: YES (transitive IS-A inference)

Step 2: Query "Is Cat warm-blooded?"
  Cat → is-a → Mammal → has-property → Warm-blooded
  Answer: YES (property inheritance)

Step 3: Query "Does Dog have Fur?"
  Dog → is-a → Mammal (known)
  Mammal ──has──► ? (no "has Fur" on Mammal)
  Answer: CANNOT INFER (Fur is a property of Cat specifically, 
          not inherited through Mammal)

How Frame Reasoning Works – Step by Step

Scenario (Exercise 3 from slides): An AI healthcare assistant uses Frames.

Patient Alice reports: fever and headache.

Reasoning process:

1. Slot matching: Alice’s symptoms (Fever, Headache) match Malaria’s Common Symptoms (Fever, Headache, Chills) – 2 out of 3 match
2. Cross-frame inference: Alice’s Recent Travel = “Tropical regions” matches Malaria’s Transmission Risk = “High in tropical regions”
3. Default/constraint check: Alice has no travel vaccines (Vaccination History slot) and Malaria’s Prevention = Vaccination → increased susceptibility
4. Conclusion: Malaria flagged as potential diagnosis

How Rule-Based Systems Work – Step by Step

Scenario (Exercise 4 from slides): Fire detection system.

Current sensor readings: Temperature = 85C, Smoke = YES, Carbon Monoxide = Safe, Sprinklers = NO

Forward chaining:

1. Check R1: Temperature (85) > 60C ✅ AND Smoke Detected ✅ → Fire Alarm triggered
2. Check R2: Temperature (85) > 80C ✅ → Emergency Evacuation triggered
3. Check R3: Carbon Monoxide = Safe ❌ → R3 does NOT fire
4. Check R4: Sprinklers = NO ❌ → R4 does NOT fire

Final actions: Trigger Fire Alarm (R1) + Trigger Emergency Evacuation (R2)

How Knowledge Graph Inference Works – Step by Step

Scenario (Exercise 5 from slides): Historical figures KG.

Query: “Did Isaac Newton’s discoveries influence Albert Einstein?”

Graph traversal:

Newton ──Discovered──► Law of Gravity
                            │
                      Influenced ▼
                  Theory of Relativity ◄──Developed── Einstein

Path: Newton → Discovered → Law of Gravity → Influenced → Theory of Relativity ← Developed ← Einstein

Answer: YES – Newton’s Law of Gravity influenced Einstein’s Theory of Relativity. The graph does not connect them directly, but AI can infer the relationship by traversing the graph.

⚖️ 权衡分析（Trade-offs & Comparisons）

Complete KR Methods Comparison Table

Differences Between KR Methods (from slides)

Key distinction (from slides):

• Semantic Network: Early graph-based KR using nodes and links. No unified standard. Small/domain-specific.
• Knowledge Graph: A large-scale, standardized graph using RDF triples. Designed for web-scale.
• KGs can be viewed as a modern, large-scale implementation and extension of the original Semantic Network concept.

When to Choose Which?

KR Landscape (from slides)

                Knowledge Representation
                         │
          ┌──────────────┼──────────────┐
     Logic-based     Graph-based    Structured/Rule-based
          │           │       │           │          │
    Symbolic     Semantic   Knowledge   Frames   Rule-based
     Logic      Networks    Graphs               Systems

Key takeaway from slides: “There is no single best KR method. Different methods have different strengths in representation, inference, scalability, and interpretability. In practice, AI systems may combine multiple KR methods to solve real-world problems.”

🏗️ 设计题答题框架

Prompt type: “Compare different KR methods and explain which you would choose for [scenario]. Justify your choice.”

WHAT

Identify which KR methods are relevant:

• “For this scenario, I would compare Semantic Networks, Frames, Rule-Based Systems, and Knowledge Graphs as candidate approaches…”
• “The primary representation would be a Knowledge Graph with an ontology providing the schema…”

WHY

Justify based on the 5 KR requirements:

• Expressiveness: “A KG can represent diverse entity types and relationship types via flexible triples”
• Computational Efficiency: “Rule-based systems offer fast decision-making via direct rule matching”
• Scalability: “KGs scale to billions of triples; frames and rule-based systems do not”
• Interpretability: “Rule-based systems are the most transparent – every conclusion traces to a human-readable rule”
• Modifiability: “KGs can be updated by adding new triples without restructuring the entire system”

HOW

Describe the architecture:

1. Choose the primary KR method and explain its structure
2. Show how knowledge is stored (e.g., as triples, as frames, as rules)
3. Explain how inference works (e.g., graph traversal, property inheritance, forward chaining)

TRADE-OFF

Discuss what you sacrifice:

• “Semantic Networks are intuitive but lack standardization and cannot handle uncertainty”
• “Rule-Based Systems are transparent but brittle and hard to scale beyond ~10K rules”
• “Frames are structured but rigid and cannot reason with probabilities”
• “KGs are scalable but may be incomplete and require maintenance”

EXAMPLE

Walk through a concrete scenario:

• “A medical AI receives symptom data. Using a KG: (Patient, hasSymptom, Fever), (Patient, hasSymptom, Cough). Graph traversal finds: (Flu, hasSymptom, Fever), (Flu, hasSymptom, Cough). Match! Suggest Flu as possible diagnosis.”

📝 历年真题 + 课堂练习（Exercises 1–5 from Slides）

Exercise 1 – Structured vs Unstructured Knowledge

Question: Which of the following is an example of structured knowledge?

A) A collection of handwritten medical prescriptions. B) A database storing customer purchase histories. C) A video recording of a classroom lecture. D) A set of research papers in PDF format.

Exercise 2 – Semantic Network Inference

Question: Which of the following best demonstrates inference in a Semantic Network?

A) A chatbot randomly generating responses. B) AI deducing that “whales are mammals” based on an “is-a” relationship. C) A search engine ranking web pages based on popularity. D) A neural network recognizing images of cats.

Exercise 3 – Frame-Based Reasoning (Healthcare)

Scenario: An AI-powered healthcare assistant uses Frames to manage patient medical records and suggest possible diagnoses.

Patient Alice reports: fever and headache.

Frame: Patient	Slot	Filler
Alice	Age	25
	Symptoms	Fever, Headache
	Family History	None
	Recent Travel	Tropical regions (2 weeks ago)
	Vaccination History	No recent travel vaccines

Frame: Malaria	Slot	Filler
Malaria	Common Symptoms	Fever, Headache, Chills
	Transmission Risk	High in tropical regions
	Prevention	Vaccination

Question: What is the most likely reason the AI flags Malaria as a potential diagnosis?

A) Alice has a family history of malaria. B) Malaria is common in all patients with pain in the lungs. C) Malaria is common in Age from 20 to 30. D) Alice recently traveled to a high-risk area and shows matching symptoms.

Exercise 4 – Rule-Based System (Fire Detection)

Scenario: Rule-Based AI system for fire detection in a smart building.

Rule ID	IF Condition	THEN Conclusion
R1	Temperature > 60C AND Smoke Detected	Trigger Fire Alarm
R2	Temperature > 80C	Trigger Emergency Evacuation
R3	Carbon Monoxide > Safe Limit	Alert Building Manager
R4	Sprinklers Activated AND Smoke Detected	Confirm Fire

Current Sensor Readings: Temperature = 85C, Smoke Detected = YES, Carbon Monoxide = Safe, Sprinklers Activated = NO

Question: What actions will the AI take?

A) Trigger Fire Alarm and Emergency Evacuation. B) Only Alert the Building Manager. C) Only Trigger the Fire Alarm. D) Confirm Active Fire and Trigger Evacuation.

Exercise 5 – Knowledge Graph Inference (Historical Figures)

Scenario: An AI system uses a Knowledge Graph for historical figures and scientific discoveries.

Entity (Node)	Relation (Edge)	Entity (Node)
Isaac Newton	Discovered	Law of Gravity
Law of Gravity	Related To	Physics
Albert Einstein	Contributed To	Physics
Albert Einstein	Developed	Theory of Relativity
Theory of Relativity	Related To	Gravity
Theory of Relativity	Influenced By	Law of Gravity

Question: Did Isaac Newton’s discoveries influence Albert Einstein?

A) No, no direct link between Newton and Einstein. B) Yes, Einstein contributed to Physics, and Physics includes Gravity. C) Yes, Newton discovered Law of Gravity, and Theory of Relativity was influenced by it. D) No, Einstein worked on different theories.

🌐 英语表达要点（English Expression）

Defining KR Methods

"Knowledge Representation refers to the methods used in AI to store,
 retrieve, and handle knowledge to enable intelligent reasoning."

"A Semantic Network is a graph-based KR method where nodes represent
 concepts and edges represent relationships such as IS-A and HAS-PROPERTY."

"A Frame is a structured representation that groups related information
 about an entity into a slot-filler structure, enabling inheritance
 and default reasoning."

"A Rule-Based System encodes domain knowledge as a set of IF-THEN
 production rules, providing transparent and explainable decision-making."

"A Knowledge Graph is a graph-based representation that connects
 entities (nodes) with relationships (edges), storing facts as
 RDF triples in the form (Subject, Predicate, Object)."

Comparing Methods

"While Semantic Networks represent knowledge as interconnected concept
 nodes, Knowledge Graphs use standardized RDF triples and are designed
 for web-scale applications with billions of facts."

"Unlike Rule-Based Systems, which require manually crafted IF-THEN rules,
 Knowledge Graphs can be populated semi-automatically using NLP techniques
 such as Named Entity Recognition and Relation Extraction."

"Frames organize knowledge similarly to objects in programming, with
 slots (attributes) and fillers (values), whereas Semantic Networks
 focus on the relationships between concepts rather than their attributes."

"The fundamental trade-off between Rule-Based Systems and Knowledge Graphs
 is interpretability versus scalability: rules are transparent but brittle
 at scale, while KGs scale to billions of facts but paths can be opaque."

Discussing Requirements

"A good KR system must balance five requirements: expressiveness,
 computational efficiency, scalability, interpretability, and modifiability."

"The choice of KR method depends on the application's priorities --
 for example, medical diagnosis systems prioritize interpretability,
 while web search engines prioritize scalability."

易错词汇

✅ 自测检查清单

• Can I define Knowledge Representation and its purpose in one sentence?
• Can I list and explain the 5 key requirements of KR (Expressiveness, Computational Efficiency, Scalability, Interpretability, Modifiability)?
• Can I explain the difference between Structured and Unstructured Knowledge with examples?
• Can I describe how Symbolic Logic (PL + FOL) is used in KR?
• Can I draw a Semantic Network and explain IS-A inference and property inheritance?
• Can I name 3 strengths and 3 weaknesses of Semantic Networks?
• Can I describe a Frame with its slots and fillers, and explain the 4 reasoning mechanisms (defaults, inheritance, constraints, procedural attachment)?
• Can I name 4 strengths and 4 weaknesses of Frames?
• Can I write an IF-THEN rule and trace forward chaining through a set of rules?
• Can I name 3 strengths and 3 weaknesses of Rule-Based Systems?
• Can I explain Knowledge Graph structure (nodes, edges, properties) and write RDF triples?
• Can I name the 4 types of KG inference (transitive, relationship expansion, entity disambiguation, QA)?
• Can I name 4 strengths and 2 weaknesses of Knowledge Graphs?
• Can I compare all five KR methods in a table (core idea, representation, reasoning, strengths, weaknesses)?
• Can I explain the KR Landscape diagram showing logic-based, graph-based, and structured/rule-based categories?
• Can I solve all 5 exercises from the lecture slides?

Cross-references:

• For Symbolic Logic in depth, see Propositional Logic & FOL chapter
• For Knowledge Graphs, TransE, and RAG in depth, see KG for AI chapter
• For Expert Systems and MYCIN, see MYCIN chapter

Knowledge Graphs for AI – Construction, Inference & TransE (W3L2)

🎯 考试重要度

🟠 高频 | Week 3 Lecture 2 (56 slides) | Sample Test Q3 (2 marks) 直接考查 KG Embeddings 计算

Exam alert: Q3 asks you to explain Knowledge Graph Embeddings and give a common KG inference task. You must know the TransE formula and be able to compute L1 distances by hand. Every past test asks about entity/relation embeddings in KG completion. Every test asks about TransE (h+r≈t) and its scoring function. Link prediction example: (Einstein, bornIn, ?) → Germany.

📖 核心概念（Core Concepts）

🧠 费曼草稿（Feynman Draft）

Part 1: From Semantic Networks to Knowledge Graphs

Imagine you drew a concept map on a napkin – “Einstein discovered Relativity”, “Relativity is related to Physics”. That napkin is essentially a Semantic Network: a small, informal web of concepts and relationships. Now imagine Google took that idea and built it with billions of facts, standardized formats (RDF triples), and web-scale infrastructure. That is a Knowledge Graph.

Key insight from slides: “Knowledge graphs can be viewed as a modern, large-scale implementation and extension of the original semantic network concept.”

Example showing the difference:

• Semantic Network: Einstein –discovered–> Theory of Relativity; Theory of Relativity –related to–> Physics
• Knowledge Graph: (Albert Einstein, discovered, Theory of Relativity); (Theory of Relativity, relatedTo, Physics) – standardized triple format

Part 2: Expert Systems – The Rule-Following Doctor

Imagine a very obedient robot doctor. Before seeing any patient, human experts sat down and wrote every diagnosis rule on index cards:

IF patient has fever AND bacterial infection
THEN recommend antibiotic treatment

The robot has three parts:

1. Knowledge Base – the box of index cards (rules + facts)
2. Inference Engine – the process of matching current symptoms to rules and firing them
3. User Interface – how the doctor talks to patients

MYCIN (1970s) was a real expert system for diagnosing bacterial infections. It outperformed some human doctors! But it could only handle what its rules covered – it could not learn, adapt, or handle situations no one had written rules for.

Part 3: Ontologies – The Grammar Book for Knowledge

Think of an ontology as a grammar book for knowledge. It does not tell you what specific facts are true – it tells you what kinds of facts are allowed.

A medical ontology might say:

• “Disease” is a class. “Medicine” is a class.
• A Medicine treats a Disease (this kind of relationship is valid).
• A treatment must be associated with at least one disease (constraint).

Now compare:

• Ontology says: “Medicine treats Disease” (what kinds of statements are valid – schema + rules)
• Knowledge Graph says: “(Aspirin, treats, Headache)” (what specific facts are true – data)

An ontology is like the grammar book; a KG is like the encyclopedia written following that grammar.

Five components of an Ontology:

1. Concepts (Classes) – categories: Disease, Medicine, Symptom
2. Instances (Individuals) – specific members: Flu, Aspirin, Fever
3. Relationships (Properties) – connections: Medicine “treats” Disease
4. Constraints & Rules – restrictions: “A treatment must be associated with at least one disease”
5. Inference Mechanisms – derive new facts: If Aspirin is-a Pain Reliever, and Pain Relievers treat Headache, then Aspirin can treat Headache

Part 4: RDF and OWL – The Technical Standards

RDF (Resource Description Framework) is a W3C standard for representing facts as triples:

(Subject, Predicate, Object)  =  (Head, Relation, Tail)  =  (h, r, t)

Examples:
<Einstein> <born_in> <Germany>
<Einstein> <discovered> <Theory of Relativity>
<Theory of Relativity> <related_to> <Physics>

RDF is flexible (any fact can be a triple), scalable (designed for the web), and machine-readable.

OWL (Web Ontology Language) extends RDF by adding logical reasoning:

<owl:Class rdf:ID="Scientist">
  <rdfs:subClassOf rdf:resource="#Person"/>
</owl:Class>

This says “Scientist is a subclass of Person.” Now if we know “Einstein is-a Scientist”, OWL can automatically infer “Einstein is-a Person.”

Key difference:

• RDF = facts (the basic triple-based data model for representing knowledge)
• OWL = logic + ontology (extends RDF with richer ontology constructs and logical reasoning)

Part 5: Building a Knowledge Graph

How do you fill a KG with facts? Four steps:

Step 1: Entity Extraction (NER)
  "Albert Einstein was born in Germany" → {Albert Einstein, Germany}

Step 2: Relation Extraction
  → (Albert Einstein, born_in, Germany)

Step 3: Knowledge Integration (Entity Resolution)
  "Albert Einstein" (source A) = "A. Einstein" (source B) → merge

Step 4: Storage & Query
  Store in graph database (Neo4j, RDF Store, Dgraph)
  Query using SPARQL or Cypher

Data sources for KG construction:

1. Structured (databases, existing KBs) – already organized, e.g., DBpedia, Wikidata
2. Unstructured (text, webpages) – use NLP (NER + RE) to extract knowledge
3. Semi-Structured (JSON, XML, APIs) – requires transformation, e.g., Wikipedia infoboxes

SPARQL query example (from slides):

SELECT ?birthplace WHERE {
  <http://dbpedia.org/resource/Albert_Einstein>
  <http://dbpedia.org/ontology/birthPlace> ?birthplace.
}

Part 6: Three Families of KG Inference

1. Rule-Based (Symbolic Inference): Apply explicit logical rules:

IF (A, part_of, B) AND (B, part_of, C) THEN (A, part_of, C)

Facts: (Auckland, part_of, New Zealand), (New Zealand, part_of, Oceania)
Infer: (Auckland, part_of, Oceania) ✅

Often implemented using OWL, SPARQL, and FOL.

2. Graph-Based (Path-Based Inference): Traverse graph structure using graph query languages (SPARQL, Cypher) and graph algorithms (PageRank, Shortest Path):

Query: "Was Einstein indirectly mentored by Curie?"
Shortest path in Neo4j → Curie ──mentored──► X ──mentored──► Einstein
Answer: Yes, through intermediate node X

3. Embedding-Based (KGE – this is where TransE lives): Represent entities and relations as dense vectors in continuous space. Predict missing facts via vector arithmetic. This is the approach tested in exams.

Part 7: TransE – The Key Idea

Think of it like giving directions on a map. If “Paris” is at position (0.5, 0.2, 0.7) and the direction “located_in” is the movement (0.3, 0.2, 0.3), then after following that direction you should arrive at “France”:

$$\mathbf{h} + \mathbf{r} = (0.5 + 0.3,\ 0.2 + 0.2,\ 0.7 + 0.3) = (0.8,\ 0.4,\ 1.0)$$

Now compare this predicted destination to all candidate entities:

France wins with distance 0.0. The model correctly predicts (Paris, located_in, France).

The beauty: you never told the model any rules. It learned that “located_in” means “move by (0.3, 0.2, 0.3)” just from seeing thousands of (city, located_in, country) examples.

Part 8: RAG – The Librarian + The Storyteller

An LLM (like GPT) is a great storyteller but sometimes makes things up (hallucination). RAG adds a librarian step:

User asks: "Who won the Turing Award in 2023?"

WITHOUT RAG (hallucination risk):
  LLM: "The Turing Award is given annually for contributions to 
        computer science, but I am unsure who won in 2023."

WITH RAG:
  Step 1: RETRIEVE from knowledge base
    → "In 2023, the Turing Award was awarded to Geoffrey Hinton 
       for his contributions to deep learning"
  Step 2: AUGMENT -- feed retrieved context to LLM
  Step 3: GENERATE grounded answer
    → "The 2023 Turing Award was awarded to Geoffrey Hinton 
       for his contributions to deep learning."

Why RAG over fine-tuning? RAG updates knowledge by updating the retrieval index (cheap), not by retraining the model (expensive). The LLM’s weights are never modified.

RAG Pipeline (from slides):

1. User Query – “Who won the Turing Award in 2023?”
2. Knowledge Retrieval – search structured (DBs, KGs) and unstructured (documents) sources using BM25 (sparse) or DPR/FAISS (dense)
3. Contextual Integration – retrieved documents passed to LLM as additional context
4. Response Generation & Re-Ranking – LLM generates factually grounded answer; some models apply re-ranking

Mathematical representation: $\text{Generated Response} = \text{LLM}(\text{Query} + \text{Retrieved Knowledge})$

⚠️ Common Misconception: Students often think TransE proves a fact is true. It does NOT. TransE gives a score (distance). A low score means the triple is likely true based on learned patterns. It is probabilistic, not logical.

⚠️ Common Misconception: RAG does not retrain or fine-tune the LLM. It only provides additional context at inference time. The LLM parameters remain frozen.

⚠️ Common Misconception: Students confuse Ontology and Knowledge Graph. An ontology defines what is valid (schema + rules); a KG stores what is true (specific facts). AI systems integrate: Ontology (rules/schema) → Knowledge Graph (facts).

💡 Core Intuition: TransE treats relations as translations in vector space – add the relation vector to the head, and you should land near the tail.

📐 正式定义（Formal Definition）

Semantic Networks vs Knowledge Graphs (Formal Comparison)

Expert System – Three Components

              ┌─────────────────────┐
              │    User Interface   │  ← Doctor inputs patient symptoms
              └─────────┬───────────┘
                        │
              ┌─────────▼───────────┐
              │   Inference Engine  │  ← Applies rules to facts
              │  (Forward/Backward  │     to derive conclusions
              │    Chaining)        │
              └─────────┬───────────┘
                        │
              ┌─────────▼───────────┐
              │   Knowledge Base    │  ← IF fever AND bacterial infection
              │   (Rules + Facts)   │     THEN recommend antibiotic
              └─────────────────────┘

MYCIN example (from slides): AI for medical diagnosis (1970s). “IF patient has fever AND bacterial infection, THEN recommend an antibiotic treatment.” MYCIN outperformed some doctors in diagnosing bacterial infections.

Ontology – Five Components

Ontology vs Knowledge Graph (from slides):

• KG: (subject, predicate, object) – only represents facts; no clear statement on what is valid
  • Example: (Aspirin, treats, Headache); (Flu, hasSymptom, Fever)
• Ontology: concepts, relations, rules – defines that only Medicine can treat Disease
  • Example: Medicine “treats” Disease (schema-level constraint)
• AI systems integrate: Ontology (rules/schema) → Knowledge Graph (facts)

Knowledge Graph – Formal Structure

A Knowledge Graph is a tuple $\mathcal{G} = (E, R, T)$ where:

• $E$ = set of entities (nodes)
• $R$ = set of relation types (edge labels)
• $T \subseteq E \times R \times E$ = set of triples (directed, labeled edges representing facts)

RDF and OWL

RDF represents knowledge using triples:

• $(S, P, O) = (\text{Subject, Predicate, Object}) = (h, r, t)$
• Flexible, scalable, machine-readable

OWL extends RDF:

• Allows logical reasoning and ontology-based classification
• Defines concepts, relationships, and hierarchy constraints
• Example: OWL defines “Scientist” as subclass of “Person” → Einstein is-a Scientist → infer Einstein is-a Person

KG Inference Tasks (from slides)

TransE Scoring Function

For a triple $(h, r, t)$, the energy (score) function is:

$$f(h, r, t) = |\mathbf{h} + \mathbf{r} - \mathbf{t}|_{p}$$

where $p = 1$ for L1 norm (Manhattan distance) or $p = 2$ for L2 norm (Euclidean distance).

• Low $f(h,r,t)$ → triple is likely true
• High $f(h,r,t)$ → triple is likely false

L1 norm (Manhattan distance): $$|\mathbf{h} + \mathbf{r} - \mathbf{t}|1 = \sum{i=1}^{d} |h_i + r_i - t_i|$$

L2 norm (Euclidean distance): $$|\mathbf{h} + \mathbf{r} - \mathbf{t}|2 = \sqrt{\sum{i=1}^{d} (h_i + r_i - t_i)^2}$$

Margin-Based Ranking Loss

$$\mathcal{L} = \sum_{(h,r,t) \in S}\ \sum_{(h’,r,t’) \in S’} \max!\Big(0,\ \gamma + f(h,r,t) - f(h’,r,t’)\Big)$$

where:

• $S$ = set of correct triples (positive examples)
• $S’$ = set of corrupted triples (negative examples)
• $\gamma > 0$ = margin hyperparameter (separation gap between positive and negative scores)
• Goal: push $f(\text{positive})$ down and $f(\text{negative})$ up, with at least $\gamma$ gap

Negative Sampling (Corruption)

Given a true triple $(h, r, t)$, generate negatives by:

• Corrupt head: replace $h$ with random $h’ \in E$, yielding $(h’, r, t)$
• Corrupt tail: replace $t$ with random $t’ \in E$, yielding $(h, r, t’)$

Constraint: the corrupted triple must not exist in $T$ (otherwise it is a valid fact, not a true negative).

🔄 机制与推导（How It Works）

KG Construction Pipeline – Step by Step

Raw Text / Structured Data / Semi-Structured Data
        ↓
[Step 1] Entity Extraction (NER)
        "Albert Einstein was born in Germany and developed
         the Theory of Relativity"
        → {Albert Einstein, Germany, Theory of Relativity}
        ↓
[Step 2] Relation Extraction
        → (Albert Einstein, born_in, Germany)
        → (Albert Einstein, discovered, Theory of Relativity)
        ↓
[Step 3] Knowledge Integration (Entity Resolution)
        "Albert Einstein" (Wikipedia) = "A. Einstein" (paper) → merge
        ↓
[Step 4] Store in Graph Database & Query
        ├── Neo4j (Property Graph, Cypher queries)
        ├── RDF Store (Triple Store, SPARQL queries)
        └── Dgraph (Distributed, GraphQL+)

Graph Database Comparison

Key distinction: Property graphs allow key-value attributes on both nodes and edges. RDF triples are purely (S, P, O) – to attach metadata you need reification.

Three Types of KG Inference – Detailed

1. Rule-Based Inference（基于规则的推理）

Apply explicit logical rules (IF-THEN, OWL reasoning, SPARQL, FOL):

Rule: IF (X, part_of, Y) AND (Y, part_of, Z) THEN (X, part_of, Z)

Facts: (Auckland, part_of, New Zealand), (New Zealand, part_of, Oceania)
Infer: (Auckland, part_of, Oceania) ✅

Strengths: deterministic, interpretable, guaranteed sound. Weakness: requires manually written rules; cannot handle missing data.

2. Graph-Based Inference（基于路径的推理）

Traverse graph paths using SPARQL, Cypher, graph algorithms (PageRank, Shortest Path):

Query: "Did Newton influence Einstein?"
Path found: Newton →[discovered]→ Law of Gravity →[influenced]→ 
            Theory of Relativity ←[developed]← Einstein
Answer: Yes — Newton's work indirectly influenced Einstein.

Strengths: uses graph structure directly; no training needed. Weakness: only finds what is reachable; cannot generalize beyond existing edges.

3. Embedding-Based Inference（基于嵌入的推理）

Represent entities and relations as dense vectors; predict missing facts via vector arithmetic.

Why use embeddings?

• Captures hidden patterns: generalizes beyond explicit triples
• Scalable & efficient: works well for large-scale KGs (Wikidata, Freebase)
• Enables deep learning integration: works with LLMs and generative AI

This is where TransE operates. See the complete treatment below.

TransE Training – Complete Process

Step 1: Initialize embeddings

Assign each entity $e \in E$ a random $d$-dimensional vector $\mathbf{e} \in \mathbb{R}^d$. Assign each relation $r \in R$ a random $d$-dimensional vector $\mathbf{r} \in \mathbb{R}^d$. (Optional) Normalize all entity vectors to unit length: $|\mathbf{e}| = 1$.

Step 2: Sample a mini-batch of true triples

From the training set $T$, sample positive triples, e.g.:

• (Paris, located_in, France)
• (Berlin, located_in, Germany)
• (France, part_of, Europe)

Step 3: Generate negative triples (corruption)

For each positive triple $(h, r, t)$, create a negative by randomly replacing head or tail:

• (Paris, located_in, France) → corrupt tail → (Paris, located_in, Germany) [negative]
• (Berlin, located_in, Germany) → corrupt head → (Tokyo, located_in, Germany) [negative]

Step 4: Compute scores

For positive triple: $f^+ = |\mathbf{h} + \mathbf{r} - \mathbf{t}|$ For negative triple: $f^- = |\mathbf{h’} + \mathbf{r} - \mathbf{t}|$ (or $|\mathbf{h} + \mathbf{r} - \mathbf{t’}|$)

We want $f^+$ to be small and $f^-$ to be large.

Step 5: Compute margin loss and update

$$\text{loss} = \max(0,\ \gamma + f^+ - f^-)$$

If $f^- - f^+ > \gamma$, the loss is zero (good separation). Otherwise, adjust embeddings via gradient descent to push $f^+$ down and $f^-$ up.

Step 6: (Optional) Normalize entity embeddings

Re-normalize entity vectors after each gradient step to prevent embedding magnitudes from exploding.

Step 7: Repeat until convergence.

TransE Inference – Worked Example (Lecture Slides 45–46)

This exact computation style appears in Sample Test Q3. Practice until automatic.

Setup:

Known facts:

• (Paris, located_in, France)
• (France, part_of, Europe)

Pre-trained embeddings ($d = 3$):

Query: (Paris, located_in, ?) – Which entity is Paris located in?

Step 1: Compute $\mathbf{h} + \mathbf{r}$:

$$\mathbf{h} + \mathbf{r} = (0.5, 0.2, 0.7) + (0.3, 0.2, 0.3) = (0.8, 0.4, 1.0)$$

Step 2: Compute L1 distance to each candidate entity:

$$d(\text{France}) = |0.8 - 0.8| + |0.4 - 0.4| + |1.0 - 1.0| = 0 + 0 + 0 = \mathbf{0.0}$$

$$d(\text{Europe}) = |0.8 - 0.9| + |0.4 - 0.3| + |1.0 - 1.2| = 0.1 + 0.1 + 0.2 = \mathbf{0.4}$$

$$d(\text{Germany}) = |0.8 - 1.2| + |0.4 - 0.6| + |1.0 - 1.5| = 0.4 + 0.2 + 0.5 = \mathbf{1.1}$$

Step 3: Rank by distance (ascending):

Answer: France (smallest L1 distance = 0.0). The model predicts (Paris, located_in, France).

Ontology Inference – Worked Example (Exercise 2 from slides)

Scenario: A company ontology for employees, projects, and roles.

Ontology structure:

• Classes: Employee (Alice, Bob, Charlie), Project (Project X, Project Y), Role (Manager, Developer)
• Relationships: Employee “works on” Project; Employee “has role” Role; Role “is responsible for” Project
• Instances:
  • Alice → has role → Manager; Bob → has role → Developer; Charlie → has role → Developer
  • Manager → is responsible for → Project X; Developer → is responsible for → Project Y
  • Alice → works on → Project X; Bob → works on → Project Y; Charlie → works on → Project X
• Constraints:
  1. Each Project has at least one Employee working on it
  2. Each Role is responsible for at least one Project
  3. If an Employee has a Role and that Role is responsible for a Project, then the Employee can be inferred to be working on that Project
  4. An employee works on exactly one Project

Question: Which of the following inferences is logically valid?

• A) Alice can be inferred to be working on Project Y
• B) Charlie can be inferred to be responsible for Project X
• C) Bob can be inferred to be working on Project Y because his Role (Developer) is responsible for that Project
• D) Alice and Bob must switch projects

Answer: C

Reasoning:

• A incorrect: No relationship between Alice and Project Y in the ontology
• B incorrect: Charlie is a Developer, but Project X is the responsibility of a Manager. The ontology states that Roles (not individuals) are responsible. Charlie has the role Developer, and Project Y is the responsibility of the Developer role. But this does NOT automatically mean Charlie is responsible for Project X.
• C correct: Bob is a Developer. The ontology states Developer is responsible for Project Y. Constraint 3 says: if Employee has Role AND Role is responsible for Project → Employee works on that Project. Therefore Bob works on Project Y. ✅
• D incorrect: No rule states a Manager must be assigned to all projects

Important note from slides: In ontology reasoning: (1) Explicit facts take priority, (2) Inferences cannot contradict or replace given facts.

RDF + OWL Inference – Worked Example (Exercise 3 from slides)

Scenario: A university KG stored using RDF triples and OWL reasoning rules.

RDF triples:

<Prof_John> <teaches> <AI_Course>
<AI_Course> <belongs_to> <CS_Department>
<CS_Department> <part_of> <Engineering_Faculty>
<Prof_John> <works_in> <CS_Department>

OWL ontology rules:

1. All courses belong to exactly one department
2. If a professor teaches a course, they are part of that course’s department
3. All departments are part of a faculty
4. If a professor works in a department, they are a member of that faculty

Question: Which faculty does Prof. John belong to?

Answer: B – Prof. John belongs to the Engineering Faculty based on OWL reasoning rules.

Step-by-step reasoning:

1. RDF: Prof. John teaches AI_Course → AI_Course belongs_to CS_Department → Prof. John is in CS_Department (OWL Rule 2)
2. RDF: Prof. John works_in CS_Department (also given directly)
3. OWL Rule 4: Professor works in department → also faculty member; CS_Department is part_of Engineering_Faculty (OWL Rule 3)
4. Conclusion: Prof. John is a faculty member of the Engineering Faculty

TransE Limitations & Extensions

Why TransE Struggles

TransE’s core equation $\mathbf{h} + \mathbf{r} = \mathbf{t}$ means that for a given relation $r$ and tail $t$, there is exactly one ideal head vector: $\mathbf{h} = \mathbf{t} - \mathbf{r}$.

This causes problems with 1-to-N, N-to-1, and N-to-N relations:

Example (N-to-1): (Paris, located_in, France), (Lyon, located_in, France), (Marseille, located_in, France).

TransE requires: $\mathbf{Paris} + \mathbf{r} \approx \mathbf{France}$, $\mathbf{Lyon} + \mathbf{r} \approx \mathbf{France}$, $\mathbf{Marseille} + \mathbf{r} \approx \mathbf{France}$.

This forces $\mathbf{Paris} \approx \mathbf{Lyon} \approx \mathbf{Marseille}$ – all three cities collapse to the same point, losing their distinct identities!

Extensions Beyond TransE (from slides)

TransH – deals with many-to-one issue:

• Each relation $r$ has a normal vector $\mathbf{w}_r$ defining a hyperplane
• Project entities onto the hyperplane: $\mathbf{h}_\perp = \mathbf{h} - \mathbf{w}_r^\top \mathbf{h} \cdot \mathbf{w}_r$
• Score: $f(h,r,t) = |\mathbf{h}\perp + \mathbf{r} - \mathbf{t}\perp|$
• Different $h$ can get the same $h_\perp$, allowing distinct entities to have different projected representations
• Example: “Paris located_in France” and “Louvre located_in France” are projected onto different planes, preventing entity overlap

TransR – projects into relation-specific space:

• Each relation $r$ has a projection matrix $\mathbf{M}_r \in \mathbb{R}^{k \times d}$
• Project entities: $\mathbf{h}_r = \mathbf{M}_r \mathbf{h}$, $\mathbf{t}_r = \mathbf{M}_r \mathbf{t}$
• Score: $f(h,r,t) = |\mathbf{h}_r + \mathbf{r} - \mathbf{t}_r|$
• More expressive but requires more parameters

⚖️ 权衡分析（Trade-offs & Comparisons）

KG Inference Methods Compared

Expert Systems vs Ontologies vs Knowledge Graphs

RAG vs Fine-Tuning vs Vanilla LLM

Evolution of KR in AI (from slides)

Expert Systems (1970s--1980s)
  ↓ Early symbolic AI, rule-based knowledge bases
  ↓ Example: MYCIN for medical diagnosis
  
Ontologies (1990s--2000s)
  ↓ Formal representation of domain knowledge
  ↓ Defines concepts, relationships, constraints
  ↓ Enables logical reasoning and classification
  
Knowledge Graphs (2000s--present)
  ↓ Large-scale graph-based representation
  ↓ Built using RDF/OWL
  ↓ Supports reasoning, inference, retrieval
  
RAG (2020s--present)
  ↓ Combines KG retrieval with LLMs
  ↓ Reduces hallucination, improves accuracy

🏗️ 设计题答题框架

Prompt: “Design a knowledge-based system that uses KG embeddings to recommend research papers.”

WHAT: “I would design a system that constructs a Knowledge Graph of papers, authors, topics, and citations, then uses TransE-family embeddings for link prediction to discover relevant but undiscovered connections, with a RAG pipeline to generate natural-language explanations.”

WHY: “A KG captures structured relationships (author-wrote-paper, paper-cites-paper, paper-covers-topic) that collaborative filtering alone misses. Embeddings enable prediction of missing links (e.g., papers a researcher should read but hasn’t cited).”

HOW:

1. KG Construction: Extract entities (papers, authors, topics) from metadata + NLP on abstracts. Relations: wrote, cites, covers_topic, affiliated_with.
2. Storage: Use Neo4j for rich property attributes (publication year, citation count on edges).
3. Embedding Training: Train TransR (not TransE – because “covers_topic” is N-to-N: many papers cover the same topic). Optimize margin-based ranking loss.
4. Inference: For researcher $R$, compute $\mathbf{R} + \mathbf{should_read}$ and rank all papers by L1 distance. Top-k = recommendations.
5. RAG layer: User asks “Why is this paper relevant?” → retrieve related KG triples → LLM generates natural-language explanation grounded in facts.

TRADE-OFF:

• TransE is simpler and faster but would collapse papers covering the same topic → choose TransR for expressiveness at the cost of more parameters.
• Neo4j offers rich property storage but single-machine limits → if scale demands, migrate to Dgraph.
• RAG adds latency but eliminates “black box” recommendations.

EXAMPLE: “Researcher studies ‘attention mechanisms’. KG link prediction finds (Researcher, should_read, ‘FlashAttention paper’) with low distance score. RAG retrieves: (FlashAttention, improves, Transformer efficiency), (Researcher, studies, Attention) → LLM explains: ‘This paper is relevant because it improves the efficiency of the attention mechanisms you study.’”

📝 历年真题 + 练习题

Sample Test Q3 (2 marks) – Original

Explain Knowledge Graph Embeddings and give a common KG inference task.

Model answer (2-mark level):

Knowledge Graph Embeddings represent entities and relations as dense vectors in a continuous space. Models like TransE learn these vectors such that for a true triple $(h, r, t)$, the relationship $\mathbf{h} + \mathbf{r} \approx \mathbf{t}$ holds. This enables the system to predict missing facts via vector arithmetic rather than explicit graph traversal.

A common inference task is Link Prediction: given an incomplete triple $(h, r, ?)$, compute $\mathbf{h} + \mathbf{r}$ and find the entity $t^*$ whose embedding is nearest (by L1 or L2 distance). For example, (Einstein, born_in, ?) → compute $\mathbf{h} + \mathbf{r}$ → nearest entity = Germany.

Exercise 1 – Expert Systems: Fraud Detection (from W3L2 slides)

Scenario: A bank uses an Expert System for fraud detection with these IF-THEN rules:

Rule ID	IF Condition	THEN Conclusion
R1	Transaction amount > $10,000 AND foreign country AND no travel history	Flag as Potential Fraud
R2	Multiple transactions occur within 5 min in different locations	Flag as High-Risk Fraud
R3	User confirms transaction via 2FA	Approve Transaction
R4	Transaction is flagged as fraud (R1 or R2) AND user does NOT confirm via 2FA	Temporarily Block Card
R5	User has history of similar transactions in same location	Approve Transaction

Case Study: A user attempts a $12,500 transaction in Japan at 3 PM.

• The user has no travel history to Japan
• Five minutes earlier, a $100 transaction occurred in New York, USA
• The user does NOT confirm via 2FA
• The user has no prior transactions in Japan

Question: How should the Expert System respond?

A) Approve the transaction because the user has made similar purchases before. B) Temporarily block the user’s card due to suspicious activity. C) Approve the transaction because it happened at a normal time. D) Flag the transaction but allow it since the amount is not too high.

Exercise 2 – Ontology Reasoning (Employee/Project)

See the detailed Exercise 2 worked example in the “How It Works” section above.

Exercise 3 – RDF + OWL Inference (Prof. John)

See the detailed Exercise 3 worked example in the “How It Works” section above.

Exercise 4 – Extracting Triples from Text (Marie Curie)

Scenario: An AI system uses NER and RE to construct a Knowledge Graph from unstructured text.

Text: “Marie Curie, a physicist and chemist, was born in Poland in 1867. She discovered radium and polonium, and was awarded the Nobel Prize in Physics in 1903 along with Pierre Curie. Later, in 1911, she won another Nobel Prize, this time in Chemistry.”

Question: What triples can you extract for the Knowledge Graph (as many as you can)?

Exercise 5 – TransE Computation (from W3L2 slides, same as Sample Test style)

Scenario: TransE is trained on facts: (Paris, located_in, France), (France, part_of, Europe), (Berlin, located_in, Germany), (Germany, part_of, Europe).

Learned embeddings:

• Paris → $(0.5, 0.2, 0.7)$, France → $(0.8, 0.4, 1.0)$, Europe → $(0.9, 0.3, 1.2)$, Germany → $(1.2, 0.6, 1.5)$
• located_in → $(0.3, 0.2, 0.3)$

Query: (Paris, located_in, ?) – which entity is the most likely prediction using L1 distance?

Practice Problem – TransE Computation ($d = 4$)

Entity embeddings:

• Tokyo → $(0.1, 0.5, 0.3, 0.8)$
• Japan → $(0.4, 0.7, 0.6, 1.1)$
• China → $(0.6, 0.9, 0.5, 1.3)$
• Seoul → $(0.2, 0.4, 0.4, 0.9)$
• South Korea → $(0.5, 0.6, 0.7, 1.2)$

Relation embedding:

• capital_of → $(0.3, 0.2, 0.3, 0.3)$

Query: (Tokyo, capital_of, ?)

Practice Problem – Negative Sampling

Given the true triple (Berlin, located_in, Germany), generate two negative triples by corruption.

Practice Problem – Conceptual (Short Answer)

Why does TransE fail for N-to-1 relations? Give a specific example.

🌐 英语表达要点（English Expression）

Defining KG Embeddings (exam sentence starters)

"Knowledge Graph Embeddings map entities and relations to continuous 
 vector representations, enabling algebraic operations for inference 
 over incomplete knowledge graphs."

"TransE models each relation as a translation vector in embedding space, 
 such that for a valid triple (h, r, t), the equation h + r ≈ t holds."

Explaining Link Prediction

"To predict the missing tail in (h, r, ?), we compute h + r and rank 
 all candidate entities by their L1 or L2 distance to this predicted 
 point. The entity with the smallest distance is the predicted answer."

Explaining Ontologies vs KGs

"An ontology provides the formal schema — defining what types of entities
 exist and how they may relate — while a knowledge graph stores the 
 specific factual instances conforming to that schema."

"The fundamental difference is that an ontology defines what is *valid*,
 while a KG stores what is *true*."

Describing Expert Systems

"An Expert System consists of three components: a Knowledge Base storing
 domain rules and facts, an Inference Engine that applies rules to derive
 conclusions, and a User Interface for input/output."

Describing RAG

"Retrieval-Augmented Generation addresses LLM hallucination by retrieving 
 relevant knowledge from external sources at inference time and injecting 
 it into the prompt as context, without modifying the model's parameters."

"The key advantage of RAG over fine-tuning is that the knowledge base
 can be updated independently of the model, enabling real-time access
 to the latest information at minimal cost."

Comparing Models

"While TransE is computationally efficient and works well for 1-to-1 
 relations, it struggles with N-to-N mappings because multiple entities 
 sharing the same relation and target collapse to identical embeddings."

"TransH addresses this limitation by introducing a relation-specific 
 hyperplane, allowing entities to have distinct projected representations 
 even when they share the same relation."

易错词汇

✅ 自测检查清单

• Can I compare Semantic Networks vs Knowledge Graphs in a table (origin, scale, standardization)?
• Can I draw the 3-component architecture of an Expert System (KB + Inference Engine + UI)?
• Can I explain the MYCIN example and what an Expert System does?
• Can I list the 5 components of an Ontology (Concepts, Instances, Relationships, Constraints, Inference)?
• Can I explain the difference between an Ontology and a Knowledge Graph in one sentence?
• Can I explain RDF (triples) and how OWL extends it (adds logical reasoning)?
• Can I solve the Exercise 2 ontology reasoning problem (employee/project)?
• Can I trace the Exercise 3 RDF+OWL inference (Prof. John → Engineering Faculty)?
• Can I compare Neo4j vs RDF Store vs Dgraph in a table?
• Can I explain the 4-step KG construction pipeline (Entity Extraction → Relation Extraction → Knowledge Integration → Storage & Query)?
• Can I extract triples from a text passage (Exercise 4, Marie Curie)?
• Can I name and explain the 3 types of KG inference (rule-based, path-based, embedding-based)?
• Can I list 6 KG inference tasks (completion, relation prediction, fact verification, fact generation, reasoning, alignment)?
• Can I write the TransE scoring formula $f(h,r,t) = |\mathbf{h} + \mathbf{r} - \mathbf{t}|$ from memory?
• Can I compute $\mathbf{h} + \mathbf{r}$ and L1 distances to predict a missing entity by hand in under 2 minutes?
• Can I explain negative sampling – how to corrupt a triple and why we need it?
• Can I write the margin-based ranking loss and explain what $\gamma$ controls?
• Can I explain why TransE fails for N-to-1 relations with a concrete example?
• Can I describe how TransH fixes TransE’s limitation (hyperplane projection)?
• Can I compare TransE, TransH, TransR in a table?
• Can I draw the RAG pipeline (Query → Retrieve → Augment → Generate)?
• Can I explain the difference between RAG and fine-tuning in one sentence?
• Can I compare RAG vs Fine-Tuning vs Vanilla LLM in a table?
• Can I explain why modern AI combines KR (structured knowledge) with LLMs (data-driven models)?
• Can I solve a TransE computation problem like Sample Test Q3 under exam conditions?

Cross-references:

• For KR fundamentals (Semantic Networks, Frames, Rule-Based Systems), see KR Methods chapter
• For Symbolic Logic (PL + FOL), see Symbolic Logic chapter
• For Expert Systems and MYCIN in depth, see MYCIN chapter

MYCIN Expert System — Deep Dive (W4L1)

🎯 考试重要度

🟡 中频 — 但正式考试很可能出现 | 整个 W4L1 专门讲 MYCIN，CF 计算是极易出计算题的考点

MYCIN did not appear in some sample tests, but an entire lecture was devoted to it. Confidence Factor calculations are extremely testable as short numerical questions. Backward chaining reasoning is a favourite topic for “explain with an example” questions. S1 2025 Sample Q6 (3 marks) directly tests backward chaining for medical diagnosis.

📖 核心概念（Core Concepts）

🧠 费曼草稿（Feynman Draft）

The Junior Doctor with a Giant Manual

Imagine a brand-new doctor on their first day in the hospital. They have zero experience but someone hands them a thick manual – 450 pages of rules written by the best infectious disease specialist in the country. Each page says something like:

“IF the patient’s culture shows gram-negative organisms AND the organism has rod morphology AND the organism is anaerobic, THEN the organism is Bacteroides (I’m about 60% sure).”

The junior doctor doesn’t think creatively. They just follow the manual backwards: they start with a question (“What is causing this infection?”), look up which rules could answer it, then check whether they already know the required facts. If they don’t know something, they either look it up in the patient’s chart or ask the patient directly.

That’s MYCIN. It’s not intelligent in the human sense – it’s a systematic rule-follower with a clever strategy for deciding what to ask.

The Manual is Written in a Weird Language

MYCIN was built in LISP – a programming language where everything is written in prefix notation（前缀表示法）with lots of parentheses:

;; Instead of 2 + 3, you write:
(+ 2 3)          ; → 5

;; Key LISP operations MYCIN uses:
(cons 'a '(b c)) ; → (a b c)   -- prepend an element to a list
(list 'a 'b 'c)  ; → (a b c)   -- create a list
(setq x 5)       ; → x is now 5 -- assign a value to a variable
(eval '(+ 2 3))  ; → 5         -- evaluate an expression

You don’t need to write LISP for the exam, but you should know MYCIN was implemented in LISP and understand prefix notation if given an example.

How Does the Junior Doctor Actually Work?

Let’s walk through a tiny example. Suppose MYCIN’s knowledge base has just three rules:

Rule 1: IF infection is primary-bacteremia
        AND culture-site is sterile-site
        THEN organism is E.coli  (CF = 0.8)

Rule 2: IF organism is E.coli
        THEN recommend drug Ampicillin  (CF = 0.9)

Rule 3: IF infection is primary-bacteremia
        AND patient-age > 60
        THEN organism is Klebsiella  (CF = 0.6)

Goal: “What drug should I recommend?”

Step 1 – MYCIN looks for rules whose THEN part mentions a drug recommendation. It finds Rule 2 (recommend Ampicillin if E.coli). But Rule 2 needs to know the organism. Is it E.coli? Unknown. So “organism is E.coli” becomes a sub-goal.

Step 2 – Now MYCIN searches for rules whose THEN part concludes about the organism. It finds Rule 1. Rule 1 needs two things: (a) infection type and (b) culture site. MYCIN checks working memory (MONITOR). If unknown, it asks the clinician (FINDOUT): “What is the infection type?” The doctor answers: “primary-bacteremia (CF = 1.0).” “What is the culture site?” Answer: “sterile-site (CF = 0.9).”

Step 3 – Now Rule 1 can fire:

• CF(premise) = min(1.0, 0.9) = 0.9 (because AND takes the minimum)
• CF(E.coli) = 0.9 x 0.8 = 0.72

Step 4 – Rule 2 can now fire:

• CF(Ampicillin) = 0.72 x 0.9 = 0.648

MYCIN would report: “I recommend Ampicillin with confidence 0.648.”

This is backward chaining – we started from the goal and worked backwards through the rule chain, only asking questions that were actually needed.

When Does MYCIN Give Up?

MYCIN is smart about not wasting time. It abandons a hypothesis when CF drops below 0.2. Here’s a concrete example of CF propagation down a chain:

Starting hypothesis CF = 0.5
  → Apply Rule (CF_rule = 0.6):
    CF(condition1) = 0.5 x 0.6 = 0.30     (still above 0.2, keep going)
  → Apply next Rule (CF_rule = 0.6):
    CF(condition2) = 0.30 x 0.6 = 0.18    (below 0.2 → ABANDON this path!)

This is efficient: rather than chasing every possible chain of reasoning, MYCIN prunes away paths where confidence has become too low to be useful.

What if Two Rules Support the Same Conclusion?

Suppose Rule 1 gives CF(E.coli) = 0.72 and another Rule 4 also concludes E.coli with CF = 0.5. We combine them:

$$CF_{combined} = 0.72 + 0.5 \times (1 - 0.72) = 0.72 + 0.14 = 0.86$$

Two independent pieces of evidence reinforce each other. Notice the combined CF is higher than either alone, but never reaches 1.0 from two uncertain pieces – that makes intuitive sense!

⚠️ Common Misconception 1: Students often multiply CFs when combining multiple rules for the same conclusion. That’s WRONG. Multiplication is for chaining rules in sequence (premise CF x rule CF). The special combination formula $CF_1 + CF_2(1 - CF_1)$ is for when two different rules both support the same conclusion.

⚠️ Common Misconception 2: Students confuse AND (take the minimum) with OR (take the maximum). Think of it this way – a chain is only as strong as its weakest link (AND = min), but you only need one good reason (OR = max).

⚠️ Common Misconception 3: “IF A THEN B” does NOT mean A is the only cause of B. Multiple rules can conclude B from different premises. Backward chaining identifies possible necessary conditions, not unique ones.

💡 Core Intuition: MYCIN is a backward-chaining rule system that asks only necessary questions, propagates uncertainty through confidence factors, and abandons low-confidence paths early.

📐 正式定义（Formal Definition）

MYCIN Architecture – Three Subprograms

┌─────────────────────────────────────────────────────────────────┐
│                         MYCIN System                            │
│                                                                 │
│  ┌──────────────────────┐    ┌───────────────────────────────┐  │
│  │   Knowledge Base      │    │      Dynamic Data             │  │
│  │   (Persistent,        │    │  (Working Memory,             │  │
│  │    Long-term Memory)  │    │   Per-case, Short-term)       │  │
│  │   450+ IF-THEN rules  │    │   Patient facts gathered      │  │
│  │   with CF values      │    │   during this consultation    │  │
│  └──────────┬────────────┘    └──────────────┬────────────────┘  │
│             │                                │                  │
│  ┌──────────┴────────────────────────────────┴────────────────┐ │
│  │            Inference Engine (MONITOR + FINDOUT)             │ │
│  │            Backward Chaining Controller                    │ │
│  │            Abandons paths when CF < 0.2                    │ │
│  └──────────────────────┬─────────────────────────────────────┘ │
│                         │                                       │
│  ┌──────────────────────┴─────────────────────────────────────┐ │
│  │                                                            │ │
│  │  Subprogram 1:           Subprogram 2:                     │ │
│  │  CONSULTATION SYSTEM     EXPLANATION SYSTEM                │ │
│  │  (Conducts the           (Handles WHY and HOW              │ │
│  │   diagnostic dialogue)    queries from clinician)          │ │
│  │                                                            │ │
│  │  Subprogram 3:                                             │ │
│  │  RULE-ACQUISITION SYSTEM                                   │ │
│  │  (Allows experts to add/modify rules in KB)                │ │
│  │                                                            │ │
│  └────────────────────────────────────────────────────────────┘ │
│                                                                 │
│  ┌────────────────────────────────────────────────────────────┐ │
│  │              User Interface (CLI)                          │ │
│  │  Clinician answers questions, asks WHY/HOW,                │ │
│  │  receives diagnosis and treatment recommendation           │ │
│  └────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Key architectural insight: The separation of Knowledge Base from Inference Engine is what enabled E-MYCIN – remove the medical rules and you get a reusable shell.

Production Rule Format

IF   [condition₁] AND [condition₂] AND ...
THEN [conclusion] WITH CF [confidence_factor]

Concrete example from lecture:

IF   the gram stain of the organism is gram-negative     (condition 1)
AND  the morphology of the organism is rod               (condition 2)
AND  the aerobicity of the organism is anaerobic         (condition 3)
THEN the identity of the organism is Bacteroides  (CF = 0.6)

CF calculation for this rule:

$$CF(\text{conclusion}) = CF(\text{premise}) \times CF(\text{rule})$$

$$CF(\text{premise}) = \min(CF(\text{gram-negative}),; CF(\text{rod}),; CF(\text{anaerobic}))$$

Confidence Factor (CF) Formulas

Range: $CF \in [-1.0, +1.0]$

Formula 1 – Conjunction (AND) of premises:

$$CF(A \text{ AND } B) = \min(CF_A, ; CF_B)$$

Intuition: a chain is only as strong as its weakest link.

Formula 2 – Disjunction (OR) of premises:

$$CF(A \text{ OR } B) = \max(CF_A, ; CF_B)$$

Intuition: you only need one good reason to believe.

Formula 3 – Rule application (premise → conclusion):

$$CF(\text{conclusion}) = CF(\text{premise}) \times CF(\text{rule})$$

Intuition: uncertainty compounds when you reason through a rule.

Formula 4 – Combining multiple rules for the same conclusion (both positive):

$$CF_{combined} = CF_1 + CF_2 \times (1 - CF_1)$$

Intuition: independent evidence reinforces belief, but with diminishing returns.

Formula 4b – Both negative:

$$CF_{combined} = CF_1 + CF_2 \times (1 + CF_1)$$

Formula 4c – One positive, one negative:

$$CF_{combined} = \frac{CF_1 + CF_2}{1 - \min(|CF_1|, |CF_2|)}$$

For the exam, the “both positive” case (Formula 4) is by far the most commonly tested.

🔄 机制与推导（How It Works）

Forward Chaining vs Backward Chaining – Formal Definitions

Forward Chaining (Data-Driven, A → B)

• Starts from known facts in working memory
• Applies all matching rules to derive new conclusions
• Uses Modus Ponens: IF A is true AND (A → B), THEN B is true
• Direction: facts → conclusions
• Example: “Patient has fever and cough → apply matching rules → conclude possible flu”

Backward Chaining (Goal-Driven, B → A)

• Starts from a hypothesis or goal
• Finds rules whose conclusion matches the goal
• Checks if premises are supported; if not, makes them sub-goals or asks the user
• Direction: hypothesis → required evidence

Critical Logical Distinction (Exam-Critical!)

IF A THEN B means:
  - A is SUFFICIENT for B (A being true is enough to conclude B)
  - B is NECESSARY for A (if B is false, A cannot lead to B)

IMPORTANT: IF A THEN B does NOT mean:
  - A is the ONLY cause of B (other rules may also conclude B!)
  - B implies A (that would be the converse fallacy)

Backward chaining implication:
  - When working backward from B, we find A as a POSSIBLE condition
  - A is a possible necessary condition, but NOT necessarily the unique one
  - Multiple rules can have B as their conclusion

Example: Rule 1 says “IF flu THEN fever.” Rule 2 says “IF meningitis THEN fever.” Starting from “fever” and working backward, we find BOTH flu and meningitis as possible causes – backward chaining identifies possible necessary conditions, not unique ones.

Backward Chaining in MYCIN – Step by Step

GOAL: Determine the identity of the organism

Step 1: Find rules whose THEN mentions "organism identity"
        → Rule 1, Rule 3 are candidates
        → Start with the HIGHEST-CONFIDENCE goal

Step 2: Try Rule 1:
        IF infection = primary-bacteremia  [Unknown → FINDOUT]
        AND site = sterile-site            [Unknown → FINDOUT]
        THEN organism = E.coli (CF=0.8)

Step 3: FINDOUT "infection type" → Clinician answers:
        "primary-bacteremia" (CF = 1.0) → store in Working Memory

Step 4: FINDOUT "culture site" → Clinician answers:
        "sterile-site" (CF = 0.9) → store in Working Memory

Step 5: Rule 1 fires:
        CF(premise) = min(1.0, 0.9) = 0.9
        CF(E.coli)  = 0.9 × 0.8 = 0.72

Step 6: Try Rule 3:
        IF infection = primary-bacteremia  [MONITOR: already known, CF=1.0]
        AND patient-age > 60              [Unknown → FINDOUT]
        THEN organism = Klebsiella (CF=0.6)

Step 7: FINDOUT "patient age" → Clinician answers:
        "age = 72" (CF = 1.0)

Step 8: Rule 3 fires:
        CF(premise) = min(1.0, 1.0) = 1.0
        CF(Klebsiella) = 1.0 × 0.6 = 0.6

Result: E.coli (CF=0.72) vs Klebsiella (CF=0.6)
        → Most likely: E.coli

Notice how MYCIN only asked three questions (infection type, culture site, patient age) – it didn’t ask about every possible fact. That’s the efficiency of backward chaining: ask only what you need.

CF Abandonment Threshold (CF < 0.2)

MYCIN does not chase every hypothesis indefinitely. When a chain of reasoning produces a CF below 0.2, the system abandons that path:

Example: Investigating whether organism X causes the infection

Step 1: Start with hypothesis CF = 0.5
Step 2: Apply Rule (CF_rule = 0.6):
        CF(condition1) = 0.5 × 0.6 = 0.30   ← still ≥ 0.2, continue
Step 3: Apply next Rule (CF_rule = 0.6):
        CF(condition2) = 0.30 × 0.6 = 0.18  ← below 0.2, ABANDON!

The system stops pursuing this line of reasoning because
the accumulated confidence is too low to be useful.

This prevents wasting time on weak hypotheses and focuses the system on the most promising diagnoses.

MONITOR vs FINDOUT – Three-Step Priority

Evaluate premise P:
  1. MONITOR: Is P already in Working Memory?
     → YES: use it (with its associated CF)
     → NO: go to step 2

  2. Are there rules whose conclusion matches P?
     → YES: set P as a sub-goal, recurse (backward chain again)
     → NO: go to step 3

  3. FINDOUT: Ask the user directly
     → Store answer in Working Memory for future MONITOR calls

This three-step priority is crucial: MYCIN avoids redundant questions by always checking memory first.

CF Calculation – Full Worked Example

Scenario: Diagnosing measles with two supporting rules.

Rule A: IF fever(CF=0.8) AND rash(CF=0.6)
        THEN measles (CF_rule = 0.7)

Rule B: IF recent-contact-with-measles-patient(CF=0.9)
        THEN measles (CF_rule = 0.5)

Step 1 – Rule A fires:

$$CF_A(\text{premise}) = \min(0.8, 0.6) = 0.6$$

$$CF_A(\text{measles}) = 0.6 \times 0.7 = 0.42$$

Step 2 – Rule B fires:

$$CF_B(\text{premise}) = 0.9$$

$$CF_B(\text{measles}) = 0.9 \times 0.5 = 0.45$$

Step 3 – Combine Rule A and Rule B (both positive):

$$CF_{combined} = CF_A + CF_B \times (1 - CF_A)$$ $$CF_{combined} = 0.42 + 0.45 \times (1 - 0.42)$$ $$CF_{combined} = 0.42 + 0.45 \times 0.58$$ $$CF_{combined} = 0.42 + 0.261 = 0.681$$

Result: measles with CF = 0.681

Key insight: neither rule alone gives high confidence (0.42 and 0.45), but together they push it to 0.681. Independent evidence accumulates, but never blindly – the formula ensures we can’t exceed 1.0.

Three More Rules – Extended Example

What if a third rule also supports measles with CF = 0.3?

$$CF_{new} = 0.681 + 0.3 \times (1 - 0.681) = 0.681 + 0.3 \times 0.319 = 0.681 + 0.0957 = 0.777$$

Each additional piece of evidence adds less and less – diminishing returns, just like in real life.

Explanation Facility

WHY Query (backward chaining style – “why are you asking this?”):

Clinician: WHY?
MYCIN:     I am trying to determine whether the patient has measles.
           Rule A states:
             IF the patient has fever
             AND the patient has a rash
             THEN there is evidence (CF=0.7) that the diagnosis is measles.
           I already know the patient has fever (CF=0.8).
           I need to know about rash to evaluate this rule.

The WHY query reveals the current backward chaining goal – it shows which rule MYCIN is trying to evaluate and why it needs the requested information.

HOW Query (forward chaining style – “how did you conclude that?”):

Clinician: HOW measles?
MYCIN:     I used Rule A and Rule B.
           Rule A concluded measles (CF=0.42) based on:
             - fever (CF=0.8) [told by clinician]
             - rash (CF=0.6) [told by clinician]
           Rule B concluded measles (CF=0.45) based on:
             - recent contact with measles patient (CF=0.9) [told by clinician]
           Combined CF = 0.681

The HOW query traces the forward chain of reasoning that led to the conclusion – it shows which rules fired and what evidence was used.

This transparency is a major advantage of rule-based systems over modern neural networks.

⚖️ 权衡分析（Trade-offs & Comparisons）

Forward Chaining vs Backward Chaining