Boolean-Calc · 布尔逻辑表达式化简器

把逻辑表达式（如 AC()D + B()CD() + ABCD）化简成最简与或式与最简或与式， 并给出逐步化简过程、卡诺图与真值表。

提供三个独立实现，互不依赖：

实现	文件	运行方式
纯 C99 命令行	boolean-simplifier.c	gcc 编译，零第三方依赖
网页版 · 逐步化简	boolean-simplifier.html	双击用浏览器打开
网页版 · 最小项 / 卡诺图	boolean-minterm-studio.html	双击用浏览器打开

---

快速开始

C 版

gcc -std=c99 -O2 -Wall -Wextra -static -o boolean-simplifier boolean-simplifier.c

# 直接算一个式子
./boolean-simplifier "AC()D + B()CD() + ABCD"

# 只看答案
./boolean-simplifier -q "AC()D + B()CD() + ABCD"

# 展开全部中间细节（真值表、每一组合并对、完整质蕴含项表）
./boolean-simplifier -v "AC()D + B()CD() + ABCD"

# 不带参数 → 交互模式，一行一个式子
./boolean-simplifier

选项	作用
-q / --quiet	只输出结果
-v / --verbose	展开全部中间细节
-e	强制按表达式解析（不尝试最小项列表模式）

支持最多 8 个变量。

网页版

两个 HTML 都是单文件、零依赖，直接双击即可用。

• boolean-simplifier.html —— 输入表达式，左侧逐步列出化简依据（幂等律 / 吸收律 / 并项法 / 德摩根…），每一步都盖「与原式等价 ✓」徽章；另有卡诺图与真值表视图。
• boolean-minterm-studio.html —— 以最小项列表 / 真值表点选为主体， 适合做卡诺图分组练习，支持 2–6 变量的 Gray 码分组可视化。

---

输入语法

含义	写法	示例
非	X()、!X、X'、¬X、X̄	AC() = A·C'
与	相邻直接相乘、X*Y、X&Y、X·Y	ABCD = A·B·C·D
或	X+Y、X|Y	A+B
异或	X^Y	A^B
分组	(...)，全角 （） 也认	(A+B)C
常量	0、1	A+0
最小项列表	m(2,9,10)、M(...)、d(...)	m(0,1,4)+d(6,7)

两个要点：

1. 变量就是单个字母 —— ABCD 是四个变量相乘，不是名叫 "ABCD" 的变量。
2. 空括号紧跟操作数表示取反，写在变量或括号组后面都可以：AC()D 是 A·C'·D， (A+B)() 是整个括号组取反，即 A'·B'。

列表模式下变量个数按最大编号自动推断：m(3,6,7) 会被当成 3 变量函数 （因为 2³ > 7），需要更多变量时请用表达式模式显式写出变量。

---

输出示例

输入 AC()D + B()CD() + ABCD：

  ── 第 0 步　读入并解析表达式
  输入表达式：AC()D + B()CD() + ABCD
  解析结果　：F = A·C'·D + B'·C·D' + A·B·C·D
  变量识别　：A, B, C, D　（4 个变量，16 种输入组合）

  ── 第 1 步　列真值表 → 找出最小项
      16 行真值表中 F = 1 的有 5 行（-v 可看完整真值表）
      ⇒ 最小项：F = Σm(2, 9, 10, 13, 15)

  ── 第 2 步　代数展开为「与项之和」
      F = A·C'·D + B'·C·D' + A·B·C·D
      3 项 / 10 个文字

  ── 第 3 步　并项法逐轮合并
      （只有 1 个变量相反的两项可以合并，消掉那个变量）
      第 1 轮：5 个项参与合并
        A'B'CD'    + AB'CD'     = B'CD'       ← 消去 A
        AB'C'D     + ABC'D      = AC'D        ← 消去 B
        ABC'D      + ABCD       = ABD         ← 消去 C
        → 本轮产出 3 个新项
      第 2 轮：3 个项参与合并
        → 本轮产出 0 个新项，合并结束
      ⇒ 质蕴含项 3 个：B'CD'、AC'D、ABD

  ── 第 4 步　质蕴含项 → 挑出本质项
      B'CD'        → m2★ m10★ [本质项]
      AC'D         → m9★ m13 [本质项]
      ABD          → m13 m15★ [本质项]
      ★ = 该最小项只被这一个质蕴含项覆盖；共 3 个本质项

  ── 第 5 步　最小覆盖 → 最简与或式
      F = A·B·D + A·C'·D + B'·C·D'
      （3 项 / 9 个文字）

  ── 第 6 步　由最简 F' 经德摩根取反 → 最简或与式
      补函数 F' = A'·D + B·D' + C'·D' + B'·C·D
      逐项取反（乘→加、原变量↔反变量）再相乘 → F = (A + D')·(B' + D)·(C + D)·(B + C' + D')

