离散数学(01)

1、1 “离散数学离散数学”是一门相对于是一门相对于“连续数学连续数学”而命名的数学分支，也叫而命名的数学分支，也叫“不连续的数不连续的数学学”“”“离散数学离散数学”主要研究一些不连续的数主要研究一些不连续的数学问题。学问题。 概率论与数理统计概率论与数理统计中的随机变量就中的随机变量就有离散型和连续型之区分；有离散型和连续型之区分； 离散数学离散数学是是现代数学现代数学的一个重要分支，上的一个重要分支，上世纪八十年代，计算机科学得到迅猛发展，世纪八十年代，计算机科学得到迅猛发展，2 迫切需要一门适合计算机科学的相关数学课迫切需要一门适合计算机科学的相关数学课程，离散数学由此建立，它是研究离散量

2、的程，离散数学由此建立，它是研究离散量的结构及相互关系的学科。它充分描述了计算结构及相互关系的学科。它充分描述了计算机科学离散性的特点，是计算机科学与技术机科学离散性的特点，是计算机科学与技术的理论基础，所以又称为计算机数学。是计的理论基础，所以又称为计算机数学。是计算机、软件专业本科生必修的专业基础课；算机、软件专业本科生必修的专业基础课；到硕士研究生段还将开设到硕士研究生段还将开设“组合数学组合数学”；到；到博士研究生段还将开设博士研究生段还将开设“计算数学计算数学”；3 “离散数学离散数学”一方面给后继课，如一方面给后继课，如“数据数据结构结构”、“编译系统编译系统”、“操作系统操作系统

3、”、“数据库原理数据库原理”等，提供必要的科学基础；等，提供必要的科学基础；另一方面，通过学习离散数学，培养和提高另一方面，通过学习离散数学，培养和提高了同学们的抽象思维和逻辑推理能力，为大了同学们的抽象思维和逻辑推理能力，为大家今后继续学习和工作打下坚实的数学基础。家今后继续学习和工作打下坚实的数学基础。 我们选用的这本教材是我们选用的这本教材是方世昌方世昌著著离散离散数学数学（第二版），西安电子科技大学（第二版），西安电子科技大学4 出版社出版。是高等学校工科电子类规划教材出版社出版。是高等学校工科电子类规划教材精选系列，本书是一本非常有特点的教材。精选系列，本书是一本非常有特点的教材。初

4、版出版十三年后，经过全国众多学校的应初版出版十三年后，经过全国众多学校的应用，于用，于1996年改进后出第二版；本书力求把年改进后出第二版；本书力求把握与计算机科学密切相关的问题，通过精选握与计算机科学密切相关的问题，通过精选的大量实例深入浅出地介绍了的大量实例深入浅出地介绍了数理逻辑、集数理逻辑、集合论、二元关系、函数、代数系统、格与布合论、二元关系、函数、代数系统、格与布尔代数尔代数* 、图论、图论等（我们省掉其中的等（我们省掉其中的“无限集无限集合合”一章）一章）5 与与计算机科学技术密切相关的课题，既着重于计算机科学技术密切相关的课题，既着重于各部分内容之间的紧密联系，又深入探讨各部各

5、部分内容之间的紧密联系，又深入探讨各部分内容的概念、理论、算法和实际应用。因而分内容的概念、理论、算法和实际应用。因而本书既有深度，又有广度，相信学了本书，即本书既有深度，又有广度，相信学了本书，即能培养思维能力，又能培养理论联系实际的扎能培养思维能力，又能培养理论联系实际的扎实功底实功底 。各章内容大致如下：。各章内容大致如下： 第一章第一章 数理逻辑数理逻辑 将形式逻辑符号化后进行逻辑推理，来将形式逻辑符号化后进行逻辑推理，来6证明命题的真值，对命题公式运算。证明命题的真值，对命题公式运算。 第二章第二章 集合集合 研究集合基本概念、集合之间的运算关研究集合基本概念、集合之间的运算关系以及

