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

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

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

3、概念和符号。关于命题、命题的真值、命题词、命题常量和命题变元以及逻辑五个联结词其含意和在命命题词、命题常量和命题变元以及逻辑五个联结词其含意和在命题逻辑中的基本相同，题逻辑中的基本相同，o本章中只介绍谓词逻辑中新出现的基本概念和符号，其中主要的本章中只介绍谓词逻辑中新出现的基本概念和符号，其中主要的是是个体词，谓词，量词以及函词个体词，谓词，量词以及函词。2022-7-245.第5页，共74页。1.谓词与个体词 将简单命题分解成个体与谓词这样两个组成部分。谓词，通常是用来描述个体的性质或特征，或者个体之间的关系。谓词逻辑，是命题逻辑的扩充与发展。例例1 1：下面两个命题 1.张华是学生 2.李

4、明是学生 a:张华 b:李明 H H：是学生，则 H H（x x）:x是学生 1，2可分别表示成 H(a)H(a)，H(b).H(b).这样表示就揭示了两命题间有相同的谓语这一特征。2022-7-246.第6页，共74页。例例2 2：张华比李明高 令 a:张华 b:李明 L(x，y):x高于y 该命题可表示为：L(aL(a，b)b)例1和例2中的 H、L称为谓词，其中H是一元谓词，表示个体的性质（是什么），L是二元谓词，表示个体之间的关系。注注：（1）常用大写拉丁字母表示谓词常用大写拉丁字母表示谓词.（2）谓词是用来刻划个体的性质或者个体之间的关谓词是用来刻划个体的性质或者个体之间的关系的。系

5、的。2022-7-247.第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元谓词元谓词.n.n元谓词反映了个体之间元谓词反映了个体之间的的n n元关系元关系.2022-7-248.第8页，共74页。2.个体词个体词v个体是可以独立存在的实体，它可以是一个具体的个体是可以独立存在的实体，它可以是一个具体的 事

6、物事物-个体常元，个体常元，常用小写拉丁字母常用小写拉丁字母a，b，c等表示。等表示。也可以是一个抽象的概念（即没指定哪一个个体）也可以是一个抽象的概念（即没指定哪一个个体）-个体变元个体变元，常用小写拉丁字母：，常用小写拉丁字母：x，y，z等表示等表示2022-7-249.第9页，共74页。函词函词例：张华的哥哥比李明高张华的哥哥比李明高 a:张华 b:李明 L(x，y):x高于y f(x):x的哥哥则上述符号化为：L(f(a)L(f(a)，b)b)f f称为函词函词定义定义：一个：一个n n元函词元函词即是一个论域上的一个即是一个论域上的一个n n元函数元函数2022-7-2410.第10

7、页，共74页。v 变元在谓词中的次序直接影响了谓词的取值变元在谓词中的次序直接影响了谓词的取值 。如:设谓词P(x，y)为“x比y高”，设张三为170cm，李四为180cm.则:P(李四，张三)为真命题。P(张三，李四)为假命题.概念的讨论概念的讨论2022-7-2411.第11页，共74页。命题的符号化命题的符号化o 例例1:武汉位于重庆与上海之间武汉位于重庆与上海之间.n解:用个体词a，b，c分别表示武汉，重庆和上海，谓词P(x，y，z)表示x位于y与z之间，则该命题表示为:P(a，b，c).p 例例2：如果王英坐在李红的后面，则王英比李红高：如果王英坐在李红的后面，则王英比李红高.解：令

8、 a:王英;b:李红;P(x，y):x坐在y的后面;G(x，y):x比y高.则该命题表示为：P(a，b)G(a，b).2022-7-2412.第12页，共74页。3.量词量词 使用前面介绍的概念，还不足以表达日常生活中的各种命题。使用前面介绍的概念，还不足以表达日常生活中的各种命题。例如：例如：“所有的正整数都是素数所有的正整数都是素数”“有些正整数是素数有些正整数是素数”两种量词两种量词:全称量词和存在量词全称量词和存在量词.2022-7-2413.第13页，共74页。全称量词全称量词:1.全称量词全称量词：（任意，所有）（任意，所有）x:“对一切对一切x”，“对所有的对所有的x”，“对任一

