离散数学电子教材

1、-PAGE . z.第1章 命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。辩证逻辑是研究反映客观世界辩证开展过程的人类思维的形态的。形式逻辑是研究思维的形式构造和规律的科学，它撇开具体的、个别的思维内容，从形式构造方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式构造和推理的规律的数学学科。所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。因此数理逻辑也称为符号逻辑。数理逻辑的根底局部是命题逻辑和谓词逻辑。本章主要讲述命题逻辑，谓词逻辑将在第2章进展讨论。1.1命题及其表示1.1.1命题的根本概念数理逻辑研究的中心问题是推理Infer

2、ence)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的根本要素。在数理逻辑中，将能够判断真假的陈述句称为命题。因此命题就成为推理的根本单位。在命题逻辑中，对命题的组成局部不再进一步细分。定义1.1.1能够判断真假的陈述句称为命题Proposition。命题的判断结果称为命题的真值，常用 T(True)或1表示真，F(False)或0表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。判断以下句子是否为命题是中国的首都。请勿吸烟！雪是

3、黑的。明天开会吗？*+y=5。我正在说谎。9+512。1+101=110。今天天气多好啊！别的星球上有生物。解 在上述的十个句子中，2、9为祈使句，4为疑问句，5、6虽然是陈述句，但5没有确定的真值，其真假随*、y取值的不同而有改变，6是悖论(Parado*)即由真能推出假，由假也能推出真，因而2、4、5、6、9均不是命题。1、3、7、8、10都是命题，其中10虽然现在无法判断真假，但随着科技的进步是可以判定真假的。需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例 的81+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题。还有的

4、命题的真假不能马上给出，如例1.1.1 的10，但它确实有真假意义。命题分类根据命题的构造形式，命题分为原子命题和复合命题。定义不能被分解为更简单的陈述语句的命题称为原子命题(Simple Proposition )。由两个或两个以上原子命题组合而成的命题称为复合命题(pound Proposition )。例如，例中的命题全部为原子命题，而命题小王和小李都去公园。是复合命题，是由小王去公园。与小李去公园。两个原子命题组成的。命题标识符定义表示原子命题的符号称为命题标识符(Identifier)。通常用大写字母A，B，C，P，Q，等表示命题，如P：今天下雨。命题标识符依据表示命题的情况，分为命

5、题常元和命题变元。一个表示确定命题的标识符称为命题常元或命题常项(Propositional constant)；没有指定具体内容的命题标识符称为命题变元或命题变项(Propositional Variable)。命题变元的真值情况不确定，因而命题变元不是命题。只有给命题变元P一具体的命题取代时，P有了确定的真值，P才成为命题。习题1.1判断以下语句是否为命题，假设是，指出其真值。外面下雨吗？7能被2 整除。2*+34。2燕子北回，春天来了。1设P：雪是黑色的。Q：2+24。则1可表示为PQ，其真值为T。2设R：燕子北回。S：春天来了。则2可表示为R S，其真值为T。与前面的联结词一样，条件联

6、结词和双条件联结词连接的两个命题之间可以没有任何的因果联系，只要能确定复合命题的真值即可。习题1.21指出以下命题的真值：假设2+24，则太阳从西方升起。假设a，则aA。 胎生动物当且仅当是哺乳动物。 指南针永指北方，除非它旁边有磁铁。除非ABCD 是平行四边形,否则它的对边不都平行。2令P：天气好。Q：我去公园。请将以下命题符号化。如果天气好，我就去公园。只要天气好，我就去公园。只有天气好，我才去公园。我去公园，仅当天气好。 或者天气好，或者我去公园。天气好，我去公园。1.3命题公式与翻译命题公式上一节介绍了5种常用的逻辑联结词，利用这些逻辑联结词可将具体的命题表示成符号化的形式。对于较为复

7、杂的命题，需要由这5种逻辑联结词经过各种相互组合以得到其符号化的形式，则怎样的组合形式才是正确的、符合逻辑的表示形式呢？定义1单个的命题变元是命题公式。2如果是命题公式，则也是命题公式。3如果、是命题公式，则(),), ()和()也是命题公式。 4当且仅当能够有限次地应用1、2、3所得到的包含命题变元、联结词和括号的符号串是命题公式又称为合式公式，或简称为公式。上述定义是以递归的形式给出的，其中1称为根底，2、3称为归纳，4称为界限。由定义知,命题公式是没有真假的，仅当一个命题公式中的命题变元被赋以确定的命题时，才得到一个命题。例如在公式中，把命题雪是白色的。赋给，把命题2+24。赋给，则公式

