离散数学命题逻辑.ppt

第一章第一章 命命 题题 逻逻 辑辑 命题与联结词离散数学2 2逻辑逻辑³研究人类思维的科学公元前四世纪亚里斯多德《工具论》奠定了逻辑学的理论基础中国最早的一部逻辑专著－－《墨经》也创造了一个比较完整的逻辑体系形式逻辑形式逻辑形式逻辑形式逻辑辨证逻辑辨证逻辑辨证逻辑辨证逻辑数理逻辑数理逻辑数理逻辑数理逻辑离散数学3 3数理逻辑³数理逻辑是一门用数理逻辑是一门用数学方法数学方法来研究推理规律的来研究推理规律的科学³所谓所谓数学方法数学方法主要是主要是指引进一套符号体系的方指引进一套符号体系的方法法，所以数理逻辑也称做符号逻辑所以数理逻辑也称做符号逻辑创始人：十七世纪，德国数学家莱布尼兹）离散数学4 4形式符号体系形式符号体系³由于自然语言存在模棱两可、含糊的特性，所以有必要引入由于自然语言存在模棱两可、含糊的特性，所以有必要引入形式化语言形式化语言形式化语言形式化语言在数理逻辑中称为在数理逻辑中称为目标语言目标语言 例如：今天晚上八点中央一台播放连续剧例如：今天晚上八点中央一台播放连续剧或或纪录片 我吃苹果我吃苹果或或雪梨³[定义定义]目标语言目标语言：具有单一、明确的含义的语言。

基本元素：具有单一、明确的含义的语言基本元素是命题）是命题）³[定义定义]形式符号体系形式符号体系：由目标语言和一些规定的公式与符号构：由目标语言和一些规定的公式与符号构成的体系成的体系离散数学5 5为何学习数理逻辑为何学习数理逻辑 程序程序 = 算法算法 + 数据结构数据结构 算法算法 = 逻辑逻辑 + 控制控制 离散数学6 6数理逻辑的主要内容数理逻辑的主要内容 ³数理逻辑内容丰富，但其主要包括数理逻辑内容丰富，但其主要包括“两个演算两个演算” 加加“四论四论”，即：，即：²逻辑演算逻辑演算包括命题演算命题演算和和谓词演算谓词演算²证明论证明论主要研究数学理论系统的相容性（即不矛盾、协主要研究数学理论系统的相容性（即不矛盾、协调性）的证明调性）的证明²递归论递归论（能行性理论）自从电子计算机发明后，迫切需（能行性理论）自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数递归论研究能行要在理论上弄清计算机能计算哪些函数递归论研究能行可计算的理论，它为能行可计算的函数找出各种理论上精可计算的理论，它为能行可计算的函数找出各种理论上精确化的严密类比物。

确化的严密类比物²模型论模型论主要是对各种数学理论系统建立模型，并研究各主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系模型之间的关系以及模型与系统之间的关系²公理集合论公理集合论主要研究在消除已知集合论悖论的情况下，主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去用公理方法把有关集合的理论充分发展下去现代数理逻辑离散数学7 7命题逻辑研究的内容命题逻辑研究的内容³命题逻辑也称为命题演算命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系研究以命题为基本单位构成的前提和结论之间的可推导关系. (1) 什么是命题？什么是命题？ (2) 如何表示命题？如何表示命题？ (3) 如何由一些前提推导出一些结论如何由一些前提推导出一些结论?离散数学8 8命题与联结词命题与联结词³命题命题³ 联结词联结词离散数学9 9命题的概念命题的概念³具有判断内容（非真即假）的陈述句称为命题具有判断内容（非真即假）的陈述句称为命题²能够能够确定或分辨确定或分辨其其真假真假的的陈述句陈述句。

³命题有一个值，称为真值，真值只有命题有一个值，称为真值，真值只有“真真”和和“假假”两种，分别用两种，分别用“T”（或（或“1”）和）和“F”（或（或“0”）表示³命题中的判断正确，其真值为真，称为真命题，命题命题中的判断正确，其真值为真，称为真命题，命题中的判断错误，真值为假，称为假命题中的判断错误，真值为假，称为假命题离散数学1010命题示例命题示例1²中华人民共和国的首都是北京中华人民共和国的首都是北京²我们在学习我们在学习《《离散数学离散数学》》的数理逻辑部分的数理逻辑部分²所有素数都是奇数所有素数都是奇数²雪是黑色的雪是黑色的离散数学1111命题示例命题示例2³某些某些感叹句感叹句、、祈使句祈使句、、疑问句疑问句等没有真假之分，所以不是等没有真假之分，所以不是命题命题²明天开会吗？明天开会吗？²多美妙啊！多美妙啊！²请进来²全体立正全体立正离散数学1212判断语句是否为命题要注意的问题：判断语句是否为命题要注意的问题：²目前无法确定真值，但从本质而言，真值存在的语句是命题目前无法确定真值，但从本质而言，真值存在的语句是命题例：例： (1) 别的星球上有生物别的星球上有生物。

