********1.5联结词全功能集联结词全功能集与非联结词,或非联结词*联结词的全功能集定义设S是一个联结词集合，如果任何n(n?1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.根据定义，若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.设S1,S2是两个联结词集合，且S1?S2.若S1是全功能集，则S2也是全功能集.反之，若S2不是全功能集，则S1也不是全功能集.*2元真值函数对应的真值表pq0001101100000000000011110011001101010101pq0001101111111111000011110011001101010101*联结词全功能集实例定理{?,∧,∨}、{?,∧}、{?,∨}、{?,→}都是联结词全功能集.证明每一个真值函数都可以用一个主析取范式表示,故{?,∧,∨}是联结词全功能集.p∨q??(?p∧?q)，故{?,∧}是全功能集.p∧q??(?p∨?q)，故{?,∨}是全功能集.p→q??p∨q,故{?,→}也是全功能集.*复合联结词与非式:p?q??(p?q)或非式:p?q??(p?q)?和?与?,∧,∨有下述关系:?p??(p∧p)?p?pp∧q???(p∧q)??(p?q)?(p?q)?(p?q)p∨q??(?p∧?q)?(?p)?(?q)?(p?p)?(q?q)*?p?p?pp∧q?(p?p)?(q?q)p∨q?(p?q)?(p?q)定理{?},{?}是联结词全功能集.可以证明:{∧,∨}不是全功能集,从而{∧},{∨}也不是全功能集.复合联结词(续)*例例将公式p∧?q化成只含下列各联结词集中的联结词的等值的公式.(1){?，∨}；(2){?，→}；(3){↑}；(4){↓}.解(1)p∧?q??(?p∨q).(2)p∧?q??(?p∨q)??(p→q).(3)p∧?q?p∧(q↑q)??(?(p∧(q↑q)))??(p↑(q↑q))?(p↑(q↑q))↑(p↑(q↑q)).(4)p∧?q??(?p∨q)?(?p)↓q?(p↓p)↓q.*1.6组合电路组合电路逻辑门与门,或门,非门,与非门,或非门奎因-莫可拉斯基方法组合电路逻辑门:实现逻辑运算的电子元件.与门,或门,非门.组合电路:实现命题公式的由电子元件组成的电路.*与门或门非门xx∧yx∨y?xyxyx组合电路的例子*(x∨y)∧?x的组合电路xyxyx第一种画法第二种画法例楼梯的灯由上下2个开关控制,要求按动任何一个开关都能打开或关闭灯.试设计一个这样的线路.解：以x,y表示开关的状态,F为灯的状态, 打开为1,关闭为0.不妨设开始时，2个开关都为0，而灯也是打开的. 之后的变化如右表F=m0∨m3=(?x∧?y)∨(x∧y)*例(续)********