数理逻辑与集合论：1 命题逻辑的基本概念

1、 引言n 现代科学技术的各个领域，都提出了大量离散结构的科学问题。例如：n计算机科学计算机科学n程序设计程序设计n计算机网络计算机网络n信息论与编码信息论与编码n通信理论通信理论n现代密码学现代密码学n数字信号处理数字信号处理n形式语言形式语言 等等 它们都与离散数学密切相关。引言n离散数学n是是现代数学现代数学的一个重要分支，是计算机科学中基的一个重要分支，是计算机科学中基础理论的础理论的核心课程核心课程。n主要目标主要目标 研究研究离散量离散量的结构和相互之间关系。的结构和相互之间关系。n研究对象研究对象 一般是一般是有限个有限个或或可数个可数个元素。元素。n研究内容研究内容n数理逻辑数理

2、逻辑n集合论集合论n代数学代数学n组合数学组合数学n图论图论n计算理论计算理论n复杂网络复杂网络n网格及网络计算等网格及网络计算等数理逻辑与集合论的主要内容第一部分第一部分 数理逻辑数理逻辑第第1章章 命题逻辑的基本概念命题逻辑的基本概念第第2章章 命题逻辑的等值和推理演算命题逻辑的等值和推理演算第第4章章 谓词逻辑的基本概念谓词逻辑的基本概念第第5章章 谓词逻辑的等值和推理演算谓词逻辑的等值和推理演算第二部分第二部分 集合论集合论第第 9 章章 集合集合第第10章章 关系关系第第11章章 函数函数第第12章章 实数集合与集合的基数实数集合与集合的基数本课程的要求n授课总学时n32学时：授课周

3、数为学时：授课周数为16周，每周周，每周2学时；学时；n作业第第3 3、6 6、8 8、1010、1212、1414、1616周周交作业，只有当交作业，只有当作业收齐交到讲台上后才开始上课作业收齐交到讲台上后才开始上课；n成绩评定n 平平 时时 成成 绩：绩：20%n期末考成绩：期末考成绩：80%第一部分 数理逻辑n 先看著名物理学家爱因斯坦出的一道题先看著名物理学家爱因斯坦出的一道题: n一个商人想招聘一位聪明的助手，有两人前来应聘，一个商人想招聘一位聪明的助手，有两人前来应聘，商人为了试试谁更聪明，就把两人带进一间漆黑的屋商人为了试试谁更聪明，就把两人带进一间漆黑的屋子里，子里，n他打开灯

4、后说他打开灯后说：“桌子上有五顶帽子，桌子上有五顶帽子，两顶红色两顶红色，三三顶黑色顶黑色，现在把灯关掉，并把帽子的位置弄乱，然后，现在把灯关掉，并把帽子的位置弄乱，然后我们每人摸一顶帽子戴在自己头上，我再藏起余下的我们每人摸一顶帽子戴在自己头上，我再藏起余下的两顶帽子，开灯后，你们要尽快说出自己头上戴的帽两顶帽子，开灯后，你们要尽快说出自己头上戴的帽子的颜色。子的颜色。”n当开灯后，那两个应试者看到商人头上戴的是一顶当开灯后，那两个应试者看到商人头上戴的是一顶红红帽子帽子，其中一个人便喊道：，其中一个人便喊道：“我戴的是我戴的是黑帽子黑帽子。”n 请问这个人说得对吗？他是怎么推导出来的呢？请

5、问这个人说得对吗？他是怎么推导出来的呢？ 第一部分 数理逻辑n 这需要经历如下过程：这需要经历如下过程：n 什么是前提？有哪些前提？什么是前提？有哪些前提？n 结论是什么？结论是什么？n 根据什么进行推理？根据什么进行推理？n 怎么进行推理？怎么进行推理？ n 数理逻辑将回答这些问题，它包括数理逻辑将回答这些问题，它包括n 命题逻辑命题逻辑n 一阶逻辑一阶逻辑n 数理逻辑（符号逻辑）数理逻辑（符号逻辑）n 是用数学方法来研究是用数学方法来研究推理推理的的形式结构形式结构和和推理规律推理规律的数学学科的数学学科n 它除了研究数学基础课题个，还扩展到了现代科学技术中，如它除了研究数学基础课题个，还

