第二章 谓词逻辑.ppt

《第二章 谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《第二章 谓词逻辑.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、PPT模板下载：/moban/ 行业PPT模板：/hangye/ 节日PPT模板：/jieri/ PPT素材下载：/sucai/PPT背景图片：/beijing/ PPT图表下载：/tubiao/ 优秀PPT下载：/xiazai/ PPT教程： /powerpoint/ Word教程： /word/ Excel教程：/excel/ 资料下载：/ziliao/ PPT课件下载：/kejian/ 范文下载：/fanwen/ 试卷下载：/shiti/ 教案下载：/jiaoan/ 字体下载：/ziti/ 第二章 谓词逻辑第二章第二章 谓词逻辑谓词逻辑 第一节第一节 谓词谓词逻辑基本概念逻辑基本概念 内

2、容：内容： 个体词，谓词，量词，命题符号化。 重点：重点： 1、掌握个体词，谓词，量词的有关概念， 2、掌握在一阶逻辑中的命题符号化。 一、谓词逻辑研究的内容。一、谓词逻辑研究的内容。例如：判断以下推理是否正确： 凡人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。 这是著名的“苏格拉底三段论”， 若用推理形式为, ,p q r()pqr分别表示以上3个命题，不是重言式。二、个体词，谓词，量词。二、个体词，谓词，量词。 1、个体词，谓词 。例如：陈景润是数学家。 是无理数。 2小王比小李高2厘米 。 (1) 个体词个体词简单命题中表示主体或客体的词(由名词组成)。个体域个体域(或称论域论域

3、)个体变项取值的范围。 (2) 谓词谓词刻画个体词的性质或个体词之间关系的词。个体词个体常项用个体变项用, ,a b c, ,x y z表示表示谓词谓词常项谓词变项都用,F G H表示：小王， a：小明， b：小王比小明高。 ( , )F a b元谓词元谓词(用n12( ,)nF x xx表示)如( , )F x yxy高。比：其中( , )F x y, x y为个体词。是二元谓词，例如：李华是大学生， 小明是大学生。 一元谓词 个体常项 个体常项 ：李华 a：小明 b( ),( )F a F b分别表示李华，小明是大学生， 它们是0元谓词。 ：( )F xx是大学生， 2、量词量词表示数量的

4、词。 全称量词量词存在量词使用量词时，应注意以下6点： (1) 在不同个体域中，命题符号化的形式可能不一样， (2) 一般，除非有特别说明，均以全总个体域为个体域，(3) 在引入特性谓词后，使用全称量词用“使用存在量词用“”，”，(4)nn个量词，元谓词化为命题至少需要如(5) 当个体域为有限集时，12 ,nDa aa12( )()()()nxA xA aA aA a12( )()()()nxA xA aA aA a，则(6) 多个量词同时出现时， 不能随意颠倒顺序。 三、命题符号化。三、命题符号化。 例例1、在一阶逻辑中将下面命题符号化。 (1) 所有的有理数均可表成分数。 解：解：因无指定

5、个体域，则以全总个体域为个体域。( )( )x Q xF x：( )Q xx为有理数，：x( )F x可表成分数， (2) 有的有理数是整数。 解：解：( )( )x Q xZ x：( )Q xx为有理数，：x( )Z x为整数，注：注：若本题指定的个体域为有理数集， 则(1)，(2)分别符号化为和( )xF x( )xZ x。例例2、在一阶逻辑中将下列命题符号化。 (1) 凡偶数均能被2整除。 ( )( )x F xG x(2) 存在着偶素数。 ( )( )x F xH x解：解： ( )F x：x是偶数，：x( )G x能被2整除，：解：解： ( )F xx是偶数，：( )H xx是素数，

6、(3) 没有不犯错误的人。 ( )( )x M xF x原命题即：“每个人都犯错误”。 又可符号化为： ( )( )x M xF x解：解： ( )M x：x是人，( )F x：x犯错误，(4) 每列火车都比某些汽车快。 某些汽车比所有的火车慢。 第一句为： ( )( )( , )x F xy G yH x y 或 ( )( )( , )x y F xG yH x y 解：解： ( )F x：x是火车，( )G y：y是汽车， ( , )H x y：xy快，比第二句为： ( )( )( , )y G yx F xH x y或 ( )( )( , )y x G yF xH x y 例例3 设个体

