离散数学电子教材1.docx

《离散数学电子教材1.docx》由会员分享，可在线阅读，更多相关《离散数学电子教材1.docx（48页珍藏版）》请在三一办公上搜索。

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

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

3、的首都。（2） 请勿吸烟！（3） 雪是黑的。（4） 明天开会吗？（5） x+y=5。（6） 我正在说谎。（7） 9+512。（8） 1+101=110。（9） 今天天气多好啊！（10） 别的星球上有生物。解 在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。（1）、（3）、（7）、（8）、（10）都是命题，其中（10）虽然现在无法判断真假，但随着科技的进步是可以判定真假的。需要进一

4、步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1 的（8）1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题。还有的命题的真假不能马上给出，如例1.1.1 的（10），但它确实有真假意义。1.1.2 命题分类根据命题的结构形式，命题分为原子命题和复合命题。定义1.1.2 不能被分解为更简单的陈述语句的命题称为原子命题(Simple Proposition )。由两个或两个以上原子命题组合而成的命题称为复合命题(Compound Proposition )。例如，例1.1.1中的命题全部为原子命题，而命题“小王和小李都去公园。

5、”是复合命题，是由“小王去公园。”与“小李去公园。”两个原子命题组成的。1.1.3命题标识符定义1.1.3 表示原子命题的符号称为命题标识符(Identifier)。通常用大写字母A，B，C，P，Q， 等表示命题，如P：今天下雨。命题标识符依据表示命题的情况，分为命题常元和命题变元。一个表示确定命题的标识符称为命题常元（或命题常项）(Propositional constant)；没有指定具体内容的命题标识符称为命题变元（或命题变项）(Propositional Variable)。命题变元的真值情况不确定，因而命题变元不是命题。只有给命题变元P一具体的命题取代时，P有了确定的真值，P才成为命

6、题。习题1.11 判断下列语句是否为命题，若是，指出其真值。（1） 外面下雨吗？（2） 7能被2 整除。（3） 2x+34。（2）燕子北回，春天来了。（1）设P：雪是黑色的。Q：2+24。则（1）可表示为PQ，其真值为T。（2）设R：燕子北回。S：春天来了。则（2）可表示为R S，其真值为T。与前面的联结词一样，条件联结词和双条件联结词连接的两个命题之间可以没有任何的因果联系，只要能确定复合命题的真值即可。习题1.21指出下列命题的真值：（1） 若2+24，则太阳从西方升起。（2） 若a，则aA。 （3） 胎生动物当且仅当是哺乳动物。 （4） 指南针永指北方，除非它旁边有磁铁。（5） 除非AB

7、CD 是平行四边形,否则它的对边不都平行。2令P：天气好。Q：我去公园。请将下列命题符号化。（1） 如果天气好，我就去公园。（2） 只要天气好，我就去公园。（3） 只有天气好，我才去公园。（4） 我去公园，仅当天气好。 （5） 或者天气好，或者我去公园。（6） 天气好，我去公园。1.3 命题公式与翻译1.3.1命题公式上一节介绍了5种常用的逻辑联结词，利用这些逻辑联结词可将具体的命题表示成符号化的形式。对于较为复杂的命题，需要由这5种逻辑联结词经过各种相互组合以得到其符号化的形式，那么怎样的组合形式才是正确的、符合逻辑的表示形式呢？定义1.3.1（1）单个的命题变元是命题公式。（2）如果是命题

8、公式，那么也是命题公式。（3）如果、是命题公式，那么(),（), ()和()也是命题公式。 （4）当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是命题公式（又称为合式公式，或简称为公式）。上述定义是以递归的形式给出的，其中（1）称为基础，（2）、（3）称为归纳，（4）称为界限。由定义知,命题公式是没有真假的，仅当一个命题公式中的命题变元被赋以确定的命题时，才得到一个命题。例如在公式中，把命题“雪是白色的。”赋给，把命题“2+24。”赋给，则公式被解释为假命题；但若的赋值不变，而把命题“2+2=4。”赋给，则公式被解释为真命题。定义中的符号,不同于具体公

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

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

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

12、是表兄弟。此命题是一个原子命题，“与是表兄弟。”表示两个对象之间的关系。“张三是表兄弟。”及“李四是表兄弟。”都不是命题。所以上述命题只能符号化为的形式。其中：张三与李四是表兄弟。 例1.3.5 将下列命题符号化。 （1） 如果明天早上下雨或下雪，则我不去学校。（2） 如果明天早上不下雨且不下雪，则我去学校。（3） 如果明天早上不是雨夹雪，则我去学校。（4） 当且仅当明天早上不下雨且不下雪时，我才去学校。设：明天早上下雨。：明天早上下雪。：我去学校。（1） 符号化为：（2） 符号化为：（3） 符号化为：（4） 符号化为：例1.3.6 将下列命题符号化。（1） 如果小王和小张都不去，则小李去。（

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

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

