离散第9讲命题与逻辑联结词new

1、 1 11 1级专业选修课程级专业选修课程 授课人：王薇授课人：王薇信息与计算教研室信息与计算教研室离散数学数理逻辑代数结构图 论集合代数命题逻辑谓词逻辑集合与关系函数基本概念矩阵表示典型图树本教材离散数学知识结构离散数学前言vPowerPoint Template_Sub 逻辑学是一门非常古老的学科，逻辑学是一门非常古老的学科，它是它是研究人类推理过程的研究人类推理过程的科学科学。到现在已经有了两千多年的历史。古典逻辑学主要到现在已经有了两千多年的历史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说，他创作的工起源于古希腊学者亚里士多德的逻辑学说，他创作的工具论一书是古代一部最完备的逻辑

2、学著作具论一书是古代一部最完备的逻辑学著作。古典逻辑学的基本特点是用自然语言描述对逻辑的研究，古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一旦超出这个范围，引入数学的方法来研究逻辑，就产而一旦超出这个范围，引入数学的方法来研究逻辑，就产生了远远优于古典逻辑学的现代逻辑学生了远远优于古典逻辑学的现代逻辑学。 数理逻辑也称符号逻辑，是现代逻辑学研究的主体部分，数理逻辑也称符号逻辑，是现代逻辑学研究的主体部分，是是一门运用数学方法研究思维规律的边缘性学科一门运用数学方法研究思维规律的边缘性学科。将推理将推理变成数学演算变成数学演算，这是数理逻辑的指导思想，并且已经成为，这是数理逻辑的指导思想

3、，并且已经成为这门学科的主要特征这门学科的主要特征 。数理逻辑是用形式化数理逻辑是用形式化(符号化符号化)方法来研究推理的科学方法来研究推理的科学。* *命题逻辑研究命题和命题连接词的逻辑结构以及命题之间的推理关系。命题逻辑:推理的基本要素是命题. 引言 先看著名物理学家爱因斯坦出过的一道题： 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个人更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出

4、自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。” 请问这个人说得对吗？他是怎么推导出来的呢？请问这个人说得对吗？他是怎么推导出来的呢？ 要回答这样的问题，实际上就是看由一些诸如要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子商人戴的是红帽子”这样的这样的前提前提能否推出能否推出“猜出答猜出答案的应试者戴的是黑帽子案的应试者戴的是黑帽子”这样的这样的结论结论来。来。 这又需要经历如下过程：这又需要经历如下过程： (

5、1) 什么是前提？有哪些前提？什么是前提？有哪些前提？ (2) 结论是什么？结论是什么？ (3) 根据什么进行推理？根据什么进行推理？ (4) 怎么进行推理？怎么进行推理？ 学习命题逻辑学习命题逻辑将回答这几个问题。将回答这几个问题。-8-第第9讲讲 命题与逻辑联结词命题与逻辑联结词vPowerPoint Template_Sub 1命题与逻辑联结词命题与逻辑联结词2逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式3范式范式4证明技术（补充）证明技术（补充）v命题与逻辑联结词命题与逻辑联结词离散数学离散数学第第9 9讲讲 Page Page 5656 to to 7878-10-第第9讲讲 命题与

6、逻辑联结词命题与逻辑联结词v内容提要内容提要命题的概念命题的概念命题、命题真值表示命题、命题真值表示原子命题和复合命题、命题常元、命题变元原子命题和复合命题、命题常元、命题变元逻辑联结词逻辑联结词 、 、 、 、 命题公式命题公式 公式的归纳定义公式的归纳定义指派指派自然语句的形式化自然语句的形式化-11-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v命题命题 (proposition (proposition或或statement) statement) 命题：命题：是一句有确定真假值的是一句有确定真假值的陈述句。陈述句。命题只有两个结果，或是真，或是假，但二者或是真，或是假，但二者不能得兼

7、（排中律），也不能不能得兼（排中律），也不能不真又不假。真、假常被称为命题的真值真、假常被称为命题的真值 。 命题的真值命题的真值作为命题的陈述句所表达的判断结果称为命题的作为命题的陈述句所表达的判断结果称为命题的真值真值, 真值只有真值只有2个个:真或假。用真或假。用T , F或或1 , 0表示。表示。当判断正确或符合客观实际时，称该命题当判断正确或符合客观实际时，称该命题真真(true)， 否则称该命题否则称该命题假假(false)。任何命题的真值都是唯一的任何命题的真值都是唯一的.判断给定句子是否为命题的步骤判断给定句子是否为命题的步骤:首先判定它是否为陈述句首先判定它是否为陈述句判断它

