离散数学课件：第1章 命题逻辑3

1、11.5 联结词全功能集联结词全功能集 联结词全功能集联结词全功能集与非联结词与非联结词, ,或非联结词或非联结词2联结词的全功能集联结词的全功能集定义定义 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1) 元元真值函数都可以由仅含真值函数都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联结词全功能集联结词全功能集.根据定义，若根据定义，若S是联结词全功能集，则任何命题公是联结词全功能集，则任何命题公式都可用式都可用S中的联结词表示中的联结词表示. 设设S1, S2是两个联结词集合，且是两个联结词集合，且S1 S2. 若若S1是全是全功能集

2、，则功能集，则S2也是全功能集也是全功能集. 反之，反之，若若S2不是全功能不是全功能集，则集，则S1也不是全功能集也不是全功能集.32元真值函数对应的真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFFp q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(15)2(14)2(13)2(12)

3、2(11)2(10)2(9)2(8FFFFFFFF4联结词全功能集联结词全功能集实例实例定理定理 , ,、 , 、 , 、 , 都是都是联结词全功能集联结词全功能集.证明证明 每一个真值函数都可以用一个主析取范式表示每一个真值函数都可以用一个主析取范式表示, 故故 , ,是联结词全功能集是联结词全功能集. pq( p q)，故，故 , 是全功能集是全功能集. pq( p q)，故，故 , 是全功能集是全功能集. pqpq, 故故 , 也是全功能集也是全功能集.5复合联结词复合联结词 与非式与非式: p q(p q)或非式或非式: p q(p q) 和和 与与 , ,有下述关系有下述关系: p(

4、pp)p ppq( pq)(p q)(p q) (p q)pq( p q)( p) ( q)(p p) (q q)6 pp ppq(p p) (q q)pq(p q) (p q)定理定理 , 是联结词全功能集是联结词全功能集.可以证明可以证明: ,不是全功能集不是全功能集, 从而从而, 也也不是全功能集不是全功能集.复合联结词复合联结词( (续续) ) 7例例例例 将公式将公式p q化成只含下列各联结词集中的联结化成只含下列各联结词集中的联结词的等值的公式词的等值的公式. (1) ，；(2) ，；(3) ；(4) .解解 (1) p q( pq).(2) p q( pq)(pq).(3) p

5、q p(qq)( (p(qq) (p(qq)(p(qq)(p(qq).(4) p q( pq) ( p)q(pp)q.81.6 组合电路组合电路n组合电路组合电路n逻辑门逻辑门 与门与门, , 或门或门, , 非门非门, , 与非门与非门, , 或非门或非门n奎因奎因- -莫可拉斯基方法莫可拉斯基方法组合电路组合电路逻辑门逻辑门: : 实现逻辑运算实现逻辑运算的的电子元件电子元件. .与门与门, , 或门或门, , 非门非门. .组合电路组合电路: :实现命题公式实现命题公式的由电子的由电子元件组成的电路元件组成的电路. .9与门与门或门或门非门非门xxyxy xyxyx组合电路的例子组合电路

6、的例子10 (xy) x的组合电路的组合电路xyxyx第一种画法第一种画法第二种画法第二种画法例例楼梯楼梯的的灯由上下灯由上下2个开关控制个开关控制, 要求按动任何一个要求按动任何一个开关都能打开或关闭灯开关都能打开或关闭灯. 试设计一个这样的线路试设计一个这样的线路.解解：以：以 x, y表示表示开关的状态开关的状态, F为为灯的状态灯的状态, 打开为打开为1, 关闭为关闭为0. 不妨设不妨设开始时，开始时，2个开关都个开关都为为0，而，而灯灯也也是打开的是打开的. 之后的变化如右表之后的变化如右表 F=m0 m3= ( x y)(xy)11 x y F(x,y) 0 0 1 0 1 0 1

7、 0 0 1 1 1例例(续续)12x yxxy(xy)( x y)yxy为应用问题设计组合电路为应用问题设计组合电路步骤步骤: 1.构造输入输出表构造输入输出表(问题的问题的真值函数真值函数), 2. 写出主析取范式写出主析取范式, 3. 化简化简.最简展开式最简展开式: 包含最少运算的公式包含最少运算的公式例例 当且仅当当且仅当 x=y=z=1 或或 x=y=1且且 z=0 时输出时输出1. F= m6m7 = (xy z)(xyz) 4个与门个与门,1个或门和一个非门个或门和一个非门 Fxy 一个与门一个与门13奎因奎因-莫可拉斯基方法莫可拉斯基方法1. 合并简单合取式合并简单合取式，生

8、成所有可能出现在最简展开生成所有可能出现在最简展开式式中的项中的项.2. 确定最简展开式中的项确定最简展开式中的项. 14例例 求下述公式的最简展开式求下述公式的最简展开式: F=( x1 x2 x3x4)( x1 x2x3x4) ( x1x2 x3x4)( x1x2x3x4) (x1 x2x3 x4)(x1 x2x3x4) (x1x2x3 x4)例例(续续)解解15编号编号 极小项极小项 角码角码 标记标记 1 x1x2x3 x4 1110 * 2 x1 x2x3x4 1011 * 3 x1x2x3x4 0111 * 4 x1 x2x3 x4 1010 * 5 x1x2 x3x4 0101

9、* 6 x1 x2x3x4 0011 * 7 x1 x2 x3x4 0001 *例例(续续)标记标记*表示该项已被合并表示该项已被合并16 第一批第一批 第二批第二批合并项合并项 项项 表示串表示串 标记标记 合并项合并项 项项 表示串表示串(1,4) x1x3 x4 1 10 (3,5,6,7) x1x4 0 1 (2,4) x1 x2x3 101 (2,6) x2x3x4 011 (3,5) x1x2x4 01 1 * (3,6) x1x3x4 0 11 * (5,7) x1 x3x4 0 01 *(6,7) x1 x2x4 00 1 *例例(续续)选择选择(1,4), (2,4)和和(3,5,6,7), 或者或者(1,4), (2,6)和和(3,5,6,7). 最简展开式为最