6、特殊集合。系以及特殊集合。 第三章第三章 二元关系二元关系 是研究是研究“关系关系”的运算、的运算、 复合、划分，以复合、划分，以及及“关系关系”上的闭包运算等问题。本章内容上的闭包运算等问题。本章内容占全书很大比例。占全书很大比例。7第四章第四章 函数函数 本章内容我们已经是第三次学习，重点放本章内容我们已经是第三次学习，重点放在函数的映射问题上。在函数的映射问题上。第六章第六章 代数代数 是研究是研究“代数系统代数系统”中元素与运算构成群、中元素与运算构成群、半群、环与域的有关问题。完全不同于中学、半群、环与域的有关问题。完全不同于中学、大一学习过的代数问题大一学习过的代数问题8第七章第七

7、章 格与布尔代数格与布尔代数*(在时间充足时学习在时间充足时学习) 是研究是研究“代数系统代数系统”中中“格格”以及以及“特殊特殊格格” 的有关问题。是对的有关问题。是对“代数系统代数系统”的进一的进一步研究。步研究。第八章第八章 图论图论 是研究平面图形中是研究平面图形中“结点结点”与与“连线连线”之之间的关系，路径的优化、网络、匹配等问题，间的关系，路径的优化、网络、匹配等问题，9 离散数学离散数学课每周上课两次，课每周上课两次，4学时，安学时，安排排15周，共周，共60学时。学时。 考核方式：期末笔试占考核方式：期末笔试占70%，平时作业占，平时作业占30%， 每人准备两个作业本（或者用

8、合页纸），写每人准备两个作业本（或者用合页纸），写清班级、学号、姓名。每星期交一次作业，由清班级、学号、姓名。每星期交一次作业，由班长统一收齐交到四楼班长统一收齐交到四楼“专业教研室专业教研室”。交新。交新作业时领回批改过的作业，按学校规定每次作作业时领回批改过的作业，按学校规定每次作业将登记，批改三分之一。业将登记，批改三分之一。10 第一章第一章 数理逻辑数理逻辑1.1 命命 题题 逻辑学分为：逻辑学分为：“形式逻辑形式逻辑”和和“数理逻辑数理逻辑”两个部分，他们的最大区别在于，两个部分，他们的最大区别在于， “形式逻辑形式逻辑”允许有二意性而允许有二意性而“数理逻辑数理逻辑”决不允许。决

9、不允许。“数数理逻辑理逻辑” 就是将就是将 “形式逻辑形式逻辑”数学符号化；数学符号化； 例如：陈述句例如：陈述句“你吃饱了你吃饱了”在在“形式逻辑形式逻辑”中中可以理解为：可以理解为：11（1）你的确是吃的过饱了）你的确是吃的过饱了（2）你这个人的行为很无聊，如同吃饱饭撑的。）你这个人的行为很无聊，如同吃饱饭撑的。 这就是这就是“形式逻辑形式逻辑”的二意性。一个陈述句的二意性。一个陈述句可能有两个意识。可能有两个意识。 命题是逻辑学中的基本单位；陈述语句是逻命题是逻辑学中的基本单位；陈述语句是逻辑学的形式语言，断言是一个陈述语句。辑学的形式语言，断言是一个陈述语句。12 1.1.1 命题命题

10、 在特定的范围、时间、和空间内具有唯在特定的范围、时间、和空间内具有唯一确定的真假性。这样的陈述语句就是一确定的真假性。这样的陈述语句就是命题命题； 一个命题是一个或真或假而不一个命题是一个或真或假而不能两者都是的能两者都是的断言断言。如果命题是真。如果命题是真, 我们说它的我们说它的真值真值为真，为真，如果命题是如果命题是假假, 我们说它的我们说它的真值真值是假。是假。13 例例 1 下述都是命题下述都是命题: (a) 今天下雪今天下雪; (c) 2 是偶数而是偶数而 3 是奇数是奇数; (b) 3+3=6; (d) 陈胜起义那天陈胜起义那天, 杭州下雨杭州下雨;(e) 2008年人类将登上

11、火星。年人类将登上火星。 以上命题以上命题, (a)的真值取决于今天的天气的真值取决于今天的天气, (b)和和(c)是真是真, (d)已无法查明它的真值已无法查明它的真值, 但它但它是或真或假是或真或假, 将它归属于命题。将它归属于命题。 (e)目前尚未目前尚未确定其真假确定其真假, 但它是有真值的但它是有真值的, 应归属于命题。应归属于命题。14例例 2 下述都不是命题下述都不是命题:(a) x+y4。 (c) 真好啊真好啊! (b) x=3。 (d) 你去哪里你去哪里? (a)和和(b)是断言，不是命题是断言，不是命题, 因为它的真值因为它的真值取决于取决于x和和y的值。的值。 (c)和和

