在 Python 中创建和简化 bool 公式

Question

麻姑法（高等教育中的离散数学）求最大内部稳定图集的问题。给定一个带有邻接矩阵（已经实现）的图，那么你需要制作布尔公式，其中将有相邻顶点否定的所有析取的合取。也就是说，例如，如果存在从 V1 到 V2 和从 V1 到 V3 的路径，则公式将包括 (!V1 v !V2) & (!V1 v !V3)。然后这个表达式被转化为一个缩短的 DNF，然后你可以看到每个括号中缺少了图的哪些顶点——那些顶点正好形成了这些最大内部稳定集。只是问题是如何制作这个初始布尔公式，然后用什么可以将这个公式简化为缩写的 DNF？我假设你需要使用 sympy 库，但我找不到关于我的问题的任何具体信息......目前的代码

import numpy as np
from sympy import *
from sympy.logic.boolalg import And
from sympy.logic.boolalg import Or

print("Number of nodes in graph:")
amount = int(input())
matrix = np.zeros((amount, amount))
i = 0
j = 0

while i < amount:
    while j < amount:
        print("insert matrix element", i, j, ":")
        matrix[i, j] = int(input())
        j += 1
    j = 0
    i += 1
print(matrix)

Answer 1

问题已解决

i = 0
j = 0
counter = 0
while i < amount:
    while j < amount:
        if matrix[i, j] == 1:
            x = symbols(str(i + 1))
            y = symbols(str(j + 1))
            if counter == 0:
                formula = (~x | ~y)
                counter += 1
            else:
                formula = formula & (~x | ~y)
        j += 1
    j = 0
    i += 1
formula_to_string = pycode(simplify_logic(formula, form='dnf', force=True))

在 Python 中创建和简化 bool 公式

Creating and simplifying of bool formula in Python

python

numpy

discrete-mathematics

sympy