离散数学第3章命题逻辑.ppt

《离散数学第3章命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学第3章命题逻辑.ppt（192页珍藏版）》请在三一办公上搜索。

1、第3章 命题逻辑,3.1 命题的有关概念,本讲内容,命题之间的还有些什么关系?认知关系:我知道偏好关系:他喜欢,逻辑关系,Chapter 3 命题逻辑,逻辑学是研究思维形式及思维规律尤其是推理的学科.逻辑推理无处不在.亚里士多德(Aristotle,公元前384公元前322)是形式逻辑的创始人.数学,物理学,化学,天文学,地学,生物学,逻辑学.(MBA,MPA,招聘等),莱布尼茨(G.Leibniz,1647-1716)是数理逻辑的创始人.传统的数理逻辑(内容包括逻辑演算、公理化集合论、模型论、递归论和证明论).,应用逻辑,如多值逻辑、模态逻辑、归纳逻辑、时序逻辑、动态逻辑、模糊逻辑、非单调逻

2、辑、缺省逻辑、数字逻辑、电路逻辑、算法逻辑及程序逻辑等,这些都与计算机科学密切相关.计算机如何进行逻辑思维的计算思维培养.,命题逻辑与谓词逻辑是数理逻辑的基础部分.本章学习命题逻辑.命题逻辑的研究对象是命题.,3.1 命题的有关概念,计算机的计算过程就是推理过程,而每一步推理离不开判断,判断的对象就是命题.1.什么是命题?命题是能判断出真假的语句.从三个方面去理解：,(1)命题必须是一个完整的句子,包括用数学式子如代表的语句.(2)所给语句具有真假意义,即有是否符合客观实际或是否合理之分.一般来说,只有陈述句才具有真假意义,祈使句、疑问句和感叹句不具有真假意义;(3)能判断出真假.要是将来某时

3、候能判断出真假也行.,例3-1 判断下列语句是否是命题.(1)辽宁舰是中国的第一首航空母舰.(2)我喜欢智能手机和平板电脑.(3)x 3.(4)立正！(5)这朵花真漂亮！,(6)你要我的手机号码是想给我充话费?(7)火星上有生物.(美国Discovery号:火星上有水?2012年着陆火星的Curiosity号,1+1=2)(8)我说的都是假话.(9)小王和小李是同学.(10)你只有刻苦学习,才能取得好成绩.,歌德巴赫猜想:至今已200多年.(1)1+1=2:大于4的偶数是两个奇素数之和.6=3+3;8=3+5;10=3+7=5+5;12=5+7;(2)任何大于7的奇数是三个奇素数之和.9=3+

4、3+3;11=3+3+5;13=3+3+7;15=3+5+7;陈景润(1966)的“陈式定理”:1+2=3,任何充分大的偶数是一个素数与两个素数乘积之和.2007年11月15日重庆商报,大坪67岁罗仁德破解.1935年出生的河北的何宝起自称破解,奔波8年无人理.,2.命题的真值(truth)命题的真值就是命题的逻辑取值.经典逻辑值只有两个:1和0,它们是表示事物状态的两个量.若一个命题是真命题,其真值为1;若一个命题是假命题,其真值为0.实际上在数理逻辑中,更多时候逻辑真是用T(True)或t,逻辑假用F(False)或f表示的.,3.原子命题与复合命题若一个命题不包含有更小的命题,则称其为原

5、子命题(atom)当时认为原子最小?或简单命题,否则称为复合命题(compound proposition).原子命题是命题逻辑研究的基本单位,区分原子命题在后面命题的符号化时是很重要的.通常用小写英文字母p,q,r,s,或带下标p1,p2,p3,等来表示原子命题,如用p:2+3=5,q:今天我们上课.,4.逻辑常量与逻辑变量把1和0称为逻辑常量(logical constant).在逻辑表达式中出现的p,q,r或p1,p2,p3 等称为命题变元(proposition variable)或逻辑变量(logical variable).命题变元可以代表任意命题,从取值的角度看,命题变元既可以取

6、1又可以取0.课堂练习 习题3.1 1,2.,小结,第3章 命题逻辑,3.2 逻辑联结词,本讲内容,pq,pq,pq,3.2 逻辑联结词,逻辑联结词就是逻辑运算:复合命题是由原子命题构成的,它需要联结词.给定了原子命题,使用逻辑联结词可以构成复合命题.逻辑联结词类似于自然语言中的连词.,1.否定(not)联结词:p p:2+3=5,p:2+3 5.p是数理逻辑中的标准符号,也可记为p,C语言!p,在计算机其他课程中用,对应于逻辑门电路中的“非门”.,2.合取(and)联结词:p q p:小李能歌,q:小李善舞.p q:小李能歌且善舞.合取“”相当于“并且”,“和”,“与”,“以及”等.,Rem

