(3) P(e)
(4) P(e) Q(e)
(5) Q(e)
(6) x Q(x)
(3)(4)
(5) Q(e)
(6) x Q(x)
✘
(3)(4)
21/51
小结 谓词演算的推理理论
推理的形式结构 重要的推理定律 推理规则 构造证明 附加前提证明法
22
7
例 下面推理是否正确？
设前提为∀x∃yF（x，y）， （1） ∀x∃yF（x，y） 前提引入 （2） ∃y F（y，y） 全称量词消去
解 推理并不正确。 如果给定解释I：个体域为实数集， F（x，y）：x＞y。 则 ∀x∃yF（x，y）意为 “对于每个实数x，均存在着比之更小的实数y”， 这是一个真命题。 而∃yF（y，y）意为 “存在着比自己小的实数”，是假命题。 之所以出现这样的错误,是因为∃yF（x，y） 中有1个自由变 元x, 而∃y F（y，y）中无自由变元。
20
附加前提引入 ①UI 前提引入 ③UI ②④假言推理 ⑤UG
例 (p55) x(P(x)Q(x))(xP(x)xQ(x))
解： 解：
(1) x(P(x) Q(x))
(2) x P(x)
(1) x(P(x) Q(x))
(2) x P(x)
(3) P(e) Q(e)
(4) P(e)
6
(2)结论引入规则 (4)假言推理规则 (6)化简规则 (8)假言三段论规则 (10)构造性二难推理规则
推理规则(续)
(12) 全称量词消去规则（简记为UI规则或UI）
xA( x ) A( y)
或
xA( x ) A( c )
两式成立的条件是： 在第一式中，取代x的y应为任意的不在A(x)中 约束出现的个体变项. 在第二式中，c为任意个体常项. 用y或c去取代A(x)中的自由出现的x时，一定要 在x自由出现的一切地方进行取代.
14
构造推理证明(续)
例2 乌鸦都不是白色的. 北京鸭是白色的. 因此，北京鸭不是乌鸦. 令 F(x): x是乌鸦, G(x): x是北京鸭, H(x): x是白色的 前提：x(F(x)H(x))， x(G(x)H(x)) 结论：x(G(x)F(x))
15
前提：x(F(x)H(x))，x(G(x)H(x)) 结 论：x(G(x)F(x))
11
例如，设(ｘ)Ｐ(ｘ)和(ｘ)Ｑ(ｘ)都真， 则对于某些ｃ和某些ｄ，可以断定Ｐ(ｃ)∧Ｑ (ｄ)为真，但却不能断定Ｐ(ｃ)∧Ｑ(ｃ)为真 或Ｐ(ｄ)∧Ｑ(ｄ)为真。 例 考察∃yF（x，y） 存在量词消去能不能得到下式: F（x，c）
F（x，c）表示对常元c与任意变元x成立, 错误
在于: c可能与x有关的.
8/51
推理规则(续)
(13) 全称量词引入规则（简记为UG规则或UG）
A( y ) xA( x )
该式成立的条件是： 无论A(y)中自由出现的个体变项y取何值，A(y) 应该均为真. 取代自由出现的y的x，也不能在A(y)中约束出 现.
9
推理规则(续)
(14) 存在量词引入规则（简记为EG规则或EG）
18
例 在自然推理系统中构造下面推理的证明 前提： xP(x)→xQ(x) 结论： x(P(x)→Q(x))
证明: (1) xP(x)→xQ(x) (2) xP(x) (3) P(a)→xQ(x) (4) P(a) (5) xQ(x)
✘
前提引入 前提引入? 去存在量词(1) ? 去全称量词(2) (3)(4)
第二组 由基本等值式生成 如 由 xA(x)xA(x) 生成 xA(x)xA(x), xA(x)xA(x), … 第三组 xA(x)xB(x)x(A(x)B(x)) x(A(x)B(x))xA(x)xB(x)
5
推理规则
(1)前提引入规则 (3)置换规则 (5)附加规则 (7)拒取式规则 (9)析取三段论规则 (11)合取引入规则
13/51
构造推理证明
例1 证明苏格拉底三段论: “人都是要死的, 苏格拉 底是人，所以苏格拉底是要死的.”
令 F(x): x是人, G(x): x是要死的, a: 苏格拉底 前提：x(F(x)G(x))，F(a) 结论：G(a) 证明：① F(a) 前提引入 ② x(F(x)G(x)) 前提引入 ③ F(a)G(a) ②UI ④ G(a) ①③假言推理 注意：使用UI时，用a取代x .
17前提：xF(x)xG(x) 结论：x(F(x)G(x)) 证明：① xF(x)xG(x) ② xy(F(x)G(y)) ③ x(F(x)G(z)) ④ F(z)G(z) ⑤ x(F(x)G(x))
前提引入 ①置换 ②UI ③UI ④UG
(2)并非是结论的前件 (3)错误使用规则，(1)并非前束范式
19/51
构造推理证明(续)
例5 构造下述推理证明 前提：x(F(x)G(x)) 结论：xF(x)xG(x) 证明：① xF(x) ② F(y) ③ x(F(x)G(x)) ④ F(y)G(y) ⑤ G(y) ⑥ xG(x) 本题可以使用附加前提证明法
A( c ) xA( x )
该式成立的条件是： c是使A为真的特定个体常项. 取代c的x不能在A(c)中出现过.
10
推理规则(续)
(15) 存在量词消去规则（简记为EI规则或EI）
xA( x ) A( c )
闭 式
该式成立的条件是： c是使A为真的特定的个体常项. c不在A(x)中出现. 若A(x)中除自由出现的x外，还有其他自由出现 的个体变项，此规则不能使用.
✘
12
例 下面推理是否正确？
设前提为∀x∃yF（x，y）， （1） ∀x∃yF（x，y） （2） ∃yF（t，y） （3） F（t，c） （4） ∀xF（x，c） （5） ∃yxF（x，y）
前提引入 全称量词消去 存在量词消去 全称量词引入 存在量词引入
解： 推理并不正确。 如果给定解释I：个体域为实数集，F(x,y)：x＞y。 则 x∃yF（x，y）为真， 而∃y xF（x，y）意为“存在着最小实数”， 是假命题，故知推理不正确。 之所以出现这样的错误，是在第（3）步中， ∃yF（t，y ）非闭式（含有自由变元t)。
证明： ① x(F(x)H(x)) ② F(y)H(y) ③ x(G(x)H(x)) ④ G(y)H(y) ⑤ H(y)G(y) ⑥ F(y)G(y) ⑦ G(y)F(y) ⑧ x(G(x)F(x))
16
前提引入 ①UI 前提引入 ③UI ④置换 ②⑤假言三段论 ⑥置换 ⑦UG
2
重要的推理定律
第一组 命题逻辑推理定律代换实例 如 xF(x)yG(y)xF(x)为化简律代换实例. xF(x)yG(y)的代换实例为pq 化简律: (pq) p
3
推理定律——重言蕴涵式
重要的推理定律 A (AB) (AB) A (AB)A B (AB)B A (AB)B A (AB)(BC) (AC) (AB)(BC) (AC) (AB)(CD)(AC) (BD) 附加律 化简律 假言推理 拒取式 析取三段论 假言三段论 等价三段 构造性二难
构造推理证明(续)
例3 构造下述推理证明 前提：x(F(x)G(x))，xF(x) 结论：xG(x) 证明：① xF(x) 前提引入 ② x(F(x)G(x)) 前提引入 ③ F(c) ①EI ④ F(c)G(c) ②UI ⑤ G(c) ③④假言推理 ⑥ xG(x) ⑤EG 注意：必须先消存在量词
第5讲 谓词演算的推理理论
推理的形式结构 重要的推理定律 推理规则 构造证明 附加前提证明法
1
推理
推理的形式结构有两种： 第一种 A1A2…AkB (*) 第二种 前提：A1，A2，…，Ak 结论： B 其中 A1,A2,…,Ak,B为一阶逻辑公式. 若(*)为永真式, 则称推理正确, 否则称推理不正确. 判断方法: 真值表法, 等值演算法, 主析取范式法及构造证 明法. 前3种方法采用第一种形式结构, 构造证明 法采用第二种形式结构.