离散数学命题逻辑1ppt课件

1、 命题与结合词离散数学逻辑逻辑 研讨人类思想的科学。公元前四世纪亚里斯多德奠定了逻辑学的实际根底。中国最早的一部逻辑专著也发明了一个比较完好的逻辑体系。离散数学数理逻辑数理逻辑是一门用数学方法来研讨推理规律的科数理逻辑是一门用数学方法来研讨推理规律的科学。学。所谓数学方法主要是指引进一套符号体系的方法，所谓数学方法主要是指引进一套符号体系的方法，所以数理逻辑也称做符号逻辑。所以数理逻辑也称做符号逻辑。开创人：十七世纪，德国数学家莱布尼兹离散数学方式符号体系方式符号体系 由于自然言语存在模棱两可、模糊的特性，所以有必要引入由于自然言语存在模棱两可、模糊的特性，所以有必要引入方式化言语。方式化言语

2、在数理逻辑中称为目的言语。方式化言语。方式化言语在数理逻辑中称为目的言语。 例如：今天晚上八点中央一台播放延续剧或纪录片。例如：今天晚上八点中央一台播放延续剧或纪录片。 我吃苹果或雪梨。我吃苹果或雪梨。 定义定义目的言语：具有单一、明确的含义的言语。根本元素目的言语：具有单一、明确的含义的言语。根本元素是命题是命题 定义定义方式符号体系：由目的言语和一些规定的公式与符号构方式符号体系：由目的言语和一些规定的公式与符号构成的体系成的体系离散数学为何学习数理逻辑为何学习数理逻辑 程序程序 = 算法算法 + 数据构造数据构造 算法算法 = 逻辑逻辑 + 控制控制 离散数学数理逻辑的主要内容数理逻辑的

3、主要内容 数理逻辑内容丰富，但其主要包括数理逻辑内容丰富，但其主要包括“两个演算两个演算 加加“四论，即：四论，即： 逻辑演算。包括命题演算和谓词演算逻辑演算。包括命题演算和谓词演算 证明论。主要研讨数学实际系统的相容性即不矛盾、协调性的证明。证明论。主要研讨数学实际系统的相容性即不矛盾、协调性的证明。 递归论能行性实际。自从电子计算机发明后，迫切需求在实际上弄递归论能行性实际。自从电子计算机发明后，迫切需求在实际上弄清计算机能计算哪些函数。递归论研讨能行可计算的实际，它为能行可清计算机能计算哪些函数。递归论研讨能行可计算的实际，它为能行可计算的函数找出各种实际上准确化的严密类比物。计算的函数

4、找出各种实际上准确化的严密类比物。 模型论。主要是对各种数学实际系统建立模型，并研讨各模型之间的关模型论。主要是对各种数学实际系统建立模型，并研讨各模型之间的关系以及模型与系统之间的关系。系以及模型与系统之间的关系。 公理集合论。主要研讨在消除知集合论悖论的情况下，用公理方法把有公理集合论。主要研讨在消除知集合论悖论的情况下，用公理方法把有关集合的实际充分开展下去。关集合的实际充分开展下去。现代数理逻辑离散数学命题逻辑研讨的内容命题逻辑研讨的内容 命题逻辑也称为命题演算命题逻辑也称为命题演算 研讨以命题为根本单位构成的前提和结论之间的可推导关研讨以命题为根本单位构成的前提和结论之间的可推导关系

5、系. (1) 什么是命题？什么是命题？ (2) 如何表示命题？如何表示命题？ (3) 如何由一些前提推导出一些结论如何由一些前提推导出一些结论?离散数学命题与结合词命题与结合词命题命题 结合词结合词离散数学命题的概念命题的概念具有判别内容非真即假的陈说句称为命题。具有判别内容非真即假的陈说句称为命题。可以确定或分辨其真假的陈说句。可以确定或分辨其真假的陈说句。命题有一个值，称为真值，真值只需命题有一个值，称为真值，真值只需“真和真和“假两假两种，分别用种，分别用“T或或“1和和“F或或“0表示。表示。命题中的判别正确，其真值为真，称为真命题，命题命题中的判别正确，其真值为真，称为真命题，命题中

