《离散数学》第2章 谓词逻辑.ppt

《《离散数学》第2章 谓词逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、个体词之间关系的词。个体词个体常项用个体变项用表示表示谓词谓词常项谓词变项都用表示：小王，：小明，：小王比小明高。元谓词(用表示)如高。比：其中为个体词。是二元谓词，例如：李华是大学生，小明是大学生。一元谓词个体常项个体常项：李华：小明分别表示李华，小明是大学生，它们是0元谓词。：是大学生，2、量词——表示数量的词。全称量词量词存在量词使用量词时，应注意以下6点：(1)在不同个体域中，命题符号化的形式可能不一样，(2)一般，除非有特别说明，均以全总个体域为个体域，(3)在引入特性谓词后，使用全称量词用“使用存在量词用“”，”，(4)个量词，元谓词化为命题至少需

3、要如(5)当个体域为有限集时，，则(6)多个量词同时出现时，不能随意颠倒顺序。三、命题符号化。例1、在一阶逻辑中将下面命题符号化。(1)所有的有理数均可表成分数。解：因无指定个体域，则以全总个体域为个体域。：为有理数，：可表成分数，(2)有的有理数是整数。解：：为有理数，：为整数，注：若本题指定的个体域为有理数集，则(1)，(2)分别符号化为和。例2、在一阶逻辑中将下列命题符号化。(1)凡偶数均能被2整除。(2)存在着偶素数。解：：是偶数，：能被2整除，：解：是偶数，：是素数，(3)没有不犯错误的人。原命题即：“每个人都犯错误”。又可符号化为：解：：是人，：犯

4、错误，(4)每列火车都比某些汽车快。某些汽车比所有的火车慢。第一句为：或解：：是火车，：是汽车，：快，比第二句为：或例3设个体域为实数集，令是整数．是有理数．．．试用日常语言叙述下列命题，并指出其真值．（1）（2）（3）（4）（2）存在着实数，使得对于任意实数，都有．该命题真值为0．（3）存在着实数和,使得且．该命题真值为1．（4）对于任意实数，存在着实数，使得且，解：（1）对于任意实数，存在着实数，使得．该命题真值为1．该命题真值为0．内容：合式公式，解释，逻辑有效式，矛盾式，可满足式。重点：(1)掌握合式公式的概念，(2)掌握量词的辖域，约束变项，自由变项

5、的概念，(3)掌握逻辑有效式，矛盾式，可满足式的概念。第二节一阶逻辑合式公式及解释一般：(1)换名规则，代替规则，(2)解释的概念，(3)代换实例。了解：(1)闭式的概念，(2)判断合式公式的类型。一、一阶逻辑中的合式公式。1、字母表。(1)个体常项：(2)个体变项：(3)函数符号：(4)谓词符号：(5)量词符号：(6)联结词符：(7)括号和逗号：(，)，，。2、元的递归定义。(1)个体常项和变项是元。(3)只有有限次地使用(1)、(2)生成的符号串才是元。例如：等都是元。(2)若是元，则元函数，是任意是元。3、原子公式。4、合式公式的递归定义。(1)原子公式

6、是合式公式；设是项，则称为原子公式。元谓词，是任意(3)若也是合式公式；是合式公式，则是合式公式，则也是合式公式；(2)若(5)只有有限次地应用(1)－(4)构成的符号串才是合式公式(也称谓词公式)，简称公式。(4)若也是合式公式；是合式公式，则5、约束出现，自由出现。在合式公式中，称为指导变项，称为相应量词的辖域，约束出现，自由出现例1、指出下列各合式公式中的指导变项，量词的辖域，个体变项的自由出现和约束出现。（1）（2）（3）闭式(封闭的合式公式)——无自由出现的个体变项的合式公式。换名规则——指导变项，约束变项换名例如：换成代替规则——自由变项代替例如：

7、换成二、合式公式的解释。对公式中各种变项(个体变项，函数变项，谓词变项)，指定特殊的常项去代替，就构成了公式的一个解释。(1)非空个体域；(2)中一部分特定元素；1、解释由以下4部分组成：(3)上一些特定的函数；(4)上一些特定的谓词；例2给定解释如下：中特定元素；(1);(2)函数为；(3)谓词为；(4)为为．；在解释下，求下列各式的真值．（1）；（2）；（3）；（4）．解：设（1）、（2）、（3）、（4）中公式分别为．在解释下，．2、逻辑有效式(永真式)，矛盾式(永假式)，可满足式。逻辑有效式——在任何解释下都取值为真的合式公式。矛盾式——在任何解释下都取

8、值为假的合式公式。可满足式——至少存在