离散数学第二章谓词逻辑ppt课件

1、n命题逻辑的局限性：命题逻辑的局限性：n 在命题逻辑中，命题是命题演算的根本单位，在命题逻辑中，命题是命题演算的根本单位，不不n再对原子命题进展分解，因此无法研讨命题的内部再对原子命题进展分解，因此无法研讨命题的内部结结n构、成分及命题之间的内在联络，甚至无法处置一构、成分及命题之间的内在联络，甚至无法处置一些些n简单而又常见的推理过程。简单而又常见的推理过程。 第二章第二章 谓谓 词词 逻逻 辑辑 例如，以下推理：例如，以下推理： 一切的人都是要死的。一切的人都是要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。苏格拉底是要死的。 众所周知，这是真命题。但在命题逻辑中众所周知，这是真

2、命题。但在命题逻辑中,假设假设用用P，Q，R表示以上三个命题，那么上述推理过程表示以上三个命题，那么上述推理过程为：为：PQR。借助命题演算的推理实际不能证明其。借助命题演算的推理实际不能证明其为重言式。为重言式。 第二章第二章 谓谓 词词 逻逻 辑辑缘由：命题逻辑不能将命题之间的内在联络和数量缘由：命题逻辑不能将命题之间的内在联络和数量关系反映出来。关系反映出来。处理方法：将命题进展分解。处理方法：将命题进展分解。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示2.2 命题函数与量词命题函数与量词2.3 谓词公式与翻译谓词公式与翻译2.4 变元的约束变元的约束2

3、.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2.6 前束范式前束范式2.7 谓词演算的推理实际谓词演算的推理实际 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示 在谓词逻辑中，可将原子命题划分为个在谓词逻辑中，可将原子命题划分为个体和谓体和谓词两部分。词两部分。个体：可以独立存在的详细事物的或笼统的个体：可以独立存在的详细事物的或笼统的概念。概念。例如，电子计算机、李明、玫瑰花、黑板、例如，电子计算机、李明、玫瑰花、黑板、实数、实数、 中国、思想、唯物主义等，客体也可称中国、思想、唯物主义等，客体也可称之为之为 主语。主语。谓词：用来刻划个体的性质或个体

4、之间的相谓词：用来刻划个体的性质或个体之间的相互关系互关系 的词。的词。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示例如在下面命题中：例如在下面命题中： 1张明是个劳动模范。张明是个劳动模范。 2李华是个劳动模范。李华是个劳动模范。 刻划个体的性质刻划个体的性质 3王红是个大学生。王红是个大学生。 4小李比小赵高小李比小赵高2cm。 5点点a在在b与与c之间。之间。 刻划个体之间的相互关系刻划个体之间的相互关系 6阿杜与阿寺同岁。阿杜与阿寺同岁。“是个劳动模范、是个劳动模范、“是个大学生、是个大学生、“比比高高2cm、 “在在与与之间之间 “与与同岁都是谓词。

5、同岁都是谓词。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示n刻划一个个体性质的词称之为一元谓词，刻划刻划一个个体性质的词称之为一元谓词，刻划n个个体之间关系的词称之为个个体之间关系的词称之为n元谓词。元谓词。n普通我们用大写英文字母表示谓词，用小写英普通我们用大写英文字母表示谓词，用小写英文字母表示个体称号。文字母表示个体称号。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示例如，将上述谓词分别记作大写字母例如，将上述谓词分别记作大写字母F、G、H、 R、S，那么上述命题可表示为：，那么上述命题可表示为： (1) F(a) a：张

6、明：张明 (2) F(b) b：李华：李华 (3) G(c) c：王红：王红 (4) H(s,t) s：小李：小李 t：小赵：小赵 (5) R(a,b,c) (6) S(a,b) a:阿杜阿杜 b:阿寺阿寺其中，其中，(1)、(2)、(3)为一元谓词，为一元谓词，(4)、(6)为二元谓为二元谓词，词，(5)为三元谓词。为三元谓词。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示留意留意:(1)单独一个谓词并不是命题，在谓词字母后填单独一个谓词并不是命题，在谓词字母后填 上个体所得到的式子称之为谓词方式。上个体所得到的式子称之为谓词方式。(2)在谓词方式中，假设个体