8、被解释为假命题；但假设的赋值不变，而把命题2+2=4。赋给，则公式被解释为真命题。定义中的符号,不同于具体公式里的、等符号，它可以用来表示任意的命题公式。例，等都是命题公式，而，等都不是命题公式。为了减少命题公式中使用括号的数量，规定：1逻辑联结词的优先级别由高到低依次为、。2具有一样级别的联结词，按出现的先后次序进展计算，括号可以省略。3命题公式的最外层括号可以省去。也可以写成，也可写成，也可写成，而中的括号不能省去。定义 设是命题公式的一局部，且也是命题公式，则称为的子公式。例如及都是公式的子公式；、及都是公式的子公式。 命题的符号化 有了命题公式的概念之后，就可以把自然语言中的一些命题翻

9、译成命题逻辑中的符号化形式。把一个文字描述的命题相应地写成由命题标识符、逻辑联结词和圆括号表示的命题形式称为命题的符号化或翻译。命题符号化的一般步骤：1明确给定命题的含义；2找出命题中的各原子命题，分别符号化。3使用适宜的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化形式。把命题符号化，是不管具体内容而突出思维形式的一种方法。注意在命题符号化时，要正确地分析和理解自然语言命题，不能仅凭文字的字面意思进展翻译。 *三或李四都可以做这件事。设：*三可以做这件事。：李四可以做这件事。则命题符号化为：，而不是。 1只有你走，我才留下。这个命题的意义也可以理解为：如果我留下了，则你一定走了。设

10、：你走。：我留下。则命题符号化为：。与原命题类似的命题如：仅当你走我才留下。我留下仅当你走。当我留下你得走。注意：在一般的命题表述中，仅当是必要条件，译成条件命题时其后的命题是后件，而当是充分条件，译成条件命题时其后的命题是前件。2仅当天不下雨且我有时间，我才上街。设：天下雨。：我有时间。：我上街。命题符号化为：。3你将失败，除非你努力。这个命题的意义可以理解为：如果你不努力，则你将失败。设：你努力。：你失败。则命题符号化为：。含有除非的命题，非是充分条件，译成条件命题时，非是条件的前件。4中没有元素，就是空集。设：中有元素。：是空集。则命题符号化为：5*三与李四是表兄弟。此命题是一个原子命题

11、，与是表兄弟。表示两个对象之间的关系。*三是表兄弟。及李四是表兄弟。都不是命题。所以上述命题只能符号化为的形式。其中：*三与李四是表兄弟。例 将以下命题符号化。如果明天早上下雨或下雪，则我不去学校。如果明天早上不下雨且不下雪，则我去学校。如果明天早上不是雨夹雪，则我去学校。当且仅当明天早上不下雨且不下雪时，我才去学校。设：明天早上下雨。：明天早上下雪。：我去学校。符号化为：符号化为：符号化为：符号化为：例将以下命题符号化。如果小王和小*都不去，则小李去。如果小王和小*不都去，则小李去。设：小王去。：小*去。：小李去。符号化为：符号化为：或例 将以下命题符号化。1说离散数学无用且枯燥无味是不对的

12、。2假设天不下雨，我就上街；否则在家。对于1，设：离散数学是有用的。：离散数学是枯燥无味的。则命题符号化为：。对于2，设：天下雨。：我上街。：我在家。则命题符号化为：。通过上述的例题可以看出，要正确地将自然语言中的联结词翻译成恰当的逻辑联结词，必须要正确地理解各原子命题之间的关系。习题1.31判断以下各式子是否是命题公式1234562将以下命题符号化句中括号内提示的是相应的原子命题的符号表示1我去新华书店，仅当我有时间。2我们不能既划船又跑步。3只要努力学习，成绩就会好的。4或者你没有给我写信，或者它在路上丢了。5如果上午不下雨，我就去看电影，否则我就在家里读书或看报纸。6我今天进城，除非下雨

13、。7如果太阳没出来，则或者下雨或者阴天而且温度下降。8指南针永指南北，除非它旁边有磁铁。9说逻辑枯燥无味和毫无价值是不对的。10人不犯我，我不犯人；人假设犯我，我必犯人。1.4真值表与等价公式真值表定义 设，是出现在命题公式中的全部命题变元，给，各指定一个真值，称为对公式的一个赋值或解释或真值指派。假设指定的一组值使公式的真值为1，则这组值称为公式的成真赋值。假设指定的一组值使公式的真值为0，则这组值称为公式的成假赋值。例如，对公式，赋值011即令，则可得到公式的真值为1；假设赋值000，则公式真值为0。因此，011为公式的一个成真赋值；000为公式的一个成假赋值。除了上述的两种赋值外，公式的

14、赋值还有000，001，等。一般的结论是在含有n个命题变元的命题公式中，共有种赋值。定义 将命题公式在所有赋值下的取值情况列成表，称为公式的真值表(Truth Table)。构造真值表的根本步骤：1找出公式中所有的命题变元，按二进制从小到大的顺序列出种赋值。2当公式较为复杂时，按照运算的顺序列出各个子公式的真值。3计算整个命题公式的真值。 写出以下公式的真值表，并求其成真赋值和成假赋值。123解1的真值表见表1-6。表1-6的真值表0011011110001101成真赋值为00，01，11，成假赋值为10。2的真值表见表1-7。表1-7的真值表00100011001001011100无成真赋值

