《离散数学命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学命题逻辑.ppt（37页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 命命 题题 逻逻 辑辑 命题与联结词离散数学2 2逻辑逻辑研究人类思维的科学。公元前四世纪亚里斯多德工具论奠定了逻辑学的理论基础。中国最早的一部逻辑专著墨经也创造了一个比较完整的逻辑体系。形式逻辑形式逻辑形式逻辑形式逻辑辨证逻辑辨证逻辑辨证逻辑辨证逻辑数理逻辑数理逻辑数理逻辑数理逻辑离散数学3 3数理逻辑数理逻辑是一门用数理逻辑是一门用数学方法数学方法来研究推理规律的来研究推理规律的科学。科学。所谓所谓数学方法数学方法主要是主要是指引进一套符号体系的方指引进一套符号体系的方法法，所以数理逻辑也称做符号逻辑。，所以数理逻辑也称做符号逻辑。（创始人：十七世纪，德国数学家莱布尼兹）离散
2、数学4 4形式符号体系形式符号体系由于自然语言存在模棱两可、含糊的特性，所以有必要引入由于自然语言存在模棱两可、含糊的特性，所以有必要引入形式化语言形式化语言。形式化语言形式化语言在数理逻辑中称为在数理逻辑中称为目标语言目标语言。 例如：今天晚上八点中央一台播放连续剧例如：今天晚上八点中央一台播放连续剧或或纪录片。纪录片。 我吃苹果我吃苹果或或雪梨。雪梨。定义定义目标语言目标语言：具有单一、明确的含义的语言。（基本元素：具有单一、明确的含义的语言。（基本元素是命题）是命题）定义定义形式符号体系形式符号体系：由目标语言和一些规定的公式与符号构：由目标语言和一些规定的公式与符号构成的体系成的体系离
3、散数学5 5为何学习数理逻辑为何学习数理逻辑 程序程序 = 算法算法 + 数据结构数据结构 算法算法 = 逻辑逻辑 + 控制控制 离散数学6 6数理逻辑的主要内容数理逻辑的主要内容 数理逻辑内容丰富，但其主要包括数理逻辑内容丰富，但其主要包括“两个演算两个演算” 加加“四论四论”，即：，即：逻辑演算逻辑演算。包括。包括命题演算命题演算和和谓词演算谓词演算证明论证明论。主要研究数学理论系统的相容性（即不矛盾、协。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。调性）的证明。递归论递归论（能行性理论）。自从电子计算机发明后，迫切需（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计
4、算机能计算哪些函数。递归论研究能行要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理论上精可计算的理论，它为能行可计算的函数找出各种理论上精确化的严密类比物。确化的严密类比物。模型论模型论。主要是对各种数学理论系统建立模型，并研究各。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。模型之间的关系以及模型与系统之间的关系。公理集合论公理集合论。主要研究在消除已知集合论悖论的情况下，。主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去。用公理方法把有关集合的理论充分发展下去。现代数理逻辑离散数学
5、7 7命题逻辑研究的内容命题逻辑研究的内容命题逻辑也称为命题演算命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系研究以命题为基本单位构成的前提和结论之间的可推导关系. (1) 什么是命题？什么是命题？ (2) 如何表示命题？如何表示命题？ (3) 如何由一些前提推导出一些结论如何由一些前提推导出一些结论?离散数学8 8命题与联结词命题与联结词命题命题 联结词联结词离散数学9 9命题的概念命题的概念具有判断内容（非真即假）的陈述句称为命题。具有判断内容（非真即假）的陈述句称为命题。能够能够确定或分辨确定或分辨其其真假真假的的陈述句陈述句。命题有一个值，称为真值，真值只
6、有命题有一个值，称为真值，真值只有“真真”和和“假假”两种，分别用两种，分别用“T”（或（或“1”）和）和“F”（或（或“0”）表示。）表示。命题中的判断正确，其真值为真，称为真命题，命题命题中的判断正确，其真值为真，称为真命题，命题中的判断错误，真值为假，称为假命题。中的判断错误，真值为假，称为假命题。离散数学1010命题示例命题示例1中华人民共和国的首都是北京。中华人民共和国的首都是北京。我们在学习我们在学习离散数学离散数学的数理逻辑部分。的数理逻辑部分。所有素数都是奇数。所有素数都是奇数。雪是黑色的。雪是黑色的。离散数学1111命题示例命题示例2某些某些感叹句感叹句、祈使句祈使句、疑问句
7、疑问句等没有真假之分，所以不是等没有真假之分，所以不是命题命题。明天开会吗？明天开会吗？多美妙啊！多美妙啊！请进来。请进来。全体立正。全体立正。离散数学1212判断语句是否为命题要注意的问题：判断语句是否为命题要注意的问题：目前无法确定真值，但从本质而言，真值存在的语句是命题。目前无法确定真值，但从本质而言，真值存在的语句是命题。例：例： (1) 别的星球上有生物。别的星球上有生物。 (2) 2046年世界杯在中国举行。年世界杯在中国举行。真值因时因地而异的判断性陈述句是命题。真值因时因地而异的判断性陈述句是命题。例：例：(1) 现在是上午。现在是上午。 (2) 今天下雨。今天下雨。含有未确定
8、内容的代词，不能判断真假的语句不是命题。含有未确定内容的代词，不能判断真假的语句不是命题。例：例： (1) 1+101=110。当当1和和101是二进制数，语句为真，为十进制数，语句为假。是二进制数，语句为真，为十进制数，语句为假。 (2) x+y10。悖论不是命题。悖论不是命题。 例：我正在说慌。例：我正在说慌。离散数学1313 命题的分类命题的分类根据命题的构成形式，可以将命题分为：根据命题的构成形式，可以将命题分为：定义定义原子命题原子命题：不包含任何联结词的：不包含任何联结词的命题命题。定义定义复合命题复合命题：由由原子命题原子命题和联结词组成的命题和联结词组成的命题。连接词一。连接词
9、一般译为：般译为：“或者或者”、“并且并且”、“不不”、“如果如果则则”、“仅仅当当”、“当且仅当当且仅当”等。等。 例如：例如：“明天下雪明天下雪”、“9是素数是素数”都是都是原子命题原子命题， “2不不是素数是素数”是是复合命题复合命题 “明天下雪明天下雪或或明天下雨明天下雨”是是复合命题复合命题。 “中国获得中国获得2008奥运的主办权奥运的主办权并且并且加入了加入了WTO”是是复合命题复合命题。 “如果如果A和和B是对顶角，是对顶角，则则角角A等于角等于角B”是是复合命题复合命题。离散数学1414 命题的表示命题的表示定义定义命题标识符：命题标识符：表示命题的符号，通常是大写英文字母。
10、表示命题的符号，通常是大写英文字母。定义定义命题符号化：命题符号化：将表示命题的符号放在该命题的前面。将表示命题的符号放在该命题的前面。 例：例：P P：北京是中国的首都北京是中国的首都。 Q Q：北京承办北京承办20082008年奥运。年奥运。 离散数学1515命题的表示（续）命题的表示（续） 定义定义 命题常量：命题常量：表示表示确定命题确定命题的命题标识符。的命题标识符。 定义定义 命题变元：命题变元：可表示任意一个（可表示任意一个（原子或复合原子或复合）命题的）命题的命题命题标识符标识符，就称为，就称为命题变元命题变元。当。当命题变元命题变元表示表示原子命题原子命题时，该时，该变元称为
11、变元称为原子变元。原子变元。 当命题变元当命题变元P P用一个特定命题去取代时，用一个特定命题去取代时， 才能确定才能确定P P的真值，的真值，这时也称对这时也称对P P进行进行指派。指派。 例：例： 若若P P是是命题变元，命题变元， P P：北京是中国的首都北京是中国的首都。（指派。（指派P P为命题北京是中国的首为命题北京是中国的首都）都）离散数学1616命题命题小结小结判断一句话是否是命题的步骤：判断一句话是否是命题的步骤： 1 1）看它是否是）看它是否是陈述句陈述句，如果是疑问句、感叹句和祈使句则，如果是疑问句、感叹句和祈使句则不不是是命题命题； 2 2）看它是否是）看它是否是悖论悖
12、论，悖论不是命题，如，悖论不是命题，如“我正在说谎我正在说谎”； 3 3）看它真值）看它真值是否是否唯一，如果不唯一，则不是唯一，如果不唯一，则不是命题命题。离散数学1717命题与联结词命题与联结词命题命题 联结词联结词离散数学1818命题联结词命题联结词1. 否定：否定： 2. 合取：合取： 3. 析取：析取： 4. 排斥析取：排斥析取： 5. 条件（蕴含）：条件（蕴含）： 6. 双条件：双条件：离散数学1919否定否定设设P为为命题命题，P的的否定否定也是一个也是一个命题命题，记作，记作 P当当P为为T时，时， P为为F当当P为为F时，时， P为为TP与与P的关系如右表的关系如右表例：例：
13、设设P：上海是个大城市。：上海是个大城市。 则则P：上海不是一个大城市。：上海不是一个大城市。 或：上海是个不大的城市。或：上海是个不大的城市。PPFTTF离散数学2020合取合取设设P、Q是命题，是命题，P和和Q的的合取合取也是个命题，记作也是个命题，记作P Q当且仅当当且仅当P、Q同时为同时为T时，时，P Q为为T其他情况下，其他情况下，P Q的真值都是的真值都是F读作读作“P并且（与）并且（与）Q”PQP QFFFFTFTFFTTT离散数学2121合取示例合取示例(1) P: 我富有我富有。 Q: 我快乐我快乐。 P Q：我富有我富有并且并且快乐快乐。(2) P: 我们去食堂吃饭我们去食
14、堂吃饭。 Q: 教室里有三块黑板教室里有三块黑板。 P Q: 我们去食堂吃饭我们去食堂吃饭并且并且教室里有三块黑板教室里有三块黑板。注：注：复合命题复合命题中的中的原子命题原子命题之间无需有一般逻辑意义上的关之间无需有一般逻辑意义上的关联，如联，如(2)。离散数学2222 析取析取设设P、Q是命题，则是命题，则P和和Q的的析取析取也是个命题，记作也是个命题，记作P Q。当且仅当当且仅当P、Q同时为同时为F时，时，P Q为为F其他情况下，其他情况下， P Q的真值都是的真值都是T读作读作“P或或Q” （与自然语言中的（与自然语言中的“或或”不完全相同，是不完全相同，是兼并或）兼并或） PQP Q
15、FFFFTTTFTTTT离散数学2323析取例子析取例子例：例：(1) P：猴子吃香蕉猴子吃香蕉。 Q：猴子吃橘子猴子吃橘子。 猴子猴子吃香蕉吃香蕉或者或者吃橘子吃橘子 ？ P Q (2) P：他明天早上吃蛋糕他明天早上吃蛋糕。 Q：他明天早上喝牛奶他明天早上喝牛奶。 P Q？ 他明天早上他明天早上吃蛋糕吃蛋糕或者或者喝牛奶喝牛奶 。 (3) P: 我明天早上我明天早上9点在家看书。点在家看书。 Q: 我明天早上我明天早上9点出去打球。点出去打球。 我明天早上我明天早上9点在家看书点在家看书或或出去打球出去打球 P Q？ 离散数学2424 排斥析取排斥析取设设P、Q是命题，是命题，P和和Q的的
16、排斥析取排斥析取也是个命题，记作也是个命题，记作 PQ 当且仅当当且仅当P和和Q的真值不相同时，的真值不相同时， PQ为为T，其他情况下其他情况下,PQ的真值都是的真值都是F读作读作“P或或Q” （排斥或）（排斥或）PQPQFFFFTTTFTTTFPQP QFFFFTTTFTTTT离散数学2525排斥析取示例排斥析取示例指出下列命题中的指出下列命题中的“或或”是是析取析取还是还是排斥析取排斥析取1.今晚我去看演出或在家里看电视现场转播。今晚我去看演出或在家里看电视现场转播。2.他是一百米冠军他是一百米冠军或或跳高冠军。跳高冠军。3.派小王派小王或或小赵出差去上海。小赵出差去上海。4.派小王派小
17、王或或小赵中的一个出差去上海。小赵中的一个出差去上海。2、3为析取，为析取，1、 4为排斥析取为排斥析取PQPQFFFFTTTFTTTFPQP QFFFFTTTFTTTT离散数学2626条件条件/蕴含蕴含设设P、Q是命题，是命题，P对于对于Q的条件命题记为的条件命题记为PQ，或称为，或称为P蕴含蕴含Q 。当且仅当当且仅当P的真值为的真值为T，Q的真值为的真值为F时，时，PQ的真值为的真值为F，其他情况，其他情况， PQ的真值为的真值为T。读作读作“如果（若）如果（若）P，则，则Q”、“Q是是P的必要条件的必要条件” 、“仅当仅当Q为真时，为真时，P为真为真” 称称P为为前件前件，Q为为后件后件
18、。PQPQFFTFTTTFFTTT离散数学2727条件示例条件示例P：天不下雨：天不下雨 Q：我去看电影：我去看电影 如果天不下雨，那么我去看电影：如果天不下雨，那么我去看电影： PQ 。P：我不到学校去。：我不到学校去。 Q：我生病。：我生病。 PQ：如果我不到学校去，那么我生病。：如果我不到学校去，那么我生病。P：我去踢足球。：我去踢足球。 Q：我有时间。：我有时间。 仅当我有时间，我去踢足球。仅当我有时间，我去踢足球。PQ?FFTFTTTFFTTTP PQQ离散数学2828双条件双条件P、Q是命题，是命题，P和和Q的的双条件双条件命题记作：命题记作：P Q当当P和和Q的真值相同时，的真值
19、相同时，P Q的真值为的真值为T，否则否则PQ的真值为的真值为F翻译为：翻译为：“P当且仅当当且仅当Q” 或者或者“若若P则则Q，否则，则，否则，则 Q”PQP QFFTFTFTFFTTT离散数学2929双条件示例双条件示例P：整数：整数a能被能被2整除整除 Q：a是偶数。是偶数。 当且仅当当且仅当整数整数a能被能被2整除，整除，a才是偶数：才是偶数：P Q 。P：天不下雨：天不下雨 Q：我去看足球：我去看足球 P Q：如果天不下雨，我就去看足球，否则，我就不去看足球。：如果天不下雨，我就去看足球，否则，我就不去看足球。P：224 Q：雪是白的：雪是白的 224当且仅当当且仅当雪是白的：雪是白
20、的： P Q 注注：复合命题复合命题中的中的原子命题原子命题之间无需有一般逻辑意义上的关联。如此例中之间无需有一般逻辑意义上的关联。如此例中P和和Q并无因并无因果关系，果关系，P Q仍是命题，其真值根据联结词定义以及仍是命题，其真值根据联结词定义以及P和和Q的真值来确定。的真值来确定。离散数学3030综合示例综合示例设设P表示命题表示命题“天下雪天下雪”。Q表示命题表示命题“我去看电影我去看电影”。R表示命题表示命题“我有时间我有时间”。试以试以符号形式符号形式表示下列命题：表示下列命题：1.P2.PQ3.Q R4.(Q R) P1.天不下雪。天不下雪。2.如果天不下雪，那么我去看电如果天不下
21、雪，那么我去看电影。影。3.我去看电影，仅当我有时间。我去看电影，仅当我有时间。4.如果我去看电影且我有时间，如果我去看电影且我有时间，那么天不下雪。那么天不下雪。离散数学3131联结词联结词小结小结1. 1. 复合命题复合命题的真值只取决于构成它们的的真值只取决于构成它们的原子命题原子命题的真值和命的真值和命题联结符的定义，而与它们的内容、含义无关，与联结词所题联结符的定义，而与它们的内容、含义无关，与联结词所连接的两个连接的两个原子命题原子命题之间是否有关系无关。之间是否有关系无关。2. 2. ， 和和具有具有可交换性可交换性，而，而 ，没有。没有。离散数学3232联结词联结词小结小结1.
22、1.“只要只要( (若、当若、当)A)A成立，则成立，则B B成立成立” ：A AB B 2.2.“仅当仅当A A成立时成立时,B,B成立成立”和和“只有只有A A成立时，成立时，B B成立成立”： B BA A3. 3. “A A成立成立, ,否则否则B B成立成立”： A AB B。4. 4. 遇到遇到“或或”，就需要考察两件事情可否同时发生，若不能，就需要考察两件事情可否同时发生，若不能同时，则是同时，则是，否则用，否则用“ ”。离散数学3333联结词运算顺序联结词运算顺序优先级从高到底排列：优先级从高到底排列： 、/ / /、 、 离散数学3434命题（合式）公式命题（合式）公式定义定
23、义命题合式公式命题合式公式： (1) 单个命题变元本身是一个命题合式公式。单个命题变元本身是一个命题合式公式。 (2) 如果如果A是合式公式，则是合式公式，则A A是命题合式公式。是命题合式公式。 (3) 如果如果 A和和B是合式公式，则是合式公式，则AB,ABB,AB、A ABB、ABAB、A AB都是命题合式公式。都是命题合式公式。 (4) 当且仅当能够有限次应用当且仅当能够有限次应用(1)、(2)、(3)所得到的包含命题所得到的包含命题变元，联结词和括号的符号串是命题合式公式。变元，联结词和括号的符号串是命题合式公式。离散数学3535命题（合式）公式举例命题（合式）公式举例设设P、Q、R
24、、S、T都是命题变元，判断下列字符串哪些是合式都是命题变元，判断下列字符串哪些是合式公式：公式： (1) (P Q) (2)(PQ) (Q R ) (S T) (3) (PQ) (Q) (4) (PQ)， (P Q) Q) (1) (1)和和(2)(2)是命题是命题合式公式合式公式离散数学3636重点掌握重点掌握命题的定义和判定。命题的定义和判定。命题常量、命题变元的概念。命题常量、命题变元的概念。命题联结词命题联结词命题（合式）公式的定义命题（合式）公式的定义符号化复杂命题和用自然语言叙述命题；符号化复杂命题和用自然语言叙述命题；、 、 、 的定义的定义 离散数学3737课堂练习课堂练习以符号形式写出下列命题：以符号形式写出下列命题：(1)上海到北京的上海到北京的14次列车是下午五点半或六点开。次列车是下午五点半或六点开。(2) 他虽聪明但是不用功。他虽聪明但是不用功。(3) 除非你努力，否则你将失败。除非你努力，否则你将失败。(4) 如果你来了，他唱不唱歌将由你是否伴奏决定。如果你来了，他唱不唱歌将由你是否伴奏决定。
