离散数学：1-1 命题逻辑

离散数学1考核方法出勤(10’)：事假、病假均扣分，缺1/3不能考试；平时成绩(10’)：随堂测试，课堂表现，提问等；作业(10’)：分为优、良、阅、缺；最后成绩中，卷面成绩占70%，其他30%；2离散数学是计算机科学与技术的理论基础，如果说“高科技本质上是数学技术”的话，计算机科学与技术基本上是离散数学技术。自从计算机产生到以后的每一步发展都离不开数学，1936年A.M.Turing发表了著名论文：‘理想计算机’，从而给出了计算机设计的理论模型，1946年在J.von.Neumann领导下制造了世界第一台计算机ENIAC.离散数学一般包含如下5个主题：数学推理、组合分析、离散结构、算法思维、应用及模拟。3离散数学简介研究人的思维形式和规律的科学称为逻辑学，由于研究的对象和方法各有侧重而又分为形式逻辑、辨证逻辑和数理逻辑。数理逻辑是应用数学方法研究推理的科学。数理逻辑又叫符号逻辑，因为它的主要工具是符号体系。数理逻辑的核心是把逻辑推理符号化，即变成象数学演算一样完全形式化了的逻辑演算。4第一章命题逻辑前言51.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论第一章命题逻辑

6一、命题与真值二、命题分类：原子命题，复合命题三、命题常项与命题变项及其符号化四、联结词§1

命题符号化及联结词

所谓命题，是能判断真假的陈述句，且真与假必居其一。简言之，命题是非真即假的陈述句。命题是具有唯一真值的陈述句。命题是真就说其真值（或值）为真，命题是假就说其真值为假。判断命题的两个步骤：是否为陈述句；是否有确定的、唯一的真值。7命题与真值例1.1：判断下列句子是否为命题。(1).2是素数。(2).雪是黑色的。(3).2+3=5。(4).明年的10月1日是晴天。(5).3能被2整除。(6).这朵花多好看啊！(7).明天下午有会吗？8(8).请关上门！(9).x+y>5。(10).地球外的星球星球上也有人。说明：只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。910原子命题，命题常元/变元不能再分解的命题称为原子命题。用小写英文字母p,q,r…,pi

,qi,ri,…表示，将其放在命题的前面，称为命题符号化。命题常元/常项：简单命题，真值确定。命题变元/变项：真值可以变化的简单陈述句。命题变元不是命题！命题真值符号化：“

真”=1(或T)，“假”=0(或F)。复合命题与命题联结词由简单命题用命题联结词联结而成的命题，称为复合命题。例如，“明天下雪或明天下雨”是复合命题。命题联结词又称为逻辑运算符，常用的有五种，它们是：否定词、合取词、析取词、蕴涵词和等价词。11p¬p011012设p表示命题，复合命题“非p”(或“p的否定”)

称为p的否定式，记为¬p，读为“非p”。否定词可用右表定义，此表称为

¬p的真值表。由真值表可知，¬p为真，当且仅当p为假。1否定联结词

¬（p2）例p:天津是一个城市。

q:3是偶数。┐p:天津不是一个城市。

┐q:3不是偶数。例p:苏州处处清洁。

q:这些都是男同学。┐p:苏州不处处清洁(注意,不是处处不清洁)。┐q:这些不都是男同学。131例pqp∧q000110110001142合取联结词∧

（p2）若p，q为两命题，复合命题

“p并且q”称为p与q的合取式，记为p∧q,读为“p合取q”。p∧q

的真值表如右表所示。由真值表可知，p∧q

为真，当且仅当p、q同时为真。例

将下列命题符号化。（p3）(1)李平既聪明又用功。

(2)李平虽然聪明，但不用功。(3)李平不但聪明，而且用功。(4)李平不是不聪明，而是不用功。

（设p:李平聪明。q:李平用功。）例将下列命题符号化。

(1)李敏和李华是姐妹。(2)李敏和张华是朋友。注意：不要见到“与”、“和”就使用联结词“∧”！152例pqp∨q000110110111163析取联结词∨（p3）若p,q

为两命题，复合命题

“p或q”

称为p与q的析取式，记为p∨q,读为“p析取q”。p∨q

的真值表如右表所示。由真值表可知，p∨q

真,当且仅当p、q至少有一个真。（1）小王爱打球或爱跑步。（相容或）

