离散数学笔记

1、离散数学 第一章 命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的：1 熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。2 熟练掌握常用的基本等价式及其应用。3 熟练掌握（主）析/合取范式的求法及其应用。4 熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。5 熟练掌握形式演绎的方法。教学重点：1命题的概念及判断2联结词，命题的翻译3主析（合）取范式的求法4逻辑推理教学难点：1主析（合）取范式的求法2逻辑推理1.1命题及其表示法1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称

2、作命题。1.1.2 命题的表示命题通常使用大写字母A，B，Z或带下标的大写字母或数字表示，如Ai，10，R等，例如A1：我是一名大学生。A1:我是一名大学生.10：我是一名大学生。R：我是一名大学生。1.2命题联结词1.2.1 否定联结词P01101.2.2 合取联结词0000101001111.2.3 析取联结词0000111011111.2.4 条件联结词0010111001111.2.5 双条件联结词0010101001111.2.6 与非联结词001011101110性质：（1） PP（PP）P；（2）（2）（PQ）（PQ）（PQ） PQ；（3）（PP）（QQ）PQ PQ。1.2.7

3、或非联结词001010100110性质：（1）PP（PQ）P；（2）（PQ）（PQ）（PQ）PQ；（3）（PP）（QQ）PQ（PQ）PQ。1.3 命题公式、翻译与解释1.3.1 命题公式定义 命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则P是公式；（3）如果P、Q是公式，则PQ、PQ、PQ、 PQ都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。例如，下面的符号串都是公式：（P）Q）R）S）（PQ）（RS） （PQ）R以下符号串都不是公式：（PQ）（Q） （Q）1.3.2 命题的翻译 可以把自然语言

4、中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项：（1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。例：假如上午不下雨，我去看电影，否则就在家里读书或看报。解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本例可表示为： （PQ）（P（RS）。1.3.3 命题公式的解释定义 设P1，P2，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。例如，G=（PQ）R，则I：110是G的一个

5、解释，在这个解释下G的真值为1，即TI（G）=1。1.4 真值表与等价公式1.4.1 真值表定义 将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。构造真值表的方法如下：（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，Pn。 （2）列出G的2n个解释，赋值从000（n个）开始，按二进制递加顺序依次写出各赋值，直到111为止（或从111开始，按二进制递减顺序写出各赋值，直到000为止），然后从低到高的顺序列出G的层次。（3）根据赋值依次计算各层次的真值并最终计算出G的真值。例：G=（ PQ ）Q 001000110010010111001.4.2 命题公式的分类 定

6、义 设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。1.4.3 等价公式 定义 设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为AB。性质定理设A、B、C是公式，则（1）AA（2）若AB则BA（3）若AB且BC则AC定理 设A、B、C是公式，则下述等价公式成立：（1）双重否定律 AA（2）等幂律 AAA ； AAA（3）交换律 ABBA ； ABBA（4）结合律 （AB）CA（BC）（AB）CA（BC）（

7、5）分配律 （AB）C（AC）（BC）（AB）C（AC）（BC）（6）德·摩根律 （AB）AB（AB）AB（7）吸收律 A（AB）A；A（AB）A（8）零一律 A11 ； A00（9）同一律 A0A ； A1A（10）排中律 AA1（11）矛盾律 AA0（12）蕴涵等值式 ABAB（13）假言易位 ABBA（14）等价等值式 AB（AB）（BA）（15）等价否定等值式 ABABBA（16）归缪式 （AB）（AB）A1.4.4 置换规则 定理（置换规则） 设（A）是一个含有子公式A的命题公式，（B）是用公式B置换了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。1.5 对偶

8、与范式1.5.1 对偶定义 在仅含有联结词Ø、的命题公式A中，将联结词换成，将换成，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。例：公式（PQ）（PQ） 的对偶式为：（PQ）（PQ）定理 设A和A*互为对偶式，P1，P2，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则（1）A（P1，P2，Pn）A*（P1，P2，Pn）（2）A（P1，P2，Pn）A*（P1，P2，Pn） 定理（对偶原理）设A、B是两个命题公式，若AÛB，则A*B*，其中A*、B*分别为A、B的对偶式。1.5.2 范式定义 仅由有限个命题变元及

9、其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。定义 仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。1.5.3 主范式定义 在含有n个命题变元P1，P2，Pn的简单合取范式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极大项。n个命题变元P1，P2，Pn的极小项用公式

