离散数学2 一阶逻辑

1、第二章第二章 一阶逻辑一阶逻辑 第一节第一节 一阶逻辑基本概念一阶逻辑基本概念 内容：内容： 个体词，谓词，量词，命题符号化。 重点：重点： 1、掌握个体词，谓词，量词的有关概念， 2、掌握在一阶逻辑中的命题符号化。 知识点回顾 命题逻辑：命题逻辑： 不再对简单命题进行分解不再对简单命题进行分解 命题（命题演算的基本单位）命题（命题演算的基本单位） 无法研究命题的内部结构无法研究命题的内部结构 一、一阶逻辑一、一阶逻辑(谓词逻辑谓词逻辑)研究的内容。研究的内容。 例如：判断以下推理是否正确： 凡人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。 这是著名的“苏格拉底三段论”， 若用 推理形

2、式为 , ,p q r ()pqr 分别表示以上3个命题， ，不是重言式。 （前提） （前提） （结论） 例如：判断以下推理是否正确： 凡人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。 命题逻辑的局限性： 未将 , ,p q r 的内在联系反映出来 对简单命题进一步分析。 简单命题 个体词 谓词 用来刻画个体词的用来刻画个体词的 性质或个体词之间性质或个体词之间 关系的词关系的词 所研究对象中可以独立所研究对象中可以独立 存在的具体的或抽象的存在的具体的或抽象的 客体客体 二、个体词，谓词，量词。二、个体词，谓词，量词。 二、个体词，谓词，量词。二、个体词，谓词，量词。 1、个体词，谓

3、词、个体词，谓词 。 例如：李华李华是大学生。 是无理数。 2 小王小王比小明小明高。 (1) 个体词个体词简单命题中表示主体或客体的词 (由名词组成)。 个体词 个体常项用 个体变项用 , ,a b c , ,x y z 表示 表示 个体常项：表示具体的或特定的个体的词个体常项：表示具体的或特定的个体的词 个体变项：表示抽象的或泛指的个体的词个体变项：表示抽象的或泛指的个体的词 个体域个体域 （或论域）（或论域） 个体变项的个体变项的 取值范围取值范围 全总个全总个 体域体域 宇宙间一切宇宙间一切 事物组成的事物组成的 个体域个体域 (2) 谓词谓词刻画个体词的性质性质或 个体词之间关系个体

4、词之间关系的词。 谓词 谓词常项:表示具体性质或关系 谓词变项:表示抽象或者泛指的性质或关系 均用 表示.,F G H ( )F aaF 例如： (1) 表示个体变项 有性质 表示个体常项 有性质 (3) 表示个体变项 和 有关系 ( )F x xF ( , )F x yxyF 以后常称这种个体变项和谓词以后常称这种个体变项和谓词 的联合体的联合体F(x),L(x,y)等为谓词等为谓词 例1：分析下列个命题中的个体和谓词 1. 1. 是无理数。是无理数。 2. 2. 张三与李四同在电子信息学院。张三与李四同在电子信息学院。 3. 3. x x与与y y的和等于的和等于z z（x x，y y，z

5、 z是确定的数）。是确定的数）。 4. 4. 的平方是非负的。的平方是非负的。 5. 5. 所有的实数的平方都是非负的。所有的实数的平方都是非负的。 6. 6. 有一个比有一个比21000大的素数。大的素数。 （1）是无理数。 解： 个体词：（代表圆周率） 谓词：是无理数，表示“”的性质。 （2）张三与李四同在电子信息学院。 解：个体词：张三，李四 谓词： 与同在电子信息学院 表示“张三”与“李四”之间的关系。 （3 3）x x 与与 y y 的和等于的和等于 z z （x x，y y，z z是确定的数）是确定的数） 个体词：个体词： x x、 y y、 z z 谓词：谓词： 与与的和等于的和

6、等于 （4） 的平方是非负的。 解：个体词： 谓词： 的平方是非负的 个体词： 的平方 谓词： 是非负的 （5）所有的实数的平方都是非负的。 个体词：每一个实数 谓词： 的平方是非负的 （6）有一个比21000大的素数。 个体词：一个素数 谓词： 比21000大 “所有”是什么？ 量词：所有 “有一个有一个”是什么？是什么？ 量词：有一个量词：有一个 ：小王， a ：小明， b ：小王比小明高。 ( , )F a b 元谓词元谓词(用n 12 (,) n Fxxx表示) 如( , )F x yxy高。比： 其中( , )F x y, x y为个体词。是二元谓词， 表示含 个体变项的谓词。n 元