7、ark(1)“小王和小李是同学”中的“和”没有合取之意.(2)在数理逻辑中,合取联结词可以将任意两个命题联结起来以构造出新的命题,如用p:2+3=5,q:今天上课,则p q:2+3=5且今天上课.下面要介绍的其他联结词都是这样理解.,(3)p:小李结婚了q:小李有小孩了p q,q p?p q:p&q,p&q,p q=pq,对应于“与门”.,3.析取(or)联结词:p q p:这学期我选修人工智能课程,q:这学期我选修模式识别课程.p q:这学期我选修人工智能课程或者模式识别课程.,析取“”相当于“或者”.p|q,p|q,p+q(“或门”).,本讲内容,pq,pq,pq,4.异或(exclusi

8、ve or,XOR)联结词:p q自然语言中的“或”:(1)“可兼或”(inclusive or),它表示两者可同时为真,用析取表示即可.(2)“不可兼或”,它表示两者不能同时为真,换句话说,两者同时为真是假命题.这就需要异或联结词.,p:明天去深圳的飞机是上午八点起飞,q:明天去深圳的飞机是上午八点半起飞.p q:明天去深圳的飞机是上午八点或上午八点半起飞.本学期张三或李四当选为班长.今天晚上在寝室上自习或去电影院看3D电影.(都在寝室?7:30?),与异或联结词对应的门电路为“异或门”.一般来说,只要不是非常明显的不可兼就使用.,5.条件(conditional)联结词:p q p:我有时

9、间,q:我去看望我的父母.pq:如果我有时间,那么我去看望我的父母.“”相当于“如果那么”,“若则”,等.p q 可读作“(若)p则q”.,蕴涵联结词也可以称为条件联结词.在p q中,p称为前件,q称为后件.当 p=1,q=1时p q=1;当 p=1,q=0时p q=0,这是比较好理解的两种情形.规定的合理性见下面的例子.(1)如果太阳从西边出来,那么2+3=5.(2)如果太阳从西边出来,那么2+3=4.,实际上,在根据子集的定义证明1.1节的定理:对于任意集合A,有 A时,就要用到上述实质蕴涵的定义.同样,在理解关系的自反、反自反、对称、反对称及传递性质时,也要用到上述实质蕴涵的定义.当然,

10、在现代逻辑中,对蕴涵的不同理解会得到不同的逻辑系统,如由严格蕴涵得出模态逻辑系统.,6.双条件(biconditional)联结词:p q p:四边形是平行四边形,q:四边形的对边平行.p q:四边形是平行四边形当且仅当四边形的对边平行.p q:可读作“p当且仅当q”.双条件联结词“”相当于自然语言中的“当且仅当”、“充分必要条件”,其英文为if and only if,缩写为iff.,“p当且仅当q”有两层含义：(1)“p当q”是指q p.(2)“p仅当q”是指p q.正因为此,等价联结词又可以称为双蕴涵联结词或双条件联结词.数字逻辑等课程 的“同”,并用“”表示.,本讲内容,pq,pq,p

11、q,7.与非(NOT AND)联结词:p q在数字逻辑以及计算机组成原理中“”没有专用的运算符号,“p与非q”直接记为,对应的门电路为“与非门”.,8.或非(NOT OR)联结词:p q在数字逻辑以及计算机组成原理中“”没有专用的运算符号,“p或非q”直接记为,对应的门电路为“或非门”.,9.条件否定(NOT-IF-THEN)联结词:读作“p条件否定q”,其中n表示否定not.“p条件否定q”可直接记为,上面介绍了1个一元逻辑运算、8个二元逻辑运算.后面将证明：不同的一元逻辑运算和二元逻辑运算共9个.要求 理解记忆上述9个,特别是最前面的6个联结词的运算表.思考 如何定义三元逻辑运算?课堂练习