10、可表示为 Pi* ，极大项可表示为Pi*，其中，Pi*为Pi或Pi（i=1，2，n）。定义 设G为公式，P1，P2，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，Pn的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。定理 任意的命题公式都存在一个唯一的与之等价的主析取范式。 用等值演算求主析取范式步骤如下：（1） 求G的析取范式G'；（2）（2）若G中某个简单合取式m中没有出现某个命题变元Pi或其否定Pi，则将m作如下等价变换：mm（PiPi）（ mPi）（mPi）（3）将重复出现的命题变元、矛盾式和重复出现的极小项都消去；（4）重复步骤（2

11、）、（3），直到每一个简单合取式都为极小项；（5）将极小项按脚标由小到大的顺序排列，并用表示。如m0m1m7可表示为（0，1，7）。 定义 设G为公式，P1，P2，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，Pn的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用表示。重言式的主合取范式中不含任何极大项，用1表示。 定理 任意的命题公式都存在一个唯一的与之等价的主合取范式。1.6 公式的蕴涵1.6.1 蕴涵的概念定义 设G、H是两个公式，若GH是永真式，则称G蕴涵H，记作GH。蕴涵关系有如下性质：（1） 对于任意公式G，有GG；（2）（2）对任意公式G、H

12、，若GH且HG，则GH；（3） 若GH且HL，则GL。 广义的蕴涵概念 定义 设G1，G2，Gn，H是公式，如果（G1G2Gn）H是永真式，则称G1，G2，Gn蕴涵H，又称H是G1，G2，Gn的逻辑结果，记作（G1G2Gn）H或（G1，G2，Gn）H。1.6.2 基本蕴涵式（1）PQP； （2）PQQ；（3）PPQ； (4) QPQ；（5）P（PQ）； （6）Q（PQ）；（7）（PQ）P； （8）（PQ）Q；（9）P，PQQ； （10）Q，PQP；（11）P，PQQ； （12）PQ，QRPR；（13）PQ，PR，QRR； （14）PQ，RS（PR）（QS）；（15）P，QPQ。1.7 其它联结

13、词与最小联结词组1.7.1 其它联结词定义 设P、Q为命题公式，则复合命题P Q称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，PQ的真值为1，否则PQ的真值为假。定义 设P、Q是两个命题公式，复合命题P Q称为命题P、Q的条件否定，当且仅当P的真值为1，Q的真值为0时，P Q的真值为1，否则 PQ的真值为0。1.7.2 最小联结词组定义 设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S是最小全功能集，又称最小联结词组。 定理 ，是联结词的全功能集。 定理

14、 ，是联结词的全功能集。定理 ，、，是最小联结词组。 定理 ，是最小联结词组。1.8 命题逻辑推理理论1.8.1 命题逻辑推理理论定义 如果G1，G2，Gn蕴涵H，则称H能够由G1，G2，Gn有效推出，G1，G2，Gn称为H的前提，H称为G1，G2，Gn的有效结论。称（G1G2Gn）H是由前提G1，G2，Gn推结论H的推理的形式结构。1.8.2 推理规则下面给出推理中常用的推理规则。1 前提引入规则：可以在证明的任何时候引入前提；2 结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；3 置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。4

15、 言推理规则：P，PQQ5 附加规则：PPQ；6 化简规则：P，QP；7 拒取式规则： Q，PQP；8 假言三段论规则：PQ，QRPR；9 析取三段论规则：P，PQQ；10.构造性二难规则：PQ，PR，QRR；11.合取引入规则：P，QPQ1.8.3 推理常用方法1.直接证法 直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。 例 构造下列推理的证明。前提：PQ，PR，QS 结论：SR证明（1）PQ 前提引入规则 （2）PR 前提引入规则 （3）QS 前提引入规则 （4）SR （1）（2）（3）构造性二难规则2间

16、接证法 间接证法主要有如下两种情况。 （1）附加前提证明法 有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：（G1G2Gn）（RC）设（G1G2Gn）为S，则上述推理可表示为证明S（RC），即证明S（RC）为永真式。 用附加前提证明法证明下面推理。前提：P（QR），SP，Q 结论：SR证明：（1）SP 前提引入规则 （2）S 附加前提引入规则 （3）P （1）（2）析取三段论规则 （4）P（QR） 前提引入规则 （5）QR （3）（4）假言推理规则 （6）Q 前提引入规则 （7）R （5）（6）假言推理规则2）归缪法定义 设G1，G2，Gn是n个命题公式，如果G1G2Gn是可满足式，则

