离散数学电子教材1edes.docx

《离散数学电子教材1edes.docx》由会员分享，可在线阅读，更多相关《离散数学电子教材1edes.docx（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 命命题逻辑辑逻辑是研研究人的的思维的的科学，包包括辩证证逻辑和和形式逻逻辑。辩辩证逻辑辑是研究究反映客客观世界界辩证发发展过程程的人类类思维的的形态的的。形式式逻辑是是研究思思维的形形式结构构和规律律的科学学，它撇撇开具体体的、个个别的思思维内容容，从形形式结构构方面研研究概念念、判断断和推理理及其正正确联系系的规律律。数理理逻辑是是用数学学方法研研究推理理的形式式结构和和推理的的规律的的数学学学科。所所谓的数数学方法法也就是是用一套套有严格格定义的的符号，即即建立一一套形式式语言来来研究。因因此数理理逻辑也也称为符符号逻辑辑。数理逻辑辑的基础础部分是是命题逻逻辑和谓谓词逻辑辑。本章章

2、主要讲讲述命题题逻辑，谓谓词逻辑辑将在第第2章进进行讨论论。1.1命命题及其其表示1.1.1命题的的基本概概念数理逻辑辑研究的的中心问问题是推推理（IInfeerennce)，而推理理就必然然包含前前提和结结论，前前提和结结论都是是表达判判断的陈陈述句，因因而表达达判断的的陈述句句就成为为推理的的基本要要素。在在数理逻逻辑中，将将能够判判断真假假的陈述述句称为为命题。因此命题就成为推理的基本单位。在命题逻辑中，对命题的组成部分不再进一步细分。定义1.1.1能够判判断真假假的陈述述句称为为命题（Propposiitioon）。命命题的判判断结果果称为命命题的真真值，常常用 TT(Truee)（或

3、或1）表表示真，FF(Falsse)（或或0）表表示假。真真值为真真的命题题称为真真命题，真真值为假假的命题题称为假假命题。从上述的的定义可可知，判判定一个个句子是是否为命命题要分分为两步步：一是是判定是是否为陈陈述句，二二是能否否判定真真假，二二者缺一一不可。例1.11.1判断下下列句子子是否为为命题（1） 北京是中中国的首首都。（2） 请勿吸烟烟！（3） 雪是黑的的。（4） 明天开会会吗？（5） x+y=5。（6） 我正在说说谎。（7） 9+512。（8） 1+1001=1110。（9） 今天天气气多好啊啊！（10） 别的星球球上有生生物。解 在在上述的的十个句句子中，（22）、（99）为

4、祈祈使句，（44）为疑疑问句，（55）、（66）虽然然是陈述述句，但但（5）没没有确定定的真值值，其真真假随xx、y取值的的不同而而有改变变，（66）是悖悖论(Paraadoxx)（即由由真能推推出假，由由假也能能推出真真），因因而（22）、（44）、（55）、（66）、（99）均不不是命题题。（11）、（33）、（77）、（88）、（110）都都是命题题，其中中（100）虽然然现在无无法判断断真假，但但随着科科技的进进步是可可以判定定真假的的。需要进一一步指出出的是，命命题的真真假只要要求它有有就可以以，而不不要求立立即给出出。如例例1.11.1的的（8）11+1001=1110，它它的真假

5、假意义通通常和上上下文有有关，当当作为二二进制的的加法时时，它是是真命题题，否则则为假命命题。还还有的命命题的真真假不能能马上给给出，如如例1.1.11 的（100），但但它确实实有真假假意义。1.1.2命题分分类根据命题题的结构构形式，命命题分为为原子命命题和复复合命题题。定义1.1.2不能被被分解为为更简单单的陈述述语句的的命题称称为原子子命题(Simpple Propposiitioon )。由两两个或两两个以上上原子命命题组合合而成的的命题称称为复合合命题(Comppounnd PPropposiitioon )。例如，例例1.11.1中中的命题题全部为为原子命命题，而而命题“小王和和