15、，成假赋值为00，01，10，11。3的真值表见表1-8。表1-8的真值表000111010111100111111001成真赋值为00，01，10，11，无成假赋值。 等价公式定义 给定两个命题公式，设，是出现在命题公式中的全部命题变元，假设给，任一组赋值，公式和的真值都对应一样，则称公式与等价或逻辑相等(Equivalence)，记作。需要注意的是，不是逻辑联结词，因而不是命题公式，只是表示两个命题公式之间的一种等价关系，即假设，和没有本质上的区别，最多只是和具有不同的形式而已。具有如下的性质：1自反性：。2对称性：假设，则。3传递性：假设，则。给定n个命题变元，根据公式的形成规则，可以形

16、成许多个形式各异的公式，但是有很多形式不同的公式具有一样的真值表。因此引入公式等价的概念，其目的就是将复杂的公式简化。下面介绍两种证明公式等价的方法。1真值表法由公式等价的定义可知，利用真值表可以判断任何两个公式是否等价。例 证明证明命题公式与的真值表见表1-9。由表1-9可知，在任意赋值下与两者的真值均对应一样。因此表1-9与的真值表001111011000100100111111例 判断公式与二者是否等价。证明公式与的真值表见表1-10。表1-10与的真值表0011011010011111可见真值表中的最后两列值不完全一样，因此公式与不等价。从理论上来讲，利用真值表法可以判断任何两个命题公

17、式是否等价，但是真值表法并不是一个非常好的方法，因为当公式中命题变元较多时，其计算量较大，例如当公式中有四个变元时，需要列出=16种赋值情况，计算较为繁杂。因此，通常采用其他的证明方法。这种证明方法是先用真值表法验证出一些等价公式，再用这些等价公式来推导出新的等价公式，以此作为判断两个公式是否等价的根底。下面给出12组常用的等价公式，它们是进一步推理的根底。牢记并熟练运用这些公式是学好数理逻辑的关键之一。1双重否认律：2结合律：，3交换律：，4分配律：，5幂等律：，6吸收律：，7德.摩根律：，8同一律：9零律：10否认律：11条件等价式：12双条件等价式：上述12组公式均可以通过构造真值表法来

18、证明。2等值演算法定理代入规则在一个永真式中，任何一个原子命题变元出现的每一处用另一个公式代入，所得的公式仍为永真式。证明：因为永真式对于任何指派，其真值都是1，与每个命题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元出现的每一处，所得到的命题公式的真值仍为1。例如，是永真式，将原子命题变元用代入后得到的式子仍为永真式。定理置换规则 设是命题公式的一个子公式，假设，如果将公式中的用来置换，则所得到的公式与公式等价，即。证明：因为，所以在相应变元的任一种指派情况下，与的真值一样，故以取代后，公式与公式在相应的指派情况下真值也必一样，因此。例如，利用置换，则。从定理可以看出，代入规则是

19、对原子命题变元而言，而置换规则可对命题公式进展；代入必须处处代入，替换可以局部或全部替换；代入规则可以用来扩大永真式的个数，替换规则可以增加等价式的个数。有了上述的12组等价公式及代入规则和置换规则后，就可以推演出更多的等价式。由等价式推出另外一些等价式的过程称为等值演算(Equivalent Calculation)。 证明以下公式等价。12证明12例*件事情是甲、乙、丙、丁4人中*一个人干的。询问4人后答复如下：1甲说是丙干的；2乙说我没干；3丙说甲讲的不符合事实；4丁说是甲干的。假设其中3人说的是真话，一人说假话，问是谁干的？解设：这件事是甲干的。：这件事是乙干的。：这件事是丙干的。：这

20、件事是丁干的。4个人所说的命题分别用、表示，则1、2、3、4分别符号化为：；则3人说真话，一人说假话的命题符号化为：其中同理所以，当为真时，为真，即这件事是甲干的。此题也可以从题干直接找出相互矛盾的两个命题作为解题的突破口。甲、丙两人所说的话是相互矛盾的，必有一人说真话，一人说假话，而4个人中只有一人说假话，因此乙、丁两人必说真话，由此可断定这件事是甲干的。例在*次球赛中，3位球迷甲、乙、丙对*球队的比赛结果进展猜想。甲说：该球队不会得第一名，是第二名。乙说：该球队不会得第二名，是第一名。丙说：该球队不会得第二名，也不会是第三名。比赛完毕后，结果证实甲、乙、丙3人中有一人猜的全对，有一人猜对一

