第一章命题逻辑1

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