6、小李都都去公园园。”是复合合命题，是是由“小王去去公园。”与“小李去公园。”两个原子命题组成的。1.1.3命题标标识符定义1.1.3表示原原子命题题的符号号称为命命题标识识符(Idenntiffierr)。通常用大大写字母母A，BB，C，P，Q，等表示命题，如P：今天下雨。命题标识识符依据据表示命命题的情情况，分分为命题题常元和和命题变变元。一一个表示示确定命命题的标标识符称称为命题题常元（或或命题常常项）(Propposiitioonall coonsttantt)；没没有指定定具体内内容的命命题标识识符称为为命题变变元（或或命题变变项）(Proopossitiionaal VVariiab

7、lle)。命命题变元元的真值值情况不不确定，因因而命题题变元不不是命题题。只有有给命题题变元PP一具体体的命题题取代时时，P有了确确定的真真值，PP才成为为命题。习题1.11 判断下列列语句是是否为命命题，若若是，指指出其真真值。（1） 外面下雨雨吗？（2） 7能被22 整除除。（3） 2x+334。（2）燕燕子北回回，春天天来了。（1）设设P：雪是是黑色的的。Q：2+24。则则（1）可可表示为为PQ，其真真值为TT。（2）设设R：燕子子北回。S：春天来了。则（2）可表示为R S，其真值为T。与前面的的联结词一一样，条条件联结结词和双双条件联联结词连连接的两两个命题题之间可可以没有有任何的的因

8、果联联系，只只要能确确定复合合命题的的真值即即可。习题1.21指出出下列命命题的真真值：（1） 若2+224，则则太阳从从西方升升起。（2） 若a，则则aA。 （3） 胎生动物物当且仅仅当是哺哺乳动物物。 （4） 指南针永永指北方方，除非非它旁边边有磁铁铁。（5） 除非ABBCD 是平行行四边形形,否则它它的对边边不都平平行。2令PP：天气气好。QQ：我去去公园。请请将下列列命题符符号化。（1） 如果天气气好，我我就去公公园。（2） 只要天气气好，我我就去公公园。（3） 只有天气气好，我我才去公公园。（4） 我去公园园，仅当当天气好好。 （5） 或者天气气好，或或者我去去公园。（6） 天气好，

9、我我去公园园。1.3命命题公式式与翻译译1.3.1命题公公式上一节介介绍了55种常用用的逻辑辑联结词，利利用这些些逻辑联联结词可将具具体的命命题表示示成符号号化的形形式。对对于较为为复杂的的命题，需需要由这这5种逻逻辑联结结词经过过各种相相互组合合以得到到其符号号化的形形式，那那么怎样样的组合合形式才才是正确确的、符符合逻辑辑的表示示形式呢呢？定义1.3.11（1）单单个的命命题变元元是命题题公式。（2）如如果是命命题公式式，那么么也是命命题公式式。（3）如如果、是命题题公式，那那么(),（), ()和()也是是命题公公式。 （4）当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题

10、变元、联结词和括号的符号串是命题公式（又称为合式公式，或简称为公式）。上述定义义是以递递归的形形式给出出的，其其中（11）称为为基础，（2）、（3）称为归纳，（4）称为界限。由定义知知,命题题公式是是没有真真假的，仅仅当一个个命题公公式中的的命题变变元被赋赋以确定定的命题题时，才才得到一一个命题题。例如如在公式式中，把把命题“雪是白白色的。”赋给，把命题“2+24。”赋给，则公式被解释为假命题；但若的赋值不变，而把命题“2+2=4。”赋给，则公式被解释为真命题。定义中的的符号,不同于于具体公公式里的的、等符号号，它可可以用来来表示任任意的命命题公式式。例1.33.1，等都是是命题公公式，而而，

