一阶逻辑推理理论

前提：
┐ ∃x(F(x)∧H(x)), ∀x(G(x)→H(x)) 结论： ∀x(G(x)→┐F(x))
前提：x（F(x)∧H(x)），x（G(x)→H(x)） 结论：x（G(x)→F(x)） 证明: （1）x（F(x)∧H(x)） 前提引入 （2）x（F(x)∨H(x)） (1)置换规则 （3）x（H(x)→ F(x)） (2)置换规则 （4）H(y)→F(y) UI（3） （5）x（G(x)→H(x)） 前提引入 （6）G(y)→H(y) UI（5） （7）G(y)→F(y) (4)(6）假言三段论 （8）x（G(x)→F(x)） UG（7）
例: 在自然数集中，设F(x)为x是奇数，G(x)是x 是偶数，则xF(x)∧xG(x)是真命题. 以下推理 是否正确： (1) xF(x)∧xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI (5) G(b) (3)EI (6) F(a)∧G(b) (4)(5)合取规则 (7) x(F(x)∧G(x)) (6)EG × (7)x(F(x)∧G(b)) (6)EG (8)xy(F(x)∧G(y)) (7)EG 在应用以上4条量词规则时，要特别注意！！
存在量词消去规则（简称EI规则） xA(x) A(c) ⑤
公式成立的条件是 1.c是使A为真的特定的个体常项； 2.c不曾在A(x)中出现过； 3.A(x)中除x外没有其他自由出现的个体变项。
例: 在自然数集中，设F(x)为x是奇数，G(x)是x 是偶数，则xF(x)∧xG(x)是真命题.以下推论 是否正确： (1) xF(x)∧xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)ES规则 (5) G(a) (3)ES规则 (6) F(a)∧G(a) (4)(5)合取规则 (7) x(F(x)∧G(x)) (6)EG规则
例: 在自然数集中，设F(x)为x是奇数，G(x)是x 是偶数，则xF(x)∧xG(x)是真命题. 以下推理 是否正确： (1) xF(x)∧xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI (5) G(b) (3)EI (6) F(a)∧G(b) (4)(5)合取规则 (7) x(F(x)∧G(x)) (6)EG
前提引入 EI ① 前提引入 UI③ ②化简 ④⑤假言推理 ②化简 ⑥⑦合取 EG⑧
将证明的步骤改为：
证明： ① x ( F(x) → G (x) ) ② F(c) → G(c) ③ x ( F(x) ∧ H(x) ) ④ F（c） ∧ H(c) ⑤ F(c) ⑥ G(c) ⑦ H(c) ⑧ G(c) ∧ H(c) ⑨ x ( G(x) ∧ H(x) )
今日内容
一阶逻辑推理理论 推理形式的定义 量词引入和消去规则 一阶逻辑下的推理证明
一阶逻辑推理理论
在一阶逻辑中，推理的形式结构仍为
A1∧A2∧…∧Ak→B 若该式是永真式，则称推理正确，称B是A1， A2，…，Ak的逻辑结论 此时将该式记为 A1∧A2∧…∧Ak B 命题逻辑中的推理规则及在一阶逻辑中的代 换实例，在一阶逻辑中仍然成立
离散数学
第10课
一阶逻辑推理理论
内容回顾
一阶逻辑合式公式及解释
一阶逻辑等值式及前束范式
上节课练习：求下列公式的前束范式
﹁(xF(x,y)yG(x,y)) xF(x,y) ∧ y G(x,y) x F(x,y) ∧ y G(x,y) x F(x,t) ∧ y G(s,y) x( F(x,t) ∧ y G(s,y)) xy( F(x,t) ∧ G(s,y))

一阶逻辑合式公式及解释
公式：字母表、项、原子公式、合式 公式、闭式 约束关系：指导变项、辖域、约束出 现、自由出现 解释、换名规则、代替规则

一阶逻辑等值式和规范型
等值的定义 命题逻辑等值式的引入 关于量词的等值式 命题的规范型：前束范式：存在但 不唯一 一阶逻辑推理论 推理形式的定义 命题逻辑推理理论的引入 量词引入和消去规则
课堂练习：
在一阶逻辑中构造下面推理的证明：
大熊猫都产在中国，欢欢是大熊猫。所 以，欢欢产在中国。
本章学习了
研究一阶逻辑的必要性 一阶逻辑的基本概念及一阶命题符号化
个体词：个体常项、个体变项、个体 域、全总个体域 谓词：谓词常项、谓词变项、特性谓 词、谓词的元数 量词：全称量词、存在量词 一阶命题的符号化
前提: x ( F(x) → G(x)) ，x ( F(x) ∧ H(x) ) 结论: x ( G(x) ∧ H(x) )
证明： ① x ( F(x) ∧ H(x) ) ② F（c） ∧ H(c) ③ x ( F(x) → G (x) ) ④ F(c) → G(c) ⑤ F(c) ⑥ G(c) ⑦ H(c) ⑧ G(c) ∧ H(c) ⑨ x ( G(x) ∧ H(x) )
课堂练习：
前提： x ( F(x) → ( G(y) ∧ R(x) ) ) ，x F(x) 结论： x ( F(x) ∧ R(x) ) 证明： ① x F(x) ② F（c） ③ x ( F(x) → ( G(y) ∧ R(x) ) ) ④ F(c) → ( G(y) ∧ R(c) ) ⑤ G(y) ∧ R(c) ⑥ R(c) ⑦ F(c) ∧ R(c) ⑧ x ( F(x) ∧ R(x) ) 前提引入 EI ① 前提引入 UI ③ ② ④假言推理 ⑤化简 ② ⑥合取 EG⑦
前提引入 UI ① 前提引入 EI ③ ②化简 ④⑤假言推理 ②化简 ⑥⑦合取 EG⑧
哪步存在错误？
例3 :请在一阶逻辑中证明下述推理的正确 性。
不存在能表示出分数的无理数，有理数都能表
示成分数，因此，有理数都不是无理数。

