Логические основы информатики

Полученная форма удовлетворяет  определению ДНФ.

Если ДНФ функции  от n переменных в каждой своей конъюнкции содержит все n переменных либо их отрицания, то это совершенная дизъюнктивная нормальная форма (СДНФ). Каждая функция имеет од ну-единственную СДНФ, и она может быть получена из таблицы истинности этой функции путем записи через знак логического сложения всех наборов переменных, на которых эта функция определена как истинная. Каждый такой набор переменных соответствует конъюнкции,

Например, для функции: 

СДНФ по таблице истинности может  быть построена как:

СДНФ_( F) = 000 + 010 + 100+ 101 +110_=

Теорема о КНФ. Всякая сложная логическая функция может быть сведена к КНФ.

Для того чтобы сделать эго, необходимо:

• записать булеву функцию в виде {+, -, -};
• с помощью законов де Моргана спустить черту отрицания до отдельных букв и по закону двойного отрицания уничтожить двойные черточки;
• с помощью второго закона дистрибутивности уничтожим все суммы произведений и проведем поглощение. Полученная форма удовлетворяет определению КНФ.

Если КНФ функции от n переменных в каждой своей дизъюнкции содержит все n переменных либо их отрицания, то это совершенная конъюнктивная нормальная  форма.  Каждая функция имеет одну-единственную   СКНФ, и она может быть получена из таблицы истинности этой функции путем записи через знак логического умножения всех наборов переменных, на которых эта функция определена как ложная.

Например, для функции:

СКНФ  по таблице истинности может быть построена как

СКНФ=

Пример. Составить таблицу истинности для  формулы:

(X →Y ) & ( Y → Z) v ( Z &X)

Решение.

1. Составим таблицу.
2. Выполним логическую операцию – импликацию (X → Y )
3. Выполним логическую операцию – импликацию ( Y → Z)
4. Выполним логическую операцию – конъюнкцию (X →Y ) & ( Y → Z)
5. Выполним логическую операцию – конъюнкцию ( Z &X)
6. Выполним логическую операцию – дизъюнкцию

       (X →Y ) & ( Y → Z) v ( Z &X)