11、等都不不是命题题公式。为了减少少命题公公式中使使用括号号的数量量，规定定：（11）逻辑辑联结词的的优先级级别由高高到低依依次为、。（22）具有有相同级级别的联联结词，按按出现的的先后次次序进行行计算，括括号可以以省略。（33）命题题公式的的最外层层括号可可以省去去。例1.33.2也可以以写成，也可写写成，也可写写成，而而中的括括号不能能省去。定义1.3.22 设是命命题公式式的一部部分，且且也是命命题公式式，则称称为的子公公式。例如及都都是公式式的子公公式；、及都是公公式的子子公式。1.3.2 命命题的符符号化 有了命题题公式的的概念之之后，就就可以把把自然语语言中的的一些命命题翻译译成命题题

12、逻辑中中的符号号化形式式。把一一个文字字描述的的命题相相应地写写成由命命题标识识符、逻逻辑联结结词和圆圆括号表表示的命命题形式式称为命命题的符符号化或或翻译。命题符号号化的一一般步骤骤：（11）明确确给定命命题的含含义；（22）找出出命题中中的各原原子命题题，分别别符号化化。（33）使用用合适的的逻辑联联结词，将将原子命命题分别别连接起起来，组组成复合合命题的的符号化化形式。把命题符符号化，是是不管具具体内容容而突出出思维形形式的一一种方法法。注意意在命题题符号化化时，要要正确地地分析和和理解自自然语言言命题，不不能仅凭凭文字的的字面意意思进行行翻译。例1.33.3 张张三或李李四都可可以做这

13、这件事。设：张三三可以做做这件事事。：李李四可以以做这件件事。则命题符符号化为为：，而而不是。例1.33.4 （11）只有有你走，我我才留下下。这个命题题的意义义也可以以理解为为：如果果我留下下了，那那么你一一定走了了。设：你走走。：我留下下。则命命题符号号化为：。与原命题题类似的的命题如如：仅当当你走我我才留下下。我留留下仅当当你走。当当我留下下你得走走。注意：在在一般的的命题表表述中，“仅当”是必要条件，译成条件命题时其后的命题是后件，而“当”是充分条件，译成条件命题时其后的命题是前件。（2）仅仅当天不不下雨且且我有时时间，我我才上街街。设：天下下雨。：我有时时间。：我上街街。命题题符号化

14、化为：。（3）你你将失败败，除非非你努力力。这个命题题的意义义可以理理解为：如果你你不努力力，那么么你将失失败。设：你努努力。：你失败败。则命命题符号号化为：。含有“除除非”的命题题，“非”是充充分条件件，译成成条件命命题时，“非”是条件的前件。（4）中中没有元元素，就就是空集集。设：中有有元素。：是空集。则命题符号化为：（5）张张三与李李四是表表兄弟。此命题是是一个原原子命题题，“与是表兄兄弟。”表示两两个对象象之间的的关系。“张三是表兄弟。”及“李四是表兄弟。”都不是命题。所以上述命题只能符号化为的形式。其中：张三与李四是表兄弟。例1.33.5 将下列列命题符符号化。（1） 如果明天天早上

15、下下雨或下下雪，则则我不去去学校。（2） 如果明天天早上不不下雨且且不下雪雪，则我我去学校校。（3） 如果明天天早上不不是雨夹夹雪，则则我去学学校。（4） 当且仅当当明天早早上不下下雨且不不下雪时时，我才才去学校校。设：明天天早上下下雨。：明天早早上下雪雪。：我我去学校校。（1） 符号化为为：（2） 符号化为为：（3） 符号化为为：（4） 符号化为为：例1.33.6将下列列命题符符号化。（1） 如果小王王和小张张都不去去，则小小李去。（2） 如果小王王和小张张不都去去，则小小李去。设：小王王去。：小张去去。：小小李去。（1） 符号化为为：（2） 符号化为为：或例1.33.7 将将下列命命题符号