21、半，有一人猜的全错。试分析该球队终究是第几名。解设：该球队获得第一名。：该球队获得第二名。：该球队获得第三名。则、中必然有一个真命题，两个假命题。设甲、乙、丙3人所说的命题分别用，表示。则有，。设甲、乙、丙的判断全对分别用、表示，甲、乙、丙的判断对一半分别用、表示，甲、乙、丙的判断全错分别用、表示。则有：。由于该球队不可能既是第一名又是第二名，所以。甲、乙、丙3人中有一人全对，有一人猜对一半，有一人全错的命题符号化为其中，。同理，由于该球队不可能既是第一名，又是第三名，。因此，假设为真，只有为真。因而为真命题，为假命题。即该球队获得第二名。甲的判断全对，乙的判断全错，丙的判断对一半。例、 4人

22、进展百米竞赛，观众甲、乙、丙比照赛的结果进展预测。甲：第一，第二；乙：第二，第三；丙：第二，第四。比赛完毕后发现甲、乙、丙每个人的预测结果都各对一半。试问实际名次如何假设无并列者？解设表示第名，表示第名，表示第名，表示第名，。则由题意有 1 2 3因为真命题的合取仍为真命题，所以12 434因此，第二，第四，第一，第三。习题1.41写出以下公式的真值表。12342证明以下等价公式。12343甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说：不是我。乙说：是丁。丙说：是乙。丁说：不是我。4个人的答复只有一个人符合实际，问成绩最好的是谁？ 43个球迷估计比赛结果，球迷甲说：*实德第一，国

23、安第二。球迷乙说：*申花第二，*亚泰第四。球迷丙说：*实德第二，*亚泰第四。结果3人估计的都不全对，但都对了一半，问4支球队的名次假设无并列次序。5如果，是否有？如果，是否有？如果，是否有？6化简以下公式：12 31.5 命题公式的分类与蕴含式 命题公式的分类从前述的真值表中可以看到，有的命题公式无论对命题欧变元作何种赋值，其对应的真值恒为或恒为，如例的2、3；而有的公式对应的真值则是有有，如例1.4.1的1。根据命题公式在不同赋值下的真值情况，可以对命题公式进展分类。定义 设为一命题公式，对公式所有可能的赋值：1假设的真值永为，则称公式为重言式(Tautology)或永真式。2假设的真值永为

24、，则称公式为矛盾式(Contradictory)或永假式。3假设至少存在一种赋值使得的真值为，则称公式为可满足式(Satisfiable)。由定义可知，根据命题公式的真值情况，公式可分为两大类，即矛盾式和可满足式。重言式一定是可满足式，但反之不成立。用真值表法可以判定公式的类型：假设真值表的最后一列全为1，则公式为重言式；假设最后一列全为0，则公式为矛盾式；假设最后一列至少有一个1，则公式为可满足式。在1.4的例中，1为可满足式，2为矛盾式，3为重言式。用真值表法判断公式的类型方法简单，但当变元较多时，计算量大，在后面的章节中还要介绍其他的方法。重言式与矛盾式的性质定理 任何两个重言式的析取或

25、合取，仍是一个重言式。证明：设、为两个重言式，则无论对与的分量作何种指派，总有，故，。定理一个重言式，对同一分量用任何合式公式置换，所得公式仍为一重言式。证明：因为重言式的真值与分量的指派无关，所以对同一分量用任何合式公式置换后，重言式的真值仍永为真。例如，为一重言式，用置换，所得新公式仍为重言式。对于矛盾式，也有类似于定理和定理1.5.2的结果。定理设、为两个命题公式，当且仅当为重言式。证明：假设，则在、所含命题变元的任何指派下，与的真值都一样，即恒为真。假设为重言式，由重言式的定义知，在对、所含命题变元的任何指派下，与都有一样的真值，即。例证明为重言式。证明由例知，故依据定理1.5.3有为

26、重言式。蕴含式下面讨论的重言式。定义 设、为两个命题公式，假设为重言式，则称蕴含( Implication)，记作。注意与一样，都不是逻辑联结词，因而也不是公式。是用来表示由条件能够推导出结论，或称为可以由逻辑推出。蕴含关系具有如下的性质：1自反性：对任意的公式，有。2反对称性：对任意的公式、，假设且，则有。3传递性：对任意的公式、，假设、，则有。由于不具有对称性，即与不等价，因此，对于而言，称为它的逆换式，称为它的反换式，称为它的逆反式。在上述的4个公式中，。定理的充分必要条件是且。证明：假设，则为重言式，而，故均为重言式，即且。反之，假设且，则均为重言式，于是为重言式，即为重言式，故。由定

