離散數(shù)學(xué)：聯(lián)結(jié)詞全功能集

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

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

設(shè)S是一個(gè)聯(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是兩個(gè)聯(lián)結(jié)詞集合，且S1

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

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

pq0001101111111111000011110011001101010101

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

,∧,∨}、{

,∧}、{

,∨}、{

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

,∧,∨}是聯(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組合電路組合電路邏輯門與門,或門,非門,與非門,或非門奎因-莫可拉斯基方法組合電路邏輯門:實(shí)現(xiàn)邏輯運(yùn)算的電子元件.與門,或門,非門.組合電路:實(shí)現(xiàn)命題公式的由電子元件組成的電路.9與門或門非門xx∧yx∨y

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

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

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

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

之后的變化如右表

F=m0∨m3=(

x∧

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

——最簡(jiǎn)展開式:包含最少運(yùn)算的公式例

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

x=y=z=1或

x=y=1且

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

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

x∧y

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

求下述公式的最簡(jiǎn)展開式:

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編號(hào)

極小項(xiàng)

角碼

標(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)記*表示該項(xiàng)已被合并16第一批

第二批合并項(xiàng)

項(xiàng)

表示串

標(biāo)記

合并項(xiàng)

項(xiàng)

表示串(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).最簡(jiǎn)展開式為F

(x1∧x3∧

x4)∨(x1∧

x2∧x3)∨(

x1∧x4)或F

(x1∧x3∧

x4)∨(

x2∧x3∧x4)∨(

x1∧x4)17項(xiàng)覆蓋