解： 命题符号化： 设 F(x):x为无理数；G(x):x为有理数；H(x)： x能表示成分数。
xA(x) A(y)中， y应为任意的不在A(x)中约束 出现的个体变项。
全称量词引入规则（简称UG规则） A(y) xA(x) ③ 公式成立的条件是 1.y在A(y)中自由出现，且y取任何值时A均为真 2.取代y的x不在A(y)中约束出现。
例:设定义域为实数， 取F(x,y)为x>y，A(y)=xF(x,y)=x(x>y)， A对任意给定的y都是真的。 如下推理是否正确 : ①xF(x,y) 前提引入 ②xxF(x,x) ①UG xx(x>x)是假命题，推理出错。 出错的原因是违背了条件2：取代y的x不在A(y) 中约束出现 ②zxF(x,z) ①UG √
存在量词引入规则（简称EG规则） A(c) xA(x) ④ 公式成立的条件是 1.c是特定的个体常项 ； 2.取代c的x不能已在A(c)中出现过 。 例1:设定义域为实数，取F(x,y)为x＜y， A(2)=xF(x,2)= x(x<2)，（真命题） 如下推理是否正确 : ①xF(x,2) 前提引入 ②xxF(x,x) ①EG 假命题，推理出错。出错的原因是违背了 条件2,x已在A(2)中出现过。
例: 在自然数集中，设F(x)为x是奇数，G(x)是x 是偶数，则xF(x)∧xG(x)是真命题.以下推论 是否正确： (1) xF(x)∧xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI规则 (5) G(a) (3)EI规则 × (6) F(a)∧G(a) (4)(5)合取规则 (7) x(F(x)∧G(x)) (6)EG规则 出错的原因是存在量词消去规则xA(x) A(c) 时违背了条件：c是使A为真的特定的个体常项
例：设定义域为实数，取F(x,y)为x＞y， A(x)=yF(x,y)， xA(x) xyF(x,y) 公式xA(x)是真命题。
考虑如下推理是否正确 : ①xyF(x,y) 前提引入 ②yF(y,y) ①UI规则 yF(y,y)是假命题，推理不正确 出错的原因是违背了条件：
一阶逻辑中新增加4条推理规则
消去和引入规则: 全称量词消去规则 全称量词引入规则 存在量词引入规则 存在量词消去规则
全称量词消去规则（简称UI规则） 这条规则含以下两种形式： xA(x) A(y) ① xA(x) A(c) ②
两式成立的条件是
1.x是A(x)中自由出现的个体变项； 2.在①式中，y为任意的不在A(x)中约束出现 的个体变项； 3.在②式中，c为个体域中任意的个体常项。 只有在满足上述条件时，推理规则才成立！ 在推理过程中① ，②两种形式可根据需要选 用。
一阶逻辑推理实例
命题逻辑中的推理规则及在一阶逻辑中
的代换实例，在一阶逻辑推理中仍然使 用 量词消去和引入规则
例1: 证明苏格拉底三段论“凡人都是要死的。 苏格拉底是人.所以苏格拉底是要死的。” 命题符号化：F（x）：x是人（特性谓词）； G（x）：x是要死的； a：苏格拉底 前提：x（F(x)→G(x)），F(a) 结论：G(a) 证明： （1）x（F(x)→G(x)） 前提引入 （2）F(a)→G(a) UI(1) （3）F(a) 前提引入 （4）G(a) (2)(3)假言推理
存在量词引入规则（简称EG规则） A(c) xA(x) ④ 公式成立的条件是 1.c是特定的个体常项 ； 2.取代c的x不能已在A(c)中出现过 。 例1:设定义域为实数，取F(x,y)为x＜y， A(2)=xF(x,2)= x(x<2)，（真命题） 如下推理是否正确 : ①xF(x,2) P ②yxF(x,y) EG, ① √

作业
一来自百度文库逻辑中构造下面推理的证明：
任何自然数都是整数，存在着自然数， 所以存在着整数。个体域为实数集 R。
例2:所有的有理数都是实数，有的有理数是整数。 所以，有的实数是整数。 请在一阶逻辑中证明上述推理的正确性。
证明： 命题符号化： F(x) ：x为有理数； G(x) ：x为实数； H(x) ：x为整数
前提: x ( F(x) → G(x)) ，x ( F(x) ∧ H(x) ) 结论: x ( G(x) ∧ H(x) )