9、对任一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-2414.第14页，共74页。存在量词存在量词:2.存在量词：存在量词：（存在）（存在）x:“存在存在x“、”某些某些x“、”至少有一至少有一x”如：如：x P(x)“存在存在x，P(x)是真是真”x P(x)“存在存在x，P(x)是真，并非这样是真，并非这样”x P(x)“存在存在x

10、，P(x)是真是真”如如:“有些有理数是整数。有些有理数是整数。”令(x）：x是整数，设x的个体域为有理数集合，则命题可表示为：x I(x）2022-7-2415.第15页，共74页。4.4.论论 域域 含有量词的命题的表达式的形式，与论域有关。用量词量化后含有量词的命题的表达式的形式，与论域有关。用量词量化后的命题，其值也与的命题，其值也与论域论域有关有关。例例 1 1 x x（x=0)x=0)若论域为整数集，则此命题值为真，若论域为整数集，则此命题值为真，若论域为正整数集，则命题的值为假。若论域为正整数集，则命题的值为假。为了方便，引入全总个体域，记为：为了方便，引入全总个体域，记为：U

11、U，简称，简称全域全域:定义定义:宇宙间所有的个体聚集在一起所构成的集合称为宇宙间所有的个体聚集在一起所构成的集合称为全域。全域。2022-7-2416.第16页，共74页。特性谓词特性谓词o后面的讨论中，除特殊说明外，均使用后面的讨论中，除特殊说明外，均使用全域全域。而对个体变化的。而对个体变化的真正取值范围，用特性谓词加以限制。真正取值范围，用特性谓词加以限制。一般地，对全称量词，特性谓词作蕴含的前件引入；而对存在量词一般地，对全称量词，特性谓词作蕴含的前件引入；而对存在量词，特性谓词常作为合取项引入。，特性谓词常作为合取项引入。2022-7-2417.第17页，共74页。例例 (1)“(

12、1)“所有的人都是要死的。所有的人都是要死的。”(2)“(2)“有的人不怕死。有的人不怕死。”1.1.当当x x的个体域为的个体域为全体人全体人组成的集合时，符号化上述命题。组成的集合时，符号化上述命题。解解:令令D D（x x）：）：x x是要死的，令是要死的，令G G（x x）：）：x x怕死。怕死。则（则（1 1）可表示为）可表示为:x x D(x)D(x)。（2 2）可表示为）可表示为:x x G(x)G(x)。2022-7-2418.第18页，共74页。论域为全域时论域为全域时2.当取当取x x的个体域为全域时，必须引入一个特性谓词将的个体域为全域时，必须引入一个特性谓词将“人人”从

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