(2) 2046年世界杯在中国举行年世界杯在中国举行²真值因时因地而异的判断性陈述句是命题真值因时因地而异的判断性陈述句是命题例：例：(1) 现在是上午现在是上午 (2) 今天下雨今天下雨²含有未确定内容的代词，不能判断真假的语句不是命题含有未确定内容的代词，不能判断真假的语句不是命题例：例： (1) 1+101=110当当1和和101是二进制数，语句为真，为十进制数，语句为假是二进制数，语句为真，为十进制数，语句为假 (2) x+y>10²悖论不是命题悖论不是命题 例：我正在说慌例：我正在说慌离散数学1313 命题的分类命题的分类³根据命题的构成形式，可以将命题分为：根据命题的构成形式，可以将命题分为：³[定义定义]原子命题原子命题：不包含任何联结词的：不包含任何联结词的命题命题³[定义定义]复合命题复合命题：：由由原子命题原子命题和联结词组成的命题和联结词组成的命题连接词一连接词一般译为：般译为：“或者或者”、、“并且并且”、、“不不”、、“如果如果…则则…”、、“仅仅当当”、、“当且仅当当且仅当”等 例如：例如：““明天下雪明天下雪””、、““9是素数是素数””都是都是原子命题原子命题，， ““2不不是素数是素数””是是复合命题复合命题 ““明天下雪明天下雪或或明天下雨明天下雨””是是复合命题复合命题。

““中国获得中国获得2008奥运的主办权奥运的主办权并且并且加入了加入了WTO””是是复合命题复合命题 ““如果如果A和和B是对顶角，是对顶角，则则角角A等于角等于角B””是是复合命题复合命题离散数学1414 命题的表示命题的表示³[定义定义]命题标识符：命题标识符：表示命题的符号，通常是大写英文字母表示命题的符号，通常是大写英文字母³[定义定义]命题符号化：命题符号化：将表示命题的符号放在该命题的前面将表示命题的符号放在该命题的前面 例：例：P P：：北京是中国的首都北京是中国的首都 Q Q：：北京承办北京承办20082008年奥运 离散数学1515命题的表示（续）命题的表示（续） [ [定义定义] ]命题常量：命题常量：表示表示确定命题确定命题的命题标识符的命题标识符 [ [定义定义] ]命题变元：命题变元：可表示任意一个（可表示任意一个（原子或复合原子或复合）命题的）命题的命题命题标识符标识符，就称为，就称为命题变元命题变元当命题变元命题变元表示表示原子命题原子命题时，该时，该变元称为变元称为原子变元。

原子变元 当命题变元当命题变元P P用一个特定命题去取代时，用一个特定命题去取代时， 才能确定才能确定P P的真值，的真值，这时也称对这时也称对P P进行进行指派 例：例： 若若P P是是命题变元，命题变元， P P：：北京是中国的首都北京是中国的首都指派P P为命题北京是中国的首为命题北京是中国的首都）都）离散数学1616命题命题——小结小结³判断一句话是否是命题的步骤：判断一句话是否是命题的步骤： 1 1）看它是否是）看它是否是陈述句陈述句，如果是疑问句、感叹句和祈使句则，如果是疑问句、感叹句和祈使句则不不是是命题命题；； 2 2）看它是否是）看它是否是悖论悖论，悖论不是命题，如，悖论不是命题，如““我正在说谎我正在说谎””；； 3 3）看它真值）看它真值是否是否唯一，如果不唯一，则不是唯一，如果不唯一，则不是命题命题离散数学1717命题与联结词命题与联结词³命题命题³ 联结词联结词离散数学1818命题联结词命题联结词1. 否定：否定： ┐2. 合取：合取： ∧ ∧3. 析取：析取： ∨ ∨4. 排斥析取：排斥析取： ▽▽5. 条件（蕴含）：条件（蕴含）：  6. 双条件：双条件：离散数学1919否定否定³设设P为为命题命题，，P的的否定否定也是一个也是一个命题命题，记作，记作 ┐P²当当P为为T时，时， ┐P为为F²当当P为为F时，时， ┐P为为T³P与与┐P的关系如右表的关系如右表³例：例：设设P：上海是个大城市。

