Построение СКНФ и СДНФ по таблице истинности

1. СКНФ
2. СДНФ

Нормальной форме логической формулы не свойственна эквивалентность, отрицание формул неэлементарного типа и знаки импликации.

Выделяют такие виды формы нормального типа:

• КНФ (конъюнктивная нормальная форма), где подразумевается конъюнкция того или иного количества дизъюнкций, как пример, ;
• ДНФ (дизъюнктивная нормальная форма), где осуществляется дизъюнкция конъюнкций, как пример, .

СКНФ

Совершенная КНФ является разновидностью конъюнктивной нормальной формы, удовлетворяющей такие условия:

• отсутствие одинаковых элементарных дизъюнкций;
• дизъюнкции не содержат одинаковые переменные;
• все дизъюнкции содержат каждую переменную из входящих в конъюнктивную НФ такого типа.

Построение СКНФ согласно таблице истинности

Если функция равна нулю, то в случае каждого набора записывают сумму, причем с отрицанием берутся те переменные, которые равны единице.

СДНФ

Совершенная ДНФ является разновидностью дизъюнктивной нормальной формы, удовлетворяющей следующие условия:

• отсутствие одинаковых элементарных конъюнкций;
• конъюнкции не свойственно обладать одинаковыми переменными;

в случае любой конъюнкции элементарного типа имеет место быть переменная, входящая в такую нормальную дизъюнктивную форму. При этом в одинаковом порядке.

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

Построение СДНФ согласно таблице истинности

Если функция соответствует единице, то в случае каждого набора записывается произведение, причем с отрицанием берутся те переменные, которые равны нулю.

Нахождение СКНФ и СДНФ: примеры

Пример

Согласно таблице истинности записать логическую функцию:

Рисунок 1.

Решение:

Прибегнем к правилу построения совершенной ДНФ

Рисунок 2.

Получаем такую СДНФ

Задействовав правило её построения:

Рисунок 3.

Получаем СКНФ:

Пример

Представить функцию как СДНФ и СКНФ, при том, что она задаётся таблицей истинности.

Рисунок 4.

Решение

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

Рисунок 5.

Вычисленные конъюнкции из вспомогательного столбца необходимо объединить знаком дизъюнкции и получим необходимую логическую функцию, имеющую вид совершенной конъюнктивной формы нормального типа:

Запишем логическую функцию в СКНФ.

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

Рисунок 6.

Вычисленные дизъюнкции из вспомогательного столбца необходимо объединить знаком конъюнкции, так как таким образом и можно получить необходимую логическую функцию, имеющую вид совершенной нормальной формы конъюнктивного типа.