交大数理逻辑课件4-1 谓词逻辑的基本概念.ppt

《交大数理逻辑课件4-1 谓词逻辑的基本概念.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件4-1 谓词逻辑的基本概念.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作业讲评1第1章习题nP12：2(2)用自然语言叙述：(P Q)n设设P：今天很冷，：今天很冷，Q：正在下雪：正在下雪n(PQ)：今天：今天不是不是既既很冷很冷又又下雪下雪nP13：5(7)形式自然语言：n如果如果水是清的，水是清的，那么那么或者或者张三能见到池底张三能见到池底或者或者他是个近视眼他是个近视眼n设设P：水是清的，：水是清的，Q：张三能见到池底，：张三能见到池底，R：张本是个近视眼：张本是个近视眼 P(QR)(Q R)P (Q R)不可兼或不可兼或第1章习题nP13：6将下公式写成波兰式和逆波兰式(1)PQ R S P Q R S P Q R S (3)(3)P(W R)Q P

2、W R Q 或 P W R Q P W R Q 第4章谓词逻辑的基本概念 4.1谓词和个体词4.2函数和谓词4.3合式公式4.4自然语句的形式化4.5 有 限 域 下 公 式(x)P(x)、(x)P(x)的表示法4.6公式的普遍有效性和判定问题一阶逻辑 在命题逻辑中最基本的研究对象是命题一一个个原原子子命命题题是是不不能能再再分分割割的的,两两个个命命题题之之间间没没有有任任何何内在的联系内在的联系这这种种研研究究方方法法显显然然不不足足以以刻刻划划世世界界上上事事物物间间千千变变万万化化的逻辑关系的逻辑关系就连最古老、最简单的苏格拉底三段论也无法从命题逻辑中推出前提：凡人都是要死的前提：凡人

