第3章 一阶逻辑

1、1第第2 2章章 命题逻辑命题逻辑( (复习复习) )2.3 2.3 范式范式2.4 2.4 命题逻辑推理理论命题逻辑推理理论第第3 3章章 一阶逻辑一阶逻辑( (新课新课) )3.1 3.1 一阶逻辑基本概念一阶逻辑基本概念3.2 3.2 一阶逻辑等值演算一阶逻辑等值演算p范式与数字逻辑中化简逻辑函数的关联范式与数字逻辑中化简逻辑函数的关联p命题逻辑推理如何用计算机实现命题逻辑推理如何用计算机实现2离散数学知识框架离散数学知识框架( (应用型应用型) )p逻辑：研究思维的逻辑：研究思维的规律性。规律性。p学习和工作时时处学习和工作时时处处离不开处离不开“逻辑逻辑”。p数理逻辑：研究推数理逻辑

2、：研究推理、计算等逻辑问题。理、计算等逻辑问题。p在离散数学中数理在离散数学中数理逻辑的内容一般包括逻辑的内容一般包括命题逻辑和一阶逻辑。命题逻辑和一阶逻辑。命题逻辑和一阶逻辑命题逻辑和一阶逻辑33离散数学与其他课程的关系离散数学与其他课程的关系高等高等代数代数数学数学分析分析概率概率统计统计算法设计算法设计与分析与分析算法与数算法与数据结构据结构编译技术编译技术网络技术网络技术软件工程软件工程人工智能人工智能p基础数学的延伸基础数学的延伸p算法与数据结构算法与数据结构 的理论基础的理论基础p概率统计、算法概率统计、算法 设计与分析的理设计与分析的理 论基础论基础p其他专业课程的其他专业课程的