17、称G1，G2，Gn是相容的。否则（即G1G2Gn是矛盾式）称G1，G2，Gn是不相容的。例 用归缪法证明。前提：PQ，PR，QS 结论：SR证明（1）（SR） 附加前提引入规则 （2）SR （1）置换规则 （3）S （2）化简规则 （4）R （2）化简规则 （5）QS 前提引入规则 （6）QS （5）置换规则 （7）Q （3）（6）析取三段论 （8）PQ 前提引入规则 （9）P （7）（8）析取三段论规则 （10）PR 前提引入规则 （11）PR （10）置换规则 （12）R （9）（11）析取三段论规则 （13）RR （4）（12）合取引入规则第二章 谓词逻辑第三章本章学习目标 命题逻辑中原

18、子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。内容：谓词、量词及谓词公式等概念，基本等价式、永真蕴涵式及谓词演算的形式推理方法，谓词范式的概念教学目的：1 深刻理解个体、谓词、量词的概念。2 深刻理解原子、公式、解释的概念。3 掌握用解释的方法证明等价式和蕴涵式。4 熟练掌握谓词演算的形式推理方法。 教学重点： 1个体、谓词、量词的概念 2用解释的方法证明等价式和蕴涵式 3谓词演算的形式推理方法 教学难点： 1解释的方法证明等价式和蕴涵式 2谓词演算的形式推理方法2.1 谓词逻辑命题的符号化 1个体词 ：个体词

19、是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体 个体常项或个体常元 ： 个体变项或个体变元 ： 个体域或论域 ： 2谓词：用来刻画个体词的性质或个体词之间关系的词 一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“大于”谓词。我们把A（x）称为一元谓词,B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。 例2.1 将下列命题在谓词逻辑中符号化，并讨论它们的真值：（1）只有4是素数，8才是素数。（2）如果2小于3，则8小于7。 解（1）设谓词G（x）：x

20、是素数，a：4，b：8；（1）中的题符号化为谓词的蕴涵式：G（a）G（b）由于此蕴涵式的前件为假，所以（1）中的命题为真。（2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命题符号化为谓词的蕴涵式：H（a，b）H（c，d）由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。 例 2.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。（2）有的人天生就近视。其中：（a）个体域D1为人类集合。 （b）个体域D2为全总个体域。 解（a）令F（x）：x要死的；G（x）：x天生就近视。（1）在个体域D1中除人外，没有其他的事物，因而（

21、1）可符号化为：x F（x）（2）在个体域D1中有些人是天生就近视，因而（2）可符号化为谓词的蕴涵式：x G（x） （b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描述如下：（1） 对于宇宙间的一切事物，如果事物是人，则他是要死的。（2） 在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为： （1） x（M（x）F（x） （2） x（M（x）G（x）在个体域D1、D2中命题（1）、（2）都是真命题。 例2.3 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x

22、，都有x2-5x+6 =（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。 （b）个体域D2为实数集合。 解 （a）令F（x）：x2-5x+6 =（x-2）（x-3）；G（x）：x+1=0。（1）可符号化为：x F(x)（2）可符号化为：x G（x）在个体域D1中命题（1）为真命题，命题（2）为假命题。（b）在个体域D2中（1）、（2）符号化分别为（1） x F（x）（2） x G（x）在个体域D2中命题（1）、（2）都是真命题。 例2.4 将下列命题符号化，并指出真值情况。（1）没有人登上过月球。（2）所有人的头发未必都是黑色的。解 个体域为全总个体域，令

23、M（x）：x是人。（1）令F（x）：x登上过月球。命题（1）符号化为：x（M（x）F（x）设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）F（a）为真，故命题（1）为假。（2）令H（x）：x的头发是黑色的。命题（2）可符号化为：x（M（x）H（x）我们知道有的人头发是褐色的，所以x（M（x）H（x）为假，故命题（2）为真。 例2.5 将下列命题符号化。（1）猫比老鼠跑得快。（2）有的猫比所有老鼠跑得快。（3）并不是所有的猫比老鼠跑得快。（4）不存在跑得同样快的两只猫。解 设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y

