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