7、谓词元谓词: 不带个体变项的谓词.0 当0元谓词中的谓词为谓词常项时，0元谓词 为命题. 所以命题逻辑中的命题均可以表示成 0元谓词。 (1)n 例如：李华是大学生， 小明是大学生。 一元谓词 个体常项 个体常项 ：李华 a ：小明 b ( ),( )F a F b分别表示李华，小明是大学生， 它们是0元谓词。 ：( )F xx是大学生， (1) 2是素数且是偶数 例2 将下列命题用0元谓词符号化 解： ( )F xx： 是素数。 ( )G xx： 是偶数。 :2a 则命题符号化为： ( )F aG a （ ） (2) 如果2大于3，则2大于4 例2 将下列命题用0元谓词符号化 解： ( ,

8、):L x yxy大于 :2; :3; :4abc 则命题符号化为： ( , ),L a bL a c （） (3)如果张明比李民高， 李民比赵亮高，则张明比赵亮高。 例2 将下列命题用0元谓词符号化 解： ( ,) :H x yxy比 高 :; :; :abc张明李民赵亮 则命题符号化为： ( , ),H a bH b cH a c（ , ）（） 例3：将下列命题在一阶逻辑中符号化 (1) 所有的人都是要死的。 (2) 有的人活百岁以上。 称表示个体常项或变项之称表示个体常项或变项之 间数量关系的词为量词间数量关系的词为量词 2、量词、量词表示数量的词。表示数量的词。 量词 存在量词 全称量

9、词 “一切”“所有的”“任意的”等全称量词全称量词: “存在着”“有一个”“至少有一个”等存在量词存在量词: :对个体域里的所有个体 :个体域里的所有个体都有性质F x ( )xF x :存在个体域里的个体 :存在着个体域里的个体具有性质F x ( )xF x 下面考虑以上两个命题的符号化 (1) 所有的人都是要死的。所有的人都是要死的。 (2) 有的人活百岁以上。有的人活百岁以上。 在命题符号化之前必须在命题符号化之前必须明确个体域明确个体域。 第一种情况：个体域第一种情况：个体域D为人类集合为人类集合 (1) 符号化为( )xF x ( ):.F xx是要死的 真命题 (2) 符号化为(

10、)xG x ( ):.G xx活百岁以上 真命题 下面考虑以上两个命题的符号化 (1) 所有的人都是要死的。所有的人都是要死的。 有的人活百岁以上。有的人活百岁以上。 第二种情况：个体域第二种情况：个体域D为全总个体域为全总个体域 (1) 对所有个体而言，如果它是人，则它是要死对所有个体而言，如果它是人，则它是要死 的。的。 (2) 存在着个体，它是人并且活百岁以上。存在着个体，它是人并且活百岁以上。 特性谓词 ( ):.M xx是人 下面考虑以上两个命题的符号化 (1) 所有的人都是要死的。所有的人都是要死的。 (2) 有的人活百岁以上。有的人活百岁以上。 第二种情况：个体域第二种情况：个体

11、域D为全总个体域为全总个体域 (1)对所有个体而言，如果它是人，则它是要死对所有个体而言，如果它是人，则它是要死 的。的。 (2) 存在着个体，它是人并且活百岁以上。存在着个体，它是人并且活百岁以上。 ( )( )x M xF x ( )( )x M xF x 注意：使用量词时，应注意以下6点： (1) 在不同个体域中， 命题符号化的形式可能不一样， (2) 一般，除非有特别说明， 均以全总个体域为个体域， (3) 在引入特性谓词后，使用全称量词用“ 使用存在量词用“ ”， ”， (4)nn个量词，元谓词化为命题至少需要 如 (5) 当个体域为有限集时， 12 , n Da aa 12 ( )