12、 习题3.2 16.,小结,第3章 命题逻辑,3.3 命题公式及其真值表,本讲内容,3.3 命题公式及其真值表,有了前面的两节内容,就可以得到命题逻辑的符号体系.1.命题公式(proposition formula)的定义逻辑函数(logical function)逻辑表达式(logical expression),其中的常量是逻辑常量1和0,其中的变元是命题变元或逻辑变量.,命题公式是由命题常量、命题变元、逻辑联结词、左圆括号及右圆括号构成的有意义(well-formed)的符号串,其严格定义需借助于递归定义方式给出.Definition(1)1,0,p,q,r,(2)A(A)(3)A,B(

13、4)有限次应用(1)(2)(3)所得到的符号串是仅有的命题公式.,命题公式可称为合式公式(Well-Formed Formula,WFF)或简称为公式,其全称为命题合式公式,是书写正确、含义清楚的表达式或者说符号串.借助于函数给命题公式下定义.,可以省略括号的约定:(1)最外层的括号可以省略.在形成最终的命题公式时,所有的中间过程得到的命题公式,包含其本身,都称为该命题公式的子公式.,(2)9个联结词运算的优先顺序依次为:符合本约定的有些括号可以不写.如命题公式 Remark 这种规定不是唯一的.,(3)同级运算从左至右依次进行.如 实际上,在对命题进行符号化时,只要书写正确的逻辑函数都是命题

14、公式.,2.命题的符号化命题的符号化就是使用符号命题变元、逻辑联结词和括号将所给出的命题表示出来.符号体系来源于实际问题.给出进一步学习逻辑演算系统的语义解释时的一种标准模型.,命题的符号化的步骤:Step 1 找出所给命题的所有原子命题,并用小写英文字母或带下标表示；Step 2 确定应使用的联结词,进而将原命题用符号表示出来.,例3-7 将下列命题符号化.(1)天气很好或很热.(2)如果张三和李四都不去,那么我就去.(3)仅当你走,我留下.(4)我今天进城,除非天下雨.(5)你只有刻苦学习,才能取得好成绩.,Solution(1)用p:天气很好,q:天气很热“天气很好或很热”可符号化为(2

15、)用p:张三去,q:李四去,r:我去.则原命题可符号化为(3)用p:你走,q:我留下则“仅当你走,我留下”可符号化为,(4)p:我今天进城,q:天下雨.除非=如果不.(5)p:你刻苦学习,q:你取得好成绩.只有p,才q?,本讲内容,3.命题公式的真值表命题公式的真值表就是命题公式的取值情况表.若对中出现的每个命题变元都指定一个真值1或者0,就对命题公式A进行了一种真值指派或一个解释,而在该指派下会求出公式A的一个真值.将A的所有可能的真值指派以及在每一个真值指派下的取值列成一个表,就得到命题公式A的真值表(truth table).例3-8 写出命题公式 的真值表.,要求大家能准确写出一个命题

16、公式的真值表,这是本节的重点内容,当然必须牢记联结词的运算表才行.由表知,含3个命题变元的命题公式有8=23 种不同的真值指派.很显然,含2个命题变元的命题公式有4=22 种不同的真值指派.含n个命题变元的命题公式的不同的真值指派有2n种.,4.命题公式的类型(1)在任何指派下均取真的命题公式称为永真式或重言式(tautology)；(2)在任何指派下均取假的命题公式称为永假式或矛盾式(contradiction)；(3)至少有一种指派使其为真的命题公式称为可满足式(satisfactable formula)；,(4)至少有一种指派使其为真同时至少有一种指派使其为假的命题公式称为中性式(偶然

17、式)(contingency).,例3-9真值表法?,例3-10Proof 由A=1可推出B=1,则A B永真.由B=0可推出A=0,则A B永真.取值法?(本质上是真值表法),最后介绍永真式的代入定理RS(Rule of Substitution).Theorem 3-1(永真式的代入定理)如何使用?,小结与作业,第3章 命题逻辑,3.4 逻辑等值的命题公式,本讲内容,3.4 逻辑等值的命题公式,命题“四边形的对边平行”与命题“四边形的对边相等”是逻辑等值的,它们在逻辑上说的是同一回事.上述两个命题的真值是相同的.下面讨论两个命题公式逻辑等值.,1.逻辑等值的定义Def 给定两个命题公式A和

18、B,若在任何真值指派下A和B的真值都相同,则称命题公式A和B逻辑等价或逻辑等值(logically equal)或简称为等值或相等,记为 A=B.Remark“=”是命题公式之间的关系符号.A B?,Theorem 3-2 A=B的充要条件是A B永真.Proof Clearly.下面的例子说明如何利用真值表(第一种方法)证明两个命题公式等值.,例3-11 证明:,Theorem 3-3例如,Theorem 逻辑等值是命题公式间的等价关系:(1)自反,(2)对称,(3)传递.Problem 等价类是什么?,2.基本等值式(I)与,有关的等值式Theorem 3-5(1)(2)(3)(4)(5)

