离散数学最优DNF形式求解及Python代码调试、可视化求助

一、如何找出所有最优DNF形式 #

最优DNF通常指最简析取范式，即合取项数量最少，且每个合取项的文字数量最少。步骤如下：

• 提取极小项：从真值表中找出所有使公式为真的输入组合，每个组合对应一个极小项（每个变量取原变量或非变量，用合取连接）。
• 生成质蕴涵项：
  • 用卡诺图(K-map)：将极小项按相邻性（仅一个变量取值不同）排列成矩阵，合并相邻的1单元格，每个合并块对应一个消去冗余变量的质蕴涵项。
  • 用奎因-麦克拉斯基算法：系统地合并极小项，生成所有质蕴涵项，避免遗漏。
• 最小覆盖求解：通过覆盖表找出能覆盖所有真输入的最少质蕴涵项组合，每个组合对应一个最优DNF。

二、Python代码无输出的错误排查与修正 #

你的代码核心逻辑存在两处关键错误，导致无输出：

错误分析 #

1. 合取项连接符错误：合取项内部的变量应该用and连接，而非or。你当前生成的是单个析取式（如A or B or ~C），而非合取项。
2. DNF生成逻辑错误：你要的是包含3个合取项的DNF（size=3），但当前代码仅生成单个伪合取项，且用运算符总数来判断size，完全不符合需求。当size=3时，单个伪合取项的运算符数量为2（两个or），因此被过滤，无输出。

修正后的代码 #

以下代码生成所有包含3个合取项的DNF，每个合取项恰好有2个原变量（length=2）：

import itertools

def generate_dnf(variables, conj_length=None, num_conjs=None):
    num_vars = len(variables)
    conjuncts = []

    # 生成所有符合长度要求的合取项：conj_length个原变量，其余为非变量
    if conj_length is not None:
        # 选择conj_length个变量作为原变量，其余取非
        for selected in itertools.combinations(range(num_vars), conj_length):
            conj = []
            for i in range(num_vars):
                if i in selected:
                    conj.append(variables[i])
                else:
                    conj.append(f'~{variables[i]}')
            conjuncts.append(' and '.join(conj))
    
    # 生成所有num_conjs个合取项的组合，用or连接成DNF
    dnf_formulas = []
    if num_conjs is not None:
        for combo in itertools.combinations(conjuncts, num_conjs):
            dnf_formulas.append(' or '.join(combo))
    
    return dnf_formulas

variables = ['A', 'B', 'C']
# 生成每个合取项有2个原变量、共3个合取项的所有DNF
dnfs = generate_dnf(variables, conj_length=2, num_conjs=3)
for dnf in dnfs:
    print(dnf)

代码说明 #

• 先生成所有符合conj_length=2的合取项（如A and B and ~C、A and ~B and C等，共3个）。
• 然后生成这些合取项的所有3元组合（由于只有3个合取项，仅1种组合），最终输出A and B and ~C or A and ~B and C or ~A and B and C。

三、真值表衍生图转布尔代数的思路 #

从真值表对应的图（如卡诺图、决策图）转换为布尔代数表达式，可参考以下方法：

1. 卡诺图转换：
   • 将真值表的行按相邻规则排列成卡诺图，标记出所有输出为1的单元格。
   • 合并相邻的1单元格块（块的大小为2的幂），每个块对应一个质蕴涵项：块中取值不变的变量保留，取值变化的变量消去。
   • 将所有覆盖所有1单元格的质蕴涵项用析取连接，得到布尔表达式。
2. 二叉决策图(BDD)转换：
   • 从BDD的根节点遍历到每个输出为1的叶子节点，每条路径对应一个合取项：路径上的变量取值（真/假）对应原变量/非变量。
   • 合并冗余路径（如相同子树），简化后将所有合取项用析取连接，得到DNF。
3. 直接化简法：
   • 从真值表提取所有真输入对应的极小项，利用布尔代数的等价律（分配律、吸收律、德摩根律等）逐步合并化简，得到最简表达式。

内容的提问来源于stack exchange，提问作者Liuzili