6、的判别错误，真值为假，称为假命题。中的判别错误，真值为假，称为假命题。离散数学命题例如命题例如1 中华人民共和国的首都是北京。中华人民共和国的首都是北京。 我们在学习我们在学习的数理逻辑部分。的数理逻辑部分。 一切素数都是奇数。一切素数都是奇数。 雪是黑色的。雪是黑色的。离散数学命题例如命题例如2 某些感慨句、祈使句、疑问句等没有真假之分，所以不是某些感慨句、祈使句、疑问句等没有真假之分，所以不是命题。命题。 明天开会吗？明天开会吗？ 多愉快啊！多愉快啊！ 请进来。请进来。 全体立正。全体立正。离散数学判别语句能否为命题要留意的问题：判别语句能否为命题要留意的问题：目前无法确定真值，但从本质而

7、言，真值存在的语句是命题。目前无法确定真值，但从本质而言，真值存在的语句是命题。例：例： (1) (1) 别的星球上有生物。别的星球上有生物。 (2) 2046 (2) 2046年世界杯在中国举行。年世界杯在中国举行。真值因时因地而异的判别性陈说句是命题。真值因时因地而异的判别性陈说句是命题。例：例：(1) (1) 如今是上午。如今是上午。 (2) (2) 今天下雨。今天下雨。含有未确定内容的代词，不能判别真假的语句不是命题。含有未确定内容的代词，不能判别真假的语句不是命题。例：例： (1) 1+101=110 (1) 1+101=110。当当1 1和和101101是二进制数，语句为真，为十进

8、制数，语句为假。是二进制数，语句为真，为十进制数，语句为假。 (2) x+y10 (2) x+y10。悖论不是命题。悖论不是命题。 例：我正在说慌。例：我正在说慌。离散数学 命题的分类命题的分类根据命题的构成方式，可以将命题分为：根据命题的构成方式，可以将命题分为： 定义定义 原子命题：不包含任何结合词的命题。原子命题：不包含任何结合词的命题。 定义定义 复合命题：由原子命题和结合词组成的命题。衔接词普复合命题：由原子命题和结合词组成的命题。衔接词普通译为：通译为：“或者、或者、“并且、并且、“不、不、“假设假设那么那么、“仅当仅当、“当且仅当等。当且仅当等。 例如：例如：“明天下雪、明天下雪

9、、“9 9是素数都是原子命题，是素数都是原子命题， “2 2不是素数是复合命题不是素数是复合命题 “明天下雪或明天下雨是复合命题。明天下雪或明天下雨是复合命题。 “中国获得中国获得20192019奥运的主办权并且参与了奥运的主办权并且参与了WTOWTO是复合命题。是复合命题。 “假设假设A A和和B B是对顶角，那么角是对顶角，那么角A A等于角等于角B B是是复合命题。复合命题。离散数学 命题的表示命题的表示 定义定义 命题标识符：表示命题的符号，通常是大写英文字母。命题标识符：表示命题的符号，通常是大写英文字母。 定义定义 命题符号化：将表示命题的符号放在该命题的前面。命题符号化：将表示命

10、题的符号放在该命题的前面。 例：例：P P：北京是中国的首都。：北京是中国的首都。 Q Q：北京承办：北京承办20192019年奥运。年奥运。 离散数学命题的表示续命题的表示续 定义定义 命题常量：表示确定命题的命题标识符。命题常量：表示确定命题的命题标识符。 定义定义 命题变元：可表示恣意一个原子或复合命题的命命题变元：可表示恣意一个原子或复合命题的命题标识符，就称为命题变元。当命题变元表示原子命题时，题标识符，就称为命题变元。当命题变元表示原子命题时，该变元称为原子变元。该变元称为原子变元。 当命题变元当命题变元P P用一个特定命题去取代时，用一个特定命题去取代时， 才干确定才干确定P P

11、的真值，的真值，这时也称对这时也称对P P进展指派。进展指派。 例：例： 假设假设P P是命题变元，是命题变元， P P：北京是中国的首都。指派：北京是中国的首都。指派P P为命题北京是中国的为命题北京是中国的首都首都离散数学命题命题小结小结 判别一句话能否是命题的步骤：判别一句话能否是命题的步骤： 1 1看它能否是陈说句，假设是疑问句、感慨句和祈使句那看它能否是陈说句，假设是疑问句、感慨句和祈使句那么不是命题；么不是命题； 2 2看它能否是悖论，悖论不是命题，如看它能否是悖论，悖论不是命题，如“我正在说谎；我正在说谎； 3 3看它真值能否独一，假设不独一，那么不是命题。看它真值能否独一，假设