6、扩展到了现代科学技术中，如n 程序语言、自动机理论、逻辑网络、机器翻译与机器证明等程序语言、自动机理论、逻辑网络、机器翻译与机器证明等吴文俊(1919-)数学机械化n 1976年，吴文俊教授在中国古代数学的启发下，创建了数学机械化方法n 从从几何公理体系几何公理体系出发，引进坐标，将任意几何问题出发，引进坐标，将任意几何问题代数化代数化，将证，将证明题的明题的假设假设与与结论结论分别表示成分别表示成多元多项式方程多元多项式方程，在计算机上编程，在计算机上编程运算，以判断定理是否成立。运算，以判断定理是否成立。n 至至2008年，运用吴文俊教授的方法，已证明出年，运用吴文俊教授的方法，已证明出6

7、00多条定理，许多条定理，许多定理的证明不超过几秒钟。甚至有一些定理证明相当繁杂，即多定理的证明不超过几秒钟。甚至有一些定理证明相当繁杂，即便交给杰出的数学家来证也是相当困难的。便交给杰出的数学家来证也是相当困难的。n “数学机械化数学机械化” 是是近代数学史上的第一个中国原创的领域近代数学史上的第一个中国原创的领域，被国，被国际上称为际上称为“”。n 它它终于实现了千百年来终于实现了千百年来几何定理几何定理机械化证明的梦想。机械化证明的梦想。n 它它给给2000多年的公理化演绎体系带来了强烈冲击。多年的公理化演绎体系带来了强烈冲击。n 2000年年吴文俊吴文俊院士获院士获首届首届国家最高科技

8、奖国家最高科技奖。第1章 命题逻辑的基本概念 1.1 命题命题1.2 命题联结词及真值表命题联结词及真值表1.3 合式公式合式公式1.4 重言式重言式1.5 命题形式化命题形式化1.1 命题n 命题的概念 n引例就是要对引例就是要对“我戴的是黑帽子我戴的是黑帽子”，进行判断。，进行判断。这样的这样的陈述句陈述句称为命题。称为命题。n命题 可判断真假的陈述句。可判断真假的陈述句。n如：如：2是素数。是素数。 雪是黑色的。雪是黑色的。n命题的真值 判断的结果判断的结果n真值的取值 真（真（1或或T）与假（）与假（0或或F）n真命题真命题: 真值为真的命题（判断正确）真值为真的命题（判断正确）n假命

9、题假命题: 真值为假的命题（判断错误）真值为假的命题（判断错误）n任何命题的真值都是任何命题的真值都是唯一唯一的。的。命题n 注意: n感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题n如：如：你跑得真快！你跑得真快！ 全体起立。全体起立。 又上课了吗？又上课了吗？n陈述句中的陈述句中的判断结果不惟一确定判断结果不惟一确定以及以及( (疑似疑似) )悖论悖论也不也不是命题是命题n如：如：x + 5 3 我是说谎者。我是说谎者。 利用正三角形导出利用正三角形导出“2=12=1”的的“证明证明”n 判断给定句子是否为命题的步骤n首先判定它是否为陈述句，首先判定它是否为陈述句，n其次

10、判断它是否有唯一的真值其次判断它是否有唯一的真值。 除地球外的星球有生物。除地球外的星球有生物。 太阳明天会出来。太阳明天会出来。命题变项 n约定：用大写英文字母（如：约定：用大写英文字母（如：P, Q, R, ）来形式）来形式化命题，如化命题，如n用用P表示表示“ 2是素数是素数”。n用用Q表示表示“2 + 5 = 7”。n当当P表示任一命题时，表示任一命题时，P称为称为命题变项（变元）命题变项（变元）n命题与命题变项的区别命题与命题变项的区别n命题命题指具体确定真值的陈述句指具体确定真值的陈述句相当于常量相当于常量n如：如：“ 2是素数是素数”。n命题变项命题变项的真值不确定，它不是命题，