8、是否有唯一的真值判断它是否有唯一的真值.疑问句、祈使句、感叹句和悖论等都不是命题。疑问句、祈使句、感叹句和悖论等都不是命题。悖论悖论：由真推出假又由假推出真的陈述句称为悖：由真推出假又由假推出真的陈述句称为悖论。即自相矛盾的句子。论。即自相矛盾的句子。-14-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v命题举例命题举例 雪是白的雪是白的 半径为半径为1的圆的的圆的周长周长为为2 2是偶数是偶数且且3也是偶数也是偶数 陈胜起义那天杭州下雨陈胜起义那天杭州下雨 大于大于2的偶数均可以分解为两个质数的和的偶数均可以分解为两个质数的和 数学多美啊数学多美啊! X+Y=4 “我正在说谎。我正在说谎。”

9、 我只给那些不给自己刮胡子的人刮胡子我只给那些不给自己刮胡子的人刮胡子TTFT-15-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v原子命题和复合命题原子命题和复合命题原子命题：原子命题：一个不能再分解成更简单语句的命题一个不能再分解成更简单语句的命题原子命题是最简单的陈述句原子命题是最简单的陈述句 （1）雪是白的。(T)（2）2+2=5(F)（3）2是素数。(T)（4）北京是中国的首都。(T) 上述命题都是简单陈述句，他们都不能分解为更上述命题都是简单陈述句，他们都不能分解为更简单的陈述句了，称这样的命题为简单的陈述句了，称这样的命题为原子命题.-16-第第9讲讲 命题与逻辑联结词命题与逻辑

10、联结词v原子命题和复合命题原子命题和复合命题原子命题通常记为原子命题通常记为p、q、r等小写字母，等小写字母，f表示表示恒假命题，恒假命题，t表示恒真命题。表示恒真命题。例：例：p：2000年年4月月5日是星期一。日是星期一。 q: 星期二的前一天是星期一。星期二的前一天是星期一。 恒真恒真 -17-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v原子命题和复合命题原子命题和复合命题命题常元和变元命题常元和变元原子命题原子命题有确定有确定的的真值，又真值，又称为命题常元。称为命题常元。命题变元是指一个命题变元是指一个未确定真值未确定真值的任意命题，其的任意命题，其值在值在0，1上变化上变化。例例

11、 p: x+y=5 不是命题，但不是命题，但x,y一旦确定，它一旦确定，它的真值就确定了。的真值就确定了。这种真值可以变化的简单陈这种真值可以变化的简单陈述句称为命题变元。述句称为命题变元。命题命题变元变元也用也用p、q、r等小写字母等小写字母表示表示。-18-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v原子命题和复合命题原子命题和复合命题复合复合命题：命题： 相对于原子命题的是相对于原子命题的是复合命题复合命题，它是由原子命题，它是由原子命题通过通过逻辑联结词逻辑联结词进行适当的组合而成的进行适当的组合而成的 。复合命题的真值不仅依赖于这两个组成它的命题，而且复合命题的真值不仅依赖于这两个

12、组成它的命题，而且还依赖于这个还依赖于这个联结词联结词的意义的意义 。-19-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v举例举例p：3是素数是素数；q：3是偶数是偶数 利用联结词利用联结词“不不”、“或或”、“且且”等可分别等可分别构成新命题：构成新命题： “非非p”：3不是素数不是素数“p或或q” ：3是素数或偶数是素数或偶数“p并且并且q”： 3是素数且是偶数是素数且是偶数带连接词的命题：带连接词的命题：1）并非并非2是无理数。是无理数。(T)2） 4是偶数是偶数且且4也是素数。也是素数。(F)3）2或或4是素数。是素数。(T)4）如果如果角角A和角和角B是对顶角，是对顶角，则则角角A

