Creating and simplifying of bool formula in Python

user_14227647 0
Viewed 75

There is a problem of finding maximal internally stable graph sets by the Magu method (discrete mathematics in higher education). Given a graph with an adjacency matrix(already implemented), then you need to make Boolean formulas where there will be a conjunction of all disjunctions of negations of adjacent vertices. That is, for example, if there is a path from V1 to V2 and from V1 to V3, then the formula will include (!V1 v !V2) & (!V1 v !V3). Then this expression is transformed into a shortened DNF, and then you can see which vertices of the graph are missing in each bracket - those vertices just form these maximum internally stable sets. Just the question is how to make this initial Boolean formula, and with what you can then simplify this formula to the abbreviated DNF? I assume that you need to use the sympy library, but I can't find any specific information on my question... The code at the moment

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)
sympy discrete-mathematics numpy python
1 Answers

Problem solved

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))
user_142276470
Related