• / 35
  • 下载费用:10 金币  

第2章 重庆大学谓词逻辑.ppt

关 键 词:
第2章 重庆大学谓词逻辑.ppt
资源描述:
表示具体的或特定的个体的词称为个体常项或个体常元,一般用小写英文字母a,b,c,…, ai,bi,ci表示。,第2章 谓词逻辑,§2.1 谓词逻辑基本概念,1 个体,个体变项的取值范围称为个体域或论域,个体域可以是有限事物的集合,如D={1,2,3}等,也可以是无限事物的集合,如自然数集合N等。当未指定个体域时,将宇宙间一切事物组成的客体集合作为个体域,称为全总个体域。,定义2.1:个体是指可以独立存在的客观实体。,,表示抽象的或泛指的个体的词称为个体变项或个体变元,常用小写英文字母x,y,z,…, xi,yi,zi表示,§2.1 谓词逻辑基本概念,例:对于下面3个简单命题:(1)2是偶数。(2)小王和小李是好朋友。(3)小刘坐在小张和小赵的中间。其个体可以表示为:,a:2,b:小王 c:小李,d:小刘 e:小张 f:小赵,§2.1 谓词逻辑基本概念,2 谓词,如上面三个命题可以表示为:F(a):2是偶数。G(b,c):小王和小李是好朋友。H(d,e,f):小刘坐在小张和小赵的中间。,定义2.2:刻画个体具有的性质或个体之间的关系的词叫谓词。,表示具体性质或关系的谓词称为谓词常项或谓词常元,表示抽象的或泛指的谓词称为谓词变项或谓词变元,谓词常项和谓词 变项都用大写英文字母如F,G,H,…,Fi,Gi,Hi等表示。因此,要根据上下文来确定表示的是谓词常项还是变项。,§2.1 谓词逻辑基本概念,谓词中包含的个体数称为元数。含n(n≥1)个个体的谓词称为n元谓词。一元谓词常表示所含个体的性质,n(n≥2) 元谓词常表示所含个体的之间的关系。,一般, n元谓词表示以个体变项的个体域为定义域,以{0,1}为值域的n元函数,并且n个个体变项的顺序不能随意改动。,若一个谓词中不含个体变项称这个谓词为0元谓词。如F(a),G(b,c),H(d,e,f),它们都是0元谓词,但不是命题,当给F、G、H赋以确切的意义,它们才是命题。可见,命题逻辑中的任何简单命题都能用0元谓词表示,并且命题逻辑中的所有联结词在谓词逻辑中都能应用,所以,命题只是谓词的特殊情况,任意命题都能在谓词逻辑中符号化。,(1)全称量词:自然语言中常用的“所有”、“都”、“任何一个”、“一切”、 “凡”统称为全称量词,用符号“”表示。x表示个体域中的所有个体,x F (x)表示个体域中的所有个体都具有性质F。,§2.1 谓词逻辑基本概念,例:用0元谓词符号化下列命题:林平不仅喜欢唱歌,而且喜欢跳舞。,解:F (x):x喜欢唱歌。 G (x):x喜欢跳舞。a:林平。 命题符号化为:F (a) ∧ G (a)。,3 量词,定义2.3:量词,(2)存在量词:自然语言中常用的“存在”、“有一些”、“至少有一个”、“有一个” 统称为存在量词,用符号“”表示。 x表示个体域中存在个体, x F (x)表示个体域中存在个体具有性质F。,§2.1 谓词逻辑基本概念,在谓词逻辑中进行命题的符号化,首先应明确个体变项的取值范围即个体域。如符号化下列命题:(1)所有的人都是要死的。(2)有的人精神永存。,对于上面两个命题指定个体域D为人类集合,则分别符号化为:(1) x F (x),其中F (x):x是要死的。(2)  x G (x),其中G (x):x精神永存。,若不指定个体域,则指的是全总个体域,此时上面两个命题确切叙述为:(1)对于所有的个体,如果它是人,则它是要死的。(2)存在一些个体,它是人并且精神永存。,§2.1 谓词逻辑基本概念,(1) x (M (x) →F (x))(2) x (M (x) ∧G (x)),引入用于限定个体域的词:M (x):x是人,称谓词逻辑中这种限定个体域的词为特性谓词。上面两个命题确切符号化为:,若D={a1,a2, …,an},则对于任意的谓词F (x)都有:(1)  x F (x)F(a1)∧ F(a2) ∧… ∧ F (an)(2)  x F (x)F(a1)∨ F(a2) ∨… ∨ F (an),§2.1 谓词逻辑基本概念,4 命题符号化,在谓词逻辑中将命题符号化,即明确个体域后,分别找出个体常项、个体变项、量词、谓词,按照原命题的意思用适当的联结词将它们组合,此外: (1)引入特性谓词时,全称量词和存在量词的符号化形式不同。 (2)多个量词同时出现时,它们的顺序不能随意颠倒。,例:符号化命题:存在x,使x+2=0,个体域分别为:(1)自然数集合 (2)整数集合 (3)实数集合,解:不用引入特性谓,在上述3个个体域中,均符号化为: x F (x),其中F (x): x+2=0 。但在个体域为(1)时,为假命题,为(2)(3)时,为真命题。,§2.1 谓词逻辑基本概念,例:将下列命题符号化:有的自然数是偶数。个体域分别为: (1)自然数集合(2)实数集合(3)全总个体域,解:(1)不用引入特性谓词符号化为:  x F (x),其中,F (x):x是偶数,(2) 引入特性谓词M (x):x是自然数符号化为:  x ( M (x) ∧F (x) ),其中,F (x):x是偶数,(3) 引入特性谓词M (x):x是自然数符号化为:  x ( M (x) ∧F (x) ),其中,F (x):x是偶数,在上面3个个体域中,均为真命题。,(2)符号化为: ﹁  x ( M (x) → F (x) ),其中M (x):x是大学生;F (x): x能成才。 本命题还可叙述为“存在一些大学生不能成才”,符号化为: x ( M (x) ∧﹁ F (x) ),§2.1 谓词逻辑基本概念,例:将下列命题符号化:(1)没有人不爱看电视。(2)并非所有的大学生都能成才。,解:本题未指定个体域,所以取全总个体域为个体域。(1)符号化为: ﹁  x ( M (x) ∧﹁F (x) ),其中M (x):x是人;F (x): x爱看电视。本命题还可叙述为“所有的人都爱看电视”,符号化为: x ( M (x) →F (x) ),(2)符号化为: x y ( M (x)∧M (y)∧H (x , y)→ z ( M (z) ∧L(x , y , z ))其中M (x):x是实数; H (x , y):x<y;L (x , y , z):x ≤ z ≤y。,§2.1 谓词逻辑基本概念,例:多元谓词的符号化: (1)所有对顶角都相等。(2)任何两个实数之间都存在无穷多个实数。,解:(1)符号化为: x  y ( M (x) ∧M (y) ∧H (x , y) → L (x , y))其中M (x):x是角;H (x , y):x和y互为对顶角; L (x , y):x=y。,命题的符号化是没有止境的,只做到能明确表明命题的意思,满足后面对推理有效性讨论要求就可以了。,说明,作业5(A本)P51:3,§2.2 谓词公式及其解释,1 谓词公式,同命题逻辑中的命题公式类似,谓词公式是由一系列个体常项符号、个体变项符号、函数符号、谓词符号、量词符号、联结词符号等组成。,定义2.4 项的构成如下:,(1)个体常项和个体变项是项。 (2)若f(x1,x2, …,xn)是n元函数,t1,t2, …,tn是项,则f (t1,t2, …,tn)也是项。 (3)仅当有限次地应用(1)、(2)生成的符号串是项。,§2.2 谓词公式及其解释,定义2.5 设P(x1,x2, …,xn)是任意的n元谓词, t1,t2, …,tn是项,则称P (t1,t2, …,tn)为原子谓词公式,简称原子公式。,定义2.6 谓词公式,谓词公式的最外层括号可以省略,并将谓词公式简称为公式。,§2.2 谓词公式及其解释,2 约束变项和自由变项,定义2.7 在谓词公式x A和x A中,x称为指导变项,A称为相应量词的辖域。辖域中x的所有出现称为约束出现,x称为约束变项,A中不是约束出现的其它变项的出现称为自由出现,自由出现的变项称为自由变项。,例:对于 x ( F (x)∧  y P (x , y) ), y P (x , y)中,y为指导变项,量词 的辖域为P (x , y),其中,y是约束出现的,x是自由出现的。整个公式中,x为指导变项,量词 的辖域为( F (x)∧  y P (x , y) ),x、y都是约束出现的,其中,x约束出现2次,y约束出现1次。,因此,在一个公式中,有的个体变项既是约束出现的,又是自由出现的,如上面②中的x。为避免混淆,常采用下面规则:,§2.2 谓词公式及其解释,定义2.8 设A是任一公式,若A中无自由出现的个体变项,则称A为封闭的公式,简称闭式。,(1)约束变项换名规则 将量词辖域中出现的某个约束变项及其对应的指导变项,改成公式中未曾出现过的个体变项符号,公式中其余部分不变。 (2)自由变项代替规则 将公式中某自由变项用原公式中未曾出现过的某个个体变项符号代替,且处处代替。,如:①  x ( F (x)∧ M (x) )是闭式,而②  x F (x) → y G (x , y) 不是闭式,定义2.9 为使公式成为真值确定的命题而指定的有关规定,叫做谓词公式的一个解释I。一个解释I由下面4部分组成:,§2.2 谓词公式及其解释,如:对于 x F (x) → y G (x , y) ) 利用换名规将x改成z得: z F (z) → y G (x , y) ) 利用代替规用z代替x得: x F (x) → y G (z , y) ),(1)特定的个体域D; (2)D中一部分特定元素; (3)D上每个函数变项所取的具体函数; (4)D上每个谓词变项所取的具体谓词。,3 谓词公式的解释,§2.2 谓词公式及其解释,例 给定解释I如下:(1)D1={2,3} (2)D1中特定元素a=3(3)函数f (x)为f(2)=2,f(3)=3(4)谓词F (x)为F(2)=1,F(3)=0;G (x , y)为G (i , j)=0,i,j=2,3H (x , y)为H(2,3)=H(3,2)=1; H(2,2)=H(3,3)=0判断在解释I下,下列公式的真值:(1) x y H (x , y)(2) x ( F( x )∧G( x , a) )(3) x ( F (f (x) )∧G (x , f (x) ) ),§2.2 谓词公式及其解释,解 (1) 原式 ( H(2,2)∨H(2,3))∧(H(3,2)∨H(3,3)) (0 ∨1) ∧(1 ∨ 0)1∧11,(2) 原式 ( F(2)∧G(2,3))∧ (F(3)∧G(3,3)) (1 ∧ 0) ∧(0 ∧ 0)0,(3) 原式 ( F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) ( F(2)∧G(2,2))∨(F(3)∧G(3,3)) (1 ∧ 0) ∨(0 ∧ 0) 0,定义2.10 设A为一谓词公式: (1)若A在任何解释下都为真,则称A为逻辑有效式(永真式); (2)若A在任何解释下都为假,则称A为矛盾式(永假式); (3)若至少存在一个解释使A为真,则称A为可满足式;,§2.2 谓词公式及其解释,4 谓词公式的分类,定义2.11 设A0是含命题变项p1,p2,…,pn的命题公式;A1,A2,…,An是n个谓词公式。用Ai( i=1,2,…,n)代换A0中每一处pi所得公式A称为A0的代换实例。,如:F( x ) ∧ G( x )是p ∧ q的代换实例;x F (x)∨  x G( x ) → H( x )是p ∨ q →r的代换实例。,解:①此公式是p → ( p ∨ q )的代换实例,在命题逻辑中它为重言式,因此原公式为逻辑有效式。②此公式是﹁( p → q ) ∧ q 的代换实例,在命题逻辑中它为矛盾式,因此原公式也为矛盾式。,§2.2 谓词公式及其解释,定理2.1 命题公式中的重言式的代换实例在谓词公式中为逻辑有效式;命题公式中的矛盾式的代换实例在谓词公式中仍为矛盾式。,例:判断下列公式的类型①  x F (x) → ( x F (x) ∨  y G (y) )②﹁( L (x , y) → P (x , y) ) ∧ P (x , y),§2.3 谓词逻辑等值式,定义2.12 设谓词逻辑中任意两个公式A、B,若A ↔ B为逻辑有效式,则称A与B为等值式,记作AB。,说明:由于命题逻辑中重言式的代换实例在谓词逻辑中都是逻辑有效式,因此1.3中给出的24个等值式的代换实例都是谓词逻辑中的等值式。另外,对某公式运用2.2节中给出的换名规则与代替规则后,所得公式与原来的公式等值。,下面给出谓词逻辑中其它一些重要的等值式:,1 量词否定等值式,设A (x)为任意的谓词公式,则有: (1)﹁ x A (x)  x﹁ A (x) (2)﹁ x A (x)  x﹁ A (x),§2.3 谓词逻辑等值式,2 量词辖域收缩与扩张等值式,设A (x)是含自由变项x的公式,B是不含变项X的公式,则: (1) ① x ( A (x) ∨ B )  x A (x) ∨ B② x ( A (x) ∨ B )  x A (x) ∨ B③ x ( A (x) ∧ B )  x A (x) ∧ B④ x ( A (x) ∧ B )  x A (x) ∧ B (2) ① x ( A (x) → B )  x A (x) → B② x ( A (x) → B )  x A (x) → B③ x ( B → A (x) )  B → x A (x)④ x ( B → A (x) )  B → x A (x),§2.3 谓词逻辑等值式,3 量词分配等值式,设A (x)和B (x)是含自由变项x的任意公式,则有: (1) x ( A (x) ∧ B ( x ) )  x A (x) ∧ x B (x) (2) x ( A (x) ∨ B ( x ) )  x A (x) ∨ x B (x),称(1)为 对∧的分配,(2)为 对∨的分配。,4 量词交换等值式,设A (x , y) 是任意的含x , y自由出现的谓词公式,有: (1) x y A (x , y)  y x A (x , y) (2) x y A (x , y)  y x A (x , y),作业6(B本)P52:11,§2.4 前束范式,定义2.13 如果一个谓词公式A具有如下形式Q1x1Q2x2…QkxkB 其中,Qi(i=1,2, …,k)为量词 或 ,B为不含量词的谓词公式,则称A为前束范式。,如 x y ( F (x) ∧ G (y) → L (x , y) )是前束范式,而x ( F (x) → y ( G (y) ∧ L (x , y) ) )不是前束范式。,即一个前束范式就是量词全在公式的开头,而量词的整个辖域延伸到整个公式的末尾的句子。,定理 任意谓词公式都有一个与之逻辑等值的前束范式。,求一个给定公式的前束范式,就是利用各种等值式及等值规则进行等值演算,把所有量词都变换到公式的开头。,§2.4 前束范式,例 求公式 x F (x) → x G (x)的前束范式。,解 方法①:x F (x) → x G (x) ﹁ x F (x) ∨ x G (x) x﹁ F (x) ∨ x G (x) x (﹁ F (x) ∨ G (x) ),方法②:x F (x) → x G (x) x F (x) → y G (y) x ( F (x) → y G (y) ) x y ( F (x) → G (y) ),可见,对一个公式运用不同规则进行变换,可得到不同的前束范式,其缺点是形式不唯一。,,§2.4 前束范式,例 求公式x F (x) ∨y G (x, y)的前束范式。,①:约束变项换名规则x F (x) ∨y G (x, y)  z F (z) ∨y G (x, y)  z (F (z) ∨y G (x, y))  z y (F (z) ∨ G (x, y)),②:自由变项代替规则x F (x) ∨y G (x, y)  x F (x) ∨y G (z, y)  x (F (x) ∨y G (z, y))  x y (F (x) ∨ G (z, y)),解 分别采用约束变项换名规则和自由变项代替规则,,①前束范式中的各指导变项应各不相同 ②原公式中的自由变项在前束范式中还应是自由变项,说明,§2.5 谓词逻辑的推理理论,定理2.14 设谓词逻辑中任意两个公式A、B,若A→B为逻辑有效式,则称A蕴涵B,记作A  B。,前面介绍的命题逻辑中的重言蕴涵式,这些蕴涵式在谓词逻辑中的代入实例都是有效蕴涵式。另外,由等值式与蕴涵式的关系可知,每一个等值式均可当作两个有效蕴涵式使用。,关于量词分配的几个常用蕴涵式:,① x (A (x) → B (x))  x A (x) → x B (x) ② x (A (x) → B (x))  x A (x) →  x B (x) ③ x (A (x) ∧ B (x))  x A (x) ∧  x B (x) ④ x A (x) ∨ x B (x)  x ( A (x) ∨ B (x) ),§2.5 谓词逻辑的推理理论,定理2.15 对于谓词公式A1,A2,…,An,B,若有A1∧ A2 ∧ … ∧ An  B 则称B为A1,A2,…,An逻辑结论或有效结论,也称B可由一组前提A1,A2,…,An逻辑推出,记为A1,A2,…,An ╞ B,谓词逻辑中的推理是命题逻辑中推理的推广。,1 UI(全称量词消去规则),两种形式:① x A (x)  A (y)② x A (x)  A (c) 其中, A是谓词,①中y为任意不在A (x)中约束出现的个体变元;②中c为个体域中的任意一个个体常元。,§2.5 谓词逻辑的推理理论,2 UG(全称量词引入规则),A (y)  x A (x) 其中, y为个体域中任意一个个体,且y取任何值时A均为真;x不在A (y)中约束出现。,3 EI(存在量词消去规则), x A (x)  A (c) 其中, c为个体域中某个确定的个体常项,且使A为真;c不曾在A (x)中出现过; A (x)中没有自由变项。,§2.5 谓词逻辑的推理理论,4 EG(存在量词引入规则),A (c)   x A (x) 其中, c为个体域中某个个体常项;x不在A (c)中出现。,例 证明苏格拉底三段论:凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的。,解 命题符号化:M (x):x是人。 F (x):x是要死的。 a:苏格拉底。前提:x ( M (x) →F (x) ),M (a);结论:F (a),证明:① x ( M (x) →F (x) ) 前提引入② M (a) →F (a) ①UI ③ M (a) 前提引入④ F (a) ②③假言推理,§2.5 谓词逻辑的推理理论,例 构造并证明下面的推理:参加比赛者都是计算机系的学生并且是高级程序员。有些参赛者是女生。所以有的参赛者是女高级程序员。,解 命题符号化:M (x):x是参赛者。 F (x):x是计算机系的学生。G (x):x是高级程序员。 H (x):x是女生。前提:x (M (x) →F (x) ∧ G (x)), x (M (x) ∧H (x))结论:x (M (x) ∧H (x) ∧G (x) ),证明:① x (M (x) ∧H (x)) 前提引入② M (c) ∧ H (c) ①EI ③ x (M (x) →F (x) ∧ G (x)) 前提引入④ M (c) →F (c) ∧ G (c) ③UI,§2.5 谓词逻辑的推理理论,证明:⑤ M (c) ②化简⑥ F (c) ∧ G (c) ④⑤假言推理⑦ G (c) 前提引入 ⑥化简⑧ H (c) ②化简⑨ M (c) ∧ F (c) ∧ G (c) ⑤⑦⑧合取⑩ x (M (x) ∧H (x) ∧G (x) ) ⑨UG,注意:运用EI、UI消去公式中的量词时,一定是针对前束范式。若不是前束范式,如﹁ x( F (x) ∧H (x) ),应先变换为前束范式 x (﹁ F (x) ∨﹁ H (x) ) ,再进行推理。,作业7(B本)P52:12(1) P53:13(4)、15,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第2章 重庆大学谓词逻辑.ppt
链接地址:https://www.weizhuannet.com/p-10036024.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开