19、,(6)(7)(8)(9)(10)Remarks(1)与集合的有关性质类似.(2)每条性质均可证明.,(II)其他重要的等值式 Theorem(1)(2)(3)(4)(5)(6)Proof(?),3.等值演算法基本等值式有很多用途,如化简命题公式、判断命题公式的类型、证明等值式、计算命题公式的范式、命题逻辑中的推理等,要求大家要熟记,特别是定理3-5中的等值式.,在使用等值式时,常用下列的等值置换定理RR(Rule of Replacement).等值置换定理 设C是命题公式A的子公式,若C=D,则将A中的C部分或全部替换为D所得到的命题公式与A等值.利用基本等值式以及等值置换定理求解问题的方

20、法称为“等值演算法”.,例3-13 化简(?)下列命题公式并将最后结果用只含和表示.(1)(2)Solution(1),数字逻辑、计算机组成中经常化简单!,利用等值演算法,判断一个命题公式的类型是比较方便的.例3-14 设A,B,C是任意的命题公式,判断下列命题公式的类型:(1)(2)Solution(2),证明两个命题公式等值的第二种方法:等值演算法.例3-15 设A,B,C是任意的命题公式,证明下列等值式.(1)(2)Proof(2),4.对偶原理在与,有关的基本等值式中,除性质(1)外,其它性质都是成对出现的,两者间有一定的联系.先给出命题公式的对偶式的定义.Def 3-4 设命题公式A

21、中至多含有3个逻辑联结词,(1)将A中的换成；(2)A中的换成；(3)A中的1换成0；(4)A中的0换成1,所得到的命题公式称为是A的对偶式(dual formula),记为A*.,例如 Remark 一般来说,对偶原理 设A和B是命题公式,若A=B,则A*=B*.有了对偶原理后,定理3-5中除性质(1)外的等值式,只需要记住其中一个就可以了.有了对偶原理,我们可以求出任意命题公式的对偶式.,小结与作业,第3章 命题逻辑,3.5 命题公式的范式,本讲内容,3.5 命题公式的范式,命题公式的范式就是其标准形式或规范形式.有了命题公式的范式,就可以不用写出真值表就能确定在何真值指派下取真以及在何真

22、值指派下取假.,1.命题公式的析取范式及合取范式(1)析取范式及合取范式的定义 Def 3-5 设A是命题公式,若A=A1 A2 An(n 1),其中Ai(1 i n)是由命题变元或其否定组成的合取式,则称A1 A2 An为A的析取范式(disjunctive normal form).Remarks Ai=p q r,p q,q r,q,r?n=1?如A=p q r=(p q r).,Def 3-6 设A是命题公式,若A=A1 A2 An(n 1),其中Ai(1 i n)是由命题变元或其否定组成的析取式,则称A1 A2 An为A的合取范式(conjunctive normal form).R

23、emarks Ai=p q r,p q,q r,q,r?n=1?如A=p q r=(p q r).若A=p q r,则p q r也是A的析取范式.,(2)析取范式及合取范式的计算Step1 使用等值式,将命题公式中的联结词归约为,；Step2 利用De Morgan律将移到命题变元的前面；Step3 根据分配律得到命题公式的析取范式及合取范式：A(BC)=(AB)(AC)(求析取范式用).A(BC)=(AB)(AC)(求合取范式用).,例3-17 设p,q和r是命题变元,求命题公式A=(p q)r的析取范式及合取范式.Solution 求命题公式的析取范式及合取范式的Step1和Step2是相

24、同的.,析取范式:合取范式:,(3)析取范式及合取范式的应用根据命题公式的析取范式及合取范式可分别得出该命题公式取真、假的指派.,例3-18 从p,q,r,s四人中选派2人出差,求满足下列3个条件的选派方法有哪几种.(1)若p去,则r和s中只去1人；(2)q和r不能都去；(3)若r去,则s不能去.Solution p:p去出差,q:q去出差,r:r去出差,s:s去出差,则(1)(2)(3),(a)p,s去;(b)q,s去;(c)p,r去.,2.命题公式的主析取范式及主合取范式一般来说,命题公式的析取范式及合取范式不是唯一的,如A=(p q)(p q)=p都是A的析取范式.下面讨论,给定命题公式

