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

11级专业选修课程授课人：王薇信息与计算教研室本教材离散数学知识结构离散数学前言PowerPointTemplate_Sub

逻辑学是一门非常古老的学科，它是研究人类推理过程的科学。到现在已经有了两千多年的历史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说，他创作的《工具论》一书是古代一部最完备的逻辑学著作。古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一旦超出这个范围，引入数学的方法来研究逻辑，就产生了远远优于古典逻辑学的现代逻辑学。

数理逻辑也称符号逻辑，是现代逻辑学研究的主体部分，是一门运用数学方法研究思维规律的边缘性学科。将推理变成数学演算，这是数理逻辑的指导思想，并且已经成为这门学科的主要特征

。数理逻辑是用形式化(符号化)方法来研究推理的科学。*

命题逻辑研究命题和命题连接词的逻辑结构以及命题之间的推理关系。命题逻辑:推理的基本要素是命题.

引言

先看著名物理学家爱因斯坦出过的一道题：

一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个人更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”

请问这个人说得对吗？他是怎么推导出来的呢？

要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程：

(1)什么是前提？有哪些前提？

(2)结论是什么？

(3)根据什么进行推理？

(4)怎么进行推理？学习命题逻辑将回答这几个问题。-8-第9讲命题与逻辑联结词PowerPointTemplate_Sub

1命题与逻辑联结词2逻辑等价式和逻辑蕴涵式3范式4证明技术（补充）命题与逻辑联结词《离散数学》第9讲Page56to78-10-第9讲命题与逻辑联结词内容提要命题的概念命题、命题真值表示原子命题和复合命题、命题常元、命题变元逻辑联结词┐、∧、∨、→、

命题公式

公式的归纳定义指派自然语句的形式化-11-第9讲命题与逻辑联结词命题(proposition或statement)命题：是一句有确定真假值的陈述句。命题只有两个结果，或是真，或是假，但二者不能得兼（排中律），也不能不真又不假。真、假常被称为命题的真值。

命题的真值

作为命题的陈述句所表达的判断结果称为命题的真值,

真值只有2个:真或假。用T,F或1,0表示。

当判断正确或符合客观实际时，称该命题真(true)，

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

“我正在说谎。”我只给那些不给自己刮胡子的人刮胡子√T√T√F√√T××××-15-第9讲命题与逻辑联结词原子命题和复合命题原子命题：一个不能再分解成更简单语句的命题原子命题是最简单的陈述句（1）雪是白的。(T)

（2）2+2=5(F)

（3）2是素数。(T)

（4）北京是中国的首都。(T)上述命题都是简单陈述句，他们都不能分解为更简单的陈述句了，称这样的命题为原子命题.-16-第9讲命题与逻辑联结词原子命题和复合命题原子命题通常记为p、q、r等小写字母，f表示恒假命题，t表示恒真命题。例：p：2000年4月5日是星期一。q:星期二的前一天是星期一。恒真

-17-第9讲命题与逻辑联结词原子命题和复合命题命题常元和变元原子命题有确定的真值，又称为命题常元。命题变元是指一个未确定真值的任意命题，其值在{0，1}上变化。例p:x+y=5不是命题，但x,y一旦确定，它的真值就确定了。这种真值可以变化的简单陈述句称为命题变元。命题变元也用p、q、r等小写字母表示。-18-第9讲命题与逻辑联结词原子命题和复合命题复合命题：相对于原子命题的是复合命题，它是由原子命题通过逻辑联结词进行适当的组合而成的。复合命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这个联结词的意义。-19-第9讲命题与逻辑联结词举例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=角B。(T)5）两个三角形全等当且仅当它们的3组对应边相等。(T)

这几个命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这些联结词的意义。像这样的联结词称为逻辑联结词（logicalconnectives）。练习

所以复合命题是由若干个简单命题和若干个连接词构成的。

下面我们将连接词也符号化。-22-第9讲命题与逻辑联结词常用5个逻辑联结词一.否定词(negation)：┐“┐P

表示P不成立”、“并非P”否定词是一元运算。否定的是整个命题，并不是否定命题中个别的词。“A和B都大于0”的否定：“A和B都不大于0”“A和B不都大于0”“A和B至少有一个不大于0”“A和B至少有一个小于等于0”“A大于0”的否定：“A不大于0”“A小于等于0”×-23-第9讲命题与逻辑联结词常用的5个逻辑联结词真值表将复合命题的所有变元的所有取值列成表，就构成真值表P┐P0110真值表*练习1：设P:今天是周三。则┐P表示什么？练习2：设Q:所有的自然数都是偶数。则┐Q表示什么？-25-第9讲命题与逻辑联结词常用5个逻辑联结词二.合取词(conjunction)：∧

p∧q表示“p并且q”、“p和q都成立”合取词是二元运算只有当p和q均为真时，p∧q才是真的，否则，p∧q是假的∧是可交换的pqp∧q000010100111p:今天是星期四；q:今天上离散数学课；p∧q：今天是星期四并且上离散数学课；*例1.

如果P表示命题“你去了学校”,Q表示命题“我去了工厂”，那么P∧Q表示命题”你去了学校并且我去了工厂“。

