(1.3)--离散数学离散数学.ppt

《(1.3)--离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(1.3)--离散数学离散数学.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2024/1/202024/1/20离散数学离散数学1 1离 散 数 学离 散 数 学2024/1/202024/1/20离散数学离散数学2 2 第二章第二章 一阶逻辑一阶逻辑 2.12.1 一阶逻辑基本概念一阶逻辑基本概念一阶逻辑基本概念一阶逻辑基本概念 2.22.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2.32.3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2.42.4 一阶逻辑推理理论一阶逻辑推理理论一阶逻辑推理理论一阶逻辑推理理论2024/1/202024/1/20离散数学离散数学3 3推理：推理：推理：推理：从从从

2、从前提前提前提前提推出推出推出推出结论结论结论结论的思维的思维的思维的思维过程过程过程过程。前提前提前提前提指已知的命题公式，指已知的命题公式，指已知的命题公式，指已知的命题公式，结论结论结论结论是从前提出发按照一定的是从前提出发按照一定的是从前提出发按照一定的是从前提出发按照一定的推理规则推出的命题公式。推理规则推出的命题公式。推理规则推出的命题公式。推理规则推出的命题公式。逻辑结论逻辑结论逻辑结论逻辑结论（有效结论）：若（有效结论）：若（有效结论）：若（有效结论）：若(A A1 1 A A2 2 A An n)B B为重言式，为重言式，为重言式，为重言式，则称前提则称前提则称前提则称前提A

3、 A1 1,A A2 2,A An n推结论推结论推结论推结论B B的推理正确，的推理正确，的推理正确，的推理正确，B B是是是是A A1 1,A A2 2,A An n的逻辑结论或有效结论。的逻辑结论或有效结论。的逻辑结论或有效结论。的逻辑结论或有效结论。并记之为并记之为并记之为并记之为(A A1 1 A A2 2 A An n )B B (p p p p q q q q)r r r r是可满足式是可满足式是可满足式是可满足式2024/1/202024/1/20离散数学离散数学4 4在命题逻辑中，有些问题得不到解决在命题逻辑中，有些问题得不到解决在命题逻辑中，有些问题得不到解决在命题逻辑中，

4、有些问题得不到解决例如：判断以下推理是否正确：例如：判断以下推理是否正确：例如：判断以下推理是否正确：例如：判断以下推理是否正确：凡人都是要死的，凡人都是要死的，凡人都是要死的，凡人都是要死的，苏格拉底是人，苏格拉底是人，苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。所以苏格拉底是要死的。所以苏格拉底是要死的。这是著名的这是著名的这是著名的这是著名的“苏格拉底三段论苏格拉底三段论苏格拉底三段论苏格拉底三段论”，若用，若用，若用，若用p p p p,q q q q,r r r r 分分分分别表示以上别表示以上别表示以上别表示以上3 3 3 3个命题，推理形式为个命题，推

5、理形式为个命题，推理形式为个命题，推理形式为(p p p p q q q q)r r r r ，不是，不是，不是，不是重言式，也就是说用命题逻辑无法解决这个根据常识重言式，也就是说用命题逻辑无法解决这个根据常识重言式，也就是说用命题逻辑无法解决这个根据常识重言式，也就是说用命题逻辑无法解决这个根据常识就可断定的正确推理。就可断定的正确推理。就可断定的正确推理。就可断定的正确推理。2024/1/202024/1/20离散数学离散数学5 5凡凡凡凡人人人人都是要死的，都是要死的，都是要死的，都是要死的，苏格拉底苏格拉底苏格拉底苏格拉底是是是是人人人人，所以所以所以所以苏格拉底苏格拉底苏格拉底苏格拉

6、底是要死的。是要死的。是要死的。是要死的。主语、宾语被替换（一般被特定替换）主语、宾语被替换（一般被特定替换）主语、宾语被替换（一般被特定替换）主语、宾语被替换（一般被特定替换）“凡凡凡凡人人人人都是要死的都是要死的都是要死的都是要死的”可分解出三部分：可分解出三部分：可分解出三部分：可分解出三部分：（1 1）*都是要死的，都是要死的，都是要死的，都是要死的，（2 2）*是人是人是人是人（3 3）凡是）凡是）凡是）凡是2024/1/202024/1/20离散数学离散数学6 6 因此，有必要研究简单命题的各种成分因此，有必要研究简单命题的各种成分因此，有必要研究简单命题的各种成分因此，有必要研究