上海是个大城市 则则┐P：上海不是一个大城市上海不是一个大城市 或：上海是个不大的城市或：上海是个不大的城市P┐PFTTF离散数学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: 我们去食堂吃饭我们去食堂吃饭 Q: 教室里有三块黑板教室里有三块黑板 P∧ ∧Q: 我们去食堂吃饭我们去食堂吃饭并且并且教室里有三块黑板教室里有三块黑板³注：注：复合命题复合命题中的中的原子命题原子命题之间无需有一般逻辑意义上的关之间无需有一般逻辑意义上的关联，如联，如(2)离散数学2222 析取析取³设设P、、Q是命题，则是命题，则P和和Q的的析取析取也是个命题，记作也是个命题，记作P∨ ∨Q。

²当且仅当当且仅当P、、Q同时为同时为F时，时，P∨ ∨Q为为F²其他情况下，其他情况下， P∨ ∨Q的真值都是的真值都是T³读作读作“P或或Q” （与自然语言中的（与自然语言中的“或或”不完全相同，是不完全相同，是兼并或）兼并或） PQP∨ ∨QFFFFTTTFTTTT离散数学2323析取例子析取例子³例：例：(1) P：：猴子吃香蕉猴子吃香蕉 Q：：猴子吃橘子猴子吃橘子 猴子猴子吃香蕉吃香蕉或者或者吃橘子吃橘子 ＝？＝？ P∨ ∨Q (2) P：：他明天早上吃蛋糕他明天早上吃蛋糕 Q：：他明天早上喝牛奶他明天早上喝牛奶 P∨ ∨Q＝？＝？ 他明天早上他明天早上吃蛋糕吃蛋糕或者或者喝牛奶喝牛奶 (3) P: 我明天早上我明天早上9点在家看书点在家看书 Q: 我明天早上我明天早上9点出去打球。

点出去打球 我明天早上我明天早上9点在家看书点在家看书或或出去打球出去打球 ＝＝P∨ ∨Q？？ 离散数学2424 排斥析取排斥析取³设设P、、Q是命题，是命题，P和和Q的的排斥析取排斥析取也是个命题，记作也是个命题，记作 P▽▽Q ²当且仅当当且仅当P和和Q的真值不相同时，的真值不相同时， P▽▽Q为为T，，²其他情况下其他情况下,P▽▽Q的真值都是的真值都是F³读作读作“P或或Q” （排斥或）（排斥或）PQP▽▽QFFFFTTTFTTTFPQP∨ ∨QFFFFTTTFTTTT离散数学2525排斥析取示例排斥析取示例³指出下列命题中的指出下列命题中的“或或”是是析取析取还是还是排斥析取排斥析取1.今晚我去看演出或在家里看电视现场转播今晚我去看演出或在家里看电视现场转播2.他是一百米冠军他是一百米冠军或或跳高冠军跳高冠军3.派小王派小王或或小赵出差去上海小赵出差去上海4.派小王派小王或或小赵中的一个出差去上海小赵中的一个出差去上海³2、、3为析取，为析取，1、、 4为排斥析取为排斥析取PQP▽▽QFFFFTTTFTTTFPQP∨ ∨QFFFFTTTFTTTT离散数学2626条件条件/蕴含蕴含³设设P、、Q是命题，是命题，P对于对于Q的条件命题记为的条件命题记为P→Q，或称为，或称为P蕴含蕴含Q 。

²当且仅当当且仅当P的真值为的真值为T，，Q的真值为的真值为F时，时，P→Q的真值为的真值为F，，²其他情况，其他情况， P→Q的真值为的真值为T³读作读作“如果（若）如果（若）P，则，则Q”、、“Q是是P的必要条件的必要条件” 、、“仅当仅当Q为真时，为真时，P为真为真” ³称称P为为前件前件，，Q为为后件后件PQP→QFFTFTTTFFTTT离散数学2727条件示例条件示例³P：天不下雨：天不下雨 Q：我去看电影：我去看电影 如果天不下雨，那么我去看电影：如果天不下雨，那么我去看电影： P→Q ³P：我不到学校去我不到学校去 Q：我生病 P→Q：如果我不到学校去，那么我生病如果我不到学校去，那么我生病³P：我去踢足球我去踢足球 Q：我有时间我有时间 仅当我有时间，我去踢足球仅当我有时间，我去踢足球PQ?FFTFTTTFFTTTP P离散数学2828双条件双条件³P、、Q是命题，是命题，P和和Q的的双条件双条件命题记作：命题记作：P  Q²当当P和和Q的真值相同时，的真值相同时，P  Q的真值为的真值为T，，²否则否则PQ的真值为的真值为F³翻译为：翻译为：“P当且仅当当且仅当Q” 或者或者“若若P则则Q，否则，则，否则，则 Q”PQP  QFFTFTFTFFTTT离散数学2929双条件示例双条件示例³P：整数：整数a能被能被2整除整除 Q：：a是偶数。