15、的真值为1，则这组值称为公式的成真赋值。若指定的一组值使公式的真值为0，则这组值称为公式的成假赋值。例如，对公式，赋值011（即令，则可得到公式的真值为1；若赋值000，则公式真值为0。因此，011为公式的一个成真赋值；000为公式的一个成假赋值。除了上述的两种赋值外，公式的赋值还有000，001，等。一般的结论是在含有n个命题变元的命题公式中，共有种赋值。定义1.4.2 将命题公式在所有赋值下的取值情况列成表，称为公式的真值表(Truth Table)。构造真值表的基本步骤：（1）找出公式中所有的命题变元，按二进制从小到大的顺序列出种赋值。（2）当公式较为复杂时，按照运算的顺序列出各个子公式

16、的真值。（3）计算整个命题公式的真值。例1.4.1 写出下列公式的真值表，并求其成真赋值和成假赋值。（1）（2）（3）解 （1）的真值表见表1-6。表1-6 的真值表0011011110001101成真赋值为00，01，11，成假赋值为10。（2）的真值表见表1-7。表1-7 的真值表00100011001001011100无成真赋值，成假赋值为00，01，10，11。（3）的真值表见表1-8。表1-8 的真值表000111010111100111111001成真赋值为00，01，10，11，无成假赋值。1.4.2 等价公式定义1.4.3 给定两个命题公式，设，是出现在命题公式中的全部命题变元

17、，若给，任一组赋值，公式和的真值都对应相同，则称公式与等价或逻辑相等(Equivalence)，记作。需要注意的是，“”不是逻辑联结词，因而“”不是命题公式，只是表示两个命题公式之间的一种等价关系，即若，和没有本质上的区别，最多只是和具有不同的形式而已。“”具有如下的性质：（1）自反性：。（2）对称性：若，则。（3）传递性：若，则。给定n个命题变元，根据公式的形成规则，可以形成许多个形式各异的公式，但是有很多形式不同的公式具有相同的真值表。因此引入公式等价的概念，其目的就是将复杂的公式简化。下面介绍两种证明公式等价的方法。1真值表法由公式等价的定义可知，利用真值表可以判断任何两个公式是否等价。

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

19、明方法是先用真值表法验证出一些等价公式，再用这些等价公式来推导出新的等价公式，以此作为判断两个公式是否等价的基础。下面给出12组常用的等价公式，它们是进一步推理的基础。牢记并熟练运用这些公式是学好数理逻辑的关键之一。（1）双重否定律：（2）结合律：，（3）交换律：，（4）分配律：，（5）幂等律：，（6）吸收律：，（7）德.摩根律：，（8）同一律：（9）零律：（10）否定律：（11）条件等价式：（12）双条件等价式：上述12组公式均可以通过构造真值表法来证明。2等值演算法定理1.4.1（代入规则）在一个永真式中，任何一个原子命题变元出现的每一处用另一个公式代入，所得的公式仍为永真式。证明：因为永

20、真式对于任何指派，其真值都是1，与每个命题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元出现的每一处，所得到的命题公式的真值仍为1。例如，是永真式，将原子命题变元用代入后得到的式子仍为永真式。定理1.4.2（置换规则） 设是命题公式的一个子公式，若，如果将公式中的用来置换，则所得到的公式与公式等价，即。证明：因为，所以在相应变元的任一种指派情况下，与的真值相同，故以取代后，公式与公式在相应的指派情况下真值也必相同，因此。例如，利用置换，则。从定理可以看出，代入规则是对原子命题变元而言，而置换规则可对命题公式进行；代入必须处处代入，替换可以部分或全部替换；代入规则可以用来扩大永真式的

21、个数，替换规则可以增加等价式的个数。有了上述的12组等价公式及代入规则和置换规则后，就可以推演出更多的等价式。由已知等价式推出另外一些等价式的过程称为等值演算(Equivalent Calculation)。例1.4.4 证明下列公式等价。 （1）（2）证明 （1） （2） 例1.4.5 某件事情是甲、乙、丙、丁4人中某一个人干的。询问4人后回答如下：（1）甲说是丙干的；（2）乙说我没干；（3）丙说甲讲的不符合事实；（4）丁说是甲干的。若其中3人说的是真话，一人说假话，问是谁干的？解 设：这件事是甲干的。：这件事是乙干的。：这件事是丙干的。：这件事是丁干的。4个人所说的命题分别用、表示，则（1

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

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