7、确定，那么在谓词方式中，假设个体确定，那么A(a1，a2，.，an)就变成了命题。就变成了命题。 (3)在多元谓词表达式中，个体字母出现的先后在多元谓词表达式中，个体字母出现的先后 次序与事先商定有关，普通不可以随意交换次序与事先商定有关，普通不可以随意交换 位置。位置。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示小结：本节将原子命题进展分解，分为个体小结：本节将原子命题进展分解，分为个体和谓词两部分。进而引见了个体和谓词、一和谓词两部分。进而引见了个体和谓词、一元谓词和元谓词和n元谓词的概念。重点掌握一元谓元谓词的概念。重点掌握一元谓词和词和n元谓词的概念。

8、元谓词的概念。 第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示2.2.1 命题函数命题函数2.2.2 量词量词 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词2.2.1 命题函数命题函数例如：设谓词例如：设谓词H表示表示“是劳动模范，是劳动模范， a表表示个体示个体张明，张明，b表示个体李华，表示个体李华，c表示个体这只老虎，表示个体这只老虎，那么那么H(a) 、 H(b)、H(c)表示三个不同的命题，表示三个不同的命题，但它们但它们有一个共同的方式，即有一个共同的方式，即H(x)。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与

9、量词命题函数与量词 普通地，普通地， H(x)表示个体表示个体x具有性质具有性质H。这里。这里x表示抽表示抽象的或泛指的个体，称为个体变元，常用小写英文字母象的或泛指的个体，称为个体变元，常用小写英文字母x,y,z, 表示。相应地，表示详细或特定的个体的词称表示。相应地，表示详细或特定的个体的词称为个体常元，常用小写英文字母为个体常元，常用小写英文字母a,b,c, 表示。表示。 同理，个体变元同理，个体变元x,y具有关系具有关系L，记作，记作L(x,y)；个体；个体变元变元x,y,z具有关系具有关系A，记作，记作A(x,y,z)。 H(x)、L(x,y) 、A(x,y,z)本身并不是一个命题。

10、只需本身并不是一个命题。只需用特定的个体取代个体变元用特定的个体取代个体变元x,y,z后，它们才成为命题。后，它们才成为命题。我们称我们称H(x)、L(x,y) 、A(x,y,z)为命题函数。为命题函数。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词定义定义:由一个谓词由一个谓词H和和n个个体变元组成的表达式个个体变元组成的表达式 H(x1,x2 , , xn)称为称为n元简单命题函数。元简单命题函数。 由定义可知，由定义可知，n元谓词就是有元谓词就是有n个个体变元个个体变元的命题函数。当的命题函数。当n=0时，称为时，称为0元谓词。因此，元谓词。因此，普通情况下，