7、简单命题的各种成分(个体词，个体词，个体词，个体词，谓词，量词谓词，量词谓词，量词谓词，量词)，以及它们的形式结构和逻辑关系，总，以及它们的形式结构和逻辑关系，总，以及它们的形式结构和逻辑关系，总，以及它们的形式结构和逻辑关系，总结出正确的推理形式和规则。结出正确的推理形式和规则。结出正确的推理形式和规则。结出正确的推理形式和规则。这部分内容即一阶逻辑这部分内容即一阶逻辑这部分内容即一阶逻辑这部分内容即一阶逻辑(又称谓词逻辑又称谓词逻辑又称谓词逻辑又称谓词逻辑)。谓词逻辑应用很广，如谓词逻辑与数据库，特别谓词逻辑应用很广，如谓词逻辑与数据库，特别谓词逻辑应用很广，如谓词逻辑与数据库，特别谓词逻

8、辑应用很广，如谓词逻辑与数据库，特别是关系数据库有密切关系。在关系数据库中，逻辑代是关系数据库有密切关系。在关系数据库中，逻辑代是关系数据库有密切关系。在关系数据库中，逻辑代是关系数据库有密切关系。在关系数据库中，逻辑代数表达式是谓词表达式之一。采用谓词逻辑作为数据数表达式是谓词表达式之一。采用谓词逻辑作为数据数表达式是谓词表达式之一。采用谓词逻辑作为数据数表达式是谓词表达式之一。采用谓词逻辑作为数据库系统的理论背景，可将数据库系统扩展改造成知识库系统的理论背景，可将数据库系统扩展改造成知识库系统的理论背景，可将数据库系统扩展改造成知识库系统的理论背景，可将数据库系统扩展改造成知识库。库。库。

9、库。2024/1/202024/1/20离散数学离散数学7 7内容：内容：个体词，谓词，量词，命题符号化重点：重点：1、掌握个体词，谓词，量词 的有关概念，2、掌握在一阶逻辑中的命题符号化。2.1 2.1 一阶逻辑基本概念一阶逻辑基本概念2024/1/202024/1/20离散数学离散数学8 8 如：如：如：如：(1)(1)(1)(1)是无理数是无理数是无理数是无理数 (性质性质性质性质)(2)(2)(2)(2)小李比小赵高小李比小赵高小李比小赵高小李比小赵高2 2厘米厘米厘米厘米 (关系关系关系关系)简单命题总可以被分解成个体词和谓词两部分。简单命题总可以被分解成个体词和谓词两部分。简单命题

10、总可以被分解成个体词和谓词两部分。简单命题总可以被分解成个体词和谓词两部分。一、个体词与谓词 可以独立存在的客体。既可以是抽象的可以独立存在的客体。既可以是抽象的可以独立存在的客体。既可以是抽象的可以独立存在的客体。既可以是抽象的 概念，也可以是具体的事物。概念，也可以是具体的事物。概念，也可以是具体的事物。概念，也可以是具体的事物。2.1 2.1 一阶逻辑基本概念一阶逻辑基本概念 用来刻划个体词的性质或个体词之间的关用来刻划个体词的性质或个体词之间的关用来刻划个体词的性质或个体词之间的关用来刻划个体词的性质或个体词之间的关 系的词。系的词。系的词。系的词。如：李明，自然数，如：李明，自然数，

11、如：李明，自然数，如：李明，自然数，个体词：个体词：个体词：个体词：谓谓谓谓 词：词：词：词：2024/1/202024/1/20离散数学离散数学9 9又如：又如：又如：又如：(1)(1)计算机是科学技术的工具计算机是科学技术的工具计算机是科学技术的工具计算机是科学技术的工具.其中其中其中其中“计算机计算机计算机计算机”是是是是个体词，个体词，个体词，个体词，“是科学技术的工具是科学技术的工具是科学技术的工具是科学技术的工具”是谓是谓是谓是谓词。词。词。词。(2)(2)张三是李四的领导张三是李四的领导张三是李四的领导张三是李四的领导.其中其中其中其中“张三张三张三张三”和和和和“李四李四李四李

12、四”都是个体词，都是个体词，都是个体词，都是个体词，“是是是是的领导的领导的领导的领导”都是都是都是都是谓词。谓词。谓词。谓词。(3)(3)他是三好学生。他是三好学生。他是三好学生。他是三好学生。(4)5(4)5大于大于大于大于3 3。2024/1/202024/1/20离散数学离散数学1010一、个体词与谓词（续）表示具体的或特定的个体的词。用小写表示具体的或特定的个体的词。用小写表示具体的或特定的个体的词。用小写表示具体的或特定的个体的词。用小写 字母字母字母字母 a a,b b,c c,表示。表示。表示。表示。表示抽象的或泛指的个体的词。用小写表示抽象的或泛指的个体的词。用小写表示抽象的