设p：小王爱打球。q：小王爱跑步。（2）林芳学过英语或法语。（相容或）

设p：林芳学过英语。q：林芳学过法语。（3）派小王或小李中的一人去开会。（排斥或）

设p：派小王去开会。q：派小李去开会。（4）人固有一死，或重于泰山或轻于鸿毛。（？）（5）ab=0,即a=0或b=0.（？）由此可见,“p∨q”表示的是“相容或”。173例pqp→q000110111101184蕴涵词→（p3）若p,q

为两命题，复合命题“如果p，则q”称作p与q的蕴涵式，记为p→q，读为“p蕴涵q”。

p→q的真值表如右表所示。由真值表可知，p→q为假，当且仅当p为真且q为假。

p→q表示的基本逻辑关系是：q是p的必要条件，或p是q的充分条件。包括：“只要p就q”；“p仅当q”；“只有q才p”。p为蕴涵式的前件，q为蕴涵式的后件。19注意事项与自然语言不同：前件与后件可以没有任何内在联系！与实际生活的区别在日常生活或数学中，“若p则q”往往表示前件p为真，则后件q为真的推理关系，即只考虑p=1的情形，因为当p=0时，p→q没有实际意义。但数理逻辑中，当前件p为假时，不管q如何，p→q的真值为真。20关于p→q真值表的说明p→q真值表中规定：当p=0时，不管q如何，p→q的真值都为1。

有没有道理呢？例，张对李说：“我去图书馆一定帮你借X书”。可以将这句话表为命题p→q（p:张去图书馆，q:张借X书)。但后来张因有事未去图书馆，即p=0，此时按规定p→q为真。我们应理解为张讲了真话，即他要是去图书馆我们相信他一定会为李借书。这种理解也称为“善意推定”。21

例将下列命题符号化。（1）天不下雨，则草木枯黄。p：天下雨，q：草木枯黄。（2）如果小明学日语，小华学英语，则小芳学德语。p：小明学日语，q：小华学英语，r：小芳学德语。（3）只要不下雨，我就骑自行车上班。

只有不下雨，我才骑自行车上班。p：天下雨，q：我骑自行车上班。224例（4）如果2+2=4，则太阳从东方升起。

如果2+2=4，则太阳从西方升起。

如果2+2≠4，则太阳从东方升起。

如果2+2≠4，则太阳从西方升起。 p:2+2=4，q:太阳从东方升起， r:则太阳从西方升起。23pqp↔q000110111001245等价联结词↔(p4)若p,q

为两命题，复合命题“p当且仅当q”称为p与q的等价式，记为p↔q,读为“p等值于q”。

p↔q

的真值表如右表所示。由真值表可知，p↔q

为真，当且仅当p与q真值相同。注意事项同样，两命题之间可以没有任何内在联系！p与q互为充分必要条件，只要真值同为真或同为假，p↔q的真值为真，否则真值为假。25例将下列命题符号化。(1)2+2=4当且仅当3是奇数。

2+2=4当且仅当3不是奇数。 2+2≠4当且仅当3是奇数。 2+2≠4当且仅当3不是奇数。 p:2+2=4，q:3是奇数。(2)两圆的面积相等当且仅当它们的半径相等。265例命题符号化

——自然语言翻译为逻辑式步骤分析出各简单命题，将其符号化；使用合适的联结词，将简单命题逐个联结，组成复合命题的符号化表示。注意事项按逻辑关系翻译，而不能仅凭字面！27五个逻辑运算符强弱顺序运算符结合力的强弱顺序约定为：

¬,∧,∨,→,↔（特别注意先∧后∨）没有括号时按上述先后顺序执行。相同运算符按从左至右顺序执行括号可省去。最外层的括号总可以省去。例如，¬p→¬p∨q∧¬S∨¬q∧R等同于¬p→(¬p∨(q∧¬S)∨(¬q∧R))286例将下列命题符号化。(1)小王是游泳冠军或百米赛跑冠军。(2)小王现在在宿舍或在图书馆。(3)选小王或小李中的一人当班长。(4)如果我上街，我就去书店看看，除非我很累。(5)王一乐是计算机系的学生，他生于1968年或1969年，他是三好学生。296练习将下列命题符号化。(1)除非你努力(p)，否则你将失败(q)。(2)只有睡好觉(p)才能恢复疲劳(q)。(3)我今天进城(q)，除非下雨(p)。(