Русская Википедия:Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма (СКНФ) — одна из форм представления функции алгебры логики (булевой функции) в виде логического выражения. Представляет собой частный случай КНФ, удовлетворяющий следующим трём условиям:
· в ней нет одинаковых множителей (элементарных дизъюнкций);
· в каждом множителе нет повторяющихся переменных;
· каждый множитель содержит все переменные, от которых зависит булева функция (каждая переменная может входить в множитель либо в прямой, либо в инверсной форме).
Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ.[1].
Пример нахождения СКНФ
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи минимизация логических функций методом Квайна:
| <math>x_1</math> | <math>x_2</math> | <math>x_3</math> | <math>x_4</math> | <math>f(x_1, x_2, x_3, x_4)</math> |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
В ячейках строки́ <math>f(x_1, x_2, x_3, x_4)</math> отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.
Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:
- <math>x_1 = 0</math>
- <math>x_2 = 0</math>
- <math>x_3 = 1</math>
- <math>x_4 = 1</math>
В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: <math>x_1 \vee x_2 \vee \overline{x_3} \vee \overline{x_4}</math>
Остальные члены СКНФ составляются по аналогии:[2]
- <math>({x_1} \lor {x_2} \lor \overline{x_3} \lor \overline{x_4}) \land ({x_1} \lor \overline{x_2} \lor {x_3} \lor {x_4}) \land ({x_1} \lor \overline{x_2} \lor {x_3} \lor \overline{x_4}) \land ({x_1} \lor \overline{x_2} \lor \overline{x_3} \lor \overline{x_4}) \land</math>
- <math>(\overline{x_1} \lor {x_2} \lor {x_3} \lor {x_4}) \land (\overline{x_1} \lor {x_2} \lor {x_3} \lor \overline{x_4}) \land (\overline{x_1} \lor {x_2} \lor \overline{x_3} \lor {x_4}) \land (\overline{x_1} \lor {x_2} \lor \overline{x_3} \lor \overline{x_4}) \land </math>
- <math>(\overline{x_1} \lor \overline{x_2} \lor {x_3} \lor {x_4}) \land (\overline{x_1} \lor \overline{x_2} \lor {x_3} \lor \overline{x_4})</math>
См. также
- Конъюнктивная нормальная форма
- Дизъюнктивная нормальная форма
- Совершенная дизъюнктивная нормальная форма
Примечания
- ↑ Шаблон:Cite web
- ↑ В.И. Игошин. Задачник-практикум по математической логике. 1986
