本文關(guān)鍵詞：數(shù)字邏輯，由筆耕文化傳播整理發(fā)布。

u013795675

數(shù)字邏輯中的最小完全集

發(fā)表于2015/3/20 2:05:13  867人閱讀

分類： 數(shù)字邏輯電路topics

邏輯門

這里只研究單輸入單輸出、二輸入單輸出的邏輯門。
單輸入的邏輯門是非門（恒等的情況不考慮），真值表為

A B

0 1

1 0

邏輯門的類型，參見(jiàn)下表

A B C

0 0

0 1

1 0

1 1

任一種的組合都構(gòu)成一種邏輯門，所以理論上共有16個(gè)邏輯門（邏輯函數(shù)）。但是經(jīng)常提到的只有與門（AND）、或門(OR)、與非門(NAND)、或非門(NOR)、同或門(XNOR)、異或門(XOR)等。它們的真值表分別是

與門

A B C

0 0 0

0 1 0

1 0 0

1 1 1

或門

A B C

0 0 0

0 1 1

1 0 1

1 1 1

與非門

A B C

0 0 1

0 1 1

1 0 1

1 1 0

或非門

A B C

0 0 1

0 1 0

1 0 0

1 1 0

同或門

A B C

0 0 1

0 1 0

1 0 0

1 1 1

異或門

A B C

0 0 0

0 1 1

1 0 1

1 1 0

通常只提到它們的原因是，這些邏輯門滿足交換律，即AB=BA，或者說(shuō)AB不可區(qū)分，表現(xiàn)在真值表上就是中間兩行的輸出值相等。

這樣滿足交換律的門還有兩個(gè)，即輸出全為0和輸出全為1的，是無(wú)意義或者說(shuō)是平凡的。所以說(shuō)，以上六個(gè)邏輯門是所有的非平凡的對(duì)稱邏輯門。除此之外，還有8個(gè)不滿足對(duì)稱性的邏輯門。

完全集

能夠?qū)崿F(xiàn)任何邏輯函數(shù)的邏輯門類型的集合，被稱為邏輯門的完全集。

完全集的一個(gè)常見(jiàn)的例子是與門、或門、非門。但是這樣的概念并不精煉，數(shù)學(xué)上我們還要求完全集具有最少的元素，，即滿足
1. 任一個(gè)邏輯函數(shù)，都可以集合中的邏輯門實(shí)現(xiàn)，即完備性；
2. 集合中的一個(gè)元素不能被集合中其他元素實(shí)現(xiàn)，即獨(dú)立性。
我們稱這樣的集合為最小完全集。
事實(shí)上我們馬上會(huì)知道，{與門，或門，非門}并不是一個(gè)最小完全集。

那么哪些邏輯門可以構(gòu)成最小完全集呢？

我們提出以下命題：

與非門（或非門）一種可以構(gòu)成完全集

與非門證明：

已知{與門，或門，非門}是完全集，所以與單獨(dú)一種與非門可以實(shí)現(xiàn)所有邏輯函數(shù)，構(gòu)成一個(gè)單元素的完全集（當(dāng)然也就是最小完全集）。

圖示：
blabla

或者考慮代數(shù)的表示

1.
2. NAND
3.

或非門證明：

同或門（異或門）一種不能構(gòu)成完全集 證法一 數(shù)論方法

異或門不能構(gòu)成完全集。

僅用異或邏輯可以實(shí)現(xiàn)的所有邏輯函數(shù)可以表示成若干個(gè)

如果異或門可以構(gòu)成完全集，那么可以實(shí)現(xiàn)與邏輯。按照與邏輯的真值表

X Y F

0 0 0

0 1 0

1 0 0

1 1 1

得

矛盾。所以異或門不能單獨(dú)構(gòu)成完全集。
2. 同或門和異或門的等價(jià)性。
異或門串聯(lián)一個(gè)非門即得同或門，而非門可以用異或門實(shí)現(xiàn)，方法是異或門的一端接高電平。

因此同或門和異或門都不可以單獨(dú)構(gòu)成完全集。

補(bǔ)充：
證明同或門不可行也可以用代數(shù)方法直接證明，而不必通過(guò)兩步轉(zhuǎn)換。

僅用同或邏輯可以實(shí)現(xiàn)的所有邏輯函數(shù)可以表示成若干個(gè)

如果同或門可以構(gòu)成完全集，那么可以實(shí)現(xiàn)與邏輯。按照與邏輯的真值表，得到

矛盾。
所以同或門不能單獨(dú)構(gòu)成完全集。

證法二 群論方法

同或滿足交換律和結(jié)合律。


任一個(gè)邏輯函數(shù)可以表示成若干個(gè)X,Y,1,0的異或運(yùn)算的和，根據(jù)交換律和結(jié)合律，可以得到

同或的性質(zhì)是，根據(jù)奇偶性有四種情況，組合起來(lái)一共有8種情況

01組合 A B F

1 2m 2n 1