16、号化。（1）说说离散数数学无用用且枯燥燥无味是是不对的的。（2）若若天不下下雨，我我就上街街；否则则在家。对于（11），设设：离散散数学是是有用的的。：离离散数学学是枯燥燥无味的的。则命命题符号号化为：。对于（22），设设：天下下雨。：我上街街。：我我在家。则则命题符符号化为为：。通过上述述的例题题可以看看出，要要正确地地将自然然语言中中的联结词翻译译成恰当当的逻辑辑联结词，必必须要正正确地理理解各原原子命题题之间的的关系。习题1.31判断断下列各各式子是是否是命命题公式式（1）（2）（3）（4）（5）（6）2将下下列命题题符号化化（句中中括号内内提示的的是相应应的原子子命题的的符号表表示）（

17、1）我我去新华华书店，仅仅当我有有时间。（2）我我们不能能既划船船又跑步步。（3）只只要努力力学习，成成绩就会会好的。（4）或或者你没没有给我我写信，或或者它在在路上丢丢了。（5）如如果上午午不下雨雨，我就就去看电电影，否否则我就就在家里里读书或或看报纸纸。（6）我我今天进进城，除除非下雨雨。（7）如如果太阳阳没出来来，则或或者下雨雨或者阴阴天而且且温度下下降。（8）指指南针永永指南北北，除非非它旁边边有磁铁铁。（9）说说逻辑枯枯燥无味味和毫无无价值是是不对的的。（10）人人不犯我我，我不不犯人；人若犯犯我，我我必犯人人。1.4真真值表与与等价公公式1.4.1真值表表定义1.4.11 设，是出

18、现现在命题题公式中中的全部部命题变变元，给给，各指定定一个真真值，称称为对公公式的一一个赋值值（或解解释或真真值指派派）。若指定的的一组值值使公式式的真值值为1，则则这组值值称为公公式的成成真赋值值。若指定的的一组值值使公式式的真值值为0，则则这组值值称为公公式的成成假赋值值。例如，对对公式，赋赋值0111（即即令，则则可得到到公式的的真值为为1；若若赋值0000，则则公式真真值为00。因此此，0111为公公式的一一个成真真赋值；0000为公式式的一个个成假赋赋值。除除了上述述的两种种赋值外外，公式式的赋值值还有0000，0011，等。一般般的结论论是在含含有n个命题题变元的的命题公公式中，共

19、共有种赋赋值。定义1.4.2 将命命题公式式在所有有赋值下下的取值值情况列列成表，称称为公式式的真值值表(Trutth TTablle)。构造真值值表的基基本步骤骤：（1）找找出公式式中所有有的命题题变元，按二二进制从从小到大大的顺序序列出种种赋值。（2）当当公式较较为复杂杂时，按按照运算算的顺序序列出各各个子公公式的真真值。（3）计计算整个个命题公公式的真真值。例1.44.1 写写出下列列公式的的真值表表，并求求其成真真赋值和和成假赋赋值。（1）（2）（3）解（1）的的真值表表见表11-6。表1-66的真值值表0011011110001101成真赋值值为000，011，111，成假假赋值为为

20、10。（2）的的真值表表见表11-7。表1-77的真值值表00100011001001011100无成真赋赋值，成成假赋值值为000，011，100，111。（3）的的真值表表见表11-8。表1-88的真值值表000111010111100111111001成真赋值值为000，011，100，111，无成成假赋值值。1.4.2 等等价公式式定义1.4.3 给定定两个命命题公式式，设，是出现现在命题题公式中中的全部部命题变变元，若若给，任一组组赋值，公公式和的真值值都对应应相同，则则称公式式与等价或或逻辑相相等(Equiivallencce)，记作作。需要注意意的是，“”不是逻辑联结词，因而“”