24、跑得同样快。这4个命题分别符号化为：（1）xy（C（x）M（y）Q（x，y）；（2）x（C（x）y（M（y）Q（x，y）；（3）x y（C（x）M（y）Q（x，y）；（4）x y（C（x）C（y）L（x，y）2.2 谓词逻辑公式与解释2.2.1 谓词逻辑的合式公式 定义2.1 设P（x1，x2，xn）是n元谓词公式，其中，x1x2，xn是个体变项，则称P（x1，x2，xn）为谓词演算的原子公式。 定义2.2 谓词演算的合式公式定义如下：（1）原子公式是合式公式；（2）若A是合式公式，则（A）也是合式公式；（3）若A，B是合式公式，则（AB）、（AB）、（AB）、（AB）是合式公式；（4）若A是

25、合式公式，则x A、x A是合式公式；（5）只有有限次地应用（1）（4）构成的符号串才是合式公式。 例2.5 在谓词逻辑中将下列命题符号化。（1）不存在最大的数。（2）计算机系的学生都要学离散数学。解 取个体域为全总个体域。（1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号化为x（F（x） y（F（y） L（x，y）（2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为： x（C（x） G（x） 例2.6 将下列命题符号化。（1）尽管有人聪明，但并非所有人都聪明。（2）这只大红书柜摆满了那些古书。解 （1）令C（x）：x聪明；M（x）：x是人。则

26、命题（1）可符号化为x（M（x）C（x）x（M（x）C（x）（2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）:x是古书；a：这只；b：那些。则命题（2）可符号化为R（a）Q（b）F（a，b） 2.2.2 约束变元与自由变元 1约束变元与自由变元的概念定义 2.3 在公式x F（x）和x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。 例2.7 指出下列各式量词的辖域及变元的约束情况：（1）x（F（x，y） G（x，z）（2）x（P（x）y R（x，y）（3）x（F（

27、x） G（y） y（H（x）M（x，y，z） 解 （1）对于x的辖域是A=（F（x，y） G（x，z），在A中，x是约束出现的，而且约束出现两次，y，z均为自由出现，而且各自由出现一次。（2）对于x的辖域是（P（x）y R（x，y），y的辖域是R（x，y），x，y均是约束出现的。（3）对于x的辖域是（F（x） G（y），其中x是约束出现的，而y是自由出现的。对y的辖域是（H（x）M（x，y，z），其中y是约束出现的，而x，z是自由出现的。在整个公式中，x约束出现一次，自由出现两次，y约束出现一次，自由出现一次，z仅自由出现一次。 2约束变元的换名与自由变元的代入 例2.8 对公式x（P（x）

28、R（x，y）Q（x，y）进行换名。解 对约束变元x换名为t后为t（P（t） R（t，y）Q（x，y）同理，对公式中的自由变元也可以更改，这种更改称作代入。自由变元的代入规则是：（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。（2）用以代入的变元与原公式中所有变元的名称都不能相同。 例2.9 对公式x（F（x） G（x，y）y H（y）代入。解 对y实施代入，经过代入后原公式为x（F（x） G（x，t） y H（y）另外，量词作用域中的约束变元，当论域的元素是有限时，个体变元的所有可能的取代是可以枚举的。设论域元素为a1，a2，an，则 x A（x） A

29、（a1）A（a2）A（an） x A（x） A（a1）A（a2）A（an）。 2.2.3 谓词逻辑公式的解释 定义2.4 谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：（1）对每一个常项符号指定D中一个元素。（2）对每一个n元函数符号，指定一个函数。（3）对每一个n元谓词符号，指定一个谓词。显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，记作TI（G）。 例2.10 指出下面公式在解释I下的真值。（1）G=x（P（f（x）Q（x，f（a）；（2）H=x（P（x）Q（x，a）。给出如下的解释I：D=2，3；a：2

30、；f（2）：3、f（3）：2；P（2）：0、P（3）：1； Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；解 （1）TI（G）= TI（P（f（2）Q（2，f（2）（P（f（3）Q（3，f（2） = TI（P（3）Q（2，3）（P（2）Q（3，3） = （11）（01） = 1（2）TI（H）= TI（P（2）Q（2，2）P（3）Q（3，2） =0110=0 定义2.5 若存在解释I，使得G在解释I下取值为真，则称公式G为可满足的，简称I满足G。定义2.6 若不存在解释I，使得I满足G，则称公式G为永假式（或矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或重

