1、11.5 联结词全功能集 联结词全功能集与非联结词 ,或非联结词2联结词的全功能集定义 设 S是一个联结词集合，如果任何 n(n1) 元真值函数都可以由仅含 S中的联结词构成的公式表示，则称 S是 联结词全功能集 .说明：若 S是联结词全功能集，则任何命题公式都可用 S中的联结词表示 .设 S1, S2是两个联结词集合，且 S1 S2. 若 S1是全功能集，则 S2也是全功能集 . 反之， 若 S2不是全功能集，则 S1也不是全功能集 .3联结词 全功能集 实 例定理 , , 、 , 、 , 、 , 都是联结词 全功能集 .证 明 每一个真 值 函数都可以用一个主析取范式表示, 故 , , 是
2、 联结词 全功能集 .p q(p q)，故 , 是全功能集 .p q(p q)，故 , 是全功能集 .p qp q, 故 , 也是全功能集 .4复合联结词 与非式 : pq(pq)或非式 : pq(pq) 和 与 , , 有下述关系 :p(p p)ppp q( p q)(pq)(pq)(pq)p q(p q)(p)(q)(pp)(qq)5pppp q(pp)(qq)p q(pq)(pq)定理 , 是 联结词 全功能集 .可以 证 明 : , 不是全功能集 , 从而 , 也不是全功能集 .复合联结词 (续 ) 6例例 将公式 p q化成只含下列各 联结词 集中的 联结词 的等 值 的公式 .(1
3、) ， ； (2) ， ； (3) ； (4) .解 (1) p q(p q).(2) p q(p q)(p q).(3) p q p (qq)(p (qq)(p(qq)(p(qq)(p(qq).(4) p q(p q) (p)q(pp)q.作业n 1.10781.6 组 合 电 路n 组合电路n 逻辑门与门 , 或门 , 非门 , 与非门 , 或非门n 奎因 -莫可拉斯基方法组合电路逻辑门 : 实现逻辑 运算 的 电 子元件 .与 门 , 或 门 , 非 门 .组 合 电 路 :实现 命 题 公式 的由 电 子 元件 组 成的 电 路.9与门 或门 非门x x y x y xy xy x组合电路的例子10(x y) x的 组 合 电 路xy xyx第一种画法 第二种画法
