CH2 一阶逻辑03.ppt

1、离散数学,一阶逻辑推理理论,内容回顾,一阶逻辑合式公式及解释 一阶逻辑等值式及前束范式,例:给定解释I如下： 1.DI=2，3 2.DI中特定元素a=2 3.DI上的函数f（x）为f（2）=3，f（3）=2； 4.DI上的谓词F（x）为 F（2）=0，F（3）=1； G（x,y）为 G（i,j）= 1 （i,j=2，3）； L（x,y）为 L（2,2）= L（3,3）=1； L（2,3）= L（3,2）=0； 求在解释I下，下列各式的真值: x（F（x） G（x，a） x（F（f（x） G（x，f（x） xyL（x，y）,回顾： 当个体域为有限集时， 如D=a1，a2，am， 对于任意的谓词A

2、（x），都有: xA（x） A（a1）A（a2）A（am） xA（x） A（a1）A（a2）A（am）,3. xyL（x，y） yL（2，y） yL（3，y） （L（2，2） L（2，3） （L（3，2） L（3，3） 1 1 1,练习：求下列公式的前束范式 (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),今日内容,一阶逻辑推理理论 推理形式的定义 量词引入和消去规则 一阶逻辑下的推理证明,一阶逻辑推理理论,在一阶逻辑中，推理的形