7、域为实数集，令 是整数 是有理数 试用日常语言叙述下列命题，并指出其真值xxI:)(xxQ:)(1: ),( yxyxA0:),( yxyxB（1）（2）（3）（4） ),(yxyAx),(yxxAy),(),(yxByxAyx),(),(yxByxAyx（2）存在着实数 ，使得对于任意实数 ，都有 该命题真值为0（3）存在着实数 和 ,使得 且 该命题真值为1 （4）对于任意实数 ，存在着实数 ，使得 且 ，解：解：（1）对于任意实数 ，存在着实数 ，使得 该命题真值为1 xy1 yxyx1 yxxy1 yx0 yxxy1 yx0 yx该命题真值为0 内容：内容： 合式公式，解释，逻辑有效式

8、，矛盾式，可满足式。重点：重点： (1) 掌握合式公式的概念， (2) 掌握量词的辖域，约束变项，自由变项的概念，(3) 掌握逻辑有效式，矛盾式，可满足式的概念。第二节第二节 一阶逻辑合式公式及解释一阶逻辑合式公式及解释 一般：一般： (1) 换名规则，代替规则， (2) 解释的概念， (3) 代换实例。 了解：了解： (1) 闭式的概念， (2) 判断合式公式的类型。 一、一阶逻辑中的合式公式。一、一阶逻辑中的合式公式。 1、字母表。 (1) 个体常项：个体常项： , , ,. , , ,1iiia b ca b ci (2) 个体变项：个体变项： , , ,. ,1iiix y zx y

9、zi (3) 函数符号：函数符号： , , ,. ,1iiif g hf g hi (4) 谓词符号：谓词符号： ,. ,1iiiF G HF G Hi (5) 量词符号：量词符号： , (6) 联结词符：联结词符： , , , (7) 括号和逗号：括号和逗号：( ，)， ， 。 2、元的递归定义。 (1) 个体常项和变项是元。 (3) 只有有限次地使用(1)、(2)生成的符号串才是元元。 例如： , , , ,( , ), ( , )21,a b x y f x yxy g x yxy( , ), ( , )(21)h x yx y f a g x yaxy等都是元。 (2)若12( ,)n

10、x xxn12, ,nt tt是元，则12( , , )nt tt元函数，是任意是元。3、原子公式。 4、合式公式的递归定义。 (1) 原子公式是合式公式； 设12( ,)nR x xxn12, ,nt tt是项，则称12( , , )nR t tt为原子公式原子公式。元谓词，是任意(3)若,A B(),(),ABAB(),()ABAB也是合式公式； 是合式公式，则是合式公式，则A()A也是合式公式；(2) 若(5) 只有有限次地应用(1)(4)构成的符号串 才是合式公式合式公式(也称谓词公式谓词公式)，简称公式公式。 (4) 若A,xAxA也是合式公式；是合式公式，则5、约束出现，自由出现。

11、 在合式公式,xAxA中，称x为指导变项指导变项，称A为相应量词的辖域辖域， 约束出现，自由出现约束出现，自由出现 例例1、指出下列各合式公式中的指导变项，量词的辖域，个体变项的自由出现和约束出现。 ( , )( , )( , )x y R x yL y zxH x y ),()(zyyQxPx)(),(),()(xSyxRyyxQxPx（1）（2）（3）闭式闭式(封闭的合式公式封闭的合式公式) 无自由出现的个体变项的合式公式。 换名规则换名规则指导变项，约束变项换名 例如： ( )( , )x F xyH x y换成 ( )( , )z F zyH z y代替规则代替规则自由变项代替 例如：

12、 ( , )( , )( , )x y R x yL y zxH x y 换成 ( , )( , )( , )x y R x yL y ztH t w 二、合式公式的解释。二、合式公式的解释。 对公式中各种变项(个体变项，函数变项， 谓词变项)，指定特殊的常项去代替，就构成了公式的一个解释。 (1) 非空个体域D；(2)D中一部分特定元素；1、解释I由以下4部分组成：(3)D上一些特定的函数；(4)D上一些特定的谓词；例2 给定解释 如下：I3 , 2D 中特定元素 ； D2a(1) ;(2)函数 为 ；)(xf2)3(, 3)2(ff(3) 谓词 为 ；)(xF1)3(, 0)2(FF(4)

13、,(yxG3 , 2, , 1), (jijiG为),(yxL)2 , 2(L1)3 , 3(L为 )3 , 2(L0)2 , 3(L；在解释 下，求下列各式的真值I（1） ；（2） ；（3） ；（4） ),()(axGxFx)(,()(xfxGxfFx),(yxyLx),( yxyLx解：解： 设（1）、（2）、（3）、（4）中公式分别为 在解释 下，DCBA,I)2 , 3 () 3 ()2 , 2() 2(GFGFA) 11 () 10 (0)2 (, 2 ()2 (fGfFB)3 (, 3 ()3 (fGfF)3 , 2() 3 (GF)2 , 3()2(GF1) 10() 11 ()

14、3 , 3()2 , 3()3 , 2()2 , 2(LLLLC0) 10()01 ( D)3 , 3 () 2 , 3 ()3 , 2 () 2 , 2 (LLLL1112、逻辑有效式(永真式)，矛盾式(永假式)，可满足式。 逻辑有效式逻辑有效式 在任何解释下都取值为真的合式公式。 矛盾式矛盾式 在任何解释下都取值为假的合式公式。 可满足式可满足式 至少存在一种解释使其取值为真的合式公式。 有一些公式，可以利用命题公式的结论。 代换实例代换实例 个命题变项0A12,np ppn将n12,nA AA12,np pp词公式称为0A设是含的命题公式，所得的谓取代个谓词的代换实例代换实例。 例如：

15、( )( ),( )( ),F xG xxF xG x( )( )xF xxG x 等都是的代换实例。 pq命题公式中重言式，矛盾式的代换实例在谓词公式中仍是重言式(逻辑有效式)，矛盾式。 例例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。 (1) ( )( )xF xxF x 解：解： 设ID。是任意的解释，设其个体域为若存在0 xD0()F x( )xF x为假，为假，则，从而( )( )xF xxF x 为真；(2) ( )( , )( )xF xx yG x yxF x 解：解： 原公式是命题公式()pqp的代换实例，()()1pqppqp (重言式) ， 而且所以原公式是逻辑有效

16、的。 (3) ( )( )( )xF xxF xyG y 解：解： 原公式是命题公式()ppq的代换实例，(重言式) ， 而且()()1ppqppq 所以原公式是逻辑有效的。 (4) ( , )( , )( , )F x yR x yR x y而且()()pqqpqq (矛盾式) ， 0pqq 所以原公式是矛盾式。 解：解： 原公式是命题公式()pqq的代换实例， 内容：内容： 一阶逻辑等值式，前束范式。 重点：重点： 掌握基本等值式， (量词否定等值式，量词辖域收缩与扩张等值式，量词分配等值式)的内容。 一般：一般： 使用基本等值式进行等值演算。 了解：了解： 前束范式的定义和求法。 第三节

17、第三节 谓词逻辑等值式谓词逻辑等值式一、一阶逻辑等值式。一、一阶逻辑等值式。 已有的等值式命题公式中的24个等值式及代换实例由换名规则及代替规则所得公式与原公式等值定义：定义： 若ABAB为逻辑有效式，记定理定理21 量词否定等值式。 (1) ( )( )xA xx A x (2) ( )( )xA xx A x 定理定理22 量词分配等值式。 (1) ( )( )( )( )x A xB xxA xxB x (2) ( )( )( )( )x A xB xxA xxB x 定理定理23 量词辖域收缩与扩张等值式。 (1) ( )( )x A xBxA xB (2) ( )( )x A xBx

18、A xB (4) ( )( )x BA xBxA x (3) ( )( )x A xBxA xB (5) ( )( )x A xBxA xB (6) ( )( )x A xBxA xB (7) ( )( )x A xBxA xB (8) ( )( )x BA xBxA x 定理定理24 多个量词间的次序排列等值式。 (1) ( , )( , )x yA x yy xA x y (2) ( , )( , )x yA x yy xA x y 二、前束范式。二、前束范式。 前束范式：前束范式：形式 1 122kkQ x Q xQ x B例如： ( )( , )x y F xG x y ( )( ,

19、)F xG x y，( , , )( )x y z F x y zG y 等都是前束范式， 而 ( )( , )x F xyG x y ( )( , )x F xyG x y等都不是前束范式。 任一合式公式都可表示为前束范式，其化归步骤如下：（1）消去公式中出现的多余量词；（2）将合式公式中出现的联结词都化为（3）利用双重否定律，德摩根律及量词否定等值式将合式公式中的否定字符深入到谓词字母前；（4）利用代替规则和换名规则，使所有约束变元均不相同，并且使自由变元与约束变元不同（5）利用量词辖域收缩与扩张等值式，扩大量词的辖域至整个公式,例例2、求下列公式的前束范式。 解：解： )()(xxGxx

20、F(1)()(xxGxxF（定理21 （2）)()(xGxxxF（换名规则）)()(yGyxxF（定理23 （1）)()(yGyxFx（定理23 （1）)()(yGxFyx),()(),(yxxHyyGyxxF(2)解：解： ),()(),(yxxHyyGyxxF（代替规则）),()(),(zxxHyyGzxxF（换名规则）), ()(),(zttHyyGzxxF（定理23 （2）),()(),(zttHyyGzxFx（定理23 （2）),()(),(zttHyGzxFyx（定理23 （1）),()(),(zttHyGzxFyx（定理23 （1）),()(),(ztHyGzxFtyx内容：内容

21、： 谓词谓词逻辑推理理论。 了解：了解： 推理规则在推理中的正确使用。 重点：重点： 掌握谓词谓词逻辑推理的概念。 一般：一般： 全称量词消去规则()UI，全称量词引入规则()UG，存在量词引入规则()EG，存在量词消去规则()EI。第四节第四节 谓词逻辑中的推理谓词逻辑中的推理一、一、谓词谓词逻辑推理的概念。逻辑推理的概念。 1、概念。 已有的推理定律命题公式中的重言蕴涵式及代换实例一阶逻辑中的等值式(每个等值式可产生两条推理定律)若12kAAAB则称推理正确，记为 12kAAAB为逻辑有效式，2、量词分配定律。 (1) ( )( )( )( )xA xxB xx A xB x (2) (

22、)( )( )( )x A xB xxA xxB x (3) ( )( )( )( )x A xB xxA xxB x (4) ( )( )( )( )x A xB xxA xxB x 二、推理规则。二、推理规则。 1、全称量词消去规则 ()UI( )( )xA xA y( )( )xA xA c要求： (1)x( )A x中自由出现的个体变项，是 (2)y( )A x中约束出现的个体变项， 为任意的不在(3)c为任意的个体常项。2、全称量词引入规则 ()UG( )( )A yxA x 要求： (1)y( )A yyA中自由出现，且在均为真，(2) 取代yx( )A y中约束出现。不能在的取任

23、何值时3、存在量词消去规则 ()EI( )( )xA xA c要求： (1)cA为真的特定的个体常项， 是使(2)c( )A x中出现过，不曾在(3)( )A xx个体变项时，不能用此规则。 外还有其他自由出现的 中除4、存在量词引入规则 ()EG( )( )A cxA x 要求： (1)c是特定的个体常项，(2) 取代cx( )A c中出现过。 不能已在的：苏格拉底。 a解：解：设：( )F xx是人，( )G x：x是要死的，前提： ( )( ) ,( )x F xG xF a结论： ( )G a例1 证明苏格拉底三段论“凡人都是要死的苏格拉底是人所以苏格拉底是要死的”证明：证明： ( )

24、( )x F xG x前提引入 ( )( )F aG a UI ( )F a前提引入 ( )G a假言推理 例2 指出下面推理的错误 前提引入 UI EI UG EG),(yxyFx),(yzyF),(czF),(cxxF),(yxxFy解：解： 因 中存在自由出现的个体变项， 因而不能使用EI规则，所以错误),(yzyFz例3 构造下面推理的证明前提：结论：)()(),()(xBxCxxBxAx)()(xAxCx证明： 前提引入 前提引入 UI UI 假言易位 假言三段论 假言易位 UG)()(xBxAx)()(xBxCx)()(cBcA)()(cBcC)()(cCcB)()(cCcA)()

25、(cAcC)()(xAxCx一、谓词逻辑的基本概念。一、谓词逻辑的基本概念。 1、基本概念。 个体，个体域，个体词，个体常项和变项； 谓词；量词，全称量词和存在量词。 2、应用。 在谓词谓词逻辑中将命题符号化。 第二章第二章 小结与例题小结与例题 二、谓词逻辑合式公式及解释。二、谓词逻辑合式公式及解释。 1、基本概念。 合式公式；辖域，约束变项，自由变项； 闭式；解释；代换实例；逻辑有效式， 矛盾式，可满足式。 2、应用。 (1) 求某些公式在给定解释下的真值。 (2) 判断某些简单公式的类型。 三、谓词逻辑等值式。三、谓词逻辑等值式。 基本概念。 等值式，常用等值式；前束范式。 四、谓词逻辑

26、推理理论。四、谓词逻辑推理理论。 1、基本概念。 推理；全称量词消去规则()UI全称量词引入规则存在量词引入规则()UG()EI()EG，存在量词消去规则。，2、应用。 用构造法证明某些简单的推理。 例例1、在一阶逻辑中将下列命题符号化。 (1)至少有一个实数不是自然数 (2) 任何金属均可溶解于某种液体中。 ：解：解：( )P xx( )G xx：( , )R x yxy是液体，：是金属，符号化为溶解( )( )( , )x G xy p yR y x 设 是实数， 是自然数，符号化为 xxR:)(xxN:)()()(xNxRx解：例例2、将下列命题译成自然语言，并确定其真值。 (个体域为

27、) Z真值0。 真值0。 (1)( , )x yG x y ( , ):G x yxyy，其中解：解：对任意正整数xy使得xyy，存在正整数。(2)( , )x yF x y ( , ):F x yxyy，其中解：解：存在正整数xy满足xyy，使得对任意的正整数。真值0。 真值1。 (3)( , )x yM x y ( , ):1M x yxy ，其中解：解：对任意正整数xy使得1xy ，存在正整数。(4)( , )x yN x y ( , ):2N x yyx，其中解：解：对任意正整数xy使得2yx，存在正整数。设解释I为：个体域为 ，谓词 6 , 3 , 2D7:)(,5:)(,3:)(x

28、xRxxGxxF例3根据解释I，求下列各式的真值：（1） ；（2） ；（3） )()(xGxFx)5()()(GxFxRx)()(xGxFx解：)()(xGxFx)6 () 6 ()3 () 3 ()2() 2(GFGFGF0) 10 () 01 () 01 (（1）)5()()(GxFxRx0)6()6()3()3()2()2(FRFRFR0)01()11()11(（2）（3）)()(xGxFx)()(xxGxxF)6 () 3 () 2()6 () 3 () 2(GGGFFF1) 100()011 (例4 航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明这个人一定不是航海家证明：证明：设个体域是人的集合谓词 是航海家；教育他的孩子成为航海家xxS: )(xxE: )(前提：结论：)(),()(xExxExSx)()(xSxEx证明： 前提引入 EI 前提引入 UI 拒取式 合取)(xEx )(cE)()(xExSx)()(cEcS)(cS)(cE)(cS EG)(xEx )(xS