27、义知，要证明，只需证明为重言式即可。因此，前面介绍的真值表法和等值演算法均可应用。下面综合介绍证明的各种方法。1真值表法例 证明证明只需证明为重言式。真值表见表1-11。表1-11的真值表00010101100111112等值演算法例 证明证明只需证明为重言式。即3分析法分析法包括以下两种形式：1假定前件为真，推出后件为真，则。2假定后件为假，推出前件为假，则。理由是：1假设为真，则可能为真也可能为假，但由假设推出为真，所以否认了为真、为假的可能，只能是为真、也为真。所以为重言式，即。对于2，假设后件为假，则前件可能为真也可能为假。假设为真，为假，则为假；假设为假，为假，则为真。而由假设推知为

28、假，因此否认了为真，为假的可能。所以为重言式，即。例证明12证明1假设前件为真，则为真，为真；由此有为假，为真。因此。2假设后件为假，假设为真，则为假，有为假。假设为假，则为真，有为假。综上，假设后件为假，无论为真还是假，前件均为假。因此。需要指出的是，在例的2中，因为不知道的真值情况，所以要分情况讨论。例1.5.5 分析以下论证的有效性。 条件：香烟有利于安康； 如果香烟有利于安康，则医生就会把香烟作为药品开给病人。结论：医生把香烟作为药品开给病人。解设：香烟有利于安康。：医生把香烟作为药品开给病人。上述推理符号化为：。其证明同例的2。因此上述论证是有效的。下面给出的蕴含式其正确性均可用上述

29、的推理方法进展证明。1234567891011121314习题1.51判断以下命题公式的类型。1。2。3。4。2证明以下各蕴含式。12343判断以下命题的真假。1重言式的否认是矛盾式。2矛盾式的否认是重言式。3不是重言式就是矛盾式。4不是矛盾式就是重言式。5重言式必是可满足式。6不是矛盾式就是可满足式。7可满足式未必是重言式。8不是可满足式就是矛盾式。4设P表示命题8是偶数，Q表示命题糖果是甜的。试以句子写出：1。2的逆换式。3的反换式。4的逆反式。5表达以下各个命题的逆换式和逆反式，并以符号写出。1如果下雨，我不去。2仅当你走我将留下。3如果我不能获得更多帮助，我不能完成这个任务。6检验以下

30、论证的有效性。如果我学习，则我数学不会不及格。如果我不热衷于玩扑克，则我将学习。但我数学不及格。因此，我热衷于玩扑克。7用符号写出以下各式并且验证论证的有效性。如果6是偶数，则7被2除不尽。或5 不是素数，或7被2除尽。但5是素数。所以6是奇数。8证明，Q逻辑蕴含P。1.6 其它逻辑联结词和最小功能完备联结词组其它逻辑联结词 前面介绍了5种常用的逻辑联结词，和，但是这5种联结词还不能很广泛地直接用来表达命题间的联系，为此，下面再介绍4种联结词。1不可兼析取(排斥或/异或)(e*clusive or)定义设、为两个命题公式，复合命题称为异或。规定的真值为，当且仅当与的真值不一样，否则的真值为。联

31、结词的定义见表1-12。表1-12 联结词的定义000011101110从真值表中易见，。利用真值表法，易证具有如下性质：12345；6假设，则，且为一矛盾式。2与非联结词(Nand)( ) 定义 设、为两个命题公式，复合命题称为和的与非式。当且仅当与的真值都为时，的真值为，否则的真值为。联结词的定义见表1-13。表1-13 联结词的定义001011101110从真值表中易见，。联结词具有如下性质：1233或非联结词(Nor)定义 设、为两个命题公式，复合命题称为和的或非式。当且仅当与的真值都为时，的真值为，否则的真值为。联结词的定义见表1-14。表1-14 联结词的定义00101010011

32、0从真值表中易见，。联结词具有如下性质：1234条件否认联结词(Non-conditional)定义 设、为两个命题公式，复合命题称为和的条件否认。当且仅当的真值为，的真值为时，的真值为，否则的真值为。联结词的定义见表1-15。表1-15 联结词的定义000010101110从真值表中易见，。 最小功能完备联结词组到目前为止，共定义了9个联结词，但这些联结词在表达命题时并不是缺一不可，因为包含*些联结词的公式可以用含有另外一些联结词的公式来进展表示。如这说明可以转化为，而可转化为由与表示，而与又可以相互转化。对于另外的4个联结词，由于，这说明任意的一个命题公式最终都可以转化为仅包含，或，的命题

33、公式来等价地表示。定义 设是一个联结词的集合，假设任意一个命题公式都可用中联结词构成的公式来表示，则称为功能完备联结词组。如果在中去掉任何一个联结词后都不再具有这种性质，则称为最小功能完备联结词组，简称为最小联结词组。可以证明，等都是功能完备联结词组，而，及，均为最小功能完备联结词组。由联结词及的性质知，联结词、和可分别用 或表示，所以及也是最小功能完备联结词组。通常为了命题表示的简洁清楚，常用包含，的联结词组来表示命题。习题1.61将以下命题公式转化为仅含联结词的命题公式。1232将以下命题公式用只含和的等价式表达，并要求尽可能简单。1233证明不是最小功能完备连接词组。4证明是最小功能完备

