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

第一章 命题逻辑,杨圣洪 yangshenghong8 13007432216,引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分， 但究竟什么是命题？ 如何表示命题？ 如何构造出复杂的命题？ 在本章将讨论这些问题。,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不是102“ p:离散数学的教室是102 q:离散数学的教室是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) 的真值表完全一样，称为等值。 定义1.3.1 设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，即 pr p1r p(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”的公式 。 如 pr p0r p(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为永真式。 AAB A(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)B AB为真 前提条件 A B为真 与(1)等值 A为真 前提条件 B为真 (2)(3)消解得到 “假言推理”与“消解规则”可以互相推出，因此一方推出的结论另一方也可以推出 因此习题三可由消解规则推导出来呀,