12、(d)都不都不是断言是断言, 所所以不是命题。以不是命题。自然语句中有自然语句中有陈述句陈述句、祈使句祈使句、疑问句疑问句、和、和感叹句感叹句等，其中能判断对错的只等，其中能判断对错的只有有陈述句陈述句。15例例 3 一个人说一个人说:“我正在说谎我正在说谎”。 他是在说谎还是在说真话呢他是在说谎还是在说真话呢? 如果他讲真如果他讲真话话, 那么他所说的是真那么他所说的是真, 也就是他在说谎。也就是他在说谎。 我我们得出结论如果他讲真话们得出结论如果他讲真话, 那么他是在说谎。那么他是在说谎。 另一方面另一方面, 如果他是说谎如果他是说谎, 那么他说的是假那么他说的是假; 因为他承认他是说谎因

13、为他承认他是说谎, 所以他实际上是在说真所以他实际上是在说真话话, 我们得出结论如果他是说谎我们得出结论如果他是说谎, 那么他是讲那么他是讲真话。真话。16 从以上分析从以上分析, 我们得出他必须既非说谎也我们得出他必须既非说谎也不是讲真话。这样不是讲真话。这样, 断言断言“我正在说谎我正在说谎”事实事实上不能指定它的上不能指定它的真假真假, 所以不是命题。所以不是命题。 这种这种断言叫断言叫悖论悖论。例：学生甲在教师乙处学习法律，约定一年学例：学生甲在教师乙处学习法律，约定一年学成甲支付学费成甲支付学费2000圆，同时规定在学生甲和圆，同时规定在学生甲和教师乙在同一场官司中，师生分别作为控辩

14、教师乙在同一场官司中，师生分别作为控辩双方，若学生方获胜为学成的标准；双方，若学生方获胜为学成的标准；17 学业结束后学生拒绝支付学费，他认为：学业结束后学生拒绝支付学费，他认为： 教师您可以通过打官司解决，如果教师教师您可以通过打官司解决，如果教师官司打输了，我自然不支付学费，如果教师官司打输了，我自然不支付学费，如果教师官司打嬴了，说明我还没有学成，根据先前官司打嬴了，说明我还没有学成，根据先前的约定，我仍然可以不支付学费。的约定，我仍然可以不支付学费。 这也是个悖论的例子，无论教师乙的怎样这也是个悖论的例子，无论教师乙的怎样努力，在签合同时就被学生甲算计进去了。努力，在签合同时就被学生甲

15、算计进去了。18 若一个命题已不能分解成更简单的命题若一个命题已不能分解成更简单的命题, 则这个命题叫则这个命题叫原子命题原子命题或或本原命题本原命题。 例例 1 中中(a) , (b) , (d) , (e)都是本原命题都是本原命题, 但但(c)不不是是, 因为它可写成因为它可写成“2 是偶数是偶数”和和“3 是奇数是奇数”两个命题。两个命题。 命题和本原命题常用大写字母命题和本原命题常用大写字母P , Q , R :表示。表示。 如用如用P表示表示“4 是质数是质数”, 则记为则记为 ： P: 4 是质数。是质数。 19第一章第一章 数理逻辑数理逻辑 1.2 命题联结词命题联结词 1.1.

16、2 命题联结词命题联结词 命题和原子命题常可通过一些联结词构命题和原子命题常可通过一些联结词构成新命题成新命题, 这种新命题叫这种新命题叫复合命题复合命题。例如。例如 ： P: 明天下雪明天下雪, Q: 明天下雨明天下雨是两个命题是两个命题, 利用联结词利用联结词“不不”, “并且并且”, “或或”等可分别构成新命题等可分别构成新命题:20 “明天不下雪明天不下雪”; “明天下雪并且明天下雨明天下雪并且明天下雨”; “明天下雪或者明天下雨明天下雪或者明天下雨”等。等。 即即 ：“非非P”; ;“P并且并且Q”; “P或或Q”等。等。21 在代数式在代数式x+3 中中, “x “, “3” 叫运

