本頁使用了標題或全文手工轉換

規範形式 (布林代數)

維基百科,自由的百科全書
跳至導覽 跳至搜尋

布林代數中,由標準邏輯運算子組成的布林函數可以按利用了對偶性「極小項」和「極大項」的概念的規範形式來表達。

極小項[編輯]

我們首先開始於定義極小項(minterm)為只由邏輯與和補運算子組成的 n 個變數的邏輯運算式。

例如,下列是極小項的例子:

a b'c
a' b c

n 個變數有 2n 個極小項 - 這是因為在極小項運算式中一個變數要麼是自身要麼是它的補的形式 - n 個變數每個都有兩種選擇。

索引極小項[編輯]

一般的,你可以指派給每個極小項(確保以同樣的次序寫變數,通常按字母序),基於極小項的二進制值的一個索引。一個補項a' 被當作二進制的 0,而一個非補項如 a 被當作二進制 1。例如,你可以對 a b c'(1102) 關聯上數字 6,並把極小項運算式寫為 m6。所以三個變數的 m0a'b'c'(0002),而 m7a b c(1112)。

函數等價[編輯]

明顯的,極小項 n 對這個邏輯函數的第 n+1 個唯一的函數輸入給出真值。例如,極小項 5,a b' c,只在 ac 都為真而 b 為假的時候是真的 - 輸入為 a = 1, b = 0, c = 1 得到 1。

如果你給出一個邏輯函數的真值表,就可以把這個函數寫為"積之和"(由極小項OR起來的序列)。這是析取範式的特殊形式。例如,如果給出真值表

a b  f(a, b)
0 0  1
0 1  0
1 0  1
1 1  0

觀察到輸出為 1 的行是第一行和第三行,所以我們可以把 f 寫為極小項 m0m2 的和。

如果我們要驗證它:

f(a,b) = m0 + m2 = (a'b')+(ab')

通過直接計算,結果和這個函數的真值表是一樣的。

極大項[編輯]

極大項是極小項想法的對偶。不再使用 AND 和補運算,我們轉而使用 OR 和補運算,處理是類似的。

例如,下面是極大項的例子:

a+b'+c
a'+b+c

n 個變數也有 2n 個極大項 - 這是因為在極大項運算式中一個變數要麼是自身要麼是它的補的形式 - n 個變數每個都有兩種選擇。

索引極大項[編輯]

索引極大項是同極小項相反的方式完成的。你可以指派給每個最大項(確保以同樣的次序寫變數,通常按字母序),基於項的補的次序的一個索引,例如,對 a'+b'+c 關聯上數字 6,而寫為 M6。所以三個變數的 M0 現在是 a+b+cM7a'+b'+c'.

對偶化[編輯]

可以輕易的使用德·摩根定律驗證,極小項的補是各自補的極大項。例如

m2' = M2
(a+b')'= a'b

函數等價[編輯]

明顯的,極大項 n 現在對這個邏輯函數的第 n+1 個唯一的函數輸入給出值。例如,極大項 5,a'+b+c',只在 ac 都為真而 b 為假的時候是假的 - 輸入為 a = 1, b = 0, c = 1 得到 0。

如果你給出一個邏輯函數的真值表,就可以把這個函數寫為"和之積" (由極大項AND起來的序列)。它是合取範式的特殊形式。例如,如果給出真值表

a b  f(a, b)
0 0  1
0 1  0
1 0  1
1 1  0

觀察到輸出為 0 的行是第二行和第四行,所以我們可以把 f 寫為極大項 M1M3 的積。

如果我們要驗證它:

f(a,b) = M1 M3 = (a+b')(a'+b')

通過直接計算,結果和這個函數的真值表是一樣的。

結果總結[編輯]

所以邏輯函數都可以用規範形式表達,要麼是"極小項之和"要麼是"極大項之積"的形式。除了可以用直接和簡單的代數形式表達複雜的邏輯函數之外,它還允許把這些函數強力分析成最簡化的形式,這對於數字電路的最小化是非常重要的。

參見[編輯]