3、式结构仍为 A1A2AkB 若该式是永真式，则称推理正确，称B是A1，A2，Ak的逻辑结论 此时将该式记为 A1A2Ak B 命题逻辑中的推理规则及在一阶逻辑中的代换实例，在一阶逻辑中仍然成立,回顾 量词辖域收缩与扩张等值式: 对于含变项x约束出现的任意公式A(x)和不含x的任意公式B 1.(1) x(A(x)B) xA(x) B (2) x(A(x)B) xA(x) B (3) x(A(x)B) xA(x) B (4) x(B A(x) BxA(x) 2.(1) x(A(x)B) xA(x) B (2) x(A(x)B) xA(x) B (3) x(A(x)B) xA(x) B (4) x(

4、B A(x) BxA(x),量词分配等值式: 对于任意的公式A(x)和B(x), x(A(x)B(x) (xA(x)xB(x) 对的分配 x(A(x)B(x) (xA(x)xB(x) 对的分配 注意： 对不满足分配律 对不满足分配律,(1) xA(x)xB(x) x(A(x)B(x) (2) x(A(x)B(x) xA(x)xB(x) (3) x(A(x)B(x) xA(x)xB(x) (4) x(A(x)B(x) xA(x)xB(x),一些常用的重要推理定律,一阶逻辑中新增加4条推理规则 消去和引入规则: 全称量词消去(指定)规则 全称量词引入(推广)规则 存在量词引入( 推广)规则 存在量

5、词消去(指定)规则,U: universal E: existential G: generalization I: instantiation,全称量词消去规则（简称UI规则）这条规则含以下两种形式：xA(x) A(y) xA(x) A(c) ,两式成立的条件是 1.x是A(x)中自由出现的个体变项； 2.在式中，y为任意的不在A(x)中约束出现的个体变项； 3.在式中，c为个体域中任意的个体常项。 只有在满足上述条件时，推理规则才成立！ 在推理过程中 ，两种形式可根据需要选用。,例：设定义域为实数，取F(x,y)为xy， A(x)=yF(x,y)， xA(x) xyF(x,y) 公式xA(

6、x)是真命题。 考虑如下推理是否正确 : xyF(x,y) 前提引入 yF(y,y) UI规则 yF(y,y)是假命题，推理不正确 出错的原因是违背了条件： 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)为xy，A(y)=xF(x,y)=x(xy)， A对任意给定的y都是真的。 如下推理是否正确 : xF(x,y) 前提引入 xxF(x,x) UG xx(xx)是假命

7、题，推理出错。 出错的原因是违背了条件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)为xy， A(2)=xF(x,2)= x(x2)，（真命题） 如下推理是否正确 : xF(x,2) 前提引入 xxF(x,x) EG 假命题，推理出错。出错的原因是违背了条件2,x已在A(2)中出现过。,存在量词引入规则（简称EG规则） A(c) xA(x) 公式成立的条件是 1.c是特定的个体常项 ； 2.取代c

8、的x不能已在A(c)中出现过 。 例1:设定义域为实数，取F(x,y)为xy， A(2)=xF(x,2)= x(x2)，（真命题） 如下推理是否正确 : xF(x,2) 前提引入 yxF(x,y) EG, ,存在量词消去规则（简称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) x

9、G(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规则,例: 在自然数集中，设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规则 出错的原因是存在量词消去

10、规则 xA(x) A(c) 时违背了条件：c是使A为真的特定的个体常项,例: 在自然数集中，设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,例: 在自然数集中，设F(x)为x是奇数，G(x)是x是偶数，则xF(x)xG(x)是真命题. 以下推理是否正确： (1) xF(x)xG(x) 前提

11、引入 (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条量词规则时，要特别注意！,一阶逻辑推理实例,命题逻辑中的推理规则及在一阶逻辑中的代换实例，在一阶逻辑推理中仍然使用 量词消去和引入规则,例: 证明苏格拉底三段论“凡人都是要死的。苏格拉底是人.所以苏格拉底是要死的。” 命题符号化：F（x）：x是人（特性谓词）； G（x）：x是

12、要死的； a：苏格拉底 前提：x（F(x)G(x)），F(a) 结论：G(a) 证明： （1）x（F(x)G(x)） 前提引入 （2）F(a)G(a) UI(2) （3）F(a) 前提引入 （4）G(a) (2)(3)假言推理,例1:所有的有理数都是实数，有的有理数是整数。所以，有的实数是整数。 请在一阶逻辑中证明上述推理的正确性。 证明： 命题符号化： 令F(x) ：x为有理数； G(x) ：x为实数； H(x) ：x为整数 前提: x ( F(x) G(x) ， x ( F(x) H(x) ) 结论: x ( G(x) H(x) ),例1:所有的有理数都是实数，有的有理数是整数。所以，有的

13、实数是整数。 请在一阶逻辑中证明上述推理的正确性。 证明： 命题符号化： F(x) ：x为有理数； G(x) ：x为实数； H(x) ：x为整数,前提: x ( F(x) G(x) ，$x ( F(x) H(x) ) 结论: $ x ( G(x) H(x) ),前提: x ( F(x) G(x) ，$x ( F(x) H(x) ) 结论: $ x ( G(x) H(x) ),证明： $x ( F(x) H(x) ) 前提引入 F（c） H(c) EI x ( F(x) G (x) ) 前提引入 F(c) G(c) UI F(c) 化简 G(c) 假言推理 H(c) 化简 G(c) H(c) 合

14、取 $ x ( G(x) H(x) ) EG,将证明的步骤改为：,证明： x ( F(x) G (x) ) 前提引入 F(c) G(c) UI $x ( F(x) H(x) ) 前提引入 F（c） H(c) EI F(c) 化简 G(c) 假言推理 H(c) 化简 G(c) H(c) 合取 $ x ( G(x) H(x) ) EG 哪步存在错误？,例2 :请在一阶逻辑中证明下述推理的正确性。,不存在能表示成分数的无理数，有理数都能表示成分数，因此，有理数都不是无理数。 解： 命题符号化： 设 F(x):x为无理数；G(x):x为有理数；H(x)：x能表示成分数。 前提： x(F(x)H(x),

15、 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）,课堂练习： 前提： x ( F(x) ( G(y) R(x) ) ) ，$x F(x) 结论： $ x ( F(x) R(x) ),证明： $x F(x) 前提引入 F（c） EI x ( F(x) ( G(y) R(x) ) ) 前提引入 F(c) ( G(y) R(c) ) UI G(y) R(c) 假言推理 R(c) 化简 F(c) R(c) 合取 $ x ( F(x) R(x) ) EG,本章学习了,研究一阶逻辑的必要性 一阶逻辑的基本概念及一阶命题符号化 个体词：个体常项、个体变项、个体域、全总个体域 谓词：谓词常项、谓词变项、特性谓词、谓词的元数 量词：