13、或泛指的个体的词。用小写表示抽象的或泛指的个体的词。用小写 字母字母字母字母 x x,y y,z z,表示。表示。表示。表示。个体常项：个体常项：个体常项：个体常项：个体变项：个体变项：个体变项：个体变项：2024/1/202024/1/20离散数学离散数学1111一、个体词与谓词（续）设设设设Q(xQ(x，y)y)表示表示表示表示“x x比比比比y y重重重重”，当，当，当，当x x，y y指人或物时，指人或物时，指人或物时，指人或物时，它是一个命题，但若它是一个命题，但若它是一个命题，但若它是一个命题，但若x x，y y指实数时，指实数时，指实数时，指实数时，Q(xQ(x，y)y)就不是就

14、不是就不是就不是一个命题。一个命题。一个命题。一个命题。命题函数不是一个命题，只有客体变元取特定名称时，才命题函数不是一个命题，只有客体变元取特定名称时，才命题函数不是一个命题，只有客体变元取特定名称时，才命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。但是客体变元在哪些范围内取特定的值，能成为一个命题。但是客体变元在哪些范围内取特定的值，能成为一个命题。但是客体变元在哪些范围内取特定的值，能成为一个命题。但是客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。对是否成为命题及命题的真值极有影响。对是否成为命题及命题的真值极有影响。对是否成为命题及命题的真值极

15、有影响。R(x)R(x)表示表示表示表示“x x是大学生是大学生是大学生是大学生”，是永真式是永真式是永真式是永真式?永假式永假式永假式永假式?可满足式？可满足式？可满足式？可满足式？2024/1/202024/1/20离散数学离散数学1212个体域可以是有限事物的集合，也可以是无限事个体域可以是有限事物的集合，也可以是无限事个体域可以是有限事物的集合，也可以是无限事个体域可以是有限事物的集合，也可以是无限事物的集合。不加声明即为全总个体域。物的集合。不加声明即为全总个体域。物的集合。不加声明即为全总个体域。物的集合。不加声明即为全总个体域。一、个体词与谓词（续）从上述看到，命题函数确定为命题

16、，与客体变从上述看到，命题函数确定为命题，与客体变从上述看到，命题函数确定为命题，与客体变从上述看到，命题函数确定为命题，与客体变元的论述范围有关。元的论述范围有关。元的论述范围有关。元的论述范围有关。个体变项的取值范围，又称论域。个体变项的取值范围，又称论域。个体变项的取值范围，又称论域。个体变项的取值范围，又称论域。宇宙间一切事物组成的个体域。宇宙间一切事物组成的个体域。宇宙间一切事物组成的个体域。宇宙间一切事物组成的个体域。个个个个 体体体体 域：域：域：域：全总个体域：全总个体域：全总个体域：全总个体域：2024/1/202024/1/20离散数学离散数学1313 个体变项个体变项个体

17、变项个体变项 x x,y y 具有关系具有关系具有关系具有关系L L，记作，记作，记作，记作L L(x x,y y)一、个体词与谓词（续）表示性质或关系表示性质或关系表示性质或关系表示性质或关系 用大写字母用大写字母用大写字母用大写字母F F,G G,HH,表示。表示。表示。表示。一般根据上下文区分常项和变项。一般根据上下文区分常项和变项。一般根据上下文区分常项和变项。一般根据上下文区分常项和变项。个体变项个体变项个体变项个体变项 x x 具有性质具有性质具有性质具有性质F F，记作，记作，记作，记作F F(x x)谓词：谓词：谓词：谓词：2024/1/202024/1/20离散数学离散数学1

18、414一、个体词与谓词（续）如如如如:(1):(1)设设设设S S(x x)：x x学习很好，学习很好，学习很好，学习很好，W W(x x)：x x是三好学生是三好学生是三好学生是三好学生 则则则则 S S(x x)表示表示表示表示 S S(x x)WW(x x)表示表示表示表示 S S(x x)WW(x x)表示表示表示表示 “x x学习不是很好学习不是很好学习不是很好学习不是很好”。“x x学习很好且是三好学生学习很好且是三好学生学习很好且是三好学生学习很好且是三好学生”。“如果如果如果如果x x的学习很好，则的学习很好，则的学习很好，则的学习很好，则x x是三好学生。是三好学生。是三好学

