湖南大学离散数学教案-命题逻辑.ppt

第一章 命题逻辑,杨圣洪,引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。命题逻辑是数理逻辑的基础部分，但究竟什么是命题？如何表示命题？如何构造出复杂的命题？在本章将讨论这些问题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如：(1)湖南大学是一本学校。(2)命题逻辑是计算机科学的基础课程。(3)命题及联结词是命题逻辑的最基础的内容。(4)4是素数。(5)湖南大学坐落于湘江以东。(6)2011年湖南长沙轻轨通车。其中(1)、(2)、(3)与事实相符，是对的、正确的，称为真命题，或者称命题的值为“真”，简记为T或数字1。而(4)、(5)明显与事实不相符，是错的、不正确，称为假命题，或称命题的值为“假”，简记为F或数字0。陈述句(6)的正确性，到2011年12月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如：(7)x与y之和为100，其中x为整数，y为整数(8)1加1等于10(7)的对错不确定的。当x为50、y为50时是对的，当x为51、y为52时是错的。(8)的对错是不确定的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句不是命题。(9)岳麓山的红叶真美呀！(10)动作快点！(11)你是离散数学老师吗？这三个语句不是陈述语句，因此不是命题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如：(12)我在说假话。(13)我只给自己不能理发的人理发。(14)派出所说:必须先房子再能上户口 单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗?这是一个悖论，其真值不能确定，故不是命题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如：(13)我既要学程序设计，又要学离散数学。(14)我们早餐在公寓食堂或外面早点摊上吃。(15)我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。其中(13)与(14)可分解为另外二句话的组合，而(15)是对“我是数学院学生”的否定，这些语句称为“复合命题”，不能再分解的语句称为“简单命题”或“原子命题”，为了便于推理与书写，常用小写字母表示简单命题或原子命题。,1.1 命题及联结词 简单命题组合成复杂命题时所使用的辅助词称为“联结词”。命题逻辑中的联结词归纳为以下5种。合取：C语言中&and 并且 析取：C语言中|or 或 否定：C语言中!not 非,不是,否定 条件式：C语言中 if()如果那么 如p则q 双条件式：如p则q且如q则p,当且仅当,1.1 命题及联结词 定义1.1合取：当p、q都对，即取值为真(T或1)时，“p合取q”的值为真.,1.1 命题及联结词 定义1.1合取：当p、q都对，即取值为真(T或1)时，“p合取q”的值为真，其他情况为假。,逻辑运算符“合取”，与汉语中“并且、而且、同时”含义相当,1.1 命题及联结词 定义1.2析取：当p、q都不对，即取值为假(F或0)时，“p析取q”的值为假，其他情况为真。,逻辑运算符“析取”，与汉语中“或”含义相当，但有细微的区别,1.1 命题及联结词 逻辑运算符“析取”与汉语的“或”几乎一致但有区别：(16)“讲离散数学的老师是杨老师或刘老师”，可以表示为“讲离散数学的老师是杨老师”“讲离散数学的老师是刘老师”，这两个原子命题有可能都是对的，这种“或”称为“可同时为真的或”，或简称为“可兼或”。(17)“离散数学的教室是102或302”，不可以表示为“离散数学的教室是102”“离散数学的教室是302”，因为这两个原子命题不可能都对，只能这二种情况之一，这种“或”称为“不可同时为真的或”，或简称为“不可兼或”、“排斥或”.这种“或”表示不能简单表示为“析取”，需要联合使用下面将要介绍的“否定”与“析取”符号，才能准确表达。,1.1 命题及联结词 定义1.3否定:当p是1，p的否定p即为0。,逻辑运算符“否定”，与汉语中“否定”含义相当.“我不是数学院的学生”可表示为“我是数学院的学生”“离散数学的教室是102或302”,表示离散数学的教室是102不是302或离散数学的教室是302不是102p:离散数学的教室是102q:离散数学的教室是302上面的语句表示:(pq)(pq),1.1 命题及联结词 定义1.4条件:当p是1,q是0时,pq为0,即10为0,其他情况为1。,逻辑运算符“如果那么”，它是用单个运算符表示一个复合语句。如老妈说：“如果期终考了年级前10名，那么奖励1000元”。p:期终考了年级前10名 q:奖励1000元则上面的语句表示为pq。当p为1即“期终考了年级前10”，且q为0即“没有奖励1000元”这时老妈的话是假话空话，故pq为0,1.1 命题及联结词 定义1.4条件式(蕴含式):当p是1,q是0时,pq为0,即10为0,其他情况为1。p为前件,q为后件,(1)当p为1即“我期终考了年级前10”q为0即“我老妈没有奖励1000元”这时老妈的话为假，即pq为0(2)当p为1即“我期终考了年级前10”q为1即“我老妈奖励1000元”这时妈妈的话就对了，即pq为1(3)至于p为0即“我期终考了年级不是前10”时,无论q为1或为0，即无论我老妈奖励1000元或不奖励，都不能说老妈的话是假的，故可善意的认为pq为1均为1,1.1 命题及联结词 定义1.5双条件:当p与q值相同0时,pq为1,不同为0。称p与q的等价式,“我明年赚了10万当且仅当我买彩票中了大奖”，可以表示为“我明年赚了10万我买彩票中了大奖”,1.2公式及其赋值 对错明确的陈述语句称为命题，其真值确定，又称为命题常元或命题常项，相当于初等数学中的“常数”。数学的运算符号为“加+、减-、乘x、除、幂”，命题逻辑的符号“合取、析取、否定、条件、双条件”数学中用变量x表示某些数，如x2+x+10是代数式，命题逻辑用变量表示任意一个命题，如p,q,r,这时由符号与变量所构成命题表达式，简称为“命题公式”。代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为“合式公式”，也称为“命题公式”，简称为“公式”。,1.2公式及其赋值定义1.2.1 合式公式的生成规则(1)单个命题变元、命题常元为合式公式(原子公式)。(2)若A是合式公式，则A、(A)也是合式公式。(3)若A、B是合式公式，则AB、AB、AB、AB是合式公式。(4)有限次使用(2)(3)形成的字符串均为合式公式。如：(p1)q是合式公式。因为p、1是合公式，则(p1)是合式公式，而r是合式公式，故(p1)q是合式公式。(p1)r不是合式公式。因为p、1是合公式，则(p1)是合式公式，而r是合式公式，但(p1)r不是合法公式。,1.2公式及其赋值 对于代数式x2+y+10，当x与y的值不确定时，该代数式的值是不确定的。对于公式(p1)q，由于p与q值不确定时，公式(p1)q的值不确定，因而不是命题。只有当p与q的值确定后，公式(p1)q的值才能确定，我们可能像表1.2到表1.5一样，给出公式在各种情况下的取值，即得到这个公式的真值表。,p与q每一种取值称为p、q的一种解释,1.2公式及其赋值 公式(pq)、pq的真值表如下表。,真值表的构造方法：(1)命题变元的取值从全0开始，依次加1，直到全1，当有n个变元时，则共有2n种不同的取值情况。(2)分步骤计算公式的值(3)见黑板上写,成真赋值:如pq为(0,0),(0,1),(1,1)成假赋值:如pq为(1,0),1.2公式及其赋值 公式(pq)(qp)、pq的真值表。,无论p/q取何值，这两个公式的值总相等。,1.2公式及其赋值 公式(pq)、p q的真值表。,无论p/q取何值，这两个公式的值总相等。,1.2公式及其赋值 公式pq、pq的真值表。,无论p/q取何值，这两个公式的值总相等。,1,1.2公式及其赋值 公式pq、qp的真值表。,无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题,1,1.2公式及其赋值 公式p(qr)、(pq)(pr)的真值表。,无论p/q取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！,1.3 等值式一、复习 由前节可知：pq与pq、qp pq与(pq)(qp)、(pq)(pq)(pq)与p q p(qr)、(pq)(pr)的真值表完全一样，称为等值。定义 设A、B是两个合法的命题公式，无论其中的命题变元取何值，这两个公式的总相等，称为两个公式等值，记为AB,由定义及前节习题有：(1)pqpqqp条件式的等值式(2)pq(pq)(qp)(pq)(pq)双条件(3)pp 双重否定律(4)ppppp幂等律(5)pq qp，pq qp 交换律(6)p(qr)(pq)r 结合律 p(qr)(pq)r(7)p(qr)(pq)(pr)分配律 p(qr)(pq)(pr)(8)p(pr)p吸收律(多吃少)p(pr)p(9)(pq)pq德摩律(pq)pq 将以上等值式中的变元换成合式公式仍等值！,如：pq pq 则有 AB AB 尽管A/B可能很复杂，但是公式值也只有0、1二种可能，公式A/B的组合只有0/0,0/1,1/0,1/1四种，如下表所示,显然有 AB AB,置换规则：当将公式A中的子公式B换成C得到公式D后，若BC，那么AD。因为A、D除了“A中B所在之处、D中C所在之处”外，其他地方均相同，而不同之处的B与C等值，所以公式A、公式D的真值表应该完全他相同，故AD。当将一个公式的局部进行等值替换后，仍与原公式等值，这也是数学中最常见的方法，不断对局部进行等值替换的操作，称为“等值演算”。利用该规则及前述的等值式，可进行等值演算，从而推导出新的公式。,求证(pq)r(pr)(qr)(pq)r(pq)r 条件式的等值式(pq)r 利用德摩律 r(pq)交换律(rp)(rq)分配律(p r)(qr)交换律(pr)(qr)条件式等值式,等值演算的基本套路(1)转换：ABAB(2)恰当转换：AB(AB)(AB)(AB)(AB)确保公式只保留 联结词(3)否定到底：A,(AB),(AB)(4)恰当使用分配律、吸收律。,利用等值演算，判断公式的类型(pq)p)q(pq)p)q(pq)p)q(条件式的等值式)(pq)p)q(条件式的等值式)(pq)p)q(德摩律)(pq)p)q(德摩律)(pq)(pq)(结合律)(pq)(pq)(逆用德摩律)AA(A=(pq)1 称为永真式或重言式，即利用等值演算，可以判断公式的类型。,利用等值演算判断公式类型：(p(pq)r解：(p(pq)r(p(pq)r(条件式的等值式)(pp)q)r(结合律)(1q)r(析取的性质即析取定义真值表)1r(析取的性质即析取定义真值表)0r(否定的定义)0(析取的性质即析取定义真值表)永假式或矛盾式。问题：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？,1.4 析取范式与合取范式 文字：命题变项(变元)及其否定称为文字.如:p,q,r,p,q,r 简单析取式:仅由有限个文字构成的析取式.如:pq,pq,pq,p q,pqr 简单合取式:仅由有限个文字构成的合取式.如:pq,pq,pq,pq,pqr定理：简单析取式与简单合取式(1)一个简单析取式Ai是重言式 含有某个命题变元及其否定式，如Ai=pp(2)一个简单合取式Ai是矛盾式 含有某个命题变元及其否定式，如Ai=pp,1.4 析取范式与合取范式析取范式：由有限个简单合取式的析取构成的命题公式称为析取范式。总体是析取式，每对括号内是合取式 A=(pq)(pr)合取范式：由有限个简单析取式的合取构成的命题公式称为合取范式。总体是合取式，每对括号内是析取式 A=(pq)(pr),1.4 析取范式与合取范式 总体是析取式，每对括号内是合取式 A=(pq)(pr)析取范式 总体是合取式，每对括号内是析取式 A=(pq)(pr)合取范式定理：析取范式与合取范式(1)一个析取范式A是矛盾式 每个简单合取式是矛盾式。A=(pq)(pr)(2)一个合取范式A是重言式 每个简单析取式是重言式。A=(pq)(pr),1.4 析取范式与合取范式(1)转换：ABAB(2)恰当转换：AB(AB)(AB)(AB)(AB)(3)否定到底：A,(AB),(AB)(4)适当使用分配律：A(BC),A(BC).经过第1步、第2步转换后，公式中只有、三种运算符。经过第3步后，从括号外深入到变元的前面，与变元结合成文文字，文字之间只有、。,1.4 析取范式与合取范式(1)转换：ABAB(2)恰当转换：AB(AB)(AB)(AB)(AB)(3)否定到底：A,(AB),(AB)(4)适当使用分配律：A(BC),A(BC).如果外层运算符全部是，而内层子公式全部是简单析取式，则已经是合取范式。如果内层某子公式形如A(BC)，不是简单析取式，则转换为(AB)(AC)。,1.4 析取范式与合取范式(1)转换：ABAB(2)恰当转换：AB(AB)(AB)(AB)(AB)(3)否定到底：A,(AB),(AB)(4)适当使用分配律：A(BC),A(BC).如果外层运算符全部是，而内层子公式全部是简单合取式，则已经是析取范式。如果内层某子公式形如A(BC)，不是简单合取式，则转换为(AB)(AC)。因此有：(1)不是永假的命题公式，存在析取范式。(2)不是永真的命题公式，存在合取范式。,1.4 析取范式与合取范式(1)转换：ABAB(2)恰当转换：AB(AB)(AB)(AB)(AB)(3)否定到底：A,(AB),(AB)(4)适当使用分配律：A(BC),A(BC).如析取式范式：(pq)r(pq)r(pq)r)(pq)r)(p r)(qr)(pqr),1.4 析取范式与合取范式求(pq)r的析取范式、合取范式解：(1)求析取范式。即外层是，内层是，所以转换模式为AB(AB)(AB)(pq)r(pq)r)(pq)r)(整体为析取)(pq)r)(pq)r)(ABAB)(pq)r)(pq)r)(德摩律)(p r)(qr)(pq)r)(分配律)(p r)(qr)(pq r)(结合律),1.4 析取范式与合取范式解：(1)求合取范式。所以转换模式为AB(AB)(AB)(pq)r(pq)r)(pq)r)(整体为合取)(pq)r)(pq)r)(条件等价式)(pq)r)(pq)r)(德摩律)(pr)(qr)(pq)r)(分配律)(pr)(qr)(pq r)(结合律),1.4 析取范式与合取范式小项：在含有n个变元的简单合取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单合取式为(极)小项。如：pqr,pqr,pqr,pqr(p r),(qr)非小项大项：在含有n个变元的简单析取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单析取式为(极)大项。如：pqr,pqr,pqr,pqr(pr),(qr)非大项,1.4 析取范式与合取范式主析取范式：一个析取范式中，如果所有简单合取式均为(极)小项，则称为主析取范式。(pq)r(p r)(qr)(pqr)不是(pqr)(pqr)(pqr)(pqr)是主析取范式,1.4 析取范式与合取范式主合取范式：一个合取范式中，如果所有简单析取式均为(极)大项，则称为主合取范式。(pq)r(pr)(qr)(pqr)不是(pqr)(pqr)(pqr)(pqr)是主合取范式,1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元，因为pp1，1r1，可在缺少变元的小项中加入形如“pp”的公式。如小项(pr)缺少变元q，加入qq，即prp1rp(qq)r(pqr)(pqr)。,1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元，因为pp1，1r1，可在缺少变元的小项中加入形如“pp”的公式。(pq)r(pr)(qr)(pqr)(p(qq)r)(pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr),1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元，因为pp0，0pp，可在缺少变元的大项中加入形如“pp”的公式。如prp0rp(qq)r(pqr)(pqr),1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元，因为pp0，0pp，可在缺少变元的大项中加入形如“pp”的公式。(pq)r(pr)(qr)(pqr)(p(qq)r)(pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr),1.4 析取范式与合取范式 当一个公式比较复杂时，得到其析取范式、合取范式的演算量比较大，再将简单析取式转换为大项，或简单合取式转换为小项，又需要进一步演算，能否直接基于原公式，不进行等值演算直接得到，或者能按某种统一的方式得到其主析取范式、主合取范式呢？通过真值表可以实现！为此先研究小项与大项的性质。,1.4 析取范式与合取范式 通过真值表可以实现！为此先研究小项与大项的性质，下表是各小项的真值表。,1.3个变元的小项共有8个，它们各不相同。2.从每一行来看，命题变元的每个指派中，只有一个小项的值为1。3.从每一列来看，每个小项仅在一个指派中值为1，其余7种指派中均为0。4.小项值为1(如pqr=1)时，p,q,r均为1，即(p,q,r)=(0,0,0)，取该值为小项编号，如最后一行。,(5)根据小项的编号，可写出小项的具体形式。如小项m101，其编号为101，表示(p,q,r)=(1,0,1)时该小项的值为1，而小项是文字的合取，故小项的各个文字必须为1,则文字只能是p、q、r,故该小项为pqr。规则：1对应变元本身(如p)，0对应其否定(如p)。如m00为pq、m01为pq、m10为pq、m11为pq。很重要！,(1)三个变元的大项共有8个。(2)每一行:每个指派中，只有一个大项的值为0。(3)每一列:每个大项仅在一个指派下值为0。(4)大项值为0(如pqr=0)时，p、q、r均为0，则(p,q,r)=(1,1,1)，将其记为大项编号,如表最后行。,(5)根据大项的编号，可写出大项的具体形式。如大项M101,其编号为101，表示(p,q,r)=(1,0,1)时该大项的值为0，而大项是文字的析取，故各个文字必须为0，文字只能是p、q、r，故该大项为pqr。规则：1对应变元的否定(如p)，0对应变元(如p)如M00为pq,M01为pq,M10为pq,M11为pq。,1.4 析取范式与合取范式获取方法1、先转换析取式或合取式，再合取1或析取0。2、先建立真值表，取出所有成真赋值对应的小项，析取所有小项得主析取范式。小项与成真赋值对应。取出所有成假赋值对应的大项，合取所有大项得主合取范式。大项与成假赋值对应。如用真值表求主范式:(pq)r,pq,pq,(pq)q,p(pq),(pq)r的主析取范式、主合取范式,主析取范式公式值为1的指派对应小项的析取m001 m011 m100 m111 1变元,0变元否定,使小项=1(pqr)(pqr)(pqr)(pqr),(pq)r的主析取范式、主合取范式,主合取式范式公式值为0的指派对应大项的合取 M000 M010 M101 M110 1变元否定0变元,使大项=0(pqr)(pqr)(pqr)(pqr),(pq)r、与其主析取范式、主合取范式的真值完全一样，说明三者互相等值，一般情况下有如下定理：(1)不是永假的命题公式，有等值的主析取范式。(2)不是永真的命题公式，有等值的主合取范式。由于永假没有取值为1的解释，故无相应小项，故没有主析取范式。永真无取值为0的解释,故没有主合取范式.,设计一个电子评分系统，3位专家打分，如果有2位以上专家打分为“通过”，则总成绩为“通过”。,对应的主析取范式值为1的指派对应的小项的析取m011m101m110m111(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2)(x1x2)x3)(x1x2(x3x3)(x1x2)(x1x2)x3)(x1x2)(x1x2)(x1x2)x3)(x1x2)与非或门表示,某公司要从曹、乔、宋、黎、邹5人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件：(1)如果曹去，那么乔也去；(2)黎、邹两人中必有一人去；(3)乔、宋两人中去且仅去一人；(4)宋、黎两人同去或同时不去；(5)若邹去，则曹、乔也同去；解：用小写字母表示：c:曹去，q：乔去 s：宋去 l：黎去 z：邹去时，以上5句话可表示为如下的公式：(cq)、(lz)、(qs)(qs)、(sl)、(z(qc)，5句话同时成立即每句话的值均为1，也即其合取式(cq)(lz)(qs)(qs)(sl)(z(qc)为1,(cq)(lz)(qs)(qs)(sl)(z(qc)(cq)(lz)(qs)(qs)(sl)(sl)(z(qc)(cq)(lz)(z(qc)(qssl)(qssl)(qssl)(qssl)(cq)(lz)(z(qc)(qsl)(qsl)(cq)(lz)(zqsl)(zqsl)(qcsl)(cq)(zqsl)(zqcsl)(czqsl)(zqcsl)因(cq)(lz)(qs)(qs)(sl)(z(qc)为1，故1(czqsl)(zqcsl)，故1(czqsl)或1(zqcsl)故方案一是：曹不去、邹不去、乔不去，宋与黎去。方案二是：曹去、乔去、邹去，宋与黎均不去,在某班班委的选举中，该班的甲、乙、丙学生预言：甲说：王娟为班长、刘强为生活委员；乙说：金鑫为班长、王娟为生活委员；丙说：刘强为班长、王娟为学习委员；结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、刘强、金鑫各任何职？解：p1,q1,r1:表示王娟，刘强，金鑫是班长；p2,q2,r2:分别表示王娟，刘强，金鑫是学习委员；p3,q3,r3:分别表示王娟，刘强，金鑫是生活委员；“每个人说法对一半”将是一个非常复杂的公式(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)，要构造这9个变元的真值表，将需要29=512行，工作量实在太大了，！,参考“真值表”，设计如下的判断表,1.6 推理理论 从已知条件、假设、前提或公理出发，根据推理规则推出结论、定理的过程，称为推理。定义1 设A与C是两个命题公式，若AC为永真式(重言式)，则称C是A的有效结论，或称A可以逻辑推出C，记为AC.由“”的定义可知，当A为假时，AC肯定为真，故只要考虑A为真时C是否为真即可，故有:定义2 设A与C是两个命题公式，若当A为真时C也为真，则称C是A的有效结论，或称A可以逻辑推出C，记为AC。一般情况下，利用定义2去证明要简单些，我们在其他学科中遇到的证明都是基于定义2的。判断AC为永真可用等值演算、真值表等方法,例题 求证：A(AB)B(A(AB)B(A(AB)B(的等值式)(A(AB)B(的等值式)(AA)(AB)B(分配律)(0(AB)B(合取的性质)(AB)B(析取的性质)(AB)B(德摩律)A(BB)(结合律)A1(析取的性质)1(析取的性质)所以(A(AB)B是重言式，真值表也证永真所以A(AB)B。这是有名的“假言推理(modus ponens)”，或“分离原则”,假如我今年进入年级前10名老爸给我买iphone 4;期末考试后我为年级第8名，所以老爸应该给我买iphone4。这是假言推理。A(AB)B 从形式上看，结论B是AB的后件，推导的结果是将后件分离出来，故也称为分离原则。利用假言推理规则或分离规则，结合析取、合取、否定的定义，只要不歉麻烦，几乎可推出所有的结论。为了提高推理效率，还需要学习、掌握某些推理规则。,例题 求证 AAB 采用定义1来证明，即证明AAB为永真式。AABA(AB)(的等值式)(AA)B(结合律)1B(析取的性质)1(析取的性质)所以AAB,例题 求证 ABA ABA(AB)A(的等值式)(AB)A(德摩律)ABA(结合律)1B(析取的性质)1(析取的性质)类似 ABB 根据的定义可知AB为真时，A与B均为真，因此由推理定义2可知 ABA，AB B。同样由的定义可知A为真时 AB为真，故由推理定义2可知AAB。然这3个推理式不必记忆！推理定义2效率较高,例题 求证(AB)(BC)(AC)根据定义1，要证明下式为永真式。(AB)(BC)(AC)(AB)(BC)(AC)(的等值式)(AB)(BC)(AC)(的等值式)(AB)(BC)(AC)(德摩律)(A B)(A C)(B B)(BC)(AC)(分配律)(A B)(A C)1(BC)(AC)(析取的性质)(A B)(A C)(BC)(AC)(析取的性质)(A BAC)(A CAC)(BCAC)(分配律)(1 BC)(1 CC)(BA1)(析取的性质)111(析取的性质)1(析取的性质)判断公式的类型，除等值演算外，还有真值表与范式等方法。,例题 求证(AB)(BC)(AC),由上表可知，(AB)(BC)(AC)为重言式，由定义1可知(AB)(BC)(AC)。这是有名的传递律，要记住呀！,例题 求证(AB)(CD)(AC)BD 利用定义1证明了假言推理规则(AB)AB,传递规则(AB)(BC)(AC)。有了这2条规则后,可用定义2来证明推理式了。由于这2条规则的结论中没有析取式，只有条件式，因此将题中结论转换为 BD,题设中转换为(1)(AB)(CD)(AC)为真前提条件(定义2的套路)(2)(AB)为真(1)及合取的性质(3)(CD)为真(1)及合取的性质(4)(AC)为真(1)及合取的性质(5)(BA)为真(2)及(AB)(BA)(6)(AC)为真(4)及(AC)(AC)(7)(BC)为真(5)、(6)及推理传递律(8)(BD)为真(7)、(3)及推理传递律(9)BD为真(8)及(BD)BD,例题 求证(AB)(CD)(BD)AC 可用传递律来证明，还有更高效的方法 由定义1只要证(AB)(CD)(BD)(AC)为重言式，而(AB)(CD)(BD)(AC)(AB)(CD)(BD)(AC)(AB)(CD)(BD)A)C)(AB)(CD)(BD)A)C)(AB)(CD)(BD)A)C故只需证(AB)(CD)(BD)A)C为重言式即只需证明(AB)(CD)(BD)AC A从结论中挪到前提中，这种技巧称为附加条件(CP)法，适合于结论为条件式的情形。,例题 求证(AB)(CD)(BD)AC(1)(AB)(CD)(BD)A为真 CP规则及前提(2)AB为真(1)及合取的性质(3)A为真(1)及合取的性质(4)B为真(2)(3)及假言推理式(AB)AB(5)BD为真(1)及合取的性质(6)BD为真(5)及BDBD(7)D为真(4)(6)及假言推理式(BD)BD(8)CD为真(1)及合取的性质(9)DC为真(8)及原命题逆否命题(10)C为真(7)(9)假言推理式(DC)DC提示：熟练后可不写(1)式，直接引用(2)(3)(5)(8)！,例题 求证(AB)(CD)(BD)AC(1)AB为真前提条件(2)A为真附加前提(3)B为真(1)(2)及假言推理式(AB)AB(4)BD为真前提条件(5)BD为真(4)及BDBD(6)D为真(3)(5)及假言推理式(BD)BD(7)CD为真前提条件(8)DC为真(7)及原命题逆否命题(9)C为真(6)(8)假言推理式(DC)DC,求证(WR)V,V(CS),SU,C,UW 提示：此处用逗号简写前述各例中的合取式，从而鼓励大家直接引用前提。利用假言推理、传递律及前面所学的等值式，可以推出结论。在黑板上演示一番 考虑到本题的结论是W，可采用反证法。根据定义2可知“当前提为真时结论也为真”，反证法是“前提为真时，假设结论不为真即结论的否定为真”。即基于前提、结论否定进行推理。如果推出了一个矛盾的结论出来，则说明“假设结论不为真”是错误的，即表示结论只能为真了,求证(WR)V,V(CS),SU,C,UW(1)W为真假设结论W为0即 W为1(真)(2)W为真(1)与否定的性质(3)(WR)为真(2)与析取的性质(4)(WR)V为真前提条件(5)V为真(4)(3)假言推理(WR)V)(WR)V(6)V(CS)为真前提条件(7)(CS)为真(5)(6)假言推理(V(CS)V(CS)(8)CS为真(7)与条件式的等值式CSCS(9)C为真前提条件(10)S为真(8)(9)与假言推理(CS)(C)S(11)SU为真前提条件(12)U为真(10)(11)假言推理(SU)SU(13)U为真前提条件显然(12)与(13)矛盾，故假设有误！,应用题 天气情况要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回来后不做饭，结论是：如果我已做饭那么肯定天下雨了。解：用M表示天晴，R表示天下雨，C表示爬山，F表示做饭，则问题可表示为 MR，MC，CFFR(MR)(MR)，MC，CFFR,应用题MR，MC，CFFR(1)F为真附件前提(2)CF为真前提条件(3)FC为真(2)的等值式(4)FC为真(3)的等值式(5)C为真(1)(4)的假言推理(6)MC为真前提条件(7)CM为真(6)的等值式(8)M为真(5)(7)的假言推理(9)MR为真前提条件(10)MR为真(9)的等值式(11)R为真(8)(10)的假言推理,应用题MR，MC，CFFR(1)F为真附件前提(2)CF为真前提条件(3)FC为真(2)的等值式(4)FC为真(3)的等值式(5)C为真(1)(4)的假言推理(6)MC为真前提条件(7)CM为真(6)的等值式(8)M为真(5)(7)的假言推理(9)(MR)(MR)为真前提条件(10)(MR)(MR)为真(9)的等值式(11)MR(MR)为真(10)的等值式(12)MR为真(8)与析取的定义(13)(MR)为真(11)(12)的假言推理(14)R为真(13)与合取的定义,定义2证明推理式的规律(1)利用“条件等值式”，尽可能将前提、中间结论及最终结论中的“析取式”转换为“条件式”，以便可引用假言推理、传递律。(2)如果结论为条件式，则将条件式的前件做为附加前提。CP原则(3)如果结论的否定在前提中多次出现，可采 用反证法。(4)每一步的推理理由可简化，如“前提条件”简写为“P”，“假言推理”可简写“M”，等值式只写“等值”或简写“E”。(5)这种从前提出发，应用已证明的推理式，不断推出中间结论，最后推出结论的方式，称为自然推理，这是最常见的方式。,1.7消解规则 证明(AC)(BC)AB(1)(AC)为真前提条件(2)A C为真与(1)等值(3)BC为真前提条件(4)C B为真与(3)等值(5)CB为真与(4)等值(6)AB为真(2)(5)传递律(7)AB为真与(6)等值 因此当(AC)(BC)为真时，AB为真。由于(AC(BC)中互补的公式C、C同时消失了，称“AB”为“(AC)，(BC)”的消解式。因此在采用定义2进行推理时，只要(AC)、(BC)同时为真，则可直接写出AB为真，从而节省大量的中间环节，提高了证明效率。,1.7消解规则 例题(AB)(CD)(BD)AC 利用条件式的等值式，则此题等价于证明(AB)(CD)(BD)AC(1)(AB)为真前提条件(2)(BD)为真前提条件(3)AD为真 当(1)(2)为真消解式AD为真(4)CD为真前提条件(5)AC为真当(3)(4)为真消解式AC为真 采用假言推理原则时，尽可能将析取转换为条件式。采用消解法时，尽可能将条件式转换为析取。消解法是一种高效的方法。消解法可完成1.6节中所有推理式,1.7消解规则 采用定传递律证明了(AC)(BC)AB 因AB AB,故可用假言推理及CP原则证明(1)A为真附加前提(2)(AC)为真前提条件(3)A C为真与(1)等值(4)C为真(1)(3)假言推理(5)B C 为真前提条件(6)CB为真与(4)等值(7)B为真(4)(6)假言推理 用假言推理证明了消解规则，反过来用消解规则可证明假言推理,1.7消解规则 用假言推理证明了消解规则证明了(AC)(BC)AB 反过来，用消解规则可证明假言推理 A(AB)BAB为真前提条件A B为真与(1)等值A为真前提条件B为真(2)(3)消解得到“假言推理”与“消解规则”可以互相推出，因此一方推出的结论另一方也可以推出 因此习题三可由消解规则推导出来呀,