命题符号化及联结词.ppt

离散数学,离散数学是研究世界事物间的离散结构和相互关系的学科. 离散数学是现代数学的一个分支，在数学、计算学科、电 子信息学科中的作用与地位日渐突显.,第一篇： 数理逻辑 第二篇： 集合论 第三篇： 代数系统 第四篇： 图论,学习目的,初步掌握现代数学的观点和方法； 初步掌握处理离散结构的方法，提高计算机系统 设计和程序设计的逻辑数字的能力； 初步掌握计算机在进行数的处理时的方法和计算； 培养学习抽象思维和缜密思考的能力；,了解离散数学在计算机网络，通信，工程，技术等各门学科乃至社会科学的重要作用与意义，以适应学习数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊断、机器定理证明等其他专业课程的各种需要 和将来从事软、硬件开发和应用研究打下坚实的基础。,学习参考书,离散数学及其应用（第5 版）,K.H.Rosen， 机械工业出版社，2003年 离散数学题解，屈婉玲、耿素云、张立昂 编， 清华大学出版社，1999年 离散数学结构(第五版),罗平译, 高等教育出版社,2005年,第一篇： 数理逻辑,逻辑规则给出数学语句的准确含义，这些规则用来区分有效和无效的数学论证。逻辑不仅是所有数学推理的基础，而且对计算机的电路设计、系统规范说明、人工智能、计算机程序设计、程序设计语言以及计算机科学的其他领域都有实际的应用。,逻辑难题,有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，今加派两名战士负责解答你所提的任何问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问：逻辑学家手指一门问身旁一名战士说：这扇门是死亡门，他（指另一名战士）将回答是，对吗？”当被问战士回答完对或否后，逻辑学家开门从容离去。,解 当被问战士回答“对”，则逻辑学家开启所指的门从容离去。当被问战士回答“否”，则逻辑学家开启另一门从容离去。,分析：如果被问者是诚实战士，他回答“对” 。则另一 名战士是说谎战士，他回答“是”，那么，这扇门不是死亡门。 如果被问者是诚实战士，他回答“否”。则另一名是说谎战士，他回答“不是”，那么，这扇门是死亡门。 如果被问者是说谎战士可以类似分析，,被问战士是诚实人。 被问战士的回答是“是”。 另一战士的回答是“是”。 这扇门是死亡门,数理逻辑：用数学的方法来研究推理的形式结 构和推理规律的数学学科,数理逻辑与数学的其他分支、计算机科学、人工智能、语言学等学科密切相关，并且具有广泛的应用前景。,数理逻辑分五部分：逻辑演算、证明论、公理集合论、递归论和模型论。,第一章 命题逻辑,一、命题与真值 二、联结词 三、小结 思考题,第一节 命题符号化及联结词,一、命题与真值,命题：称能判断真假，但不会既能真又能假的 陈述句为命题。,命题的真值：,命题的判断结果称为命题的真值， 真值只取两个值：真和假.,称真值为真的命题为真命题，真值为假的命题为假命题.,说明：,命题是陈述句，命题所表达的判断 只有两个结果 .,其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因此均不是命题。,例如：判断下列句子是否为命题。,1）你是谁？ 2）请注意听讲！ 3）新加坡真美丽啊！ 4）海洋的面积比陆地大。 5） 3+210 6) x+y2 7) 明天是晴天。 9）银河系中除地球外还有有人生存的星球。,判断标准：,1.陈述句； 2.判断结果唯一。非真即假。 （并不意味着现在就能确定其真假） 3.不包括悖论。,2.罗素悖论,1理发师的头发由谁来理？,在一个小镇上，仅有一名理发师，且镇里的所有人都需要理发，理发师公开宣布：他给而且只给小镇上所有自己不给自己理发的人理发。好事者问：理发师先生，你自己的头发由谁来理？,原子命题：,称由简单陈述句构成的命题为简单命题或原子命题，,命题变项：真值可以变化的简单陈述句。如例6。,注：1.命题变项不是命题。 2.当用命题常项带入命题变项时，命题变项变 为命题。真值确定。,复合命题：称由简单命题用联结词联结而成的命题 构成复合命题的命题称为复合命题的支命题。,联结词：使得复合后的命题的真值可以完全由各个支命题所决定的联结词称为逻辑联结词或命题联结词。常用的联结词（逻辑联结词）及它们所联结的复合命题有以下5种：,例如：数理逻辑不是枯燥无味的。,说明：1、 p是一元联结词 所谓一元联结词就是联结一个命题的联结词。,注：相容或与排斥或的区分： 析取联结词指相容或（两个命题可同时为真） 排斥或：两个命题不可能同时为真，当且仅当一个为真，一个为假时，为真。,例如：1）李明是三好学生或是优秀团员。 2）李明在宿舍或在图书馆。 3）选小王或小李中的一人当班长。 4）我昨晚做了六或八道数学题。,相容或与不能同时为真的排斥或均可符号化为pVq。,例如（1）今天下雨或刮风。 （2）今天第一节课是语文课或数学课。 （3）他现在在301室或302室。,pq的逻辑关系为q是p的必要条件或p是q的充分条件。,例：p: 明天天气好。 q: 妈妈带孩子去动物园玩。,注： 1.一般因为p，所以q；只要p就q；p仅当q；只 有q才p；除非q才p；除非q,否则非p等都可符号化为pq。 2.前件与后件无因果关系。 3.前件为假，真值永远为真。 前件为假时，pq必为真； 后件为真时，pq必为真。,例：将下列命题符号化 1) 如果1+23,则太阳从东边升起。 2) 如果1+23,则太阳从东边升起。 3) 如果1+23,则太阳从西边升起。 4) 如果1+23,则太阳从西边升起。,说明:在数理逻辑中，即使p、q没有内在联系， 但仍有意义.,例1.6 1）集合A中没有元素当且仅当集合A是空集。 2）当王刚心情愉快时，他唱歌；反之，当 他唱歌时，一定心情愉快。 3）三角形三边相等的充要条件是三个角相等。 4) 2+2=5的充要条件是太阳从西边升起。,说明：1.“p等价于q”相当于“ p当且仅当q”， “p是q的充要条件”。 2.在数理逻辑中，即使p、q没有内在联系， p与q的等价式 仍有意义。,说明：1）基本的复合命题：由联结词集中的一 个联