离散数学教案 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组
离散数学教案 1 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组
离散数学教案 谓词逻辑 、学习目的与要求 本章目的是讲授谓词逻辑与命题逻辑的联系与区别，通过本章的学习，使学生了 解谓词逻辑的基本概念，掌握谓词逻辑中的基本定义、定理。了解谓词逻辑的推理方 法。 二、知识点 1.谓词逻辑的概念与表示方法。 2.命题函数与量词 3.谓词逻辑中的合式公式(Wf)与自然语言的翻译： 4.谓词中的变元约束： 5.谓词逻辑演算中的等价式与蕴涵式： 6.谓词逻辑中的前束范式： 7.谓词逻辑的推理理论。 三、要求 1.识记 全称量词、存在量词的概念，量词的辖域，约束变元、自由变元的辨认。 2.领会 谓词逻辑中的合式公式(W)的递归定义、自然语言翻译成谓词公式，化公式 为前束范式，谓词逻辑的推理理论、证明方法、推理规则。命题公式扩充到谓词逻辑 中的联系与区别。 3.简单应用 利用谓词逻辑解决简单的论证应用题。 四、主要内容 第2章谓词逻辑 在Ls中，把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研 究以原子命题为基本单位的复合命题之间的逻辑关系和推理。这样，有些推理用命题 逻辑就难以确切地表示出来。例如，著名的亚里士多德三段论苏格拉底推理： 所有的人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的
离散数学教案 2 谓词逻辑 一、学习目的与要求 本章目的是讲授谓词逻辑与命题逻辑的联系与区别，通过本章的学习，使学生了 解谓词逻辑的基本概念，掌握谓词逻辑中的基本定义、定理。了解谓词逻辑的推理方 法。 二、知识点 1．谓词逻辑的概念与表示方法； 2．命题函数与量词 3．谓词逻辑中的合式公式（Wff）与自然语言的翻译； 4．谓词中的变元约束； 5．谓词逻辑演算中的等价式与蕴涵式； 6．谓词逻辑中的前束范式； 7．谓词逻辑的推理理论。 三、要求 1．识记 全称量词、存在量词的概念，量词的辖域，约束变元、自由变元的辨认。 2．领会 谓词逻辑中的合式公式（Wff）的递归定义、自然语言翻译成谓词公式，化公式 为前束范式，谓词逻辑的推理理论、证明方法、推理规则。命题公式扩充到谓词逻辑 中的联系与区别。 3．简单应用 利用谓词逻辑解决简单的论证应用题。 四、主要内容 第 2 章 谓词逻辑 在 Ls 中，把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研 究以原子命题为基本单位的复合命题之间的逻辑关系和推理。这样，有些推理用命题 逻辑就难以确切地表示出来。例如，著名的亚里士多德三段论苏格拉底推理： 所有的人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的
离散数学教案 根据常识，认为这个推理是正确的。但是，若用Ls来表示，设P、Q和R分别表 示这三个原子命题，则有 P,Q-R 然而，(P∧Q)一R并不是永真式，故上述推理形式又是错误的。一个推理，得出 矛盾的结论，问题在哪里呢？问题就在于这类推理中，各命题之间的逻辑关系不是体 现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构的 更深层次上。对此，Ls是无能为力的。所以，在研究某些推理时，有必要对原子命 题作进一步分析，分析出其中的个体词，谓词和量词，研究它们的形式结构的逻辑关 系、正确的推理形式和规则，这些正是谓词逻辑（简称为L)的基本内容。 2.1个体、谓词和量词 在印中，命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和 谓语两部分组成。在L印中，为揭示命题内部结构及其不同命题的内部结构关系，就 按照这两部分对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。 1,个体、谓词和命题的谓词形式 定义2.1.1在原子命题中，所描述的对象称为个体：用以描述个体的性质或个 体间关系的部分，称为谓词。 个体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明， 计算机，精神等。表示特定的个体，称为个体常元，以a,b,c.或带下标的ai,bi, ci.表示；表示不确定的个体，称为个体变元，以x,y,z.或xi,yi,zi.表示。 谓词，当与一个个体相联系时，它刻划了个体性质：当与两个或两个以上个体相 联系时，它刻划了个体之间的关系。表示特定谓词，称为谓词常元，表示不确定的谓 词，称为谓词变元，都用大写英文字母，如P,Q,R,.,或其带上、下标来表示。 在本书中，不对谓词变元作更多地讨论。 对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示 时，规定把小写字母写在大写字母右侧的圆括号()内。例如，在命题“张明是位大 学生”中，“张明”是个体，“是位大学生”是谓词，它刻划了“张明”的性质。设 S:是位大学生，c:张明，则“张明是位大学生”可表示为S(c),或者写成S(c): 张明是位大学生。又如，在命题“武汉位于北京和广州之间”中，武汉、北京和广州 是三个个体，而“.位于.和.之间”是谓词，它刻划了武汉、北京和广州之间的关 3
离散数学教案 3 根据常识，认为这个推理是正确的。但是，若用 Ls 来表示，设 P、Q 和 R 分别表 示这三个原子命题，则有 P，QR 然而，(P∧Q)→R 并不是永真式，故上述推理形式又是错误的。一个推理，得出 矛盾的结论，问题在哪里呢? 问题就在于这类推理中，各命题之间的逻辑关系不是体 现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构的 更深层次上。对此，Ls 是无能为力的。所以，在研究某些推理时，有必要对原子命 题作进一步分析，分析出其中的个体词，谓词和量词，研究它们的形式结构的逻辑关 系、正确的推理形式和规则，这些正是谓词逻辑（简称为 Lp）的基本内容。 2.1 个体、谓词和量词 在 Lp 中，命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和 谓语两部分组成。在 Lp 中，为揭示命题内部结构及其不同命题的内部结构关系，就 按照这两部分对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。 １.个体、谓词和命题的谓词形式 定义 2.1.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个 体间关系的部分，称为谓词。 个体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明， 计算机，精神等。表示特定的个体，称为个体常元，以 a，b，c.或带下标的 ai，bi， ci.表示；表示不确定的个体，称为个体变元，以 x，y，z.或 xi，yi，zi.表示。 谓词，当与一个个体相联系时，它刻划了个体性质；当与两个或两个以上个体相 联系时，它刻划了个体之间的关系。表示特定谓词，称为谓词常元，表示不确定的谓 词，称为谓词变元，都用大写英文字母，如 P，Q，R，.，或其带上、下标来表示。 在本书中，不对谓词变元作更多地讨论。 对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示 时，规定把小写字母写在大写字母右侧的圆括号( )内。例如，在命题“张明是位大 学生”中，“张明”是个体，“是位大学生”是谓词，它刻划了“张明”的性质。设 S：是位大学生，c：张明，则“张明是位大学生”可表示为 S(c)，或者写成 S(c)： 张明是位大学生。又如，在命题“武汉位于北京和广州之间”中，武汉、北京和广州 是三个个体，而“.位于.和.之间”是谓词，它刻划了武汉、北京和广州之间的关
离散数学教案 系。设P:.位于.和.之间，a:武汉，b:北京，c:广州，则P(a,b,c):武汉 位于北京和广州之间。 定义2.1.2一个原子命题用一个谓词（如P)和n个有次序的个体常元（如a1, a2,.,an)表示成P(al,a2,.,an),称它为该原子命题的谓词形式或命题的谓 词形式。 应注意的是，命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变 动，否则真值会有变化。如上述例子中，P(b,a,c)是假。 2.原子谓词公式 原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的个 个体常元被替换成个体变元，如xl,x2,···,x,这样便得了一种关于命题结构的 新表达形式，称之为n元原子谓词。 定义2.1.3由一个谓词（如P)和n个体变元（如xl,x2,.,xn)组成的P(x1, x2,·,xn),称它为n元原子谓词或n元命题函数，简称n元谓词。而个体变元的 论述范围，称为个体域或论域。 当n=1时，称一元谓词：当n=2时，称为二元谓词，.。特别地，当n=0,称为 零元谓词。零元谓词是命题，这样命题与谓词就得到了统一。 元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成 为一个命题。但个体变元在哪些论域取特定的值，对命题的真值极有影响。例如，令 S(x):x是大学生。若x的论域为某大学的计算机系中的全体同学，则S(x)是真的： 若x的论域是某中学的全体学生，则S(x)是假的：若x的论域是某剧场中的观众， 且观众中有大学生也有非大学生的其它观众，则S(x)是真值是不确定的。 通常，把一个n元谓词中的每个个体的论域综合在一起作为它的论域，称为n元 谓词的全总论域。定义了全总论域，为深入研究命题提供了方便。当一个命题没有指 明论域时，一般都从全总论域作为其论域。而这时又常常要采用一个谓词如P(x)来 限制个体变元x的取值范围，并把P(x)称为特性谓词。 3.量词 利用元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题， 例如S(x)表示x是大学生，而x的个体域为某单位的职工，那么S(x)可表示某单位 职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在
离散数学教案 4 系。设 P：.位于.和.之间，a：武汉，b：北京，c：广州，则 P(a，b，c)：武汉 位于北京和广州之间。 定义 2.1.2 一个原子命题用一个谓词(如 P)和 n 个有次序的个体常元(如 a1， a2，.，an)表示成 P(a1，a2，.，an)，称它为该原子命题的谓词形式或命题的谓 词形式。 应注意的是，命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变 动，否则真值会有变化。如上述例子中，P(b,a,c)是假。 ２.原子谓词公式 原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的 n 个 个体常元被替换成个体变元，如 x1,x2,···,xn，这样便得了一种关于命题结构的 新表达形式，称之为 n 元原子谓词。 定义 2.1.3 由一个谓词(如 P)和 n 个体变元(如 x1，x2，.，xn)组成的 P(x1， x2，.，xn)，称它为 n 元原子谓词或 n 元命题函数，简称 n 元谓词。而个体变元的 论述范围，称为个体域或论域。 当 n=1 时，称一元谓词；当 n=2 时，称为二元谓词，.。特别地，当 n=0，称为 零元谓词。零元谓词是命题，这样命题与谓词就得到了统一。 n 元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成 为一个命题。但个体变元在哪些论域取特定的值，对命题的真值极有影响。例如，令 S(x)：x 是大学生。若 x 的论域为某大学的计算机系中的全体同学，则 S(x)是真的； 若 x 的论域是某中学的全体学生，则 S(x)是假的；若 x 的论域是某剧场中的观众， 且观众中有大学生也有非大学生的其它观众，则 S(x)是真值是不确定的。 通常，把一个 n 元谓词中的每个个体的论域综合在一起作为它的论域，称为 n 元 谓词的全总论域。定义了全总论域，为深入研究命题提供了方便。当一个命题没有指 明论域时，一般都从全总论域作为其论域。而这时又常常要采用一个谓词如 P(x)来 限制个体变元 x 的取值范围，并把 P(x)称为特性谓词。 ３.量词 利用 n 元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题， 例如 S(x)表示 x 是大学生，而 x 的个体域为某单位的职工，那么 S(x)可表示某单位 职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在
离散数学教案 L印中，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，即量词， 其定义如下： 定义2.1.4 ①符号V称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、 “一切”等词语：x称为全称量词，称x为指导变元。 ②符号称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一 些”、“某个”等词语：x称为存在量词，x称为指导变元。 ③符号！称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语： !x称为存在唯一量词，称x为指导变元。 全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家Fray引 入的，有了量词之后，用逻辑符号表示命题的能力大大加强了。 例2.1.1试用量词、谓词表示下列命题： ①所有大学生都热爱祖国： ②每个自然数都是实数： ③一些大学生有远大理想： ④有的自然数是素数。 解令S(x):x是大学生，L(x):x热爱祖国，N(x):x是自然数，R(x):x是实数 I(x):x有远大理想，P(x):x是素数。 则例中各命题分别表示为： ①（付x)(S(x)→L(x) ②(x)(N(x)→R(x)】 ③（白x)(S(x)AI(x) ④（臼x)(N(x)AP(x) 在该例的解答中，由于命题中没有指明个体域，这便意味着各命题是在全总论域 中讨论，因而都使用了特性谓词，如S(x)、N(x)。而且还可以看出，量词与特性谓 词的搭配还有一定规律，即全称量词后跟一个条件式，而特性谓词作为其前件出现： 存在量词后跟一个合取式，特性谓词作为一个合取项出现。 如果在解答时，指明了个体域，便不用特性谓词，例如在①、③中令个体域为全 体大学生，②和④中的个体域为全部自然数，则可符号化为： ①(x)L(x) ②(Hx)R(x)
离散数学教案 5 Lp 中，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，即量词， 其定义如下： 定义 2.1.4 ①符号称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、 “一切”等词语；x 称为全称量词，称 x 为指导变元。 ②符号称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一 些”、“某个”等词语；x 称为存在量词，x 称为指导变元。 ③符号!称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语； !x 称为存在唯一量词，称 x 为指导变元。 全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家 Fray 引 入的，有了量词之后，用逻辑符号表示命题的能力大大加强了。 例 2.1.1 试用量词、谓词表示下列命题： ① 所有大学生都热爱祖国； ② 每个自然数都是实数； ③ 一些大学生有远大理想； ④ 有的自然数是素数。 解 令 S(x)：x 是大学生，L(x)：x 热爱祖国，N(x)：x 是自然数，R(x)：x 是实数， I(x)：x 有远大理想，P(x)：x 是素数。 则例中各命题分别表示为： ①(x)(S(x)→L(x)) ②(x)(N(x)→R(x)) ③(x)(S(x)I(x)) ④(x)(N(x)P(x)) 在该例的解答中，由于命题中没有指明个体域，这便意味着各命题是在全总论域 中讨论，因而都使用了特性谓词，如 S(x)、N(x)。而且还可以看出，量词与特性谓 词的搭配还有一定规律，即全称量词后跟一个条件式，而特性谓词作为其前件出现； 存在量词后跟一个合取式，特性谓词作为一个合取项出现。 如果在解答时，指明了个体域，便不用特性谓词，例如在①、③中令个体域为全 体大学生，②和④中的个体域为全部自然数，则可符号化为： ①(x)L(x) ②(x)R(x)