31、言式）。2.3 谓词逻辑约束公式的等价与蕴涵2.3.1 谓词逻辑的等价公式 定义2.7 设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有TI（A）= TI（B），则称公式A、B在E上是等价的，记作AB。 定理1 设A（x）是谓词公式，有关量词否定的两个等价公式：（1）x A（x）xA（x）（2）x A（x）xA（x） 证明 （1）设个体域是有限的为：D= a1，a2，an，则有x A（x）（A（a1）A（a2）A（an）A（a1）A（a2）A（an） xA（x）（2）设个体域是有限的为：D= a1，a2，an，则有 x A（x）（A（a1） A（a2）A（an）

32、 A（a1） A（a2）A（an）xA（x）定理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x） B）x A（x） B（4）x（BA（x）B x A（x）（5）x（A（x）B） x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x） B）x A（x） B（8）x（BA（x）Bx A（x）证明 （1）设D是个体域，I为任意解释，即用确定的命题及确定的个体代替出现在x（A（x）B）和x A（x）B中的命题变元和个体变元，于是得到两个命题，若对x（A（x）B）代替之后所

33、得命题的真值为真，此时必有A（x）B的真值为真；因而A（x）真值为真或B的真值为真，若B的真值为真，则x A（x）B的真值为真；若B的真值为假，则必有对D中任意x都使得A（x）的真值为真，所以x（A（x）B）为真，从而x A（x）B为真。若对x（A（x）B）代替之后所得命题的真值为假，则A（x）和B的真值必为假，因此x A（x）B的真值为假；所以x（A（x）B）为假，有x A（x）B为假。（2）、（5）和（6）证明与（1）类似，证明过程略。（3）x（A（x） B）x（A（x）B） xA（x） B x A（x）B x A（x） B（4）、（7）、（8）证明与（3）类似，证明过程略。 定理3 设A

34、（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） 证明 （1）设D是任一个体域，若x（A（x）B（x）的真值为真，则对任意aD，有A（a）和B（a）同时为真，即x A（x）为真、x B（x）为真，从而x A（x）x B（x）为真。若x（A（x）B（x）的真值为假，则对任意aD，有A（a）和B（a）不能同时为真，即x A（x）和 x B（x）的真值不能同时为真，从而x A（x）x B（x）的真值为假。综上所述 x（A（x）B（x）x A（x）x B（x） （2）设D是任一个体域，若x（A

35、（x）B（x）的真值为真,则存在aD，使得A（a）B（a）为真，即A（a）为真或B（a）为真，即x A（x）为真或x B（x）为真，从而x A（x）x B（x）为真。若x（A（x）B（x）的真值为假，则存在aD，使得A（a）B（a）为假，此时，A（a）为假，B（a）为假，从而x A（x）x B（x）的真值为假。综上所述 x（A（x）B（x）x A（x）x B（x） 例2.11 证明下列各等价式（1）x（A（x）B（x）x（A（x）B（x）（2）x（A（x） B（x）x（A（x）B（x）证明 （1）x（A（x）B（x） x （A（x）B（x） x（A（x）B（x） x（A（x）B（x） （2）x

36、（A（x） B（x） x （A（x） B（x） x （A（x）B（x） x（A（x）B（x） 2.3.2 谓词逻辑的蕴涵公式 定义2.8 设A、B是命题逻辑中的任意两个公式，若AB是永真式，则称公式A蕴涵公式B，记作AB。 定理4 下列蕴涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x） B（x）x A（x） x B（x）（4）x（A（x） B（x）x A（x） x B（x）（5）x A（x） x B（x）x（A（x） B（x） 证明： （1）设x A（x）x B（x）在任意解释下的真值为真，即对个体域中的每一个x。都

37、能使A（x）的真值为真或者对个体域中的每一个x都能使B（x）的真值为真，无论哪种情况，对于个体域中的每一个x都能使A（x）B（x）的真值为真。因此，蕴涵式x A（x）x B（x）x（A（x）B（x）成立。 （2）设个体域为D，在解释I下x（A（x）B（x）的真值为真，即存在aD使得A（a）B（a）为真，从而A（a）为真，B（a）为真，故有x A（x）、x B（x）均为真，所以，蕴涵式x（A（x）B（x）x A（x）x B（x）成立。（3）设个体域为D，在解释I下x A（x） x B（x）的真值为假,即存在aD使得A（a） B（a）为假，所以蕴涵式x（A（x） B（x）x A（x） x B（x）

