离散数学(高教版)第4章.ppt

《离散数学(高教版)第4章.ppt》由会员分享，可在线阅读，更多相关《离散数学(高教版)第4章.ppt（30页珍藏版）》请在三一办公上搜索。

1、1,主要内容一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑命题符号化一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式,第四章 一阶逻辑基本概念,2,4.1 一阶逻辑命题符号化,个体词所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事务，用a,b,c表示 个体变项：抽象的事物，用x,y,z表示 个体域(论域)个体变项的取值范围 有限个体域，如 a,b,c,1,2 无限个体域，如 N,Z,R,全总个体域由宇宙间一切事物组成,3,谓词,谓词表示个体词性质或相互之间关系的词 谓词常项 如,F(a)：a是人 谓词变项 如,F(x)：x具有性质F n（n1）

2、元谓词 一元谓词(n=1)表示性质 多元谓词(n2)表示事物之间的关系 如,L(x,y)：x与 y 有关系 L，L(x,y)：xy，0元谓词不含个体变项的谓词,即命题常项 或命题变项,4,量词,量词表示数量的词 全称量词:表示所有的.x:对个体域中所有的x 如,xF(x)表示个体域中所有的x具有性质F xyG(x,y)表示个体域中所有的x和y有关系G 存在量词:表示存在,有一个.x:个体域中有一个x 如,xF(x)表示个体域中有一个x具有性质F xyG(x,y)表示个体域中存在x和y有关系G xyG(x,y)表示对个体域中每一个x都存在一个y使得 x和y有关系G xyG(x,y)表示个体域中存