11、当它用确定命题的真值不确定，它不是命题，当它用确定命题取代后，它才能确定真值。取代后，它才能确定真值。命题的分类 n简单命题(原子命题)n不能分解为更简单的句子的陈述句。不能分解为更简单的句子的陈述句。n如如 “2 2是素数是素数”n复合命题复合命题n由几个简单命题与由几个简单命题与联结词联结词按一定规则复合而成按一定规则复合而成的命题的命题 。n如：如： 3不不是偶数。是偶数。 2是素数是素数和和偶数偶数。1.2 命题联结词及真值表1. 否定词n 定义定义: 设设 P 是一个命题是一个命题, 构造一个新命题是原命构造一个新命题是原命题的否定题的否定, 称该命题是命题称该命题是命题 P 的的取

12、否命题取否命题, 表示表示成成“ P ”.n规定规定: :n P 为真当且仅当为真当且仅当P为假为假例如例如: P : 今天下雨今天下雨. P : 今天今天不不下雨下雨.自然语言中用到的联结词自然语言中用到的联结词: 非非 , 不不 , 并非并非 P PF T T F 真值表真值表公式在所有赋值下的取值公式在所有赋值下的取值情况列成的表情况列成的表 联结词2. 合取词 n 定义定义: 设命题设命题 P 和和 Q 是两个命题是两个命题,构造一个新命题构造一个新命题“ P 与与 Q ”,称作命题称作命题 P 和和 Q 的合取的合取,表示成表示成“P Q ”. n 规定规定n当且仅当当且仅当 P 和

13、和 Q 都为真时都为真时, P Q 为真为真.n 自然语言中用到的联结词自然语言中用到的联结词:n“和和”，“与与” , “, “并且并且”n“既既.又又.” .” “不仅不仅.而且而且.” n“虽然虽然.但是但是. P Q P Q F FF TT FT T FFFT 例: 将下列命题符号化 P:李平聪明. Q:李平用功.(1) 李平既聪明又用功. (2) 李平虽然聪明但不用功.(3) 李平不但聪明而且用功.(4) 李平不是不聪明而是不用功.P QP QP Q ( P) Q例例: P:今天下雨今天下雨. Q: 3+3=6今天下雨与今天下雨与3+3=6. 可表示为可表示为:P Q “ ” 可以连

14、接两个完全没有联系的命题可以连接两个完全没有联系的命题. .联结词3. 析取词n 定义定义:设命题设命题 P 和和 Q 是两个命题是两个命题, 构造一个新命题构造一个新命题“ P 或或Q ”, 称作命题称作命题 P 和和 Q 的析取的析取, 表示成表示成“P Q”. n 规定规定nPQ为假当且仅当为假当且仅当 P 与与 Q 同时为假同时为假. n当且仅当当且仅当 P 和和 Q 中至少一个为真时中至少一个为真时, P Q 为真为真. P Q PQ F FF TT FT TFTTT联结词n 例如：n P: 灯泡有故障灯泡有故障. Q: 开关有故障开关有故障.n灯泡有故障或开关有故障灯泡有故障或开关

15、有故障. (可能同时发生可能同时发生)n应表示为应表示为 P Qn 注意注意: 析取词析取词表示的是表示的是“可兼或可兼或”.n 例如例如:n P: 小李正在家里看书小李正在家里看书. Q: 小李正在剧场看戏小李正在剧场看戏.n 小李正在家里看书或正在剧场看戏小李正在家里看书或正在剧场看戏. （不可能同时发生）（不可能同时发生）n 表示为：表示为： (P Q) ( P Q) =P Q P Q P Q F FF TT F T TFTT F P Q PQ F FF TT FT TFTTT4. 蕴涵词n 定义定义: 设设 P,Q为二命题，复合命题为二命题，复合命题 “如果如果P,则则Q” 称作称作P

16、与与Q的的蕴涵式蕴涵式，记作，记作 P Q，并称，并称nP是蕴涵式的是蕴涵式的前件前件，nQ为蕴涵式的为蕴涵式的后件后件， n称作称作蕴涵联结词蕴涵联结词，n P是是Q的的充分条件充分条件，Q是是P 的的必要条件必要条件。n 常见错误常见错误n不分不分充分与必要条件充分与必要条件n混淆混淆充分与必要条件充分与必要条件联结词n“如果如果 P，则，则 Q ” 的不同表述法很多的不同表述法很多n 若若 P，就就 Qn 只要只要 P，就就 Qn P 仅当仅当 Qn 只有只有 Q 才才 Pn 除非除非 Q, 才才 P n 除非除非 Q, 否则非否则非 P联结词 PQ P是是Q 的的充分条件充分条件 P是

