第2章谓词逻辑优秀PPT.ppt

第第2章谓词逻辑章谓词逻辑现在学习的是第1页，共91页所有的人都是要死的，所有的人都是要死的，苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。根据常识，认为这个推理是正确的。但是，根据常识，认为这个推理是正确的。但是，若用若用Ls来表示，设来表示，设P、Q和和R分别表示这三个原分别表示这三个原子命题，则有子命题，则有P，QR现在学习的是第2页，共91页然然而而，(PQ)R并并不不是是永永真真式式，故故上上述述推推理理形形式式又又是是错错误误的的。一一个个推推理理，得得出出矛矛盾盾的的结结论论，问问题题在在哪哪里里呢呢?问问题题就就在在于于这这类类推推理理中中，各各命命题题之之间间的的逻逻辑辑关关系系不不是是体体现现在在原原子子命命题题之之间间，而而是是体体现现在在构构成成原原子子命命题题的的内内部部成成分分之之间间，即即体体现现在在命命题题结结构构的的更更深深层层次次上上。对对此此，Ls是是无无能能为为力力的的。所所以以，在在研研究究某某些些推推理理时时，有有必必要要对对原原子子命命题题作作进进一一步步分分析析，分分析析出出其其中中的的个个体体词词，谓谓词词和和量量词词，研研究究它它们们的的形形式式结结构构的的逻逻辑辑关关系系、正正确确的的推推理理形形式式和和规规则则，这这些些正正是是谓谓词词逻辑（简称为逻辑（简称为Lp）的基本内容。）的基本内容。现在学习的是第3页，共91页2.1 个体、谓词和量词个体、谓词和量词2.2 谓词公式与翻译谓词公式与翻译2.3 约束变元与自由变元约束变元与自由变元2.4 公式解释与类型公式解释与类型2.5 等价式与蕴涵式等价式与蕴涵式2.6 谓词公式范式谓词公式范式2.7 谓词逻辑的推理理论谓词逻辑的推理理论现在学习的是第4页，共91页2.1 个体、谓词和量词个体、谓词和量词在在Lp中中，命命题题是是具具有有真真假假意意义义的的陈陈述述句句。从从语语法法上上分分析析，一一个个陈陈述述句句由由主主语语和和谓谓语语两两部部分分组组成成。在在Lp中中，为为揭揭示示命命题题内内部部结结构构及及其其不不同同命命题题的的内内部部结结构构关关系系，就就按按照照这这两两部部分分对对命命题题进进行行分分析析，并并且且把把主主语语称称为为个个体体或或客客体体，把把谓语谓语称为称为谓词谓词。现在学习的是第5页，共91页.个体、谓词和命题的谓词形式定义定义2.1.1 在原子命题中，所描述的在原子命题中，所描述的对象对象称称为为个体个体；用以描述；用以描述个体的性质个体的性质或或个体间关系个体间关系的的部分，称为部分，称为谓词谓词。例如例如：张三：张三是个大学生是个大学生；5大于大于3个体，是指可以独立存在的事物，它可以个体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张三，计算机，是具体的，也可以是抽象的，如张三，计算机，精神等。表示特定的个体，称为精神等。表示特定的个体，称为个体常元个体常元，以，以a，b，c或带下标的或带下标的ai，bi，ci表示；表示不表示；表示不确定的个体，称为确定的个体，称为个体变元个体变元，以，以x，y，z或或xi，yi，zi表示。表示。现在学习的是第6页，共91页谓词，当与一个个体相联系时，它刻划了谓词，当与一个个体相联系时，它刻划了个体性质个体性质；当与两个或两个以上个体相联系时，；当与两个或两个以上个体相联系时，它刻划了它刻划了个体之间的关系个体之间的关系。表示特定谓词，称。表示特定谓词，称为为谓词常元谓词常元，表示不确定的谓词，称为，表示不确定的谓词，称为谓词变谓词变元元，都用大写英文字母，如，都用大写英文字母，如P，Q，R，或，或其带上、下标来表示。在本书中，不对谓词变其带上、下标来表示。在本书中，不对谓词变元作更多地讨论。元作更多地讨论。现在学习的是第7页，共91页对于给定的命题，当用表示其个体的小写对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆括号把小写字母写在大写字母右侧的圆括号()内。内。例如例如，在命题，在命题“张三是位大学生张三是位大学生”中，中，“张三张三”是个体，是个体，“是位大学生是位大学生”是谓词，它刻是谓词，它刻划了划了“张三张三”的性质。设的性质。设S：是位大学生，：是位大学生，c：张三，则张三，则“张三是位大学生张三是位大学生”可表示为可表示为S(c)，或，或者写成者写成S(c)：张三是位大学生。：张三是位大学生。现在学习的是第8页，共91页又如又如，在命题，在命题“武汉位于北京和广州之间武汉位于北京和广州之间”中，武汉、北京和广州是三个个体，而中，武汉、北京和广州是三个个体，而“位于位于和和之间之间”是谓词，它刻划了武汉、北是谓词，它刻划了武汉、北京和广州之间的关系。设京和广州之间的关系。设P：位于位于和和之间，之间，a：武汉，：武汉，b：北京，：北京，c：广州，则：广州，则P(a，b，c)：武汉位于北京和广州之间。武汉位于北京和广州之间。现在学习的是第9页，共91页定义定义2.1.2 一个原子命题用一个谓词一个原子命题用一个谓词(如如P)和和n个有次序的个有次序的个体常元个体常元(如如a1，a2，an)表表示成示成P(a1，a2，an)，称它为该原子命题的，称它为该原子命题的谓词形式或谓词形式或命题的谓词形式命题的谓词形式。应注意的是，命题的谓词形式中的应注意的是，命题的谓词形式中的个体出个体出现的次序影响命题的真值现的次序影响命题的真值，不是随意变动，否，不是随意变动，否则真值会有变化。如上述例子中，则真值会有变化。如上述例子中，P(b,a,c)是假。是假。通常个体出现的次序事先要约定好。通常个体出现的次序事先要约定好。现在学习的是第10页，共91页.原子谓词公式原子命题的谓词形式还可以进一步加以抽原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的象，比如在谓词右侧的圆括号内的n个个个体常元个体常元被替换成被替换成个体变元个体变元，如，如x1,x2,xn，这样，这样便得了一种关于命题结构的新表达形式，称之便得了一种关于命题结构的新表达形式，称之为为n元原子谓词。元原子谓词。现在学习的是第11页，共91页定义定义2.1.3 由一个谓词由一个谓词(如如P)和和n个体变元个体变元(如如x1，x2，xn)组成的组成的P(x1，x2，xn)，称它为称它为n元原子谓词元原子谓词或或n元命题函数元命题函数，简称，简称n元谓元谓词。而个体变元的论述范围，称为词。而个体变元的论述范围，称为个体域个体域或或论论域域。当当n=1时，称一元谓词；当时，称一元谓词；当n=2时，称为二时，称为二元谓词，元谓词，。特别地，当。特别地，当n=0，称为零元谓词。，称为零元谓词。零元谓词零元谓词就是通常的命题，这样命题与谓词就就是通常的命题，这样命题与谓词就得到了统一。得到了统一。通常一元谓词表达了个体的通常一元谓词表达了个体的“性质性质”，而，而多元谓词表达了个体之间的关系。多元谓词表达了个体之间的关系。现在学习的是第12页，共91页n元谓词不是命题元谓词不是命题，只有其中的个体变元用只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命特定个体或个体常元替代时，才能成为一个命题。题。但个体变元在哪些论域取特定的值，对命但个体变元在哪些论域取特定的值，对命题的真值极有影响。题的真值极有影响。例如例如，令，令S(x)：x是大学生。若是大学生。若x的论域为的论域为某大学的计算机系中的全体同学，则某大学的计算机系中的全体同学，则S(x)是真的；是真的；若若x的论域是某中学的全体学生，则的论域是某中学的全体学生，则S(x)是假的；是假的；若若x的论域是某剧场中的观众，且观众中有大学的论域是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则生也有非大学生的其它观众，则S(x)是真值是不是真值是不确定的。确定的。现在学习的是第13页，共91页通常，把一个通常，把一个n元谓词中的每个个体的论域元谓词中的每个个体的论域综合在一起作为它的论域，称为综合在一起作为它的论域，称为n元谓词的全总元谓词的全总论域。定义了论域。定义了全总论域全总论域或全总个体域，为深入或全总个体域，为深入研究命题提供了方便。当一个命题没有指明论研究命题提供了方便。当一个命题没有指明论域时，一般都从全总论域作为其论域。而这时域时，一般都从全总论域作为其论域。而这时又常常要采用一个谓词如又常常要采用一个谓词如P(x)来限制个体变元来限制个体变元x的取值范围，并把的取值范围，并把P(x)称为称为特性谓词特性谓词。现在学习的是第14页，共91页.量词利用利用n元谓词和它的论域概念，有时还是不元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题。能用符号来很准确地表达某些命题。例如例如 S(x)表示表示x是大学生，而是大学生，而x的个体域为的个体域为某单位的职工，那么某单位的职工，那么S(x)可表示某单位职工都是可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在为了避免理解上的歧义，在Lp中，需要引入用中，需要引入用以刻划以刻划“所有的所有的”、“存在一些存在一些”等表示不同等表示不同数量的词，即量词，其定义如下：数量的词，即量词，其定义如下：现在学习的是第15页，共91页定义定义2.1.4 符号符号 称为全称量词符，用来称为全称量词符，用来表达表达“对所有的对所有的”、“每一个每一个”、“对任何一对任何一个个”、“一切一切”等词语；等词语；x称为称为全称量词全称量词，称，称x为指导变元。为指导变元。符号符号 称为存在量词符，用来表达称为存在量词符，用来表达“存在存在一些一些”、“至少有一个至少有一个”、“对于一些对于一些”、“某个某个”等词语；等词语；x称为称为存在量词存在量词，x称为指导变称为指导变元。元。现在学习的是第16页，共91页符号符号!称为存在唯一量词符，用来表达称为存在唯一量词符，用来表达“恰有一个恰有一个”、“存在唯一存在唯一”等词语；等词语；!x称为称为存在唯一量词，称存在唯一量词，称x为指导变元。为指导变元。全称量词、存在量词、存在唯一量词统称全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家量词。量词记号是由逻辑学家Fray引入的，有引入的，有了量词之后，用逻辑符号表示命题的能力大大了量词之后，用逻辑符号表示命题的能力大大加强了。加强了。现在学习的是第17页，共91页例例2.1.1 试用量词、谓词表示下列命题：试用量词、谓词表示下列命题：所有大学生都热爱祖国；所有大学生都热爱祖国；每个自然数都是实数；每个自然数都是实数；一些大学生有远大理想；一些大学生有远大理想；有的自然数是素数。有的自然数是素数。现在学习的是第18页，共91页解解 令令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)现在学习的是第19页，共91页在该例的解答中，由于命题中没有指明个在该例的解答中，由于命题中没有指明个体域，这便意味着各命题是在全总论域中讨论，体域，这便意味着各命题是在全总论域中讨论，因而都使用了特性谓词，如因而都使用了特性谓词，如S(x)、N(x)。而且还。而且还可以看出，量词与特性谓词的搭配还有一定规可以看出，量词与特性谓词的搭配还有一定规律，即律，即全称量词后跟一个条件式全称量词后跟一个条件式，而特性谓词，而特性谓词作为其前件出现；作为其前件出现；存在量词后跟一个合取式存在量词后跟一个合取式，特性谓词作为一个合取项出现。特性谓词作为一个合取项出现。现在学习的是第20页，共91页如果在解答时，指明了个体域，便不用特如果在解答时，指明了个体域，便不用特性谓词，例如在性谓词，例如在、中令个体域为全体大学中令个体域为全体大学生，生，和和中的个体域为全部自然数，则可符中的个体域为全部自然数，则可符号化为：号化为：(x)L(x)(x)R(x)(x)I(x)(x)P(x)现在学习的是第21页，共91页谓词前加上了量词，称为谓词的量化。谓词前加上了量词，称为谓词的量化。若若一个谓词中所有个体变元都量化了，则该谓词一个谓词中所有个体变元都量化了，则该谓词就变成了命题就变成了命题。这是因为在谓词被量化后，可。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同以在整个个体域中考虑命题的真值了。这如同数学中的函数数学中的函数f(x)，的值是不确定的，的值是不确定的，但但 可确定其值。可确定其值。现在学习的是第22页，共91页2.2 谓词公式与翻译谓词公式与翻译.谓词公式为为了了方方便便处处理理数数学学和和计计算算机机科科学学的的逻逻辑辑问问题及谓词表示的直觉清晰性，将引进题及谓词表示的直觉清晰性，将引进项项的概念。的概念。定义定义2.2.1 项由下列规则形成：项由下列规则形成：个体常元和个体变元是项；个体常元和个体变元是项；若若f是是n元元函函数数，且且t1，t2，tn是是项项，则则f(t1，t2，tn)是项；是项；所有项都由所有项都由和和生成。生成。现在学习的是第23页，共91页有了项的定义，函数的概念就可用来表示有了项的定义，函数的概念就可用来表示个体常元和个体变元。例如，令个体常元和个体变元。例如，令f(x,y)表示表示x+y，谓词谓词N(x)表示表示x是自然数，那么是自然数，那么f(2,3)表示个体自表示个体自然数然数5，而，而N(f(2,3)表示表示5是自然数。这里函数是是自然数。这里函数是就广义而言的，例如就广义而言的，例如P(x):x是教授，是教授，f(x):x的父的父亲，亲，c:张强，那么张强，那么P(f(c)便是表示便是表示“张强的父亲张强的父亲是教授是教授”这一命题。这一命题。现在学习的是第24页，共91页函数的使用给谓词表示带来很大方便。例函数的使用给谓词表示带来很大方便。例如，用谓词表示命题：对任意整数如，用谓词表示命题：对任意整数x，x2-1=(x+1)(x-1)是恒等式。令是恒等式。令I(x):x是整数，是整数，f(x)=x2-1，g(x)=(x+1)(x-1)，E(x,y):x=y，则该命，则该命题可表示成：题可表示成：(x)(I(x)E(f(x),g(x)。现在学习的是第25页，共91页定义定义2.2.2 若若P(x1，x2，xn)是是n元谓词，元谓词，t1，t2，tn是项，则称是项，则称P(t1，t2，tn)为为Ls中原子谓词公式，简称中原子谓词公式，简称原子公式原子公式。下面，由原子公式出发，给出下面，由原子公式出发，给出Lp中的中的合式合式谓词公式谓词公式的归纳定义。的归纳定义。现在学习的是第26页，共91页定义定义2.2.3 合式谓词公式当且仅当由下列规合式谓词公式当且仅当由下列规则形成的符号串则形成的符号串 原子公式是合式谓词公式；原子公式是合式谓词公式；若若A是合式谓词公式，则是合式谓词公式，则(A)是合式谓是合式谓词公式；词公式；若若A，B是合式谓词公式，则是合式谓词公式，则(AB)，(AB)，(AB)和和(AB)都是合式谓词公式；都是合式谓词公式；若若A是合式谓词公式，是合式谓词公式，x是个体变元，则是个体变元，则(x)A、(x)A都是合式谓词公式；都是合式谓词公式；仅有有限项次使用仅有有限项次使用、和和形成形成的才是合式谓词公式。的才是合式谓词公式。现在学习的是第27页，共91页.谓词逻辑的翻译把把一一个个文文字字叙叙述述的的命命题题，用用谓谓词词公公式式表表示示出出来来，称称为为谓谓词词逻逻辑辑的的翻翻译译或或符符号号化化；反反之之亦亦然然。一般说来，符号化的步骤如下：一般说来，符号化的步骤如下：正正确确理理解解给给定定命命题题。必必要要时时把把命命题题改改叙叙，使使其其中中每每个个原原子子命命题题、原原子子命命题题之之间间的的关关系系能能明明显表达出来。显表达出来。现在学习的是第28页，共91页把每个原子命题分解成个体、谓词和量把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。词；在全总论域讨论时，要给出特性谓词。找出恰当量词。应注意全称量词找出恰当量词。应注意全称量词(x)后后跟条件式，存在量词跟条件式，存在量词(x)后跟合取式。后跟合取式。用恰当的联结词把给定命题表示出来。用恰当的联结词把给定命题表示出来。现在学习的是第29页，共91页例例2.2.1 将将命命题题“没没有有不不犯犯错错误误的的人人”符符号号化。化。解解 令令 M(x):x是人是人;F(x):x犯错误，犯错误，则原命题表示为：则原命题表示为：(x(M(x)F(x)也可以表示为：也可以表示为：(x)(M(x)F(x)。现在学习的是第30页，共91页例例2.2.2 将命题将命题“没有最大的自然数没有最大的自然数”符号化。符号化。解解 命命题题中中“没没有有最最大大的的”显显然然是是对对所所有有的的自自然然数数而而言言，所所以以可可理理解解为为“对对所所有有的的x，如如果果x是是自自然然数数，则则一一定定还还有有比比x大大的的自自然然数数”，再再具具体体点点，即即“对对所所有有的的x如如果果x是是自自然然数数，则则一一定定存存在在y，y也也是是自自然然数，并且数，并且y比比x大大”。令。令N(x):x是自然数，是自然数，G(x,y):x大于大于y，则原命题表示为：则原命题表示为：(x)(N(x)(y)(N(y)G(y,x)。现在学习的是第31页，共91页例例2.2.3 将语句将语句“今天有雨雪，有些人会跌跤今天有雨雪，有些人会跌跤”符号化。符号化。解解 本语句可理解为本语句可理解为“若今天下雨又下雪，则若今天下雨又下雪，则存在存在x，x是人且是人且x会跌跤会跌跤”。令令R:今天下雨，今天下雨，S:今天下雪，今天下雪，M(x):x是人，是人，F(x):x会跌跤，则本语句可表示为：会跌跤，则本语句可表示为：RS(x)(M(x)F(x)。由于人们对命题的文字叙述含意理解的不同，由于人们对命题的文字叙述含意理解的不同，强调的重点不同，对个体性质的刻画深度不同，强调的重点不同，对个体性质的刻画深度不同，会影响到命题符号化的形式不同。会影响到命题符号化的形式不同。现在学习的是第32页，共91页例例2.2.4 “这只大红书柜摆满了那些古书这只大红书柜摆满了那些古书”。解法解法1 设设F(x,y):x摆满了摆满了y;R(x):x是大红书柜；是大红书柜；Q(y):y是古书是古书;a:这只这只;b:那些那些.R(a)Q(b)F(a,b).解法解法2 设设A(x):x是书柜是书柜;B(x):x是大的是大的;C(x):x是红的是红的;D(y):y是古老的是古老的;E(y):y是书是书;F(x,y):x摆满了摆满了y;a:这只这只;b:那些那些.A(a)B(a)C(a)D(b)E(b)F(a,b).现在学习的是第33页，共91页2.3 约束变元与自由变元约束变元与自由变元定定义义2.3.1 给给定定一一个个谓谓词词公公式式A，其其中中有有一一部部分分公公式式形形如如(x)B(x)或或(x)B(x)，则则称称它它为为A的的x约约束束部部分分，称称B(x)为为相相应应量量词词的的作作用用域域或或辖辖域域。在在辖辖域域中中，x的的所所有有出出现现称称为为约约束束出出现现，x称称为为约约束束变变元元；A中中不不是是约约束束出出现现的的其其它它个个体体变变元元的的出出现现称称为为自自由由出出现现，这这些些个个体体变变元元称称自自由变元由变元。自由变元可以看作是公式中的参数。自由变元可以看作是公式中的参数。现在学习的是第34页，共91页对于给定的谓词公式，能够对于给定的谓词公式，能够准确地判定它准确地判定它的的辖域辖域、约束变元约束变元和和自由变元自由变元是很重要的是很重要的。通常，一个量词的辖域是某公式通常，一个量词的辖域是某公式A的一部分，的一部分，称为称为A的子公式。因此，确定一个量词的辖域即的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具是找出位于该量词之后的相邻接的子公式，具体地讲：体地讲：现在学习的是第35页，共91页若量词后有括号，则括号内的子公式就若量词后有括号，则括号内的子公式就是该量词的辖域；是该量词的辖域；若量词后无括号，则与量词邻接的子公若量词后无括号，则与量词邻接的子公式为该量词的辖域。式为该量词的辖域。判定给定公式判定给定公式A中个体变元是约束变元还是中个体变元是约束变元还是自由变元，关键是要看它在自由变元，关键是要看它在A中是约束出现，还中是约束出现，还是自由出现。是自由出现。现在学习的是第36页，共91页今今后后常常用用元元语语言言符符号号A(x)表表示示x是是其其中中的的一一个个个个体体变变元元自自由由出出现现的的任任意意公公式式，如如A(x)可可为为P(x)Q(x)，P(x)(y)Q(x,y)等等。一一旦旦在在A(x)前前加加上上量量词词(x)或或(x)，即即得得公公式式(x)A(x),或或(x)A(x)。这这时时，x即即是是约约束束出出现现了了。类类似似地，用地，用A(x,y)表示表示x和和y是自由出现的公式。是自由出现的公式。现在学习的是第37页，共91页定义定义2.3.2 设设A为任意一个公式，若为任意一个公式，若A中无中无自由出现的个体变元，则称自由出现的个体变元，则称A为封闭的合式公式，为封闭的合式公式，简称简称闭式闭式。由闭式定义可知，闭式中所有个体变元均由闭式定义可知，闭式中所有个体变元均为约束出现。为约束出现。现在学习的是第38页，共91页例例 说明以下各式的辖域与变元约束的情况。说明以下各式的辖域与变元约束的情况。a)(x)(P(x)Q(x);(闭式闭式)b)(x)(y)(P(x)Q(x,y);(闭式闭式)c)(x)(P(x)Q(x,y);d)(y)(z)L(x,y,z);e)(x)(y)(P(x,y)Q(y,z)(x)P(x,y);f)(x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y);在在e)f)中中,个体变元个体变元y既约束出现又自由出现。既约束出现又自由出现。现在学习的是第39页，共91页从下面讨论可以看出，从下面讨论可以看出，在一公式中，有的在一公式中，有的个体变元既可以是约束出现，又可以是自由出个体变元既可以是约束出现，又可以是自由出现现，这就容易产生混淆。为了避免混淆，采用，这就容易产生混淆。为了避免混淆，采用下面两个规则：下面两个规则：约束变元约束变元改名规则改名规则，将量词辖域中某个，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。辖域中未曾出现过的个体变元，其余不变。自由变元自由变元代入规则代入规则，对某自由出现的个，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且体变元不同的个体变元去代入，且处处代入处处代入。现在学习的是第40页，共91页例例 对约束变元进行换名或对自由变元进行代对约束变元进行换名或对自由变元进行代入：入：1.(x)(P(x)Q(x,y)Q(x,y);可改名为：可改名为：(z)(P(z)Q(z,y)Q(x,y);代入：代入：(x)(P(x)Q(x,u)Q(v,u);2.(x)(P(y)Q(x,y)；可改名为：可改名为：(u)(P(y)Q(u,y)可代入为：可代入为：(x)(P(z)Q(x,z).现在学习的是第41页，共91页改改名名规规则则与与代代入入规规则则的的共共同同点点都都是是不不能能改改变约束关系，而不同点是：变约束关系，而不同点是：施施行行的的对对象象不不同同。改改名名是是对对约约束束变变元元施施行，代入是对自由变元施行。行，代入是对自由变元施行。施施行行的的范范围围不不同同。改改名名可可以以只只对对公公式式中中一一个个量量词词及及其其辖辖域域内内施施行行，即即只只对对公公式式的的一一个个子子公公式式施施行行；而而代代入入必必须须对对整整个个公公式式同同一一个个自自由由变变元元的的所所有有自自由由出出现现同同时时施施行行，即即必必须须对对整整个公式施行。个公式施行。现在学习的是第42页，共91页 施行后的结果不同。改名后，公式含义施行后的结果不同。改名后，公式含义不变，不变，因为约束变元只改名为另一个个体变元，因为约束变元只改名为另一个个体变元，约束关系不改变约束关系不改变。约束变元不能改名为个体常。约束变元不能改名为个体常元；代入，不仅可用另一个个体变元进行代入，元；代入，不仅可用另一个个体变元进行代入，并且也可用个体常元去代入，从而使公式由具并且也可用个体常元去代入，从而使公式由具有普遍意义变为仅对该个体常元有意义，即公有普遍意义变为仅对该个体常元有意义，即公式的含义改变了。式的含义改变了。现在学习的是第43页，共91页需要指出的是：量词作用域中的约束变元，需要指出的是：量词作用域中的约束变元，当论域的元素有限时，个体变元的所有可能的当论域的元素有限时，个体变元的所有可能的取代时可枚举的。取代时可枚举的。设论域元素为：设论域元素为：a1,a2,an.则则(x)A(x)A(a1)A(a2)A(an)(x)A(x)A(a1)A(a2)A(an).此外，量词对变元的约束，通常与量词的此外，量词对变元的约束，通常与量词的顺序有关，不能随意颠倒，约定按从左到右的顺序有关，不能随意颠倒，约定按从左到右的顺序读出。顺序读出。现在学习的是第44页，共91页2.4 公式解释与类型公式解释与类型1公式解释一一般般情情况况下下，Lp中中的的公公式式含含有有：个个体体常常元元、个个体体变变元元（约约束束变变元元或或自自由由变变元元）、函函数数变变元元、谓谓词词变变元元等等，对对各各种种变变元元用用指指定定的的特特殊殊常常元元去去代代替替，就就构构成成了了一一个个公公式式的的解解释释或或赋赋值值。也也就就是是当当个个体体变变元元由由具具体体的的个个体体所所代代替替，而而命命题题变变元元由由具具体体的的命命题题所所代代替替，这这样样就就确确定定了了一一个个具具有有真真值值：真真与与假假的的命命题题。当当然然在在给给定定的的解解释释下下，可可以以对对多多个个公公式式进进行行解解释释。下面给出解释的一般定义。下面给出解释的一般定义。现在学习的是第47页，共91页定义定义2.4.1 一个解释一个解释I由下面由下面4部分组成：部分组成：非空个体域非空个体域DI。DI中部分特定元素中部分特定元素a，b，。DI上的特定一些函数上的特定一些函数f，g，。DI上特定谓词：上特定谓词：P，Q，。在一个具体解释中，个体常元、函数符号、在一个具体解释中，个体常元、函数符号、谓词符号的数量一般是有限的，并且其解释一旦谓词符号的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体确定下来就不再改变，只是个体变元的值在个体域域DI内变化，量词符内变化，量词符 或或 仅作用于仅作用于DI中的元素。中的元素。现在学习的是第48页，共91页2公式类型定定义义2.4.2 若若一一公公式式在在任任何何解解释释下下都都是是真的，称该公式为真的，称该公式为逻辑有效的逻辑有效的，或，或永真的永真的。若若一一公公式式在在任任何何解解释释下下都都是是假假的的，称称该该公式为矛盾式，或公式为矛盾式，或永假式永假式或不可满足的。或不可满足的。若若一一公公式式至至少少存存在在一一个个解解释释使使其其为为真真，称该公式为称该公式为可满足式可满足式。现在学习的是第49页，共91页从定义可知，逻辑有效式为可满足式，反从定义可知，逻辑有效式为可满足式，反之未必成立。之未必成立。与命题公式中分类一样，谓词公式也分为与命题公式中分类一样，谓词公式也分为三种类型，即逻辑有效式（或重言式）、矛盾三种类型，即逻辑有效式（或重言式）、矛盾式（或永假式）和可满足式。式（或永假式）和可满足式。现在学习的是第50页，共91页由于谓词公式的复杂性和解释的多样性，由于谓词公式的复杂性和解释的多样性，至今还没有一个可行的算法判定任何公式的类至今还没有一个可行的算法判定任何公式的类型。早在型。早在1936年，年，Churen和和Turing各自独立地各自独立地证明了：证明了：对于对于Lp，其判定问题是不可解的。但，其判定问题是不可解的。但是，是，Lp是个半个可判定的，即若是个半个可判定的，即若Lp中公式是重中公式是重言式，则存在算法在有限步骤内能验证它。言式，则存在算法在有限步骤内能验证它。当当然，对于一些较为简单的公式，或某些特殊公然，对于一些较为简单的公式，或某些特殊公式，还是可以判定其类型的。式，还是可以判定其类型的。现在学习的是第51页，共91页下面讨论代入规则的扩展，因为它对判定下面讨论代入规则的扩展，因为它对判定重言式这种公式类型是很有用的。重言式这种公式类型是很有用的。在在2.3节中，介绍了自由变元的代入规则，节中，介绍了自由变元的代入规则，实际上代入规则并非只局限于自由变元，对公实际上代入规则并非只局限于自由变元，对公式中命题变元、谓词变元均可实施代入，式中命题变元、谓词变元均可实施代入，其关其关键是不能因为代入而改变原有公式的约束关系键是不能因为代入而改变原有公式的约束关系。今将谓词变元（包括命题变元）代入规则叙述今将谓词变元（包括命题变元）代入规则叙述如下：如下：现在学习的是第52页，共91页在一公式中，一个在一公式中，一个n元元(n0)谓词变元谓词变元P(x1,x2,xn)可以代入至少有可以代入至少有n个自由变个自由变元的公式元的公式B(y1,y2,yn,yn+1,yn+2,yn+r)，其中，其中r0，y1,y2,yn是分别对应于是分别对应于x1,x2,xn的任意选定的的任意选定的n个自由变元，且个自由变元，且对对P出现进行处处代入，出现进行处处代入，B中的中的r个自由变元不允个自由变元不允许在原公式中以约束出现，许在原公式中以约束出现，P中的个体变元也不中的个体变元也不允许在允许在B中以约束出现。中以约束出现。为保证代入规则顺利而正确地实行，常常为保证代入规则顺利而正确地实行，常常对约束变元改名而适应之。对约束变元改名而适应之。现在学习的是第53页，共91页2.5 等价式与蕴涵式等价式与蕴涵式1等价式定定义义2.5.1 设设A、B为为任任意意两两个个公公式式，若若AB为为逻逻辑辑有有效效的的，也也即即对对变变元元的的任任一一赋赋值值其其真真值值一一样样，则则称称A与与B是是等等价价的的，记记为为AB，称称AB为等价式。为等价式。由由于于重重言言式式(永永真真式式)都都是是逻逻辑辑有有效效的的，可可见见1.3节节中中的的命命题题定定律律（基基本本等等价价式式）都都是是Lp 等等价式。价式。现在学习的是第54页，共91页此外，还有一置换规则：此外，还有一置换规则：设设(A)是含有是含有A出现的公式，出现的公式，(B)是用公是用公式式B替换若干个公式替换若干个公式A的结果。的结果。若若AB，则，则(A)(B)。显然，显然，若若(A)为重言式，则为重言式，则(B)也是重言也是重言式式。现在学习的是第55页，共91页下面给出涉及量词的基本等价式。下面给出涉及量词的基本等价式。(1)量词否定等价式：(a)(x)A(x)(x)A(x)(b)(x)A(x)(x)A(x)证明证明 在有限个体域上证明。设个体域的个在有限个体域上证明。设个体域的个体变元为体变元为a1,a2,an.则则(x)A(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)(x)A(x).(x)A(x)(A(a1)A(a2)A(an)(x)A(x).现在学习的是第56页，共91页这两个等价式，可用量词的定义给予说明。这两个等价式，可用量词的定义给予说明。由于由于“并非对一切并非对一切x，A为真为真”等价于等价于“存在一存在一些些x，A为真为真”，故，故(a)成立。由于成立。由于“不存在一不存在一些些x，A为真为真”等价于等价于“对一切对一切x，A为真为真”，所，所以以(b)成立。这两个等价式的意义是：否定联结成立。这两个等价式的意义是：否定联结词可通过量词深入到辖域中。对比这两个式子，词可通过量词深入到辖域中。对比这两个式子，容易看出，将容易看出，将(x)与与(x)两者互换，可从一两者互换，可从一个式子得到另一个式子，这表明个式子得到另一个式子，这表明(x)与与(x)具有对偶性。另外，由于这两个公式成立也表具有对偶性。另外，由于这两个公式成立也表明了，两个量词是不独立的，可以互相表示，明了，两个量词是不独立的，可以互相表示，所以只有一个量词就够了。所以只有一个量词就够了。现在学习的是第57页，共91页对于多重量词前置对于多重量词前置“”，可反复应用上面，可反复应用上面结果，逐次右移结果，逐次右移。例如，。例如，(x)(y)(z)P(x,y,z)(x)(y)(z)P(x,y,z)当量词前面的当量词前面的 移到量词的后面去时，存在移到量词的后面去时，存在量词改为全称量词，而全称量词改为存在量词，量词改为全称量词，而全称量词改为存在量词，反之，如将量词后面的反之，如将量词后面的 移到量词之前时，也要移到量词之前时，也要做相应的改变。做相应的改变。（2）量词辖域缩小或扩大等价式设设B是不含是不含x自由出现，自由出现，A(x)为有为有x约束出现约束出现的任意公式，则有：的任意公式，则有：现在学习的是第58页，共91页(a)(x)(A(x)B)(x)A(x)B(b)(x)(A(x)B)(x)A(x)B(c)(x)(A(x)B)(x)A(x)B(d)(x)(BA(x)B(x)A(x)(e)(x)(A(x)B)(x)A(x)B(f)(x)(A(x)B)(x)A(x)B(g)(x)(A(x)B)(x)A(x)B(h)(x)(BA(x)B(x)A(x)。现在学习的是第59页，共91页例例 证明证明(x)(A(x)B)(x)A(x)B.证明：证明：(x)(A(x)B)(x)(A(x)B)(x)A(x)B(x)A(x)B(x)A(x)B.例例 证明证明(x)(A(x)B)(x)A(x)B.证明证明：(x)A(x)B(x)A(x)B (x)(A(x)B(x)(A(x)B)(x)(A(x)B).现在学习的是第60页，共91页当谓词的变元与量词的指导变元不同时，当谓词的变元与量词的指导变元不同时，也有类似的公式：如也有类似的公式：如(x)(A(x)B(y)(x)A(x)B(y).(x)(y)(P(x,y)Q(z)(x)(y)P(x,y)Q(z).现在学习的是第61页，共91页(3)量词分配律等价式：(见书P70)例例：联欢会上所有的人既唱歌又跳舞；：联欢会上所有的人既唱歌又跳舞；与与 联欢会上，所有人唱歌且所有人跳舞。联欢会上，所有人唱歌且所有人跳舞。(a)(x)(A(x)B(x)(x)A(x)(x)B(x)(b)(x)(A(x)B(x)(x)A(x)(x)B(x)(b)的证明的证明：(x)(A(x)B(x)(x)A(x)(x)B(x)故故(x)(A(x)B(x)(x)A(x)(x)B(x)也即：也即：(x)(A(x)B(x)(x)A(x)(x)B(x)。现在学习的是第62页，共91页(4)多重量词等价式(a)(x)(y)A(x,y)(y)(x)A(x,y)(b)(x)(y)A(x,y)(y)(x)A(x,y)其中其中A(x,y)为含有为含有x自由出现的任意公式。自由出现的任意公式。例例 A(x,y)表示表示x和和y同姓；论域：同姓；论域：x是甲村的是甲村的人，人，y是乙村的人。是乙村的人。(x)(y)A(x,y):甲村与乙村的所有人同甲村与乙村的所有人同姓。姓。(y)(x)A(x,y)：乙村与甲村的所有人同