3、在一个x使得对每一个y,x和y有关系G,5,实例1,例1 用0元谓词将命题符号化(1)墨西哥位于南美洲(2)是无理数仅当 是有理数(3)如果23，则34,解：在命题逻辑中：(1)p,p为墨西哥位于南美洲（真命题）(2)pq,其中,p：是无理数，q：是有理数.是假命题(3)pq,其中，p：23，q：34.是真命题,6,实例1解答,在一阶逻辑中：(1)F(a)，其中，a：墨西哥，F(x)：x位于南美洲.(2)F()G(),其中，F(x)：x是无理数，G(x)：x是有理数(3)F(2,3)G(3,4)，其中，F(x,y)：xy，G(x,y)：xy,7,实例2,例 2 在一阶逻辑中将下面命题符号化(1

4、)人都爱美(2)有人用左手写字个体域分别为(a)D为人类集合(b)D为全总个体域,解(a)(1)xG(x),G(x)：x爱美,(2)xG(x),G(x)：x用左手写字,(b)F(x)：x为人，G(x)：x爱美,(1)x(F(x)G(x),(2)x(F(x)G(x),1.引入特性谓词F(x)2.(1),(2)是一阶逻辑中两个“基本”公式,8,实例3,例3 在一阶逻辑中将下面命题符号化(1)正数都大于负数(2)有的无理数大于有的有理数,解 注意：题目中没给个体域，一律用全总个体域(1)令F(x)：x为正数，G(y)：y为负数,L(x,y)：xy,x(F(x)y(G(y)L(x,y)或者 xy(F(

5、x)G(y)L(x,y),(2)令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xy,x(F(x)y(G(y)L(x,y)或者 xy(F(x)G(y)L(x,y),9,实例4,例4 在一阶逻辑中将下面命题符号化(1)没有不呼吸的人(2)不是所有的人都喜欢吃糖,解(1)F(x):x是人,G(x):x呼吸,x(F(x)G(x),x(F(x)G(x),(2)F(x):x是人,G(x):x喜欢吃糖,x(F(x)G(x),x(F(x)G(x),10,实例5,例5 设个体域为实数域,将下面命题符号化(1)对每一个数x都存在一个数y使得xy(2)存在一个数x使得对每一个数y都有xy,解 L(x,

6、y):xy,(1)xyL(x,y),注意:与不能随意交换显然(1)是真命题,(2)是假命题,(2)xyL(x,y),11,4.2 一阶逻辑公式及解释,定义4.1 设L是一个非逻辑符集合,由L生成的一阶语言L 的字母表包括下述符号：非逻辑符号(1)个体常项符号：a,b,c,ai,bi,ci,i 1(2)函数符号：f,g,h,fi,gi,hi,i 1(3)谓词符号：F,G,H,Fi,Gi,Hi,i 1逻辑符号(4)个体变项符号：x,y,z,xi,yi,zi,i 1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，,12,一阶语言L 的项与原子公式,定义4.2 L 的项的定义如下：(

7、1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的 n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的 如,a,x,x+y,f(x),g(x,y)等都是项,定义4.3 设R(x1,x2,xn)是L 的任意n元谓词，t1,t2,tn 是L 的任意n个项，则称R(t1,t2,tn)是L 的原子公式.如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式,13,定义4.4 L 的合式公式定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(

8、AB),(AB),(AB)也是 合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串才是合式公式.合式公式简称公式 如,F(x),F(x)G(x,y),x(F(x)G(x)xy(F(x)G(y)L(x,y)等都是合式公式,一阶语言L 的公式,14,封闭的公式,定义4.5 在公式 xA 和 xA 中，称x为指导变元，A为相应量词的辖域.在x和 x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如，x(F(x,y)G(x,z)，x为指导变元，(F(x,y)G(x,z)为x 的辖域，x的两次出现均为约束出现，y与

9、z 均为自由出现又如,x(F(x,y,z)y(G(x,y)H(x,y,z),x中的x是指导变元,辖域为(F(x,y,z)y(G(x,y)H(x,y,z).y中的y是指导变元,辖域为(G(x,y)H(x,y,z).x的3次出现都是约束出现,y的第一次出现是自由出现,后2次是约束出现,z的2次出现都是自由出现,15,封闭的公式,定义4.6 若公式A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式.例如，xy(F(x)G(y)H(x,y)为闭式，而 x(F(x)G(x,y)不是闭式,16,公式的解释,定义4.7 设L 是L生成的一阶语言,L 的解释I由4部分组成：(a)非空个体域 DI.(b)

10、对每一个个体常项符号aL,有一个 DI,称 为a在I 中的解释.(c)对每一个n元函数符号fL,有一个DI上的n元函数,称 为f在I中的解释.(d)对每一个n元谓词符号FL,有一个DI上的n元谓词常项,称 为F在I中的解释.,设公式A,取个体域DI,把A中的个体常项符号a、函数符号f、谓词符号F分别替换成它们在I中的解释、,称所得到的公式A为A在I下的解释,或A在I下被解释成A.,17,实例,例6 给定解释 I 如下：(a)个体域 D=R(b)(c)(d)写出下列公式在I下的解释,并指出它的真值.(1)xF(f(x,a),g(x,a),x(x+0=x0)真,(2)xy(F(f(x,y),g(x

11、,y)F(x,y),xy(x+y=xyx=y)假,(3)xF(g(x,y),a),x(xy=0)真值不定,不是命题,18,公式的类型,定理4.1 闭式在任何解释下都是命题注意:不是闭式的公式在解释下可能是命题,也可能不是命题.定义4.8 若公式A在任何解释下均为真,则称A为永真式(逻辑有效式).若A在任何解释下均为假,则称A为矛盾式(永假式).若至少有一个解释使A为真,则称A为可满足式.几点说明：永真式为可满足式，但反之不真 判断公式是否是可满足的(永真式,矛盾式)是不可判定的,19,代换实例,定义4.9 设A0是含命题变项 p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(

12、1in)处处代替A0中的pi，所得公式A称为A0的代换实例.例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例.定理4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,20,实例,例7 判断下列公式中，哪些是永真式，哪些是矛盾式？(1)xF(x)(xyG(x,y)xF(x),重言式 p(qp)的代换实例，故为永真式.,(2)(xF(x)yG(y)yG(y),矛盾式(pq)q 的代换实例，故为永假式.,(3)x(F(x)G(x),解释I1:个体域N,F(x):x5,G(x):x4,公式为真 解释I2:个体域N,F(x):x5,G(x):x4,公式为假结论:非永真式的可

13、满足式,21,第四章 习题课,主要内容个体词、谓词、量词一阶逻辑命题符号化一阶语言L 项、原子公式、合式公式公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释公式的类型 永真式(逻辑有效式)、矛盾式(永假式)、可满足式,22,基本要求,准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解释 记住闭式的性质并能应用它 深刻理解永真式、矛盾式、可满足式的概念,会判断简 单公式的类型,23,练习1,1.在分别取个体域为(a)D1=N(b)D2=R(c)D3为全总个体域的条件下,将下面命题符号化，并讨论真值(1)对于任意的数x，均有,解 设G(

14、x):(a)xG(x),(b)xG(x),(c)又设F(x):x是实数 x(F(x)G(x),真,真,假,24,练习1(续),解 设H(x)：x+7=5(a)xH(x),(2)存在数x，使得 x+7=5,(b)xH(x),(c)又设F(x)：x为实数 x(F(x)H(x),本例说明：不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不同（也可能相同）.,真,真,假,25,练习2,2.在一阶逻辑中将下列命题符号化(1)大熊猫都可爱,(2)有人爱发脾气,(3)说所有人都爱吃面包是不对的,设F(x):x为大熊猫，G(x):x可爱 x(F(x)G(x),设F(x):x是人，G(x):x爱发脾

15、气 x(F(x)G(x),设F(x):x是人，G(x):x爱吃面包 x(F(x)G(x)或 x(F(x)G(x),26,练习2,(4)没有不爱吃糖的人,(5)任何两个不同的人都不一样高,(6)不是所有的汽车都比所有的火车快,设F(x):x是人，G(x):x爱吃糖x(F(x)G(x)或 x(F(x)G(x),设F(x):x是人,H(x,y),x与y相同,L(x,y):x与y一样高 x(F(x)y(F(y)H(x,y)L(x,y)或 xy(F(x)F(y)H(x,y)L(x,y),设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快 xy(F(x)G(y)H(x,y)或 xy(F(x)

16、G(y)H(x,y),27,练习3,x(2x=x)假,3.给定解释 I 如下:(a)个体域D=N(b)=2(c)(d)说明下列公式在 I 下的涵义,并讨论真值(1)xF(g(x,a),x),(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假,28,练习3,(3)xyzF(f(x,y),z),(5)xF(f(x,x),g(x,x),(4)xyzF(f(y,z),x),xyz(y+z=x)假,xyz(x+y=z)真,x(x+x=xx)真,(3),(4)说明与不能随意交换,29,练习4,4.证明下面公式既不是永真式，也不是矛盾式:,(1)x(F(x)G(x),(2)xy(F(x)G(y)H(x,y),解释1:D1=N,F(x):x是偶数,G(x):x是素数,真,解释2:D2=N,F(x):x是偶数,G(x):x是奇数,假,解释1:D1=Z,F(x):x是正数,G(x):x是负数,H(x,y):xy 真,解释2:D2=Z,F(x):x是偶数,G(x):x是奇数,H(x,y):xy 假,30,练习5,5.证明下列公式为永真式:(1)(xF(x)yG(y)xF(x)yG(y),(2)x(F(x)(F(x)G(x),(AB)AB的代换实例,设I是任意的一个解释,对每一个xDI,F(x)(F(x)G(x)恒为真,