13、=角角B 。(T)5）两个三角形全等两个三角形全等当且仅当当且仅当它们的它们的3组对应边相等。组对应边相等。 (T) 这几个命题的真值不仅依赖于这两个组成它的命题，而这几个命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这些联结词的意义。像这样的联结词称为且还依赖于这些联结词的意义。像这样的联结词称为逻逻辑联结词辑联结词（logical connectives）。）。练习练习 所以所以复合命题复合命题是由若干个是由若干个简单命题简单命题和和若干个若干个连接词连接词构成的。构成的。 下面我们下面我们将将连接词也符号化连接词也符号化。-22-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常

14、用5 5个逻辑联结词个逻辑联结词 一一.否定词否定词(negation) ：“P 表示表示P不成立不成立”、“并并非非P” 否定词是一元运算。否定词是一元运算。否定的是整个命题否定的是整个命题，并不是否定命题中个别的词。，并不是否定命题中个别的词。“A A和和B B都大于都大于0 0”的否定：的否定：“A A和和B B都不大于都不大于0 0”“A A和和B B不都大于不都大于0 0”“A A和和B B至少有一个不大于至少有一个不大于0 0”“A A和和B B至少有一个小于等于至少有一个小于等于0 0”“A大于大于0”的否定：的否定： “A不大于不大于0” “A小于等于小于等于0”-23-第第9

15、讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用的的5 5个逻辑联结词个逻辑联结词 真值表真值表将复合命题的所有变元的所将复合命题的所有变元的所有取值列成表，就构成真值表有取值列成表，就构成真值表PP0110真值表真值表* *练习练习1：设：设 P:今天是周三。今天是周三。 则则 P表示什么？表示什么？练习练习2：设：设 Q:所有的自然数都是偶数。所有的自然数都是偶数。 则则 Q表示什么？表示什么？-25-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词二二. 合取词合取词(conjunction) ： pq表示表示“p并且并且q”、“p和和q都成立都成立”

16、合取词是二元运算合取词是二元运算只有当只有当p和和q均为真时，均为真时，pq才是真才是真的，否则，的，否则，pq是假的是假的是可交换的是可交换的pqpq000010100111p:今天是星期四；今天是星期四；q:今天上离散数学课；今天上离散数学课；p q：今天是星期四并且上离散数学课；：今天是星期四并且上离散数学课；* *例例1.如果如果P表示命题表示命题“你去了学校你去了学校”,Q表示命题表示命题“我去了工厂我去了工厂”， 那么那么PQ表示命题表示命题”你去了学校并且我去了工厂你去了学校并且我去了工厂“。 PQ为真，当且仅当你、我分别去了学校和工厂。为真，当且仅当你、我分别去了学校和工厂。注

17、注:使用合取联结词时，不要求两命题间一定有任何关系。使用合取联结词时，不要求两命题间一定有任何关系。例例2：P :今天下雨了今天下雨了。Q :教室里有教室里有100把椅子。把椅子。 则则,PQ：今天下雨了且教室里有今天下雨了且教室里有100把椅子。把椅子。离散数学第一章：命题逻辑对的说明的说明是二元连接词是二元连接词PQ中的中的P，Q可以没有内在联系（如例可以没有内在联系（如例2）具有对称性，具有对称性， PQ 与与Q P 的真值相同的真值相同P P=F可以把若干个命题连接在一起可以把若干个命题连接在一起.如，如， P Q R S 补充练习补充练习: 将下列命题符号化。将下列命题符号化。 (1

18、) 吴颖吴颖既既用功用功又又聪明。聪明。 (2) 吴颖吴颖不仅不仅用功用功而且而且聪明。聪明。 (3) 吴颖吴颖虽然虽然聪明，聪明，但但不用功。不用功。 (4) 张辉张辉和和王丽王丽都都是三好学生。是三好学生。 (5) 张辉与王丽是同学。张辉与王丽是同学。 步步骤骤： 先找原子命先找原子命题并题并符符号号化化 再找再找连连接接词词1.1. 将将原命原命题题符符号号化化解解 ：首先首先将将原子命原子命题题符符号号化：化： p p: : 吴颖吴颖用功。用功。, ,q q: : 吴颖聪吴颖聪明。明。 r r: : 张辉张辉是三好是三好学学生。生。 s s: : 王王丽丽是三好是三好学学生。生。 u