38、成立。（4）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） 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）（5）x A（x） x B（x）x A（x）x B（x） x A（x）x B（x） x（A（x）B（x） x（A（x） B（x） 2.3.3 多个量词的使用 定义2.9 设谓词公式G，不包含联结词，。把G中出现的联结词，互换；命题常量T，F互换；量词，互换之后得到的公式称为G的对偶公式，

39、记作G*。 定理5（对偶定理） 设A、B是任意两个公式并且不包含联结词，。若AB，则A*B*。2.4 前束范式 定义2.10 一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。 定理6 对任意一个谓词公式都可以化为与它等价的前束范式。证明 首先利用等价公式将谓词公式中的联结词，去掉。其次利用量词的转化律将量词前面的否定深入到谓词前面，在利用改名和代入规则以及量词辖域扩张的公式将量词移到全式的最前面，这样便得到前束范式。 例2.12 求下列谓词公式的前束范式。（1）x y（z A（x，z）A（x，z）t B（x，y，t）解 （1）x y（z A（x，z）A（x，

40、z） t B（x，y，t） x y（z A（x，z）A（x，z）t B（x，y，t） x y（zA（x，z）A（x，z）t B（x，y，t） （量词转化） x y（wA（x，w）A（x，z）t B（u，v，t） （改名及代入规则） x y w t（A（x，w）A（x，z）B（u，v，t）（量词辖域扩张）（2）x（y P（x，y） x y（Q（x，y）y（P（y，x）Q（x，y） 解 （2）x（y P（x，y） x y（Q（x，y）y（P（y，x）Q（x，y） x（y P（x，y）x y（Q（x，y）y（P（y，x）Q（x，y） x（y P（x，y）xy（Q（x，y）y（P（y，x） Q（x，y

41、） （量词转化、德·摩根定律） x（y P（x，y）x y（Q（x，y）z（P（z，x）Q（x，z） （改名原则）x（y P（x，y）x y z（Q（x，y）（P（z，x）Q（x，z） （量词辖域扩张） x（y P（x，y）u v z（Q（u，v）（P（z，u）Q（u，z） （改名原则）x y u v z （P（x，y）（ Q（u，v）（P（z，u）Q（u，z） （量词辖域扩张） 定义2.11 若一个谓词公式，具有如下形式，则称该公式为前束析取范式。 定义2.12 若一个谓词公式，具有如下形式，则称该公式为前束合取范式。 定理7 任意谓词公式都可以化为与其等价的前束析取范式和前束合取

42、范式。2.5 谓词演算的推理理论 1全称指定规则（简称US规则） 这条规则有下面两种形式：(1)x P（x）P（y）(2)x P（x）P（c）其中，P是谓词，（1）中y为任意不在P（x）中约束出现的个体变元；（2）中c为个体域中的任意一个个体常元。 2存在指定规则（简称ES规则） x P（x）P（c）其中，c为个体域中使P成立的特定个体常元。必须注意，应用存在指定规则，其指定的个体c不是任意的。 3全称推广规则（简称UG规则） P（y）x P（x） 4存在推广规则（简称EG规则）P（c）x P（x）其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有x

43、 P（x）。 例2.13 证明 x（M（x） D（x）M（s）D（s）这是著名的苏格拉底三段论的论证。其中 M（x）：x是一个人。 D（x）：x是要死的。 s：苏格拉底。证明 （1）x（M（x） D（x） P （2）M（s） D（s） US（1） （3）M（s） P （4）D（s） T（2）（3）I 例 2.14 判断下列的推理过程是否正确。 （1）x y G（x，y） P （2）y G（z，y） US（1） （3）G（z，c） ES（2） （4）x G（x，c） UG（3） （5）y x G（x，y） EG（4） 解 这个推理过程是错误的，因为从它可以得出结论： x y G（x，y）y x G（x，y）从前面的学习中我们知道这个式子不成立。它的推导错误出现在第（3）步。x y G（x，y）的含义是：对于任意的一个x，存在着与它对应的y，使得G（x，y）成立。但是，对y G（z，y）利用ES规则消去存在变量后得到G（z，c）的含义却是：对于任意个体z，有同一个体c，使得G（z，c）成立。显然，G（z，c）不是y G（z，y）的有效结论。因此，使用ES规则x P（x）P（c）消去存在量词的条件是:P（x）中除x外没有