34、连接词组。1.7 对偶与*式对偶式与对偶原理 1对偶式定义 在只含有逻辑联结词，的命题公式中，假设把与互换，与互换得到一个新的命题公式，则称是的对偶式(Dualistic Formula)，或称与互为对偶式。显然。例1.7.1 写出以下公式的对偶式。123解上述公式的对偶式为123例 求，的对偶式。解因为，所以的对偶式为。同理，的对偶式为。2对偶原理(Duality Principle) 一个仅含有逻辑联结词，的命题公式和它的对偶式之间具有如下等值关系：定理设公式为仅含有逻辑联结词，及命题变元，的命题公式，是的对偶式，则有：12证明：由德.摩根定律，故同理例 设，证明证明因为，所以，而所以定理

35、对偶原理假设公式，则。证明：设，是出现在命题公式，中所有的命题变元，因为，即，所以。由定理得，即为重言式故也为重言式即对偶定律说明，利用公式的对偶式可以扩大等价式的数量，也可以简化证明。例如与这两个等价公式的两端互为对偶式，因而只需证明一个等价公式成立即可。命题公式的*式从前面的讨论可知,存在大量互不一样的命题公式，实际上互为等价，因此，有必要引入命题公式的标准形式，使得相互等价的命题公式具有一样的标准形式。这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法，同时对命题公式的简化和推证也是十分有益的。1简单析取式与简单合取式定义 单个的命题变元及其否认形式称为文字。如，等。定义

36、 仅由有限个文字组成的析取式称为简单析取式。仅由有限个文字组成的合取式称为简单合取式。例如，等都是简单析取式；，等都是简单合取式。一个文字既是简单析取式，又是简单合取式。定理简单析取式是重言式当且仅当它同时含有*个命题变元及其否认形式。证明：设公式为简单析取式，含有命题变元。假设同时含有及，显然为重言式。假设为重言式但不同时含有*个命题变元及其否认形式，不妨设，假设真值均为0，而真值均为1，则的真值为0，这与为重言式矛盾。对于简单合取式也有类似的性质。定理简单合取式是矛盾式当且仅当它同时含有*个命题变元及其否认形式。证明同定理。2析取*式与合取*式定义由有限个简单合取式组成的析取式称为析取*式

37、Disjunctive Normal Form。由有限个简单析取式组成的合取式称为合取*式Conjunctive Normal Form。析取*式与合取*式统称为*式。例如，等是析取*式。，等是合取*式。对于单独的一个命题变元或其否认既可以看成是析取*式，又可看成是合取*式。当然既可以看成是简单析取式，又可以看成是简单合取式。至于，假设把它看作为简单合取式的析取，则它是析取*式；假设把它看成是文字的析取，则它是合取*式。同理，等既是析取*式，又是合取*式。定理*式存在定理任何一个命题公式都存在着与之等价的析取*式和合取*式。从析取*式和合取*式的定义可知，*式中不存在除了，以外的其余逻辑联结词

38、。下面给出求公式*式的步骤：1消去除，以外公式中出现的所有逻辑联结词。2将否认联结词消去或内移到各命题变元之前。如，；。3利用分配律、结合律将公式转化为合取*式或析取*式。如，；。例 求的析取*式和合取*式。解析取*式 合取*式例 求的析取*式。解上面所求的最后两个等价的公式都是原公式的析取*式，所以命题公式的析取*式不唯一。例 求的合取*式。解上面所求的最后两个等价的公式都是原公式的合取*式，所以命题公式的合取*式不唯一。3*式的应用利用*式判断命题公式类型的问题称为判定问题。定理 一个析取*式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取*式是重言式当且仅当它的每个简单析取式都是重

39、言式。例判断以下公式的类型。12解1 由定理可知，为矛盾式。2由定理可知，为重言式。命题公式的主析取*式和主合取*式由于一个命题公式的*式不唯一，这就使得*式的应用受到了一定的限制，为了使任意命题公式化为唯一的标准形式，下面引入主*式的概念。1主析取*式定义 在含有n个命题变元的简单合取式中，假设每个命题变元及其否认不同时出现，而二者之一必出现且仅出现一次，则称该简单合取式为小项。例如，两个命题变元和生成的4个小项为：，。三个命题变元，和生成的8个小项为：，。 一般说来，n个命题变元共有个小项。小项的二进制编码为：命题变元按字母顺序排列，命题变元与1对应，命题变元的否认与0对应，则得到小项的二