是偶数 当且仅当当且仅当整数整数a能被能被2整除，整除，a才是偶数：才是偶数：P  Q ³P：天不下雨：天不下雨 Q：我去看足球：我去看足球 P  Q：如果天不下雨，我就去看足球，否则，我就不去看足球如果天不下雨，我就去看足球，否则，我就不去看足球³P：：2＋＋2＝＝4 Q：雪是白的：雪是白的 2＋＋2＝＝4当且仅当当且仅当雪是白的：雪是白的： P  Q 注注：：复合命题复合命题中的中的原子命题原子命题之间无需有一般逻辑意义上的关联如此例中之间无需有一般逻辑意义上的关联如此例中P和和Q并无因并无因果关系，果关系，P  Q仍是命题，其真值根据联结词定义以及仍是命题，其真值根据联结词定义以及P和和Q的真值来确定的真值来确定离散数学3030综合示例综合示例³设设P表示命题表示命题“天下雪天下雪”³Q表示命题表示命题“我去看电影我去看电影”³R表示命题表示命题“我有时间我有时间”³试以试以符号形式符号形式表示下列命题：表示下列命题：1.┐P2.┐P→Q3.Q →R4.(Q∧ ∧R) → ┐P1.天不下雪天不下雪2.如果天不下雪，那么我去看电如果天不下雪，那么我去看电影。

影3.我去看电影，仅当我有时间我去看电影，仅当我有时间4.如果我去看电影且我有时间，如果我去看电影且我有时间，那么天不下雪那么天不下雪离散数学3131联结词联结词———小结小结³1. 1. 复合命题复合命题的真值只取决于构成它们的的真值只取决于构成它们的原子命题原子命题的真值和命的真值和命题联结符的定义，而与它们的内容、含义无关，与联结词所题联结符的定义，而与它们的内容、含义无关，与联结词所连接的两个连接的两个原子命题原子命题之间是否有关系无关之间是否有关系无关³2. 2.  ，， 和和具有具有可交换性可交换性，而，而 ，，没有离散数学3232联结词联结词———小结小结³1.1.““只要只要( (若、当若、当)A)A成立，则成立，则B B成立成立”” ：：A AB B ³2.2.““仅当仅当A A成立时成立时,B,B成立成立””和和““只有只有A A成立时，成立时，B B成立成立””：： B BA A³3. 3. ““A A成立成立, ,否则否则B B成立成立””：： A AB B³4. 4. 遇到遇到““或或””，就需要考察两件事情可否同时发生，若不能，就需要考察两件事情可否同时发生，若不能同时，则是同时，则是▽▽，否则用，否则用““ ””。

离散数学3333联结词运算顺序联结词运算顺序³优先级从高到底排列：优先级从高到底排列： ┐ ┐、、∧∧/ /∨∨/ /▽▽、、 → →、、  离散数学3434命题（合式）公式命题（合式）公式[定义定义]命题合式公式命题合式公式：： (1) 单个命题变元本身是一个命题合式公式单个命题变元本身是一个命题合式公式 (2) 如果如果A是合式公式，则是合式公式，则┐┐A A是命题合式公式是命题合式公式 (3) 如果如果 A和和B是合式公式，则是合式公式，则A∧B,A∨B∧B,A∨B、、A A▽B▽B、、A→BA→B、、A AB都是命题合式公式都是命题合式公式 (4) 当且仅当能够有限次应用当且仅当能够有限次应用(1)、、(2)、、(3)所得到的包含命题所得到的包含命题变元，联结词和括号的符号串是命题合式公式变元，联结词和括号的符号串是命题合式公式离散数学3535命题（合式）公式举例命题（合式）公式举例设设P、、Q、、R、、S、、T都是命题变元，判断下列字符串哪些是合式都是命题变元，判断下列字符串哪些是合式公式：公式： (1) ┐(P ∧∧Q) (2)((P→Q) ∧∧(Q →R )) (S T) (3) (P→Q) →(∧∧Q) (4) ((P→Q)，， (P ∧∧Q) →Q) (1) (1)和和(2)(2)是命题是命题合式公式合式公式离散数学3636重点掌握重点掌握³命题的定义和判定。

命题的定义和判定³命题常量、命题变元的概念命题常量、命题变元的概念³命题联结词命题联结词³命题（合式）公式的定义命题（合式）公式的定义³符号化复杂命题和用自然语言叙述命题；符号化复杂命题和用自然语言叙述命题；┐、、∧∧、、∨ ∨、、▽▽、、 →、、  的定义的定义 离散数学3737课堂练习课堂练习³以符号形式写出下列命题：以符号形式写出下列命题：(1)上海到北京的上海到北京的14次列车是下午五点半或六点开次列车是下午五点半或六点开2) 他虽聪明但是不用功他虽聪明但是不用功3) 除非你努力，否则你将失败除非你努力，否则你将失败4) 如果你来了，他唱不唱歌将由你是否伴奏决定如果你来了，他唱不唱歌将由你是否伴奏决定。