19、生。是三好学生。”2024/1/202024/1/20离散数学离散数学1515(2)(2)用用用用H(x,y)H(x,y)：x x比比比比y y长得高，长得高，长得高，长得高，设设设设b b：李四，：李四，：李四，：李四，c c：张三。：张三。：张三。：张三。则则则则 H(bH(b，c)c)表示表示表示表示 H(bH(b，c)c)H(cH(c，b)b)表示表示表示表示“李四不比张三长得高李四不比张三长得高李四不比张三长得高李四不比张三长得高”。“李四不比张三长得高李四不比张三长得高李四不比张三长得高李四不比张三长得高”且且且且“张三不比李四长得张三不比李四长得张三不比李四长得张三不比李四长得高

20、高高高”即即即即“张三与李四同样高张三与李四同样高张三与李四同样高张三与李四同样高”。2024/1/202024/1/20离散数学离散数学1616一、个体词与谓词（续）例例例例1 1:将下列命题符号化将下列命题符号化将下列命题符号化将下列命题符号化 (1)(1)是无理数。是无理数。是无理数。是无理数。(2)(2)偶数加奇数等于偶数。偶数加奇数等于偶数。偶数加奇数等于偶数。偶数加奇数等于偶数。解：解：解：解：(1)(1)设设设设F F(x x):):x x 是无理数，是无理数，是无理数，是无理数，a a:则符号化为则符号化为则符号化为则符号化为 (2)(2)设设设设L L(x x,y y):):

21、x x 加加加加 y y 等于偶数，等于偶数，等于偶数，等于偶数，a a:偶数，偶数，偶数，偶数，b b:奇数奇数奇数奇数 则符号化为则符号化为则符号化为则符号化为F F(a a)。L L(a a,b b)。2024/1/202024/1/20离散数学离散数学1717一、个体词与谓词（续）例例例例1 1:将下列命题符号化将下列命题符号化将下列命题符号化将下列命题符号化 (3)(3)你们是大二的学生。你们是大二的学生。你们是大二的学生。你们是大二的学生。(4)(4)情商比智商更重要。情商比智商更重要。情商比智商更重要。情商比智商更重要。解：解：解：解：(1)(1)设设设设G G(x x):):x

22、 x 是大二的学生，是大二的学生，是大二的学生，是大二的学生，a a:你们你们你们你们 则符号化为则符号化为则符号化为则符号化为 (2)(2)设设设设H H(x x,y y):):x x 比比比比 y y 更重要，更重要，更重要，更重要，a a:情商，情商，情商，情商，b b:智商智商智商智商 则符号化为则符号化为则符号化为则符号化为G G(a a)。H H(a a,b b)。2024/1/202024/1/20离散数学离散数学18180 0 元谓词：元谓词：元谓词：元谓词：不含个体变项的谓词。不含个体变项的谓词。不含个体变项的谓词。不含个体变项的谓词。如：如：如：如：a a为为为为2 2，b

23、 b为为为为3 3，L L(a a,b b)是是是是0 0元谓词。元谓词。元谓词。元谓词。简单命题都可以用简单命题都可以用简单命题都可以用简单命题都可以用0 0元谓词表示，使用联结词便元谓词表示，使用联结词便元谓词表示，使用联结词便元谓词表示，使用联结词便可将复合命题用可将复合命题用可将复合命题用可将复合命题用0 0元谓词符号化。元谓词符号化。元谓词符号化。元谓词符号化。一、个体词与谓词（续）元元元元 数：数：数：数：谓词中所包含的个体词数。谓词中所包含的个体词数。谓词中所包含的个体词数。谓词中所包含的个体词数。n n 元谓词：元谓词：元谓词：元谓词：含含含含n n(n n 1)1)个个体词个

24、个体词个个体词个个体词(个体变项个体变项个体变项个体变项)的谓词，的谓词，的谓词，的谓词，可用可用可用可用P P(x x1 1,x x2 2,x xn n)表示。表示。表示。表示。一元谓词表示性质，二元或多元谓词表示关系。一元谓词表示性质，二元或多元谓词表示关系。一元谓词表示性质，二元或多元谓词表示关系。一元谓词表示性质，二元或多元谓词表示关系。2024/1/202024/1/20离散数学离散数学1919一、个体词与谓词（续）例例例例2 2：将下列命题用：将下列命题用：将下列命题用：将下列命题用0 0元谓词符号化。元谓词符号化。元谓词符号化。元谓词符号化。(1)2(1)2是素数且是偶数。是素数