1 2m 2n+1 B`1

1 2m+1 2n A

1 2m+1 2n+1 AB

0 2m 2n 0

0 2m 2n+1 B’

0 2m+1 2n A’

0 2m+1 2n+1 (AB)’

上面這8行，每行代表一個(gè)邏輯函數(shù)，所以單獨(dú)的同或門只能實(shí)現(xiàn)著8種邏輯函數(shù)，不能構(gòu)成完全集。

證法三 窮舉法

窮舉的判據(jù)仍然是：如果只用這一種（同或）邏輯可以實(shí)現(xiàn)所有的邏輯函數(shù)，那么它就是完全集。

用真值表來(lái)表述：如果只用這一種（同或）邏輯可以得到所有16種真值表，那么它就是完全集。僅用同或門可以實(shí)現(xiàn)的所有邏輯函數(shù)可以用若干個(gè)A,B,0,1進(jìn)行異或運(yùn)算得到。

給A,B,0,1分別編碼為，它們中的每?jī)蓚�(gè)運(yùn)算，就是相應(yīng)的兩個(gè)編碼按位進(jìn)行運(yùn)算，運(yùn)算的結(jié)果也是一個(gè)四位編碼，對(duì)應(yīng)一個(gè)邏輯函數(shù)。對(duì)這個(gè)碼字的運(yùn)算的組合、順序和次數(shù)進(jìn)行窮舉，如果可以得到16個(gè)不同的碼字，那么就證明了同或門可以構(gòu)成完全集，反之不可以。

窮舉的過(guò)程用計(jì)算機(jī)來(lái)實(shí)現(xiàn)，因?yàn)檫\(yùn)算次數(shù)雖然有限，還是挺繁瑣的。貼一段python代碼實(shí)現(xiàn)：

: r="" for i in range(len(x)): if x[i]==y[i]: r+='1' else: r+='0' return r stas=['0101','0011','0000','1111'] con=True while con: con=False for sta in stas: for stb in stas: newSt=Xnor(sta,stb) if not newSt in stas: stas.append(newSt) print(sta+' '+stb+' '+newSt) con=True print(len(stas),stas)

輸出結(jié)果：

['0101', '0011', '0000', '1111', '1001', '1010', '1100', '0110'] >>>

這就是在同或邏輯下實(shí)現(xiàn)的8個(gè)邏輯函數(shù)，因?yàn)橥耆笥?6個(gè)輸出結(jié)果，所以同或門不能構(gòu)成完全集。

與門和非門（或門和非門）構(gòu)成最小完全集

因此{(lán)與門，非門}和{或門，非門}構(gòu)成最小完全集。

最小完全集代碼全解

下面考慮用編程的方法，對(duì)完全集做進(jìn)一步的探索。

單獨(dú)構(gòu)成完全集的二輸入邏輯門

有一個(gè)說(shuō)法是，能夠單獨(dú)構(gòu)成完全集的二輸入邏輯門只有與非門和或非門。其實(shí)這個(gè)說(shuō)法的前提是對(duì)稱的邏輯門，也就是以上六種門，當(dāng)然可以這么說(shuō)了。事實(shí)上，不滿足交換律的邏輯門還有四個(gè)也可以單獨(dú)構(gòu)成完全集。

: r="" add1 = door/8 add2 = (door/4)%2 add3 = (door/2)%2 add4 = door%2 for i in range(len(x)): if (x[i]=='0')and(y[i]=='0'): r += str(add1) if (x[i]=='0')and(y[i]=='1'): r += str(add2) if (x[i]=='1')and(y[i]=='0'): r += str(add3) if (x[i]=='1')and(y[i]=='1'): r += str(add4) return r door = 1 for door in range(16): stas=['0101','0011','0000','1111'] #print "*********************" #print 'This door is ',door con=True while con: con=False for sta in stas: for stb in stas: newSt=find_new_element(door,sta,stb) if not newSt in stas: stas.append(newSt) con=(len(stas)==16): print door

輸出結(jié)果

這多出來(lái)的四個(gè)邏輯門的真值表是
1.

A B C

0 0 0

0 1 0

1 0 1

1 1 0

2.

A B C

0 0 0

0 1 1

1 0 0

1 1 0

3.

A B C

0 0 1

0 1 1

1 0 0

1 1 1

4.

A B C

0 0 1

0 1 0

1 0 1

1 1 1

實(shí)際上，這四個(gè)門可以歸結(jié)成一個(gè)，即不滿足交換律，且當(dāng)輸入同為0或同為1時(shí)輸出相同。

由對(duì)稱二輸入邏輯門以及非門中的兩個(gè)構(gòu)成的完全集。 （待續(xù)） 完全集的應(yīng)用 注：

本文內(nèi)容來(lái)自PKU2013級(jí)電子系數(shù)字邏輯電路課程小班討論整理，感謝參與討論的各位同學(xué)、老師和助教。

  本文關(guān)鍵詞：數(shù)字邏輯，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：287201