3、都是要死的 p 苏格拉底是人苏格拉底是人 q结论：苏格拉底是要死的结论：苏格拉底是要死的 rp q r谓词演算谓词演算(一阶谓词演算）是命题演算的扩充和发展一阶谓词演算是重要的符号逻辑系统是重要的符号逻辑系统它它是是程程序序设设计计理理论论、语语义义形形式式化化及及程程序序逻逻辑辑研研究究的的重重要要基基础础，是是程程序序验验证证、程程序序分分析析、综综合合及自动生成及自动生成、定理证明定理证明和和知识表示知识表示的有力工具的有力工具。4.1谓词和个体词n在谓词演算中，将原子命题分解为谓词和个体两部分。如：张三张三是是人人。n个体个体n 可以独立存在的东西，可以独立存在的东西，它可以是一个具体

4、的事它可以是一个具体的事物，也可以是一个抽象的概念。物，也可以是一个抽象的概念。n谓词谓词 用于刻划个体的性质和个体之间的关系用于刻划个体的性质和个体之间的关系 个体个体谓词谓词个体n考察下面的三个原子命题：李玲李玲是优秀共青团员。是优秀共青团员。张华张华比比李红李红高。高。小高小高坐在坐在小王小王和和小刘小刘的中间。的中间。n个体的分类n个体常项个体常项：表示具体或特定个体的标识符表示具体或特定个体的标识符n如如 a：李玲，：李玲，b：张华，：张华，c：李红，：李红，d：小高，：小高，e：小王，：小王，f：小刘：小刘n个体变项个体变项：表示任意个体或泛指某类个体的标识符表示任意个体或泛指某类

5、个体的标识符n如：偶数、生物，如：偶数、生物，用用x,y,z表示表示n 个体域个体域D个体变项的变化范围n有限个体域：有限个体域：如如a,b,c,1,2n无限个体域：无限个体域：如如N,Z,R,n全总个体域全总个体域:宇宙间一切事物组成（宇宙间一切事物组成（默认的个体域默认的个体域）谓词n考察下面的三个原子命题：李玲李玲是优秀共青团员是优秀共青团员。张华张华比比李红李红高高。小高小高坐在坐在小王小王和和小刘小刘的中间的中间。n谓词:用于刻划个体性质或各个个体的关系，常用大写英文字母表示。n谓词常项谓词常项：n如：如：F:是人是人，则，则 F(a)：a是人是人n谓词变项谓词变项：n如：如：F:具

6、有性质具有性质F，则，则F(x)：x具有性质具有性质Fn如：可用如：可用F，G，H表示上面三个命题中谓词：表示上面三个命题中谓词：F：是优秀共青团员。是优秀共青团员。G：比比高。高。H：坐在坐在和和的中间的中间。谓词n考察下面的三个原子命题：李玲李玲是优秀共青团员是优秀共青团员。张华张华比比李红李红高高。小高小高坐在坐在小王小王和和小刘小刘的中间的中间。n如：可用F，G，H表示上面三个命题中谓词：F：是优秀共青团员。是优秀共青团员。G：比比高。高。H：坐在坐在和和的中间的中间。n谓词的分类n 一元谓词一元谓词:刻划一个个体的性质，如谓词刻划一个个体的性质，如谓词F(x)n 多元谓词多元谓词:刻

7、划两个或以上个体间的关系，刻划两个或以上个体间的关系，n 如如 L(x,y)：x与与y有关系有关系L，L(x,y)：x y，n如谓词如谓词G(x,y)、H(x,y,z)n0元元谓谓词词:不不含含个个体体变变项项的的谓谓词词,即即命命题题常常项项或或命命题变项题变项 F(a)G(b,c)H(d,e,f)a：李玲，：李玲，b：张华，：张华，c：李红，：李红，d：小高，：小高，e：小王，：小王，f：小刘小刘n函数n它是某个体域到另一个体域的映射，由一个谓词它是某个体域到另一个体域的映射，由一个谓词字母和字母和n个个体变项组成的表达式：个个体变项组成的表达式：F(x,y,z)n注意：n F(x,y,z

8、)不是命题，它的真值无法确定，要想不是命题，它的真值无法确定，要想使它成为命题，必须指定某一谓词常项代替使它成为命题，必须指定某一谓词常项代替F，同同时还要用时还要用n个个体常项代替个个体常项代替n个个体变项。个个体变项。n 如：如：L(x,y)是一个二元谓词，它不是命题。是一个二元谓词，它不是命题。n当令当令L表示表示“小于小于”之后，之后，L(x,y)还不是命题。还不是命题。n当令当令a=2，b=3时，时，L(a,b)才是命题，并且是真命题。才是命题，并且是真命题。n当令当令c=2，d=1时，时，L(c,d)为假命题。为假命题。4.2函数和量词 将下列命题用谓词符号化(1)如果23，则33

9、，q：3y，G(x,y)：xy,n命题符号化为命题符号化为 F(2,3)G(3,4)(2)2是素数且是偶数。n在命题逻辑中在命题逻辑中,设设 p:2是素数是素数,q:2是偶是偶数数n命题符号化为：命题符号化为：p q,这是真命题这是真命题n在一阶逻辑中在一阶逻辑中,设设F(x)：x是素数。是素数。G(x)：x是偶数。是偶数。a：2，n命题命题符号化为：符号化为：F(a)G(a)将下列命题用谓词符号化(3)如果张明比李民高，李民比李民高，则张明比赵亮高。解：在命题逻辑中，设：p：张明比李民高，q：李民：李民比李民高 r：张明比赵亮高则命题符号为则命题符号为：p qr在一阶逻辑中，设H(x,y)：

10、x比y高。a：张明；b：李民；c：赵亮，则命题符号化为：则命题符号化为：H(a,b)H(b,c)H(a,c)4.2.2量词n引入量词表示个体域中所有个体或部分个体具有某种性质。n全称量词全称量词:表示任意的表示任意的,所有的所有的,一切的等一切的等n如如:x 表示对个体域中所有的表示对个体域中所有的x xF(x)表示个体域里的所有个体都有性质表示个体域里的所有个体都有性质Fn存在量词存在量词:表示存在表示存在,有的有的,至少有一个等至少有一个等n如如:x 表示在个体域中存在表示在个体域中存在x xF(x)表示存在着个体域中的个体具有性质表示存在着个体域中的个体具有性质F（1 1）每个人都有一双

11、手。每个人都有一双手。每个人都有一双手。每个人都有一双手。（2 2）有的人很聪明。有的人很聪明。有的人很聪明。有的人很聪明。（1 1）每个人都有一双手。每个人都有一双手。每个人都有一双手。每个人都有一双手。（2 2）有的人很聪明。有的人很聪明。有的人很聪明。有的人很聪明。第一种情况考虑个体域D为人类集合。(1)符号化为：符号化为：xF(x)，其中其中F(x)：x都有一双手都有一双手都有一双手都有一双手。这个命题是真命题。这个命题是真命题。(2)符号化为符号化为 xF(x)，其中其中F(x)：x很聪明很聪明很聪明很聪明。这个命题也是真命题。这个命题也是真命题。在一阶逻辑中将下面命题符号化（1 1

12、）每个人都有一双手。每个人都有一双手。每个人都有一双手。每个人都有一双手。（2 2）有的人很聪明。有的人很聪明。有的人很聪明。有的人很聪明。第二种情况，考虑个体域D为全总个体域。引出一个新的谓词，将人分离出来引出一个新的谓词，将人分离出来:M(x)：x是人。是人。称这个谓词为称这个谓词为特性谓词特性谓词。在全总个体域的情况下，以上两命题可叙述如下在全总个体域的情况下，以上两命题可叙述如下(1)对所有个体而言，如果它是人，则它有一双手对所有个体而言，如果它是人，则它有一双手。(2)存在着个体，它是人并且很聪明。存在着个体，它是人并且很聪明。则（则（1）符号化为）符号化为 x(M(x)F(x)（2

13、）符号化为符号化为 x(M(x)F(x)，在一阶逻辑中将下面命题符号化4.2.3约束变元和自由变元 n定义定义 n在在公公式式(x)A和和(x)A中中，称称x为为指指导导变变元元，称称A为为辖辖域域.n 在在 x和和 x的辖域中，的辖域中，nx的所有出现都称为的所有出现都称为约束出现，约束出现，nA中不是约束出现的其他变元均称为是中不是约束出现的其他变元均称为是自由变元自由变元。n如：在公式(x)(F(x,y)G(x,z)中n A=(F(x,y)G(x,z)为为 x的辖域，的辖域，n x是是约束变元约束变元，y与与z均为自由变元。均为自由变元。n如(x)P(x)(z)Q(x,z)(y)R(x,

14、y)Q(x,y)n在在 x中，中，x、y、z是约束变元，是约束变元，nQ(x,y)中中x，y是自由变元。是自由变元。n闭式闭式:不含自由变元的公式.约束变元的换名规则n如：如：(x)P(x)R(x,y)n(x)的辖域为的辖域为P(x)，x是约束变元是约束变元nR(x,y)中中x,y 都是自由变元都是自由变元nx既可以是约束的、又可以是自由的，容易混淆。既可以是约束的、又可以是自由的，容易混淆。n换名规则n将将量量词词辖辖域域中中的的某某个个约约束束出出现现的的个个体体变变项项及及对对应应的的指指导导变变项项改改成成公公式式中中未未曾曾出出现现的的个个体体变变项项符符号号，公公式式中中的的其其余

15、部分不变。余部分不变。n注意：n改名时一定要更改为辖域中没有出现的变元名称改名时一定要更改为辖域中没有出现的变元名称。n例如：(x)P(x)R(x,y)n改名为：改名为：(z)P(z)R(x,y)或(x)P(x)R(z,y)自由变元的代入规则n代替规则n对某自由出现的个体变项用与原公式中所有个体变对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。项符号不同的变项符号去代替，且处处代替。n注意：n用以代入的变项与原公式中所有变项名不能相同用以代入的变项与原公式中所有变项名不能相同n如：(x)F(x)G(x,y)n利用代替规则：利用代替规则：(x)F(x)G(z,

16、y)n(x)P(x)(z)Q(x,z)(y)R(x,y)Q(x,y)n对对Q(x,y)中自由出现的中自由出现的x用用t代入，代入，y用用s代入则：代入则：(x)P(x)(z)Q(x,z)(y)R(x,y)Q(t,s)4.3 合式公式(谓词公式)n量词的作用范围：量词的作用范围：n量量词词仅仅作作用用于于个个体体变变元元，不不允允许许作作用用于于命命题题变变项项和和谓词变项，不出现：谓词变项，不出现：n(p)(F(x,y)p),(F)(F(x,y)G(x,z)n本课程中用到的符号说明：n命题变项：命题变项：p,q,r,pi,qi,ri,i 1n个体变项：个体变项：x,y,z,xi,yi,zi,i

17、 1 n个体常项：个体常项：a,b,c,ai,bi,ci,i 1n谓词变项：谓词变项：P,Q,R,Pi,Qi,Ri,i 1n谓词常项：谓词常项：GREAT,ON,n函数符号：函数符号：f,g,h,fi,gi,hi,i 1n量词符号：量词符号：,n联结词符号：联结词符号：,n括号与逗号：括号与逗号：(,),，合式公式(谓词公式)n合式公式合式公式定义如下：定义如下：(1)命命题题常常项项、命命题题变变项项和和原原子子谓谓词词公公式式（不含联结词的谓词）是合式公式（不含联结词的谓词）是合式公式.(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式 (3)若若A,B是是合合式式公公

18、式式，则则(A B),(A B),(AB),(AB)也是合式公式也是合式公式 (4)若若A是是合合式式公公式式，而而x在在A中中是是自自由由变变元元，则则(x)A,(x)A 也是合式公式也是合式公式 (5)只有适合以上只有适合以上4条的才是条的才是合式公式合式公式.n如：如：(x)(M(x)F(x)4.4自然语句的形式化n自然数集的形式描述对每个数，有且仅有一个相继后元对每个数，有且仅有一个相继后元解：注意到题目中没给个体域,一律用全总个体域设：谓词E(x,y)：x=y函数f(x)=x+1(表示个体x的相继后元)理解为：对每个对每个x都存在都存在y,y是是x的相继后元，且对任一的相继后元，且对

19、任一z，若它也，若它也是是x的相继后元，则必有的相继后元，则必有y=z形式化为：(x)(y)(E(y,f(x)(z)(E(z,f(x)E(y,z)自然语句的形式化n自然数集的形式描述没有这样的数，没有这样的数，0是其相继后元是其相继后元解：注意到题目中没给个体域,一律用全总个体域设：谓词E(x,y)：x=y函数f(x)=x+1(表示个体x的相继后元)理解为：不存在不存在x，它的相继后元为，它的相继后元为0 形式化为：形式化为：(x)(E(0,f(x)自然语句的形式化n自然数集的形式描述对除对除0外的数，有且仅有一个相继前元外的数，有且仅有一个相继前元解：注意到题目中没给个体域,一律用全总个体域

20、设：谓词E(x,y)：x=y函数g(x)=x-1(表示个体x的相继前元)理解为：对每个对每个x,若若x0,都存在都存在y,y是是x的相继前元，且对任一的相继前元，且对任一z，若它也是，若它也是x的相继前元，则必有的相继前元，则必有y=z形式化为：(x)(E(x,0)(y)(G(y,f(x)(z)(G(z,f(x)E(y,z)在使用量词时，应注意以下特点n在不同个体域中，命题符号化的形式可能不一样。n如如“有的人很聪明。有的人很聪明。有的人很聪明。有的人很聪明。”n在人类集合个体域中，在人类集合个体域中，xF(x)n在全总个体域中，在全总个体域中，x(M(x)F(x)n若事先没有给出个体域，都默

21、认为全总个体域。n在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的n如如“有的人很聪明。有的人很聪明。有的人很聪明。有的人很聪明。”x(M(x)F(x)n如如“每个人都有一双手每个人都有一双手每个人都有一双手每个人都有一双手”x(M(x)F(x)全称量词后是条件式全称量词后是条件式存在量词后是合取式存在量词后是合取式在使用量词时，应注意以下特点n个体域和谓词的含义确定之后，n元命题函数要转化为命题至少需要n个量词。n当个体域为有限集时，如D=a1,a2,a3,.an。对于任意谓词，都有n x A(x)=A(a1)A(a2)A(an)n x A(x)=A(a1)A(a2)A(an)n

22、这实际上是将一阶逻辑中命题公式转化为命题逻辑中这实际上是将一阶逻辑中命题公式转化为命题逻辑中的命题公式问题。的命题公式问题。n多个量词同时出现时，不能随意颠倒它们的顺序。颠倒后可能会改变原命题的含义随意颠倒量词顺序可能会改变原命题的含义n取个体域为实数集，H（x，y）：x+5=y则xyH（x，y）n表示表示“对任意的对任意的x，存在着存在着y，使得使得x+5=y。”n这是个这是个真命题真命题。n将量词的顺序颠倒，得，yxH（x，y）n表示表示“存在着存在着y，对任意的对任意的x，都有都有x+5=y”，n这是这是假命题假命题。作业5P66:1(1)(5)(7)(10)P67:3P67:5(1)(4)(8)P67:6(1)(8)