25、的唯一的标准形式：主析取范式以及主合取范式.给定命题公式,从A中命题变元产生的最小项和最大项的角度来讨论A的主析取范式及主合取范式,在逻辑电路中也会讨论其相应的标准形式.,(1)主析取范式Def 对于给定的命题变元,若由命题变元或其否定组成的合取式满足(1)每个命题变元或其否定二者之一只出现一次;(2)按字典顺序或按下标从小到大顺序出现,称这样的合取式为由所给命题变元产生的最小项.,对于每一个最小项只有一种指派使其取1.可以根据这个结论对最小项编码.最小项用表示mi,其下标是由成真指派得到的二进制数或对应的十进制数,对于最小项p q r,成真指派得到的二进制数为110,因为(110)2=6,所

26、以p q r=m110=m6.表3-15?,Def 对于命题公式A,若A等值于由A中所有命题变元产生的若干个最小项的析取,则把后者称为A的主析取范式(major disjunctive form).含n个命题变元的命题公式,“若干个”最大为2n,最小为0.所有最小项的析取为永真式1,而0个最小项的析取意味着A为永假式0,这时的主析取范式不存在.除这两种极端情形外,A均为中性式.,显然,主析取范式是析取范式,但反过来不成立.,根据这个分析,我们得到求A的主析取范式的第一种方法：等值演算法.利用等值演算法求A的主析取范式的步骤为Step1 求出A的析取范式；Step2 利用分配律补充所缺少的命题变

27、元.由上面的主析取范式可知,使A取1的真值指派为(p,q,r)=(1,0,0),(0,1,1),(0,0,1),(1,1,1).实际上,我们可以利用A的真值表求A的主析取范式.,利用真值表求主析取范式的3个步骤为Step1 写出命题公式A的真值表；Step2 对于使A取1的指派,写出对应的最小项,使该最小项在该指派下也为1；Step3(可以证明)A等值于所有这样写出的最小项的析取.,例3-20 设p,q和r是命题变元,求命题公式(p q)r 的主析取范式.,(2)主合取范式主合取范式的讨论与主析取范式是类似的,为了方便自学,我们还是进行完整的讨论.Def 3-9 对于给定的命题变元,若由命题变

28、元或其否定组成的析取式满足(1)每个命题变元或其否定二者之一只出现一次;(2)按字典顺序或按下标从小到大顺序出现,称这样的析取式为由所给命题变元产生的最大项(maximal term).,对于每一个最大项只有一种指派使其取0.可以根据这个结论对最大项编码.最大项用表示Mi,其下标是由成假指派得到的二进制数或对应的十进制数,对于最大项p q r,成真指派得到的二进制数为001,因为(001)2=1,所以p q r=M001=M1.,Def 3-10 对于命题公式A,若A等值于由A中所有命题变元产生的若干个最大项的合取,则把后者称为A的主合取范式.含n个命题变元的命题公式,“若干个”最大为2n,最

29、小为0.所有最大项的合取为永假式0,而0个最大项的合取意味着A为永真式1,这时的主合取范式不存在.除这两种极端情形外,A均为中性式.,主合取范式是合取范式,但反过来不成立.,根据这个分析,我们得到求A的主合取范式的第一种方法：等值演算法.利用等值演算法求A的主合取范式的步骤为Step1 求出A的合取范式；Step2 利用分配律补充所缺少的命题变元.由上面的主合取范式可知,使A取0的真值指派为(p,q,r)=(0,0,0),(0,1,0),(1,1,0),(1,0,1).实际上,我们可以利用A的真值表求A的主合取范式.,下面介绍求的主合取范式的第二种方法：真值表法.Step1 写出命题公式A的真

30、值表；Step2 对于使A取0的指派,写出对应的最大项,使该最大项在该指派下也为0；Step3(可以证明)A等值于所有这样写出的最大项的合取.,例3-22 设p,q和r是命题变元,求命题公式(p q)r 的主合取范式.,Theorem 3-9 任意非永假命题公式都存在唯一的主析取范式;任意非永真命题公式都存在唯一的主合取范式.(1)命题公式的主析取范式和主合取范式是等值的.(2)主析取范式中所含的最小项个数加上主合取范式中所含的最大项个数等于该命题公式的真值指派数目.(3)可以从主析取范式求出主合取范式,反过来亦然(?).,A.利用命题公式的主析取范式及主合取范式判定其类型.例3-23 设p和