17、算对象叫运算对象,代代数中的运算对象分有数中的运算对象分有“变量变量(x)”和和“常量常量(3)”；命题演算同样对原子命题有命题演算同样对原子命题有“变元变元(P)”和和“常元常元(真、假真、假)”之分；之分； “+”叫运算符叫运算符, x+3 表示运算结果。在命表示运算结果。在命题演算中题演算中, 也用同样术语。联结词就是命题演也用同样术语。联结词就是命题演算中的运算符算中的运算符, 叫叫逻辑运算符逻辑运算符或叫或叫逻辑联结词逻辑联结词。 常用的有以下常用的有以下 5 个。个。22 1.否定词否定词 设设P表示命题表示命题, 那么那么“P不真不真”是另一命题是另一命题, 表示为表示为 P,

18、叫做叫做P的的否定否定, 读做读做“非非P”。 从排从排中律知中律知: 如果如果P是假是假, 则则 P是真是真, 反之亦然。反之亦然。 所以所以否定词否定词 可以如下表所示定义。可以如下表所示定义。归纳为：归纳为：非真非真即假即假，非假即真非假即真。P P假假真真真真假假P P011023 这张表叫这张表叫真值表真值表, 定义运算符的真值表定义运算符的真值表, 指指明如何用运算对象的真值明如何用运算对象的真值, 来决定一个应用运来决定一个应用运算符的命题的真值。算符的命题的真值。 真值表的左边列出运算真值表的左边列出运算对象的真值的所有可能组合对象的真值的所有可能组合, 结果命题的真值结果命题

19、的真值列在最右边的一列。为了便于阅读列在最右边的一列。为了便于阅读, 我们通常我们通常用符号用符号T(true)或或 1 代表代表真真, 符号符号F(false)或或 0 代表代表假假。 一般在一般在公式中采用公式中采用T T和和F F, 在在真值表真值表中采用中采用 1 1 和和 0 0。24 例例 4(a) P: 4 是质数。是质数。P: 4 不是质数。不是质数。 或或 4 是质数是质数, 不是这样。不是这样。 (b) Q: 这些都是男同学。这些都是男同学。 Q: 这些不都是男同学。这些不都是男同学。 (翻译成翻译成“这些都不是男同学这些都不是男同学”是错的。是错的。 ) 原命题为原命题为

20、p，非命题，非命题p 一般的理解为：一般的理解为： 并非并非p；即在命题前加；即在命题前加“并非并非”二二字。字。25例如：例如： p：上海是一个处处都清洁的城市；：上海是一个处处都清洁的城市； p：并非上海是一个处处都清洁的城市；：并非上海是一个处处都清洁的城市；而不能写成：上海是一个处处都不清洁的城市；而不能写成：上海是一个处处都不清洁的城市；2.合取词合取词 如果如果P和和Q是命题是命题, 那么那么“P并且并且Q”也是一也是一命题命题, 记为记为PQ, 称为称为P和和Q的的合取合取, 读做读做“P与与Q”或或“P并且并且Q”。 运算符运算符定义如下表所示定义如下表所示: 从真值表可知从真

21、值表可知PQ是真当且仅当是真当且仅当P和和Q俱真。俱真。26归纳为：归纳为： p，q同真时同真时pq为真，其余为假为真，其余为假。 类似集合运算中的：类似集合运算中的： “交交 ，”P QP Q0 00 11 01 10001例例5 P: 王华的成绩王华的成绩很好很好, Q: 王华的品德王华的品德很好。很好。 PQ: 王华的成绩王华的成绩很好并且品德很好。很好并且品德很好。27 3. 析取词析取词 如果如果P和和Q是命题是命题, 则则“P或或Q”也是一命题也是一命题, 记记作作PQ, 称为称为P和和Q的的析取析取, 读做读做“P或或Q”。运。运算符算符定义如右表所示。从真值表可知定义如右表所示

22、。从真值表可知PQ为真为真, 当且仅当当且仅当P或或Q至少有一为真。至少有一为真。归纳为：归纳为： p，q同假时同假时 p q 为假，其余为真为假，其余为真。 看的出：合取与析取有对偶的关系。看的出：合取与析取有对偶的关系。28析取类似集合运算中的：析取类似集合运算中的： “并并 ，”P QP Q0 00 11 01 10111例例 6 (a) P: 今晚今晚我写字我写字, Q: 今晚今晚我看书。我看书。 PQ: 今晚今晚我写字或看书我写字或看书 29 (b) P: 今年是闰年今年是闰年; Q: 今年她生孩子。今年她生孩子。 PQ: 今年是闰年或者今年她生孩子。今年是闰年或者今年她生孩子。 逻