12、不独一，那么不是命题。离散数学命题与结合词命题与结合词命题命题 结合词结合词离散数学命题结合词命题结合词1. 否认：否认： 2. 合取：合取： 3. 析取：析取： 4. 排斥析取：排斥析取： 5. 条件蕴含：条件蕴含： 6. 双条件：双条件：离散数学否认否认 设设P为命题，为命题，P的否认也是一个命题，记作的否认也是一个命题，记作 P 当当P为为T时，时， P为为F 当当P为为F时，时， P为为T P与与P的关系如右表的关系如右表 例：设例：设P：上海是个大城市。：上海是个大城市。 那么那么P：上海不是一个大城市。：上海不是一个大城市。 或：上海是个不大的城市。或：上海是个不大的城市。PPFT

13、TF离散数学合取合取 设设P、Q是命题，是命题，P和和Q的合取也是个命题，记作的合取也是个命题，记作PQ 当且仅当当且仅当P、Q同时为同时为T时，时，PQ为为T 其他情况下，其他情况下，PQ的真值都是的真值都是F 读作读作“P并且与并且与QPQPQFFFFTFTFFTTT离散数学合取例如合取例如(1) P: 我富有。我富有。 Q: 我高兴。我高兴。 PQ：我富有并且高兴。：我富有并且高兴。(2) P: 我们去食堂吃饭。我们去食堂吃饭。 Q: 教室里有三块黑板。教室里有三块黑板。 PQ: 我们去食堂吃饭并且教室里有三块黑板。我们去食堂吃饭并且教室里有三块黑板。注：复合命题中的原子命题之间无需有普

14、通逻辑意义上的关联，注：复合命题中的原子命题之间无需有普通逻辑意义上的关联，如如(2)。离散数学 析取析取 设设P、Q是命题，那么是命题，那么P和和Q的析取也是个命题，记作的析取也是个命题，记作PQ。 当且仅当当且仅当P、Q同时为同时为F时，时，PQ为为F 其他情况下，其他情况下， PQ的真值都是的真值都是T 读作读作“P或或Q 与自然言语中的与自然言语中的“或不完全一样，是或不完全一样，是兼并或兼并或 PQPQFFFFTTTFTTTT离散数学析取例子析取例子例：例：(1) P：猴子吃香蕉。：猴子吃香蕉。 Q：猴子吃橘子。：猴子吃橘子。 猴子吃香蕉或者吃橘子猴子吃香蕉或者吃橘子 ？ PQ (2

15、) P：他明天早上吃蛋糕。：他明天早上吃蛋糕。 Q：他明天早上喝牛奶。：他明天早上喝牛奶。 PQ？ 他明天早上吃蛋糕或者喝牛奶他明天早上吃蛋糕或者喝牛奶 。 (3) P: 我明天早上我明天早上9点在家看书。点在家看书。 Q: 我明天早上我明天早上9点出去打球。点出去打球。 我明天早上我明天早上9点在家看书或出去打球点在家看书或出去打球 PQ？ 离散数学 排斥析取排斥析取 设设P、Q是命题，是命题，P和和Q的排斥析取也是个命题，记作的排斥析取也是个命题，记作 PQ 当且仅当当且仅当P和和Q的真值不一样时，的真值不一样时， PQ为为T， 其他情况下其他情况下,PQ的真值都是的真值都是F 读作读作“

16、P或或Q 排斥或排斥或PQPQFFFFTTTFTTTFPQPQFFFFTTTFTTTT离散数学排斥析取例如排斥析取例如 指出以下命题中的指出以下命题中的“或是析取还是排斥析取或是析取还是排斥析取 今晚我去看上演或在家里看电视现场转播。今晚我去看上演或在家里看电视现场转播。 他是一百米冠军或跳高冠军。他是一百米冠军或跳高冠军。 派小王或小赵出差去上海。派小王或小赵出差去上海。 派小王或小赵中的一个出差去上海。派小王或小赵中的一个出差去上海。 2、3为析取，为析取，1、 4为排斥析取为排斥析取PQPQFFFFTTTFTTTFPQPQFFFFTTTFTTTT离散数学条件条件/蕴含蕴含 设设P、Q是命

