离散数学谓词逻辑.ppt

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

1、第二章谓词逻辑数理逻辑命题逻辑：从语句来讲是不可再分谓词逻辑：将命题再细分在命题逻辑中，命题演算的基本单位是命题，不再对原子命题进行分解，故无法研究命题语句的结构、成份和内在的逻辑特征。如果任何两个原子命题具有一些共同特征，那么欲表达这些共同特征，显然是不可能的事。这就使得在命题逻辑中，甚至无法处理一些简单而又常见的推理过程。在命题的研究中，基于谓词分析的逻辑，称为谓词逻辑。谓词逻辑是命题逻辑的扩充和发展。本章重点1.谓词公式2.自然语言表述和谓词公式表示间的相互转化3.基于谓词公式的推理例子：我班有人能考上研究生。我班所有人都能考上研究生。经典例子苏格

2、拉底三段论:1)所有人都要死；2)苏格拉底是人；3)所以苏格拉底是要死的。设P:所有人都要死；Q:苏格拉底是人；R:苏格拉底是要死的。则前提：P,Q结论：R显然P∧QR不是永真式。引入谓词引入原因：1)克服原子命题的不可再分在性，将主语和谓语分开；2)原子命题不能描述数量关系。一、基本三要素个体与个体域：克服原子命题底不可再分性，可分为主语和谓语；个体：不依赖于人们的主观而独立存在的客观实体;是独立存在的客体，可以是具体事物也可以是抽象概念。个体域（D）：个体取值的范围。全总个体域。谓词：用于刻画个体的性质或者个体间的关系；－－谓词部分量词(、)量

3、词的辖域（作用域）个体谓词例如“猫是动物”一句中的“是动物”就是一个谓词，而“猫”是客体。“3大于2”中“大于”是一个谓词。3和2是客体。张三比李四高。用H（x,y）表示x比y高。a:张三b:李四H（a,b）：张三比李四高H（b,a）：李四比张三高谓词只涉及一个客体的谓词称为一元谓词，涉及两个客体的谓词称为二元谓词，涉及n个客体的谓词称为n元谓词。一般，如A表示谓词符号，用Xi表示第i个客体变项，则n元谓词表示为A(x1,…,xn)。谓词常项和谓词变项谓词常项：表示某个确定判定的谓词称为谓词常项。如上述两个谓词"是动物"、"大于"。谓词变项：尚未确定

4、的谓词称为谓词变项。例如用P（3，2）记一个谓词变项，可以表示“3大于2”、“3小于2”等等。n元谓词：在一个命题中，若有n个客体名称与谓词相联系，则称该谓词为n元谓词。如上述“是动物”为一元谓词，因为只有“猫”这一个客体与之相联系。而命题“3大于2”中的谓词“大于”与两个客体联结，是一个二元谓词。谓词与命题的关系一般来说，谓词不是命题，它的真值无法确定；为了使得它成为命题，必须：指定某一谓词常项代替P；指定n个个体常项a1,a2,…..,an分别代替n个个体变项x1,x2,…..,xn。例如：L（x，y）是一个2元谓词，它不是命题；当令L（x，y）

5、表示“x大于y”后，该谓词中的谓词部分便成了常项，但是它不是命题；当取a为2，b为3时，L（a，b）才是命题，并且是假命题。c为2，d为0时，L（c，d）是真命题。有时将不带个体变项的谓词称为0元谓词。0元谓词中的谓词的意义确定后，0元谓词是命题。使用谓词注意：（1）n元谓词中，客体变项的次序很重要。例：F（x,y）表示x是y的父亲，a:张三，b:张小明。F（a,b）表示张三是张小明的父亲。F（b,a）表示张小明是张三的父亲。（2）在讨论一个问题是必须先确定好个体域D。如不作限制，表示宇宙一切事物组成的个体，成为全总个体域。（3）同一个n元谓词，取不同的

6、个体，真假会不同。A（x）：x是大学生。A（a）真值可能为真，而A（b）真值可能为假。（4）对于同一谓词，个体域D不同，真值可能也不同。例：对于A（x），x是大学生。如D={大学生全体}，A（x）是重言式。如D={学生全体}，A（x）是仅可满足式。如D={老鼠全体}，A（x）是永假式。量词：有一个，存在，一些，some：所有的，全体，任意的，every，all量词的使用：一个量词后面紧跟着一个个体变元，不单独使用。xP(x)，yQ(y)，xyP(x,y)等。作用变元、指导变元量词的辖域xA(x)，xA(x)例如：D=全班同学的集合。A

7、(x):今天x迟到了。xA(x)表示今天x迟到了。x∈D，从而x指同学。xA(x)表示今天有同学迟到了。xA(x)就表示为今天所有的同学都迟到了。显然，当D为有限集合时，D={a1,a2,……,an}xP(x)=P(a1)∨P(a2)∨……∨P(an)xP(x)=P(a1)∧P(a2)∧……∧P(an)二、将命题用0元谓词符号化例如：2是素偶数。如果2大于3，则2大于4。解题步骤：1）找出个体词、量词和谓词；2）符号化谓词和个体词；3）使用符号化的谓词和个体词以及联接词进行命题符号化。带量词命题的符号化例如：所有人都是要死的。有些人长寿。由于量

8、词和个体域之间有紧密的联系，在考虑命题符号化问题时，必须先明确个体域。（没有特别