离散数学的谓词逻辑详解(课堂PPT)课件(PPT 74页)

1、谓 词 逻 辑2022/7/221.第1页，共74页。命题逻辑的局限性 苏格拉底三段论： P：所有的人都是要死的。 Q：苏格拉底是人 。 R：所以苏格拉底要死 。 凭直觉知道这个结论是真的，推理是有效的。但是，借助命题演算的推理理论，却不能推导出这个结论（无法证明它的正确性）。Why ?2022/7/222.第2页，共74页。 此三段论的论断显然正确。 但是，在命题逻辑中无法得到正确性的反应: PQR 不是重言式！命题逻辑不能正确反映此三段论的推理过程。这是命题逻辑的局限性!2022/7/223.第3页，共74页。原 因在命题逻辑中无法将简单命题之间的内在联系反映出来。命题逻辑中描述的上述三段

2、论，即PQR，使R与命题P、Q无关的独立命题。但是，实际上R与命题P、Q是有关系的，只是这种关系在命题逻辑中得不到反映。要反映这种内在联系，需对简单命题作进一步分解，分解出其中的成份，包括：个体词，谓词，量词，函词等，研究它们的形式结构及逻辑关系，总结出正确的推理形式和规则，这就是一阶逻辑所研究的内容.一阶逻辑也称谓词逻辑。谓词逻辑是一种表达能力更强的逻辑。2022/7/224.第4页，共74页。谓词逻辑我们将介绍谓词逻辑的基本概念和符号。关于命题、命题的真值、命题词、命题常量和命题变元以及逻辑五个联结词其含意和在命题逻辑中的基本相同，本章中只介绍谓词逻辑中新出现的基本概念和符号，其中主要的是

3、个体词，谓词，量词以及函词。2022/7/225.第5页，共74页。1.谓词与个体词 将简单命题分解成个体与谓词这样两个组成部分。谓词，通常是用来描述个体的性质或特征，或者个体之间的关系。谓词逻辑，是命题逻辑的扩充与发展 。例1：下面两个命题 1. 张华是学生 2. 李明是学生 a: 张华 b:李明 H：是学生 ，则 H（x）:x是学生 1，2可分别表示成 H(a) ，H(b). 这样表示就揭示了两命题间有相同的谓语这一特征。 2022/7/226.第6页，共74页。例2：张华比李明高 令 a:张华 b:李明 L(x，y):x高于y 该命题可表示为： L(a，b)例1和例2中的 H、L称为谓词

4、， 其中H是一元谓词，表示个体的性质（是什么）， L是二元谓词，表示个体之间的关系。 注： （1）常用大写拉丁字母表示谓词. （2）谓词是用来刻划个体的性质或者个体之间的关系的。2022/7/227.第7页，共74页。命题函数与命题例: 令P(x)表示x为质数，则P(x)为一元谓词。 令 H(x，y)表示“x高于y”,则 H(x，y)为二元谓词。 则：H(张三，李四) 表示“张三高于李四”，是命题。注意： P(x.y), H(x，y)为命题函数. P(2)与 H(张三，李四)才是命题。谓词中如果有n个变元则称为n元谓词. n元谓词反映了个体之间的n元关系. 2022/7/228.第8页，共74

5、页。2.个体词个体是可以独立存在的实体，它可以是一个具体的 事物-个体常元，常用小写拉丁字母a，b，c等表示。也可以是一个抽象的概念（即没指定哪一个个体） -个体变元，常用小写拉丁字母：x，y，z等表示2022/7/229.第9页，共74页。函词例：张华的哥哥比李明高 a:张华 b:李明 L(x，y):x高于y f(x):x的哥哥则上述符号化为： L(f(a)，b) f称为函词定义：一个n元函词即是一个论域上的一个n元函数2022/7/2210.第10页，共74页。 变元在谓词中的次序直接影响了谓词的取值 。如:设谓词P(x，y)为“x比y高”， 设张三为170cm，李四为180cm.则: P

6、(李四，张三)为真命题。 P(张三，李四)为假命题.概念的讨论2022/7/2211.第11页，共74页。命题的符号化例1:武汉位于重庆与上海之间.解:用个体词a，b，c分别表示武汉，重庆和上海， 谓词P(x，y，z)表示x位于y与z之间， 则该命题表示为:P(a，b，c).例2：如果王英坐在李红的后面，则王英比李红高.解：令 a:王英;b:李红;P(x，y):x坐在y的后面; G(x，y):x比y高.则该命题表示为：P(a，b)G(a，b).2022/7/2212.第12页，共74页。3. 量词 使用前面介绍的概念，还不足以表达日常生活中的各种命题。 例如： “ 所有的正整数都是素数 ” “

7、 有些正整数是素数 ” 两种量词: 全称量词和存在量词.2022/7/2213.第13页，共74页。全称量词: 1.全称量词 ： （任意，所有） x: “对一切x”，“对所有的x”， “对任一x” 如： x P(x) “对一切x，P(x)是真” x P(x) “并非对一切x，P(x)是真” x P(x) “对一切x， P(x) 是真” 如: “ 所有人都是要死的”设x的个体域为全体人的集合，则可表示为 x D(x) 2022/7/2214.第14页，共74页。存在量词: 2. 存在量词： （存在） x: “存在x“、 ”某些x“、 ”至少有一x”如： x P(x) “存在x， P(x)是真”