12、()()() n xA xA aA aA a 12 ( )()()() n xA xA aA aA a ，则 (6) 多个量词同时出现时， 不能随意颠倒顺序。 例如：对任意的x，存在着y, 使得x+y=5. 取个体域为实数集。 三、命题符号化。三、命题符号化。 例例4、在一阶逻辑中将下面命题符号化。 (1) 所有的有理数均可表成分数。 解：解：因无指定个体域，则以全总个体域为个体域。 ( )( )x Q xF x ：( )Q xx为有理数， ：x( )F x可表成分数， 三、命题符号化。三、命题符号化。 例例4、在一阶逻辑中将下面命题符号化。 (2) 有的有理数是整数。 解：解： ( )( )

13、x Q xZ x ：( )Q xx为有理数，：x ( )Z x 为整数， 注：注：若本题指定的个体域为有理数集， 则(1)，(2)分别符号化为 和 ( )xF x ( )xZ x。 例例5、在一阶逻辑中将下列命题符号化。 (1) 凡偶数均能被2整除。 ( )( )x F xG x (2) 存在着偶素数。 ( )( )x F xH x 解：解： ( )F x ：x是偶数，：x( )G x能被2整除， ： 解：解： ( )F xx是偶数，：( )H xx是素数， 全总个体域 例例5、在一阶逻辑中将下列命题符号化。 (3) 没有不犯错误的人。 ( )( )x M xF x 原命题即：“每个人都犯错误

14、”。 又可符号化为： ( )( )x M xF x 解：解： ( )M x：x是人，( )F x：x犯错误， 例例5、在一阶逻辑中将下列命题符号化。 (4) 素数不全是奇数。 ( )( )x F xG x 原命题即：“有的素数不是奇数”。 又可符号化为： ( )( )x F xG x 解：解： ( )F x：x是素数， ( )G x：x是奇数， 例例5、在一阶逻辑中将下列命题符号化。 (5) 在北京工作的人未必是北京人。 ( )( )x F xG x (6) 尽管有些人聪明，但未必一切人都聪明。 ( )( )( )( )x M xF xx M xF x 解：解： ： ( )F x x是在北京工

