Шпаргалка по "Логике"

пределение. ДНФ называется совершенной (СДНФ), если каждая элементарная конъюнкция в ней содержит все переменные с отрицаниями или без.

В приведённом выше примере  является СДНФ, а  не является СДНФ, но  эквивалентная ей СДНФ. 

Теорема. Любую логическую формулу, не эквивалентную константе 0, можно представить в виде СДНФ, т.е. для каждой формулы найдётся эквивалентная ей СДНФ с таким же набором букв. 

Приведём алгоритм построения СДНФ. Сначала строится таблица истинности для формулы. Затем по тем строкам, в которых формула принимает  значение 1, строят элементарные конъюнкции следующим образом. Если буква в  данной интерпретации имеет нулевое  значение, то оно включается в элементарную конъюнкцию с отрицанием, а если она равна единице, то – без  отрицания.

2. Равносильные формулы  алгебры логики

Определение. Две формулы  алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний.

Обозначается это так: А≡В.