8、x P(x) “存在x， P(x)是真，并非这样” x P(x) “存在x， P(x)是真” 如: “有些有理数是整数。” 令(x）：x是整数，设x的个体域为有理数集合，则命题可表示为： x I(x） 2022/7/2215.第15页，共74页。 4. 论 域 含有量词的命题的表达式的形式，与论域有关。用量词量化后的命题，其值也与论域有关。 例 1 x（x=0) 若论域为整数集，则此命题值为真， 若论域为正整数集，则命题的值为假。 为了方便，引入全总个体域，记为：U，简称全域: 定义:宇宙间所有的个体聚集在一起所构成的集合称为全域。 2022/7/2216.第16页，共74页。特性谓词后面的讨

9、论中，除特殊说明外，均使用全域。而对个体变化的真正取值范围，用特性谓词加以限制。 一般地，对全称量词，特性谓词作蕴含的前件引入；而对存在量词，特性谓词常作为合取项引入。2022/7/2217.第17页，共74页。例 (1) “所有的人都是要死的。” (2) “有的人不怕死。” 1.当x的个体域为全体人组成的集合时，符号化上述命题。解: 令D（x）：x是要死的，令G（x）：x怕死。 则（1）可表示为: x D(x)。 （2）可表示为: x G(x)。 2022/7/2218.第18页，共74页。论域为全域时2. 当取x的个体域为全域时，必须引入一个特性谓词将“人”从全域中分离出来。 （1）对所有

10、个体而言，如果它是人，则它是要死的。 （2）存在着个体，它是人并且它不怕死 于是令 M（x）：x是人。 （1） x（M(x)D(x) （2） x (M（x） G（x） 2022/7/2219.第19页，共74页。命题符号化(翻译)：将汉语(或其他自然语言)语句翻译成逻辑表达式，这在数学、逻辑编程、人工智能、软件工程以及许多其他学科中都是一项重要的任务。翻译的目的是生成简单而有用的逻辑表达式。20.第20页，共74页。命题符号化：例：没有不犯错误的人令H（x）： x是人， M（x）： x犯错误例：存在着偶质数令E(x)：x是偶数，P(x)：x是质数则有：x(E(x)P(x)2022/7/2221

11、.第21页，共74页。例：每个自然数都有后继数若令：N（x）：x 是自然数， H（x，y）：y是x的后继数例：对平面上的任意两点，有且仅有一条直线通过这两点。若令P（x）： x是一个点，L（x）：x是一条直线，T（x，y，z）：z通过x，y，E（x，y）：x等于y2022/7/2222.第22页，共74页。 例5 将下列命题符号化(使用全域)。 (1) 发光的并非都是金子 令：P（x）：x发光；G（x）：x是金子。则该命题可表示为 ： （2）所有运动员都钦佩某些教练。 令：P（x）：x是运动员；T（x）：x是教练；Q（x，y）：x钦佩y。则该命题可表示为 ：2022/7/2223.第23页，共

12、74页。 （3）凡是实数均能比较大小。 若令R（x）：x是实数；G（x，y)：x与y可比较大小. 则该命题可表示为：例6将苏格拉底三段论进行符号化：令：(x)：x是人(x): x要死则2022/7/2224.第24页，共74页。 量化断言与命题的关系 (1)如果论述域是有限的，不妨设论述域是1，2，3，则 x P(x)P(1)P(2)P(3) x P(x) P(1)P(2)P(3) (2) 如果论述域是可数无限，例如自然数集合，我们可以这样理解： (x)P(x) P(1)P(2)P(3) (x)P(x) P(1)P(2)P(3) (3)如果论述域不可数无限，则无法表达。 2022/7/2225

13、.第25页，共74页。练习 任何金属都可以溶解在某种液体中.令J(x):x是金属; E(x):x是液体;S(x，y):x可以溶解在y中，2022/7/2226.第26页，共74页。原子与公式 设P(x1，xn)是n元谓词，则称其为为原子公式，或简称原子谓词公式，简称为公式，其递归定义为：（1）原子是合式公式；（2）若A是合式公式，则(A)也是合式公式；（3）若A，B是合式公式，则(AB)， (AB)， (AB)， (AB)也是合式公式；（4）若A是合式公式，x是A中的变量符号，（5）只有有限次地使用（1）（4）所生成的符号串才是合式公式。2022/7/2227.第27页，共74页。前面各命题符

14、号化的结果都是合式公式。对于一个谓词，如果其中每一个变量都在一个量词的作用之下，则它就不再是命题函数而是一个命题了。但是，这种命题和命题逻辑中的命题还是有区别的。因为这种命题中毕竟还有变量，尽管这种变量和命题函数中的变量有所不同。因此，有必要区分这些变量。2022/7/2228.第28页，共74页。例1 ：令 P（x， y）：“ xy.则A(y)是真命题原因是:条件2)不满足。2022/7/2258.第58页，共74页。存在推广规则EG 使用此规则时注意: (1) c是个体域中某个确定的个体。 (2) 代替c的x不能已在A(c)中出现。例如：设A(x，y):xy，考查下面的推理过程: (1)

15、A(x，c) (2) 是错误的！原因在于代替c的x已在A(x)中出现2022/7/2259.第59页，共74页。存在指定规则(ES规则):成立条件：1) c是使A(c)为真的常量符号3)A(x)中的自由变元只有x.例如：设D为自然数集， F(x)表示“x是奇数”，G(x)表示“x是偶数”.注意：以上四条规则中的A(x)都是公式2022/7/2260.第60页，共74页。但，若不注意使用条件，则有：前提引入化简，根据（1）ES规则，根据（2）化简，根据（1）ES规则，根据（4）合取，根据（3），（5）EG规则，根据（6）于是得出：（）违反了条件2）2022/7/2261.第61页，共74页。例

