8
правок
Изменения
КНФ
,Новая страница: «''' КНФ (Конъюнктивная нормальная форма)''' в булевой логике — нормальная форма, в которой б…»
''' КНФ (Конъюнктивная нормальная форма)''' в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов.
Пример КНФ:
<math>(x \or y) \and (y \or \neg z)</math>
''' СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
* каждая элементарная дизъюнкция содержит каждую из входящих в данную КНФ переменных.
Пример СКНФ:
<math>(x \or \neg y \or z) \and (x\or y \or \neg z)</math>
==Алгоритм построения СКНФ по таблице истинности==
*В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
*В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
*Полученные дизъюнкции связываем операциями конъюнкции
==Примеры СКНФ для некоторых функций==
Стрелка пирса: <math>(\neg x \or y) \and (x \or \neg y) \and (\neg x \or \neg y)</math>
Медиана трёх: <math>( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)</math>
Пример КНФ:
<math>(x \or y) \and (y \or \neg z)</math>
''' СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
* каждая элементарная дизъюнкция содержит каждую из входящих в данную КНФ переменных.
Пример СКНФ:
<math>(x \or \neg y \or z) \and (x\or y \or \neg z)</math>
==Алгоритм построения СКНФ по таблице истинности==
*В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
*В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
*Полученные дизъюнкции связываем операциями конъюнкции
==Примеры СКНФ для некоторых функций==
Стрелка пирса: <math>(\neg x \or y) \and (x \or \neg y) \and (\neg x \or \neg y)</math>
Медиана трёх: <math>( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)</math>