21、不是命题公式，只是表示两个命题公式之间的一种等价关系，即若，和没有本质上的区别，最多只是和具有不同的形式而已。“”具有有如下的的性质：（1）自自反性：。（22）对称称性：若若，则。（33）传递递性：若若，则。给定n个个命题变变元，根根据公式式的形成成规则，可可以形成成许多个个形式各各异的公公式，但但是有很很多形式式不同的的公式具具有相同同的真值值表。因因此引入入公式等等价的概概念，其其目的就就是将复复杂的公公式简化化。下面介绍绍两种证证明公式式等价的的方法。1真值值表法由公式等等价的定定义可知知，利用用真值表表可以判判断任何何两个公公式是否否等价。例1.44.2 证明明证明命题题公式与与的真值

22、值表见表表1-99。由表1-9可知知，在任任意赋值值下与两者的的真值均均对应相相同。因因此表1-99与的真值值表001111011000100100111111例1.44.3 判断断公式与与二者是是否等价价。证明公式式与的真值表表见表11-100。表1-110与的真值值表0011011010011111可见真值值表中的的最后两两列值不不完全相相同，因因此公式式与不等价价。从理论上上来讲，利利用真值值表法可可以判断断任何两两个命题题公式是是否等价价，但是是真值表表法并不不是一个个非常好好的方法法，因为为当公式式中命题题变元较较多时，其其计算量量较大，例例如当公公式中有有四个变变元时，需需要列出出

23、=166种赋值值情况，计计算较为为繁杂。因因此，通通常采用用其他的的证明方方法。这这种证明明方法是是先用真真值表法法验证出出一些等等价公式式，再用用这些等等价公式式来推导导出新的的等价公公式，以以此作为为判断两两个公式式是否等等价的基基础。下下面给出出12组组常用的的等价公公式，它它们是进进一步推推理的基基础。牢牢记并熟熟练运用用这些公公式是学学好数理理逻辑的的关键之之一。（1）双双重否定定律：（2）结结合律：，（3）交交换律：，（4）分分配律：，（5）幂幂等律：，（6）吸吸收律：，（7）德德.摩根根律：，（8）同同一律：（9）零零律：（10）否否定律：（11）条条件等价价式：（12）双双条件

24、等等价式：上述122组公式式均可以以通过构构造真值值表法来来证明。2等值值演算法法定理1.4.1（代入入规则）在一个永真式中，任何一个原子命题变元出现的每一处用另一个公式代入，所得的公式仍为永真式。证明：因因为永真真式对于于任何指指派，其其真值都都是1，与与每个命命题变元元指派的的真假无无关，所所以，用用一个命命题公式式代入到到原子命命题变元元出现的的每一处处，所得得到的命命题公式式的真值值仍为11。例如，是是永真式式，将原原子命题题变元用用代入后得到的的式子仍仍为永真真式。定理1.4.2（置换换规则） 设是命题公式的一个子公式，若，如果将公式中的用来置换，则所得到的公式与公式等价，即。证明：

25、因因为，所所以在相相应变元元的任一一种指派派情况下下，与的真值值相同，故故以取代代后，公公式与公公式在相相应的指指派情况况下真值值也必相相同，因因此。例如，利利用置换换，则。从定理可可以看出出，代入入规则是是对原子子命题变变元而言言，而置置换规则则可对命命题公式式进行；代入必必须处处处代入，替替换可以以部分或或全部替替换；代代入规则则可以用用来扩大大永真式式的个数数，替换换规则可可以增加加等价式式的个数数。有了上述述的122组等价价公式及及代入规规则和置置换规则则后，就就可以推推演出更更多的等等价式。由由已知等等价式推推出另外外一些等等价式的的过程称称为等值值演算(Equiivallentt

26、Calcculaatioon)。例1.44.4 证证明下列列公式等等价。（1）（2）证明（11）（2）例1.44.5某件事事情是甲甲、乙、丙丙、丁44人中某某一个人人干的。询询问4人人后回答答如下：（1）甲甲说是丙丙干的；（2）乙乙说我没没干；（33）丙说说甲讲的的不符合合事实；（4）丁丁说是甲甲干的。若若其中33人说的的是真话话，一人人说假话话，问是是谁干的的？解设：这这件事是是甲干的的。：这这件事是是乙干的的。：这这件事是是丙干的的。：这这件事是是丁干的的。4个人所所说的命命题分别别用、表示，则则（1）、（22）、（33）、（44）分别别符号化化为：；则3人说说真话，一一人说假假话的命命题