15、作的人， ：x ( )G x是北京人， 解：解： ：( )M xx是人，( )F x： x聪明， (1) 一切人都不一样高。 例6 在一阶逻辑中将下面命题符号化 ( )( )( , )( , )x y M xM yH x yL x y 又可符号化为： 解：解： ( )M x：x是人，( , )H x y：x和y不是同一个人 ( , )L x y：x和y一样高 ( )( )( , )( , )x y M xM yH x yL x y (2)每个自然数都有后继数。 ( )( ( )( , )x F xy F yH x y 解：解： ( )F x：x是自然数， ( , )H x y： y是x的后继数

16、 例6 在一阶逻辑中将下面命题符号化 (3)有的自然数无先驱数。 ( )( ( )( , )x F xy F yL x y 解：解： ( )F x：x是自然数， ( , )L x y：y是x的先驱数 例6 在一阶逻辑中将下面命题符号化 1.概念：概念： 个体词，谓词，量词，命题符号化。 2.重点：重点： 掌握个体词，谓词，量词的有关概念， 掌握在一阶逻辑中的命题符号化。 本节小结本节小结 作作 业业 P52-53， 2.1，2.3(单) 第二节第二节 一阶逻辑合式公式及解释一阶逻辑合式公式及解释 内容：内容： 合式公式，解释，逻辑有效式， 矛盾式，可满足式。 重点：重点： (1) 掌握合式公式

17、的概念， (2) 掌握量词的辖域，约束变项， 自由变项的概念， (3) 掌握逻辑有效式，矛盾式， 可满足式的概念。 一般：一般： (1) 换名规则，代替规则， (2) 解释的概念， (3) 代换实例。 了解：了解： (1) 闭式的概念， (2) 判断合式公式的类型。 一、一阶逻辑中的合式公式。一、一阶逻辑中的合式公式。 1、字母表。 (1) 个体常项：个体常项： , , ,. , , ,1 iii a b ca b ci (2) 个体变项：个体变项： , , ,. ,1 iii x y zx y zi (3) 函数符号：函数符号： , , ,. ,1 iii f g hf g hi (4) 谓

18、词符号：谓词符号： ,. ,1 iii F G HF G Hi (5) 量词符号：量词符号： , (6) 联结词符：联结词符： , , , (7) 括号和逗号：括号和逗号：( ，) ， 2、项的递归定义。 (1) 个体常项和变项是项。 (3) 只有有限次地使用(1)、(2)生成的符号串才是项项。 例如： , , , , ( , ), ( , )21,a b x y f x yxy g x yxy ( , ), ( , )(21)h x yx y f a g x yaxy 等都是项。 (2)若 12 ( ,) n x xxn 12 , , n t tt是项，则 12 ( , , ) n t tt

19、 元函数，是任意 是项。 3、原子公式。 设 12 ( ,) n R x xxn 12 , , n t tt是项，则称 12 ( , , ) n R t tt为原子公式原子公式。 元谓词，是任意 例如： 均为原子公式。 一元谓词 ( ),( )F x G y 二元谓词 ( , ), ( , )H x y L x y (5) 只有有限次地应用(1)(4)构成的符号串 才是合式公式合式公式(也称谓词公式谓词公式)，简称公式公式。 (4) 若A,xAxA也是合式公式；是合式公式，则 4、合式公式的递归定义。 (1) 原子公式是合式公式； (3)若,A B (),(),ABAB (),()ABAB也是

20、合式公式； 是合式公式，则 是合式公式，则A()A也是合式公式；(2) 若 5、约束出现，自由出现。、约束出现，自由出现。 自由出现：自由出现：A中不是约束出现的其他变项的出现，中不是约束出现的其他变项的出现， 称为称为自由出现自由出现。 在合式公式 ,xAxA中， 称x为指导变项指导变项， 称A为相应量词的辖域辖域， 约束出现：在辖域中，约束出现：在辖域中，x的所有出现称为的所有出现称为约束出现约束出现， 即即x受相应量词指导变项的约束。受相应量词指导变项的约束。 例例1、指出下列各合式公式中的指导变项， 量词的辖域，个体变项的自由出现 和约束出现。 (1) ( )( , )x F xyH

21、x y (2) ( )( , )xF xG x y (3) ( , )( , )( , )x y R x yL y zxH x y 5.闭式闭式(封闭的合式公式封闭的合式公式) 无自由出现的个体变项的合式公式。 例如： ( )( )x F xG x ( )( , )x y F xG x y 都是闭式。 ( )( , )x F xG x y ( , , )z yL x y z 而 都不是闭式。 换名规则：换名规则： 将量词辖域中某个约束出现约束出现的个体变项及 对应的指导变项，改成公式中未曾出现过 的个体变项符号，公式中其余部分不变。 ( )( , )x F xyH x y 换成 ( )( ,

22、)z F zyH z y 例如： 分析：分析：在一个合式公式中，有的个体变项可以 约束出现，也可以自由出现，容易混淆。 采用规则，使公式中无既自由出现、 又约束出现的变项。 代替规则代替规则: 对某自由出现自由出现的个体变项用与原公式中 所有个体变项符号不同的变项符号去代替， 且处处代替。 ( , )( , )( , )x y R x yL y zxH x y 换成 ( , )( , )( , )x y R x yL y ztH t w 例如： 二、合式公式的解释。二、合式公式的解释。 对公式中各种变项(个体变项，函数变项， 谓词变项)，指定特殊的常项去代替，就 构成了公式的一个解释。 (1)

23、 非空个体域D； (2)D中一部分特定元素； 1、解释I由以下4部分组成： (3)D上一些特定的函数； (4)D上一些特定的谓词； 1) 个体域为自然数集合 N D (1) ( , ),xF g x a x (0)x xx真值为0 例例2、给定解释N如下： 2) N D0a 中特定元素 3) N D ( , ), ( , )f x yxy g x yx y上特定函数 4) N D( , )F x yxy 为上特定谓词 下，下面哪些公式为真？哪些公式为假？ N在解释 解：解：在解释N下，公式化为： 真值为1 (2) ( , ),( , ),x y F f x ayF f y a x (00)x

24、y xyyx 1) 个体域为自然数集合 N D 例例2、给定解释N如下： 3) N D ( , ), ( , )f x yxy g x yx y上特定函数 4) N D( , )F x yxy 为上特定谓词 下，下面哪些公式为真？哪些公式为假？ N在解释 解：解：在解释N下，公式化为： 2) N D0a 中特定元素 真值为1 (3) ( , ),x y zF f x y z ()x y z xyz 解：解：在解释N下，公式化为： 1) 个体域为自然数集合 N D 例例2、给定解释N如下： 3) N D ( , ), ( , )f x yxy g x yx y上特定函数 4) N D( , )F