25、且是偶数。是素数且是偶数。是素数且是偶数。(2)(2)如果如果如果如果2 2大于大于大于大于3 3，则，则，则，则3 3大于大于大于大于4 4。(3)(3)如果张明比李民高，李民比赵亮高，则张明比如果张明比李民高，李民比赵亮高，则张明比如果张明比李民高，李民比赵亮高，则张明比如果张明比李民高，李民比赵亮高，则张明比 赵亮高。赵亮高。赵亮高。赵亮高。解：解：解：解：(1)(1)设设设设F F(x x):):x x 是素数，是素数，是素数，是素数，G G(x x):):x x 是偶数，是偶数，是偶数，是偶数，a a:2:2 则命题符号化为则命题符号化为则命题符号化为则命题符号化为F F(a a)G

26、 G(a a)。2024/1/202024/1/20离散数学离散数学2020一、个体词与谓词（续）例例例例2 2：将下列命题用：将下列命题用：将下列命题用：将下列命题用0 0元谓词符号化。元谓词符号化。元谓词符号化。元谓词符号化。(1)2(1)2是素数且是偶数。是素数且是偶数。是素数且是偶数。是素数且是偶数。(2)(2)如果如果如果如果2 2大于大于大于大于3 3，则，则，则，则3 3大于大于大于大于4 4。(3)(3)如果张明比李民高，李民比赵亮高，则张明比如果张明比李民高，李民比赵亮高，则张明比如果张明比李民高，李民比赵亮高，则张明比如果张明比李民高，李民比赵亮高，则张明比 赵亮高。赵亮高