40、进制编码，记为m,其下标是由二进制编码转化的十进制数。n个命题变元形成的个小项，分别记为：，。表1-16列出了两个命题变元和生成的4个小项的真值表。表1-16 两个命题变元和生成的4个小项的真值表二进制001000010100100010110001十进制从这个真值表中可以看到，没有两个小项是等价的，且每个小项都只对应着和的一组真值指派使得该小项的真值为1。这个结论可以推广到3个及3个以上变元的情况。由真值表可得到小项具有如下性质：1各小项的真值表都不一样。2每个小项当其真值指派与对应的二进制编码一样时，其真值为真，在其余种指派情况下，其真值均为假。3任意两个小项的合取式是矛盾式。例如=4全体

41、小项的析取式为永真式。定义由假设干个不同的小项组成的析取式称为主析取*式(The PrincipalDisjunctive Normal Form )。与公式等价的主析取*式称为的主析取*式。定理任意含个命题变元的非永假式命题公式都存在着与之等价的主析取*式，并且其主析取*式是唯一的。证明：设是公式的析取*式，即。假设的*个简单合取式中不含有命题变元及其否认，将展成形式，继续这个过程，直到所有的简单合取式成为小项。然后消去重复的项及矛盾式后，得到公式的主析取*式。下证唯一性。假设公式有两个与之等价的主析取*式和，则。由于和是的不同的主析取*式，不妨设小项只出现在中而不在中，于是的二进制表示为的

42、成真赋值、的成假赋值，这与矛盾。因而公式的主析取*式是唯一的。一个命题公式的主析取*式可通过两种方法求得，一是由公式的真值表得出，即真值表法；另一是由根本等价公式推出，即等值演算法。1真值表法定理 在真值表中，命题公式的真值为真的赋值所对应的小项的析取即为命题公式的主析取*式。证明：设命题公式的真值为真的赋值所对应的小项为，。令=。下证，即证与在相应指派下具有一样的真值。首先，对为真的*一指派，其对应的小项为，则因为为，而，均为，所以=为真。其次，对为假的*一指派，则其赋值所对应的小项一定不是，中的*一项，即，均为假，所以=为假。综上，。利用真值表法求主析取*式的根本步骤为：1列出公式的真值表

43、。2将真值表中的最后一列中的1的赋值所对应的小项写出。3将这些小项进展析取。例 利用真值表法求的主析取*式。解的真值表见表1-17。表1-17的真值表001011101110从表1-17中可以看出，该公式在其真值表的00行、01行、10行处取真值1，所以。例用真值表法求的主析取*式。解的真值表见表1-18。表1-18的真值表0000000101010000110110000101011101111111从表1-18中可以看出，该公式在其真值表的001行、011行、101行、110行和111行处取真值1，所以。例 设公式的真值表见表1-19，求公式的主析取*式。解由真值表可看出公式有3组成真赋值

44、，分别出现在000行，100行和111行，所以公式的主析取*式为。表1-19 公式的真值表000100100100011010011010110011112等值演算法除了用真值表法来求一个命题公式的主析取*式外，还可以利用公式的等值演算方法来推导。具体的求解步骤如下：1求公式的析取*式；2除去中所有永假的析取项；3 假设的*个简单合取式中不含有*个命题变元，也不含，则将展成形式。4将重复出现的命题变元、矛盾式及重复出现的小项都消去。5将小项按顺序排列。例求的主析取*式。解例求的主析取*式。解2主合取*式定义在含有n个命题变元的简单析取式中，假设每个命题变元及其否认形式不同时出现，但二者之一必出

45、现且仅出现一次，则称该简单析取式为大项。例如，两个命题变元和生成的4个大项为：，。3个命题变元、和生成的8个大项为：，。 一般说来，n个命题变元共有个大项。大项的二进制编码为：命题变元按字母顺序排列，命题变元与0对应，命题变元的否认与1对应，则得到大项的二进制编码，记为,其下标i是由二进制编码转化的十进制数。n个命题变元形成的个大项，分别记为：，。表1-20列出了两个命题变元和生成的4个大项的真值表。表1-20 两个命题变元和生成的4个大项的真值表二进制0 001110 110111 011011 11110十进制从这个真值表中可以看到，没有两个大项是等价的，且每个大项都只对应着和的一组真值指

46、派使得该大项的真值为0。这个结论可以推广到3个及3个以上变元的情况。由真值表可得到大项具有如下性质：1各大项的真值表都不一样。2每个大项当其真值指派与对应的二进制编码一样时，其真值为假，在其余种指派情况下，其真值均为真。3任意两个不同大项的析取式是永真式。例如=4全体大项的合取式必为永假式。定义由假设干个不同的大项组成的合取式称为主合取*式(The PrincipalConjunctive Normal Form)。与公式等价的主合取*式称为的主合取*式。定理任意含个命题变元的非永真式命题公式都存在着与之等价的主合取*式，并且其主合取*式是唯一的。与主析取*式的求解方法相类似，主合取*式同样可