11、命题函数不是命题；特殊情况普通情况下，命题函数不是命题；特殊情况0元元谓词就变成一个命题。谓词就变成一个命题。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词复合命题函数：由一个或几个简单命题函数以及逻复合命题函数：由一个或几个简单命题函数以及逻辑结合词组合而成的表达式。辑结合词组合而成的表达式。例例1：假设：假设x的学习好，那么的学习好，那么x的任务好。的任务好。 设设S(x):x学习好；学习好；W(x):x任务好任务好 那么有那么有S(x) W(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词例例2：将以下命题用：将以下命题用0元谓词

12、符号化。元谓词符号化。(1) 2是素数且是偶数。是素数且是偶数。(2) 假设假设2大于大于3，那么，那么2大于大于4。(3) 假设张明比李民高，李民比赵亮高，那么张明比假设张明比李民高，李民比赵亮高，那么张明比赵亮高。赵亮高。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词解：解：(1) 设设F(x): x是素数是素数. G(x): x是偶数是偶数. 那么命题符号化为：那么命题符号化为： F(2)G(2) (2) 设设L(x,y) ：x大于大于y. 那么命题符号化为：那么命题符号化为： L(2,3) L(2,4) (3) 设设 H(x,y): x比比y高高. a:张明

13、张明 b:李民李民 c：赵亮：赵亮 那么命题符号化为：那么命题符号化为： H(a,b)H(b ,c)H(a,c) 留意：命题函数中，个体变元在哪些范围内取特定留意：命题函数中，个体变元在哪些范围内取特定 的值，对命题的真值极有影响。的值，对命题的真值极有影响。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词例如：例如：H(x,y)H(y ,z)H(x,z) 假设假设H(x,y)解释为解释为: x大于大于y，当，当x,y,z都在实数中取都在实数中取值时，那么这个式子表示值时，那么这个式子表示“假设假设x大于大于y 且且y 大大于于z，那么，那么x大于大于z 。这是一个永

14、真式。这是一个永真式。 假设假设H(x,y)解释为解释为: “x是是y的儿子，的儿子， 当当x,y,z都都指人时，那么这个式子表示指人时，那么这个式子表示“假设假设x为为y的儿子的儿子 且且y 是是z的儿子，那么的儿子，那么x是是z的儿子的儿子 。这是一。这是一个永假式。个永假式。 假设假设H(x,y)解释为解释为: “x距距y10米，当米，当x,y,z为平为平面上的点，那么这个式子表示面上的点，那么这个式子表示“假设假设x距距y10米米且且y距距z10米，那么米，那么x距距z10米米 。这个命题的真。这个命题的真值将由值将由x,y,z的详细位置而定，它能够是的详细位置而定，它能够是1，也，也

15、能够是能够是0。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词n在命题函数中，个体变元的取值范围称为在命题函数中，个体变元的取值范围称为个体域，又称之为论域。个体域可以是有个体域，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。限事物的集合，也可以是无限事物的集合。n全总个体域：宇宙间一切事物组成的个体全总个体域：宇宙间一切事物组成的个体域称为全总个体域。域称为全总个体域。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词2.2.2 量词量词量词：全称量词量词：全称量词()和存在量词和存在量词()1.全称量词全称量词 对日常

16、言语中的对日常言语中的“一切、一切、“一切、一切、“凡是凡是 、“每一个、每一个、“恣意等词，用符号恣意等词，用符号“ 表示，表示， 表表示对个体域里的一切个体，示对个体域里的一切个体， F()表示个体域表示个体域里的一切个体具有性质里的一切个体具有性质F。 符号符号“称为全称量词。称为全称量词。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词例例3：在谓词逻辑中将以下命题符号化。：在谓词逻辑中将以下命题符号化。1凡是人都呼吸。凡是人都呼吸。 2每个学生都要参与考试。每个学生都要参与考试。3任何整数或是正的或是负的。任何整数或是正的或是负的。 第二章第二章 谓谓 词词

17、 逻逻 辑辑2.2 命题函数与量词命题函数与量词解解: (1) 当个体域为人类集合时：当个体域为人类集合时： 令令F(x): x呼吸。那么呼吸。那么1符号化为符号化为 xF(x). 当个体域为全总个体域时：当个体域为全总个体域时： 令令M(x): x是人。那么是人。那么1符号化为符号化为 x(M(x) F(x). 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词(2) 当个体域为全体学生的集合时：当个体域为全体学生的集合时： 令令P(x): x要参与考试。那么要参与考试。那么2符号化为符号化为 xP(x). 当个体域为全总个体域时：当个体域为全总个体域时： 令令S(x)

18、: x是学生。那么是学生。那么2符号化为符号化为 x(S(x) P(x). 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词(3) 当个体域为全体整数的集合时：当个体域为全体整数的集合时： 令令P(x): x是正的。是正的。N(x): x是负的。那么是负的。那么3符符号化为号化为 x(P(x)N(x) . 当个体域为全总个体域时：当个体域为全总个体域时： 令令I(x): x是整数。那么是整数。那么3符号化为符号化为 x(I(x)(P(x)N(x). 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词2.存在量词存在量词 对日常言语中的对日常言语中的

19、“有一个、有一个、“有的、有的、“存在着、存在着、“至少有一个、至少有一个、 “存在一些等词，用符号存在一些等词，用符号“ 表表示，示，表示存在个体域里的个体，表示存在个体域里的个体， F()表示表示存在个体域里的个体具有性质存在个体域里的个体具有性质F。 符号符号“称为存在量词。称为存在量词。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词例例4：在谓词逻辑中将以下命题符号化：在谓词逻辑中将以下命题符号化.1一些数是有理数。一些数是有理数。 2有些人活百岁以上。有些人活百岁以上。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词解解: (1)

20、令令Q(x): x是有理数。那么是有理数。那么1符号化为符号化为 Q(x)。 2当个体域为人类集合时：当个体域为人类集合时： 令令G(x): x活百岁以上。那么活百岁以上。那么2符号化为符号化为 xG(x)。 当个体域为全总个体域时：当个体域为全总个体域时： 令令M(x): x是人。那么是人。那么2符号化为符号化为 x(M(x) G(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词有时需求同时运用多个量词。有时需求同时运用多个量词。例例5：命题：命题“对恣意的对恣意的x,存在存在y, 使得使得x+y=5, 取个体域为实数集合，那么该命题符号化为取个体域为实数集合，

21、那么该命题符号化为 x y H(x,y). 其中其中H(x,y): x+y=5. 这是个真命题这是个真命题. 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词3. 运用量词时应留意的问题运用量词时应留意的问题1在不同的个体域，同一命题的符号化方式可在不同的个体域，同一命题的符号化方式可 能一样也能够不同。能一样也能够不同。2在不同的个体域，同一命题的真值能够一样在不同的个体域，同一命题的真值能够一样 也能够不同。也能够不同。(如，如，Rx表示表示x为大学生。如为大学生。如 果个体域为大学里的某个班级的学生，那么果个体域为大学里的某个班级的学生，那么 x Rx为真；假设个

22、体域为中学里的某个班级为真；假设个体域为中学里的某个班级 的学生，那么的学生，那么 x Rx为假。为假。) 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词3商定以后如不指定个体域，默以为全总商定以后如不指定个体域，默以为全总 个体域。对每个个体变元的变化范围个体域。对每个个体变元的变化范围,用用 特性谓词加以限制。特性谓词加以限制。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词特性谓词：限定个体变元变化范围的谓词。特性谓词：限定个体变元变化范围的谓词。普通而言，对全称量词，特性谓词常作蕴含普通而言，对全称量词，特性谓词常作蕴含的前件，如的前

23、件，如x(M(x) F(x)；对存在量词，；对存在量词，特性谓词常作合取项，如特性谓词常作合取项，如x(M(x) G(x)。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词(4)普通来说，当多个量词同时出现时，普通来说，当多个量词同时出现时， 它们的顺序不能随意互换。它们的顺序不能随意互换。 例如：在实数域上用例如：在实数域上用H(x,y)表示表示x+y=5，那么命题，那么命题“对于恣意的对于恣意的x，都，都存在存在y使得使得x+y=5可符号化为：可符号化为： x yH(x,y)，其真值为，其真值为1。假设互换。假设互换量词顺序后为：量词顺序后为： y xH(x,y)

24、 , 其真值其真值为为0。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词(5) 当个体域为有限集合时，如当个体域为有限集合时，如D=a1, a2 , an，对恣意谓词，对恣意谓词A(x)，有，有 xA(x)A(a1)A(a2)A(an ) xA(x)A(a1)A(a2)A(an ) 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词例例6：在谓词逻辑中将以下命题符号化。：在谓词逻辑中将以下命题符号化。1一切的人都长头发。一切的人都长头发。2有的人吸烟。有的人吸烟。3没有人登上过木星。没有人登上过木星。4清华大学的学生未必都是高素质的。清华大学的

25、学生未必都是高素质的。解：令解：令M(x): x是人。特性谓词是人。特性谓词1 令令F(x): x长头发。那么符号化为：长头发。那么符号化为： x(M(x) F(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词2 令令S(x): x吸烟。那么符号化为：吸烟。那么符号化为： x(M(x)S(x)3 令令D(x): x登上过木星。那么符号化为：登上过木星。那么符号化为： x(M(x)D(x)4令令Q(x):x是清华大学的学生。是清华大学的学生。H(x):x是高是高 素质的。那么符号化为：素质的。那么符号化为： x(Q(x) H(x) 第二章第二章 谓谓 词词 逻逻 辑

26、辑2.2 命题函数与量词命题函数与量词小结小结:本节引见了本节引见了n元谓词、命题函数、全元谓词、命题函数、全称量词和存在量词等概念。重点掌握全称量词和存在量词等概念。重点掌握全称量词和存在量词及量化命题的符号化。称量词和存在量词及量化命题的符号化。 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词2.3谓词公式与翻译谓词公式与翻译n元谓词元谓词A(x1，x2.xn) 称为谓词演算的原子称为谓词演算的原子公式。公式。定义：谓词演算的合式公式，可由下述各条定义：谓词演算的合式公式，可由下述各条组成组成:1原子公式是合式公式。原子公式是合式公式。2假设假设A 是合式公式，那

27、么是合式公式，那么( A)也是合式也是合式公式。公式。3假设假设A，B是合式公式，那么是合式公式，那么(A B)，(A B)，(A B)，(A B)也是合式公式。也是合式公式。4假设假设A是合式公式，是合式公式，x是是A中出现的任何中出现的任何变元变元,那么那么(x)A , (x)A，也是合式公式。，也是合式公式。5只需有限次运用只需有限次运用(1)(4)得到的公式是合得到的公式是合式公式。式公式。 第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译例例1：在谓词逻辑中将以下命题符号化：在谓词逻辑中将以下命题符号化.1凡正数都大于零。凡正数都大于零。2存在小于存在小于2的

28、素数。的素数。3没有不能表示成分数的有理数。没有不能表示成分数的有理数。4并不是一切参与考试的人都能获得好成果。并不是一切参与考试的人都能获得好成果。解：解：1令令F(x): x是正数。是正数。M(x):x大于零。大于零。 那么符号化为：那么符号化为： x(F(x)M(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译2令令E(x): x小于小于2。S(x):x是素数。那么符号化是素数。那么符号化为：为： x(E(x)S(x)真值为真值为0 3令令D(x): x是有理数。是有理数。F(x):x能表示成分数。能表示成分数。 那么符号化为：那么符号化为： x(D(x)

29、F(x) 或或 x(D(x) F(x)真值为真值为 4令令M(x)：x是人。是人。Q(x):x参与考试。参与考试。 H(x):x获得好成果。那么符号化为：获得好成果。那么符号化为： x(M(x)Q(x)H(x) 或或 x(M(x)Q(x) H(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译例例2：在谓词逻辑中将以下命题符号化：在谓词逻辑中将以下命题符号化. 1一切运发动都钦佩某些教练一切运发动都钦佩某些教练.2有些运发动不钦佩教练有些运发动不钦佩教练.设：设：L(x):x是运发动是运发动 J(y):y是教练是教练 A(x,y):x钦佩钦佩y(1) (x)(L(x

30、) y)(J(y)A(x,y)(2)x)(L(x) (y)(J(y)A(x,y) 第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译小结：本节引见了谓词合式公式的概念，重点小结：本节引见了谓词合式公式的概念，重点掌握谓词公式的翻译。掌握谓词公式的翻译。 第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译2.4.1变元的约束变元的约束定义定义:在谓词公式中，形如在谓词公式中，形如( x)P(x)和和( x)P(x)的部的部 分，称为谓词公式的分，称为谓词公式的x约束部分。约束部分。 ( x)P(x)或或( x)P(x)中的中的x叫做量词的指点变元叫做量

31、词的指点变元 或作用变元，或作用变元，P(x)称为相应量词的作用域或辖域。称为相应量词的作用域或辖域。 在在 x和和 x的辖域中，的辖域中，x的一切出现都称为约束出的一切出现都称为约束出 现，相应的现，相应的x称为约束变元称为约束变元; P(x)中除约束变元中除约束变元 以外出现的变元称为是自在变元。以外出现的变元称为是自在变元。 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束例例1： 1、 x( H(x,y)y(W(y) L(x,y,z) 2、 x( H(x)W(y) y( F(x) L(x,y,z) 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束阐明阐明

32、:(1)n元谓词公式元谓词公式A(x1，x2.xn) 中有中有n个自在变元，假个自在变元，假设对其中的设对其中的k(kn)个进展约束，那么构成了个进展约束，那么构成了n-k元元谓词；假设一个公式中没有自在变元出现，那么谓词；假设一个公式中没有自在变元出现，那么该公式就变成了一个命题。该公式就变成了一个命题。(2)一个公式的约束变元所运用的称号符号是无关紧一个公式的约束变元所运用的称号符号是无关紧要的，如要的，如(x)M(x)与与(y)M(y)意义一样。意义一样。 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束2.4.2 约束变元的换名与自在变元的代入约束变元的换名与自在变元的

33、代入 一个变元在同一个公式中既是自在出现又是约束出现，一个变元在同一个公式中既是自在出现又是约束出现，这样在了解上容易发生混淆。为了防止这种混乱，可对约这样在了解上容易发生混淆。为了防止这种混乱，可对约束变元进展换名。束变元进展换名。 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束换名规那么换名规那么: (对约束变元而言对约束变元而言对约束变元进展换名，使得一个变元在一个公式对约束变元进展换名，使得一个变元在一个公式中中只呈一种方式出现只呈一种方式出现(1)约束变元可以换名，其更改的变元称号范围是约束变元可以换名，其更改的变元称号范围是量词中的指点变元以及该量词作用域中所出现

34、的量词中的指点变元以及该量词作用域中所出现的该变元，公式的其他部分不变。该变元，公式的其他部分不变。(2)换名时一定要更改为作用域中没有出现的变元换名时一定要更改为作用域中没有出现的变元称号。称号。 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束例例1: x( P(x)R(x,y) L(x,y)换名为换名为t( P(t)R(t,y) L(x,y) 2：x( H(x,y)y(W(y) L(x,y,z)换名为换名为x( H(x,y)s(W(s) L(x,s,z) 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束代入规那么对自在变元而言代入规那么对自在变元而言对公式

35、中自在变元的更改称为代入对公式中自在变元的更改称为代入(1)对于谓词公式中的自在变元可以作代入，代入时对于谓词公式中的自在变元可以作代入，代入时需求对公式中出现该自在变元的每一处进展；需求对公式中出现该自在变元的每一处进展；(2)用以代入的变元与原公式中一切变元的称号不能用以代入的变元与原公式中一切变元的称号不能一样。一样。例：例：x( P(x)R(x,y) L(x,y) 对自在变元对自在变元y用用z来代入，得来代入，得x( P(x)R(x,z)L(x,z) 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束小结：本节引见了约束变元、自在变元的小结：本节引见了约束变元、自在变元的

36、 概念，重点掌握约束变元的换名与自在变元概念，重点掌握约束变元的换名与自在变元的代入。的代入。 第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束2.5.1谓词公式的等价和永真的概念谓词公式的等价和永真的概念定义：一个解释定义：一个解释I由下面由下面4部分组成：部分组成：1.非空个体域非空个体域DI；2.DI中部分特定元素中部分特定元素a、b， .；3.DI上的特定一些函数上的特定一些函数f、g， .；4. DI上特定谓词上特定谓词P、Q， .。见书见书P40例例2.4.1。 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式定义：给定恣

37、意的谓词公式定义：给定恣意的谓词公式A，其个体域为，其个体域为E，1对于对于A的一切解释，公式的一切解释，公式A都为真，那么称都为真，那么称A在在E上是永真的上是永真的(或有效的或有效的)。2假设对于假设对于A的一切解释，公式的一切解释，公式A都为假，那么都为假，那么称称A在在E上是永假的上是永假的(或不可满足的或不可满足的)。3假设至少存在着一种解释使得公式假设至少存在着一种解释使得公式A为真，那为真，那么称么称A在在E上是可满足的。上是可满足的。 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式定义：给定任何两个谓词公式定义：给定任何两个谓词公式

38、A、B，设它们，设它们有共同的个体域有共同的个体域E，假设对，假设对A和和B的任一组的任一组变元进展解释，所得命题的真值一样，那变元进展解释，所得命题的真值一样，那么称谓词公式么称谓词公式A和和B在在E上等价，并记为上等价，并记为A B。定义：给定任何两个谓词公式定义：给定任何两个谓词公式A、B，当且仅，当且仅当当A B是永真式时，称是永真式时，称“A蕴涵蕴涵B，记作，记作A B。 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式2.5.2 谓词演算的等价式和蕴涵式谓词演算的等价式和蕴涵式1、命题公式的推行、命题公式的推行在命题公式中成立的等价公式，

39、用谓词公式去代换在命题公式中成立的等价公式，用谓词公式去代换其中相应的命题变元，得到的公式依然成立其中相应的命题变元，得到的公式依然成立如：如： x( P(x)Q(x) x( P(x) Q(x) P(x) Q(x) P(x) Q(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式2、量词与、量词与 之间的关系之间的关系 xP(x) x P(x) xP(x) x P(x)证明：对个体域证明：对个体域 a1，a2，an， xP(x) (P(a1)P(a2)P(an) P(a1) P(a2) P(an) x P(x) 第二章第二章 谓谓 词词 逻逻 辑

40、辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式3、量词作用域的扩张与收缩、量词作用域的扩张与收缩量词作用域中假设有合取或析取项，且其中有一个量词作用域中假设有合取或析取项，且其中有一个是命题，那么可将该命题移至量词作用域之外。如：是命题，那么可将该命题移至量词作用域之外。如： xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式证明：当个体域为证明：当个体域为a1，a2，an ， xA(x)P (P(a1)P(a2)P(an)P)

41、(P(a1)P)(P(a2) P)(P(an)P) x(A(x)P) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式n量词作用域的扩张和收缩量词作用域的扩张和收缩n( xA(x)B x) (A(x) Bn(x)A(x) B) (x) (A(x)Bn(B (x)A(x)x)(B A(x)n(B (x)A(x) x(B A(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式例例1：xA(x，y)P(y) x(A(x，y)P(y)例例2：xy(P(x)Q(y ) ( x P(x) yQ(y) 第二章第二章

42、谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式例例1：xA(x，y)P(y) x(A(x，y)P(y)例例2：xy(P(x)Q(y ) ( x P(x) yQ(y)证明：证明：xy(P(x)Q(y ) xy(P(x) Q(y ) x (P(x) y Q(y ) xP(x)yQ(y ) x P(x) y Q(y ) x P(x) yQ(y) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式4、量词的分配、量词的分配设设A(x)、B(x)是恣意的含自在出现个体变是恣意的含自在出现个体变元元x的公式，那么的公式，那么(1)

43、x(A(x)B(x) x A(x) x B(x) (2) x(A(x)B(x) x A(x) x B(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式证明：对个体域证明：对个体域a1，a2，an x(A(x)B(x)(A(a1)B(a1) (A(an)B(an)(A(a1)A(a2)A(an)(B(a1)B(a2)B(an) xA(x)xB(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式(3) x(A(x)B(x) x A(x) x B(x)(4) x(A(x)B(x) x A(x) x B(

44、x) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式留意：逆方向不成立。留意：逆方向不成立。如如4式，式，xA(x) x B(x)x(A(x)B(x)不成立。不成立。举反例：设个体域是整数集合举反例：设个体域是整数集合 A(x)：x为奇数为奇数 ，B(x)：x为偶数，为偶数， 那么那么xA(x)xB(x)为真，但为真，但x(A(x)B(x)为假。为假。 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式(5) x (A(x) B(x) xA(x) xB(x)(6) x A(x) xB(x) x (A(x)

45、B(x) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式5、多个量词的运用、多个量词的运用 (1) xyP(x，y ) y xP(x，y ) (二者二者同义同义) (2) xyP(x，y ) y xP(x，y ) xyP(x，y ) x yP(x，y ) (3) yxP(x，y) xyP(x，y) (4) xyPx，y xyP(x，y) yxPx，y yxP(x，y) (5) yxPx，y yxP(x，y) 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式留意留意:上述蕴涵式逆方向均不成立。上述蕴涵式逆方

46、向均不成立。例：如例：如3中，设个体域为有理数集合，中，设个体域为有理数集合， P(x,y) ：x+y=0， 那么那么xy P(x,y)为真。为真。 但是，但是，y xP(x,y)为假。为假。 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式小结：本节引见了谓词演算的根本等价式和蕴涵式。小结：本节引见了谓词演算的根本等价式和蕴涵式。重点掌握谓词公式之间的等价演算。重点掌握谓词公式之间的等价演算。 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与谓词演算的等价式与蕴涵式蕴涵式定义定义:任何一个谓词公式任何一个谓词公式A，假设具有如下方式：

47、，假设具有如下方式： (x1) (x2) (xn)B， 其中其中能够是量词能够是量词 或量词或量词 ，xii=1， n 是个体变元，是个体变元，B是不含量词的谓词公式，那么是不含量词的谓词公式，那么称称 A是前束范式。是前束范式。阐明：前束范式的量词均在全式的开头阐明：前束范式的量词均在全式的开头,它们的作用它们的作用 域延伸到整个公式的末尾。域延伸到整个公式的末尾。 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式 例例: x y(F(x)G(y) H(x,y) x y(F(x,y)G(y,z) x H(x,y,z) 定理：任何一个谓词公式，均和一个前束范定理：任何一个谓词公式，

48、均和一个前束范 式等价。式等价。 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式前束范式的求法：前束范式的求法：第一步：否认深化。即利用量词转化公式，把否认第一步：否认深化。即利用量词转化公式，把否认结合词深化到命题变元和谓词填式的前面。结合词深化到命题变元和谓词填式的前面。第二步：改名。即利用换名规那么、代入规那么改第二步：改名。即利用换名规那么、代入规那么改换一换一些变元的称号，以便消除混乱。些变元的称号，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。把量词移到前面。这样便可求出与公式等价的前束范式。这样

49、便可求出与公式等价的前束范式。 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式例例: :求以下公式的前束范式。求以下公式的前束范式。),(),()(),()(),()()6(),()()()(),()()5()()()()()4()()()()() 3()()()()()2()()()()() 1 (yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFx 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式n解解:)()()()()()()()()()()() 1 (量词分配量词转换律xGxFxxGxxFxxGxxFx)(

50、)()()()()()()()()()()()()()()()()()()()2(辖域扩张辖域扩张换名量词转换律yGxFyxyGyxFxyGyxFxxGxxFxxGxxFx 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式 )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()(),()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(辖域扩张辖域扩张辖域扩张换名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFy

51、xztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFx 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式n ),(),()(),()(),()(),(),()(),()(),()(),(),()(),()(),()()(),(),()(),()(),()()6(yxBxyAyyxByxyxAyxyxBxyAyyxByxyxAyxyxBxyAyyxByxyxAyxyxBxyAyyxByxyxAyx 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式 ),(),(),(),()()()()()(,

52、(),()(),()(),()(),(),()(),()(),()()6(zuBuzAvuByxAzvuyxzuBuzAzvuBvuyxAyxyxBxyAyyxByxyxAyx换名续 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式阐明：阐明：1.等价演算的顺序不同，使得前束范式不独一。等价演算的顺序不同，使得前束范式不独一。2.一个谓词公式的前束范式的各指点变元应是各不一个谓词公式的前束范式的各指点变元应是各不一样的，原来在谓词公式中自在出现的个体变元一样的，原来在谓词公式中自在出现的个体变元在前束范式中还应是自在出现。在前束范式中还应是自在出现。小结：本节引见了谓词公式前束范式

53、的概念和求法。小结：本节引见了谓词公式前束范式的概念和求法。 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式2.7.1推理规那么推理规那么在谓词演算中，推理的方式构造仍为在谓词演算中，推理的方式构造仍为 H1 H2 H3 . HnC。假设假设 H1 H2 H3 . HnC是永真式，那么称是永真式，那么称由前由前提提H1,H2,H3,Hn逻辑的推出结论逻辑的推出结论C，但在谓，但在谓词词逻辑中逻辑中, H1,H2,H3,.,Hn , C均为谓词公式。均为谓词公式。命题演算中的推理规那么，可在谓词推理实命题演算中的推理规那么，可在谓词推理实际中运用。际中运用。 第二章第二章 谓谓 词

54、词 逻逻 辑辑2.7 谓词演算的推理实际谓词演算的推理实际与量词有关的四条重要推理规那么：与量词有关的四条重要推理规那么：1、全称量词消去规那么、全称量词消去规那么US规那么规那么2、全称量词产生规那么、全称量词产生规那么UG规那么规那么3、存在量词消去规那么、存在量词消去规那么ES规那么规那么4、存在量词产生规那么、存在量词产生规那么EG规那么规那么留意：只能对前束范式适用上述规那么。留意：只能对前束范式适用上述规那么。 第二章第二章 谓谓 词词 逻逻 辑辑2.7 谓词演算的推理实际谓词演算的推理实际1. 全称指定规那么全称指定规那么 US ： x A(x) A(c) x A(x) A(y)

55、 运用此规那么时要留意：运用此规那么时要留意： 1x是是A(x)中的自在变元；中的自在变元； 2c是个体域中恣意个体常元；是个体域中恣意个体常元；3y为恣意不在为恣意不在A(x)中约束出现的个体变元。中约束出现的个体变元。 第二章第二章 谓谓 词词 逻逻 辑辑2.7 谓词演算的推理实际谓词演算的推理实际例：设例：设F(x，y)：xy ， x、y的个体域为实数的个体域为实数集合集合 ，令，令A(x) y F(x，y)，那么那么x A(x) x y F(x，y) , 该式真值为该式真值为1。假设运用假设运用US得得y F(y，y) ，那么是错误的，那么是错误的，正确的做法是换成正确的做法是换成y

56、F(z，y) 第二章第二章 谓谓 词词 逻逻 辑辑2.7 谓词演算的推理实际谓词演算的推理实际2.全称推行规那么全称推行规那么UG： A(y) x A(x) 运用此规那么时留意运用此规那么时留意: (1) y在在A(y)中自在出现，且中自在出现，且y取任何值时取任何值时A均均为真；为真； (2) 取代取代y的的x不在不在A(y)中约束出现。中约束出现。 第二章第二章 谓谓 词词 逻逻 辑辑2.7 谓词演算的推理实际谓词演算的推理实际例：设例：设F(x，y)：xy ， x、y的个体域为实数的个体域为实数集合集合 ，令，令A(y) x F(x，y)，该式真值为，该式真值为1，假设运用假设运用UG规

57、那么取规那么取x替代替代y得得x x F(x，x) ，那么，那么是错误的，正确的做法是换成是错误的，正确的做法是换成z x F(x，z) 。 第二章第二章 谓谓 词词 逻逻 辑辑2.7 谓词演算的推理实际谓词演算的推理实际3.存在指定规那么存在指定规那么(ES): x A(x) A(c)留意：留意：c是个体域中的某些个体，是个体域中的某些个体，c并不具有恣意性。并不具有恣意性。运用此规那么时应留意：运用此规那么时应留意：1c是使是使A为真的特定的个体常元，且未在为真的特定的个体常元，且未在A(x)中中 出现过；出现过；2假设假设A(x)中有其他自在变元出现，且中有其他自在变元出现，且x是随其是随其 他自在变元变化的，那么不能运用此规那么。他自在变元变化