31、q是命题变元,利用主范式判断命题公式p(p q)的类型.Solution,B.利用命题公式的主析取范式及主合取范式可以判断两个命题公式是否等值.例3-24(1)(2),C.在数字逻辑等后继课程中的应用.例3-25 设公式A的真值表如下,求A.,将A化简.门电路实现.,解法1比解法2好,因为最小项的个数为3而最大项的个数为5,所以在电路实现时对A进行的化简要容易些.一般原则是,若取1的个数小于取0的个数,求出主析取范式;若取0的个数小于取1的个数,求出主合取范式.同一个命题公式的主析取范式与其主合取范式是等值的.只要给出了一个命题公式的真值表,就可以将该命题公式(的表达式)求出来.这一点在3.6

32、节中也会用到.,另外,根据真值表法可知,若得出了命题公式的主析取范式,则可以得出使为真的所有指派,进而得出使为假的所有指派,因此可以得出命题公式的主合取范式;反过来亦然.,小结与作业,第3章 命题逻辑,3.6 联结词集合的功能完备性,本讲内容,3.6 联结词集合的功能完备性,前面介绍了9个联结词,我们想知道(1)(1元和2元)联结词一共有多少个.(2)哪些联结词集合具有功能完备性.这些内容可以从一定的理论高度帮助理解逻辑门电路的种类及其按一定要求化简逻辑函数等问题.1.联结词的个数,由p和q可构成不等值的命题公式共222=16个(?),记为Ai(i=1,2,16).,集合运算与逻辑运算之间有紧

33、密的联系.问题1 能否类似于真值表形式给出集合运算的定义?若能,如何给出?前面已经说明了,不同的1元和2元逻辑运算共9种(3元逻辑运算更多),而集合运算只介绍了5种.问题2 给出另外4种集合运算的定义.问题3 9种逻辑运算与9种集合运算是如何对应的?,2.联结词集合的功能完备性有些逻辑运算可以借助于其他联结词加以定义.有些联结词如就不能由和加以定义,这涉及到联结词集合的功能完备性.,Def 3-11 对于若干个联结词组成的非空集合S,若任意的命题公式都可由仅含S中的联结词等值地表示出来,则称S为功能完备联结词集(complete group of connectives).,将S中的联结词理解

34、为门电路,则S是完备的是指任何的组合逻辑电路都可以由这些门电路实现.任意命题公式都存在唯一的主析取范式或主合取范式,于是任意的命题公式都可以由,等值表示出来.因此,有Theorem,是功能完备联结词集.,Corollary(1).(2).(3),.(4),.(5),.Proof(1),例3-26Solution,?,例3-27Solution,?,下面考虑不具有功能完备性的联结词集.例3-28,?Proof 首先证明,对于只含有联结词的任意命题公式A,在所有命题变元均取1时,A的真值为1.对A中所含的联结词个数n使用数学归纳法.n=0?AB,AB?其次说明 p p?,Def 3-12 设S是功

35、能完备的联结词集,而S的任意非空真子集都不是功能完备的联结词集,则称S为最(极)小的功能完备的联结词集.Theorem 3-11 下列联结词集是最小功能完备的:(1).(2).(3),.(4),.(5),.,知道了逻辑运算的个数以及最小的功能完备的联结词集,对于我们进一步学习、研究逻辑演算形式系统是有帮助的.在实际应用中,联结词“”以及“”可推广到多个命题变元上去,如“与或非门”等.,小结,第3章 命题逻辑,3.7 命题逻辑中的推理,本讲内容,3.7 命题逻辑中的推理,逻辑学的主要内容是研究推理,推理是从一些前提推出结论的思维过程.数理逻辑主要是用数学的方法研究逻辑中的推理,它关心的是推理形式

36、的有效性问题.,下面两个不同的推理(a)若两直线平行,则同位角相等,这两直线是平行的,所以,同位角相等.(b)若两个三角形全等,则其对应边相等,这两个三角形全等,所以,它们的对应边相等.都具有如下的推理形式:由p q,p 得出q.,所谓推理形式的有效性是指,如果前提全为真,那么所得结论必然真,而不考虑前提和结论的真实含义.有效的推理形式是四海皆准的推理规则.1.推理形式有效性的定义Def 3-13(logically follows),Theorem 的充要条件由上述定理,知“”是关系符号,它与蕴涵联结词“”是不同的.,从推理的角度看,将“=”写成“”更适合:Theorem 3-13 设A和B