25、 x yxy 为上特定谓词 下，下面哪些公式为真？哪些公式为假？ N在解释 2) N D0a 中特定元素 真值为0 (4) ( , ), ( , )x yF f x y g x y ()x y xyx y 2) N D0a 中特定元素1) 个体域为自然数集合 N D 3) N D( , ), ( , )f x yxy g x yx y上特定函数 例例2、给定解释N如下： 4) N D( , )F x y xy 为上特定谓词 在解释N下，下面哪些公式为真？哪些公式为假？ 解：解：在解释N下，公式化为： 真值为不确定(不是命题) (5) ( , ),( , )F f x yf y z xyyz 2

26、) N D0a 中特定元素1) 个体域为自然数集合 N D 3) N D( , ), ( , )f x yxy g x yx y上特定函数 例例2、给定解释N如下： 4) N D( , )F x y xy 为上特定谓词 在解释N下，下面哪些公式为真？哪些公式为假？ 解：解：在解释N下，公式化为： 闭式在任何解释之下都变成命题闭式在任何解释之下都变成命题 2、逻辑有效式(永真式)，矛盾式(永假式)， 可满足式。 逻辑有效式逻辑有效式(永真式永真式) 在任何解释下都取值为真的合式公式。 矛盾式矛盾式(永假式永假式) 在任何解释下都取值为假的合式公式。 可满足式可满足式 至少存在一种解释使其取值为真

27、的合式公式。 有一些公式，可以利用命题公式的结论。 代换实例代换实例 个命题变项 0 A 12 , n p ppn 将 n 12 , n A AA12 , n p pp 词公式称为 0 A 设是含的命题公式， 所得的谓 取代 个谓词 的代换实例代换实例。 例如： ( )( ),( )( ),F xG xxF xG x ( )( )xF xxG x 等都是 的代换实例。 pq 命题公式中重言式，矛盾式的代换实例在谓词 公式中仍是重言式(逻辑有效式)，矛盾式。 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 (1) ( )( )xF xxF x 解：解： 设ID。是任意的解释，设其个体域

28、为 若存在 0 xD 0 ()F x( )xF x 为假，为假，则， 从而( )( )xF xxF x 为真； 由以上，原公式是逻辑有效的。 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 (1) ( )( )xF xxF x 解：解： 设ID。是任意的解释，设其个体域为 若对任意xD( )F x为真，都有 则( ),( )xF xxF x 均为真， 所以( )( )xF xxF x 为真。 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 (2) ( )( , )( )xF xx yG x yxF x ()()1pqppqp (重言式) ， 而且 所以原公式是逻辑有效的。

29、解：解： 原公式是命题公式()pqp的代换实例， 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 所以原公式是逻辑有效的。 (3) ( )( )( )xF xxF xyG y (重言式) ， 而且 ()()1ppqppq 解：解： 原公式是命题公式()ppq的代换实例， 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 (4) ( , )( , )( , )F x yR x yR x y 而且 ()()pqqpqq (矛盾式) ， 0pqq 所以原公式是矛盾式。 解：解： 原公式是命题公式()pqq 的代换实例， 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 (5

30、) ( , )( , )x yF x yx yF x y 解：解： 取解释 如下： I （1）个体域为自然数集N. （2） ( , ).F x yxy为 此时，前件为 ，为真； 后件为 ，为假，因此在此解释下， 蕴含式为假。 原公式不是逻辑有效式。 ()x y xy ()x y xy 例例3、判断下列公式中哪些是逻辑有效式， 哪些是矛盾式。 (5) ( , )( , )x yF x yx yF x y 解：解： 若解释 为： I （1）个体域为自然数集N. （2） ( , ).F x yxy为 此时，前件为 ，为真； 后件为 ，为真，因此在此解释下， 蕴含式为真。 原公式不是矛盾式。 综上，原