结果卡：

  变量　　　　　　：A, B, C, D（4 个变量）
  最小项展开　　　：F = Σm(2, 9, 10, 13, 15)
  最大项展开　　　：F = ΠM(0, 1, 3, 4, 5, 6, 7, 8, 11, 12, 14)

  ★ 最简与或式 (SOP)：F = A·B·D + A·C'·D + B'·C·D'
  ★ 最简或与式 (POS)：F = (A + D')·(B' + D)·(C + D)·(B + C' + D')

  化简幅度　　　　：最小项标准式 5 项 / 20 文字  →  最简式 3 项 / 9 文字
  正确性自检　　　：✓ 用全部 16 行真值表逐行核对，最简式与原函数完全等价
  与非-与非实现　 ：F = [ (A ↑ B ↑ D) ↑ (A ↑ C' ↑ D) ↑ (B' ↑ C ↑ D') ]

---

算法

1. 词法 / 语法分析 —— 手写递归下降解析器，生成 AST；空括号 () 在 ( 处直接 产生后缀取反 token，因此变量和括号组的取反走同一条路径。
2. 代数展开 —— 分配律 + 德摩根，把 AST 展开成「与项之和」（SOP）。
3. Quine–McCluskey 并项法 —— 反复合并「只有一个变量相反」的两项，直到不能再合并， 得到全部质蕴含项。列表模式下的约束项 Σd 一并参与合并以凑出更大的圈。
4. 本质项 + 精确最小覆盖 —— 先选被唯一覆盖的最小项对应的本质项； 剩余部分用带剪枝的回溯搜索求 项数最少、其次字面量最少 的解， 并以贪心解作为上界加速；规模超限时退化为贪心。
5. 或与式 —— 对补函数 F' 重复上面流程，再用德摩根取反得到 POS。
6. 正确性自检 —— 每次输出前用全部 2ⁿ 行真值表逐行核对最简式与原函数是否等价， 结果打印在末尾（✓ / ✗）。

---

验证情况

C 版用 Node 脚本做过对撞测试，全部通过：

• 穷举全部 256 个三变量函数 —— 最简 SOP 与 POS 逐点比对真值表， 并与「暴力枚举所有蕴含项 + DFS 精确覆盖」求得的最优解比较项数与字面量：252/252 一致 （余下 4 个是恒 0 / 恒 1 的常量函数）。
• 11 组定向用例 —— 全角括号与全角符号、(A+B)() 复合式取反、异或、常量、5/6 变量、 德摩根嵌套式。
• 400 轮四变量随机函数（含约束项）与暴力最优解对撞 —— 无一例劣于最优。
• 逐步输出结构断言 —— 步骤编号连续、Σm 与最终式正确。

Web 版同样做过随机表达式与卡诺图矩形覆盖的校验。

---

目录结构

.
├── boolean-simplifier.c          # C99 命令行实现（单文件，零依赖）
├── boolean-simplifier.html       # 网页版：表达式逐步化简 + 卡诺图 + 真值表
├── boolean-minterm-studio.html   # 网页版：最小项列表 / 真值表点选 + 卡诺图分组
├── README.md
└── .gitignore

编译产物（*.exe 等）不入库，请自行编译。

---

已知限制

• 变量上限 8 个（MAXVAR），质蕴含项上限 20000 个。
• 列表模式下变量个数由最大编号推断，无法手动指定；需要特定变量数请用表达式模式。
• 回溯最小覆盖在质蕴含项极多时会退化到贪心（结果仍正确，但不保证最优）。
• Windows 纯 cmd 下会自动执行 chcp 65001 切 UTF-8；MSYS2 / Git Bash 下跳过。

---

许可

仓库目前未附许可证。如需开源授权，建议补一个 LICENSE（MIT 最省事）， 或在 GitHub 仓库设置里选择。