37、是命题公式,则A=B的充要条件是A B且B A.Hint,命题公式间的永真蕴涵关系是偏序关系.(1)A A(自反性).(2)若A B且B A,则A=B(反对称性).(3)若A B且B C,则A C(传递性).,命题公式间的关系还具有下面两条性质.Theorem 3-15(1)若A C且B C,则A B C.(2)若C A且C B,则C A B.Theorem 3-16 设A,B是命题公式,则对于命题公式间的“”关系:(1)supA,B=A B.(2)infA,B=A B.,2.基本推理规则下面举例说明,证明推理形式有效性的4种方法.例3-29 设A和B是命题公式,证明:A B,A B.分析:(

38、p q)p q永真?Proof 1 真值表法.Proof 2 取值法.(p q)p=1,q=1?,Proof 3 等值演算法.(p q)p q=1?Proof 4 主范式法.主析取范式:主合取范式:不存在.,基本推理规则或基本蕴涵式I.(1)(2)(3)(4),(5)(6)(7)(8)基本等值式E:表3-24.,3.命题逻辑的自然推理系统作为推理系统,原则上有以下四个部分：第一,它应有初始符号,它是系统中允许出现的字符.自然推理系统的初始符号有3类:(1)命题变元.(2)5个联结词.(3)左右圆括号.,第二,定义推理系统中的公式,它是按一定的形成规则得到的有意义的符号串.粗略地说,它就是命题公

39、式,但它原则上不出现除,外的其它联结词,同时原则上不出现命题常量1和0.,第三,确定公理,就是推理系统中不加推导就承认的公式.从语义的角度看,它就是永真式.自然推理系统中没有公理,这一点是与公理推理系统截然不同的.,第四,确定推理规则.在自然推理系统中,把所有与5个联结词有关的基本逻辑蕴涵式都作为推理规则(见表1),同时,一个基本等值式(见下表2)相当于两个基本逻辑蕴涵式.两个最基本的推理规则：P规则 所给的前提在证明过程中随时可以引用.T规则 已经推出的公式在以后的证明过程中可以随时引用.,自然推理系统的显著特点是没有公理,作为推理依据的只有推理规则.这似乎更符合人们日常思维的推理习惯,因此

40、称为自然推理.在进行自然推理时,采用构造性证明方法,简称“构造法”,更准确地应该说是数理逻辑中的演绎(deduction)法.通过一个例子了解证明的书写格式.,例 3-30 使用构造法证明:Proof(1)p s P(2)p T(1)I(3)s T(1)I(4)p(q r)P(5)q r T(2)(4)I(6)s q P(7)q T(3)(6)I(8)r T(5)(7)I,从证明过程可以看出,每一行由3部分组成：第一部分是编号,说明它是证明的第几步；第二部分仅写一个命题公式,实际上编号也说明了它是第几个命题公式;第三部分是写理由,交代该命题公式是怎样得来的.初学者最感困难的是,如何一步一步的构

41、造出从前提到结论的证明过程.与其它证明题一样,可以先进行分析(?).,一个推理形式是有效的,实际上是指符号推理是正确的.要证明一个推理形式是有效的,首先将所给的前提和结论符号化,再证明这个符号推理是正确的.例3-32 用构造法证明下列推理形式的有效性：如果小赵和小钱去上自习,则小孙也去.小李不去自习或小赵去自习,由于小钱和小李已经去自习了,所以小孙也去上自习了.,下面介绍两种间接的构造性证明方法.(1)反证法要证明,将结论C否定得到C,然后推出一个矛盾,如S S即可.,例3-33 反证法?Proof(1)(p)P(附加)(2)p T(1)E(3)r q P(4)q T(3)I(5)p q T(

42、2)(4)I(6)p qr P(7)r T(5)(6)I(8)r T(3)I(9)r r T(7)(8)I,(2)CP规则(条件证明规则)对于如下形式的推理只需要证明因为,例3-34 使用CP规则证明:Proof(1)p(q r)P(2)p P(附加)(3)q r T(1)(2)I(4)q p P(5)q p T(4)E(6)q T(2)(5)I(7)r T(3)(6)I(8)s r P,数理逻辑的主要研究任务是建立一个严密的逻辑推理系统公理推理系统来刻划人类的思维规律.如PC(formal system of Proposition Calculus)在理论上证明了该逻辑系统合理性、一致性、

43、完备性等与语法和语义有关的重要结论,PC能得出人类思维的所有推理规则,所提供的逻辑推理框架能保证在前提真的条件下,总能得出正确的结论.对逻辑演算形式系统感兴趣,特别是做计算机软件工作的读者请参阅有关文献.,小结与作业,离散数学,第26讲 第3章复习小结,1、命题的有关概念,能判断出真假的语句称为命题.真命题真值为1,假命题真值为0.不能分成更小的命题是原子命题,通常用小写英文字母或带下标表示,否则是复合命题.命题常量与命题变元.,2、逻辑联结词,1元或2元逻辑运算共有9个最基本的联结词是,.,例1 下列联结词中,不满足交换律的是().(A).(B).(C).(D).,3、命题公式,命题公式就是