24、 、 4人进行百米竞赛，观众甲、乙、丙对比赛的结果进行预测。甲：第一，第二；乙：第二，第三；丙：第二，第四。比赛结束后发现甲、乙、丙每个人的预测结果都各对一半。试问实际名次如何（假如无并列者）？解 设表示第名，表示第名，表示第名，表示第名，。则由题意有 （1） （2） （3）因为真命题的合取仍为真命题，所以（1）（2） （4）（3）（4） 因此，第二，第四，第一，第三。习题1.41写出下列公式的真值表。（1）（2）（3）（4）2证明下列等价公式。（1）（2）（3）（4）3甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说：不是我。乙说：是丁。丙说：是乙。丁说：不是我。已知4个人的回答只

25、有一个人符合实际，问成绩最好的是谁？ 43个球迷估计比赛结果，球迷甲说：大连实德第一，北京国安第二。球迷乙说：上海申花第二，长春亚泰第四。球迷丙说：大连实德第二，长春亚泰第四。结果3人估计的都不全对，但都对了一半，问4支球队的名次（假设无并列次序）。5如果，是否有？如果，是否有？如果，是否有？6化简下列公式：（1）（2） （3）1.5 命题公式的分类与蕴含式1.5.1 命题公式的分类从前述的真值表中可以看到，有的命题公式无论对命题欧变元作何种赋值，其对应的真值恒为或恒为，如例1.4.1的（2）、（3）；而有的公式对应的真值则是有有，如例1.4.1的（1）。根据命题公式在不同赋值下的真值情况，可

26、以对命题公式进行分类。定义1.5.1 设为一命题公式，对公式所有可能的赋值：（1）若的真值永为，则称公式为重言式(Tautology)或永真式。（2）若的真值永为，则称公式为矛盾式(Contradictory)或永假式。（3）若至少存在一种赋值使得的真值为，则称公式为可满足式(Satisfiable)。由定义可知，根据命题公式的真值情况，公式可分为两大类，即矛盾式和可满足式。重言式一定是可满足式，但反之不成立。用真值表法可以判定公式的类型：若真值表的最后一列全为1，则公式为重言式；若最后一列全为0，则公式为矛盾式；若最后一列至少有一个1，则公式为可满足式。在1.4的例1.4.1中，（1）为可满

27、足式，（2）为矛盾式，（3）为重言式。用真值表法判断公式的类型方法简单，但当变元较多时，计算量大，在后面的章节中还要介绍其他的方法。1.5.2 重言式与矛盾式的性质定理1.5.1 任何两个重言式的析取或合取，仍是一个重言式。证明：设、为两个重言式，则无论对与的分量作何种指派，总有，故，。定理1.5.2 一个重言式，对同一分量用任何合式公式置换，所得公式仍为一重言式。证明：因为重言式的真值与分量的指派无关，所以对同一分量用任何合式公式置换后，重言式的真值仍永为真。例如，为一重言式，用置换，所得新公式仍为重言式。对于矛盾式，也有类似于定理1.5.1和定理1.5.2的结果。定理1.5.3 设、为两个

28、命题公式，当且仅当为重言式。证明：若，则在、所含命题变元的任何指派下，与的真值都相同，即恒为真。若为重言式，由重言式的定义知，在对、所含命题变元的任何指派下，与都有相同的真值，即。例1.5.1 证明为重言式。证明 由例1.4.2知，故依据定理1.5.3有为重言式。1.5.3 蕴含式下面讨论的重言式。定义1.5.2 设、为两个命题公式，若为重言式，则称“蕴含( Implication)”，记作。注意“”与“”一样，都不是逻辑联结词，因而也不是公式。是用来表示由条件能够推导出结论，或称为可以由逻辑推出。蕴含关系具有如下的性质：（1）自反性：对任意的公式，有。（2）反对称性：对任意的公式、，若且，则

29、有。（3）传递性：对任意的公式、，若、，则有。由于不具有对称性，即与不等价，因此，对于而言，称为它的逆换式，称为它的反换式，称为它的逆反式。在上述的4个公式中，。定理1.5.4 的充分必要条件是且。证明：若，则为重言式，而，故均为重言式，即且。反之，若且，则均为重言式，于是为重言式，即为重言式，故。由定义1.5.2知，要证明，只需证明为重言式即可。因此，前面介绍的真值表法和等值演算法均可应用。下面综合介绍证明的各种方法。1真值表法例1.5.2 证明证明 只需证明为重言式。真值表见表1-11。表1-11 的真值表00010101100111112等值演算法例1.5.3 证明证明 只需证明为重言式

