泰来娱乐手机版

泰来娱乐手机版官网-泰来娱乐手机版官方网站-三亿鼠标的娱乐梦想

第2章 谓词逻辑(杨圣洪版教材

  离 离 散 散 数 数 学授课教师:刘慧明Email:岛科技大学青岛市郑州路53号(四方校区) 邮编:266042 第二章 谓词逻辑 《 离散数学 》二 章 第 二章 章 谓词逻辑引言命题演算的推理系统是一个完全的公理系统,其表现力还不够强大,有些问题难以用命题演算进行表达。如:著名的 苏格拉底三段论:人总是要死的,因为苏格拉底是人,所以苏格拉底总是要死的。一 这 推理过程无法用命题演算表示。若P:人总是要死的;Q:苏格拉底是人;R:苏格拉底总是要死的。则上面的话用命题公式应该表示为P∧Q→R,但P∧Q→R不是永真式,而事实上这个结论总是对的。 命题演算的局...

  离 离 散 散 数 数 学授课教师:刘慧明Email:.cn青岛科技大学青岛市郑州路53号(四方校区) 邮编:266042 第二章 谓词逻辑 《 离散数学 》二 章 第 二章 章 谓词逻辑引言命题演算的推理系统是一个完全的公理系统,其表现力还不够强大,有些问题难以用命题演算进行表达。如:著名的 苏格拉底三段论:人总是要死的,因为苏格拉底是人,所以苏格拉底总是要死的。一 这 推理过程无法用命题演算表示。若P:人总是要死的;Q:苏格拉底是人;R:苏格拉底总是要死的。则上面的话用命题公式应该表示为PQR,但PQR不是永真式,而事实上这个结论总是对的。 命题演算的局限性: 不能将原子命题进一步分解,无法反映命题之间的内在联系。 《 离散数学 》二 章 第 二章 章 谓词逻辑再如:小陈是大学生小林是大学生P Q P和Q没有任何逻辑联系两句话的共同特征: “是大学生” 主语+谓语“ 谓语P: 是大学生”主语:某某人P(小陈) ;P(小林)P称为谓词小陈、x是客体P(x)是命题函数P(x): x是大学生 可认为谓词逻辑是命题逻辑的推广,命题逻辑中的很多概念、规则都可推广到谓词逻辑中延用 《 离散数学 》二 章 第 二章 章 谓词逻辑本章内容 1 、谓词逻辑的基本概念 2 、 谓词公式及其解释 3 、谓词公式的等值演算 4 、谓词公式的范式 5 、谓词推理 《 离散数学 》1、客体与谓词 客体(个体): 在句子中,可以独立存在的客观实体(一般为句子的主语或宾语)。 客体常用小写字母表示,如:x,y,z,a 1 ,a 2 ,2.1 基本概念 谓词: 刻划客体的性质或几个客体间关系的词项叫谓词。 谓词常用大写字母A,B,,P,Q ,表示。如:3是素数 “3”- 客体 Q:“是素数”- 谓词苹果是红的 “苹果”- 客体 R:“是红的”- 谓词 《 离散数学 》2、客体(个体)常元与客体(个体)变元 客体常元: 表示具体和特定的客体。常用字母表中比较靠前的小写字母a、b、c等表示。如: “ 刘翔要喝水”、“ 姚明要喝水”,其中的“刘翔” “姚明”是客体常量 可用 表示“刘翔” 表示“姚2.1 基本概念”、“姚明”是客体常量。 可用a表示“刘翔”,c表示“姚明”。 客体变元: 表示抽象的或泛指的客体。常用字母表中比较靠后的小写字母如x、y、z等表示如: “ 某某要喝水”可表示为 函数 W(x), W表示谓词“要喝水”,x表示“某某”,泛指所有的人。 《 离散数学 》3、n元谓词 一元谓词:谓词联系着一个客体。如: “苹果是红的”,R:“是红的”联系一个客体,是一元谓词;R(x)表示x是红的。 二元谓词:有两个客体与谓词相联系。2.1 基本概念如: “32”, B:“大于”联系两个客体,是二元谓词;B(x,y)表示x大于y。 n元谓词:n个客体与谓词相联系。如:“李明坐在张华和张洪之间” 三个客体“张华和张洪打败了李明和李良”四个客体 《 离散数学 》4、命题函数由一个谓词字母和n个客体变元组成的表达式H(x1,x2,,xn),称为 命题函数。 (有的书上直接称之为n元谓词)说明: :2.1 基本概念说明: :当个体变元x没有赋予确切的客体时,H(x)没有确切的真值,即并非命题。谓词或命题函数转化为命题 的方法:用特定的客体取代各个客体变元,该过程称为 命题函数的代入实例。如: F(x): x是素数 不是命题a:3, F(a)是命题,(取值为1) 《 离散数学 》5、量词 词 全称量词  为了表示“所有女人都喜欢漂亮衣服”等这类语句中的“所有”, 引入符号“”,称为 全称量词。“ ”表示所有、全部、任意。“All”首字母A的倒写。2.1 基本概念表示所有 全部 任意 首字母 的倒写 当用x泛指“人”,“所有人”表示为“x”,“所有活人都要喝水”表示为  xW(x) 当用x表示“女人”,y表示“漂亮衣服”时,“所有女人”则表示为x、“所有漂亮衣服”则表示为“y”,因此“所有女人都喜欢漂亮衣服”表示为 x x  yL(x,y),其中L(x,y)表示“x喜欢y”。 《 离散数学 》5、量词 词 存在量词  为了表示“有些人考上了研究生”这类语句中“有些、某些”等,引入符号“”, 表示“存在、有些、有部分”等的含义, 称为 存在量词。2.1 基本概念“”是Exist的首字母,左旋180度,如: 若用谓词W表示“考上了研究生”,用z泛指“人”,那么“有些人”表示为“z”,“有些人考上了研究生”表示为zW(z)。表示全部的符号“”,表示部分的符号“”统称为 量词。 《 离散数学 》6、个体域:个体变元的取值范围称为“ 个体域”,常用符号D表示。 如: {人}, {实数,虚数,动物}在不同的客体域中,命题符号化的形式可能不一样,真值也可能不同(详见后面例子。)2.1 基本概念样,真值也可能不同(详见后面例子。)当无特别声明时,将宇宙间的一切事物组成的客体域称为“ 全总个体域”,常用大写字母U表示。 《 离散数学 》 举例:利用量词、谓词将自然语言符号化例2.1.1举例:利用量词、谓词将自然语言符号化例2.1.1 :(1)凡人都要呼吸 (2)有的人用左手写字解 :当个体域为“人类”时:用B(x)表示x呼吸,则(1)表示为xB(x);用 ( )表示 用左手写字 则( )表示为 ( )2.1 基本概念用WL(x)表示x用左手写字,则(2)表示为xWL(x)。当 个体域 为全总 个体域 (宇宙万物组成):需要引入特性谓词, 用H(x)表示个体x是人类,则(1)表示为x(H(x)B(x));(2)表示为x(H(x)WL(x))。个体域不同,谓词公式不同。思考:个体域不同,谓词公式不同。思考: (1)可否表示为x(H(x)B(x))? 《 离散数学 》 举例:利用量词、谓词将自然语言符号化例2.1.2举例:利用量词、谓词将自然语言符号化例2.1.2 (1)任意x,都有x 2 -2x+1=(x-1) 2 .(2)有x,使得x*5=3解:当x的取值范围即个体域为自然数N时:2.1 基本概念用E(x)表示x 2 -2x+1=(x-1) 2 ,则(1)表示为xE(x) (T)用F(x)表示x*5=3,则(2)表示为xF(x) (值为假)当x的个体域为实数R时:用E(x)表示x 2 -2x+1=(x-1) 2 ,则(1)表示为xE(x) (T)用F(x)表示x*5=3,则(2)表示为xF(x) (值为真)谓词公式相同但真值不同 ! 《 离散数学 》【例2.1.6】用谓词公式表示“所有人都会死的,苏格拉底是人,所以苏格拉底也会死”。注:默认个体域为全总个体域,即对个体变元的取值不做任何限制。解 : (分析:整体为蕴含式,共有两个谓词)2.1 基本概念H(x)表示对象x是人类,O(x)表示对象x会死的,则“所有人都会死的”表示为x(H(x)O(x)) ;c表示个体常元“苏格拉底”,则“苏格拉底是人”表示为H(c),“苏格拉底会死”表示为O(c),原句表示为:( (  x(H(x)  O(x)) )  H(c))  O(c) 。谓词 《 离散数学 》小结:一、基本概念1、谓词2、客体(个体),包括个体常元与个体变元3、命题函数2.1 基本概念3、命题函数4、量词,包括全称量词与存在量词5、个体域与全总个体域二、利用量词、谓词将自然语言符号化的方法要求: 掌握利用量词、谓词将自然语言符号化的方法。 《 离散数学 》2.2.1 合法的谓词公式(合式谓词公式)2.2 谓词公式及其解释 所使用的符号约定:(1)个体常元:所使用的符号约定:(1)个体常元: a , b b , c , , a i , b i , c i , i 1(2)个体变元: x , y , z , , x i , y i , z i , i1函 (3) 函数符号: : f , g , h , , f i , g i , h i , i1(4)谓词符号: F , G , H , , F i , G i , H i , i1(5)量词符号:  (6)联结词符: ┐   (7)括号和逗号: ( ) , 《 离散数学 》2.2.1 合法的谓词公式(合式谓词公式)首先引入如下概念:【定义2.2.3】(项的定义) :个体常元、个体变元及其函数表达式称为 项(item)。如: 设命题函数2.2 谓词公式及其解释E(x):x 2 -2*x+1=(x-1) 2个体变元x是一个项;E(3):3 2 -2*3+1=(3-1) 2命题常元3是一个项;E(3+x):(3+x) 2 -2*(3+x)+1=((3+x)-1) 2个体变元、个体常元的函数3+x也是一个项;注意: 项当中 不含有谓词、量词和逻辑联结词。 《 离散数学 》2.2.1 合法的谓词公式(合式谓词公式)首先引入如下概念:【定义2.2.4】(原子公式) :设R(x 1 ,x 2 ,,x n )是n元谓词,t 1 ,t 2 ,,t n 是项,则R(t 1 ,t 2 ,,t n )是原子公式。原子公式。2.2 谓词公式及其解释如: 设命题函数 E(x):x 2 -2*x+1=(x-1) 2E(3):3 2 -2*3+1=(3-1) 2E(3+x):(3+x) 2 -2*(3+x)+1=((3+x)-1) 2E(x)、E(3)、E(3+x)等都是 原子公式。注意: 原子公式中的个体变元,可以换成个体变元的表达式(即:项),但不能出现任何联结词与量词, 只能为单个谓词公式 。 《 离散数学 》2.2.1 合法的谓词公式(合式谓词公式)【定义2.2.5】(合式谓词公式)(1)原子公式是合式公式;(2)若A是合式公式,则(A)也是合式公式;( )若 为合式公式 则2.2 谓词公式及其解释(3)若A、B为合式公式,则AB,AB,AB,AB 也为合式公式。(4)若A为合式公式,则xA、xA为合式公式(5)有限次使用(2)~(4)得到的式子是合式公式。 《 离散数学 》2.2.1 合法的谓词公式(合式谓词公式)如: xy(R(x)T(y)H(x,y))x(H(x)WL(x))等均是合法的公式;F(x)F(y)G(x y)2.2 谓词公式及其解释F(x)F(y)G(x,y)F(y)G(x,y)则不是合法的公式。 后续研究中,不再拘泥于某个有具体含义的语句,直接 从 形式上 研究 合式公式 的性质 。 《 离散数学 》2.2.2 个体变元的身份谓词公式的变元,其身份并不相同,有些变元与量词相关,有些变元与量词无关,相关性不同,其含义并不相同。引入几个概念:1、量词的指导变元:xA和xA中的x量词的辖域 和 中 量词 / 的作用范围 称2.2 谓词公式及其解释2、 量词的辖域:xA和xA中,量词x/x的作用范围A称为 量词  x/  x的辖域。3、约束变元:在x和x的辖域A中出现的个体变元x,称为 约束变元。 这是与量词相关的变元,约束变元的所有出现都称为约束出现 。4、自由变元:谓词公式中与任何量词都无关的变元称为自由变元。 它的每次出现称为自由出现。 《 离散数学 》2.2.2 个体变元的身份例题1 :分析  x(F(x,y)  G(x,z))中变元的身份解 :x是量词的指导变元。(F(x,y)G(x,z))是量词的辖域2.2 谓词公式及其解释在(F(x,y)G(x,z))中x是约束出现,出现2次。在(F(x,y)G(x,z))自由出现的变元为y、z,各一次。 《 离散数学 》2.2.2 个体变元的身份例题2: 分析x(F(x)G(y))y(H(x)L(x,y,z))中变元的身份解:量词的指导变元为x。x的辖域为(F(x)G(y)),约束变元为x,自由变元为y 各出现1次。2.2 谓词公式及其解释元为x,自由变元为y,各出现1次。量词的指导变元为y。y的辖域为H(x)L(x,y,z),约束变元为y,出现1次;自由变元为x、z,其中x出现2次,z出现1次。注意:尽管x在公式x(F(x)G(y))和y(H(x)L(x,y,z))中都出现过,但两个x不是一回事,只是恰巧二个名字相同而矣。好比有2个李勇,一个是正坐在家里看电视的“李勇”,另一个是在马路上散步的“李勇”。 《 离散数学 》2.2.2 个体变元的身份例题2: 分析x(F(x)G(y))y(H(x)L(x,y,z))中变元的身份注意:为避免出现这种“误会”,需要 对其中的“ 约束变元 ”改名 如本例2.2 谓词公式及其解释名 。如本例:将量词 x x的指导变元 x、约束变元x x在 x x辖域中的每次出现换成公式中未出现的r r。将量词 y y的指导变元 y、约束变元y y在 y y辖域中的每次出现换成公式中未出现的s s,则原式化为: r r (F(r r) )  G(y))  s s (H(x)  L(x,s s ,z)),所有约束变元与自由变元均不重名,无误会。 《 离散数学 》2.2.2 个体变元的身份【定义】(闭公式)不含自由变元的谓词公式 。如:x(F(x,y)G(x,z)) 因y,z是自由变元,故不是。xr(P(x,r)Q(r,z))sP(s,y) 因z与y自由,故不是。 (P( )  Q( ) tR( t)) 因 自由故不是2.2 谓词公式及其解释s(P(s)rQ(r,z)tR(s,t)) 因z自由故不是以下公式均没有自由变元,均为闭公式:x(H(x)WL(x))xy(R(x)T(y)H(x,y))xy(R(x)T(y)H(x,y))xy(R(x)R(y)L(x,y)) 《 离散数学 》2.2.3 谓词公式的解释及真值同样的谓词公式,在不同的个体域中,采用不同的解释,其真值是不同的。因此 解释某个公式的含义、确定其真值时,需要注意如下细节解释某个公式的含义、确定其真值时,需要注意如下细节 :(1)个体域是什么? 即:个体的取值范围2.2 谓词公式及其解释( )个体域是什么 即 个体的取值范围(2)个体常元的具体值是什么?即:具体对象(3)原子公式的含义是什么? 即:原义(4)用原子公式的解释来描述整个公式的含义。然后根据个体域中的知识,判断整个公式的含义是否正确;若正确,则公式线 谓词公式的解释及线 : 解释x(F(x)G(x))将: x的取值范围是什么?F(x)的含义是什么?G(x)的含义是什么?这些问题确定后,表达式x(F(x)G(x))的真值就确定了,这就是公式的解释。2.2 谓词公式及其解释释。解释一:个体域:解释一:个体域:dom(x)=D1=全总个体域原子公式的解释:F(x)表示x是人,G(x)表示x是黄种人。则x(F(x)G(x))的含义为:所有的事物,如果是人,则是黄种人。显然这句话是错的,其真值为F。 《 离散数学 》2.2.3 谓词公式的解释及线 : 解释x(F(x)G(x))将: x的取值范围是什么?F(x)的含义是什么?G(x)的含义是什么?将这些问题确定后,表达式x(F(x)G(x))的真值就确定了,这就是公式的解释。2.2 谓词公式及其解释释。解释二:个体域:解释二:个体域:dom(x)=D2=实数集R原子公式的解释:F(x)表示x是自然数,G(x)表示x是整数。则x(F(x)G(x))的含义为:任意一个实数,如果是自然数,则为整数。显然这句话是正确的,其值为T。 《 离散数学 》2.2.3 谓词公式的解释及线 : 设个体变元的值域D=N(自然数集),常 元 a=0, 函 数 f(x,y)=x+y , g(x,y)=x*y , 谓 词F(x,y):x=y。试解释下列各公式的含义:(1) F(f(x,y),g(x,y))2.2 谓词公式及其解释( ) ( ( ,y),g( ,y))(2) xF(g(x,a),x)(3) xyzF(f(x,y),z)(4) xy(F(f(x,a),y)F(f(y,a),x)) 《 离散数学 》2.2.3 谓词公式的解释及线 : 设个体变元的值域D=N(自然数集),常 元 a=0, 函 数 f(x,y)=x+y , g(x,y)=x*y , 谓 词F(x,y):x=y。解: 将个体常元、变元、函数带入到原子公式中。( (1 1) ) ( ( ) ( ))2.2 谓词公式及其解释( (1 1) ) F F( (f f( ( x,y) ) ,g( ( x,y ))原式=F(x+y,x*y),其含义为x+y=x*y,对于自然数x、y,此式 真假不确定,故不是命题。) (2)   xF(g(x,a),x)原式=xF((x*0),x)=xF(0,x),其含义为x (0=x) ,即: “任给一个自然数x,0都等于x” ,显然是错误的; 线 。 《 离散数学 》2.2.3 谓词公式的解释及线 : 设个体变元的值域D=N(自然数集),常 元 a=0, 函 数 f(x,y)=x+y , g(x,y)=x*y , 谓 词F(x,y):x=y。解: 将个体常元、变元、函数带入到原子公式中。( (3 3) ) ( ( ) )2.2 谓词公式及其解释( (3 3) )  x x y y  zF( (f f( ( x,y) ) ,z) )原 式 =   x x   y y   , zF(x+y,z) , 其 含 义 为 x x y y  z(x+y=z),即:“任给自然数 x,任给自然y,存在自然数 z,使得 x+y=z”,因为任何两个自然的和是自然数,所以这句线 谓词公式的解释及线 : 设个体变元的值域D=N(自然数集),常 元 a=0, 函 数 f(x,y)=x+y , g(x,y)=x*y , 谓 词F(x,y):x=y。解 : 将个体常元 、 变 元 、 函数带入到原子公式中 。2.2 谓词公式及其解释解 将个体常元 变 元 函数带入到原子公式中) (4)  x x  y(F(f(x,a),y)  F(f(y,a),x))原式=xy(F(x,y)F(y,x)),其含义为: x x  y(x=y , y=x), 即: “任给一个自然数x,任给一个自然数y,如果x=y,那么y=x” ;这显然成立,故原式的 线 谓词公式的类型 与命题公式一样,谓词公式也有3种类型:永真式(逻辑有效式):在任何解释下均为真。永假式(矛盾式):在任何解释下均为假。可满足式:至少存在一种解释下为线 谓词公式及其解释说明 :(1)在命题逻辑中容易使用真值表判断命题公式的类型。(2)在一阶逻辑(即谓词逻辑)中,很难根据定义来验证一个公式的类型。(3 )“任何解释”如何穷尽?不可能。 但可以设法将命题公式类比迁移到谓词逻辑中;通过“代换实例”,即:“类比命题逻辑原则”进行判断。 《 离散数学 》2.2.4 谓词公式的类型2.2 谓词公式及其解释【定义2.2.13】(代换实例) :设A A是含有命题变元p 1 ,p 2 ,...,p n 的 命题公式 ,F 1 ,F 2 ,...,F n 是n个 谓词公式 ,将A中p p i i 的每次出现都换成F F i i ,所得公式称为A的 代换实例。如:命 题 公 式 : A : pq, 谓词公式:F(x),G(x),则F(x)G(x)可看成是命题公式pq的代换实例。同理,A(x)A(x)与xA(x)xA(x)都可看成是pp的代换实例 。 《 离散数学 》2.2.4 谓词公式的类型2.2 谓词公式及其解释例题: 判断公式F(x,y)(G(x,y)F(x,y))的类型。定理2.2.1:命题重言式的代换实例都是永真式,命题矛盾式的代换实例都是矛盾式。解: 将公式中的F(x,y)全部换为p, G(x,y)全部换为q,得命题公式p(qp),即:F(x,y)  (G(x,y)  F(x,y))是p p  (q  p)的代换实例。p(qp)p(qp)ppq1,即为重言式,故其代换实例F(x,y)(G(x,y)F(x,y))是永真式。 称p p  (q  p)为F(x,y)(G(x,y)F(x,y))的 原型 《 离散数学 》小结:1、合式谓词公式的定义2、量词的指导变元与量词的辖域3、个体变元的身份(约束变元、自由变元)4 谓词公式的解析及线、谓词公式的解析及线、谓词公式的三种类型(永真、永假、可满足)要求: 掌握利用代换实例进行公式类型判断的基本方法。 《 离散数学 》【定义2.3.1】设A、B是两个合法的谓词公式,如果在任何解释下两个公式的真值都相等,则称 A与B等值,记为A  B。2.3 谓词公式等值演算根据定义,当A A B B时,在任何解释下,公式A与公式B的真值都相同,故AB为永线】设A、B是两个合法的谓词公式,如果在任何解释下,AB为永真式,则称A与B等值,记为AA与B等值,记为A  B。 《 离散数学 》 谓词逻辑的推理公理:1、穷举法则:若个体域为有限集D={a 1 ,a 2 ,...,a n },则有xA(x)A(a 1 )A(a 2 ) A(a n )xA(x)A(a 1 )A(a 2 ) A(a n )2.3 谓词公式等值演算2.量词德摩律:xA(x)xA(x)(不是所有的个体有某特性=有些个体没有该特性)xA(x)xA(x)(不存在个体有某些特性=所有的个体都没有这个特性)注: 当否定符“”移过(从外部移到内部)时,变成,变成,变成,变成。 《 离散数学 》举例:1、 x(M(x)F(x))x(M(x)F(x))x(M(x)F(x)) 2 2 x(M(x)F(x))2.3 谓词公式等值演算2 2 、 x(M(x)F(x))x(M(x)F(x)) x(M(x)F(x))3、 xy(F(x)M(x)H(x,y))xy(F(x)M(x)H(x,y))(不再向下演算) 《 离散数学 》 谓词逻辑的推理公理:3、量词分配律x(A(x)B(x))xA(x)xB(x) (换为可否?不可)(所有的X同时具有特性A和B=所有的X具有特性A 并且所有的X具有特性B)x(A(x)B(x))xA(x)xB(x) (换为可否?不可)2.3 谓词公式等值演算(有的X具有特性A或者特性B=有的X具有特性A或者有的X具有特性B)4、量词作用域的收缩与扩张律若A(x)含有约束出现的变元x,B不含约束出现的x,则有:(1)x/x(A(x)B)x/xA(x)B(2)x/x(A(x)B)x/xA(x)B 《 离散数学 》 谓词逻辑的推理公理:5 、约束变元改名规则将公式A中某量词的指导变元及辖域中约束变元的每次约束出现,全部换成公式中未出现的字母,所得到的公式B等值于A 即AB2.3 谓词公式等值演算所得到的公式B等值于A,即AB。6 、置换规则公式的局部等值变换后,仍与原公式等值。 此外,命题逻辑中的等值式都可以通过代换实例转换为谓词逻辑的等值式。 《 离散数学 》例题2.3.1 试证明 x(A(x)B)xA(x)B 证明:x(A(x) B)x(A(x)B) pqpq的代换实例2.3 谓词公式等值演算xA(x)B 量词作用域的收缩与扩张律xA(x)B 德摩律xA(x)B pqpq的代换实例【证毕】 《 离散数学 》例题2.3.2 试证明x(M(x)F(x))x(M(x)F(x))证明:x(M(x)F(x))2.3 谓词公式等值演算x(M(x)F(x)) 德摩律x(M(x)F(x)) 德摩律x(M(x)F(x)) pqpq的代换实例【证毕】 《 离散数学 》例题2.3.4 试证明 xy(F(x)G(y)H(x,y)) xy(F(x)G(y)H(x,y)) 证明:x x y y(F(x)G(y)H(x,y))  (F( ) G( ) H( )) 德摩律2.3 谓词公式等值演算xy(F(x)G(y) H(x,y)) 德摩律xy ((F(x)G(y))H(x,y)) pqpqxy((F(x)G(y))H(x,y)) 德摩律xy((F(x)G(y))H(x,y)) ppxy(F(x)G(y)H(x,y)) 结合律【证毕】 《 离散数学 》小结:1、谓词公式等值的定义2、谓词逻辑常用的推理公理量词德摩律;2.3 谓词公式等值演算量词分配律;量词作用域的收缩与扩张律。要求: 掌握利用谓词逻辑推理公理与代换实例进行等值演算的方法。 《 离散数学 》【定义2.4.1】(前束范式)一个谓词公式,如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾,则该公式称为 前束范式。2.4 谓词公式的范式 前束范式形如Q 1 x 1 Q 2 x 2 Q k x k B B,其中Q i 为或,B B中不含量词。如: xy(F(x)G(y)H(x,y)) 是前束范式x(F(x)y(G(y)H(x,y)) 不是前束范式 《 离散数学 》【定理2.4.1】 任何逻辑公式可转换为前束范式。 将谓词公式转换为前束范式的步骤:(1)剔除不起作用的量词;(这种情况很少见)(2)若约束变元与自由变元 同名则 约束变元改名;2.4 谓词公式的范式(3)若 前后约束变元 同名,则 后者 改名;(4)利用代换实例,将、转换为表示;(5)将否定深入到原子公式的前面;(6)利用量词辖域的扩张与收缩规律或利用量词的分配律,将量词移到最左边。 《 离散数学 》例2.4.1:将公式xP(x)xQ(x)转换为前束范式。解:xP(x)x xQ(x x) (前后约束变元同名)xP(x) yQ(y) 后方约束变元改名2.4 谓词公式的范式 xP(x) yQ(y) 条件式的代换实例 x xP(x) y yQ(y) 德摩根律xy(P(x)Q(y)) 量词辖域的扩张 《 离散数学 》例2.4.2:将谓词公式xP(x,y)yQ(x,y)转换为前束范式解:xP(x,y)yQ(x,y) (变元同名)2.4 谓词公式的范式rP(r,y) sQ(x,s) 约束变元改名 rP(r,y) sQ(x,s) 转换条件式rP(r,y) sQ(x,s) 德摩律rs(P(r,y)Q(x,s)) 量词辖域的扩张 《 离散数学 》小结:1、前束范式的概念2、如何将谓词公式化为前束范式要求 : 掌握将谓词公式化为前束范式的一般2.4 谓词公式的范式要求 : 掌握将谓词公式化为前束范式的 般方法。 《 离散数学 》引言 : 学习逻辑的目的就是为了推理,学习谓词逻辑的目的也是为了推理,只是谓词逻辑推理要比命题逻辑推理更加复杂。谓词逻辑中不能使用真值表,只能使用自然推理2.5 谓词推理谓词逻辑中不能使用真值表,只能使用自然推理的方法,直接从前提出发,利用基本原则,逐渐推出结论。 《 离散数学 》【定义2.5.1】若在各种解释下A 1 A 2 A 3 A n B皆为真(即永线 ,,A n n 可推出结论B。可推出结论B。与命题逻辑一样,还有如下等价定义:2.5 谓词推理与命题逻辑 样,还有如下等价定义:【定义2.5.2】在所有A 1 A 2 A 3 A n 为真的解析下B为线 ,,A n n 可推出结论B。注: 由于无法穷尽所有解析,要验证“A 1 ,A 2,A 3, ,A n 为真时B为真”,只能采用等值演算。 《 离散数学 》 谓词推理常用的推理规则 :一、谓词逻辑的等值演算规则:如: 命题逻辑的代换实例、量词德摩律、量词分配律、量词辖域的扩张与收缩、约束变元改名等规则。二 、 命题逻辑 的推理 规则 ( 通过代换 实例 ) :2.5 谓词推理、 命题逻辑 的推理 规则 ( 通过代换 实例 ) :如: 假言推理、传递律、CP规则、反证法等。三、谓词逻辑的推理公理:1、xA(x)xB(x)x(A(x)B(x))2、x(A(x)B(x))xA(x)xB(x)(注意,这两条不是等值式, 方向不能反 ,区别于分配律)3、四条推理铁律(详见下页) 《 离散数学 》 谓词逻辑推理公理的四条推理铁律:1、全称量词的指定(US或-):xA(x)A(x 0 )其中:x 0 是论域中的 任意个体2、存在量词的指定(ES或-):xA(x)A(c)2.5 谓词推理其中:c为某个 特定个体 ,不是任意的个体3、全称量词的推广(UG或+):A(x 0 ) xA(x)其中:x 0 是论域中的 任意个体4、存在量词的推广(EG或+):A(c)  xA(x) 其中:c为 某个体 《 离散数学 》例题1 2.5.1 试 证 明( (  x(H(x)  O(x))  H(c)  O(c) 注: 谓词逻辑推理中,常用“全称指定、存在指定去掉量词全称指定、存在指定去掉量词”,然后“通过代换实例引用命题逻辑中的推理方法”,最后使用“全称推广、存在推广再加上量词全称推广、存在推广再加上量词”。2.5 谓词推理例题 试 明(亚里斯多德三段论)证明:(1) x(H(x)O(x))为线) H(c)O(c) 为真 (全称指定x=c时为线) H(c) 为线) O(c) 为线)与假言推理代换实例)【证毕】 《 离散数学 》2 例题2.5.2 证明  x(F(x)  G(x)),  xF(x)  xG(x)证明: ( 先用 “存在指定”!)(1) xF(x)为线) F(c)为真 (存在指定,存在c使F(c)为线) x(F(x)G(x))为线) x(F(x)G(x))为线) F(c)G(c)为真 (全称指定,尤其x=c时为线) G(c)为线) xG(x)为线)存在推广)注: 一定要注意 先用 “存在指定” , 再用“全称指定”“全称指定” 。否则会出现错误,如下: 《 离散数学 》2 例题2.5.2 证明  x(F(x)  G(x)),  xF(x)  xG(x)注意以下推理过程是错误的!(1) x(F(x)G(x))为线)为线) xF(x)为线) F(c)为真 (存在指定,至少存在c)(5) G(c)为线)假言推理代换实例)(6) xG(x)为线)存在推广)说明: 尽管在(2)中x0可以任意指定,但一旦指定就不能再变。(2)中指定的x0未必等于(4)中存在的c,所以F(c)为线)未必为线)推出G(c)为线 明 证明   x(F(x)  G(x)),  x(F(x)  H(x)) x(G(x)  H(x))证明:(1) x x(F(x)H(x))为线) F(c)H(c)为线) F(c)为线) F(c)为线) H(c)为线)  x x(F(x)G(x))为线) F(c)G(c)为真 (全称指定,尤其x=c时为线) G(c)为线) G(c)H(c)为线) x(G(x)H(x))为线)存在推广)【证毕】 《 离散数学 》【应用举例】 用谓词逻辑进行如下推理: 任何人违反交通规则,则要受到罚款,因此,如果没有罚款,则没有人违反交通规则。解: (整个句子中出现两个谓词:违反、受到)令:S(x,y)表示“x违反了y”2.5 谓词推理R(x,z)表示“x受到了z”设:x的个体域是“全体人类”y的个体域是“全部交通规则”z的个体域是“各种罚款”则以上语句表示为:x(yS(x,y)zR(x,z))xzR(x,z)xyS(x,y) 《 离散数学 》  x(  yS(x,y)  zR(x,z)) x x  zR(x,z) x x  yS(x,y)解:(采用附加前提法-CP规则)(1)  xzR(x,z)为线) xzR(x,z)为线)  x x(yS(x,y)zR(x,z))为线 )为线,y) zR(x0,z)为线,z)  yS(x0,y)为线,z) yS(x0,y)为线,z)为线,y)为线) xyS(x,y)为线) xyS(x,y)为线)的德摩律) 《 离散数学 》小结: 谓词推理常用的推理规则 :一、谓词逻辑的等值演算规则二、命题逻辑的推理规则(通过代换实例)三 谓词逻辑的推理公理2.5 谓词推理三、谓词逻辑的推理公理1、xA(x)xB(x)x(A(x)B(x))2、x(A(x)B(x))xA(x)xB(x)3、四条推理铁律要求: 掌握谓词逻辑推理的一般方法。 《 离散数学 》二 章 第 二章 章 谓词逻辑要求掌握的内容 1、准确掌握谓词逻辑的基本概念; 2、会将命题符号化; 3、熟练掌握谓词公式的等值演算; 4、会写谓词公式前束范式; 5、熟练掌握谓词逻辑的推理方法。