27、符号号化为：其中同理所以，当当为真时时，为真真，即这这件事是是甲干的的。本题也可可以从题题干直接接找出相相互矛盾盾的两个个命题作作为解题题的突破破口。甲甲、丙两两人所说说的话是是相互矛矛盾的，必必有一人人说真话话，一人人说假话话，而44个人中中只有一一人说假假话，因因此乙、丁丁两人必必说真话话，由此此可断定定这件事事是甲干干的。例1.44.6在某次次球赛中中，3位位球迷甲甲、乙、丙丙对某球球队的比比赛结果果进行猜猜测。甲甲说：该该球队不不会得第第一名，是是第二名名。乙说说：该球球队不会会得第二二名，是是第一名名。丙说说：该球球队不会会得第二二名，也也不会是是第三名名。比赛赛结束后后，结果果证实

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

29、该球队不不可能既既是第一一名，又又是第三三名），。因此，若若为真，只只有为真真。因而而为真命命题，为为假命题题。即该该球队获获得第二二名。甲甲的判断断全对，乙乙的判断断全错，丙丙的判断断对一半半。例1.44.7、 4人进进行百米米竞赛，观观众甲、乙乙、丙对对比赛的的结果进进行预测测。甲：第一，第第二；乙乙：第二二，第三三；丙：第二，第第四。比比赛结束束后发现现甲、乙乙、丙每每个人的的预测结结果都各各对一半半。试问问实际名名次如何何（假如如无并列列者）？解设表示示第名，表示示第名，表示示第名，表示示第名，。则由题意意有 （11） （22） （33）因为真命命题的合合取仍为为真命题题，所以以（1）

30、（22） （44）（3）（44）因此，第第二，第第四，第第一，第第三。习题1.41写出出下列公公式的真真值表。（1）（2）（3）（4）2证明明下列等等价公式式。（1）（2）（3）（4）3甲、乙乙、丙、丁丁4人参参加考试试后，有有人问他他们谁的的成绩最最好，甲甲说：不不是我。乙乙说：是是丁。丙丙说：是是乙。丁丁说：不不是我。已已知4个个人的回回答只有有一个人人符合实实际，问问成绩最最好的是是谁？ 43个个球迷估估计比赛赛结果，球球迷甲说说：大连连实德第第一，北北京国安安第二。球球迷乙说说：上海海申花第第二，长长春亚泰泰第四。球球迷丙说说：大连连实德第第二，长长春亚泰泰第四。结结果3人人估计的的都

31、不全全对，但但都对了了一半，问问4支球球队的名名次（假假设无并并列次序序）。5如果果，是否否有？如如果，是是否有？如果，是是否有？6化简简下列公公式：（1）（2） （33）1.5 命题题公式的的分类与与蕴含式式1.5.1 命命题公式式的分类从前述的的真值表表中可以以看到，有的命题公式无论对命题欧变元作何种赋值，其对应的真值恒为或恒为，如例1.4.1的（2）、（3）；而有的公式对应的真值则是有有，如例1.4.1的（1）。根据命题题公式在在不同赋赋值下的的真值情情况，可可以对命命题公式式进行分分类。定义1.5.11 设为一一命题公公式，对对公式所所有可能能的赋值值：（1）若若的真值值永为，则则称公

32、式式为重言言式(TTauttoloogy)或永真真式。（2）若若的真值值永为，则则称公式式为矛盾盾式(Conttraddicttoryy)或永永假式。（3）若若至少存存在一种种赋值使使得的真真值为，则则称公式式为可满满足式(Satiisfiiablle)。由定义可可知，根根据命题题公式的的真值情情况，公公式可分分为两大大类，即即矛盾式式和可满满足式。重重言式一一定是可可满足式式，但反反之不成成立。用真值表表法可以以判定公公式的类类型：若若真值表表的最后后一列全全为1，则则公式为为重言式式；若最最后一列列全为00，则公公式为矛矛盾式；若最后后一列至至少有一一个1，则则公式为为可满足足式。在在1.

