《《命题逻辑》课件.ppt》由会员分享，可在线阅读，更多相关《《命题逻辑》课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、离散数学,周勇,（小）,要求,基本要求 考核,考勤：按大学生手册执行（缺席三次取消考试资格，迟到10分钟不能进入教室）作业独立完成期中考试（？）考教分离周三交作业（按自然班，班长负责），下一个周三返还,平时成绩30%：作业+考勤期末成绩70%,离散数学是数学的几个分支的总称，研究基于离散空间而不是连续的数学结构。与微积分和分析等连续数学相对的。数理逻辑，集合论，代数系统，图论信息论，理论计算机科学，运筹学，概率论，博弈论,4/34,什么是数理逻辑？,数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指:用一套数学的符号系统来描述和处理思维的形式与规律。因此，数理逻辑又称为符号逻辑。,数
2、理逻辑的创始人-莱布尼茨(Leibniz,Gottfried Wilhelm)1646.7.1-1716.11.14,5/34,德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、神学等诸多方面.出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅6岁时便去世了，给他留下了丰富的藏书。,15岁时，进了莱比锡大学学习法律，一进校便跟上了大学二年级标准的人文学科的课程，还广泛阅读了培根、开普勒、伽利略等人的著作，并对他们的著述进行深入的思考和评价。在听了
3、教授讲授欧几里德的几何原本的课程后，莱布尼兹对数学产生了浓厚的兴趣。17岁时他在耶拿大学学习了短时期的数学，并获得了哲学硕士学位。19岁设计出世界第一台乘法器，被认为是现代机器数学的先驱者。Leibniz(16461716年)之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。1693年，发现了机械能的能量守恒定律。与牛顿并称为微积分的创立者。系统阐述了二进制记数法，并把它和中国的八卦联系起来。,6/34,几何系统（公理）,7/34,1.过相异两点，能作且只能作一直线（直线公理）。2.线段(有限直线)可以任意地延长。3.以任一点为圆心、任意长为半径，可作
4、一圆(圆公理)。4.凡是直角都相等(角公理)。5.两直线被第三条直线所截，如果同侧两内角和小于两个直角，则两直线作延长时在此侧会相交。,1.跟同一个量相等的两个量相等；即若 a=c 且 b=c，则 a=b（等量代换公理）。2.等量加等量，其和相等；即若 a=b 且 c=d，则 a+c=b+d（等量加法公理）。3.等量减等量，其差相等；即若 a=b 且 c=d，则 a-c=b-d（等量减法公理）。4.完全叠合的两个图形是全等的（移形叠合公理）。5.全量大於分量，即 a+ba（全量大於分量公理）。,公设：,公理：,几何系统（定理证明）,8/34,命题：在已知有限直线上可作一个等边三角形。,A,B,
5、C,设AB为已知线段，证明可在其上作一个等边三角形,证明：,以A为圆心，AB长为半径作圆A（公设3）,以B为圆心，AB长为半径作圆B（公设3）,由两圆交点C作直线AC和BC（公设1）,由圆定义可知AC=AB，BC=AB，则AC=BC=AB（公理1）,所以，ABC为所求等边三角形,主要内容,9/34,命题、命题逻辑联结词命题变元、合式公式重言式、永真蕴含、恒等式带入规则、替换规则对偶原理范式及其判定问题命题演算的推理,概述,10/34,应用：计算机电路设计 计算机程序构造 程序正确性证明,1.1 命题与命题逻辑联结词,一、命题 所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不
6、能判断其真假，故都不是命题。定义：或者为真，或者为假而不是两者同时成立的陈述句被称为一个命题。或真或假，不能既真又假。例1:判断下面语句是否是命题华盛顿是美国的首都。多伦多是加拿大的首都。1+101=110 几点了？x+1=3真热呀！坑爹神马都是浮云,11/34,或真或假，不能既真又假,1.1 命题与命题逻辑联结词,12/34,理发师问题：理发师只给所有不给自己理发的人理发分析：（1）理发师给自己理发（2）理发师不给自己理发,悖论,1.1 命题与命题逻辑联结词,2.命题的真值及表示命题用大写的英文字母，如，表示。P：今天是星期一。命题仅有两种可能的真值真和假，且二者只能居其一。如果一个命题的真
7、值是真，则用1或True(T)来表示；如果一个命题的真值是假，则用0或False(F)来表示。,13/34,定义：一个命题不能再分解为更简单的命题，这个命题称为原子命题。,如果下周日下雪，那么我就去滑雪。如果下周日不下雨并且没有考试，那么我去海边玩。这次演讲比赛，我们班将由赵明或者张强参加。,14/34,命题,原子命题,？,分子命题（复合命题）,六种逻辑联结词,（1）联结词“非”，记为“”，表示“否定”的意思。（2）联结词“合取”，记为“”，表示“且”的意思。（3）联结词“析取”，记为“”，表示“或”的意思。（4）联结词“蕴涵”，记为“”，表示“如果，则”的意思。（5）联结词“等价”，记为“”
8、，表示“当且仅当”的意思。（6）联结词“异或”，记为“”，表示“要么，要么”的意思。,15/34,定义 设P是一个命题，则P的否定是一个新的命题，记作“”，读作“非P”。自然语言中的“非”、“不”和“没有”等否定词“”的意义如下表：,否定,或,真值表：利用运算对象真值的所有可能组合判断命题的真假。,16/34,例：找出命题“熊孩子都是坑爹的”的否定。“并非所有的熊孩子都是坑爹的。”“所有的熊孩子都不是坑爹的。”,否定,对整体否定，不是对局部的否定,17/34,合取,定义：表征意义两命题合取的真值表,18/34,或,合取,19/34,析取,定义：表征意义两命题析取的真值表,20/34,或,析取,
9、21/34,可兼或,不可兼或,异或,定义：表征意义双条件 的真值表,22/34,或,蕴涵,定义：表征意义蕴含 的真值表,23/34,或,蕴涵,政治家竞选时许诺“如果我当选了，那么我将会打击腐败”。如果今天是星期五，那么2+2=4.与程序设计中if p then S语句的区别。,24/34,现实世界中无意义的语言也可以翻译,蕴涵,在日常生活中，用条件式表示前提和结论之间的因果或实质关系，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为实质条件命题。,25/34,等价,定义：表征意义等价 的真值表,26/34,或,！注意：由逻辑联结词联结的命题
10、之间不需要任何关系。优先次序：,1.1 命题与命题逻辑联结词,27/34,（）,句子到逻辑表达式的翻译,步骤：确定给定的句子是否为命题；找出各原子命题并确定句子中的连词为对应的联结词；用正确的语法把原命题表示成由原子命题、联结词和圆括号组成的公式。,28/34,句子到逻辑表达式的翻译,翻译下列命题：(1)他既聪明又用功。(2)他虽聪明但不用功。解：原子命题 P：他聪明。Q：他用功。则有：(1)翻译成：P Q(2)翻译成：P Q,29/34,句子到逻辑表达式的翻译,除非有时间，我才去看电影A：我有时间。B：我去看电影。翻译为：B A我不承认你是对的，除非太阳从西边出来A：我不承认你是对的。B：太
11、阳从西边出来。翻译为：B A,30/34,句子到逻辑表达式的翻译,如果你和他都不固执己见的话，那么不愉快的事情就不会发生了。P：你固执己见。Q：他固执己见。R：不愉快的事情不会发生。翻译为：(PQ)R如果你和他不都是固执己见的话，那么不愉快的事情就不会发生了。(PQ)R,31/34,句子到逻辑表达式的翻译,P：这个材料很有趣。Q：这个习题很难。R：这门课程使人喜欢。1、这个材料很有趣，而且这些习题很难。2、这个材料无趣，习题也不难，那么，这门课程就不会使人喜欢。3、这个材料无趣，习题也不难，而且这门课程也不使人喜欢。4、这个材料很有趣意味着这些习题很难，反之亦然。5、或者这个材料很有趣，或者这
12、些习题很难，而且两者恰具其一。,32/34,句子到逻辑表达式的翻译,除非你已满16周岁，否则只要你的身高不足4英尺就不能乘公园滑行铁道游乐车。P：你能乘坐公园滑行铁道游乐车。Q：你身高不足4英尺。R：你已满16周岁。翻译成：(R Q)P,33/34,逻辑难题,一个岛上居住着两类人骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人A和B，如果A说“B是骑士”，B说“我们两个不是一类人”，请判断A、B到底是流氓还是骑士。解：首先假设P:A是骑士；Q:B是骑士如果A是骑士如果A是流氓,34/34,作业,P21：1,2，3，4（1）、（3）P22:6（2）（4），9,35/34,http:/s/1mgpdFug,