23、辑运算符可以将两个无关的命题连接成逻辑运算符可以将两个无关的命题连接成一新命题。一新命题。 “或或”字常见的含义有两种字常见的含义有两种: 一种是一种是“可兼或可兼或”, 如上例中的或如上例中的或, 它不排除今晚既它不排除今晚既看书又写字这种情况。看书又写字这种情况。 30 一种是一种是“排斥或排斥或”, 例如例如“人固有一死人固有一死, 或或重于泰山重于泰山, 或轻于鸿毛或轻于鸿毛”中的中的“或或”, 它表示非它表示非此即彼此即彼, 不可兼得。不可兼得。 运算符运算符表示可兼或表示可兼或, 排斥排斥或以后用另一符号表达。或以后用另一符号表达。 联结词联结词是自然语言中的是自然语言中的“或或”

24、、“或者或者”的逻辑抽象，而在自然语言中，的逻辑抽象，而在自然语言中，“或或”是多义是多义的，可列表如下：的，可列表如下：31“可兼或可兼或”与与“排斥或排斥或” 的联系与区别的联系与区别 或的或的 含义含义 例如例如 说明说明联联结结词词可可兼兼或或可可兼兼容容今天晚会上我或者唱歌或者今天晚会上我或者唱歌或者跳舞，也可以边唱边跳。跳舞，也可以边唱边跳。二者至少有一个发二者至少有一个发生，不排斥二者都生，不排斥二者都发生的情况发生的情况排排斥斥或或 不不可可兼兼容容他下午他下午2：00上街或在教室上街或在教室听课。听课。非此即彼，不可兼非此即彼，不可兼的的 非联非联 结词结词去主楼需要去主楼需

25、要6分钟或分钟或8分钟分钟近似数近似数“6至至8分分钟钟”32 4. 蕴涵词蕴涵词(涵常简写作含涵常简写作含) 如果如果P和和Q是命题是命题, 那么那么“P蕴含蕴含Q”也是命题也是命题, 记为记为PQ, 称为称为蕴含式蕴含式, 读做读做“P蕴含蕴含Q”或或“如如果果P, 那么那么Q”，是典型的，是典型的“因果关系因果关系”。 运算对象运算对象P叫做叫做前提前提 , 假设假设或或前件前件, 而而Q叫做叫做结论结论或或后件后件。逻辑推理经常用到这种。逻辑推理经常用到这种“因果关因果关系系”；运算符定义如下表所示。命题；运算符定义如下表所示。命题PQ是假是假, 当且仅当当且仅当P是真而是真而Q是假。

26、是假。33 归纳为：归纳为：条件为真，结论为假时条件为真，结论为假时pq pq 为假，其余为真为假，其余为真。 我们经常把我们经常把“”（条件命题）简称为：（条件命题）简称为： 单条件命题单条件命题。以区别后面的双条件命题。以区别后面的双条件命题。P QP Q0 00 11 01 1110134例例 7 (a) P: 天不下雨天不下雨, Q: 草木枯黄。草木枯黄。 PQ: 如果天不下雨如果天不下雨, 那么草木枯黄。那么草木枯黄。 (b) R: G是正方形是正方形, S: G的四边相等。的四边相等。 RS: 如果如果G是正方形是正方形, 那么那么G的四边相等。的四边相等。 (c) W: 桔子是紫

27、色的桔子是紫色的, V: 大地是不平的大地是不平的WV: 如果桔子是紫色的如果桔子是紫色的, 那么大地是不那么大地是不平的。平的。35 在日常生活中用蕴含式来断言前提和结论在日常生活中用蕴含式来断言前提和结论之间的因果或实质关系之间的因果或实质关系, 如上例如上例(a)和和(b), 这样的这样的蕴含式叫蕴含式叫形式蕴含形式蕴含, 然而然而, 在命题演算中在命题演算中, 一个蕴一个蕴含式的前提和结论并不需要有因果和实质联系含式的前提和结论并不需要有因果和实质联系, 这样的蕴含式叫这样的蕴含式叫实质蕴含实质蕴含, 如上例如上例(c)中中, 桔子的桔子的颜色和大地的外形之间没有因果和实质关系存颜色和