27、。赵亮高。赵亮高。解：解：解：解：(2)(2)设设设设L L(x x,y y):):x x大于大于大于大于y y，a a:2:2，b b:3:3，c c:4:4 则命题符号化为则命题符号化为则命题符号化为则命题符号化为同理同理同理同理(3)(3)可可可可符号化为符号化为符号化为符号化为L L(a a,b b)L L(b b,c c)。(L(L(a a,b b)L L(b b,c c)L L(a a,c c)。2024/1/202024/1/20离散数学离散数学2121用谓词的概念可将三段论做如下的符号化：用谓词的概念可将三段论做如下的符号化：令令 H(x)：“x是人是人”，M(x)：“x必死必

28、死”，a：“苏格拉底苏格拉底”。则三段论的三个命题表示如下：则三段论的三个命题表示如下：P：H(x)M(x)Q：H(a)R：M(a)2024/1/202024/1/20离散数学离散数学2222考虑考虑考虑考虑“命题命题命题命题”P P P P的否定的否定的否定的否定“命题命题命题命题”P P P P。P P P P (H(x)(H(x)(H(x)(H(x)M(x)M(x)M(x)M(x)(H(x)H(x)H(x)H(x)M(x)M(x)M(x)M(x)H(x)H(x)H(x)H(x)M(x)M(x)M(x)M(x)亦即，亦即，亦即，亦即，“命题命题命题命题”P P P P的否定的否定的否定的否

29、定“命题命题命题命题”是是是是“所有人都不所有人都不所有人都不所有人都不死死死死”。这和人们日常对命题这和人们日常对命题这和人们日常对命题这和人们日常对命题“所有人都必死所有人都必死所有人都必死所有人都必死”的否定的理的否定的理的否定的理的否定的理解，相差得实在太远了。解，相差得实在太远了。解，相差得实在太远了。解，相差得实在太远了。其原因在于，命题其原因在于，命题P的确切意思应该是：的确切意思应该是：“对对任意任意x，如果，如果x是人，则是人，则x必死必死”。但是但是H(x)M(x)中并没有确切的表示出中并没有确切的表示出“对任意对任意x”这个意思这个意思2024/1/202024/1/20

30、离散数学离散数学2323二、量词-表示数量的词表示数量的词 表示表示表示表示“一切一切一切一切”，“所有所有所有所有”，“任意任意任意任意”等等等等的词。的词。的词。的词。用符号用符号用符号用符号“”表示。表示。表示。表示。(A Arbitrary rbitrary 任意的任意的任意的任意的)x x表示对个体域中的所有个体，表示对个体域中的所有个体，表示对个体域中的所有个体，表示对个体域中的所有个体，xF xF(x x)表示个表示个表示个表示个体域中的所有个体都有性质体域中的所有个体都有性质体域中的所有个体都有性质体域中的所有个体都有性质F F。1 1、全称量词：全称量词：全称量词：全称量词：

31、自然语言中的自然语言中的“一切一切”，“所有的所有的”，“任意的任意的”都是都是量词量词例如例如例如例如 (a)(a)所有的人都是要呼吸的。所有的人都是要呼吸的。所有的人都是要呼吸的。所有的人都是要呼吸的。(b)(b)每个学生都努力学习。每个学生都努力学习。每个学生都努力学习。每个学生都努力学习。2024/1/202024/1/20离散数学离散数学2424若设若设若设若设 M(x)M(x)：x x是人，是人，是人，是人，H(x)H(x)：x x要呼吸。要呼吸。要呼吸。要呼吸。P(x)P(x)：x x是学生，是学生，是学生，是学生，Q(x)Q(x)：x x努力学习。努力学习。努力学习。努力学习。

32、I(x)I(x)：x x是整数，是整数，是整数，是整数，R(x)R(x)：x x是正数，是正数，是正数，是正数，N(x)N(x)：x x是负数。是负数。是负数。是负数。则上述三例就记为：则上述三例就记为：则上述三例就记为：则上述三例就记为：(a)(a)所有的人都是要呼吸的：所有的人都是要呼吸的：所有的人都是要呼吸的：所有的人都是要呼吸的：(b)(b)每个学生都努力学习：每个学生都努力学习：每个学生都努力学习：每个学生都努力学习：(c)(c)任何整数或是正的或是负的任何整数或是正的或是负的任何整数或是正的或是负的任何整数或是正的或是负的:x(M(x)H(x)x(M(x)H(x)x(P(x)Q(x

33、)x(P(x)Q(x)x(I(x)R(x)x(I(x)R(x)N(x)N(x)2024/1/202024/1/20离散数学离散数学2525二、量词-表示数量的词表示数量的词 自然语言中的自然语言中的“存在着存在着”，“有一个有一个”，“至少有至少有一个一个”等都是量词。等都是量词。例如例如例如例如 (a)(a)存在一个数是质数。存在一个数是质数。存在一个数是质数。存在一个数是质数。(b)(b)一些人是聪明的。一些人是聪明的。一些人是聪明的。一些人是聪明的。(c)(c)有些人早饭吃面包。有些人早饭吃面包。有些人早饭吃面包。有些人早饭吃面包。2 2、存在量词：存在量词：存在量词：存在量词：表示表示

34、表示表示“存在存在存在存在”，“有某些有某些有某些有某些”，“至少有至少有至少有至少有一个一个一个一个”等的词。用符号等的词。用符号等的词。用符号等的词。用符号“”表示。表示。表示。表示。(E Existxist 存在存在存在存在)x x表示存在个体域中的个体，表示存在个体域中的个体，表示存在个体域中的个体，表示存在个体域中的个体，xF xF(x x)表示存在表示存在表示存在表示存在个体域中的个体具有性质个体域中的个体具有性质个体域中的个体具有性质个体域中的个体具有性质F F。2024/1/202024/1/20离散数学离散数学2626设设设设 P(x)P(x)：x x是质数。是质数。是质数。

35、是质数。M(x)M(x)：x x是人。是人。是人。是人。R(x)R(x)：x x是聪明的。是聪明的。是聪明的。是聪明的。E(x)E(x)：x x早饭吃面包。早饭吃面包。早饭吃面包。早饭吃面包。则上述三例可表示为：则上述三例可表示为：则上述三例可表示为：则上述三例可表示为：(a)(a)存在一个数是质数存在一个数是质数存在一个数是质数存在一个数是质数:(b)(b)一些人是聪明的一些人是聪明的一些人是聪明的一些人是聪明的:(c)(c)有些人早饭吃面包有些人早饭吃面包有些人早饭吃面包有些人早饭吃面包:x(P(x)x(P(x)x(M(x)x(M(x)R(x)R(x)x(M(x)x(M(x)E(x)E(x

36、)2024/1/202024/1/20离散数学离散数学2727 xG(x)取取1值值对任意对任意x D，G(x)都取都取1值；值；xG(x)取取0值值有一个有一个x0 D，使，使G(x0)取取0值。值。xG(x)取取1值值有一个有一个x0 D，使，使G(x0)取取1值；值；xG(x)取取0值值对所有对所有x D，G(x)都取都取0值。值。2024/1/202024/1/20离散数学离散数学2828二、量词（续）例例例例3 3：符号化下列命题：符号化下列命题：符号化下列命题：符号化下列命题 (1)(1)所有的人都会死。所有的人都会死。所有的人都会死。所有的人都会死。(2)(2)有的人活百岁以上。

37、有的人活百岁以上。有的人活百岁以上。有的人活百岁以上。3 3、特征谓词特征谓词特征谓词特征谓词：在全总个体域的情况下，为了指定某在全总个体域的情况下，为了指定某在全总个体域的情况下，为了指定某在全总个体域的情况下，为了指定某 个个体变项的范围，引入的谓词。个个体变项的范围，引入的谓词。个个体变项的范围，引入的谓词。个个体变项的范围，引入的谓词。解：个体域为人类集合时，符号化解：个体域为人类集合时，符号化解：个体域为人类集合时，符号化解：个体域为人类集合时，符号化(1)(1)为为为为 xF xF(x x)，其中，其中，其中，其中 F F(x x)：x x会死，会死，会死，会死，(2)(2)为为为

38、为 xG xG(x x)，其中，其中，其中，其中G G(x x)：x x能活百岁以上。能活百岁以上。能活百岁以上。能活百岁以上。解：全总个体域时，引入特征谓词解：全总个体域时，引入特征谓词解：全总个体域时，引入特征谓词解：全总个体域时，引入特征谓词M M(x x):x x是人是人是人是人 则则则则(1)(1)符号化为符号化为符号化为符号化为 x x(M M(x x)F F(x x)(2)(2)符号化为符号化为符号化为符号化为 x x(M M(x x)G G(x x)2024/1/202024/1/20离散数学离散数学2929使用量词时，使用量词时，使用量词时，使用量词时，应注意以下应注意以下应

39、注意以下应注意以下6 6 6 6点：点：点：点：(1)(1)(1)(1)在不同个体域中，命题符号化的形式在不同个体域中，命题符号化的形式在不同个体域中，命题符号化的形式在不同个体域中，命题符号化的形式可能不一样，可能不一样，可能不一样，可能不一样，(2)(2)(2)(2)一般，除非有特别说明，均以全总个一般，除非有特别说明，均以全总个一般，除非有特别说明，均以全总个一般，除非有特别说明，均以全总个体域为个体域，体域为个体域，体域为个体域，体域为个体域，(3)(3)(3)(3)在引入特性谓词后，使用全称量词在引入特性谓词后，使用全称量词在引入特性谓词后，使用全称量词在引入特性谓词后，使用全称量词

40、 用用用用“”，使用存在量词，使用存在量词，使用存在量词，使用存在量词 用用用用“”，所有的人都是要呼吸的：所有的人都是要呼吸的：所有的人都是要呼吸的：所有的人都是要呼吸的：x(M(x)H(x)x(M(x)H(x)一些人是聪明的一些人是聪明的一些人是聪明的一些人是聪明的:x(M(x)x(M(x)R(x)R(x)2024/1/202024/1/20离散数学离散数学3030使用量词时，使用量词时，使用量词时，使用量词时，应注意以下应注意以下应注意以下应注意以下6 6 6 6点：点：点：点：(4)n(4)n(4)n(4)n元谓词化为命题至少需要元谓词化为命题至少需要元谓词化为命题至少需要元谓词化为命

41、题至少需要n n n n个量词，个量词，个量词，个量词，(5)(5)(5)(5)当个体域为有限集时，如当个体域为有限集时，如当个体域为有限集时，如当个体域为有限集时，如 ，则，则，则，则 (6)(6)(6)(6)多个量词同时出现时，不能随意颠倒顺序。多个量词同时出现时，不能随意颠倒顺序。多个量词同时出现时，不能随意颠倒顺序。多个量词同时出现时，不能随意颠倒顺序。2024/1/202024/1/20离散数学离散数学3131三、应用例例例例4 4：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。(1)(1)对所有的对所有

42、的对所有的对所有的 x x，均有，均有，均有，均有 x x2 2-1=(-1=(x x+1)(+1)(x x-1)-1)。(2)(2)存在存在存在存在 x x，使得，使得，使得，使得 x x+5=2+5=2。(3)(3)凡偶数均能被凡偶数均能被凡偶数均能被凡偶数均能被2 2整除。整除。整除。整除。(4)(4)存在着偶素数。存在着偶素数。存在着偶素数。存在着偶素数。(5)(5)没有不犯错误的人。没有不犯错误的人。没有不犯错误的人。没有不犯错误的人。(6)(6)在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。(7)(7)一切人

43、都不一样高。一切人都不一样高。一切人都不一样高。一切人都不一样高。(8)(8)每个自然数都有后继数。每个自然数都有后继数。每个自然数都有后继数。每个自然数都有后继数。(9)(9)有的自然数无先驱数。有的自然数无先驱数。有的自然数无先驱数。有的自然数无先驱数。解题思想解题思想解题思想解题思想:(1)(1)找到所有的个体词；找到所有的个体词；找到所有的个体词；找到所有的个体词；(2)(2)是否要引入特征谓词；是否要引入特征谓词；是否要引入特征谓词；是否要引入特征谓词；(3)(3)描述个体词的性质描述个体词的性质描述个体词的性质描述个体词的性质(一元谓词）、描述个体一元谓词）、描述个体一元谓词）、描

44、述个体一元谓词）、描述个体词的关系词的关系词的关系词的关系(二元谓词二元谓词二元谓词二元谓词)；(4)(4)按命题的实际意义进按命题的实际意义进按命题的实际意义进按命题的实际意义进行刻划。行刻划。行刻划。行刻划。2024/1/202024/1/20离散数学离散数学3232三、应用（续）例例例例4 4：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。(1)(1)对所有的对所有的对所有的对所有的 x x，均有，均有，均有，均有 x x2 2-1=(-1=(x x+1)(+1)(x x-1)-1)。(2)(2)存在存在存在

45、存在 x x，使得，使得，使得，使得 x x+5=2+5=2。(3)(3)凡偶数均能被凡偶数均能被凡偶数均能被凡偶数均能被2 2整除。整除。整除。整除。解：解：解：解：(1)(1)xF xF(x x)，其中其中其中其中F F(x x)：x x2 2-1=(-1=(x x+1)(+1)(x x-1)-1)。(2)(2)xF xF(x x)，其中其中其中其中F F(x x)：x x+5=2+5=2。(3)(3)x x(M M(x x)F F(x x)，其中其中其中其中M M(x x)：x x 是偶数，是偶数，是偶数，是偶数，F F(x x)：x x 能被能被能被能被2 2整除。整除。整除。整除。2

46、024/1/202024/1/20离散数学离散数学3333三、应用（续）例例例例4 4：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。(4)(4)存在着偶素数。存在着偶素数。存在着偶素数。存在着偶素数。(5)(5)没有不犯错误的人。没有不犯错误的人。没有不犯错误的人。没有不犯错误的人。解：解：解：解：(4)(4)x x(M M(x x)F F(x x)，其中其中其中其中M M(x x)：x x 是偶数，是偶数，是偶数，是偶数，F F(x x)：x x 是素数。是素数。是素数。是素数。(5)(5)x x(M M(x

47、x)F F(x x)，其中其中其中其中M M(x x)：x x 是人，是人，是人，是人，F F(x x)：x x 犯错误。犯错误。犯错误。犯错误。或或或或 x x(M M(x x)F F(x x)“所有的人都会犯错误所有的人都会犯错误所有的人都会犯错误所有的人都会犯错误”2024/1/202024/1/20离散数学离散数学3434 (7)(7)x x y y(M M(x x)M M(y y)H H(x x,y y)L L(x x,y y)，其中其中其中其中M M(x x)：x x 是人，是人，是人，是人，H H(x x,y y)：x x 与与与与y y 不是同一个人，不是同一个人，不是同一个人

48、，不是同一个人，L L(x x,y y)：x x 与与与与y y 一样高。或一样高。或一样高。或一样高。或 x x y y(M M(x x)M M(y y)H H(x x,y y)L L(x x,y y)三、应用（续）例例例例4 4：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。(6)(6)在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。(7)(7)一切人都不一样高。一切人都不一样高。一切人都不一样高。一切人都不一样高。解：解：解：解：(6)(

49、6)x x(M M(x x)F F(x x)，其中其中其中其中M M(x x)：x x是在北京是在北京是在北京是在北京工作的人，工作的人，工作的人，工作的人，F F(x x)：x x是北京人。或是北京人。或是北京人。或是北京人。或 x x(M M(x x)F F(x x)2024/1/202024/1/20离散数学离散数学3535三、应用（续）例例例例4 4：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。：在一阶逻辑中将下列命题符号化。(8)(8)每个自然数都有后继数。每个自然数都有后继数。每个自然数都有后继数。每个自然数都有后继数。(9)(9)

50、有的自然数无先驱数有的自然数无先驱数有的自然数无先驱数有的自然数无先驱数。解：解：解：解：(8)(8)x x(M M(x x)y y(M M(y y)H H(x x,y y)，其中其中其中其中M M(x x)：x x 是自然数，是自然数，是自然数，是自然数，H H(x x,y y)：y y 是是是是 x x 的后继数。的后继数。的后继数。的后继数。(9)(9)x x(M M(x x)y y(M M(y y)H H(x x,y y)，其中其中其中其中M M(x x)：x x 是自然数，是自然数，是自然数，是自然数，H H(x x,y y)：y y 是是是是 x x 的先驱数。的先驱数。的先驱数。