Построение СДНФ на основе ДНФ

Прошу помочь с построением СДНФ. Таблицу истинности построить не представляется возможным (если я правильно понимаю), так как речь идёт о графе. Задача в общем - нахождение максимальных внутренне устойчивых множеств графа методом Магу. Пример: граф задан матрицей смежности:

0 1 1 1
0 0 0 1
1 1 0 1
0 1 0 0

Для этого графа ДНФ будет иметь вид [y1 v (y2 & y3 & y4)] & (y2 v y4) & [y3 v (y2 & y4)]

СДНФ: (y1 & y2 & y3) v (y1 & y2 & y4) v (y1 & y3 & y4) v (y2 & y3 & y4)

Максимальные внутренне устойчивые множества, таким образом, {v1} {v2} {v3} {v4}

Итак, я имею битовую маску для каждой строки и хочу с помощью битовых операций привести ДНФ этих масок привести к СДНФ.

Битовые маски записаны в массив размерности 4x2 в виде

[y1][y2 y3 y4]
[y2][y4]
[y3][y1 y2 y4]
[y4][y2]

В данном массиве записаны именно битовые маски для строк, а не значения в ячейках матрицы смежности.

Как мне найти СДНФ, имея ДНФ строк таблицы смежности?

P.S.:Пишу на языке C#, могу понять язык C++


Ответы (0 шт):