16、1 证明：证明如下：前提引入US规则，根据（1）前提引入ES规则，根据（3）化简，根据（4）化简，根据（4）假言推理，根据（2），（6）合取，根据（5），（7）EG规则，根据（8）2022/7/2262.第62页，共74页。本例也可作如下证明：前提引入ES规则，根据（1）化简，根据（2）前提引入US规则，根据（4）假言推理，根据(3)，(5)化简，根据（2）合取，根据（6），（7）EG规则，根据（8）2022/7/2263.第63页，共74页。例 2 证明： 苏格拉底三段论“凡人都是要死的，苏格拉底是人，所以苏格拉底是要死的”。证明:结论: D(a)首先将命题符号化：设M(x):x是人. D(

17、x):x是要死的. a:苏格拉底.前提:证明:规则US规则，（1）规则假言推理，（2），（3）2022/7/2264.第64页，共74页。例 3有些病人相信所有的医生，但是病人都不相信骗子。证明：医生都不是骗子。证明：命题符号化：设论域为全域 P(x):x是病人；D(x):x是医生；Q(x):x是骗子；R(x，y):x相信y。前提：x(P(x)y(D(y)R(x，y)， xy(P(x)Q(y)R(x，y)结论：x(D(x)Q(x)证明：2022/7/2265.第65页，共74页。x(P(x)y(D(y)R(x，y) 前提引入P(c)y(D(y)R(c，y) ES，(1)xy(P(x)Q(y)R

18、(x，y) 前提引入y(P(c)Q(y)R(c，y) US，(3)P(c)Q(z)R(c，z) US，(4)(P(c)Q(z)R(c，z) 蕴涵等值式，(5)P(c)Q(z)R(c，z) De Morgan律，(6)P(c)(Q(z)R(c，z) 蕴涵等值式，(7)P(c) 化简，(2)Q(z)R(c，z) 析取三段论，(8)，(9)R(c，z)Q(z) 等值演算，(10)y(D(y)R(c，y) 化简，(2)D(z)R(c，z) US，(12)D(z)Q(z) 假言三段论，(11)，(13)x(D(x)Q(x) UG，(14) 2022/7/2266.第66页，共74页。例 4：指出下面推理

19、的错误x(F(x)G(x) 前提引入F(y)G(y) US，(1)xF(x) 前提引入F(y) ES，(3)G(y) 假言推理，(2)，(4)xG(x) UG，(5)没有满足ES规则的条件1即： xA(x)A(c)c是使A(c)为真的常量符号。 F(c) ES，(3) G(c) 假言推理，(2)，(4)xG(x) EG，(5)2022/7/2267.第67页，共74页。例证明下述论证的正确性人会说话，猴子不会说话，因此猴子不是人。解：设论域为全域。设 M(x):x是人。 S(x): x会说话。B(x):x是猴子。则前提为：x(M(x)S(x)和 x(B(x)S(x) 结论为： x(B(x)M(

20、x)证明: 1 x(M(x)S(x) P规则，前提 2 M(x)S(x) T，1，US 3 x(B(x)S(x) P规则，前提 4 B(x)S(x) T，3，US 5 S(x) B(x) T，4， 逆反律 6 M(x) B(x) T，2，5，I6 7 B(x) M(x) T，6，逆反律 8 x(B(x)M(x) T，7，UG2022/7/2268.第68页，共74页。练习：符号化下列命题，并论证其结论：任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或 者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。命题符号化：设P(x):x喜欢步行。Q(x):x喜欢乘汽车. R(x)

21、:x喜欢骑自行车。推理的形式结构：2022/7/2269.第69页，共74页。结构形式：前提引入ES，(1)前提引入US ，(3)(5)Q(c) 析取三段论 (2)，(4).前提引入(7) P(c)Q(c)US，(6)(8) Q(c) P(c) 等值演算，(7).EG，(9).证明：推理如下：(9) P(c) 假言推理 (5)，(8).102022/7/2270.第70页，共74页。谓词逻辑应用实例-逻辑程序设计有一类重要的程序设计语言使用谓词逻辑的规则进行推理。例如:Prolog(Programming in Logic),Prolog程序包括一组声明，有两类语句:Prolog事实和Prolog规则。P