33、4的例例1.4.1中，（11）为可可满足式式，（22）为矛矛盾式，（33）为重重言式。用用真值表表法判断断公式的的类型方方法简单单，但当当变元较较多时，计计算量大大，在后后面的章章节中还还要介绍绍其他的的方法。1.5.2重言言式与矛矛盾式的的性质定理1.5.11 任何何两个重重言式的的析取或或合取，仍仍是一个个重言式式。证明：设设、为两个个重言式式，则无无论对与与的分量量作何种种指派，总总有，故，。定理1.5.22一个重重言式，对同一一分量用用任何合合式公式式置换，所所得公式式仍为一一重言式式。证明：因因为重言言式的真真值与分分量的指指派无关关，所以以对同一一分量用用任何合合式公式式置换后后，

34、重言言式的真真值仍永永为真。例如，为为一重言言式，用用置换，所所得新公公式仍为为重言式式。对于矛盾盾式，也也有类似似于定理理1.5.11和定理理1.5.22的结果果。定理1.5.3设、为两个个命题公公式，当当且仅当当为重言言式。证明：若若，则在在、所含命命题变元元的任何何指派下下，与的真值值都相同同，即恒恒为真。若为重言言式，由由重言式式的定义义知，在在对、所含命命题变元元的任何何指派下下，与都有相相同的真真值，即即。例1.55.1证明为重重言式。证明由例例1.44.2知知，故依依据定理理1.5.3有为重言言式。1.5.3蕴含式式下面讨论论的重言言式。定义1.5.2 设设、为两个个命题公公式，

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

36、为重言式式，即且且。反之，若若且，则均为为重言式式，于是是为重言言式，即即为重言言式，故故。由定义11.5.2知，要要证明，只只需证明明为重言言式即可可。因此此，前面面介绍的的真值表表法和等等值演算算法均可可应用。下面综合合介绍证证明的各各种方法法。1真值值表法例1.55.2 证明明证明只需需证明为为重言式式。真值值表见表表1-111。表1-111的真真值表00010101100111112等值值演算法法例1.55.3 证明明证明只需需证明为为重言式式。即3分析析法分析法包包括以下下两种形形式：（1）假假定前件件为真，推推出后件件为真，则则。（2）假假定后件件为假，推推出前件件为假，则则。理由

37、是：（1）若若为真，则则可能为为真也可可能为假假，但由由假设推推出为真真，所以以否定了了为真、为为假的可可能，只只能是为为真、也也为真。所所以为重重言式，即即。对于（22），若若后件为为假，则则前件可可能为真真也可能能为假。若若为真，为为假，则则为假；若为假假，为假假，则为为真。而而由假设设推知为为假，因因此否定定了为真真，为假假的可能能。所以以为重言言式，即即。例1.55.4证明（11）（2）证明（11）假设设前件为为真，则则为真，为为真；由由此有为为假，为为真。因因此。（2）假假设后件件为假，若为真，则则为假，有有为假。若为假，则则为真，有有为假。综上，若若后件为为假，无无论为真真还是假假，前件件均为假假。因此此。需要指出出的是，在在例1.5.44的（2）中中，因为为不知道道的真值值情况，所所以要分分情况讨讨论。例1.55.5 分分析下列列论证的的有效性性。 条件：香香烟有利利于健康康； 如如果香烟烟有利于于健康，那那么医生生就会把把香烟作作为药品品开给病病人。结论：医医生把香香烟作为为药品开开给病人人。解设：香香烟有利利于健康康。：医医生把香香烟作为为药品开开给病人人。上述推理理符号化化为：。其证明同同例1.5.44的（2）。因因此