47、通过真值表法或等值演算法求得。1真值表法定理在真值表中，命题公式的真值为假的赋值所对应的大项的合取即为命题公式的主合取*式。证明方法与定理的证明相类似。利用真值表法求主合取*式的根本步骤为：1列出公式的真值表。2将真值表中的最后一列中的0的赋值所对应的大项写出。3将这些大项进展合取。例求的主合取*式。解的真值表见表1-21。表1-21的真值表0010011110001111从上表可看出，公式在00行，10行处取真值0，所以。2等值演算法 具体的求解步骤如下：1求公式的合取*式；2除去中所有永真的合取项；3 假设的*个简单析取式中不含有*个命题变元，也不含，则将展成形式。4将重复出现的命题变元、

48、永真式及重复出现的大项都消去。5将大项按顺序排列。例求的主合取*式。解3主析取*式和主合取*式关系设为命题公式的主析取*式中所有小项的足标集合，为命题公式的主合取*式中所有大项的足标集合，则有或。故命题公式的主析取*式，可求得其主合取*式；反之亦然。事实上，注意到小项与大项满足，。例：，。在含有个命题变元的命题公式中，如果的主析取*式中含有个小项，则的主析取*式中必含个小项，且所以则的主合取*式中含有个大项，且的主合取*式为。因此，根据公式的主析合取*式可以写出相应的主合析取*式。如例 中的主合取*式为已求出，则主析取*式为，然后写出相应的小项即可。 例求的主析取*式与主合取*式。解4主*式的

49、应用1命题公式等价性的判定由于每个命题公式都存在着与之等价的唯一的主析取*式和主合取*式，因此，如果两个命题公式等价，则相应的主*式也对应一样。例判断与是否等价。解因为所以。( 2) 命题公式类型的判定定理设是含个命题变元的命题公式，则1为永真式当且仅当的主析取*式中含有全部个小项。2为矛盾式当且仅当的主合取*式中含有全部个大项。3假设的主析取*式中至少含有一个小项，则是可满足式。例 判断以下命题公式的类型。1) 2) 解因此，命题公式1)为永真式。因此，命题公式2)为可满足式。3 解决实际问题例 *三说李四在说谎，李四说王五在说谎，王五说*三、李四都在说谎。请问3人中到底谁在说谎？解设：*三

50、说真话即没有说谎。：李四说真话。：王五说真话。则*三说李四在说谎可符号化为：。类似地，其余两句话可符号化为：，。上述条件可表示为公式的真值表见表1-22。表1-22 公式的真值表00000010010101101000101011001110则公式的主析取*式为，即*三在说谎，李四说真话，王五说谎话。例 *单位要从4位职工甲、乙、丙、丁中挑选两位职工去外地旅游，由于工作需要，选派时要考虑以下要求：1甲、乙两人中去且仅去1人。 2乙和丁不能都去。3假设丙去，则丁必须去。4假设丁不去，则甲也不去。问该单位派谁去符合要求？解设：派甲去旅游。：派乙去旅游。：派丙去旅游。：派丁去旅游。则由条件可得命题公

51、式：公式化成主析取*式为应选派方案有：1派甲、丙、丁去旅游。2派甲、丁去旅游。3派乙去旅游。由于单位要派两位职工去旅游，因此只有方案2满足要求，即派甲、丁去旅游。习题1.71写出以下公式的对偶式。123421设，则。2，则。3求以下公式的析取*式与合取*式：1。2。3。4。4写出以下含有3个命题变元的大项或小项脚标是十进制。1 2 3 45在对、的真值指派110下，小项取值为，大项取值为。6求以下命题公式的主析取*式和主合取*式：1。2。37判断以下命题公式的类型：1。2。3。4。8*科研所有三名青年高级工程师A、B和C。所里要选派他们中的12人出国进修，由于所里工作的需要，选派时必须满足以下

52、条件：假设A去，则C也去。假设B去，则C不能去。假设C不去，则A或B去。问所里应如何选派他们？9试判断以下各组命题是否等价：(1)与。(2) 与。1.8 推理理论推理是由一个或几个命题推出另一个命题的思维形式。从构造上说，推理由前提、结论和规则3个局部组成。前提与结论有蕴含关系的推理，或者结论是从前提中必然推出的推理称为必然性推理，如演绎推理；前提和结论没有蕴含关系的推理，或者前提与结论之间并没有必然联系而仅仅是一种或然性联系的推理称为或然性推理，如简单枚举归纳推理。推理：金能导电，银能导电，铜能导电。金、银、铜都是金属。所以金属都能导电。这种从偶然现象概括出一般规律的推理就是一种简单枚举归纳推理。命题逻辑中的推理是演绎推理。在实际应用的推理中，