31、公式是非逻辑有效式的可满足式。 ()x y xy ()x y xy 本节小结本节小结 (1) 合式公式的概念， (2) 量词的辖域，约束变项，自由变项， (3) 逻辑有效式，矛盾式，可满足式 作作 业业 作业：作业： P53 2.5(1) 2.7 第三节第三节 一阶逻辑等值式一阶逻辑等值式 内容：内容： 一阶逻辑等值式，前束范式。 重点：重点： 掌握基本等值式， (量词否定等值式，量词辖域收缩与扩张等值式， 量词分配等值式)的内容。 一般：一般： 使用基本等值式进行等值演算。 了解：了解： 前束范式的定义和求法。 一、一阶逻辑等值式。一、一阶逻辑等值式。 已有的等值式 命题公式中的24个等值式

32、 及代换实例 由换名规则及代替规则所得 公式与原公式等值 定义：定义： 若AB AB为逻辑有效式，记 1、量词否定等值式。 (1) ( )( )xA xx A x (2) ( )( )xA xx A x 2、量词辖域收缩与扩张等值式。 (1) ( )( )x A xBxA xB (2) ( )( )x A xBxA xB (4) ( )( )x BA xBxA x (3) ( )( )x A xBxA xB 1、量词否定等值式。 (1) ( )( )xA xx A x (2) ( )( )A xx A x 2、量词辖域收缩与扩张等值式。 (5) ( )( )x A xBxA xB (6) (

33、)( )x A xBxA xB (8) ( )( )x BA xBxA x (7) ( )( )x A xBxA xB 3、量词分配等值式。 (1) ( )( )( )( )x A xB xxA xxB x (2) ( )( )( )( )x A xB xxA xxB x 例例1、 “今天所有的人唱歌并且今天所有的人跳舞” 有相同含义。 “今天所有的人既唱歌又跳舞”与 3、量词分配等值式。 (1) ( )( )( )( )x A xB xxA xxB x (2) ( )( )( )( )x A xB xxA xxB x 例例1、 “有些人将去旅游或有些人将去探亲”有相同含义。 “有些人将去旅游

34、或探亲”与 注意：注意： ( )( )( )( )x A xB xxA xxB x ( )( )( )( )x A xB xxA xxB x 4、多个量词间的次序排列等值式。 (1) ( , )( , )x yA x yy xA x y (2) ( , )( , )x yA x yy xA x y 二、前束范式。二、前束范式。 前束范式：前束范式：形式 1 122kk Q x Q xQ x B 例如： ( )( , )x y F xG x y ( )( , )F xG x y， ( , , )( )x y z F x y zG y 等都是前束范式， 4、多个量词间的次序排列等值式。 (1) (

35、 , )( , )x yA x yy xA x y (2) ( , )( , )x yA x yy xA x y 二、前束范式。二、前束范式。 前束范式：前束范式：形式 1 122kk Q x Q xQ x B 例如： 而 ( )( , )x F xyG x y ( )( , )x F xyG x y等都不是前束范式。 例例2、求下列公式的前束范式。 (1) ( )( )xF xxG x 解：解： ( )( )xF xxG x ( )( )xF xx G x ( )( )x F xG x 量词否定等值式 对 的分配 例例2、求下列公式的前束范式。 (2) ( )( )xF xxG x 解：解：

36、 ( )( )xF xxG x ( )( )xF xx G x ( )( )xF xy G y ( )( )x y F xG y 量词否定等值式 换名规则 量词辖域的扩张 例例2、求下列公式的前束范式。 (3) ( )( )xF xxG x 解：解： ( )( )xF xxG x 量词否定等值式 量词分配等值式 ( )( )xF xxG x ( )( )x F xxG x ( )( )xF xG x 例例2、求下列公式的前束范式。 (4) ( )( )xF xxG x 解：解： ( )( )xF xxG x 量词否定等值式 换名规则 ( )( )x F xxG x ( )( )xF xxG x

37、 ( )( )x F xyG y ( )( )xF xyG y 量词辖域的扩张 ( )( )x yF xG y 量词辖域的扩张 本节小结本节小结 一阶逻辑等值的概念一阶逻辑等值的概念 重要等值式重要等值式 前束范式前束范式 作业：作业： P54 2.12(1) 2.14 2.15 第二章第二章 小结与例题小结与例题 一、一阶逻辑的基本概念。一、一阶逻辑的基本概念。 1、基本概念。 个体，个体域，个体词，个体常项和变项； 谓词；量词，全称量词和存在量词。 2、应用。 在一阶逻辑中将命题符号化。 二、一阶逻辑合式公式及解释。二、一阶逻辑合式公式及解释。 1、基本概念。 合式公式；辖域，约束变项，自

