自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理 感兴趣的可以阅读《GEB－－一条永恒的金带》
13
14
有一位理发师声称，他给所有不给自己理发的 人理发
爱皮梅尼特是一个克里特岛人。他说：“所有 的克里特岛人都撤谎。”
第一类集合不能以自己为元素，也就是说自己 不能属于自己，我们称为r型。第二类集合可以 以自己为元素，我们称为s型。
第三章:命题逻辑的推理理论
主要内容 推理的形式结构 推理的正确与错误 推理的形式结构 判断推理正确的方法 推理定律
自然推理系统P 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法
1
3.1 推理形式结构
逻辑(语义)蕴涵：给定A1,…,Ak和B
❖符号：{A1,…,Ak} ⊨ B ❖对任意赋值v:
• 如果v(Ai)=T,则v(B)=T • 或者存在Ai使得v(Ai)=F
❖称由前提A1,…,Ak 推出结论B的推理是有效的 ❖B为有效结论
讨论
❖蕴涵跟蕴涵式的关系？ ❖注意: 推理正确不能保证结论一定正确
2
3.1 推理形式结构
例子
❖ {p, p q} ⊨ q ❖ {p, q p} ⊨ q
4
3.1 推理形式结构
蕴涵元符号： A1…Ak B 代表 {A1,…,Ak} ⊨ B 推理形式结构
❖前提A1,…,Ak ❖结论：B
5
3.1 推理形式结构
判断推理是否正确方法
① 真值表法 ② 等值演算法 ③ 主析取范式法
6
推理实例
例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号.
附加律 化简律 假言推理 拒取式 析取三段论 假言三段论 等价三段论 构造性二难 构造性二难（特殊形式） 破坏性二难
9
3.1 推理形式结构
推理定律
A (A B) (A B) A (A B) A B (A B) B A (A B) B A (A B) (B C) (A C) (A B) (B C) (A C) (A B) (C D) (A C) (B D) (A B) ( A B) B (A B) (C D) ( B D) ( A C)
解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构: (pq)pq
用等值演算法 (pq)pq
((pq)p)q pqq 1 由定理3.1可知推理正确
7
7
推理实例
(2) 推理的形式结构: (pq)qp 用主析取范式法 (pq)qp (pq)qp ((pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确
证明《数学原理》所定义的系统既是一致的(无 矛盾)又是完备的(该系统的理论框架中容纳了 每个正确的数论命题)。这就是数学史上著名的 希尔伯特纲领。
T
11
3.2 自然推理系统P
从一组已知为真的事实出发，直接运用经典逻 辑推理规则推出结论的过程
为什么要自然演绎(natural deduction)？ 给出验证 A1…Ak B 的推理过程 需要引入证明的概念 自然演绎模拟人类的推理
12
3.2 自然推理系统P
定义3.2 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作 R(I). 记I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I)>是 I 的 形式语言系统, <AX(I),R(I)> 是 I 的形式演算系统.
8
8
3.1 推理形式结构
推理定律
A (A B) (A B) A (A B) A B (A B) B A (A B) B A (A B) (B C) (A C) (A B) (B C) (A C) (A B) (C D) (A C) (B D) (A B) ( A B) B (A B) (C D) ( B D) ( A C)
p q p(pq) q p(q p)
q
F FF
FF
F
F TF
TF
T
TFF
FT
F
T TT
TT
T
3
3.1 推理形式结构
定理：{A1,…,Ak} ⊨ B 当且仅当 A1…Ak B 为重言式
证明 必要性：任意v, v(Ai)=T则v(B)=T 所以v(A1…Ak B)=T 充分性：任意v, v(A1…Ak B)=T 如果v(Ai)=T则v(B)=T
附加律 化简律 假言推理 拒取式 析取三段论 假言三段论 等价三段论 构造性二难 构造性二难（特殊形式） 破坏性二难
10
3.1 推理形式结构
证明：(A B) (B C) (A C) ((A B) (B C)) (A C)
((A B) (B C)) (A C) ((A B) (B C)) (A C) ((A B) (B C)) (A C) ((A B) (B C)) (A C) ((A B) A) ((B C) C)) (B A) (B C)