19、u : :张辉与张辉与王王丽丽是同是同学学。 则则(1)到到(4)分别符号化为分别符号化为 pq，pq，qp，rs. (5)(5)是原子命是原子命题题，符，符号号化化为为u u. .补充练习补充练习:将下列命题符号化。将下列命题符号化。 (1) 吴颖吴颖既既用功用功又又聪明。聪明。 (2) 吴颖吴颖不仅不仅用功用功而且而且聪明。聪明。 (3) 吴颖吴颖虽然虽然聪明，聪明，但但不用功。不用功。 (4) 张辉张辉和和王丽王丽都都是三好学生。是三好学生。 (5) 张辉与王丽是同学。张辉与王丽是同学。 (1)(1)到到(4)(4)都是都是复合命题，它们使用的联结词表面看来各不相同，但都是合取联结词，都

20、应符号化为，在(5)中，虽然也使用了联结词“与”，但这个联结词“与”是联结该句主语的，而整个句子仍是简单陈述句，所以(5)是原子命题，-30-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词析取词析取词(disjunction) ： pq，“p成立或者成立或者q成立成立”、“p或或q”析取词是二元运算析取词是二元运算只有当只有当p和和q的真值均为假时，的真值均为假时， pq才是假的，否则才是假的，否则, pq总是真的总是真的pqpq000011101111p:我上午上离散数学；我上午上离散数学；q:我上午上概率统计；我上午上概率统计；p q：我上午或者上离散

21、：我上午或者上离散数学，或者上数学，或者上概率统计；概率统计；p:我上午一二节课上离散数学；我上午一二节课上离散数学；q:我上午一二节课上我上午一二节课上概率统计；概率统计；p q：我上午一二节课要么上：我上午一二节课要么上离散数学，要么上离散数学，要么上概率统计概率统计(不不会上两门会上两门)；同或同或异或异或 总结总结：析取析取一般代表汉语中的一般代表汉语中的“或或”，但汉语中的，但汉语中的“或或”是多含是多含义的，见下表：义的，见下表：或的含义或的含义例子例子说明说明可兼或可兼或晚会上她唱歌或跳舞晚会上她唱歌或跳舞二者均发生或二者之一发生二者均发生或二者之一发生排斥或排斥或 他上他上“师

22、大师大”或或“南开南开”非此即彼，不可兼得非此即彼，不可兼得表示近似值的或表示近似值的或他休息他休息5或或10分钟分钟近似数，近似数，5至至10分钟分钟由析取的定由析取的定义义可知，可知， 表示可兼或。表示可兼或。例例1：如果如果p，q分别表示分别表示“今晚我看书今晚我看书”和和“今晚我看电视今晚我看电视”， 那么那么pq表示表示“今晚我看书或者看电视今晚我看书或者看电视”。 当我今晚看了书，或者看了电视，或者既看了书又看了电视当我今晚看了书，或者看了电视，或者既看了书又看了电视时，时，pq为真，只是在我既不看书也不看电视时为真，只是在我既不看书也不看电视时pq为假。为假。 值得注意的是值得注

23、意的是，这里的，这里的“或或”是所谓可兼的，即当是所谓可兼的，即当p和和q有一为有一为真时，确认真时，确认pq为真。为真。则则原原命题可表示为：命题可表示为：()()PQPQ 例例2.2.一晚上他在家看书或出去散步。一晚上他在家看书或出去散步。解：解：不可兼或不可兼或 P P：他一晚上在家看书。：他一晚上在家看书。 Q Q：他一晚上出去散步。：他一晚上出去散步。 不可兼或也称排斥或，它表示这一新命题当P为真且Q为假时成真，或反过来，当P为假且Q为真时成真。 P和Q均为真或均为假时，这一命题为假。即当P和Q中恰有一个为真时它成真，否则它为假。对对的说明的说明是二元连接词是二元连接词P Q中的中的

24、P，Q可以没有内在联系（如例可以没有内在联系（如例2）具有对称性，具有对称性， PQ 与与Q P 的真值相同的真值相同P P=T可以把若干个命题连接在一起可以把若干个命题连接在一起.如，如， P Q R S-35-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词蕴涵词蕴涵词(implication) ： pq，“如果如果p，那么，那么q”、“p蕴涵蕴涵q”、“p是是q的充分条件的充分条件” 从真值表可以看出，只有当前提为从真值表可以看出，只有当前提为真，而结论是假时，真，而结论是假时，pq才是假的才是假的 pqpq001011100111逆命题逆命题：qp；

