卡諾圖 (K-Map) 求解器

卡諾圖 (K-Map) 求解器能最小化任何 2 到 5 個變數的布林邏輯函數，並將簡化過程視覺化為帶有彩色分組的經典卡諾圖。您可以輸入最小項、最大項，或使用交互式真值表 — 求解器底層運行 Quine-McCluskey 演算法，找出每個質蘊涵項，標記必要項，並提供帶有逐步說明的最小積之和 (SOP) 或和之積 (POS) 表達式。點擊任何質蘊涵項標籤，即可查看其覆蓋的單元格，了解分組如何簡化邏輯。

什麼是卡諾圖？

卡諾圖（由 Maurice Karnaugh 於 1953 年發明）是真值表的圖形化表示，其排列方式使得僅相差一個輸入變數的單元格在物理位置上相鄰。關鍵技巧在於行和列的格雷碼排序：連續的標籤（如 00, 01, 11, 10）僅相差一個位元。這種相鄰性讓您可以視覺化地找出可以組合成分組的 1（或 0），進而簡化項。

對於 n 個輸入變數，卡諾圖有 2^n 個單元格。4 變數卡諾圖是一個 4×4 的 16 單元格網格；5 變數圖則繪製為兩個相鄰的 4×4 網格。

SOP 與 POS：該選擇哪種形式

積之和 (SOP)

SOP 對 1-單元格進行分組。每個分組變成一個文字的乘積（AND），所有分組再進行「或」（OR）運算。例如：AB'C + BD。SOP 通常是預設選項，因為它直接映射到 AND–OR 閘電路網路。

和之積 (POS)

POS 對 0-單元格進行分組。每個分組變成互補文字的和（OR），所有和項再進行「與」（AND）運算。例如：(A + B')(C + D')。當函數中的 1 多於 0 時，POS 通常更簡潔。

此工具獨立計算這兩種形式 — 您可以切換輸出模式來比較文字數量，並選擇最適合您實作的簡潔形式。

卡諾圖分組規則

• 僅限 2 的冪次分組：分組必須包含 1、2、4、8 或 16 個單元格。不允許出現 3 或 5 個單元格的分組。
• 矩形形狀：分組中的單元格必須形成矩形（水平、垂直或跨越邊界包裹）。
• 邊界包裹相鄰性：頂行與底行相鄰；最左列與最右列相鄰。這就是格雷碼排序重要的原因。
• 優先選擇最大分組：較大的分組能消除更多變數，產生更短的乘積項。8 單元格分組減少 3 個變數；4 單元格減少 2 個；2 單元格減少 1 個。
• 必須覆蓋每個 1：對於 SOP，每個 1-單元格必須至少被一個分組覆蓋（POS 則針對 0-單元格）。
• 允許重疊：如果重疊能產生更大的分組，同一個 1 可以被多個分組覆蓋。
• 無關項靈活運用：如果包含無關項能產生更大的分組，則可以將其納入，但不必強制覆蓋它們。

質蘊涵項與必要質蘊涵項

質蘊涵項（Prime Implicant）是無法進一步擴大的分組 — 擴大它將包含 0-單元格（針對 SOP）。求解器會列出找到的每個質蘊涵項，然後挑選一個最小覆蓋：覆蓋所有必需最小項的最少質蘊涵項集合。

必要質蘊涵項（Essential Prime Implicant）是指唯一覆蓋某個特定最小項的質蘊涵項，會被標記為「必要」。每個最小表達式都必須包含所有必要質蘊涵項。在選擇它們後，剩餘未覆蓋的最小項將由成本最低的其他質蘊涵項覆蓋。