28、大地的外形之间没有因果和实质关系存在在, 但蕴含式但蕴含式WV是真是真, 36 因为前提是假而结论是真因为前提是假而结论是真,这就是我们这就是我们常说的常说的”善意推断善意推断”。即：条件为假时，即：条件为假时，条件命题永真。条件命题永真。例如：如果太阳从西边出来，那么每个星期例如：如果太阳从西边出来，那么每个星期我们就休息我们就休息5天。天。 这个命题的条件是假的，无论后面的结这个命题的条件是假的，无论后面的结论是什么，整个条件命题是真的。论是什么，整个条件命题是真的。37 蕴含式蕴含式PQ可以用多种方式陈述可以用多种方式陈述:“若若P, 则则Q” “P是是Q的充分条件的充分条件” “Q是是

29、P的必要条件的必要条件” “Q每当每当P” ; “P仅当仅当Q”等。等。如上例如上例(b)中的中的RS可陈述为可陈述为“G是正方形的是正方形的必要条件是它必要条件是它的四边相等的四边相等”。38 给定原命题给定原命题PQ, 我们把：我们把： QP, 叫做命题叫做命题PQ的的逆命题逆命题 P Q, 叫做命题叫做命题PQ的的否命题否命题 Q P ， 叫做命题叫做命题PQ的的逆否命题逆否命题. 其中其中原命题原命题与与逆否命题逆否命题，逆命题逆命题与与否命题否命题是同是同真值的。真值的。39 例如：例如：P:如果天下雨，如果天下雨，Q:那么地上湿。那么地上湿。 P Q （真）（真）逆命题：如果地上湿

30、，那么天下雨。逆命题：如果地上湿，那么天下雨。否命题：如果天不下雨，那么地上不湿。否命题：如果天不下雨，那么地上不湿。 这样就不一定为真，也可能是洒水车刚这样就不一定为真，也可能是洒水车刚刚过去洒过水了。但逆否命题：刚过去洒过水了。但逆否命题： 如果地上不湿，那么天没下雨。是真的；如果地上不湿，那么天没下雨。是真的；40 5. 等值词等值词 如果如果P和和Q是命题是命题, 那么那么“P等值于等值于Q”也也是命题是命题, 记为记为P Q, 称为称为等值式等值式, 读做读做“P等值于等值于Q”。 运算符运算符 定义如下表所示。定义如下表所示。归纳为：归纳为： p、q同真、假时同真、假时 p q 为

31、真，其余为真，其余为假。为假。P QP Q0 00 11 01 1100141 把蕴含式和等值式的真值表加以比较把蕴含式和等值式的真值表加以比较, 易知如果易知如果P Q是真是真, 那么那么PQ和和QP俱真俱真; 反之如果反之如果PQ和和QP俱真俱真, 那么那么P Q是真。是真。由于这些理由由于这些理由, P Q也读做也读做“P是是Q的充要的充要条件条件”或或“P当且仅当当且仅当Q”。 如如p和和q是命题，复合命题是命题，复合命题p当且仅当当且仅当q有有时简称为时简称为双条件命题双条件命题，且表为，且表为p q。42 从以上从以上 5 个定义可看出个定义可看出, 联结词之意义由联结词之意义由其

32、真值表唯一确定其真值表唯一确定, 而不由命题的含义确定。而不由命题的含义确定。 使用以上使用以上 5 个联结词个联结词, 可将一些语句翻译成可将一些语句翻译成逻辑式。逻辑式。 翻译时为了减少圆括号翻译时为了减少圆括号(一般不用其一般不用其它括号它括号)的使用的使用, 我们作以下约定，运算符结合我们作以下约定，运算符结合力的强弱顺序为力的强弱顺序为 ; ， , , , （ 同于四则运算中的同于四则运算中的次序）次序） 43 凡符合此顺序的凡符合此顺序的, 括号均可省去。相同的括号均可省去。相同的运算符运算符, 按从左至右次序计算时按从左至右次序计算时, 括号可省去括号可省去最外层的圆括号可以省去