25、否命题否命题：pq逆否命题逆否命题：qp命题和逆否命题有相同命题和逆否命题有相同的真值（的真值（验证一下验证一下）“如果今天是星期三，那么如果今天是星期三，那么2+3=62+3=6”：前提为假，蕴涵命题为真；前提为假，蕴涵命题为真；前提和结论之间可以没有关系，前提和结论之间可以没有关系，称为实质蕴涵称为实质蕴涵p:天晴；天晴； q:我爬山；我爬山；只要天晴，我就爬山：只要天晴，我就爬山： p q 只有天晴，我才爬山：只有天晴，我才爬山： q p 注意注意： 在使用联结词在使用联结词时，要特别注意以下几点：时，要特别注意以下几点： 1在自然语言中，在自然语言中，“如果如果p，则，则q”中的前件中

26、的前件p与后件与后件q往往往往具有某种内在联系。而具有某种内在联系。而在数理逻辑中，在数理逻辑中，p与与q可以无任何内可以无任何内在联系。在联系。 2在数学或其它自然科学中，在数学或其它自然科学中，“如果如果p，则，则q”往往表达的往往表达的是前件是前件p为真，后件为真，后件q也为真的推理关系。但在数理逻辑中，也为真的推理关系。但在数理逻辑中，作为一种规定，当作为一种规定，当p为假时，无论为假时，无论q是真是假，是真是假，pq均为真。均为真。也就是说，只有也就是说，只有p为真为真q为假这一种情况使得复合命题为假这一种情况使得复合命题pq为假。为假。 例例1 将命题将命题“如果天气好，那么我去接

27、你。如果天气好，那么我去接你。”符号化。符号化。解：设解：设p表示表示“天气好天气好”，q表示表示“我去接你我去接你”， 那么，那么，pq表示原命题。表示原命题。当天气好时，当天气好时， 我去接了你，这时诺言我去接了你，这时诺言pq真；真； 我没去接你，则诺言我没去接你，则诺言pq假。假。 当天气不好时，当天气不好时，我无论去或不去接你均未食言，此我无论去或不去接你均未食言，此时认定时认定 pq为真是适当的。为真是适当的。 、 、注： 较较 三三个联结词难个联结词难理解，但若要理解，但若要对对命命题间题间因果因果关关系系进进行表行表达达，则则必必须须引用引用 。例例2 2：令：令P:P:天天气

28、气好好 ，Q:Q:我去公我去公园园试将试将下列命下列命题题符符号号化化1 1）若天）若天气气好，我就去公好，我就去公园园。 符符号号化化为为：2 2）仅当仅当天天气气好，我才去公好，我才去公园园。 符符号号化化为为：PQQP-39-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词双向蕴涵词双向蕴涵词(two-way implication) p q，“p当且仅当当且仅当q”、 “如果如果p，那么，那么q；反之亦然；反之亦然”只有当只有当p和和q的真值相同时，的真值相同时，pq才取才取真的真值真的真值 pq与与(pq)(qp)有完全相同的有完全相同的真值真值。

29、（验证一下验证一下）pqpq001010100111“只有你健康，你才会感到快乐；只有你健康，你才会感到快乐；只有感觉快乐你才健康只有感觉快乐你才健康”* *例例1如果p表示命题“ABCABC”，q表示命题“ABC与ABC的三边对应相等”，那么pq表示平面几何中的一个真命题，因为p真时q显然真，p假时q亦必然假，故p与q同真值。若q表示命题“ABC与ABC的三内角对应相等”那么pq不再是恒真的了，因p假时q未必为假。离散数学第一章：命题逻辑练习: 将将下列命下列命题题符符号号化，化，并讨论它们并讨论它们的的真值真值。 (1) (1) 根根号号5 5是无理是无理数当数当且且仅当仅当加拿大位于加拿