3、 描述和建模工具描述和建模工具离散离散数学数学4pqr0001000111010100111110001101001101011111主析取范式主析取范式( (由真值为由真值为1 1对应的最小项析取组成对应的最小项析取组成) )：m001 m011 m100 m111=( p ( p (p (p ) ), , , ,( (74313 m5p与数字逻辑的关联与数字逻辑的关联-逻辑函数的逻辑函数的 “ “与或与或”式化简式化简CBADCACBCDBF)13,12,11,10, 8 , 5 , 3 , 2(4mBADC00110110001101100 0 1 1 1 0 0 0 1 1 0 0 0

4、1 1 1 CBADBABCCBADBACBF数字逻辑：用二进制为基础的数字化技术解决逻辑问题数字逻辑：用二进制为基础的数字化技术解决逻辑问题6下列命题推理如何用计算机进行验证下列命题推理如何用计算机进行验证前提前提: p q, qr, ps, s结论结论: r(p q) )证明证明 ： ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(p q) ) 合取合取则：则：推理正确，推理正确， r(pq)是有效结论是有效结论7定理定理2.8 由前提由前提A1, A2, , Ak 推出推

5、出B 的推理正确当且仅的推理正确当且仅当当 A1 A2 AkB 为重言式为重言式.定义定义2.9 真值表真值表: 命题公式在所有可能的赋值下的取值的列命题公式在所有可能的赋值下的取值的列表含表含n个变项的公式有个变项的公式有2n个赋值。个赋值。定义定义2.10 重言式重言式(永真式永真式): 无成假赋值的命题公式无成假赋值的命题公式定义定义2.8 设设p1, p2, , pn是出现在公式是出现在公式A中全部的命题中全部的命题变项变项, 给给 p1, p2, , pn指定一组真值指定一组真值, 称为对称为对A的一个的一个赋值赋值或或解释解释.使公式为真的赋值称作使公式为真的赋值称作成真赋值成真赋

6、值, 使公式为假使公式为假的赋值称作的赋值称作成假赋值。成假赋值。p相关知识点相关知识点8p q r sEp q r sE0 0 0 011 0 0 010 0 0 111 0 0 110 0 1 011 0 1 010 0 1 111 0 1 110 1 0 011 1 0 010 1 0 111 1 0 110 1 1 011 1 1 010 1 1 111 1 1 11 B)( )()()(4321qprssprqqpEAAAA p若要证明若要证明E是永真式，只需编写程序实现如下功能：是永真式，只需编写程序实现如下功能：对于变元对于变元 p,q,r,s的所有赋值，验证的所有赋值，验证E的

7、取值是否均为的取值是否均为1即可。即可。9#include stdio.hmain() int p,q,r,s,A1,A2,A3,A4,B,E;/p,q,r,s是命题变元是命题变元,A1,.,A4是前提，是前提，B是结论是结论,E是是A1A2 A3 A4 B int yh(int p,int q)/计算蕴涵命题计算蕴涵命题pq的值的值return !p|q;/应用蕴涵等值式：应用蕴涵等值式：pqp qfor(p=0;p=1;p+) /p,q,r,s四重循环实现所有赋值情况四重循环实现所有赋值情况 for (q=0;q=1;q+) for(r=0;r=1;r+) for(s=0;s=1;s+)

8、int result=1; /result作为标志，取值为作为标志，取值为1推理有效，取值为推理有效，取值为0推理无效推理无效 A1=p|q;A2=yh(q,r); A3=yh(p,s);A4=!s;/A1,.A4是前提是前提 B=r&(p|q);/B是结论是结论 E=yh(A1&A2&A3&A4,B) if (result=1) printf(所给推理有效所给推理有效!); else printf(所给推理无效所给推理无效!);if (E=0) /成假赋值出现成假赋值出现 result=0;break; /推理无效，结束赋值结果的检查即结束循环推理无效，结束赋值结果的检查即结束循环 B)(

9、)()()(4321qprssprqqpEAAAA 11一阶逻辑的内容要点：谓词和个体谓词和个体量词量词一阶逻辑公式一阶逻辑公式置换规则置换规则一阶逻辑等值式一阶逻辑等值式推理理论推理理论一阶逻辑前束范式一阶逻辑前束范式123.1.1 命题逻辑的局限性命题逻辑的局限性3.1.2 个体词、谓词与量词个体词、谓词与量词n个体常项、个体变项、个体域、全总个体域个体常项、个体变项、个体域、全总个体域n谓词常项、谓词变项谓词常项、谓词变项n全称量词、存在量词全称量词、存在量词3.1.3 一阶逻辑命题符号化一阶逻辑命题符号化3.1.4 一阶逻辑一阶逻辑公式与分类公式与分类3.1 3.1 一阶逻辑基本概念一

10、阶逻辑基本概念(*)(* #)(*)133.1.1 3.1.1 命题逻辑的局限性命题逻辑的局限性考虑下述数学中公认的正确推理考虑下述数学中公认的正确推理:凡偶数都能被凡偶数都能被2整除整除, 6是偶数是偶数, 所以所以6能被能被2整除整除.令令 p: 凡偶数都能被凡偶数都能被2整除，整除， q: 6是偶数是偶数 r: 6能被能被2整除整除命题的符号化：命题的符号化：p q r 根据定理根据定理2.8 p q r 当且仅当当且仅当 (p q) r是永真式是永真式因为因为(p q) r不是永真式不是永真式所以不能得出所以不能得出p q r推理是有效的。推理是有效的。14。15 16例如例如 “若若

11、x是偶数是偶数, 则则x能被能被2整除整除.” p个体常项：个体常项：p个体变项：个体变项：p个体词：个体词：p个体域：个体域：3.1.2 3.1.2 个体词与个体域个体词与个体域1 1、个体词、个体词p个体词个体词: :所研究对象中可以独立存在的具体或抽象的客体所研究对象中可以独立存在的具体或抽象的客体p个体常项个体常项: : 表示具体事物的个体词表示具体事物的个体词, , 用用a a, , b b, , c c等表示等表示p个体变项个体变项: : 表示抽象事物的个体词表示抽象事物的个体词, , 用用x x, , y y, , z z等表示等表示p个体域个体域: : 个体变项的取值范围个体变

12、项的取值范围p : :宇宙间一切事物宇宙间一切事物X X、偶数和、偶数和2 2x可以是自然数集可以是自然数集N, N, , ,也可以是全总个体域也可以是全总个体域偶数和偶数和2 2全总个体域全总个体域172 2、谓词、谓词p谓词谓词: : 表示个体词性质或相互之间关系的词，谓词表示个体词性质或相互之间关系的词，谓词用用F,G,H,PF,G,H,P等表示等表示n谓词常项谓词常项: : 表示表示具体具体性质或相互之间关系的谓词性质或相互之间关系的谓词n谓词变项谓词变项: : 表示表示抽象抽象性质或相互之间关系的谓词性质或相互之间关系的谓词pn n元谓词元谓词P P( (x x1 1, , x x2

13、 2, , , x xn n) ): : 含含n n个命题变项的谓词个命题变项的谓词p0 0元谓词元谓词: :p一元谓词一元谓词: :p多元谓词多元谓词( (n n 2)2): :是定义在个体域上是定义在个体域上, , 值域为值域为0,10,1的的n n元函数元函数不含个体变项的谓词不含个体变项的谓词表示事物的性质表示事物的性质表示事物之间的关系表示事物之间的关系18p实例实例(1) 4是偶数是偶数 4是个体常项是个体常项, F: 是偶数是偶数 符号化为符号化为: F(4)(2) X是合数是合数 x是个体变项是个体变项, G: 是合数是合数 符号化为符号化为: G(x)(3) x y x,y是

14、个体变项是个体变项,H: 10, G(x): x0 -假命题假命题-真命题真命题34p实例实例例例 给定解释给定解释I I 如下如下: : (a) 个体域个体域 D=N (b) (c) (d) 谓词谓词说明下列公式在说明下列公式在 I 下的含义下的含义, 并讨论其真值并讨论其真值 2 axyyxgyxyxf ),(,),(yxyxF :),( 在在I下，公式解释为：下，公式解释为： x(2x=x)(2) x y(F(f(x,a),y)F(f(y,a),x) x y(x+2=yy+2=x) (1) xF(g(x,a),x)-假命题假命题-假命题假命题35p闭式的性质闭式的性质定理定理3.1 闭式

15、在任何解释下都变成命题闭式在任何解释下都变成命题. ( (闭式闭式: : 不含自由出现的个体变项的公式不含自由出现的个体变项的公式) ) (1) xF(g(x,a),x) -闭式闭式(2) x y(F(f(x,a),y)F(f(y,a),x) - -闭式闭式(3) x y zF(f(x,y),z) -闭式闭式(5) F(f(x,a), g(x,a) -不是闭式，不是命题不是闭式，不是命题(6) x (F(x,y)F(f(x,a), f(y,a) -不是闭式不是闭式,是命题是命题(4) xF(f(x,x),g(x,x) -闭式闭式xyyxgyxyxf ),(,),(yxyxF :),(36p一阶

16、逻辑公式的分类一阶逻辑公式的分类设设A是一个谓词公式，若是一个谓词公式，若A在在 下下均为真，则称均为真，则称A为永真式为永真式(有效式有效式)。若。若A在任何解在任何解释下均为假，则称释下均为假，则称A为永假式为永假式(矛盾式矛盾式)。若至少存。若至少存在一个解释使在一个解释使A为真，则称为真，则称A是可满足式。是可满足式。p在一阶逻辑中在一阶逻辑中, , 公式的可满足性公式的可满足性( (永真性永真性, ,永假性永假性) )是是 的的, ,即不存在算法能在有限步内判断即不存在算法能在有限步内判断任给的公式是否是可满足式任给的公式是否是可满足式( (永真式永真式, ,矛盾式矛盾式) )任何解

17、释任何解释不可判定不可判定37p代换实例代换实例定义定义3.9 设设A0是含命题变项是含命题变项p1, p2, ,pn的命题公式的命题公式, A1,A2,An是是n个谓词公式个谓词公式, 用用Ai处处代替处处代替A0中中的的pi(1 i n), 所得公式所得公式A称为称为A0的的代换实例代换实例.例例: 命题公式命题公式A0：A1 : A2 :A1 ： A2：A: 是是 的代换实例的代换实例pq xF(x) yG(y)代替代替p代替代替qpq xF(x)yG(y)定理定理3.2 永真式的代换实例都是永真式，永真式的代换实例都是永真式，矛盾式的代换实例都是矛盾式矛盾式的代换实例都是矛盾式. 38

18、p实例实例例例 判断下列公式的类型判断下列公式的类型:(1) x(F(x)G(x) -非永真式的可满足式非永真式的可满足式(2) ( xF(x) ( xF(x) -永真式永真式这是这是 p p 的代换实例的代换实例, p p是永真式是永真式, 取解释取解释I1, D1=R, :x是整数是整数, :x是有理数是有理数, 真命题真命题)(xF)(xG(3) ( xF(x)yG(y) yG(y) -矛盾式矛盾式这是这是 (pq) q的代换实例的代换实例, (pq) q是矛盾式是矛盾式取解释取解释I2, D2=R, :x是整数是整数, :x是自然数是自然数, 假命题假命题)(xF)(xG393.2 3

19、.2 一阶逻辑等值演算一阶逻辑等值演算3.2.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则n基本等值式基本等值式n置换规则、换名规则、代替规则置换规则、换名规则、代替规则3.2.2 一阶逻辑前束范式一阶逻辑前束范式403.2.1 3.2.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则定义定义3.10 若若AB是永真式是永真式, 则称则称A与与B是是等值等值的的, 记作记作AB, 并称并称AB为为等值式等值式基本等值式：基本等值式：p命题逻辑中基本等值式的代换实例命题逻辑中基本等值式的代换实例如如: xF(x)yG(y) 蕴涵等值式蕴涵等值式 ABA BxF(x)yG(y)p消去量

20、词等值式消去量词等值式 设设D=a1,a2,an xA(x)A(a1) A(a2) A(an) xA(x)A(a1) A(a2) A(an)41p基本等值式基本等值式( (续续) )量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 设设A(x)是含是含x自由出现的公式，自由出现的公式，B中不含中不含x的出现的出现关于全称量词的：关于全称量词的： x(A(x) B)xA(x) B x(A(x) B)xA(x) B x(BA(x)BxA(x) 在公式在公式 xA和和 xA中中, 称称x为指导变元为指导变元, A为相应量词的辖域为相应量词的辖域 x(A(x)B)xA(x)B42设个体域设个体域D=1

21、,2，则：，则： x(A(x)B) (A(1)B) (A(2)B)( A(1) B ) ( A(2) B)(A(1)B) (A(2)B)( A(1) A(2) B (A(1) A(2) B(A(1) A(2)B xA(x)Bp 如何理解如何理解 x(A(x)B)xA(x)B43p基本等值式基本等值式( (续续) )量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 设设A(x)是含是含x自由出现的公式，自由出现的公式，B中不含中不含x的出现的出现关于存在量词的关于存在量词的: x(A(x) B)xA(x) B x(A(x) B)xA(x) B x(BA(x)BxA(x) x(A(x)B)xA(x

22、)B44p基本等值式基本等值式( (续续) )量词否定等值式量词否定等值式设设A(x)是含是含x自由出现的公式自由出现的公式 xA(x) x A(x) xA(x) x A(x)量词分配等值式量词分配等值式 x(A(x) B(x)xA(x)xB(x) x(A(x) B(x)xA(x)xB(x)注意：注意： 对对 无分配律，无分配律， 对对 无分配律无分配律 45p 对对 无分配律，无分配律， 对对 无分配律无分配律 x(A(x) B(x)xA(x) xB(x)例：例：A(x)： B(x)： D：N x(A(x) B(x)xA(x) xB(x)例：例：A(x)： B(x)： D：N xA(x)xB

23、(x) x(A(x) B(x) x(A(x) B(x) xA(x) xB(x)x是奇数是奇数x是偶数是偶数左边左边=1 右边右边=0左边左边=0 右边右边=1x是素数是素数x是合数是合数46p等值演算的等值演算的3条规则条规则置换规则置换规则 设设 (A)是含公式是含公式A的公式的公式, (B)是用公式是用公式B取代取代 (A)中的所有中的所有A得到得到的公式的公式, 若若AB则则 (A) (B) 例：例： 设设 (A): xA(x) ( xA(x) 因为因为 xA(x) x A(x) 所以所以 ( xA(x) ( x A(x)47p等值演算的等值演算的3条规则条规则换名规则换名规则 将公式将

24、公式A中某量词的指导变元及中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项内未曾出现的某个个体变项, 其余部分不变其余部分不变, 记所得公式为记所得公式为A , 则则AA .例：例： uF(u,y,z) yG(x,y,z) uF(u,y,z) vG(x,v,z) 说明：说明： yG(x,y,z)中的约束变项中的约束变项y换名为换名为v48p等值演算的等值演算的3条规则条规则代替规则代替规则 将公式将公式A中某个自由出现的个体中某个自由出现的个体变项的所有自由出现改成变项的所有自由出现改成A中未曾出现的某中未曾出现的某个个体

25、变项个个体变项, 其余部分不变其余部分不变, 记所得公式为记所得公式为A , 则则AA。例：例： xF(x,u,z) yG(x,y,z) xF(x,u,z) yG(v,y,z) 说明：说明：G(x,y,z) 中的自由变项中的自由变项x用用v代替代替49p实例实例例例 消去公式中既约束出现、又自由出现的个体变项消去公式中既约束出现、又自由出现的个体变项(1) xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z) 换名规则换名规则 uF(u,y,z) vG(x,v,z) 换名规则换名规则或者或者 xF(x,u,z) yG(x,y,z) 代替规则代替规则 xF(x,u,z)

26、 yG(v,y,z) 代替规则代替规则(2) x(F(x,y) yG(x,y,z) x(F(x,y) tG(x,t,z) 换名规则换名规则或者或者 x(F(x,t) yG(x,y,z) 代替规则代替规则50p实例实例例例 设个体域设个体域D=a,b,c, 消去下面公式中的量词消去下面公式中的量词:(1) x(F(x)G(x) (F(a)G(a) (F(b)G(b) (F(c)G(c)(2) x(F(x)yG(y) xF(x)yG(y) 量词辖域收缩量词辖域收缩(F(a) F(b) F(c) (G(a) G(b) G(c) x(F(x,a) F(x,b) F(x,c)(3) x yF(x,y)

27、(F(a,a) F(a,b) F(a,c) (F(b,a) F(b,b) F(b,c) (F(c,a) F(c,b) F(c,c)51p实例实例解解 (F(f(2) G(2, f(2) (F(f(3) G(3, f(3)例例 给定解释给定解释I: (a) D=2,3, (b) (c) :x是奇数是奇数, : x=2 y=2, : x=y.在在I下求下列各式的真值下求下列各式的真值:(1) x(F(f(x) G(x, f(x) , 2)3(, 3)2(:fff),(yxG),(yxL)(xF(2) x yL(x,y) (1 1) (0 1) 1解解 yL(2,y) yL(3,y) (L(2,2)

28、 L(2,3) (L(3,2) L(3,3) (1 0) (0 1) 052p实例实例例例 证明下列等值式证明下列等值式: x(M(x) F(x) x(M(x) F(x)证证: x(M(x) F(x) x( M(x)F(x) 蕴涵等值式蕴涵等值式 x(M(x) F(x) x (M(x) F(x) 量词否定等值式量词否定等值式533.2.2 3.2.2 一阶逻辑前束范式一阶逻辑前束范式定义定义3.11 设设A为一个一阶逻辑公式为一个一阶逻辑公式, 若若A具有如下具有如下形式形式 Q1x1Q2x2Qkxk B，则称则称A为为前束范式前束范式, 其中其中Qi 为为 或或 , 1 i k, B为不含量

29、词的公式为不含量词的公式.例：例： x y(F(x)(G(y) H(x,y) x (F(x) G(x) x(F(x)y(G(y) H(x,y)x(F(x) G(x)-前束范式前束范式-非前束范式非前束范式54p公式的前束范式公式的前束范式定理定理3.3(前束范式存在定理前束范式存在定理) ) 一阶逻辑中的任何公一阶逻辑中的任何公式都存在与之等值的前束范式式都存在与之等值的前束范式例例 求公式的前束范式求公式的前束范式(1) xF(x)xG(x)解解1 xF(x) x G(x) 量词否定等值式量词否定等值式 x(F(x)G(x) 量词分配等值式量词分配等值式解解2 xF(x)yG(y) 换名规则

30、换名规则 xF(x) y G(y) 量词否定等值式量词否定等值式 x(F(x) y G(y) 量词辖域扩张量词辖域扩张 x y(F(x)G(y) 量词辖域扩张量词辖域扩张55 x(F(x)G(x) x y(F(x)G(y) )2()2() 1 () 1 ()2()2()1 ()2()2() 1 ()1 () 1 ()2()()1 ()()()()2()2() 1 () 1 ()2()2()1 () 1 ()()(GFGFGFGFGFGFGxFGxFxyGxFyxGFGFGFGFxGxFxD=1,2？5657(1)US规则规则(全称量词消去规则全称量词消去规则) 要求：要求： y不在不在A(x)

31、中以约束变元的形式出现。中以约束变元的形式出现。(2)ES规则规则(存在量词消去规则存在量词消去规则) 要求要求:（1）a是使是使A(x)为真的特定的个体常元为真的特定的个体常元.（2）个体常元）个体常元a不在不在A(x)和已经推导出的公式出和已经推导出的公式出现，除现，除x外，外，A(x)中无其他自由变元。中无其他自由变元。 xA(x)A(a)或或 xA(x)A(y) xA(x)A(a)58要求要求:（1）个体变元取遍整个个体域时，）个体变元取遍整个个体域时，A(y)均为真均为真（2）x不在不在A(y)中以约束变元的形式出现。中以约束变元的形式出现。要求要求:（1）x不在不在A(y)中以约束

32、变元的形式出现中以约束变元的形式出现（2）x不在不在A(a)中以约束变元的形式出现中以约束变元的形式出现5960 61pP P、E E、T T规则规则62(1)US (2)P (1)P规则规则规则规则误：误：分析下面推导过程的错分析下面推导过程的错，例：设个体域是实数集例：设个体域是实数集) ), ,( () ), ,( (, ,: :) ), ,( (yyyPyxyPxyxyx 163(2)(4)T (5)(3)ES (4)P (3)(1)ES (2)P (1)Q(P规则规则规则规则规则规则规则规则规则规则误：误：分析下面推导过程的错分析下面推导过程的错是负数，是负数，是正数，是正数，例：设

33、个体域是实数集例：设个体域是实数集) )( () )( () )( () )( () )( () )( (: :) ): :) )( (aQaPaQxxQaPxxPxxxx 64(1)UG x(2)P (1)P规则规则规则规则误：误：分析下面推导过程的错分析下面推导过程的错，例：设个体域是实数集例：设个体域是实数集) ), ,( () ), ,( (, ,: :) ), ,( (xxxPyxxPyxyx 65假命题假命题，都有，都有对于任何实数对于任何实数规则规则规则规则规则规则规则规则误：误：分析下面推导过程的错分析下面推导过程的错，例：设个体域是实数集例：设个体域是实数集 (3)E (4)

34、EG (3)(1)ES (2)P (1)P0202 xxxxxPxxxPxxxPxaxxPyxxPyyxyx: :) ), ,( () ), ,( () )( () ), ,( () ), ,( () ), ,( (: :) ), ,( (66R(x)x(Q(x)y)S(x,R(y)y(P(x)xy),S(x,y(Q(y)x(P(x)yx:y)S(x, Q 推理可表示为：相信是骗子，是教师是学生，体域，解：设个体域是全总个以教师都不是骗子。”学生都不相信骗子，所所有的老师，任何一个确性：“有些学生相信例：证明下列诊断的正xxRxxxxP:)(:)(:)(67 P y)S(x,R(y)y(P(x)x(6)(4)US x)S(a,(5)Q(x)(2)T y)S(a,y(Q(y)(4)(2)T (3)P(a)(1)ES y)S(a,y(Q(y)(2)P(a)P y)S(x,y(Q(y)x(P(x)(1)R(x)x(Q(x)y)S(x,R(y)y(P(x)xy),S(x,y(Q(y)x(P(x)规规则则规规则则：规规则则：规规则则：