Boolean Logic Minimizer

繁體中文 · English

繁體中文

這是一個 correctness-first 的布林函數最小化工具：先用 Quine–McCluskey 產生 Prime Implicants，再用 Petrick cover 搜尋最小 SOP。所有計算都在瀏覽器本機完成。

為什麼重構

舊版可操作，但演算法、DOM 與結果格式化集中在兩個約 2,400 行的檔案，沒有自動測試， 也會在三變數輸入 m8 時錯誤產生第四變數 X3。v2 把輸入契約、純演算法核心、 Web Worker、UI 與部署拆開，並把該錯誤固定為 regression test。

已驗證能力

• Minterms 與進階 Prime Implicants 兩種輸入模式。
• 1–6 個變數、最多 4 個輸出的 bounded Exact prime-cover mode。
• minterm 範圍、重複值、don’t-care 衝突、PI 寬度及 off-set 覆蓋驗證。
• 多輸出共享 product term 成本模型。
• 256 種三變數 truth table 的完整等價性與最佳成本 oracle。
• Unit、regression、property 與 Playwright browser E2E。
• Web Worker 運算、靜態 GitHub Pages 與版本化 PWA cache。

成本模型

• 單一 literal 的 product term 成本為 1。
• 多 literal product term 成本為 literal count + 1。
• 同一 product term 跨輸出重用時，每新增一個輸出連線增加 1。

多輸出搜尋會在各函數的 Prime Implicant 候選聯集中找出精確最佳 cover；它不宣稱已 枚舉所有可能的非 prime 共享 implicants。這是專案明確定義的教學／實驗成本模型， 不等同特定 cell library、FPGA LUT 或工業 logic synthesis 的實際面積與 timing。

限制

• Exact minimization 具有組合爆炸；候選連線與覆蓋目標超過上限時會 fail fast。
• 第一輪只處理 SOP，不含 POS、K-map 編輯器、Verilog 產生或 Espresso heuristic。
• 本工具適合教學、小型函數與作品驗證，不取代 EDA 工具。
• 歷史 報告書.md 與 測資.md 保留原專題脈絡；v2 的行為以程式測試與本 README 為準。

本機開發

需求：Node.js 24、npm 11。

npm ci
npm run dev

完整驗證：

npm run check
npx playwright install chromium
npm run test:e2e

架構

flowchart LR
  UI["Input UI"] --> V["Validation"]
  V --> W["Web Worker"]
  W --> Q["Quine–McCluskey"]
  Q --> P["Petrick exact cover"]
  P --> R["Structured result"]
  R --> UI

Loading

核心目錄：

src/
├─ core/       # pure validation and minimization
├─ worker/     # isolated solver execution
├─ main.ts     # DOM controller and renderer
└─ styles.css
tests/
├─ unit/
├─ property/
├─ regression/
└─ e2e/

English

Boolean Logic Minimizer is a correctness-first, browser-local SOP minimizer. It generates prime implicants with Quine–McCluskey and solves the bounded prime-implicant cover with an exact Petrick-style branch-and-bound search.

The v2 refactor separates validation, the pure TypeScript solver, Web Worker execution, UI and deployment. It includes exhaustive oracle checks for all 256 three-variable truth tables, regression coverage for legacy bugs, and Playwright browser tests.

Scope

• 1–6 variables and up to 4 outputs.
• Minterm and advanced supplied-prime input modes.
• Explicit input and complexity errors.
• A documented experimental multi-output sharing cost model.
• Local-only computation and a versioned offline cache.

This is an educational and portfolio tool for small Boolean functions. It is not an industrial logic-synthesis or EDA replacement.

License

MIT