30、大位于亚亚洲。洲。 (2) 2+3(2) 2+35 5的充要的充要条条件是根件是根号号5 5是无理是无理数数。 (3) (3) 若若两圆两圆A A，B B的面的面积积相等，相等，则它们则它们的半的半径径相等；反之相等；反之亦然。亦然。 (4) (4) 当当王小王小红红心情愉快心情愉快时时，她她就唱歌；反之，就唱歌；反之，当她当她唱歌唱歌时时，一定心情愉快。一定心情愉快。 解解 (1)(1): : 令令p p： 根根号号5 5是无理是无理数数，真值为真值为1 1， q q：加拿大位于：加拿大位于亚亚洲，洲，真值为真值为0 0， 则将则将(1)(1)符符号号化化为为p p q q，其，其真值为真值

31、为0. 0. (2)(2): : 令令r r：2 23 35 5，其，其真值为真值为1 1， 则将则将(2)(2)符符号号化化为为r r p p，真值为真值为1. 1. (3)(3): : 令令s s：两圆两圆A A，B B面面积积相等，相等， t t：两圆两圆A A，B B的半的半径径相等，相等， 则将则将(3)(3)符符号号化化为为s s t t，虽虽然不知道然不知道s s，t t的的真值真值，但由，但由s s与与t t的的内内在在联联系可知，系可知，s s t t的的真值为真值为1. 1. (4)(4): : 令令u u：王小：王小红红心情愉快，心情愉快， v v：王小：王小红红唱歌，唱

32、歌， 则将则将(4)(4)符符号号化化为为u u v. v.其其真值真值要由具体情要由具体情况况而定。而定。 练习练习：填填空空PQPQPQPQ已知已知 为为T T，则则P P为为（ ），），Q Q为为（ ）。）。已知已知 为为F F，则则P P为为（ ），），Q Q为为（ ）。）。已知已知P P为为F F，则则 为为（ ）。）。已知已知P P为为T T，则则 为为（ ）。）。已知已知 为为T T，且，且P P为为F F，则则Q Q为为（ ）。）。已知已知 为为F F，则则P P为为（ ），），Q Q为为（ ）。）。已知已知P P为为F F，则则 为为（ ）。）。已知已知Q Q为为T T，则则

33、 为为（ ）。）。已知已知 为为F F，则则P P为为（ ），），Q Q为为（ ）。）。 已知已知P P为为T T， 为为T T，则则Q Q为为（ ）。）。PQPQPQPQPQ PQT TT TT TT TT TF FF FF FF FF FT TT TT TT T以上定义了五种最基本、最常用、也是最重要的联结词以上定义了五种最基本、最常用、也是最重要的联结词， ，将它们组成一个集合，将它们组成一个集合， ，称为一个，称为一个联结词集联结词集。其中。其中为一元联结词，其余的都为一元联结词，其余的都是二元联结词。是二元联结词。 使用这些联结词有什么好处呢？使用这些联结词有什么好处呢？ 可以将复杂

34、命题表示成简单可以将复杂命题表示成简单的符号公式。的符号公式。注意： 4 4个联个联接接词构词构成的成的复复合命合命题题均可不均可不顾顾及命及命题间题间是否有是否有内内在在联联系，而只是根据系，而只是根据联联接接词词和原子命和原子命题题的的真真值值确定确定它们它们的的真值真值。 、 、 、-45-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v命题公式命题公式 (proposition formula) (proposition formula) 命题公式：命题公式：是一个表达式，它是由命题常元、命题是一个表达式，它是由命题常元、命题变元、联结词符号和圆括号所组成的一个字符串变元、联结词符号和圆

35、括号所组成的一个字符串 归纳定义：（归纳定义：（看看16页归纳定义页归纳定义）命题常元和命题变元是命题公式，也称为原子公式或原子命题常元和命题变元是命题公式，也称为原子公式或原子如果如果A，B是命题公式，那么（是命题公式，那么（A）、（）、（AB）、）、 （AB）、（）、（AB）、（）、（AB）也是命题公式）也是命题公式只有有限步引用条款（只有有限步引用条款（1）、（）、（2）所组成的符号串是命题）所组成的符号串是命题公式公式 -46-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v简写约定简写约定为了减少圆括号的使用，我们约定：为了减少圆括号的使用，我们约定：省掉最外面的括号省掉最外面的括号联

