задачи по информатике - вопрос №65435

Если я правильно понял формулу: X2*not(X3)+X1*X3+not(X2). Это ДНФ, чтобы привести к СДНФ нам надо чтобы в каждой из групп коньюнкций (умножений) присутствовали все литералы (переменные X1, X2 и X3). Таких групп у нас 3, недостающие переменные вставим в виде [X+not(X)], а потом раскроем скобки и немного упростим.

X2*not(X3)+X1*X3+not(X2) =

[X1+not(X1)]*X2*not(X3)+

X1*[X2+not(X2)]*X3+

[X1+not(X1)]*not(X2)*[X3+not(X3)]=

X1*X2*not(X3)+not(X1)*X2*not(X3)+

X1*X2*X3+X1*not(X2)*X3+

X1*not(X2)*X3+X1*not(X2)*not(X3)+not(X1)*not(X2)*X3+not(X1)*not(X2)*not(X3)

теперь найдём повторяющиеся группы (отметил одним цветом) и оставим одну из них по правилу X+X=X

В итоге получаем:

X1*X2*not(X3)+not(X1)*X2*not(X3)+X1*X2*X3+X1*not(X2)*X3+X1*not(X2)*not(X3)+not(X1)*not(X2)*X3+not(X1)*not(X2)*not(X3)

СДНФ больше ДНФ за счёт того что в ней обязаны присутствовать все литералы, но каждая из групп должна оставаться уникальной.