11.5聯(lián)結(jié)詞全功能集

聯(lián)結(jié)詞全功能集與非聯(lián)結(jié)詞,或非聯(lián)結(jié)詞2聯(lián)結(jié)詞的全功能集定義

設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n

1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞全功能集.根據(jù)定義，若S是聯(lián)結(jié)詞全功能集，則任何命題公式都可用S中的聯(lián)結(jié)詞表示.

設(shè)S1,S2是兩個聯(lián)結(jié)詞集合，且S1

S2.若S1是全功能集，則S2也是全功能集.

反之，若S2不是全功能集，則S1也不是全功能集.32元真值函數(shù)對應(yīng)的真值表pq0001101100000000000011110011001101010101

pq0001101111111111000011110011001101010101

4聯(lián)結(jié)詞全功能集實例定理{

,∧,∨}、{

,∧}、{

,∨}、{

,→}都是聯(lián)結(jié)詞全功能集.證明每一個真值函數(shù)都可以用一個主析取范式表示,故{

,∧,∨}是聯(lián)結(jié)詞全功能集.p∨q

(

p∧

q)，故{

,∧}是全功能集.

p∧q

(

p∨

q)，故{

,∨}是全功能集.p→q

p∨q,故{

,→}也是全功能集.5復(fù)合聯(lián)結(jié)詞

與非式:p

q(p

q)或非式:p

q(p

q)

和

與

,∧,∨有下述關(guān)系:

p

(p∧p)

p

pp∧q

(p∧q)

(p

q)

(p

q)

(p

q)p∨q

(

p∧

q)

(

p)

(

q)

(p

p)

(q

q)6

p

p

pp∧q

(p

p)

(q

q)p∨q

(p

q)

(p

q)定理{

},{

}是聯(lián)結(jié)詞全功能集.可以證明:{∧,∨}不是全功能集,從而{∧},{∨}也不是全功能集.復(fù)合聯(lián)結(jié)詞(續(xù))

7例例

將公式p∧

q化成只含下列各聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的等值的公式.(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.81.6組合電路組合電路邏輯門與門,或門,非門,與非門,或非門奎因-莫可拉斯基方法組合電路邏輯門:實現(xiàn)邏輯運算的電子元件.與門,或門,非門.組合電路:實現(xiàn)命題公式的由電子元件組成的電路.9與門或門非門xx∧yx∨y

xyxyx組合電路的例子10(x∨y)∧

x的組合電路xyxyx第一種畫法第二種畫法例樓梯的燈由上下2個開關(guān)控制,要求按動任何一個開關(guān)都能打開或關(guān)閉燈.試設(shè)計一個這樣的線路.解：以

x,y表示開關(guān)的狀態(tài),F為燈的狀態(tài),

打開為1,關(guān)閉為0.不妨設(shè)開始時，2個開關(guān)都為0，而燈也是打開的.

之后的變化如右表

F=m0∨m3=(

x∧

y)∨(x∧y)11例(續(xù))12為應(yīng)用問題設(shè)計組合電路步驟:1.構(gòu)造輸入輸出表(問題的真值函數(shù)),2.寫出主析取范式,3.化簡.

——最簡展開式:包含最少運算的公式例

當(dāng)且僅當(dāng)

x=y=z=1或

x=y=1且

z=0時輸出1.F=m6∨m7=(x∧y∧

z)∨(x∧y∧z)4個與門,1個或門和一個非門F

x∧y

一個與門13奎因-莫可拉斯基方法1.合并簡單合取式，生成所有可能出現(xiàn)在最簡展開式中的項.2.確定最簡展開式中的項.14例

求下述公式的最簡展開式:

F=(

x1∧

x2∧

x3∧x4)∨(

x1∧

x2∧x3∧x4)∨(

x1∧x2∧

x3∧x4)∨(

x1∧x2∧x3∧x4)∨(x1∧

x2∧x3∧

x4)∨(x1∧

x2∧x3∧x4)∨(x1∧x2∧x3∧

x4)例(續(xù))解15編號

極小項

角碼

標(biāo)記1x1∧x2∧x3∧

x4

1110*2x1∧

x2∧x3∧x41011*3

x1∧x2∧x3∧x40111*4x1∧

x2∧x3∧

x41010*5

x1∧x2∧

x3∧x40101*6

x1∧

x2∧x3∧x40011*7

x1∧

x2∧

x3∧x40001*例(續(xù))標(biāo)記*表示該項已被合并16第一批

第二批合并項

項

表示串

標(biāo)記

合并項

項

表示串(1,4)x1∧x3∧

x41

10(3,5,6,7)

x1∧x40

1(2,4)x1∧

x2∧x3101

(2,6)

x2∧x3∧x4

011(3,5)

x1∧x2∧x401

1*(3,6)

x1∧x3∧x40

11*(5,7)

x1∧

x3∧x40

01*(6,7)

x1∧

x2∧x400

1*例(續(xù))選擇(1,4),(2,4)和(3,5,6,7),或者(1,4),(2,6)和(3,5,6,7).最簡展開式為F

(x1∧x3∧

x4)∨(x1∧

x2∧x3)∨(

x1∧x4)或F

(x1∧x3∧

x4)∨(

x2∧x3∧x4)∨(

x1∧x4)17項覆蓋