17、是Q 的的必要条件必要条件。（1）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才骑自行车上班。设：设：P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。(1) 等价为：除非我骑自行车上班，否则天下雨除非我骑自行车上班，否则天下雨。 P Q（2）等价为：除非不下雨，我才骑自行车上班除非不下雨，我才骑自行车上班。 Q P 注意：注意：P Q 中的中的 P 和和 Q 不一定有内在联系不一定有内在联系。 例: 将下列命题符号化 联结词n 规定规定nPQ为为假假当且仅当当且仅当P为真为真Q为假为假. n当当 P 为假时，为假时，PQ 为真为真n 说明说明n如：如：P:“天气好天气好” Q

18、:“我去接你我去接你”n则则P Q ：“若天气好，则我去接你若天气好，则我去接你”n当天气好时，当天气好时，n我去接了你，此时，我去接了你，此时， P Q 真真n我没去接你，此时，我没去接你，此时， P Q 假假n 当天气不好时，当天气不好时，n我无论去或不去接你均未食言，此时认定我无论去或不去接你均未食言，此时认定P Q 为真为真是适当的是适当的 P Q P Q F FF TT FT TTTFT PQ= P Q联结词5. 双条件词n 定义：定义：设设P，Q为二命题，为二命题， “P当且仅当当且仅当Q”称作称作 P 与与 Q 的的等价式等价式，记作，记作PQ，n 规定规定nPQ 为为真真当且仅

19、当当且仅当 P 与与 Q 真值相同真值相同.n 说明说明:n PQ 的逻辑关系的逻辑关系: P 与与 Q 互为充分必要条件互为充分必要条件 P Q P Q F FF TT FT TTFFT P Q=(PQ) (Q P)联结词举例 P：两个三角形是全等的。 Q：两个三角形的三条对应边相等。则等价命题：则等价命题： P Q：两个三角形全等，当且仅当它们的三条对应边两个三角形全等，当且仅当它们的三条对应边分别相等。分别相等。下列复合命题的真值为(1) 2 + 2 4 当且仅当当且仅当 3 + 3 6.(2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数.(3) 2 + 2 4 当且仅当当且仅当

20、 太阳从东方升起太阳从东方升起.110 联结词的优先顺序为：联结词的优先顺序为： , , , , 1.3 合式公式n 合式公式n它由它由命题命题、命题变项命题变项按照一定的逻辑顺序用按照一定的逻辑顺序用命题联结命题联结词词连接起来构成连接起来构成n 合式公式（公式）的递归定义：(1)简单命题是合式公式简单命题是合式公式(2)若若A是合式公式，则是合式公式，则 ( A)也是合式公式也是合式公式(3)若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)也是合式公式也是合式公式(4)当且仅当经过当且仅当经过有限次有限次地使用地使用(1)(3)所组成的符号串才所组成

21、的符号串才是合式公式是合式公式n 说明:n (P Q), P(Q R), (P Q ) R 是合式公式是合式公式nPQR, P Q ，( P R ) ( P) 不是合式公式不是合式公式n 例如：合式公式 A=（P Q） Rn若若 P: “2是素数是素数”， Q: “3是奇数是奇数”， R :“4能被能被2整除整除”n则则A为为真命题。真命题。n若若 P: “2是素数是素数”， Q: “3是奇数是奇数”， R :“3能被能被2整除整除”n则则A为假命题。为假命题。合式公式的真值n 一个含有命题变项的合式公式的真值是不确定的.n 只有对合式公式的每个只有对合式公式的每个命题变项命题变项用指定的用指定的命题命题代替后，代替后，合式公式才成为合式公式才成为命题命题，其值才唯一确定。，其值才唯一确定。公式的赋值 n 定义定义 n给公式给公式A中的命题变项中的命题变项 P1, P2, , Pn指定一组真值称指定一组真值称为对为对A的一个的一个赋值赋值或或解释解释n成真赋值成真赋值: 使公式为真的赋值使公式为真的赋值n成假赋值成假赋值: 使公式为假的赋值使公式为假的赋值n 说明：说明：n A中仅出现中仅出现 P1, P2, , Pn，给，给A赋值赋值 1 2 n是指是指 P1= 1, P2= 2, , Pn= n ， i