离散数学 郝晓燕 第2章谓词逻辑

《离散数学 郝晓燕 第2章谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章谓词逻辑谓词逻辑主要研究如何把数学中一些命题表示为逻辑公式，判明哪些公式是恒真式，哪些公式相互逻辑等价，还研究如何把一般的公式逻辑等价地化为标准形式。谓词逻辑的另一个重要内容是推理，即从一些公式出发有效推导出另一些公式。§2-1-1命题逻辑的局限性所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。根据常识，认为这个推理是正确的。但是，若用Ls来表示，设P、Q和R分别表示这三个原子命题，则有P，QR有些正确论证用命题逻辑不能证明其正确性。用命题逻辑符号化出的命题公式不能反映一些命题包含的共性。原因在于

2、命题逻辑是把简单命题做为最小单位（原子命题）。谓词逻辑通过分析简单命题的内容引进谓词与量词，弥补了命题逻辑的局限。§2-1-2谓词逻辑三要素（1）个体词在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为个体词。个体词可以是具体的或特定的事物，如小张、杭州、实数2等。表示具体的或特定的个体词称为个体常元，一般用带或不带下标的小写英文字母a，b，c，…，a1，b1，c1，…等表示；个体词还可以是抽象的或泛指的事物，如房子、大米、学生、思想等，表示抽象的或泛指的个体词称为个体变元，一般用带或不带下标的小写英

3、文字母x，y，z，…，x1，y1，z1，…等表示。个体变元的取值范围称为个体域或论域有限个体域，如{a，b，c}，{1，2}等无限个体域，如整数集合Z，实数集合R等全总个体域——由宇宙间一切事物组成的论域。（2）谓词谓词是用来刻划个体词的性质或事物之间的关系的词。表示特定谓词，称为谓词常元，表示不确定的谓词，称为谓词变元，都用大写英文字母，如P，Q，R，…，或其带上、下标来表示。对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆括号（）内。例如，在命题“张明

4、是个大学生”中，“张明”是个体，“是个大学生”是谓词，它刻划了“张明”的性质。设S：是大学生，c：张明，则“张明是个大学生”可表示为S(c)又如命题“武汉位于北京和广州之间”，武汉、北京和广州是3个个体，而“……位于……和……之间”是谓词，它刻划了武汉、北京和广州之间的关系。设P：……位于……和……之间，a：武汉，b：北京，c：广州，则P(a，b，c)：武汉位于北京和广州之间。定义2-1.1一个原子命题用一个谓词（如P）和n个有次序的个体常元（如a1，a2，…，an）表示成P(a1，a2，…，an)，称它为该原子

5、命题的谓词形式或命题的谓词形式。应注意的是，命题的谓词形式中的个体出现的次序影响命题的真值，不可随意变动，否则真值会有变化。定义2-1.2由一个谓词（如P）和n个体变元（如x1，x2，…，xn）组成的P(x1，x2，…，xn)，称为n元原子谓词或n元命题函数，简称n元谓词。当n=1时，称为一元谓词；当n=2时，称为二元谓词，…。特别地，当n=0时，称为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一。n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。但个体变元在哪些论域取特定的

6、值，对命题的真值是有影响的。例2-1.1令S(x)：x是大学生。若x的论域为某大学的计算机系中的全体同学，则S(x)是真的；若x的论域是某中学的全体学生，则S(x)是假的；若x的论域是某剧场中的观众，且观众中有大学生也有非大学生的其他观众，则S(x)是真值是不确定的。通常，把一个n元谓词中的每个个体的论域综合在一起作为它的论域，称为n元谓词的全总论域。当一个命题没有指明论域时，一般都以全总个体域作为其论域。例2-1.2令S(x)：x是聪明的。若以全总个体域来讨论是否聪明这样的属性，和人类的日常思维形式未免相违，因

7、此为深入研究命题方便，通常采用一个谓词如P(x)来限制个体变元x的取值范围，并把P(x)称为特性谓词。例如，令P(x)：x是大学生。在P(x)约束的范围中讨论是否聪明是符合日常思维的。（3）量词利用n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题，例如令S(x)：x是大学生，而x的个体域为某单位的职工，那么S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生。为了避免理解上的歧义，在谓词逻辑中，需要引入用以刻划“所有的”、“存在一些”等用来表示个体常项或变项之间数量关系的词，即量词

8、。量词分为以下两种。①符号称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、“一切”、“凡是”、“任意”等词语；x称为全称量词，x为指导变元，表示个体域内所有的x。②符号称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一些”、“某个”、“有的”、“存在”等词语；x称为存在量词，x称为指导变元，表示个体域内有的x。注意：为了表达数学命题的