36、结词的优先级从高到低是联结词的优先级从高到低是 、（、（、）、）、结合能力平等的联结词从左到右运算结合能力平等的联结词从左到右运算(p) (q (r q) s)p q (r q s)-47-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v指派指派(assignment) (assignment) 设设公式公式A含有含有n个命题变元个命题变元p1， p2 ， pn记为记为A(p1, pn ) 给定这给定这n个变元任意一组确定的值个变元任意一组确定的值（每一变元都（每一变元都有取真或假两种可能），公式有取真或假两种可能），公式A得到一个确定的得到一个确定的值（值（1或或0），），我们称这一组确定的值

37、为公式我们称这一组确定的值为公式A的的一组完全指派一组完全指派 常用常用 表示指派，若在某一指派表示指派，若在某一指派 下下A取真的真值，取真的真值，则称则称 弄真弄真A，记为，记为 (A)=1, 反之称反之称 弄假弄假A，记，记为为 (A)=0 -48-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v指派举例指派举例使公式使公式A: (pq)r)p为真的指派为真的指派 (A)=11. (pq)r)=1， (p)=1， 2. (pq)r)=0， (p)=0 (r)=0, ( (r r)=1)=11.1. (q)=11.1.1. (r)=01.1.2. (r)=1 1.2. (q q)=01.2.

38、1. (r)=02.1. (q)=02.2. (q)=1(1,1,0)(1,1,1)(1,0,0)(0,0,1)(0,1,1)-49-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v复合命题公式的真值表复合命题公式的真值表 首先确定在公式中出现的首先确定在公式中出现的命题变元的个数。命题变元的个数。写出公式写出公式A的的所有指派所有指派，一个指派为一行，若有，一个指派为一行，若有n个命题变个命题变元，则有元，则有2n组指派，也就是说真值表有组指派，也就是说真值表有2n+1行。行。确定公式中确定公式中联结词的个数联结词的个数，写出单个联结词的真值，一般讲，写出单个联结词的真值，一般讲，一个联结词对

39、应着一列。一个联结词对应着一列。 (pq)r)p的真值表的真值表 pqrpqr(pq)r(pq)r)p00001100010001010011001100011000111101000011011111111011(PQ)0110原命原命题题Q QP PPQ（）P Q （）PQPQ （）（）0 01 11 11 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 1例例2 2：上海到北京的14次列车是下午五点半开或六点开。复合命题的真值表复合命题的真值表 -51-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v语句形式化举例语句

40、形式化举例设设p：a是偶数是偶数 q：a是奇数是奇数 r：a是质数是质数 s：a=2，如，如何理解下述命题公式何理解下述命题公式pq lpr s p （r s）rs q（qs）r r （q s）1.r q s-52-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v语句形式化举例语句形式化举例 我和他既是兄弟又是同学我和他既是兄弟又是同学 pq，其中：，其中：p：我和他是兄弟，：我和他是兄弟，q：我和他是同学：我和他是同学 我和他至少有一个要去外地我和他至少有一个要去外地pq，其中：，其中：p：我去外地，：我去外地，q：他去外地：他去外地 狗急跳墙狗急跳墙pq，其中：，其中： p：狗急了，：狗急了

41、，q：狗跳墙：狗跳墙 除非他来，否则我不同他和解除非他来，否则我不同他和解pq，(pq)(pq)，其中：，其中： p：他来，：他来，q：我同他和解：我同他和解-53-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v语句形式化举例语句形式化举例 如果你和他不都是傻子，那么你们俩都不会如果你和他不都是傻子，那么你们俩都不会去自讨没趣去自讨没趣（pq）（rs），其中：），其中： p：你是傻子；：你是傻子；q：他是傻子：他是傻子r：你会去自讨没趣；：你会去自讨没趣；s：他会去自讨没趣：他会去自讨没趣 若天气若天气不不下雨或不起雾，则航行比赛将举行下雨或不起雾，则航行比赛将举行而且救生表演将进行而且救生表演将进行 如果他如果他没来没来见你，那么他或者是生病了，或见你，那么他或者是生病了，或者是者是不不在本地在本地vPowerPoint Template_Sub 侦探调查了罪案的四个证人。从证人的话侦探得出的结论侦探调查了罪案的四个证人。从证人的话侦探得出的结论是：是：如果男管家说的是真话，那么厨师说的也是真话；如