14、误的人令H（x）：x是人，M（x）：x犯错误例：存在着偶质数例：存在着偶质数令E(x)：x是偶数，P(x)：x是质数则有：则有：x(E(x)P(x)x(E(x)P(x).()()()(:xMxHxxMxHx则有2022-7-2421.第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等于y).,()()(:yxHyNyxN

15、x则有).,(),()(),()()()(:zuEuyxTuLuzyxTzLzyPxPyx则有2022-7-2422.第22页，共74页。例例5 将下列命题符号化将下列命题符号化(使用全域使用全域)。(1)发光的并非都是金子发光的并非都是金子 令：令：P（x）：）：x发光；发光；G（x）：）：x是金子。是金子。则该命题可表示为则该命题可表示为：（2）所有运动员都钦佩某些教练。）所有运动员都钦佩某些教练。令：令：P（x）：）：x是运动员；是运动员；T（x）：）：x是教练；是教练；Q（x，y）：）：x钦佩钦佩y。则该命题可表示为则该命题可表示为：2022-7-2423.第23页，共74页。（3）凡

16、是实数均能比较大小。）凡是实数均能比较大小。若令若令R（x）：）：x是实数；是实数；G（x，y)：x与与y可比较大小可比较大小.则该命题可表示为：则该命题可表示为：例例6将苏格拉底三段论进行符号化：将苏格拉底三段论进行符号化：令：令：(x)：x是人是人(x):x要死要死则则2022-7-2424.第24页，共74页。量化断言与命题的关系量化断言与命题的关系(1)1)如果论述域是有限的，不妨设论述域是如果论述域是有限的，不妨设论述域是11，2 2，33，则，则 x P(x)x P(x)P(1)P(2)P(3)P(1)P(2)P(3)x P(x)x P(x)P(1)P(2)P(3)P(1)P(2)

17、P(3)(2)(2)如果论述域是可数无限，例如自然数集合，我们可以这样理解：如果论述域是可数无限，例如自然数集合，我们可以这样理解：(x)P(x)x)P(x)P(1)P(2)P(3)P(1)P(2)P(3)(x)P(x)x)P(x)P(1)P(2)P(3)P(1)P(2)P(3)(3)(3)如果论述域不可数无限，则无法表达如果论述域不可数无限，则无法表达。2022-7-2425.第25页，共74页。练习练习 任何金属都可以溶解在某种液体中任何金属都可以溶解在某种液体中.令J(x):x是金属;E(x):x是液体;S(x，y):x可以溶解在y中，);,()()(:yxSyEyxJx则可以表示为20

18、22-7-2426.第26页，共74页。原子与公式原子与公式 设设P(x1，xn)是是n元谓词，则称其为为原子公式，或简元谓词，则称其为为原子公式，或简称称原子原子谓词公式，简称为谓词公式，简称为公式公式，其递归定义为：，其递归定义为：（1）原子是合式公式；）原子是合式公式；（2）若）若A是合式公式，则是合式公式，则(A)也是合式公式；也是合式公式；（3）若）若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式；也是合式公式；（4）若）若A是合式公式，是合式公式，x是是A中的变量符号，中的变量符号，（5）只有有限次地使用（）只有有限次地使用（1）（4）所生成的

19、符号串）所生成的符号串才是合式公式。才是合式公式。.,也是合式公式则xAxA 2022-7-2427.第27页，共74页。o 前面各命题符号化的结果都是合式公式。前面各命题符号化的结果都是合式公式。o对于一个谓词，如果其中每一个变量都在一个量词的作用之下，对于一个谓词，如果其中每一个变量都在一个量词的作用之下，则它就不再是命题函数而是一个命题了。则它就不再是命题函数而是一个命题了。o 但是，这种命题和命题逻辑中的命题还是有区别的。因但是，这种命题和命题逻辑中的命题还是有区别的。因为这种命题中毕竟还有变量，尽管这种变量和命题函数中为这种命题中毕竟还有变量，尽管这种变量和命题函数中的变量有所不同。

20、因此，有必要区分这些变量。的变量有所不同。因此，有必要区分这些变量。2022-7-2428.第28页，共74页。例例1 ：令：令 P（x，y）：）：“xy.),()(yxxFyA令则A(y)是真命题,),(是假命题规则后的式子：但使用xxxFxUG是错误的。故)()(xxAyA原因是:条件2)不满足。2022-7-2458.第58页，共74页。存在推广规则存在推广规则EG)()(:)(xxAcAEG规则 使用此规则时注意使用此规则时注意:(1)c是个体域中某个确定的个体。是个体域中某个确定的个体。(2)代替代替c的的x不能已在不能已在A(c)中出现。中出现。例如：设例如：设A(x，y):xy，

21、考查下面的推理过程，考查下面的推理过程:(1)A(x，c)(2),(xxxA是错误的！原因在于代替是错误的！原因在于代替c的的x已在已在A(x)中出现中出现2022-7-2459.第59页，共74页。存在指定规则存在指定规则(ES规则规则):)()(cAxxA成立条件：成立条件：1)c是使是使A(c)为真的常量符号为真的常量符号;),()(,)2acaBxxB则比如规则若在此之前也使用过该若推理过程中3)A(x)中的自由变元只有x.例如例如：设D为自然数集，F(x)表示“x是奇数”，G(x)表示“x是偶数”.)()(是真命题则xxGxxF注意：以上四条规则中的注意：以上四条规则中的A(x)都是

22、公式都是公式2022-7-2460.第60页，共74页。但，若不注意使用条件，则有：)()()1(xxGxxF前提引入)()2(xxF化简，根据（1）)()3(cFES规则，根据（2）)()4(xxG化简，根据（1）)()5(cGES规则，根据（4）)()()6(cGcF合取，根据（3），（5）)()()7(xGxFxEG规则，根据（6）于是得出：)()()()(xGxFxxxGxxF（）违反了条件2）2022-7-2461.第61页，共74页。例例 1 证明：证明：)()()()()()(xCxBxxAxCxxBxAx证明如下：)()()1(xBxAx前提引入)()()2(yByAUS规则，

23、根据（1）)()()3(xAxCx前提引入)()()4(aAaCES规则，根据（3）)()5(aC化简，根据（4）)()6(aA化简，根据（4）)()7(aB假言推理，根据（2），（6）)()()8(aCaB合取，根据（5），（7）)()()9(xCxBxEG规则，根据（8）2022-7-2462.第62页，共74页。本例也可作如下证明：)()()1(xAxCx前提引入ES规则，根据（1）)()3(aA化简，根据（2）)()()4(xBxAx前提引入)()()5(aBaAUS规则，根据（4）)()6(aB假言推理，根据(3)，(5)()7(aC化简，根据（2）)()()8(aCaB合取，根据（

24、6），（7）)()()9(xCxBxEG规则，根据（8）)()()2(aAaC2022-7-2463.第63页，共74页。例例 2 证明证明：苏格拉底三段论苏格拉底三段论“凡人都是要死的，苏格拉底是人，凡人都是要死的，苏格拉底是人，所以苏格拉底是要死的所以苏格拉底是要死的”。证明证明:结论:D(a)首先将命题符号化：设M(x):x是人.D(x):x是要死的.a:苏格拉底.)(),()(aMxDxMx前提:证明:)()()1(xDxMx)()()2(aDaM)()3(aM)()4(aD规则US规则，（1）规则假言推理，（2），（3）2022-7-2464.第64页，共74页。例例 3o有些病人相

25、信所有的医生，但是病人都不相信骗子。证明：医生都不有些病人相信所有的医生，但是病人都不相信骗子。证明：医生都不是骗子。是骗子。o证明：证明：o命题符号化：设论域为全域命题符号化：设论域为全域 P(x):x x是病人；是病人；D(x):x是医生；是医生；Q(x):x是骗子；是骗子；R(x，y):x相信相信y。o前提：前提：x(P(x)y(D(y)R(x，y)，x y(P(x)Q(y)R(x，y)o结论：结论：x(D(x)Q(x)o证明：证明：2022-7-2465.第65页，共74页。1)1)x(x(P(x)P(x)y(D(y)Ry(D(y)R(x(x，y)y)前提引入前提引入2)2)P(c)P

26、(c)y(D(y)Ry(D(y)R(c(c，y)ESy)ES，(1)(1)3)3)x x y(y(P(x)P(x)Q(y)Q(y)R R(x(x，y)y)前提引入前提引入4)4)y(y(P(c)P(c)Q(y)Q(y)R R(c(c，y)USy)US，(3)(3)5)5)P(c)P(c)Q(z)Q(z)R R(c(c，z)USz)US，(4)(4)6)6)(P(c)P(c)Q(z)Q(z)R R(c(c，z)z)蕴涵等值式，蕴涵等值式，(5)(5)7)7)P(c)P(c)Q(z)Q(z)R R(c(c，z)De Morganz)De Morgan律，律，(6)(6)8)8)P(c)(P(c)(

27、Q(z)Q(z)R R(c(c，z)z)蕴涵等值式，蕴涵等值式，(7)(7)9)9)P(c)P(c)化简，化简，(2)(2)10)10)Q(z)Q(z)R R(c(c，z)z)析取三段论，析取三段论，(8)(8)，(9)(9)11)11)R R(c(c，z)z)Q(z)Q(z)等值演算，等值演算，(10)(10)12)12)y(D(y)Ry(D(y)R(c(c，y)y)化简，化简，(2)(2)13)13)D(z)RD(z)R(c(c，z)USz)US，(12)(12)14)14)D(z)D(z)Q(z)Q(z)假言三段论，假言三段论，(11)(11)，(13)(13)15)15)x(x(D(x

28、)D(x)Q(x)UGQ(x)UG，(14)(14)2022-7-2466.第66页，共74页。例例 4：指出下面推理的错误：指出下面推理的错误1)1)x(F(x)G(x)x(F(x)G(x)前提引入前提引入2)2)F(y)G(y)USF(y)G(y)US，(1)(1)3)3)xF(x)xF(x)前提引入前提引入4)4)F(y)ESF(y)ES，(3)(3)5)5)G(y)G(y)假言推理，假言推理，(2)(2)，(4)(4)6)6)xG(x)UGxG(x)UG，(5)(5)没有满足ES规则的条件1即：xA(x)A(c)c是使A(c)为真的常量符号。F(c)ES，(3)G(c)假言推理，(2)