無關項 (Don't-Care Conditions)

無關項（在卡諾圖上顯示為 X）是輸出無關緊要的輸入組合 — 它們要麼在實際電路中永遠不會出現，要麼其值不重要。演算法可以自由地將每個 X 視為 0 或 1，以產生更簡單的表達式。在實務中，無關項通常能減少 30–60% 的文字數量。一個常見的現實案例是：僅使用 16 種四位元輸入組合中 10 種的十進制解碼器，剩餘的 10–15 組合即為無關項。

Quine-McCluskey 演算法

卡諾圖是一種視覺化方法，但對於 4–5 個以上的變數來說並不實用。Quine-McCluskey (QM) 演算法是其表格化等效形式 — 數學嚴謹且具擴展性。此求解器內部使用 QM：

1. 以二進制列出最小項，按 1 位元的數量分組。
2. 組合配對：組合相鄰組別中僅差一個位元的項，並用破折號替換差異位元。例如：0011 + 0111 → 0-11。
3. 重複步驟：直到無法進一步組合。無法再組合的項即為質蘊涵項。
4. 建立質蘊涵表：行是質蘊涵項，列是必需的最小項。識別必要質蘊涵項（僅包含一個勾選標記的列）。
5. Petrick 方法 / 窮舉搜索：對於剩餘未覆蓋的最小項，尋找覆蓋它們的最少額外質蘊涵項組合。

如何使用此計算機

1. 選擇變數數量：2、3、4 或 5 個。卡諾圖網格會自動調整。
2. 選擇輸入方法：
   • 最小項：輸入 F = 1 的索引（例如 1, 3, 5, 7）和任何無關項。
   • 最大項：輸入 F = 0 的索引。求解器會自動將其餘視為 1。
   • 真值表：點擊每一行在 0、1 和 X 之間切換。非常適合手動設計的邏輯。
3. 選擇 SOP 或 POS 輸出。切換比較兩者形式 — 通常其中一個會比另一個更短。
4. 點擊「求解」。卡諾圖會出現，每個質蘊涵項帶有獨特顏色。點擊任何標籤可查看其覆蓋的單元格。
5. 查看步驟：Quine-McCluskey 分解過程顯示了每個質蘊涵項的推導方式以及哪些是必要的。

操作範例：含無關項的 4 變數函數

考慮 F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5)。

若不考慮無關項，最小 SOP 需要多個項。若將 {0, 2} 視為 1，求解器可以建立 4 單元格分組 A'B'（覆蓋 0, 1, 2, 3）。將 5 視為 1 則能擴展 CD 的覆蓋範圍。最終簡化結果為：

僅需 4 個文字 — 相比不使用無關項技巧時的 10 個以上顯著減少。您可以使用上方「4 變數含無關項」快速範例載入此案例。

為什麼要最小化布林函數？

• 更少的邏輯閘 = 更低的硬體成本、更小的晶片面積、更低的功耗。
• 更快的電路：關鍵路徑上的邏輯閘延遲更少。
• 更清晰的文件：簡潔的表達式更易於驗證和維護。
• 數位設計的基礎：每個 FPGA 合成工具都運行著 Quine-McCluskey 的演進版本（如 Espresso-II 等）。

局限性與何時使用其他工具

• 5 個以上變數：卡諾圖在視覺上會變得雜亂。此工具透過拆分為兩個 4×4 圖來支援最多 5 個變數。除此之外，請依賴 Quine-McCluskey 步驟或使用 ABC / Espresso 等合成工具。
• 冒險與毛刺 (Hazards and Glitches)：最小覆蓋可能包含靜態冒險。對於無冒險設計，需包含冗餘質蘊涵項 — 此工具會標記它們，但不會自動添加冒險覆蓋。
• 多輸出最小化：如果多個函數共享變數，聯合最小化（共享邏輯閘）能產生更小的硬體。此工具一次僅最小化一個函數。

常見問題解答

什麼是卡諾圖？

卡諾圖（K-map）是一種最小化布林表達式的視覺化方法。單元格的排列方式使得相鄰單元格僅相差一個變數（格雷碼排序）。將 1 組合成大小為 1、2、4、8 或 16 的矩形，即可揭示最小的積之和表達式。

SOP 和 POS 之間有什麼區別？

SOP（積之和）對 1-單元格進行分組並將其乘積項進行「或」運算，例如 A'B + CD。POS（和之積）對 0-單元格進行分組並將其和項進行「與」運算，例如 (A + B')(C' + D)。兩者描述同一個函數，但通常其中一種形式更簡潔。

什麼是無關項，為什麼要使用它們？

無關項（標記為 X）是輸出值無關緊要的輸入組合 — 它們永遠不會發生，或其值不重要。求解器可將其視為 0 或 1，以產生更簡單的表達式。無關項通常能大幅減少文字數量。

什麼是質蘊涵項？

質蘊涵項是相鄰 1-單元格盡可能大的組合（大小為 2 的冪），且無法進一步擴大。必要質蘊涵項是唯一覆蓋至少一個最小項的項，必須包含在每個最小表達式中。

Quine-McCluskey 演算法是如何運作的？

Quine-McCluskey 是卡諾圖的表格等效版本，適用於多變數。它以二進制列出最小項，按 1 的個數分組，並迭代組合僅差一個位元的配對。無法再組合的項即質蘊涵項。隨後透過質蘊涵表選擇最小覆蓋。

此卡諾圖求解器支援多少個變數？

此工具支援 2 到 5 個變數。5 變數卡諾圖顯示為兩個相鄰的 4x4 圖。超過 5 個變數後，建議針對較大函數使用 Quine-McCluskey 步驟。

延伸閱讀

• 卡諾圖 — 維基百科
• Quine-McCluskey 演算法 — 維基百科
• Petrick 方法 — 維基百科