IBM Ponder This #053 · 2002 年 9 月

John G. Fletcher 提出了这个问题。两个布尔输入到一个布尔输出共有 16 种运算。若仅交换输入顺序就能把一种运算变成另一种，则把二者视为相同；这样得到 12 类运算。

其中两类是常值 T、F，两类是一元运算 Identity（恒等）和 Not（非），其余八类为 And、Or、Nand、Nor、Equivalent、Xor、Implies、Non-implies。

一个子集称为“封闭”，当且仅当用其中运算作任意复合，所得运算仍属于该子集。允许子集为全集。零次复合视为恒等运算，因此每个封闭子集都包含 Identity。

复合表达式中的每个输入可以独立指定为 p 或 q，并把结果视为二元运算。例如 p Nand p 等于 Not p；(p Nand p) Nand p 恒为 T；(p Nand p) Nand q 和 (p Nand q) Nand q 都等于 q Implies p。因此包含 Nand 的封闭子集还必须包含 T、Not 和 Implies。

这样的封闭子集共有多少个？每个分别包含哪些运算？

穷举规模并不大，可以手算或编程，但官方更希望看到能解释分类为何完整的优雅论证，也欢迎解释各封闭子集对应的受限逻辑表达能力。

解答

认真尝试后再打开

待补充。