P∧Q为真，当且仅当你、我分别去了学校和工厂。注:使用合取联结词时，不要求两命题间一定有任何关系。例2：P:今天下雨了。

Q:教室里有100把椅子。则,P∧Q：今天下雨了且教室里有100把椅子。离散数学

第一章：命题逻辑对∧的说明∧是二元连接词P∧Q中的P，Q可以没有内在联系（如例2）∧具有对称性，P∧Q与Q∧P的真值相同P∧┐P=F∧可以把若干个命题连接在一起.如，

P∧Q∧R∧S

补充练习:

将下列命题符号化。

(1)吴颖既用功又聪明。

(2)吴颖不仅用功而且聪明。

(3)吴颖虽然聪明，但不用功。

(4)张辉和王丽都是三好学生。

(5)张辉与王丽是同学。

步骤：先找原子命题并符号化再找连接词将原命题符号化解

：首先将原子命题符号化：

p:吴颖用功。,

q:吴颖聪明。

r:张辉是三好学生。

s:王丽是三好学生。

u

:张辉与王丽是同学。

则(1)到(4)分别符号化为

p∧q，p∧q，q∧┐p，r∧s.

(5)是原子命题，符号化为u.补充练习:将下列命题符号化。

(1)吴颖既用功又聪明。

(2)吴颖不仅用功而且聪明。

(3)吴颖虽然聪明，但不用功。

(4)张辉和王丽都是三好学生。

(5)张辉与王丽是同学。

(1)到(4)都是复合命题，它们使用的联结词表面看来各不相同，但都是合取联结词，都应符号化为∧，在(5)中，虽然也使用了联结词“与”，但这个联结词“与”是联结该句主语的，而整个句子仍是简单陈述句，所以(5)是原子命题，-30-第9讲命题与逻辑联结词常用5个逻辑联结词析取词(disjunction)：∨

p∨q，“p成立或者q成立”、“p或q”析取词是二元运算只有当p和q的真值均为假时，p∨q才是假的，否则,

p∨q总是真的pqp∨q000011101111p:我上午上离散数学；q:我上午上概率统计；p∨

q：我上午或者上离散数学，或者上概率统计；p:我上午一二节课上离散数学；q:我上午一二节课上概率统计；p∨

q：我上午一二节课要么上离散数学，要么上概率统计(不会上两门)；同或异或

总结：析取∨一般代表汉语中的“或”，但汉语中的“或”是多含义的，见下表：或的含义例子说明可兼或晚会上她唱歌或跳舞二者均发生或二者之一发生排斥或

他上“师大”或“南开”非此即彼，不可兼得表示近似值的或他休息5或10分钟近似数，5至10分钟由析取的定义可知，∨表示可兼或。例1：

如果p，q分别表示“今晚我看书”和“今晚我看电视”，那么p∨q表示“今晚我看书或者看电视”。当我今晚看了书，或者看了电视，或者既看了书又看了电视时，p∨q为真，只是在我既不看书也不看电视时p∨q为假。

值得注意的是，这里的“或”是所谓可兼的，即当p和q有一为真时，确认p∨q为真。则原命题可表示为：例2.一晚上他在家看书或出去散步。解：不可兼或

P：他一晚上在家看书。Q：他一晚上出去散步。

不可兼或也称排斥或，它表示这一新命题当P为真且Q为假时成真，或反过来，当P为假且Q为真时成真。P和Q均为真或均为假时，这一命题为假。即当P和Q中恰有一个为真时它成真，否则它为假。对∨的说明∨是二元连接词P∨Q中的P，Q可以没有内在联系（如例2）∨具有对称性，P∧Q与Q∧P的真值相同P∨┐P=T∨可以把若干个命题连接在一起.如，

P∨Q∨R∨S-35-第9讲命题与逻辑联结词常用5个逻辑联结词蕴涵词(implication)：→

p→q，“如果p，那么q”、“p蕴涵q”、“p是q的充分条件”从真值表可以看出，只有当前提为真，而结论是假时，p→q才是假的pqp→q001011100111逆命题：q→p；否命题：┐p→┐q逆否命题：┐q→┐p命题和逆否命题有相同的真值（验证一下）“如果今天是星期三，那么2+3=6”：前提为假，蕴涵命题为真；前提和结论之间可以没有关系，称为实质蕴涵p:天晴；q:我爬山；只要天晴，我就爬山：

p→

q

只有天晴，我才爬山：q

→p

注意：在使用联结词→时，要特别注意以下几点：

1．在自然语言中，“如果p，则q”中的前件p与后件q往往具有某种内在联系。而在数理逻辑中，p与q可以无任何内在联系。

2．在数学或其它自然科学中，“如果p，则q”往往表达的是前件p为真，后件q也为真的推理关系。但在数理逻辑中，作为一种规定，当p为假时，无论q是真是假，p→q均为真。也就是说，只有p为真q为假这一种情况使得复合命题p→q为假。

例1

将命题“如果天气好，那么我去接你。”符号化。解：设p表示“天气好”，q表示“我去接你”，那么，p→q表示原命题。