38、由变项； 闭式；解释；代换实例；逻辑有效式， 矛盾式，可满足式。 2、应用。 (1) 求某些公式在给定解释下的真值。 (2) 判断某些简单公式的类型。 三、一阶逻辑等值式。三、一阶逻辑等值式。 基本概念。 等值式，常用等值式；前束范式。 三、一阶逻辑等值式。三、一阶逻辑等值式。 基本概念。 等值式，常用等值式；前束范式。 例例1、在一阶逻辑中将下列命题符号化。 (1) 每一个有理数都是实数。 ( )( )x Q xR x (2) 并非每一个实数都是有理数。 ( )( )x R xQ x 解：解：( )Q xx( )R xx是实数，：是有理数，： 解：解：( )R x x( )Q xx是有理数，

39、 ：是实数，： 例例1、在一阶逻辑中将下列命题符号化。 (3) 会叫的狗未必会咬人。 ： 解：解：( )D xx ( )R xx是会咬人的狗， 是会叫的狗，： ( )( )x D xR x (或( )( )x D xR x) 例例1、在一阶逻辑中将下列命题符号化。 (4) 任何金属均可溶解于某种液体中。 ( )( )( , )x G xy P yR y x ： 解：解：( )P xx ( )G xx ：( , )R x yxy 是液体，： 是金属， ，溶解 例例2、将下列命题译成自然语言，并确定其真值。 (个体域为 ) Z 真值0。 真值0。 (1)( , )x yG x y ( , ):G

40、x yxyy ，其中 解：解：对任意正整数xy 使得xyy ，存在正整数 。 (2)( , )x yF x y ( , ):F x yxyy，其中 解：解：存在正整数xy 满足xyy ，使得对任意的正整数 。 例例2、将下列命题译成自然语言，并确定其真值。 (个体域为 ) Z 真值0。 真值1。 (3)( , )x yM x y ( , ):1M x yxy ，其中 解：解：对任意正整数xy 使得1xy ，存在正整数 。 (4)( , )x yN x y ( , ):2N x yyx，其中 解：解：对任意正整数xy 使得2yx ，存在正整数 。 例例3、指出下列量词的辖域，并指出各式中 的自由

41、出现和约束出现的个体变项。 (1) ( )( )( )( )x P xQ xxR xS x 解：解： x ( )( )P xQ x ( ),( )P x Q x中的x ，的辖域为 约束出现； x 的辖域为( )R x 中的( )R x x ， 约束出现； 中的( )S x x 自由出现。 例例3、指出下列量词的辖域，并指出各式中 的自由出现和约束出现的个体变项 (2) ( )( , )( )( , , )x F xG x yyF yR x y z 解：解： x ( )( , )F xG x y ( ),( , )F x G x y中的x ( , )G x y中的 y ，的辖域为 约束出现， 自

42、由出现； ( )F y中的y y的辖域是( )F y， 约束出现； ( , , )R x y z中的, ,x y z都自由出现。 (1)( )( )xP xxR x 解解( )( )xP xxR x ( ( )( )( )( ( )( )( )P aP bP cR aR bR c 量词消除，写出与之等值的命题公式。 例例4、 设个体域为, ,Aa b c将下面谓词公式中的 例例4、 设个体域为将下面谓词公式中的量词消除， 写出与之等值的命题公式。 （2） ( ( )( )x P xQ x 解解( ( )( )x P xQ x ( ( )( )( ( )( )( ( )( )P aQ aP bQ bP cQ c 例例4、 设个体域为将下面谓词公式中的量词消除， 写出与之等值的命题公式。 （3） ( , )x yP x y 解解( , )x yP x y ( ( , )( , )( , )P a aP a bP a c ( ( , )( , )( , )P b aP b bP b c ( ( , )( , )( , )P c aP c bP c c 习习 题题 1：在一阶逻辑中将下列命题符号化 （1）没有一个运动员不是强壮的 （2）尽管有的人聪明，但未必一切人都聪明 （4）所有的人都学习和工作 （3）每个计