44、逻辑函数或逻辑表达式,其中出现命题常量0和1、命题变元和逻辑运算,但含义要清楚.将一个命题符号化后所得到的式子均为命题公式.,命题符号化的步骤:第一步,找出所给命题的所有原子命题,并用小写英文字母或带下标表示.第二步,确定应使用的联结词,进而将原命题用符号表示出来.,例2 令p:我将去上网,q:我有时间,则“我将去上网,仅当我有时间”可符号化为().(A)pq.(B)pq.(C)qp.(D)pq.,例3 设p：我们划船,q：我们跑步,则命题“我们不能既划船又跑步”符号化为()(A)p q(B)p q(C)(p q)(D)(p q),命题公式的真值表就是该命题公式的取值情况表,要求能准确写出给定

45、命题公式的真值表,当然记住逻辑运算表是至关重要的.含n个命题变元的命题公式的真值指派有2n.,例4 命题公式 p(q r)的成假赋值(p,q,r)为.Answer(0,1,1),(0,0,1),(0,0,0).成真赋值?例5(判断题)命题公式(p q)q是永真式?,4、逻辑等值的命题公式,两个命题公式等值讨论的是它们之间的一种逻辑关系.给定两个命题公式和，是指在任何真值指派下和的逻辑取值都相同.,基本等值式除与集合运算性质类似的那些外,特别要记住:,例6 下列()组命题公式是等值的.(A)A B,AB(B)A(BA),A(AB)(C)B(AB),B(AB),(D)A(A B),B,由于等值关系

46、是等价关系,可以按通常方式进行等值演算,特别在等值演算过程中可以使用“等值置换定理”.理解命题公式的对偶式,了解对偶原理:设A和B是命题公式，若A=B，则A*=B*.,例7 设A,B,C是任意的命题公式,化简命题公式(A B C)(A B C),并将最后结果仅用表示.Solution(A B C)(A B C)=A C=(A C)=(A)(C)=(AA)(CC),例8(1)列出与非联结词“”的运算表.(2)仅使用与非联结词“”分别表示,.,5、命题公式的范式,由于等值关系是等价关系,需要考虑其等价类及其代表元.命题公式的范式就是命题公式的标准形式或规范形式(作为代表元),要求能熟练得出给定命题

47、公式的范式.,若A等值于由A中所有命题变元产生的若干个最小项的析取,则把后者称为A的主析取范式.若A等值于由A中所有命题变元产生的若干个最大项的合取,则把后者称为A的主合取范式.,例9 n个命题变元 p1,p2,pn 的_称为最小项,其中每个变元与它的否定不能同时出现,但两者必须一次.A=A(p,q)?A=A(p,q,r)?,要求掌握利用等值演算法和真值表法求出命题公式的范式,尤其是命题公式的主范式.例10 分别利用(1)等值演算法和(2)真值表求命题公式A=(r(q p)(p(q r)的主析取范式和主合取范式.,Hint A的主合取范式:p q r.A的主析取范式为:?,6、联结词集合的功能

48、完备性,由等值命题公式知道,1元逻辑运算和2元逻辑运算的个数共9个.,是功能完备联结词集,进而,、,、,、和 是功能完备的.,例11(判断题)非空1元及2元联结词集合的个数为29-1?例12(判断题)任意最小功能完备联结词集至少有2个联结词?例13(填空题)联结词集合,()功能完备的.,7、命题逻辑的推理,在进行推理时,采用的方法是构造法,是一种形式证明方法只在符号之间进行.需要通过一些训练才能熟练掌握.同时,还要掌握两种间接的构造性证明方法:(1)反证法,(2)CP规则(条件证明规则).,例14 使用CP规则证明:p(q r),q(r s),p q s,Proof(1)q P(附加)(2)q(r s)P(3)r s T(1)(2)I(4)p P(5)p(q r)P(6)q r T(4)(5)I(7)r T(1)(6)I(8)q s CP,例15 构造下面推理的证明：如果小张和小王去看电影,则小李也去看电影.小赵不去看电影或小张去看电影.小王去看电影.所以,当小赵去看电影时,小李也去.,Hint 令p:小张去看电影,q:小王去看电影,r:小李去看电影,s:小赵去看电影.(p q)r,s p,q s r?,Any Questions,?,