离散数学标准讲义sy第2章.ppt

《离散数学标准讲义sy第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二章一阶逻辑9/16/20211离散数学所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。9/16/20212离散数学命题逻辑的局限符号化：P:所有的人都是要死的。Q:苏格拉底是人，R:所以苏格拉底是要死的。P∧Q→R推理正确吗?说明：命题逻辑不能表现出简单命题中各部分的内在联系。9/16/20213离散数学本章概要一阶逻辑，又称一阶谓词逻辑或谓词逻辑。对一阶逻辑的研究能够克服命题逻辑的局限性，对简单命题进行进一步的分解，以表达出个体和总体间的内在联系和数量关系。9/16/20214离散数学一阶逻辑知识结构

2、2.1一阶逻辑基本概念2.2一阶逻辑等值演算2.3一阶逻辑的推理理论第四次课第一、二次课第三次课9/16/20215离散数学一阶逻辑基本概念知识点谓词和量词概念一阶逻辑命题的符号化（特性谓词）谓词公式基本概念谓词公式的解释谓词公式的分类9/16/20216离散数学谓词和量词一个简单命题中表示研究对象即主体或客体(对应名词成分)的词称为个体词。表示一个个体词性质的或多个个体词之间关系的词称为谓词。例：小张是学生。小张在跑步。小张比小李高2cm。X是我的同学。9/16/20217离散数学谓词和量词个体词个体常项表示具体

3、的、特指的个体的词用a,b,c…表示个体变项表示抽象的、泛指的或在一定范围内变化的个体的词用x,y,z…表示个体域个体变项的取值范围全总个体域9/16/20218离散数学谓词和量词谓词谓词常项：表示具体性质或关系的谓词谓词变项：表示抽象的或泛指的性质或关系的谓词用F,G,H…表示0元谓词：不包含有个体变项的谓词n元谓词：包含有n个体变项的谓词例：（1）3是整数。（2）x和y具有关系L。（3）小张和小李是同学。9/16/20219离散数学全称量词和存在量词符号化:(1)所有的人都是要死的。(2)有的人活百岁以上。量词

4、：表示个体常项或变项之间数量关系的词全称量词用∀表示，形成的命题形式为∀xF(x)，即“对所有的x，F(x)为真”。存在量词用∃表示，形成的命题形式为∃xF(x)，即“存在x值，使F(x)为真”。9/16/202110离散数学一阶逻辑命题符号化例：在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡是人都要呼吸.(2)有的人用左手写字.其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.解答9/16/202111离散数学(1)凡是人都要呼吸.解：(a)个体域D1为人类集合(b)个体域D

5、2为全总个体域.为将人从全总个体域中分离出来，令9/16/202112离散数学(2)有的人用左手写字.解:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.9/16/202113离散数学一阶逻辑命题符号化例：在个体域限制为(a)和(b)条件时，将下列命题符号化:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2).(2)存在x，使得x+5=3.其中:(a)个体域D1=N(N为自然数集合)(b)个体域D2=R(R为实数集合)解答9/16/202114离散数学(1)对于任意的x，均有x2-3x+2=(x

6、-1)(x-2)解：令(a)个体域D1=N(N为自然数集合)命题符号化为：(b)个体域D2=R(R为实数集合)命题符号化为：TT真值：真值：9/16/202115离散数学（2）存在x，使得x+5=3.解:令(a)个体域D1=N(N为自然数集合)命题符号化为：(b)个体域D2=R(R为实数集合)命题符号化为：真值：真值：FT9/16/202116离散数学一阶逻辑命题符号化例：将下列命题符号化，并讨论真值.(1)所有的人都长着黑头发.解：定义特性谓词M(x)：x是人。定义谓词F(x)：x长着黑头发。真值：F9/16/2

7、02117离散数学(2)有的人登上过月球.解：定义特性谓词M(x)：x是人。定义谓词F(x)：x登上过月球。真值：T9/16/202118离散数学(3)没有人登上过木星.解：定义特性谓词M(x)：x是人。定义谓词F(x)：x登上过木星。真值：T9/16/202119离散数学(4)在美国留学的学生未必都是亚洲人.解：定义特性谓词M(x)：x是在美国留学的学生。定义谓词F(x)：x是亚洲人。真值：T9/16/202120离散数学例：将下列命题符号化。(1)兔子比乌龟跑得快.解：定义特性谓词F(x)：x是兔子。G(y):

8、y是乌龟。定义谓词H(x,y)：x比y跑得快。9/16/202121离散数学(2)有的兔子比所有的乌龟跑得快.解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。定义谓词H(x,y)：x比y跑得快。9/16/202122离散数学(3)并不是所有的兔子都比乌龟跑得快.解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。定义谓词H(x,y)：x比y跑得快