北大离散数学chap2

第二章一阶逻辑第一节一阶逻辑基本概念内容：个体词，谓词，量词，命题符号化。重点：1、掌握个体词，谓词，量词的有关概念，2、掌握在一阶逻辑中的命题符号化。一、一阶逻辑(谓词逻辑)研究的内容。例如：判断以下推理是否正确：凡人都是要死的，苏格拉底是人，所以苏格拉底是要死的。这是著名的“苏格拉底三段论”，若用推理形式为,,pqr()pqr分别表示以上3个命题，，不是重言式。二、个体词，谓词，量词。1、个体词，谓词。例如：李华是大学生。是无理数。2小王比小明高。(1)个体词——简单命题中表示主体或客体的词(由名词组成)。个体域(或称论域)——个体变项取值的范围。(2)谓词——刻画个体词的性质或个体词之间关系的词。个体词个体常项用个体变项用,,abc,,xyz表示表示谓词谓词常项谓词变项都用,,FGH表示：小王，a：小明，b：小王比小明高。(,)Fab元谓词(用n12(,,,)nFxxx表示)如(,)Fxyxy高。比：其中(,)Fxy,xy为个体词。是二元谓词，例如：李华是大学生，小明是大学生。一元谓词个体常项个体常项：李华a：小明b(),()FaFb分别表示李华，小明是大学生，它们是0元谓词。：()Fxx是大学生，2、量词——表示数量的词。全称量词量词存在量词使用量词时，应注意以下6点：(1)在不同个体域中，命题符号化的形式可能不一样，(2)一般，除非有特别说明，均以全总个体域为个体域，2、量词——表示数量的词。量词存在量词使用量词时，应注意以下6点：全称量词(3)在引入特性谓词后，使用全称量词用“使用存在量词用“”，”，(4)nn个量词，元谓词化为命题至少需要2、量词——表示数量的词。全称量词量词存在量词使用量词时，应注意以下6点：如(5)当个体域为有限集时，12{,,}nDaaa12()()()()nxAxAaAaAa12()()()()nxAxAaAaAa，则2、量词——表示数量的词。全称量词量词存在量词使用量词时，应注意以下6点：(6)多个量词同时出现时，不能随意颠倒顺序。三、命题符号化。例1、在一阶逻辑中将下面命题符号化。(1)所有的有理数均可表成分数。解：因无指定个体域，则以全总个体域为个体域。()()xQxFx：()Qxx为有理数，：x()Fx可表成分数，三、命题符号化。例1、在一阶逻辑中将下面命题符号化。(2)有的有理数是整数。解：()()xQxZx：()Qxx为有理数，：x()Zx为整数，注：若本题指定的个体域为有理数集，则(1)，(2)分别符号化为和()xFx()xZx。例2、在一阶逻辑中将下列命题符号化。(1)凡偶数均能被2整除。()()xFxGx(2)存在着偶素数。()()xFxHx解：()Fx：x是偶数，：x()Gx能被2整除，：解：()Fxx是偶数，：()Hxx是素数，例2、在一阶逻辑中将下列命题符号化。(3)没有不犯错误的人。()()xMxFx原命题即：“每个人都犯错误”。又可符号化为：()()xMxFx解：()Mx：x是人，()Fx：x犯错误，例2、在一阶逻辑中将下列命题符号化。(4)在北京工作的人未必是北京人。()()xFxGx(5)尽管有些人聪明，但未必一切人都聪明。()()()()xMxFxxMxFx解：：()Fxx是在北京工作的人，：x()Gx是北京人，解：：()Mxx是人，()Fx：x聪明，例2、在一阶逻辑中将下列命题符号化。(6)每列火车都比某些汽车快。某些汽车比所有的火车慢。第一句为：()()(,)xFxyGyHxy或()()(,)xyFxGyHxy解：()Fx：x是火车，()Gy：y是汽车，(,)Hxy：xy快，比例2、在一阶逻辑中将下列命题符号化。(6)每列火车都比某些汽车快。某些汽车比所有的火车慢。第二句为：()()(,)yGyxFxHxy或()()(,)yxGyFxHxy解：()Fx：x是火车，()Gy：y是汽车，(,)Hxy：xy快，比第二节一阶逻辑合式公式及解释内容：合式公式，解释，逻辑有效式，矛盾式，可满足式。重点：(1)掌握合式公式的概念，(2)掌握量词的辖域，约束变项，自由变项的概念，(3)掌握逻辑有效式，矛盾式，可满足式的概念。一般：(1)换名规则，代替规则，(2)解释的概念，(3)代换实例。了解：(1)闭式的概念，(2)判断合式公式的类型。一、一阶逻辑中的合式公式。1、字母表。(1)个体常项：,,,.,,,,1iiiabcabci(2)个体变项：,,,.,,,,1iiixyzxyzi(3)函数符号：,,,.,,,,1iiifghfghi(4)谓词符号：,,,.,,,,1iiiFGHFGHi一、一阶逻辑中的合式公式。1、字母表。(5)量词符号：,(6)联结词符：,,,,(7)括号和逗号：(，)，，。2、项的递归定义。(1)个体常项和变项是项。(3)只有有限次地使用(1)、(2)生成的符号串才是项。例如：,,,,(,),(,)21,abxyfxyxygxyxy(,),,(,)(21)hxyxyfagxyaxy等都是项。(2)若12(,,)nxxxn12,,,nttt是项，则12(,,,)nttt元函数，是任意是项。3、原子公式。4、合式公式的递归定义。(1)原子公式是合式公式；设12(,,)nRxxxn12,,,nttt是项，则称12(,,,)nRttt为原子公式。元谓词，是任意(3)若,AB(),(),ABAB(),()ABAB也是合式公式；是合式公式，则是合式公式，则A()A也是合式公式；(2)若3、原子公式。4、合式公式的递归定义。(5)只有有限次地应用(1)－(4)构成的符号串才是合式公式(也称谓词公式)，简称公式。设12(,,)nRxxxn12,,,nttt是项，则称12(,,,)nRttt为原子公式。元谓词，是任意(4)若A,xAxA也是合式公式；是合式公式，则5、约束出现，自由出现。约束出现，自由出现在合式公式,xAxA中，称x为指导变项，称A为相应量词的辖域，例1、指出下列各合式公式中的指导变项，量词的辖域，个体变项的自由出现和约束出现。(1)()(,)xFxyHxy(2)()(,)xFxGxy(3)(,)(,)(,)xyRxyLyzxHxy闭式(封闭的合式公式)——无自由出现的个体变项的合式公式。换名规则——指导变项，约束变项换名例如：()(,)xFxyHxy换成()(,)zFzyHzy代替规则——自由变项代替例如：(,)(,)(,)xyRxyLyzxHxy换成(,)(,)(,)xyRxyLyztHtw二、合式公式的解释。对公式中各种变项(个体变项，函数变项，谓词变项)，指定特殊的常项去代替，就构成了公式的一个解释。(1)非空个体域D；(2)D中一部分特定元素；1、解释I由以下4部分组成：二、合式公式的解释。对公式中各种变项(个体变项，函数变项，谓词变项)，指定特殊的常项去代替，就构成了公式的一个解释。1、解释I由以下4部分组成：(3)D上一些特定的函数；(4)D上一些特定的谓词；1)个体域为自然数集合ND(1)(,),xFgxax(0)xxx真值为0例2、给定解释N如下：2)ND0a中特定元素3)ND(,),(,)fxyxygxyxy上特定函数4)ND(,)Fxyxy为上特定谓词下，下面哪些公式为真？哪些公式为假？N在解释解：在解释N下，公式化为：真值为1(2)(,),(,),xyFfxayFfyax(00)xyxyyx1)个体域为自然数集合ND例2、给定解释N如下：3)ND(,),(,)fxyxygxyxy上特定函数4)ND(,)Fxyxy为上特定谓词下，下面哪些公式为真？哪些公式为假？N在解释解：在解释N下，公式化为：2)ND0a中特定元素真值为1(3)(,),xyzFfxyz()xyzxyz解：在解释N下，公式化为：1)个体域为自然数集合ND例2、给定解释N如下：3)ND(,),(,)fxyxygxyxy上特定函数4)ND(,)Fxyxy为上特定谓词下，下面哪些公式为真？哪些公式为假？N在解释2)ND0a中特定元素真值为0(4)(,),(,)xyFfxygxy()xyxyxy2)ND0a中特定元素1)个体域为自然数集合ND3)ND(,),(,)fxyxygxyxy上特定函数例2、给定解释N如下：4)ND(,)Fxyxy为上特定谓词在解释N下，下面哪些公式为真？哪些公式为假？解：在解释N下，公式化为：真值为不确定(不是命题)(5)(,),(,)Ffxyfyzxyyz2)ND0a中特定元素1)个体域为自然数集合ND3)ND(,),(,)fxyxygxyxy上特定函数例2、给定解释N如下：4)ND(,)Fxyxy为上特定谓词在解释N下，下面哪些公式为真？哪些公式为假？解：在解释N下，公式化为：2、逻辑有效式(永真式)，矛盾式(永假式)，可满足式。逻辑有效式——在任何解释下都取值为真的合式公式。矛盾式——在任何解释下都取值为假的合式公式。可满足式——至少存在一种解释使其取值为真的合式公式。有一些公式，可以利用命题公式的结论。代换实例——个命题变项0A12,,npppn将n12,,nAAA12,,nppp词公式称为0A设是含的命题公式，所得的谓取代个谓词的代换实例。例如：()(),()(),FxGxxFxGx()()xFxxGx等都是的代换实例。pq命题公式中重言式，矛盾式的代换实例在谓词公式中仍是重言式(逻辑有效式)，矛盾式。例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。(1)()()xFxxFx解：设ID。是任意的解释，设其个体域为若存在0xD0()Fx()xFx为假，为假，则，从而()()xFxxFx为真；由以上，原公式是逻辑有效的。例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。(1)()()xFxxFx解：设ID。是任意的解释，设其个体域为若对任意xD()Fx为真，，都有则(),()xFxxFx均为真，所以()()xFxxFx为真。例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。(2)()(,)()xFxxyGxyxFx()()1pqppqp(重言式)，而且所以原公式是逻辑有效的。解：原公式是命题公式()pqp的代换实例，例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。所以原公式是逻辑有效的。(3)()()()xFxxFxyGy(重言式)，而且()()1ppqppq解：原公式是命题公式()ppq的代换实例，例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。(4)(,)(,)(,)FxyRxyRxy而且()()pqqpqq(矛盾式)，0pqq所以原公式是矛盾式。解：原公式是命题公式()pqq的代换实例，第三节一阶逻辑等值式内容：一阶逻辑等值式，前束范式。重点：掌握基本等值式，(量词否定等值式，量词辖域收缩与扩张等值式，量词分配等值式)的内容。一般：使用基本等值式进行等值演算。了解：前束范式的定义和求法。一、一阶逻辑等值式。已有的等值式命题公式中的24个等值式及代换实例由换名规则及代替规则所得公式与原公式等值定义：若ABAB为逻辑有效式，记1、量词否定等值式。(1)()()xAxxAx(2)()()xAxxAx2、量词辖域收缩与扩张等值式。(1)()()xAxBxAxB(2)()()xAxBxAxB(4)()()xBAxBx