当天气好时，

我去接了你，这时诺言p→q真；

我没去接你，则诺言p→q假。

当天气不好时，我无论去或不去接你均未食言，此时认定p→q为真是适当的。

注：较三个联结词难理解，但若要对命题间因果关系进行表达，则必须引用。例2：令P:天气好，Q:我去公园试将下列命题符号化1）若天气好，我就去公园。符号化为：2）仅当天气好，我才去公园。符号化为：-39-第9讲命题与逻辑联结词常用5个逻辑联结词双向蕴涵词(two-wayimplication)pq，“p当且仅当q”、

“如果p，那么q；反之亦然”只有当p和q的真值相同时，pq才取真的真值pq与(p→q)∧(q→p)有完全相同的真值。（验证一下）pqpq001010100111“只有你健康，你才会感到快乐；只有感觉快乐你才健康”*例1

如果p表示命题“△ABC△A‘B’C‘”，

q表示命题“△ABC与△A‘B’C‘的三边对应相等”，那么pq表示平面几何中的一个真命题，因为p真时q显然真，p假时q亦必然假，故p与q同真值。若q表示命题“△ABC与△A‘B’C‘的三内角对应相等”那么pq不再是恒真的了，因p假时q未必为假。离散数学

第一章：命题逻辑练习:

将下列命题符号化，并讨论它们的真值。

(1)根号5是无理数当且仅当加拿大位于亚洲。

(2)2+3＝5的充要条件是根号5是无理数。

(3)若两圆A，B的面积相等，则它们的半径相等；反之亦然。

(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。解

(1):令p：根号5是无理数，真值为1，

q：加拿大位于亚洲，真值为0，

则将(1)符号化为pq，其真值为0.

(2):令r：2＋3＝5，其真值为1，则将(2)符号化为rp，真值为1.

(3):令s：两圆A，B面积相等，

t：两圆A，B的半径相等，

则将(3)符号化为st，虽然不知道s，t的真值，但由s与t的内在联系可知，st的真值为1.

(4):令u：王小红心情愉快，

v：王小红唱歌，

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

以上定义了五种最基本、最常用、也是最重要的联结词┐，∧，∨，→，，将它们组成一个集合{┐，∧，∨，→，

}，称为一个联结词集。其中┐为一元联结词，其余的都是二元联结词。

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

归纳定义：（看16页归纳定义）命题常元和命题变元是命题公式，也称为原子公式或原子如果A，B是命题公式，那么（┐A）、（A∧B）、

（A∨B）、（A→B）、（AB）也是命题公式只有有限步引用条款（1）、（2）所组成的符号串是命题公式-46-第9讲命题与逻辑联结词简写约定为了减少圆括号的使用，我们约定：省掉最外面的括号联结词的优先级从高到低是┐、（∧、∨）、→、结合能力平等的联结词从左到右运算((┐p)→(q∨((r∧q)s)))┐p→q∨(r∧qs)-47-第9讲命题与逻辑联结词指派(assignment)设公式A含有n个命题变元p1，p2

，…，pn记为A(p1,…,pn)给定这n个变元任意一组确定的值（每一变元都有取真或假两种可能），公式A得到一个确定的值（1或0），我们称这一组确定的值为公式A的一组完全指派常用表示指派，若在某一指派下A取真的真值，则称弄真A，记为

(A)=1,反之称弄假A，记为

(A)=0

-48-第9讲命题与逻辑联结词指派举例使公式A:((p∧q)∨┐r)p为真的指派(A)=11.((p∧q)∨┐r)=1，

(p)=1，2.((p∧q)∨┐r)=0，

(p)=0(┐r)=0,(r)=11.1.(q)=11.1.1.(r)=01.1.2.(r)=11.2.(q)=01.2.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讲命题与逻辑联结词复合命题公式的真值表首先确定在公式中出现的命题变元的个数。写出公式A的所有指派，一个指派为一行，若有n个命题变元，则有2n组指派，也就是说真值表有2n+1行。确定公式中联结词的个数，写出单个联结词的真值，一般讲，一个联结词对应着一列。

((p∧q)∨┐r)p的真值表pqrp∧q┐r(p∧q)∨┐r((p∧q)∨┐r)p00001100010001010011001100011000111101000011011111111011┐(PQ)0110原命题QP011111100000000000001111例2：上海到北京的14次列车是下午五点半开或六点开。复合命题的真值表

-51-第9讲命题与逻辑联结词语句形式化举例设p：a是偶数q：a是奇数r：a是质数s：a=2，如何理解下述命题公式p∨q

p∧r→sp→（r→s）r∧┐s→q┐（q∨s）→┐rr→（q∨s）rq∨s-52-第9讲命题与逻辑联结词语句形式化举例我和他既是兄弟又是同学p∧q，其中：p：我和他是兄弟，q：我和他是同学我和他至少有一个要去外地p∨q，其中：p：我去外地，q：他去外地狗急跳墙p→q，其中：p：狗急了，q：狗跳墙除非他来，否则我不同他和解pq，(p→q)∧(┐p→┐q)，其中：p：他来，q：我同他和解-53-第9讲命题与逻