第七章 命题逻辑与布尔代数

第七章命题逻辑与布尔代数7.1命题逻辑的基本概念7.1.1命题与真值表定义7.1凡能分辨真、假的语句称命题命题其实就是一种叙述，命题的叙述根据事实的状况，该命题有可能是真或是假，但命题不会同时为真又同时为假.在自然语言中有些语句是能分辨真、假的，有些则不能如：浙江省的省会城市是杭州.第六届世界合唱节在绍兴举行.第八届全国残疾人运动会在杭州圆满闭幕今天是星期日.1+1=2以上的语句能分辨真、假，因此是命题.一般而言，自然语言中的陈述句大都能分辨真、假，因此都是命题.而下面的一些语句如：请不要随地吐痰.明天会下雨吗？一路顺风.以上语句不能分辨真、假，因此不是命题.一般而言，自然语言中的祈使句、感叹句及疑问句等都不是命题.命题主要分两类：①简单命题；②复合命题.简单命题就是这个命题不能再细分成几个子命题的合成.例如：花是红的.天是蓝的.很明显，上面的命题无法再细分成子命题的合成，所以是简单命题.如下面的语句不是简单命题：花是红的，天是蓝的.(2)昨天下雨，地面是湿的.以上命题均可以分解成更为简单的命题：花是红的天是蓝的昨天下雨地面是湿的复合命题就是由简单命题通过联结词所构成的命题一般常用的联结词有否定、与、或者、蕴含和等价，其对应的符号加、A、V、T和f.例如有两个如下的简单命题：q：下雨r：地湿则：qar:下雨且地湿「qvr:不下雨或地湿上述量份额逻辑命题就是典型的复合命题.下面我们来分别介绍一下这五中关联词.否定否定联结词是一元联结词，它的作用对象仅为一个命题.否定联结词作用于一个命题后使该命题出现相反的语意.如有命题：今天下雨，而加上否定关联词后即成为：今天不下雨.在命题逻辑中将此联结词予以符号化，用「P表示命题P的否定命题.并且并且联结词是二元联结词，它的作用对象为两个命题，该联结词作用于两个命题后可将两个命题用“并且”联结于一起.如有命题：“今天我听音乐”和“今天我看电影”，则用联结词“并且”将其联结为：“今天我听音乐并且今天我看电影”.在命题逻辑中可将联结词符号化，PaQ称为P与Q的合取式，而P、Q分别叫此合取式的合取项.或者或者联结词是二元联结词，它的作用对象为两个命题，该联结词作用于两个命题后可将两个命题用“或者”联结于一起如有命题“今天我看书”，“今天我写字”，则联结词“或者”将其联结为“今天我看书或今天我写字”.在命题逻辑中可将联结词符号化，PvQ称为命题P与Q的析取式，而P、Q分别叫此析取式的析取项.蕴含蕴含联结词是二元联结词，它的作用对象为两个命题.该联结词作用于两个命题后可将两个命题用“如果…则…”联结于一起.如有命题：“明天下雨”，“明天取消旅游”，则蕴含联结词将其联结为：“如果明天下雨，则明天取消旅游”.在命题逻辑中可将联结词符号化，PTQ称为命题P与Q的蕴含式，或称P蕴含Q.而P称为PTQ的前件，Q称为PTQ的后件.在自然语言中蕴含式的前件与后件一般具有因果关系.等价等价联结词是二元联结词，它的作用对象为两个命题，该联结词作用于两个命题后可将两个命题用“等价”联结于一起.如命题“5+3=8”，“8-5=3”，等价联结词将其联结为“5+3=8等价于8-5=3”.在命题逻辑中可将联结词符号化，P〜Q称为命题P与Q的等价式，而P、Q分别叫此等价式的两端.当命题q和,均赋真或假值后，我们五个联结词为例，表7.1为这些复合命题的真值表.在表中，1代表该命题为真，0代表该命题为假.表7.1—个真值表的例子qr「qqarqvrqTr「qvrqIr001001110110111010001000110111117.1.2范式我们有自然语言出发归结出命题于命题联结词连个概念，并将其符号化，从而构成初步的符号体系.而这种系统建立的首要步骤是构建形式化的命题公式.定义7.2（命题公式）命题公式（或称命题逻辑合式公式，简称公式）可按如下规则生成：（1）命题变元与命题常元是公式（2）如果P是公式则（-P）是公式（3）如果P，Q是公式，则（PVQ），（PaQ），（PTQ）及（PIQ）是公式（4）公式由且仅由有限次应用（1）、（2）、⑶而得从形式上看，命题公式是由命题变元、命题常元、五个联结词以及圆括号按一定规则所组成的字符串.按照上述定义，下面的字符串是公式：(「(P—Q))(PT(RAQ))((PAQ)T(RAQ))而下面的字符串则不是公式：((「P)「TQ)(PQvR)(PT(AR))为了使表示简单化，在公式中的圆括号是可以省略的，其规则如下：规定五个联结词的结合能力的强弱顺序为：「、A、v、T及I，其中「为最强，—为最弱，在公式中凡符合此顺序者，括号均可省去.具有相同结合能力的联结词，按其出现的先后顺序，先出现者先联结，凡符合此要求者，其括号均可除去.最外层括号可省去.例7.1.1将下面的公式省去括号：「((Pa(「(Q))vR)T((RvP)vR))有了命题公式后可以用它表示自然语言及形式思维的多种形态.下面用一些例子表示.例7.1.2“若明天上午不是雨夹雪，我将去学校”，在此语句中可以令：P:明天上午下雨Q:明天上午下雪R:我去学校此语句可以用命题公式表示如下：「(PAQ)TR例7.1.3“明天我将风雨无阻去学校”，在此语句中可以令：P:明天下雨Q:明天刮风R:我去学校此语句可以用命题公式表示如下：PAQvPA「Qv「PAQv「PA「QTR一般而言，将自然语言转换成为命题公式须经过下列三个步骤：首先找出语句中的简单命题并以命题标识符表示之其次确定命题间的联结词最后用命题公式的定义规则组成一个合式公式.命题公式的形式是多种多样的，这对我们的研究带来诸多不便，为此须建立一种统一的、标准的公式-范式.定义7.3析取范式是范式的一种，它具有如下之形式：析取范式是一个析取式析取式中的每个析取项是一个合取式这个合取式只包含命题变元及命题变元否定.下面的公式都是析取范式：(「PaQ)v(Pa「Q)「Pv(PAQ)v(PAR)任意一个命题公式都可以化归成为析取范式，其化归步骤如下：•用AtB=「AvB和A—■B=(AaB)v(「Aa「B)，将公式中出现的一T及—■之处化归成仅出现有A、v和「•用「(AvB)=「AA「B和「(AAB)=「Av「B将否定符深入至命题变元并使用「「A=A减少否定符号，使命题变元前否定符号最多为一个•由分配律Aa(BvC)=(AaB)v(AaC)Av(BaC)=(AvB)a(AvC)Ar(BrC)=(ArB)r(ArC)将公式最终化归成析取范式.例7.1.4试化归公式TPvQ)I(PaQ)为析取范式.解：按照前面所规定的化归工程：消去联结词r与1:「(PvQ)I(PaQ)=(「(pvQ)a(PaQ))v((PvQ)a「(PaQ))将否定符深入至命题变元：(「(pvQ)a(PaQ))v((PvQ)a「(PaQ))=((「pa「Q)a(PaQ))v((PvQ)a(「Pv「Q))用分配律最后化归成析取范式：((「pa「Q)a(PaQ))v((PvQ)a(「Pv「Q))=(「Pa「QaPaQ)v(Pa「P)v(「PaQ)v(Pa「Q)v(Qv「Q)因此得到析取范式.析取范式是一种标准公式，它具有形式简单、化归方便的特点，但它也有不足，其中最大的缺点是不唯一性与标准性，因此需要在其基础上进一步化归成具有相对唯一性、标准性的公式，这就是主析取范式.定义7.4主析取范式是析取范式的一种，它具有如下具体的形式：主析取范式是一个析取范式在主析取范式的每个析取项中，该公式的所有命题变元均出现，它们或以命题变元或以命题变元否定的形式出现，且仅出现一次.下面的公式都是主析取范式：(「PaQ)v(Pa「Q)(PaQa「R)v(「PaQaR)任意一个命题公式均可以化归为主析取范式，其化归步骤如下：化归为析取范式除去所有为假的析取项，即析取项中出现有Pa「P形式的项析取项中用公式「「A=A将出现有多个相同命题变元(或其否定)化简成仅出现一次析取项中若某些命题元没有出现，则用公式Pa(Qv「Q)=P在析取项中补充，再用分配律将其展开成两个析取项并除去相同析取项例7.1.5试化归公式(Pa(PrQ))vQ为主析取范式.化归为析取范式：(Pa(PrQ))vQ=(Pa「P)v(PaQ)vQ除去假析取项：(Pa「P)v(PaQ)vQ=(PaQ)vQ在析取项中将多个相同命题变元化归成一个：无补充不足命题变元并除去相同析取项：(PaQ)vQ=(paQ)v((Pv「P)aQ)=(PaQ)v(PaQ)v(「PaQ)=(PaQ)v(「PaQ)因此得到主析取范式.与析取范式相对应，我们可以定义合取范式：定义7.5合取范式是范式的一种，它具有如下的形式；合取范式是一个合取式合取式中的每个合取项是一个析取式这个析取式只包含命题变元及命题变元否定下面的公式都是合取范式：(「Pv「P)aQ(「PvQ)a(Pv「Q)任意一个命题都可以化归为合取范式，其化归步骤如下：•用ATB—「AvB和A。^B=(AaB)v(「Aa—B)，将公式中出现的一)及之处化归成仅出现有a、v和—•用「(AvB)—「Aa—B和「(Aab)—「Av—B将否定符深入至命题变兀并使用「「a—A减少否定符号，使命题变元前否定符号最多为一个•由分配律Aa(BvC)=(AaB)v(AaC)Av(BaC)=(AvB)a(AvC)AT(BTC)—(ATB)T(ATC)将公式最终化归成合取范式.例7.1.6试化归公式Qv—(PTQ)v—(PvQ)为合取范式.解：消去联结词Qv「(PTQ)v—(PvQ)—Qv—(—PvQ)v—(PvQ)将否定符号深入Qv「(PTQ)v「(PvQ)—Qv(Pa「Q)v(—Pa「q)用分配律化归成合取范式Qv—(PTQ)v—(PvQ)—(QvPv—P)a(Qv—Q)因此得到合取范式.与析取范式类似，对合取范式可进一步化归成相对唯一性、标准性的公式称主合取范式.定义7.6主合取范式是合取范式的一种，它具有如下之形式：主合取范式是一个合取范式在主合取范式的每个合取项中，该公式的所有命题变元均出现，它们或以命题变元或以其否定的形式出现，且仅出现一次.下面的公式都是主合取范式：(—PvQ)a(PvQ)(—PvQ)任意一个命题公式都可以化归为合取范式，其化归步骤如下：化归为合取范式除去所有为真的合取项，即合取项中出现有Pv—P形式的项合取项中用公式PvP—P将出现多个相同命题变元(或其否定)化简成仅出现一次合取项中若某些命题变元没有出现，则用公式Pv(Qa—Q)=P在合取项中补充，在用分配律将其展开成两个合取项并除去相同的合取项.例7.1.7试化归公式(—PTRvP)a(qIp)为主合取范式.解：(1)化归为合取式：(—PTRvP)a(QIP)=(PvRvP)a(—QvP)a(—PvQ)(2)除去为真的合取式：无(3)消去多余的命题变元：(PvRvP)a(—QvP)a(—PvQ)=(PvR)a(—QvP)a(—PvQ)补充不足的命题变元：(—PTRvP)a(QiP)=(Pv—QvR)a(Pv—Qv—R)a(PvQvR)a(PvQv—R)a(—PvQvR)a(—PvQv—R)因此得到主合取范式.习题7.1下列那些语句是命题？合肥是安徽的省会城市.2+3=5.x+2=11.全体起立.回答这一问题.对每一对实数x、y，都有xyyx.别过去.几点了？2是无理数.令P、Q为如下命题：P：本周我买了一张彩票.Q:星期五我中了百万大奖.把下列各命题表达为汉语句子：(1)P(2)PQ(3)PQ(4)PQ⑸PQ(6)PQ(7)PQ(8)P(PQ)3.写出1下列公式的真值表⑴P(PQ)⑵(PQ)(PR)⑶(PQ)P⑷(PQ)R4.写出第3题中各小题中命题公式的真值表，并写出命题的主析取范式7.2布尔代数计算机和其他电子设备中的电路都有输入和输出，输入是0或1,输出也是0或1.电路可以用任何具有两个不同状态的基本元件来构造，开关和光学装置都是这样的元件.开关可能处于开或关的位置，光学设置可能是点亮或未点亮的1854年，乔治•布尔在《TheLawsofThought》一书中第一次给出了逻辑的基本规则.1938年，克劳德•香农揭示了怎么用逻辑的基本规则来设计电路，这些基本规则形成了布尔代数的基础.7.2.1布尔逻辑布尔代数提供的是集合｛°’｝上的运算和规则，这个集合及布尔代数的规则还可以用来研究电子和光学开关.我们用的最多的三个布尔代数运算是补、布尔和与布尔积.元素的补用上划线加以标记，其定义为：_°1且1=0.布尔和记为+或OR，它的值如下：1+1=1，1+0=10+1=10+0=0.布尔积记为或and，它的值如下：11=1，10=1，01=0，00=0.在不引起混淆时，可以删除“”.除非使用括号，布尔运算的优先级规则是：首先计算所有补，然后是布尔积，—然后是布尔和.例7.2.1计算01+(10)的值.解：根据补、布尔积与布尔和的定义得：_01+(0)=0+1=0+0=0下面定理汇集了布尔代数中常用的基本等式：定理7.1在布尔代数B={{0,1},+,•,一}中下列等式成立：a+b=b+弘加法交换律)，a•b=b•。(乘法交换律)；(a+b)+c=a+(b+c)(加法结合律)，(a•b)•c=a•(b•c)(乘法结合律)；a•(b+c)=a•b+a•c)(乘法对加法的分配律)，a+(b•c)=(a+b)•(a+c)(加法对乘法的分配律)；a+0=a,a•1=a,a+1=a,a•0=0;a+a=a,a•a=a;a=a;(a+b)=a•b,a•b=a+b;a+a=1,a•a=0补、布尔积和布尔和分别对应于逻辑运算「、v和△，且0对应于假，1对应于真.关于布尔代数的结果可以直接翻译成关于命题的结果.相反地，关于命题的结果也能翻译成关于布尔代数的命题.例7.2.2化简逻辑函数F=AB+AB+BC+BC.解：由定理7.1得F=AB(C+C)+AB(C+C)+(A+A)BC+(A+A)BC=ABC+ABC+ABC+ABC+ABC+ABC=ab(c+C)+Ac(B+B)+(A+A)BC=ab+Ac+BC7.2.2开关电路开关是一种具有一个输入和一个输出的器件，我们将若干个开关的串联与并联构成的电路称为开关电路.整个开关电路从功能上可看作是一个开关，把电路接通记为1，把电路断开记为0.而开关电路中的开关也要么处于接通状态，要么处于断开状态，这两种状态也可以用二值布尔代数来描述.一个具有n个独立开关组成的开关电路称为n元开关电路.整个开关电路是否接通完全取决于这些开关的状态以及连接方式(串联、并联或反相)，因而可以这些开关的函数.称这样的函数为开关函数，可以写成一个二值n元布尔式，称为线路的布尔表达式.线路布尔式的构造原则：串联对应布尔式中的积，并联对应布尔和，反相对应布尔补.接通条件相同的线路称为等效线路，两个开关电路是等效的，当且仅当它们对应的开关函数是等价的.找等效线路的目的是化简线路，使线路中包含的接点尽可能地少.利用布尔代数可设计一些具有指定性质的节点线路，数学上即是按给定的真值表构造相应的布尔表达式(最后经过适当的简化)，理论上涉及到范式理论，但形式上并不难构造.这样就可以设计出符合要求的开关电路.例7.2.3在举重比赛中，通常设三名裁判：一名为主裁，另两名为副裁竞赛规则规定运动员每次试举必须获得主裁及至少一名副裁的认可，方算成功裁判员的态度只能同意和不同意两种;运动员的试举也只有成功与失败两种情况.举重问题可用逻辑代数加以描述:用A、B、C三个逻辑变量表示主副三裁判：取值1表示同意（成功），取值0表示不同意（失败）.举重运动员用L表示，取值1表示成功，0表示失败.显然，L由A、B、C决定.L为A、B、C的逻辑函数.列表如下，该表称为逻辑函数L的真值表：表7.2L的真值表A00001111B00110011C01010101L00000111从真值表可看出L取值为1只有三项，A、B、C的取值分别为101、110、和111三种情况L才等于1.A•B•C、A•B•C、A•B•C三项与上述三种取值对应.由于上述三种情况之一出现就可判定L成功，故L=(A•B•C)+(A•B•C)+(A•B•C)=(A•B•C)+(A•B•C)+(A•B•C)+(A•B•C)=(A•C)+(A•B)=A•(C+B)图7.1裁判开关电路图根据上述布尔式来设计就可以得到举重裁判的控制电路.其中K1由主裁控制，K2和气分别由两个副裁控制.1237.2.3门电路门电路是实现各种逻辑关系的基本电路，是组成数字电路的最基本单元从逻辑功能上看，有与门、或门和非门，还有由它们复合而成的与非门、或非门、与或非门、异或门等从生产工艺上看，门电路又可分为两大类：分立元件门电路和应用集成电路工艺制成的集成门电路.在学习这些逻辑电路时，不必考虑它的内部结构原理，而要着重掌握它们的逻辑功能.一、与门如图，两个开关A、B串联起来控制同一个灯泡L.显然，只有A“与”B同时闭合时，灯L才会亮.在这个事件中，A、B闭合是条件，灯L亮是结果.