17、题，是命题，P对于对于Q的条件命题记为的条件命题记为PQ，或称为，或称为P蕴含蕴含Q 。 当且仅当当且仅当P的真值为的真值为T，Q的真值为的真值为F时，时，PQ的真值为的真值为F， 其他情况，其他情况， PQ的真值为的真值为T。 读作读作“假设假设假设假设P，那么，那么Q、“Q是是P的必要条件的必要条件 、“仅当仅当Q为真时，为真时，P为真为真 称称P为前件，为前件，Q为后件。为后件。PQPQFFTFTTTFFTTT离散数学条件例如条件例如 P：天不下雨：天不下雨 Q：我去看电影：我去看电影 假设天不下雨，那么我去看电影：假设天不下雨，那么我去看电影： PQ 。 P：我不到学校去。：我不到学校

18、去。 Q：我生病。：我生病。 PQ：假设我不到学校去，那么我生病。：假设我不到学校去，那么我生病。 P：我去踢足球。：我去踢足球。 Q：我有时间。：我有时间。 仅当我有时间，我去踢足球。仅当我有时间，我去踢足球。PQ?FFTFTTTFFTTT离散数学双条件双条件 P、Q是命题，是命题，P和和Q的双条件命题记作：的双条件命题记作：P Q 当当P和和Q的真值一样时，的真值一样时，P Q的真值为的真值为T， 否那么否那么PQ的真值为的真值为F 翻译为：翻译为：“P当且仅当当且仅当Q 或者或者“假设假设P那么那么Q，否那么，那么，否那么，那么 QPQP QFFTFTFTFFTTT离散数学双条件例如双条

19、件例如 P：整数：整数a能被能被2整除整除 Q：a是偶数。是偶数。 当且仅当整数当且仅当整数a能被能被2整除，整除，a才是偶数：才是偶数：P Q 。 P：天不下雨：天不下雨 Q：我去看足球：我去看足球 P Q：假设天不下雨，我就去看足球，否那么，我就不去看足球。：假设天不下雨，我就去看足球，否那么，我就不去看足球。 P：224 Q：雪是白的：雪是白的 224当且仅当雪是白的：当且仅当雪是白的： P Q 注：复合命题中的原子命题之间无需有普通逻辑意义上的关联。如此例中注：复合命题中的原子命题之间无需有普通逻辑意义上的关联。如此例中P和和Q并并无因果关系，无因果关系，P Q仍是命题，其真值根据结合

20、词定义以及仍是命题，其真值根据结合词定义以及P和和Q的真值来确定。的真值来确定。离散数学综合例如综合例如设设P表示命题表示命题“天下雪。天下雪。Q表示命题表示命题“我去看电影。我去看电影。R表示命题表示命题“我有时间。我有时间。试以符号方式表示以下命题：试以符号方式表示以下命题：PPQQ R(QR) P天不下雪。天不下雪。假设天不下雪，那么我去看电假设天不下雪，那么我去看电影。影。我去看电影，仅当我有时间。我去看电影，仅当我有时间。假设我去看电影且我有时间，假设我去看电影且我有时间，那么天不下雪。那么天不下雪。离散数学结合词结合词小结小结 1. 1. 复合命题的真值只取决于构成它们的原子命题的

21、真值和命复合命题的真值只取决于构成它们的原子命题的真值和命题结合符的定义，而与它们的内容、含义无关，与结合词所题结合符的定义，而与它们的内容、含义无关，与结合词所衔接的两个原子命题之间能否有关系无关。衔接的两个原子命题之间能否有关系无关。 2. 2. ，和和具有可交换性，而具有可交换性，而 ， 没有。没有。离散数学结合词结合词小结小结1.1.“只需只需( (假设、当假设、当)A)A成立，那么成立，那么B B成立成立 ：A A B B 2.2.“仅当仅当A A成立时成立时,B,B成立和成立和“只需只需A A成立时，成立时，B B成立：成立： B B A A3. 3. “A A成立成立, ,否那么否那么B B成立：成立： A A B B。4. 4. 遇到遇到“或，就需求调查两件事情可否同时发生，假设不能或，就需求调查两件事情可否同时发生，假设不能同时，那么是，否那么用同时，那么是，否那么用“。离散数学结合词运算顺序结合词运算顺序 优先级从高究竟陈列：优先级从高究竟陈列： 、/、 、 离散数学命题合式公式命题合式公式定