29、，(4)xG(x)EG，(5)2022-7-2467.第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(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，

30、逆反律逆反律 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-2468.第68页，共74页。练习：符号化下列命题，并论证其结论：练习：符号化下列命题，并论证其结论：a)任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或 者者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。有的人不爱步行。o命题符号化：设命题符号化：设P(x):x喜欢步行。喜欢步行。Q(x):x喜欢乘汽车喜欢乘汽车.R(x

31、):x喜欢喜欢骑自行车。骑自行车。o推理的形式结构：推理的形式结构：)()()()(),()()(),()()(xPxxRxxRxQxxQxPx2022-7-2469.第69页，共74页。结构形式：)()()()(),()()(),()()(xPxxRxxRxQxxQxPx)()(1(xRx前提引入)()2(cRES，(1)()()()(3(xRxQx前提引入)()()4(cRcQUS，(3)(5)Q(c)析取三段论 (2)，(4).)()()()(6(xQxPx前提引入(7)P(c)Q(c)US，(6)(8)Q(c)P(c)等值演算，(7).)()(9(xPx EG，(9).o 证明：推理如

32、下：(9)P(c)假言推理(5)，(8).102022-7-2470.第70页，共74页。谓词逻辑应用实例谓词逻辑应用实例-逻辑程序设计逻辑程序设计o有一类重要的程序设计语言使用谓词逻辑的规则进行推理。o例如:Prolog(Programming in Logic),Prolog程序包括一组声明，有两类语句:Prolog事实和Prolog规则。Prolog事实通过指定那些满足谓词的元素来定义谓词。Prolog规则使用Prolog事实定义好的谓词来定义新的谓词。(主要应用在人工智能方面)71.第71页，共74页。o例1,考虑一个Prolog程序，它给出的事实是每门课程的教师和学生注册的课程，程序

33、使用这些事实来回答有关给特定学生上课的教授的查询。o此程序中的Prolog事实可能包含:instructor(chan,math273)instructor(patel,ee222)instructor(grossman,cs301)enrolled(kevin,math273)enrolled(juana,ee222)enrolled(juana,cs301)enrolled(kiko,math273)enrolled(kikoi,cs301)则一个新的谓词teacher(p,s)表示教授p教学生s，可以用prolog规则来定义:teacher(P,S):-instructor(P,C),enrolled(S,C)(Prolog中用逗号表示谓词的合取)Prolog使用给定的事实和规则回答查询。如:？Enrolled(kevin,math273)生成应答 yes?Enrolled(x,math273)生成应答 kevin kiko?teacher(x,jinna)返回 patel grossman72.第72页，共74页。本章习题:o 1.6：1，3，9，10，（13，17，21，22）o 1.7:2，6，7o 1.8:3，4，5，7（8）2022-7-2473.第73页，共74页。2022-7-2474.第74页，共74页。