01 命题逻辑基本概念.ppt

第一部分数理逻辑,应用数理逻辑，可以把人类的推理过程分解成一些非常简单原始的、非常和机械的动作，使得用机器代替人类进行推理成为可能提供程序员设计算法时的思维方法指导,第一部分数理逻辑,使用电子计算机前，必须先进行程序设计，把整个推理、计算的过程，丝毫不漏地考虑到，统统编入程序，机器则依次运行必须有足够的数理逻辑训练，熟悉推理过程的全部细节，才能从事程序的设计,第一部分数理逻辑,程序设计是一个细致而麻烦的工作如何设计正确的程序？如何防止在计算过程中出现错误？如何很快地发现这种错误而及时加以改正？程序设计理论(软件理论)中的基本而重要的内容利用数理逻辑可以帮助证明程序(段)正确性,第一章数理逻辑,主要内容命题逻辑基本概念命题逻辑等值演算命题逻辑的推理理论一阶逻辑基本概念一阶逻辑等值演算与推理学习要求掌握命题、联结词、复合命题、命题公式、等值式、等值演算、推理及证明等基本概念熟练进行等值演算与构造证明,命题(proposition),命题与真值命题：判断结果惟一的陈述句(断言assert)真值：命题的判断结果取值=真/假T/FTrue/False1/0真命题与假命题二值逻辑：vs.多值逻辑、模糊逻辑,Example,sqrt(5)是有理数F2+57Tx+53你去教室吗？这个苹果真大呀！请不要讲话！2025年元旦下大雪我正在说假话今天是星期五7是命题，它的真值现在不知道，到2025年元旦就知道了。命题真值一定是客观存在的，现在可以不知道,命题,注意判断结果唯一性：“放之四海皆准”时间性区域性标准性不是命题感叹句、祈使句、疑问句悖论、判断结果不惟一的陈述句,命题符号化,简化、形式化(简单)命题：小写英文字母p，q，r，pi，qi，ri真值：“1”=真，“0”=假Examplep：是有理数，真值=0q：2+5=7，真值=1,课程时间调整安排,计科08、网络08合班上课第619周一10,11节，4313(CAI)第69周二6,7节，4515第1019周二3,4节，4518(CAI),命题概念小结,弄清概念命题命题的真值真命题、假命题学会(简单)命题符号化,(简单)命题符号化,Examplep：是有理数，真值=0q：2+5=7，真值=1？目前的命题概念能够满足需要吗？有无比目前命题形式更复杂的陈述句？,联结词与复合命题,2是偶数而3是奇数p:2是偶数而3是奇数合适吗？该语句描述了2个事实，用一个符号表示，不合适！原语句可分解为2个陈述句2是偶数3是奇数用连词“而且”将2个陈述句合为一句2是偶数，而且，3是奇数,联结词与复合命题,2是偶数，而且，3是奇数2是偶数p：2是偶数3是奇数q：3是奇数而且：2是偶数而3是奇数：pq复合命题,联结词与复合命题,简单命题、原子(atom)命题不能再分解复合命题(compoundproposition)使用联结词(connective)组合一个或多个命题构造得到的新命题联结词：逻辑运算符(logicaloperator),联结词与复合命题,否定式与否定联结词“”定义(definition):设p为命题，复合命题“非p”称为p的否定(negation)式记作：p：否定联结词规定：p为真当且仅当p为假,真值表,描述命题真值的所有取值确定由简单命题组成的复合命题的真值,联结词与复合命题,合取式与合取联结词“”定义：设p，q为二个命题，复合命题“p并且q”，称为p与q的合取(conjunction)式记作：pq：合取联结词规定：pq为真当且仅当p与q同时为真,联结词与复合命题,合取式与合取联结词“”,联结词与复合命题,合取式与合取联结词“”描述合取式的灵活性与多样性吴颖既用功又聪明吴颖虽然聪明，但是不用功吴颖不仅用功而且聪明吴颖一面看书，一面吃苹果王华与张兰都是好学生王华是好学生，并且张兰是好学生C分清简单命题与复合命题王华与张兰是同学S,联结词与复合命题,合取式与合取联结词“”可联结相互无关系的命题235且天正在下雨,联结词与复合命题,析取式与析取联结词“”定义：设p,q为二命题，复合命题“p或q”称作p与q的析取式记作：pq：析取联结词规定：pq为假当且仅当p与q同时为假,联结词与复合命题,析取式与析取联结词“”,自然语言中“或”的两种含义,相容(inclusive)或、可兼或2或4是素数2或3是素数4或6是素数,自然语言中“或”的两种含义,排斥(exclusive)或、异或小元元只能拿一个苹果或一个梨p:拿苹果，q:拿梨符号化：(pq)(pq)、pq王小红生于1975年或1976年p:生于1975，q:生于1976)符号化：(pq)(pq)pq,联结词与复合命题,析取式与析取联结词“”可联结无关系命题235或天正在下雨,联结词与复合命题,蕴涵(implication)式与蕴涵联结词“”定义：设p,q为二个命题，复合命题“如果p,则q”称作p与q的蕴涵式(或条件式)记作：pqp前件(antecedent)、前提(hypothesis)、假设(premise)q后件(consequence)、结论(conclusion)：蕴涵联结词规定：pq为假当且仅当p为真q为假,联结词与复合命题,蕴涵式与蕴涵联结词“”,联结词与复合命题,蕴涵式与蕴涵联结词“”pq的逻辑关系p是q的充分(sufficient)条件q是p的必要(necessary)条件区分充分条件与必要条件如果G是正方形，那么G的四边相等：前“充分”后“必要”如果G是等边三角形，那么G的三个角相等：互为“充要”,联结词与复合命题,蕴涵式与蕴涵联结词“”pq的不同表述如果p,则q若p，就q只要p，就qp仅当q只有q才p除非q,才p除非q，否则非p,联结词与复合命题,当p为假时，pq为真空证明：前提为假，任意结论都可能如果太阳从西方出，雪就是黑的前假、后假，肯定假如果太阳从西方出，我就不姓黄实际生活中的常用说法如果太阳从西方出，我就姓黄结论本身是正确的天下雨，路就会湿若天未下雨，路湿或路不湿都可能,联结词与复合命题,实际生活中的蕴涵“如果/则”()描述的对象之间一般有内在联系，有推理的含义有因果：原因结果能推导：条件结论,联结词与复合命题,命题逻辑中的蕴涵：实质蕴涵前后可无因果关系只有“前后”、“左右”如果天下雨，那么2+3=5不一定是条件与结论如果我去商店，就给你买苹果若我没去商店，但在市场买了苹果推测：假设推论,联结词与复合命题,实际逻辑vs.命题逻辑实际含义vs.形式语义形式逻辑：抽象化实际逻辑“重结构、轻内容”只处理真假关系，不涉及内容、意义,联结词与复合命题,蕴涵式与蕴涵联结词“”蕴涵vs.if语句语句”ifpthens”、“if(p)s;”if2+3=5thenx=x+1if语句蕴涵,复合命题符号化,p：天冷，q：小王穿羽绒服pq如果天冷，小王就穿羽绒服因为天冷，所以小王穿羽绒服只要天冷，小王就穿羽绒服若小王不穿羽绒服，则天不冷,复合命题符号化,p：天冷，q：小王穿羽绒服qp只有天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服如果天不冷，则小王不穿羽绒服小王穿羽绒服仅当天冷时,逆/反命题,pq：只要天冷，小王就穿羽绒服逆(converse)命题：qp小王穿羽绒服仅当天冷时反(inverse)命题：pq如果天不冷，则小王不穿羽绒服逆反命题：qp若小王不穿羽绒服，则天不冷pq与qp等值(真值相同),逆/反命题,联结词与复合命题,等值(equivalence)式与等值联结词“”双条件(bi-conditional)定义：设p，q为二个命题，复合命题“p当且仅当q”称作p与q的等值式记作：pq：等值联结词规定：pq为真，当且仅当，p与q同真或同假,联结词与复合命题,等值式与等值联结词“”,联结词与复合命题,等值式与等值联结词“”pq的逻辑关系：p与q互为充分必要条件2+24当且仅当3+362+24当且仅当3是偶数2+24当且仅当太阳从东方升起2+24当且仅当美国位于非洲函数f(x)在x0可导的充要条件是它在x0连续,命题基本概念小结,p,q,r,均表示命题联结词集为,p、pq、pq、pq、pq基本复合式难点：pq,命题基本概念小结,复杂陈述句翻译成复合命题/复杂逻辑式反复使用,联结词设p:是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转(pq)(rs)p)：假命题联结词运算顺序优先级：(),同级：从左到右,逆/反命题,命题逻辑基本概念的应用,搜索引擎可视化逻辑运算符Google、Baidu、CNKI布尔搜索(BooleanSearching)技术北京AND四合居AND照片OR视频北京AND四合居AND(照片OR视频),命题逻辑基本概念的应用,程序设计语言(C、VisualBasic)位操作&、or|、andxor：异或,命题逻辑基本概念的应用,思考题,古西西里的剃头匠传说有个住在边远小镇的剃头匠，必须穿过一条危险的山路才能找到他。他只给那些不自己剃须的人刮胡子。这样的剃头匠存在吗？,思考题,说谎的村民有个村庄的人要么只说真话，要么只说假话，回答问题时只说“是”、“不”。假定你在那儿旅游，走到一个左右分岔的路口，一条到遗址，一条到废墟，此时恰有一村民在路口。请问你应该如何发问，才能找到正确的方向？,命题变项与(合式)公式,命题变项(变元variable)命题常项(constant)0、1命题变项约定：小写字母p,q,r,pi,qi,ri,命题变项与合式公式,(合式)公式(well-formedformula,wff)单个命题变项、命题常项是原子公式若A是公式，则(A)是公式若A,B是公式，则(AB)、(AB)、(AB)、(AB)是公式有限次应用规则13形成的是(合式)公式,命题变项与合式公式,(合式)公式约定：大写字母外层括号可以省去归纳(induction)或递归(recursive)定义元语言和对象语言元语言：描述对象语言的语言对象语言：描述研究对象的语言,命题变项与合式公式,合式公式的层次若公式A是单个的命题变项，则称A为0层合式称A是n+1(n0)层公式是指下面情况之一A=B，B是n层公式A=BC，其中B,C分别为i层和j层公式，且n=max(i,j)A=BC，其中B,C的层次及n同上A=BC，其中B,C的层次及n同上A=BC，其中B,C的层次及n同上若公式A的层次为k，则称A为k层公式,命题变项与合式公式,合式公式的层次A=p，0层B=p，1层C=pq，2层D=(pq)r，3层E=(pq)r)(rs)，4层,公式赋值,赋值：用命题常项替换命题变项定义：设p1,p2,pn是公式A中的命题变项，给p1,p2,pn各指定一个真值，称为对A的一个赋值(assignment)或解释(interpretation)赋值：与命题变项位置一一对应的0,1串成真赋值：使A真值=1的赋值成假赋值：使A真值=0的赋值,公式的赋值(解释),赋值：0、1串按在公式A中命题变项出现的位置顺序赋值含n个变项的公式有2n个赋值(串)Ex.(pq)r成真赋值：000,010,101,110成假赋值：001,011,100,111,公式的类型,重言式(tautology)：永真式矛盾式(contradiction)：永假式可满足式(satisfaction)：不是矛盾式一般式(contingency)重言式是可满足式，但反之不真,公式的类型,Example重言式：(pp)q矛盾式：(pp)q可满足式：pq如何判断公式的类型？如何求公式A的全部的成真与成假赋值？,真值表,定义A的真值表：A的所有取值情况列表ExampleA=(pq)rB=(qp)qpC=(pq)q,A=(pq)r真值表,B=(qp)qp真值表,C=(pq)q真值表,真值表,编制方法(P2页)中间层次可不写用途从中得知公式A的一切信息所有的可能赋值公式的所有取值公式的类型其它用途？(待续),命题与公式小结,内容命题、真值、命题的分类、命题符号化联结词,、复合命题命题公式及层次公式类型真值表,命题与公式小结,要求深刻理解各联结词的逻辑关系会求复合命题的真值熟练地将复合命题符号化准确地求公式的真值表求公式成真赋值、成假赋值判断公式类型,练习题,1.将下列命题符号化豆沙包是由面粉和红小豆做成的苹果树和梨树都是落叶乔木王小红或李大明是物理组成员王小红或李大明中的一人是物理组成员由于交通阻塞，他迟到了如果交通不阻塞，他就不会迟到他没迟到，所以交通没阻塞除非交通阻塞，否则他不会迟到他迟到当且仅当交通阻塞,练习题,解析分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及必要充分条件,练习题,答案(14)豆沙包是由面粉和红小豆做成的：简单命题p:豆沙包是由面粉和红小豆做成的苹果树和梨树都是落叶乔木：合取式p:苹果树是落叶乔木q:梨树是落叶乔木pq,练习题,答案(14)王小红或李大明是物理组成员：析取式王小红是物理组成员:p李大明是物理组成员:q王小红或李大明是物理组成员:pq相容或,练习题,答案(14)王小红或李大明中的一人是物理组成员：析取式王小红是物理组成员:p李大明是物理组成员:q(pq)(pq)排斥或,练习题,答案(59)，设p:交通阻塞，q:他迟到(5)由于交通阻塞，他迟到了：pq(6)如果交通不阻塞，他就不会迟到：pq或qp(7)他没迟到，所以交通没阻塞：qp或pq(8)除非交通阻塞，否则他不会迟到：qp或pq(9)他迟到当且仅当交通阻塞：pq或pq(5)与(7)，(6)与(8)相同：逻辑等值/等价(equivalent),练习题,2.求下面命题的真值设p:2是素数q:北京比天津人口多r:美国的首都是旧金山(1)(pq)r(2)(qr)(pr)(3)(qr)(pr)(4)