12
量词消去与引入规则 UG
全称量词引入规则(UG)
A(x) xA(x)
该式成立的条件是 (1)Γ是公理和前提的合取，其中没有x的自由出现。其意
义：若从Γ可推出A(x)，那么从Γ中也可推出xA(x).
(2)在推出A(x)前提中，x必须不是自由的；且A(x)中x不
是由使用ES而引入的。
3
谓词逻辑中推理的形式结构
推理的形式结构 形式1 A1A2…AkB (*) 形式2 前提：A1, A2, … , Ak
结论： B 其中 A1,A2,…,Ak,B为谓词逻辑公式. 若(*)为永真式, 则称推理正确, 记作A1A2…Ak B
推理定律
推理定律: 谓词逻辑中永真的蕴涵式
8
注意
违反第二条： F(x,y):x>y，个体域为实数域
取A(5)= xF(x,5)—真命题 使用EG规则，若用x取代5,得xA(x)= xxF (x,x)
= xx (x>x) 假 若用y取代5,得yA(y)= yxF (x,y)
= yx (x>y) 真
9
量词消去与引入规则 EI
1.8 谓词演算的推理规则
1.8.1 谓词逻辑中推理的形式结构
重要推理定律
1.8.2 量词消去与引入规则
UI规则、UG规则、EG规则、EI规则
A(x)对y是自由的
• 如果在公式A(x)中，x不出现在量词y或 y的辖域之内，则称A(x)对y是自由的。
• 例如：B(x)= y P(y)Ｑ(x) R(z), B(x) 对y是自由的
量词消去与引入规则 UI
全称量词消去规则(UI)
xA( x) 或 xA( x)
A( y)
A(c)
成立的条件是:
•(1)A(x)对y必须是自由的。 •(2) 在第二式中, c为任意个体常元. •(3) 用y或c去取代A(x)中的自由出现的x时, 一定要在x自
由出现的一切地方进行取代.
注意
解 令 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)
①③假言推理
例2
例2 构造下述推理证明
前提：x(F(x)G(x))，xF(x)
若用5取代x,得A(5)= (5>5) 假 若用6取代x,得A(6)= (6>5) 真
11
注意
(1)个体域为自然数集合N F(x):x为奇数. G(x):x为偶数. xF(x)—真命题 xG(x)—真命题 对xF(x)使用EI规则时，取代x的只能是1，3，5等特定的 个体常元，而不能取4，6等. 对xG(x)使用EI规则时，取代x的只能是0，2，16等特定的 个体常元，而不能取3，7等.
P,前提 T,(1),US T,(2),ES
T,(3),UG T,(4),EG
14
自然推理系统F
自然推理系统F包括下述组成部分:
1. 字母表, 同谓词语言ℱ 的字母表 2. 合式公式, 同ℱ 的合式公式
3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则
重要推理定律 第一组 命题逻辑推理定律的代换实例 例如 xF(x)yG(y) xF(x) 化简律的代换实例 第二组 每个谓词逻辑基本等值式生成2个推理定律
例如 xF(x) x(F(x)), x(F(x)) xF(x)
第三组 xA(x)xB(x) x(A(x)B(x)) x(A(x)B(x)) xA(x)xB(x)
违反第一条： F(x,y):x>y，个体域为实数域 xA(x)= x yF(x,y) —真命题 使用UI规则，若用y取代x,得yF(y,y)—假命题
若用z取代x,得yF(z,y)
量词消去与引入规则 EG
存在量词引入规则(EG)
A( c )
xA( x)
该式成立的条件是：
• (1) c是使A为真的特定个体常元. • (2) 取代c的x不能在A(c)中出现过.
结论：xG(x)
证明：① xF(x)
前提引入
② x(F(x)G(x)) 前提引入
③ F(c)
①EI
④ F(c)G(c)
②UI
⑤ G(c)
③④假言推理
⑥ xG(x)
⑤EG
注意：1.必须先消存在量词
2. ⑥ xG(x) ⑤UG 行吗？为什么？
例4
例4 构造下述推理证明 前提：xF(x)xG(x) 结论：x(F(x)G(x)) 证明：① xF(x)xG(x)
15
自然推理系统F(续)
(6) 化简规则 (7) 拒取式规则 (8) 假言三段论规则 (9) 析取三段论规则 (10) 构造性二难推理规则 (11) 合取引入规则 (12) UI规则 (13) UG规则 (14) EG规则 (15) EI规则
例1
例1 证明苏格拉底三段论: “人都是要死的, 苏格拉底是人， 所以苏格拉底是要死的.”
存在量词消去规则(EI)
xA( x) A(c)
该式成立的条件是：
• (1) c是使A为真的特定的个体常元. • (2) c不在A(x)中出现. • (3) x在A(x)中自由出现, 除x之外没有其他自由
出现的个体变元
10
注意
违反第二条： F(x,y):x>y，个体域为实数域
x A(x)= x F(x,5) 对x A(x)使用EI规则，
前提引入
② yF(t,y)
①UI规则
③ F(t,c)
②EI规则
④ xF(x,c)
③UG规则
注意：③, 在F(t,y)中, 除y外, t也是自由出现, 不能使用EI 规则
附加前提引入 ①UI 前提引入 ③UI ②④假言推理 ⑤UG
4月26日 作业
P53 4 (2) 8(1)(3) 9(1)
21
例
例3 设个体域:R, F(x,y):x>y. 指出下述推理证明中的错误
前提: xyF(x,y) 真命题
结论: xF(x,c)
假命题
证明: ① xyF(x,y)
(3)在居先的步骤中，如果使用US而求得之x是自由的， 那么在后继步骤中，使用ES而引入的任何新变元都没 有在A(x)中自由出现。
• 观察下面的推理
• (1) x yP(x,y)
• (2) yP(t,y) • (3) P(t,d)
• (4) x P(x,d)
• (5) y x P(x,y)
• C(x)= yP(x,y) Q(x,y), C(x)对y不是自由 的
2
ቤተ መጻሕፍቲ ባይዱ
注：在将A(x)中的x代以y时，需要先观察 A(x)对y是否自由，如果不自由，不能代 入。
如： yP(x,y) Q(x,y)， 将x代以y得 yP(y,y) Q(y,y)，此时原来自由的x
变成约束的，故需要先将y改名。
② xy(F(x)G(y)) ③ x(F(x)G(z)) ④ F(z)G(z) ⑤ x(F(x)G(x))
前提引入 ①置换 ②UI ③UI ④UG
例5
例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)