КНФ — различия между версиями
| Строка 4: | Строка 4: | ||
}} | }} | ||
Пример КНФ: | Пример КНФ: | ||
| − | < | + | <tex>(x \lor y) \land (y \lor \neg z)</tex> |
| − | + | {{Определение | |
| + | |definition = | ||
| + | СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям: | ||
* в ней нет одинаковых элементарных дизъюнкций | * в ней нет одинаковых элементарных дизъюнкций | ||
* в каждой дизъюнкции нет одинаковых переменных | * в каждой дизъюнкции нет одинаковых переменных | ||
| − | * каждая элементарная дизъюнкция содержит | + | * каждая элементарная дизъюнкция содержит каждый из аргументов функции. |
| − | + | }} | |
Пример СКНФ: | Пример СКНФ: | ||
| − | < | + | <tex>(x \lor \neg y \lor z) \land (x\lor y \lor \neg z)</tex> |
==Алгоритм построения СКНФ по таблице истинности== | ==Алгоритм построения СКНФ по таблице истинности== | ||
| Строка 20: | Строка 22: | ||
==Примеры СКНФ для некоторых функций== | ==Примеры СКНФ для некоторых функций== | ||
| − | Стрелка Пирса: < | + | Стрелка Пирса: <tex>x ↓ y = (\neg x \lor y) \land (x \lor \neg y) \and (\neg x \lor \neg y)</tex> |
| − | Медиана трёх: < | + | Медиана трёх: <tex>( x \lor y \lor z) \land (\neg x \lor y \lor z) \and (x \lor \neg y \lor z) \and ( x \lor y \lor \neg z)</tex> |
Версия 21:12, 10 октября 2010
| Определение: |
| КНФ (Конъюнктивная Нормальная Форма) — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов. |
Пример КНФ:
| Определение: |
СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет условиям:
|
Пример СКНФ:
Алгоритм построения СКНФ по таблице истинности
- В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
- В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
- Полученные дизъюнкции связываем операциями конъюнкции
Примеры СКНФ для некоторых функций
Стрелка Пирса:
Медиана трёх:
