《离散数学第二章谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章谓词逻辑.ppt（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、n命题逻辑的局限性命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本单位，不在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法研究命题的内部结再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的推理过程。简单而又常见的推理过程。第二章第二章 谓谓 词词 逻逻 辑辑1 例如，下列推理：例如，下列推理：所有的人都是要死的。所有的人都是要死的。苏格拉底是人。苏格拉底是人。苏格拉底是要死的。苏格拉底是要死的。众所周知，这是真命题。但在命题逻辑中众所周知，这是真命题。但在命题逻辑中
2、,如果如果用用P，Q，R表示以上三个命题，则上述推理过程为：表示以上三个命题，则上述推理过程为：（PQ）R。借助命题演算的推理理论不能。借助命题演算的推理理论不能证明其证明其为重言式为重言式。第二章第二章 谓谓 词词 逻逻 辑辑2原因：命题逻辑不能将命题之间的内在联系和数量原因：命题逻辑不能将命题之间的内在联系和数量关系反映出来。关系反映出来。解决办法：将命题进行分解。解决办法：将命题进行分解。第二章第二章 谓谓 词词 逻逻 辑辑32.1 谓词的概念与表示谓词的概念与表示2.2 命题函数与量词命题函数与量词2.3 谓词公式与翻译谓词公式与翻译2.4 变元的约束变元的约束2.5 谓词演算的等价式
3、与蕴含式谓词演算的等价式与蕴含式2.6 前束范式前束范式2.7 谓词演算的推理理论谓词演算的推理理论 第二章第二章 谓谓 词词 逻逻 辑辑42.1 谓词的概念与表示谓词的概念与表示 在谓词逻辑中，可将在谓词逻辑中，可将原子命题原子命题划分为划分为个体个体和和谓谓词词两部分。两部分。个体个体：可以独立存在的具体事物的或抽象的概念。：可以独立存在的具体事物的或抽象的概念。例例如，电子计算机、李明、玫瑰花、黑板、实数、如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也可称之为中国、思想、唯物主义等，客体也可称之为 主语。主语。谓词：谓词：用来刻划个体的性质或个体之间的相互关系用
4、来刻划个体的性质或个体之间的相互关系 的词。的词。第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示5例如在下面命题中：例如在下面命题中：（1）张明是个劳动模范。）张明是个劳动模范。（2）李华是个劳动模范。）李华是个劳动模范。刻划个体的性质刻划个体的性质 （3）王红王红是个大学生。是个大学生。（4）小李比小赵高小李比小赵高2cm。（5）点）点a在在b与与c之间。之间。刻划个体之间的相互关系刻划个体之间的相互关系 （6）阿杜与阿寺同岁。阿杜与阿寺同岁。“是是个个劳劳动动模模范范”、“是是个个大大学学生生”、“比比高高2cm”、“在在与与之间之间”“与与同岁同岁”都是都是
5、谓词。谓词。第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示6n刻刻划划一一个个个个体体性性质质的的词词称称之之为为一一元元谓谓词词，刻刻划划n个个体之间关系个个体之间关系的词称之为的词称之为n元谓词元谓词。n一般我们用大写英文字母表示一般我们用大写英文字母表示谓词，谓词，用小写英用小写英文字母表示个体名称。文字母表示个体名称。第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示7例如，例如，将上述谓词分别记作大写字母将上述谓词分别记作大写字母F、G、H、R、S，则上述命题可表示为：，则上述命题可表示为：(1)F(a)a：张明张明 (2)F(
6、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 谓词的概念与表示谓词的概念与表示8注意注意:(1)单独一个谓词并不是命题，在谓词字母后填单独一个谓词并不是命题，在谓词字母后填 上个体所得到的式子称之为谓词形式。上个体所得到的式子称之为谓词形式。(2)在谓词形式中，若个体确定，则在谓词形式中，若个体确定，则A(a1，a2，
7、.，an)就变成了命题。就变成了命题。(3)在多元谓词表达式中，个体字母出现的先后在多元谓词表达式中，个体字母出现的先后 次序与事先约定有关，一般不可以随意交换次序与事先约定有关，一般不可以随意交换 位置。位置。第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓词的概念与表示谓词的概念与表示9小结：本节将原子命题进行分解，分为个体小结：本节将原子命题进行分解，分为个体和谓词两部分。进而介绍了个体和谓词、一和谓词两部分。进而介绍了个体和谓词、一元谓词和元谓词和n元谓词的概念。重点掌握一元谓元谓词的概念。重点掌握一元谓词和词和n元谓词的概念。元谓词的概念。第二章第二章 谓谓 词词 逻逻 辑辑2.1 谓
8、词的概念与表示谓词的概念与表示102.2.1 命题函数命题函数2.2.2 量词量词 第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词112.2.1 命题函数命题函数例如：设谓词例如：设谓词H表示表示“是劳动模范是劳动模范”，a表示个表示个体体张明，张明，b表示个体表示个体李华，李华，c表示个体这只老虎，表示个体这只老虎，那么那么H(a)、H(b)、H(c)表示三个不同的命题，但它们表示三个不同的命题，但它们有一个共同的形式，即有一个共同的形式，即H(x)。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词12 一般地，一般地，H(x)表示个体表示个
9、体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 命题函数与量词命题函数与量词13定义定义:由一个谓词由一个谓词H和和n个个体变元组成的表达式个个体变元组成的表达式 H(x1,x2,xn)称为称为n元元简单命题函数。简单命题函数。由定义可知，由定义可知，n元谓词就是有元谓词就是有n个个体变元个个体变元的的命题函数。命题函数。当当n=0时，称为时，称为0元谓词。元谓词。因此，因此，一般情况下，一般情况下，命题函数不是命题；特殊情况命题函数不是命题；特殊情况0元元谓词就变成
11、一个命题。谓词就变成一个命题。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词14复合命题函数复合命题函数：由一个或几个简单命题函数以及逻：由一个或几个简单命题函数以及逻辑联结词组合而成的表达式。辑联结词组合而成的表达式。例例1：若若x的学习好，则的学习好，则x的工作好。的工作好。设设S(x):x学习好；学习好；W(x):x工作好工作好 则有则有S(x)W(x)第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词15例例2：将下列命题用：将下列命题用0元谓词符号化。元谓词符号化。(1)2是素数且是偶数。是素数且是偶数。(2)如果如果2大于大于3，则，
12、则2大于大于4。(3)如果如果张明比李民高，李民比赵亮高，则张明比赵张明比李民高，李民比赵亮高，则张明比赵亮高。亮高。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词16解：解：(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:张张明明 b:李李民民 c：赵赵亮亮 则则 命命 题题 符符 号号 化化 为为：H(a,b)H(b,c)H(a,c)注意：注意：命题函数中，命题函数中
13、，个体变元在哪些范围内取特定个体变元在哪些范围内取特定 的值，对命题的真值极有影响。的值，对命题的真值极有影响。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词17例如：例如：H(x,y)H(y,z)H(x,z)n若若H(x,y)解释为解释为:x大于大于y，当，当x,y,z都在实数中都在实数中取值时，则这个式子表示取值时，则这个式子表示“若若x大于大于y 且且y 大于大于z，则，则x大于大于z”。这是一个永真式。这是一个永真式。如果如果H(x,y)解释为解释为:“x是是y的儿子的儿子”，当当x,y,z都都指人时，则这个式子表示指人时，则这个式子表示“若若x为为y的儿子的
14、儿子 且且y 是是z的儿子，则的儿子，则x是是z的儿子的儿子”。这是一个永假。这是一个永假式。式。如果如果H(x,y)解释为解释为:“x距距y10米米”，当，当x,y,z为平为平面上的点，则这个式子表示面上的点，则这个式子表示“若若x距距y10米且米且y距距z10米，则米，则x距距z10米米”。这个命题的真值将。这个命题的真值将由由x,y,z的具体位置而定，它可能是的具体位置而定，它可能是1，也可能是，也可能是0。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词18n在命题函数中，个体变元的取值范围称为在命题函数中，个体变元的取值范围称为个体域个体域，又称之为论域。个体
15、域可以是有，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。限事物的集合，也可以是无限事物的集合。n全总个体域：全总个体域：宇宙间一切事物组成的个体宇宙间一切事物组成的个体域称为域称为全总个体域。全总个体域。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词192.2.2 量词量词量词量词：全称量词：全称量词()和存在量词和存在量词()1.全称量词全称量词 对日常语言中的对日常语言中的“一切一切”、“所有所有”、“凡是凡是”、“每一个每一个”、“任意任意”等词，等词，用符号用符号“”表示表示，表表示对个体域里的所有个体，示对个体域里的所有个体，F()表示
16、个体域表示个体域里的所有个体具有性质里的所有个体具有性质F。符号符号“”称为称为全称量词。全称量词。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词20例例3：在谓词逻辑中将下列命题符号化。在谓词逻辑中将下列命题符号化。（1）凡是人都呼吸。）凡是人都呼吸。（2）每个学生都要参加考试。）每个学生都要参加考试。（3）任何整数或是正的或是负的。）任何整数或是正的或是负的。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词21解解:(1)当个体域为当个体域为人类集合人类集合时：时：令令F(x):x呼吸。则（呼吸。则（1）符号化为）符号化为 xF(x).当个
17、体域为当个体域为全总个体域全总个体域时：时：令令M(x):x是人。则（是人。则（1）符号化为）符号化为 x(M(x)F(x).第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词22(2)当个体域为当个体域为全体学生的集合全体学生的集合时：时：令令P(x):x要参加考试。则（要参加考试。则（2）符号化为）符号化为 xP(x).当个体域为当个体域为全总个体域全总个体域时：时：令令S(x):x是学生。则（是学生。则（2）符号化为）符号化为 x(S(x)P(x).第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词23(3)当个体域为当个体域为全体整数的集合全
18、体整数的集合时：时：令令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 命题函数与量词命题函数与量词242.存在量词存在量词 对日常语言中的对日常语言中的“有一个有一个”、“有的有的”、“存在存在着着”、“至少有一个至少有一个”、“存在一些存在一些”等词，等词，用符号用符号“”表表示示，表示存在个体域里的个体，表示存在个体域里的个体，F()表示表示存在个体
19、域里的个体具有性质存在个体域里的个体具有性质F。符号符号“”称为称为存在量词。存在量词。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词25例例4：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）一些数是有理数。）一些数是有理数。（2）有些人活百岁以上。）有些人活百岁以上。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词26解解:(1)令令Q(x):x是有理数。则（是有理数。则（1）符号化为）符号化为 Q(x)。（2）当个体域为）当个体域为人类集合人类集合时：时：令令G(x):x活百岁以上。则（活百岁以上。则（2）符号化为）符号化
20、为 xG(x)。当个体域为当个体域为全总个体域全总个体域时：时：令令M(x):x是人。则（是人。则（2）符号化为）符号化为 x(M(x)G(x)第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词27有时需要同时使用多个量词。有时需要同时使用多个量词。例例5：命题命题“对任意的对任意的x,存在存在y,使得使得x+y=5”,取个体域为实数取个体域为实数集合，则该命题集合，则该命题符号化为符号化为 x y H(x,y).其中其中H(x,y):x+y=5.这是个真命题这是个真命题.第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词283.使用使用量词时应注意
21、的问题量词时应注意的问题（1）在不同的个体域，同一命题的符号化形式可）在不同的个体域，同一命题的符号化形式可 能相同也可能不同。能相同也可能不同。（2）在不同的个体域，同一命题的真值可能相同）在不同的个体域，同一命题的真值可能相同 也也可可能能不不同同。(如如，R（x）表表示示x为为大大学学生生。如如 果个体域为大学里的某个班级的学生，则果个体域为大学里的某个班级的学生，则 x R（x）为真；若个体域为中学里的某个班级）为真；若个体域为中学里的某个班级 的学生，则的学生，则 x R（x）为假。）为假。)第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词29（3）约定以后如
22、不指定个体域，默认为全总）约定以后如不指定个体域，默认为全总 个体域。对每个个体变元的变化范围个体域。对每个个体变元的变化范围,用用 特性谓词加以限制。特性谓词加以限制。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词30特性谓词：特性谓词：限定个体变元变化范围的谓词。限定个体变元变化范围的谓词。一般而言，对全称量词，特性谓词常作蕴含一般而言，对全称量词，特性谓词常作蕴含的前件，如的前件，如 x(M(x)F(x)；对存在量词，；对存在量词，特性谓词常作合取项，如特性谓词常作合取项，如 x(M(x)G(x)。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函
23、数与量词31(4)一一般般来来说说，当当多多个个量量词词同同时时出出现现时时，它们的顺序不能随意调换。它们的顺序不能随意调换。例例如如：在在实实数数域域上上用用H(x,y)表表示示x+y=5，则则命命题题“对对于于任任意意的的x，都都存存在在y使使得得x+y=5”可可符符号号化化为为：x yH(x,y)，其其真真值值为为1。若若调调换换量量词词顺顺序序后后为为：y xH(x,y),其真值为其真值为0。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词32(5)当当个个体体域域为为有有限限集集合合时时，如如D=a1,a2,an，对任意谓词对任意谓词A(x)，有，有 xA(x
24、)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词33例例6：在谓词逻辑中将下列命题符号化。：在谓词逻辑中将下列命题符号化。（1）所有的人都长头发。）所有的人都长头发。（2）有的人吸烟。）有的人吸烟。（3）没有人登上过木星。）没有人登上过木星。（4）清华大学的学生未必都是高素质的。）清华大学的学生未必都是高素质的。解：令解：令M(x):x是人。（特性谓词）是人。（特性谓词）（1）令令F(x):x长头发。则符号化为：长头发。则符号化为：（x）(M(x)F(x)第二章第二章 谓谓 词词 逻逻 辑辑2.2
25、命题函数与量词命题函数与量词34（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)第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词35小小结结:本本节节介介绍绍了了n元元谓谓词词、命命题题函函数数、全全称称量量词词和和存存在在量量词词等等概概念念。重重点点掌掌握握全全称量词和存在量词及量化命题的符号化。
26、称量词和存在量词及量化命题的符号化。第二章第二章 谓谓 词词 逻逻 辑辑2.2 命题函数与量词命题函数与量词362.3谓词公式与翻译谓词公式与翻译nn元元谓词谓词A(x1，x2.xn)称为谓词演算的称为谓词演算的原子公式。原子公式。定义：定义：谓词演算的谓词演算的合式公式，合式公式，可由下述各条组成可由下述各条组成:（1）原子公式是合式公式。）原子公式是合式公式。（2）若）若A 是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。（3）若若A，B是是合合式式公公式式，则则(A B)，(A B)，(A B)，(A B)也是合式公式。也是合式公式。（4）若若A是是合合式式公公式式，x是是
27、A中中出出现现的的任任何何变变元元,则则(x)A,(x)A，也是合式公式。，也是合式公式。（5）只只有有有有限限次次应应用用(1)(4)得得到到的的公公式式是是合合式式公公式。式。第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译37例例1：在谓词逻辑中将下列命题符号化：在谓词逻辑中将下列命题符号化.（1）凡正数都大于零。）凡正数都大于零。（2）存在小于）存在小于2的素数。的素数。（3）没有不能表示成分数的有理数。）没有不能表示成分数的有理数。（4）并不是所有参加考试的人都能取得好成绩。）并不是所有参加考试的人都能取得好成绩。解：（解：（1）令）令F(x):x是正数。是正
28、数。M(x):x大于零。大于零。则符号化为：则符号化为：（x）(F(x)M(x)第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译38（2）令）令E(x):x小于小于2。S(x):x是素数。则符号化为：是素数。则符号化为：x(E(x)S(x)（真值为（真值为0）（3）令）令D(x):x是有理数。是有理数。F(x):x能表示成分数。能表示成分数。则符号化为：则符号化为：x(D(x)F(x)或或 x(D(x)F(x)（真值为）（真值为）（4）令）令M(x)：x是人。是人。Q(x):x参加考试。参加考试。H(x):x取得好成绩。则符号化为：取得好成绩。则符号化为：x(M(x)Q
29、(x)H(x)或或 x(M(x)Q(x)H(x)第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译39例例2：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）所有运动员都钦佩某些教练）所有运动员都钦佩某些教练.（2）有些运动员不钦佩教练）有些运动员不钦佩教练.设：设：L(x):x是运动员是运动员 J(y):y是教练是教练 A(x,y):x钦佩钦佩y(1)(x)(L(x)（y)(J(y)A(x,y)(2)（x)(L(x)(y)(J(y)A(x,y)第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译40小小结结：本本节节介介绍绍了了谓谓词
30、词合合式式公公式式的的概概念念，重重点点掌握掌握谓词公式的翻译。谓词公式的翻译。第二章第二章 谓谓 词词 逻逻 辑辑2.3 谓词公式与翻译谓词公式与翻译41变元的约束变元的约束定定义义:在在谓谓词词公公式式中中，形形如如(x)P(x)和和(x)P(x)的的部部 分分，称为谓词，称为谓词公式的公式的x约束部分。约束部分。(x)P(x)或或(x)P(x)中中的的x叫叫做做量量词词的的指指导导变变元元 或或作用变元作用变元，P(x)称为称为相应量词的相应量词的作用域作用域或或辖域辖域。在在 x和和 x的辖域中，的辖域中，x的所有出现都称为的所有出现都称为约束出约束出 现现，相应的，相应的x称为称为约
31、束变元约束变元;P(x)中除约束变元中除约束变元 以外出现的变元称为是以外出现的变元称为是自由变元自由变元。第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束42例例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 变元的约束变元的约束43说明说明:(1)n元谓词公式元谓词公式A(x1，x2.xn)中有中有n个自由变元，个自由变元，若对其中的若对其中的k(kn)个进行约束，则构成了个进行约束，则构成了n-k元谓元谓词；如果一个公式中没有自由变元出现，则该公式词；如果一个公式中没有自由
32、变元出现，则该公式就变成了一个命题。就变成了一个命题。(2)一个公式的约束变元所使用的名称符号是无关紧一个公式的约束变元所使用的名称符号是无关紧要的，如要的，如(x)M(x)与与(y)M(y)意义相同。意义相同。第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束442.4.2 约束变元的约束变元的换名与换名与自由变元的自由变元的代入代入 一个变元在同一个公式中既是自由出现又是约一个变元在同一个公式中既是自由出现又是约束出现，这样在理解上容易发生混淆。为了避免这束出现，这样在理解上容易发生混淆。为了避免这种混乱，可对种混乱，可对约束变元进行换名。约束变元进行换名。第二章第二章 谓谓
33、 词词 逻逻 辑辑2.4 变元的约束变元的约束45换名规则换名规则:(对约束变元而言）对约束变元而言）对约束变元进行换名，使得一个变元在一个公式中对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现只呈一种形式出现(1)约束变元可以换名，其更改的变元名称范围是约束变元可以换名，其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的量词中的指导变元以及该量词作用域中所出现的该变元，公式的其余部分不变。该变元，公式的其余部分不变。(2)换名时一定要更改为作用域中没有出现的变元换名时一定要更改为作用域中没有出现的变元名称。名称。第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束
34、变元的约束46例例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 变元的约束变元的约束47代入规则代入规则（对自由变元而言）（对自由变元而言）对公式中自由变元的更改称为代入对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入，代入时对于谓词公式中的自由变元可以作代入，代入时需要对公式中出现该自由变元的需要对公式中出现该自由变元的每一处每一处进行；进行；(2)用以代入的变元与原公式中所有变
35、元的名称不能用以代入的变元与原公式中所有变元的名称不能相同。相同。例：例：x(P(x)R(x,y)L(x,y)对自由变元对自由变元y用用z来代入，得来代入，得 x(P(x)R(x,z)L(x,z)第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束48小小结结：本本节节介介绍绍了了约约束束变变元元、自自由由变变元元的的 概概念念，重重点点掌掌握握约约束束变变元元的的换换名名与与自自由由变变元元的的代入代入。第二章第二章 谓谓 词词 逻逻 辑辑2.4 变元的约束变元的约束49谓词公式的等价和永真的概念谓词公式的等价和永真的概念定义：定义：一个一个解释解释I由下面由下面4部分部分组成：
36、组成：1.非空个体域非空个体域DI；2.DI中部分特定元素中部分特定元素a、b，.；3.DI上的特定一些函数上的特定一些函数f、g，.；4.DI上特定谓词上特定谓词P、Q，.。见书见书P40例。例。第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式50定义定义：给定任意的谓词公式给定任意的谓词公式A，其个体域为，其个体域为E，（1）对对于于A的的所所有有解解释释，公公式式A都都为为真真，则则称称A在在E上是上是永真的永真的(或有效的或有效的)。（2）若若对对于于A的的所所有有解解释释，公公式式A都都为为假假，则则称称A在在E上是上是永假的永假的(或不可
37、满足的或不可满足的)。（3）若若至至少少存存在在着着一一种种解解释释使使得得公公式式A为为真真，则则称称A在在E上是上是可满足的。可满足的。第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式51定定义义：给给定定任任何何两两个个谓谓词词公公式式A、B，设设它它们们有有共共同同的的个个体体域域E，若若对对A和和B的的任任一一组组变变元元进进行行解解释释，所所得得命命题题的的真真值值相相同同，则则称称谓词公式谓词公式A和和B在在E上等价上等价，并记为，并记为A B。定定义义：给给定定任任何何两两个个谓谓词词公公式式A、B，当当且且仅仅当当A B是是永永真真
38、式式时时，称称“A蕴蕴涵涵B”，记记作作A B。第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式522.5.2 谓词演算的等价式和蕴涵式谓词演算的等价式和蕴涵式1、命题公式的推广、命题公式的推广在命题公式中成立的等价公式，用谓词公式去代换在命题公式中成立的等价公式，用谓词公式去代换其中相应的命题变元，得到的公式依然成立其中相应的命题变元，得到的公式依然成立如：如：x(P(x)Q(x)x(P(x)Q(x)P(x)Q(x)（P(x)Q(x)）第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式532、量词与、量词与
39、 之间的关系之间的关系 （x）P(x)（x）P(x)（x）P(x)（x）P(x)证明：对个体域证明：对个体域 a1，a2，an，xP(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)x P(x)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式543、量词作用域的扩张与收缩、量词作用域的扩张与收缩量词作用域中如果有合取或析取项，且其中有一个量词作用域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词作用域之外。如：是命题，则可将该命题移至量词作用域之外。如：（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(
40、x)B（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B 第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式55证明：当个体域为证明：当个体域为a1，a2，an，xA(x)P(P(a1)P(a2)P(an)P)(P(a1)P)(P(a2)P)(P(an)P)x(A(x)P)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式56n量词作用域的扩张和收缩量词作用域的扩张和收缩(xA(x)B）（x)(A(x)B）(（x)A(x)B)(x)(A(x)B）(B (x)A(x)）（x)(B A(x)）
41、(B (x)A(x)（x）(B A(x)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式57例例1：xA(x，y)P(y)x(A(x，y)P(y)例例2：x y(P(x)Q(y)(x P(x)yQ(y)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式58例例1：xA(x，y)P(y)x(A(x，y)P(y)例例2：x y(P(x)Q(y)(x P(x)yQ(y)证明：证明：x y(P(x)Q(y)x y(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
42、)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式594、量词的分配、量词的分配设设A(x)、B(x)是是任任意意的的含含自自由由出出现现个个体体变变元元x的公式，则的公式，则(1)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 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式60证明：对个体域证明：对个体域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)
43、xB(x)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式61(3)x(A(x)B(x)x A(x)x B(x)(4)x(A(x)B(x)x A(x)x B(x)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式62注意：逆方向不成立。注意：逆方向不成立。如（如（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)为为假
44、。假。第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式63(5)x(A(x)B(x)xA(x)xB(x)(6)x A(x)xB(x)x(A(x)B(x)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式645、多个量词的使用、多个量词的使用 (1)x yP(x，y)y xP(x，y)(二者同义二者同义)(2)x yP(x，y)y xP(x，y)x yP(x，y)x yP(x，y)(3)y xP(x，y)x yP(x，y)(4)x yP（x，y）x yP(x，y)y xP（x，y）y xP(x，y)(5)y x
45、P（x，y）y xP(x，y)第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式65注意注意:上述蕴涵式逆方向均不成立。上述蕴涵式逆方向均不成立。例：如（例：如（3）中，设个体域为有理数集合，）中，设个体域为有理数集合，P(x,y)：x+y=0，则则 x y P(x,y)为真。为真。但是，但是，y xP(x,y)为假。为假。第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式66小结：本节介绍了谓词演算的基本等价式和蕴涵式。小结：本节介绍了谓词演算的基本等价式和蕴涵式。重点掌握谓词公式之间的等价演算。重点掌握谓词
46、公式之间的等价演算。第二章第二章 谓谓 词词 逻逻 辑辑2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式67定义定义:任何一个谓词公式任何一个谓词公式A，如果具有如下形式：，如果具有如下形式：(x1)(x2)(xn)B，其中其中可能是量词可能是量词 或量词或量词，xi（i=1，n）是个体变元，是个体变元，B是不含量词的是不含量词的谓词公式，则称谓词公式，则称 A是前束范式。是前束范式。说明：前束范式说明：前束范式的量词均在全式的开头的量词均在全式的开头,它们的作用它们的作用 域延伸到整个公式的末尾。域延伸到整个公式的末尾。第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式68
47、 例例:x y(F(x)G(y)H(x,y)x y(F(x,y)G(y,z)x H(x,y,z)定理：定理：任何一个谓词公式，均和一个前束范任何一个谓词公式，均和一个前束范 式等价。式等价。第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式69前束范式的求法：前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定第一步：否定深入。即利用量词转化公式，把否定联结词深入到命题变元和联结词深入到命题变元和谓词填式的谓词填式的前面。前面。第二步：改名。即利用换名规则、代入规则更换一第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。些变元的名称，以便消除混乱。第三步
48、：量词前移。即利用量词辖域的收缩与扩张第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。把量词移到前面。这样便可求出与公式等价的前束范式。这样便可求出与公式等价的前束范式。第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式70例例:求下列公式的前束范式。求下列公式的前束范式。第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式71n解解:第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式72 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式73n 第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式74 第二章第二章 谓谓 词词 逻逻
49、辑辑2.6 前束范式前束范式75说明：说明：1.等价演算的顺序不同，使得前束范式不唯一。等价演算的顺序不同，使得前束范式不唯一。2.一个谓词公式的前束范式的各指导变元应是各不相一个谓词公式的前束范式的各指导变元应是各不相同的，原来在谓词公式中自由出现的个体变元在同的，原来在谓词公式中自由出现的个体变元在前束范式中还应是自由出现。前束范式中还应是自由出现。小结：本节介绍了谓词公式前束范式的概念和求法。小结：本节介绍了谓词公式前束范式的概念和求法。第二章第二章 谓谓 词词 逻逻 辑辑2.6 前束范式前束范式76推理规则推理规则在谓词演算中，推理的形式结构仍为在谓词演算中，推理的形式结构仍为 H1
50、H2 H3.HnC。若若 H1 H2 H3.HnC是永真式，则称由前是永真式，则称由前提提H1,H2,H3,Hn逻辑的推出结论逻辑的推出结论C，但在谓词，但在谓词逻辑中逻辑中,H1,H2,H3,.,Hn,C均为谓词公式。均为谓词公式。（命题演算中的推理规则，可在谓词推理理论（命题演算中的推理规则，可在谓词推理理论中应用。）中应用。）第二章第二章 谓谓 词词 逻逻 辑辑2.7 谓词演算的推理理论谓词演算的推理理论77与量词有关的与量词有关的四条重要四条重要推理规则推理规则：1、全称量词消去规则（、全称量词消去规则（US规则）规则）2、全称量词产生规则（、全称量词产生规则（UG规则）规则）3、存在