第6章：知识表示与推理（Knowledge Representation and Reasoning）
一、导读
1.1 本章学习目标
第6章介绍了AI的核心问题之一——如何用形式化语言表示知识并进行推理。知识表示是AI系统理解和操作世界的基础。没有有效的知识表示，再强大的搜索算法也无用武之地。
本章的核心学习目标包括：
- 理解知识表示的基本要求：什么是一个好的知识表示？可表达性、推理效率、可获取性之间的权衡。
- 掌握命题逻辑：命题逻辑的语法、语义、推理方法（模型检查、归结）。
- 掌握一阶逻辑：一阶逻辑的对象、关系、函数、量词，以及如何用一阶逻辑表示复杂知识。
- 理解知识库的构建：如何将自然语言知识转化为逻辑公式，如何组织和管理知识库。
- 掌握推理方法：前向链、后向链、归结原理等推理方法。
- 了解知识工程：构建大规模知识库的方法和挑战。
1.2 为什么第六章如此重要
知识表示是AI的"语言"。搜索算法是AI的"引擎"，但引擎需要燃料——这个燃料就是知识。如何表示知识决定了AI系统能做什么、不能做什么。
命题逻辑和一阶逻辑是AI知识表示的基础。虽然现代AI越来越多地使用统计方法，但逻辑推理的思想——形式化、精确、可验证——仍然是AI的核心。知识图谱、本体论、语义网等现代技术都建立在逻辑推理的基础之上。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
为什么需要形式化知识表示？ 自然语言有什么缺陷使得我们不能直接用它来推理？
命题逻辑的局限性：命题逻辑能表达什么？不能表达什么？为什么我们需要一阶逻辑？
推理的计算复杂性：命题逻辑的可满足性问题是 NP 完全的，这意味着什么？
知识获取瓶颈：为什么将人类知识编码为逻辑公式如此困难？
逻辑推理与现代AI的关系：在大语言模型时代，逻辑推理还有价值吗？
二、核心概念详解
2.1 知识表示基础
2.1.1 知识表示的要求
一个好的知识表示应该满足：
- 可表达性：能表达领域中的重要知识
- 推理效率：支持高效的推理算法
- 可获取性：知识易于获取和修改
- 明确性：知识的含义是明确的、无歧义的
python
class KnowledgeRepresentation:
def __init__(self, name):
self.name = name
self.expressiveness = 0
self.efficiency = 0
self.tractability = 0
def evaluate(self):
print(f"表示方法: {self.name}")
print(f" 可表达性: {self.expressiveness}/10")
print(f" 推理效率: {self.efficiency}/10")
print(f" 可处理性: {self.tractability}/10")
propositional = KnowledgeRepresentation("命题逻辑")
propositional.expressiveness = 3
propositional.efficiency = 9
propositional.tractability = 8
first_order = KnowledgeRepresentation("一阶逻辑")
first_order.expressiveness = 8
first_order.efficiency = 4
first_order.tractability = 3
propositional.evaluate()
first_order.evaluate()2.2 命题逻辑
2.2.1 语法
命题逻辑的基本元素：
- 原子命题：P, Q, R, ...（不可再分的陈述句）
- 逻辑连接词：¬（非）、∧（与）、∨（或）、→（蕴含）、↔（等价）
- 复合命题：由原子命题和连接词组合而成
python
class Proposition:
def __init__(self, symbol):
self.symbol = symbol
def __repr__(self):
return self.symbol
def __eq__(self, other):
return isinstance(other, Proposition) and self.symbol == other.symbol
def __hash__(self):
return hash(self.symbol)
class Not:
def __init__(self, operand):
self.operand = operand
def __repr__(self):
return f"¬{self.operand}"
class And:
def __init__(self, *operands):
self.operands = operands
def __repr__(self):
return f"({' ∧ '.join(str(o) for o in self.operands)})"
class Or:
def __init__(self, *operands):
self.operands = operands
def __repr__(self):
return f"({' ∨ '.join(str(o) for o in self.operands)})"
class Implies:
def __init__(self, antecedent, consequent):
self.antecedent = antecedent
self.consequent = consequent
def __repr__(self):
return f"({self.antecedent} → {self.consequent})"
class Iff:
def __init__(self, left, right):
self.left = left
self.right = right
def __repr__(self):
return f"({self.left} ↔ {self.right})"
# 构建命题公式
P = Proposition('P')
Q = Proposition('Q')
R = Proposition('R')
formula = And(Implies(P, Q), Implies(Q, R))
print(f"公式: {formula}")2.2.2 语义
命题逻辑的语义由真值表定义。给定一组原子命题的真值赋值（模型），可以计算任何复合命题的真值。
python
def evaluate_proposition(formula, model):
if isinstance(formula, Proposition):
return model.get(formula.symbol, False)
elif isinstance(formula, Not):
return not evaluate_proposition(formula.operand, model)
elif isinstance(formula, And):
return all(evaluate_proposition(op, model) for op in formula.operands)
elif isinstance(formula, Or):
return any(evaluate_proposition(op, model) for op in formula.operands)
elif isinstance(formula, Implies):
return (not evaluate_proposition(formula.antecedent, model) or
evaluate_proposition(formula.consequent, model))
elif isinstance(formula, Iff):
return (evaluate_proposition(formula.left, model) ==
evaluate_proposition(formula.right, model))
return False
# 真值表生成
def truth_table(formula, symbols):
print(f"{' '.join(symbols)} | {formula}")
print("-" * 40)
for i in range(2 ** len(symbols)):
model = {}
for j, s in enumerate(symbols):
model[s] = bool(i & (1 << (len(symbols) - 1 - j)))
result = evaluate_proposition(formula, model)
values = [str(int(model[s])) for s in symbols]
print(f"{' '.join(values)} | {int(result)})
P, Q = Proposition('P'), Proposition('Q')
truth_table(Implies(P, Q), ['P', 'Q'])2.2.3 推理方法
模型检查：枚举所有可能的模型，检查公式是否在所有模型中为真（有效性）或至少在一个模型中为真（可满足性）。
python
def is_valid(formula, symbols):
for i in range(2 ** len(symbols)):
model = {}
for j, s in enumerate(symbols):
model[s] = bool(i & (1 << (len(symbols) - 1 - j)))
if not evaluate_proposition(formula, model):
return False
return True
def is_satisfiable(formula, symbols):
for i in range(2 ** len(symbols)):
model = {}
for j, s in enumerate(symbols):
model[s] = bool(i & (1 << (len(symbols) - 1 - j)))
if evaluate_proposition(formula, model):
return True
return False
def entails(kb, alpha, symbols):
return is_valid(Implies(kb, alpha), symbols)
# 示例：验证推理规则
P, Q, R = Proposition('P'), Proposition('Q'), Proposition('R')
modus_ponens = Implies(And(P, Implies(P, Q)), Q)
print(f"肯定前件式是有效的: {is_valid(modus_ponens, ['P', 'Q'])}")
hypothetical_syllogism = Implies(
And(Implies(P, Q), Implies(Q, R)),
Implies(P, R)
)
print(f"假言三段论是有效的: {is_valid(hypothetical_syllogism, ['P', 'Q', 'R'])}")归结原理：将公式转化为合取范式（CNF），然后通过归结规则进行推理。
python
def to_cnf(formula):
formula = eliminate_iff(formula)
formula = eliminate_implies(formula)
formula = move_not_inward(formula)
formula = distribute_or_over_and(formula)
return formula
def eliminate_iff(formula):
if isinstance(formula, Iff):
left = eliminate_iff(formula.left)
right = eliminate_iff(formula.right)
return And(Implies(left, right), Implies(right, left))
elif isinstance(formula, And):
return And(*[eliminate_iff(op) for op in formula.operands])
elif isinstance(formula, Or):
return Or(*[eliminate_iff(op) for op in formula.operands])
elif isinstance(formula, Not):
return Not(eliminate_iff(formula.operand))
elif isinstance(formula, Implies):
return Implies(eliminate_iff(formula.antecedent),
eliminate_iff(formula.consequent))
return formula
def eliminate_implies(formula):
if isinstance(formula, Implies):
left = eliminate_implies(formula.antecedent)
right = eliminate_implies(formula.consequent)
return Or(Not(left), right)
elif isinstance(formula, And):
return And(*[eliminate_implies(op) for op in formula.operands])
elif isinstance(formula, Or):
return Or(*[eliminate_implies(op) for op in formula.operands])
elif isinstance(formula, Not):
return Not(eliminate_implies(formula.operand))
return formula
def move_not_inward(formula):
if isinstance(formula, Not):
inner = formula.operand
if isinstance(inner, Not):
return move_not_inward(inner.operand)
elif isinstance(inner, And):
return Or(*[move_not_inward(Not(op)) for op in inner.operands])
elif isinstance(inner, Or):
return And(*[move_not_inward(Not(op)) for op in inner.operands])
elif isinstance(formula, And):
return And(*[move_not_inward(op) for op in formula.operands])
elif isinstance(formula, Or):
return Or(*[move_not_inward(op) for op in formula.operands])
return formula
def distribute_or_over_and(formula):
if isinstance(formula, Or):
operands = [distribute_or_over_and(op) for op in formula.operands]
conjuncts = [op for op in operands if isinstance(op, And)]
disjuncts = [op for op in operands if not isinstance(op, And)]
if conjuncts:
result = conjuncts[0]
for c in conjuncts[1:]:
new_operands = []
for r_op in result.operands:
for c_op in c.operands:
new_operands.append(distribute_or_over_and(Or(r_op, c_op)))
result = And(*new_operands)
if disjuncts:
inner = Or(*disjuncts) if len(disjuncts) > 1 else disjuncts[0]
new_operands = []
for r_op in result.operands:
new_operands.append(distribute_or_over_and(Or(r_op, inner)))
return And(*new_operands)
return result
return Or(*operands) if operands else formula
elif isinstance(formula, And):
return And(*[distribute_or_over_and(op) for op in formula.operands])
return formula
# 归结推理
def resolve(clause1, clause2):
tautologies = []
for lit1 in clause1:
for lit2 in clause2:
if isinstance(lit1, Not) and lit1.operand == lit2:
resolvent = [l for l in clause1 if l != lit1] + [l for l in clause2 if l != lit2]
tautologies.append(resolvent)
elif isinstance(lit2, Not) and lit2.operand == lit1:
resolvent = [l for l in clause1 if l != lit1] + [l for l in clause2 if l != lit2]
tautologies.append(resolvent)
return tautologies
def resolution_proves(kb_clauses, alpha_clauses):
all_clauses = kb_clauses + [list(clause) for clause in alpha_clauses]
new_clauses = set()
while True:
n = len(all_clauses)
pairs = [(all_clauses[i], all_clauses[j])
for i in range(n) for j in range(i+1, n)]
for (ci, cj) in pairs:
resolvents = resolve(ci, cj)
for res in resolvents:
if not res:
return True
res_set = tuple(sorted(str(l) for l in res))
if res_set not in new_clauses:
new_clauses.add(res_set)
all_clauses.append(res)
if len(new_clauses) == 0:
return False2.3 一阶逻辑
2.3.1 语法
一阶逻辑扩展了命题逻辑，引入了：
- 对象：具体的实体（人、物、事件）
- 关系：对象之间的关系
- 函数：从对象到对象的映射
- 量词：全称量词 ∀（对所有）和存在量词 ∃（存在）
python
class Term:
pass
class Constant(Term):
def __init__(self, name):
self.name = name
def __repr__(self):
return self.name
class Variable(Term):
def __init__(self, name):
self.name = name
def __repr__(self):
return self.name
class Function(Term):
def __init__(self, name, *args):
self.name = name
self.args = args
def __repr__(self):
return f"{self.name}({', '.join(str(a) for a in self.args)})"
class Predicate:
def __init__(self, name, *args):
self.name = name
self.args = args
def __repr__(self):
return f"{self.name}({', '.join(str(a) for a in self.args)})"
class ForAll:
def __init__(self, var, body):
self.var = var
self.body = body
def __repr__(self):
return f"∀{self.var} {self.body}"
class Exists:
def __init__(self, var, body):
self.var = var
self.body = body
def __repr__(self):
return f"∃{self.var} {self.body}"
# 示例：用一阶逻辑表示知识
# "所有人都会死"
# ∀x (Person(x) → Mortal(x))
x = Variable('x')
person = Predicate('Person', x)
mortal = Predicate('Mortal', x)
all_mortal = ForAll(x, Implies(person, mortal))
print(f"所有人都会死: {all_mortal}")
# "苏格拉底是人"
socrates = Constant('Socrates')
socrates_is_person = Predicate('Person', socrates)
print(f"苏格拉底是人: {socrates_is_person}")2.3.2 语义
一阶逻辑的语义基于模型，模型包含：
- 论域（Domain）：所有对象的集合
- 解释（Interpretation）：为每个常量指定论域中的对象，为每个谓词指定论域上的关系，为每个函数指定论域上的映射
python
class FOLModel:
def __init__(self, domain):
self.domain = domain
self.constants = {}
self.predicates = {}
self.functions = {}
def add_constant(self, name, value):
self.constants[name] = value
def add_predicate(self, name, func):
self.predicates[name] = func
def add_function(self, name, func):
self.functions[name] = func
def evaluate_term(self, term):
if isinstance(term, Constant):
return self.constants[term.name]
elif isinstance(term, Variable):
return None
elif isinstance(term, Function):
args = [self.evaluate_term(a) for a in term.args]
return self.functions[term.name](*args)
return None
def evaluate_predicate(self, pred, assignment=None):
args = []
for a in pred.args:
if isinstance(a, Variable) and assignment and a.name in assignment:
args.append(assignment[a.name])
else:
args.append(self.evaluate_term(a))
return self.predicates[pred.name](*args)
def evaluate_formula(self, formula, assignment=None):
if isinstance(formula, Predicate):
return self.evaluate_predicate(formula, assignment)
elif isinstance(formula, ForAll):
for obj in self.domain:
new_assignment = dict(assignment) if assignment else {}
new_assignment[formula.var.name] = obj
if not self.evaluate_formula(formula.body, new_assignment):
return False
return True
elif isinstance(formula, Exists):
for obj in self.domain:
new_assignment = dict(assignment) if assignment else {}
new_assignment[formula.var.name] = obj
if self.evaluate_formula(formula.body, new_assignment):
return True
return False
elif isinstance(formula, And):
return all(self.evaluate_formula(op, assignment) for op in formula.operands)
elif isinstance(formula, Or):
return any(self.evaluate_formula(op, assignment) for op in formula.operands)
elif isinstance(formula, Not):
return not self.evaluate_formula(formula.operand, assignment)
elif isinstance(formula, Implies):
return (not self.evaluate_formula(formula.antecedent, assignment) or
self.evaluate_formula(formula.consequent, assignment))
return False
# 构建模型验证推理
model = FOLModel(['Socrates', 'Plato', 'Aristotle'])
model.add_constant('Socrates', 'Socrates')
model.add_predicate('Person', lambda x: x in ['Socrates', 'Plato', 'Aristotle'])
model.add_predicate('Mortal', lambda x: x in ['Socrates', 'Plato', 'Aristotle'])
x = Variable('x')
formula = ForAll(x, Implies(Predicate('Person', x), Predicate('Mortal', x)))
print(f"所有人都会死: {model.evaluate_formula(formula)}")
socrates_mortal = Predicate('Mortal', Constant('Socrates'))
print(f"苏格拉底会死: {model.evaluate_formula(socrates_mortal)}")2.3.3 知识表示示例
python
class KnowledgeBase:
def __init__(self):
self.sentences = []
def tell(self, sentence):
self.sentences.append(sentence)
def ask(self, query):
return self.sentences
# 家族关系知识库
family_kb = KnowledgeBase()
# 基本事实
family_kb.tell(Predicate('Male', Constant('John')))
family_kb.tell(Predicate('Female', Constant('Mary')))
family_kb.tell(Predicate('Parent', Constant('John'), Constant('Tom')))
family_kb.tell(Predicate('Parent', Constant('Mary'), Constant('Tom')))
family_kb.tell(Predicate('Married', Constant('John'), Constant('Mary')))
# 规则
x = Variable('x')
y = Variable('y')
z = Variable('z')
# 如果 x 是 y 的父母，y 是 z 的父母，则 x 是 z 的祖父母
family_kb.tell(ForAll(x, ForAll(y, ForAll(z,
Implies(And(Predicate('Parent', x, y), Predicate('Parent', y, z)),
Predicate('Grandparent', x, z))
))))
# 如果 x 是 y 的父母且 x 是男性，则 x 是 y 的父亲
family_kb.tell(ForAll(x, ForAll(y,
Implies(And(Predicate('Parent', x, y), Predicate('Male', x)),
Predicate('Father', x, y))
)))
print("知识库包含以下句子:")
for s in family_kb.sentences:
print(f" {s}")2.4 推理方法
2.4.1 前向链与后向链
python
def forward_chain(kb_facts, kb_rules, max_iterations=100):
facts = set(str(f) for f in kb_facts)
changed = True
iteration = 0
while changed and iteration < max_iterations:
changed = False
iteration += 1
for rule in kb_rules:
if isinstance(rule, ForAll):
new_facts = apply_rule(rule, facts)
for f in new_facts:
if f not in facts:
facts.add(f)
changed = True
return facts
def apply_rule(rule, facts):
new_facts = []
return new_facts
def backward_chain(kb, query, depth=0, max_depth=10):
if depth > max_depth:
return False
if str(query) in kb:
return True
return False2.5 知识工程
2.5.1 知识获取
知识获取是将人类专家的知识转化为机器可处理的形式的过程。主要方法：
- 知识 elicitation：通过访谈、观察等方式从专家那里获取知识
- 知识编码：将获取的知识编码为形式化表示
- 知识验证：检查知识库的一致性和完备性
python
class KnowledgeEngineer:
def __init__(self, domain):
self.domain = domain
self.ontology = {}
self.rules = []
self.facts = []
def define_ontology(self, categories, relations):
self.ontology['categories'] = categories
self.ontology['relations'] = relations
def add_rule(self, condition, conclusion):
self.rules.append((condition, conclusion))
def add_fact(self, fact):
self.facts.append(fact)
def validate(self):
issues = []
for rule in self.rules:
if not self._check_types(rule):
issues.append(f"类型错误: {rule}")
return issues
def _check_types(self, rule):
return True
def report(self):
print(f"领域: {self.domain}")
print(f"本体类别: {len(self.ontology.get('categories', []))}")
print(f"规则数: {len(self.rules)}")
print(f"事实数: {len(self.facts)}")
# 医疗诊断知识工程
medical_ke = KnowledgeEngineer("医疗诊断")
medical_ke.define_ontology(
categories=['疾病', '症状', '检查', '治疗'],
relations=['引起', '表现为', '需要', '禁忌']
)
medical_ke.add_rule(
"发热 AND 咳嗽 > 3天",
"可能感染"
)
medical_ke.report()三、实战案例
3.1 案例一：Wumpus 世界
python
class WumpusWorld:
def __init__(self, size=4):
self.size = size
self.kb = KnowledgeBase()
self._init_kb()
def _init_kb(self):
for x in range(1, self.size + 1):
for y in range(1, self.size + 1):
self.kb.tell(f"At({x},{y})" if (x, y) == (1, 1) else f"NotAt({x},{y})" if (x, y) != (1, 1) else "")
self.kb.tell("NotPit(1,1)")
self.kb.tell("NotPit(1,2)")
self.kb.tell("NotPit(2,1)")
self.kb.tell("Breeze(1,2)")
self.kb.tell("Breeze(2,1)")
def query(self, query_str):
return query_str in [str(s) for s in self.kb.sentences]
world = WumpusWorld()
print(f"(1,1) 有坑吗? {world.query('NotPit(1,1)')}")
print(f"(2,2) 有坑吗? {world.query('Pit(2,2)')}")3.2 案例二：简单的定理证明器
python
class SimpleTheoremProver:
def __init__(self):
self.axioms = []
self.theorems = []
def add_axiom(self, formula):
self.axioms.append(formula)
def prove(self, goal, depth=0, max_depth=20):
if depth > max_depth:
return False
if goal in self.axioms:
self.theorems.append(goal)
return True
return False
def report(self):
print(f"公理数: {len(self.axioms)}")
print(f"已证明定理数: {len(self.theorems)}")
prover = SimpleTheoremProver()
P, Q = Proposition('P'), Proposition('Q')
prover.add_axiom(Implies(P, Q))
prover.add_axiom(P)
print(f"证明 Q: {prover.prove(Q)}")
prover.report()四、本章小结
本章介绍了知识表示与推理的核心概念。命题逻辑提供了基本的推理框架，一阶逻辑通过引入对象、关系和量词大大增强了表达能力。我们学习了模型检查、归结、前向链和后向链等推理方法。
核心知识点回顾：
- 知识表示需要在可表达性和推理效率之间权衡
- 命题逻辑简单但表达力有限
- 一阶逻辑通过对象、关系、量词增强了表达力
- 归结原理是一种完备的推理方法
- 知识工程是构建大规模知识库的系统方法
五、思考与练习
思考题
逻辑的局限性：一阶逻辑能表达所有数学知识吗？Gödel 不完备性定理对此有什么启示？
知识表示的选择：在什么情况下应该使用命题逻辑？什么情况下需要一阶逻辑？什么时候应该考虑其他表示方法（如概率模型）？
编程练习
实现 DPLL 算法：DPLL 是一种高效的命题逻辑可满足性算法。实现它并与暴力枚举比较性能。
构建家庭关系知识库：用一阶逻辑表示家庭关系（父母、祖父母、兄弟姐妹等），并实现推理功能。
实现简单的归结证明器：将知识库转化为 CNF，实现归结推理，证明给定的查询。