图7.2“与”逻辑电路如果一个事件的几个条件都满足后，该事件才能发生，这种关系叫做“与”逻辑关系如开关断开和灯不亮均用0表示，而开关闭合和灯亮用1表示，则可得表表7.3真值表ABL000010100111能实现与运算的逻辑电路称为与门，其逻辑符号如图7.3所示B——图7.3与门逻辑符号图中A、B表示输入变量，Y表示输出变量.与门的输入变量为两个或两个以上.二、或门如下图，两个开关A、B并联，控制同一个灯泡Y.在这个电路中，A“或”B只要有一个开关闭合，灯Y就会亮.图7.4“或”逻辑电路像这样的情况：如果几个条件中，只要有一个条件得到满足，某事件就会发生，这种关系叫做“或”逻辑关系.具有“或”逻辑关系的电路称为“或”门电路，简称“或”门.或运算的功能表和真值表如表7.4功能表条件结果开关A开关B灯泡L断断熄断通亮通断亮通通亮表7.5真值表101—1I1I1或门逻辑符号如图7.5所示;二一Y图7.5“或”门逻辑符号图中A、B表示输入变量，Y表示输出变量.或门的输入变量为两个或两个以上.三、非门如下图，在这个电路中，当A闭合，灯Y就会熄灭，当A断开，灯Y就会亮.图7.6“非”逻辑电路像这样输出状态和输入状态相反的逻辑关系，叫做“非”逻辑关系，具有“非”逻辑关系的电路叫做“非”门.非运算的功能表和真值表如表7.6功能表条件结果开关A灯泡Y断亮通熄表7.7真值表条件结果AY0110非门逻辑符号如图7.8所示图7.8“非”门的符号图中A、B表示输入变量，Y表示输出变量.例7.2.4求给定逻辑函数F=AB+AC+BC的相应门电路解：注意到逻辑函数先非门，再与门，后或门的顺序，考虑到多输入、单输出的结果，可得到如图7.9所示的门电路.图7.97.2.4卡诺图一、逻辑函数的最小项对于表达式Y=ABC+ABC+ABC中，每一个乘积项（与项）都是标准形式，这种标准形式的与项为最小项，因此上式被称为标准与或式，也叫最小项表达式.在式中，ABC.ABC、ABC三个乘积的共同特点是：（1）每个与项包含该逻辑函数的全部输入变量；（2）每个变量均以原变量或反变量的形式在乘积项中出现且只出现一次将满足上述特点的与项称为逻辑函数的最小项.n个输入变量的逻辑函数共有2〃个最小项，为了书写方便，对最小项采用编号的形式编号的方法是：（1）将最小项中的原变量当做1，反变量当做0，则得到一组对应的二进制数；（2）将二进制数转换为十进制数；（3）该十进制数就是最小项对应的编号，记作m..例如，三变量最小项~ABC对应的二进制数为010，相应的十进制数为2,所以ABC记作m2，即m2=ABC.二、卡诺图的画法卡诺图是由美国工程师卡诺首先提出的一种利用利用表格作图化简逻辑表达式的方法它是将逻辑函数的最小项按一定的规律排列而成的方格矩阵，每个小方格对应一个最小项，因此，卡诺图又叫最小项方格图.画卡诺图的具体步骤如下：（1）n个输入变量的逻辑函数画出2〃个小方格，每个小方格对应一个最小项.（2）各变量的取值符合几何相邻和逻辑相邻重合的原则，即变量的取值按循环码（也叫格雷码）的顺序排列几何相邻：卡诺图中的几何位置上下左右相接的最小项.每一行或每一列两端的最小项也具有几何相邻性，故卡诺图可看成一个上下、左右对折的立体图形的展开形式逻辑相邻：只有一个变量互为反变量，其余变量均为相同的两个最小项叫作在逻辑上是相邻的.如三变量ABC和ABC中只有B和万不同，其余变量相同，所以ABC和ABC是逻辑相邻的最小项.变量、三变量和四变量卡诺图如图7.10-7.12所示.BCBCBCBC00011110ABCABCAbc~AbcaBCABCABCABCAm0m1BCBCBCBC00011110ABCABCAbc~AbcaBCABCABCABCAm0m1m3m2mmmm4576图7.11三变量的卡诺图ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDCDCDABABABABCDCD013245761213151489111000011110三变量的卡诺图图7.12三变量的卡诺图三、逻辑函数的卡诺图表示法采用卡诺图化简逻辑函数时，必须先画出逻辑函数对应的卡诺图.常用的方法有2种:1）真值表法将真值表中每组输入变量的取值组合所对应的函数值填入卡诺图相应的小方格中，即函数值为1的最小项所对应的小方格中填1，函数值为0的最小项所对应的小方格中填0.例7.2.5画出表对应的卡诺图表7.8真值表ABCY00000011010001111000101111001111解：表中所描述的是3变量的逻辑函数.画出3变量的卡诺图填写卡诺图.将表中对应变量取值组合001、011、101、111的函数值为1，故在卡诺图总相应的小方格内填1，其余的小方格填0.如图7.13所示\BC注、、0001111000100111图7.132)由一般与或式画逻辑函数卡诺图法首先画出输入变量对应的卡诺图，然后根据表达式中与项的特征将最小项填入卡诺图，具体如下：与项中的原变量用1表示，非变量用0表示，与项中的变量在卡诺图中横向和纵向相交的小方格便为所求的最小项，填入1，其余的小方格填0.例7.2.6画出逻辑函数Y=ACD+BCD+AB对应的卡诺图.解：表达式中与项ACD对应的