33、。最外层的圆括号可以省去。例如例如: ( (P Q)R)(RP)Q)可写成可写成 ： (P QR)RPQ 但有时为了看起来清楚醒目但有时为了看起来清楚醒目, 也可以保留也可以保留某些原可省去的括号。某些原可省去的括号。44 例例 8 (a) 设设P表示表示“他有理论知识他有理论知识”, Q表表示示“他有实践经验他有实践经验” 则则“他既有理论知识他既有理论知识又有实践经验又有实践经验”可译为可译为: PQ。(b) 设设P: 明天下雨明天下雨, Q: 明天下雪明天下雪, R: 我去学校。我去学校。 则：则： (i) “如果明天不是雨夹雪则我去学校如果明天不是雨夹雪则我去学校”可写可写成成 ; (

34、PQ)R ;45(ii) “如果明天不下雨并且不下雪则我去学校如果明天不下雨并且不下雪则我去学校”可写成可写成 ; P QR ; (iii) “如果明天下雨或下雪则我不去学校如果明天下雨或下雪则我不去学校”可写可写成成 ; PQ R ;iv) “明天明天, 我将雨雪无阻一定去学校我将雨雪无阻一定去学校”可写成可写成 ; (PQR)(PQR)(PQR) (PQR)46 (v) “当且仅当明天不下雪并且不下雨时我当且仅当明天不下雪并且不下雨时我才去学校才去学校”可写成可写成 ; P Q R ; (c) 用逻辑符表达用逻辑符表达“说小学生编不了程序说小学生编不了程序, 或说小学生用不了个人计算机或说

35、小学生用不了个人计算机, 那是不对的那是不对的”。 设设P: 小学生会编程序小学生会编程序, Q: 小学生会用个人小学生会用个人计算机。计算机。 则上句可译为：则上句可译为： (P Q) 47 (d) 用逻辑符表达用逻辑符表达“若不是他生病或出差若不是他生病或出差了了, 我是不会同意我是不会同意 他不参加学习他不参加学习”。 设设P: 他生病了他生病了, Q: 他出差了他出差了, R: 我同意我同意他不参加学习他不参加学习, 则上句可译为则上句可译为 (PQ) R 或或 PQ R即：我同意他不参加学习的充要条件的他生即：我同意他不参加学习的充要条件的他生病了或者出差了病了或者出差了48 翻译时

36、要按逻辑关系翻译翻译时要按逻辑关系翻译, 而不能凭字而不能凭字面翻。面翻。 例如例如, 设设P: 林芬做作业林芬做作业, Q: 林芳做林芳做作业作业, 则则“林芬和林芳同在做作业林芬和林芳同在做作业”可译为可译为PQ, 但但“林芬和林芳是姐妹林芬和林芳是姐妹”就不能翻就不能翻释成两个命题的合取释成两个命题的合取, 它是一个原子命题。它是一个原子命题。 1.1.3 命题变元和命题公式命题变元和命题公式 通常通常, 如果如果P代表真值未指定的任意命题代表真值未指定的任意命题, 49 我们就称我们就称P为为命题变元命题变元; 如果如果P代表一个真代表一个真 值已指定的命题值已指定的命题, 我们就称我

37、们就称P为为命题常元命题常元。 但由于在命题演算中并不关心具体命题但由于在命题演算中并不关心具体命题的涵义的涵义, 只关心其真假值。只关心其真假值。 因此因此, 我们可以我们可以形式地定义它们。形式地定义它们。 以以“真真” , “假假”为其变域的变元为其变域的变元, 称为称为命命题变元题变元; T(1)和和F(0)称为称为命题常元命题常元。原子公式原子公式50单个原子公式是命题公式。单个原子公式是命题公式。 这种定义叫这种定义叫, 也叫也叫。由。由这种定义产生的公式也叫这种定义产生的公式也叫51 一个命题公式（合式公式一个命题公式（合式公式 ）如同一个函）如同一个函数表达式，由命题变元和命题常元取代函数数表达式，由命题变元和命题常元取代函数式中的变量和常量，由五个命题联结词取代式中的变量和常量，由五个命题联结词取代函数式中的各种运算。函数式中的各种运算。 命题公式的真假值一般不能确定。当命命题公式的真假值一般不能确定。当命题公式中所有命题变元代以真值时，命题公题公式中所有命题变元代以真值时，命题公式就确定了