30、。 即3分析法分析法包括以下两种形式：（1）假定前件为真，推出后件为真，则。（2）假定后件为假，推出前件为假，则。理由是：（1）若为真，则可能为真也可能为假，但由假设推出为真，所以否定了为真、为假的可能，只能是为真、也为真。所以为重言式，即。对于（2），若后件为假，则前件可能为真也可能为假。若为真，为假，则为假；若为假，为假，则为真。而由假设推知为假，因此否定了为真，为假的可能。所以为重言式，即。例1.5.4 证明（1）（2）证明 （1）假设前件为真，则为真，为真；由此有为假，为真。因此。（2）假设后件为假，若为真，则为假，有为假。若为假，则为真，有为假。综上，若后件为假，无论为真还是假，前件

31、均为假。因此。需要指出的是，在例1.5.4的（2）中，因为不知道的真值情况，所以要分情况讨论。例1.5.5 分析下列论证的有效性。 条件：香烟有利于健康； 如果香烟有利于健康，那么医生就会把香烟作为药品开给病人。结论：医生把香烟作为药品开给病人。解 设：香烟有利于健康。：医生把香烟作为药品开给病人。上述推理符号化为：。其证明同例1.5.4的（2）。因此上述论证是有效的。下面给出的蕴含式其正确性均可用上述的推理方法进行证明。（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）习题1.51判断下列命题公式的类型。（1）。（2）。（3）。（4）。2证明下列各

32、蕴含式。（1）（2）（3）（4）3判断下列命题的真假。（1）重言式的否定是矛盾式。（2）矛盾式的否定是重言式。（3）不是重言式就是矛盾式。（4）不是矛盾式就是重言式。（5）重言式必是可满足式。（6）不是矛盾式就是可满足式。（7）可满足式未必是重言式。（8）不是可满足式就是矛盾式。 4设P表示命题“8是偶数”，Q表示命题“糖果是甜的”。试以句子写出：（1）。（2）的逆换式。（3）的反换式。（4）的逆反式。5叙述下列各个命题的逆换式和逆反式，并以符号写出。（1）如果下雨，我不去。（2）仅当你走我将留下。（3）如果我不能获得更多帮助，我不能完成这个任务。6检验下列论证的有效性。如果我学习，那么我数学

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

34、“”的定义见表1-12。表1-12 联结词“”的定义000011101110从真值表中易见，。利用真值表法，易证“”具有如下性质：（1）（2）（）（3）（4）（5）；（6）若，则，且为一矛盾式。2与非联结词(Nand)( ) 定义1.6.2 设、为两个命题公式，复合命题称为和的“与非式”。当且仅当与的真值都为时，的真值为，否则的真值为。联结词“”的定义见表1-13。表1-13 联结词“”的定义001011101110从真值表中易见，。联结词“”具有如下性质：（1）（2）（3）3或非联结词(Nor)（）定义1.6.3 设、为两个命题公式，复合命题称为和的“或非式”。当且仅当与的真值都为时，的真值

35、为，否则的真值为。联结词“”的定义见表1-14。表1-14 联结词“”的定义001010100110从真值表中易见，。联结词“”具有如下性质：（1）（2）（3）4条件否定联结词(Non-conditional)（）定义1.6.4 设、为两个命题公式，复合命题称为和的“条件否定”。当且仅当的真值为，的真值为时，的真值为，否则的真值为。联结词“”的定义见表1-15。表1-15 联结词“”的定义000010101110从真值表中易见，。1.6.2 最小功能完备联结词组到目前为止，共定义了9个联结词，但这些联结词在表达命题时并不是缺一不可，因为包含某些联结词的公式可以用含有另外一些联结词的公式来进行表

36、示。如这说明“”可以转化为“”，而“”可转化为由“”与“”表示，而“”与“”又可以相互转化。对于另外的4个联结词，由于，这说明任意的一个命题公式最终都可以转化为仅包含，或，的命题公式来等价地表示。定义1.6.5 设是一个联结词的集合，若任意一个命题公式都可用中联结词构成的公式来表示，则称为功能完备联结词组。如果在中去掉任何一个联结词后都不再具有这种性质，则称为最小功能完备联结词组，简称为最小联结词组。可以证明，等都是功能完备联结词组，而，及，均为最小功能完备联结词组。由联结词“”及“”的性质知，联结词“”、“”和“”可分别用“” 或“”表示，所以及也是最小功能完备联结词组。通常为了命题表示的简洁清楚，常用包含，的联结词组来表示命题。习题1.61将下列命题公式转化为仅含联结词的命题公式。（1）（2）（3）2将下列命题公式用只含和的等价式表达，并要求尽可能简单。（1）（2）（3）3证明不是最小功能完备连接词组。4证明是最小功能完备连接词组。1.7 对偶与范式1.7.1对偶式与对偶原理 1对偶式定义1.7.1