Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ.
Этот факт является теоремой алгебры логики. Из него следует, что любая формула (кроме констант 0 и 1) может быть преобразован к виду как СДНФ, так и СКНФ. Константа 0 может быть представлена только СКНФ (
Алгоритм получения СДНФ по таблице истинности:
Алгоритм получения СКНФ по таблице истинности:
Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам алгебры логики: Примечание: для нахождения формулы по таблице истинности рекомендуется использовать тот из двух алгоритмов, в котором в таблице помечается меньше строк.
|
), а константа 1 – только СДНФ (
). Из вышесказанного следует, что если надо построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ или СДНФ этой функции.
– для 2-й строки;
– для 3-й строки.
.
– для 1-й строки;
– для 4-й строки.
.
.
