КНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 50 промежуточных версий 13 участников)
Строка 1: Строка 1:
 +
== КНФ ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
КНФ (Конъюнктивная Нормальная Форма) нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов.
+
'''Простой дизъюнкцией''' (англ. ''inclusive disjunction'') или '''дизъюнктом''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
 +
}}
 +
Простая дизъюнкция
 +
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно один раз;
 +
* '''монотонная''', если она не содержит отрицаний переменных.
 +
 
 +
{{Определение
 +
|definition =
 +
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
 
}}
 
}}
 
Пример КНФ:
 
Пример КНФ:
<tex>f(x,y) = (x \lor y) \land (y \lor \neg z)</tex>
+
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>
  
 +
== СКНФ ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
+
'''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
+
* в ней нет одинаковых простых дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
+
* каждая простая дизъюнкция полная
* каждая элементарная дизъюнкция содержит каждый из аргументов функции.
 
 
}}
 
}}
 
Пример СКНФ:
 
Пример СКНФ:
<tex>f(x,y,z) = (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>
 +
 
 +
 
 +
{{Теорема
 +
|statement=
 +
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
 +
|proof =
 +
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
 +
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>
 +
 
 +
Найдём инверсию левой и правой части выражения:
 +
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>
 +
 
 +
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
 +
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>
 +
 
 +
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
 +
}}
  
==Алгоритм построения СКНФ по таблице истинности==
+
== Алгоритм построения СКНФ по таблице истинности ==
*В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
+
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
*В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.  
+
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
*Полученные дизъюнкции связываем операциями конъюнкции
+
# Все полученные дизъюнкции связываем операциями конъюнкции.
 +
 
 +
== Пример построения СКНФ для медианы==
 +
=== Построение СКНФ для медианы от трех аргументов ===
 +
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
 +
 
 +
{| class="wikitable" style="width:10cm" border=1
 +
|+
 +
|-align="center" bgcolor=#EEEEFF
 +
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>
 +
|-align="center" bgcolor=#F0F0F0
 +
! 0 || 0 || 0 || 0
 +
|-align="center" bgcolor=#F0F0F0
 +
! 0 || 0 || 1 || 0
 +
|-align="center" bgcolor=#F0F0F0
 +
! 0 || 1 || 0 || 0
 +
|-align="center" bgcolor=#FFF
 +
| 0 || 1 || 1 || 1
 +
|-align="center" bgcolor=#F0F0F0
 +
! 1 || 0 || 0 || 0
 +
|-align="center" bgcolor=#FFF
 +
| 1 || 0 || 1 || 1
 +
|-align="center" bgcolor=#FFF
 +
| 1 || 1 || 0 || 1
 +
|-align="center" bgcolor=#FFF
 +
| 1 || 1 || 1 || 1
 +
|}
 +
 
 +
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
 +
 
 +
{| class="wikitable"  style="width:16cm" border=1
 +
|+
 +
|-align="center" bgcolor=#EEEEFF
 +
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> ||
 +
|-align="center" bgcolor=#F0F0F0
 +
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
 +
|-align="center" bgcolor=#F0F0F0
 +
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
 +
|-align="center" bgcolor=#F0F0F0
 +
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
 +
|-align="center" bgcolor=#FFF
 +
| 0 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#F0F0F0
 +
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
 +
|-align="center" bgcolor=#FFF
 +
| 1 || 0 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFF
 +
| 1 || 1 || 0 || 1 ||
 +
|-align="center" bgcolor=#FFF
 +
| 1 || 1 || 1 || 1 ||
 +
|}
 +
 
 +
3. Все полученные дизъюнкции связываем операциями конъюнкции.
 +
                                                                 
 +
<tex> \langle x,y,z \rangle = ( 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>
 +
 
 +
=== Построение СКНФ для медианы от пяти аргументов ===
 +
 
 +
{| class="wikitable"  style="width:16cm" border=1
 +
|+
 +
|-align="center" bgcolor=#EEEEFF
 +
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 0 || 1 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 1 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 0 || 1 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| 0 || 0 || 1 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 1 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 1 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 1 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| 0 || 1 || 0 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
! 0 || 1 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| 0 || 1 || 1 || 0 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 0 || 1 || 1 || 1 || 0 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 0 || 1 || 1 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
! 1 || 0 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 1 || 0 || 0 || 0 || 1 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
! 1 || 0 || 0 || 1 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 0 || 0 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
! 1 || 0 || 1 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 0 || 1 || 0 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 0 || 1 || 1 || 0 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 0 || 1 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
! 1 || 1 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 0 || 0 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 0 || 1 || 0 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 0 || 1 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 1 || 0 || 0 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 1 || 0 || 1 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 1 || 1 || 0 || 1 ||
 +
|-align="center" bgcolor=#FFFFFF
 +
| 1 || 1 || 1 || 1 || 1 || 1 ||
 +
|}
 +
 
 +
<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land \\ (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land \\ (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor \overline {x_5}) \land (x_1 \lor \overline {x_2} \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land (\overline {x_1} \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (\overline {x_1} \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) </tex>
  
 
==Примеры СКНФ для некоторых функций==
 
==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x $\downarrow$ y = (\neg x \lor y) \land (x \lor \neg y) \land (\neg x \lor \neg y)</tex>
+
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>
 +
 
 +
Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>
 +
 
 +
== См. также ==
 +
 
 +
* [[Специальные формы КНФ]]
 +
* [[ДНФ]]
 +
 
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
 +
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин,  Ю.Б. Фарфоровская {{---}} Дискретная математика]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
  
Медиана трёх: <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>
+
[[Категория: Булевы функции ]]

Текущая версия на 19:17, 4 сентября 2022

КНФ

Определение:
Простой дизъюнкцией (англ. inclusive disjunction) или дизъюнктом (англ. disjunct) называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

Простая дизъюнкция

  • полная, если в неё каждая переменная (или её отрицание) входит ровно один раз;
  • монотонная, если она не содержит отрицаний переменных.


Определение:
Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.

Пример КНФ: [math]f(x,y,z) = (x \lor y) \land (y \lor \neg{z})[/math]

СКНФ

Определение:
Совершенная конъюнктивная нормальная форма, СКНФ (англ. perfect conjunctive normal form, PCNF) — это такая КНФ, которая удовлетворяет условиям:
  • в ней нет одинаковых простых дизъюнкций
  • каждая простая дизъюнкция полная

Пример СКНФ: [math]f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})[/math]


Теорема:
Для любой булевой функции [math]f(\vec{x})[/math], не равной тождественной единице, существует СКНФ, ее задающая.
Доказательство:
[math]\triangleright[/math]

Поскольку инверсия функции [math]\neg{f}(\vec x)[/math] равна единице на тех наборах, на которых [math]f(\vec x)[/math] равна нулю, то СДНФ для [math]\neg{f}(\vec x)[/math] можно записать следующим образом: [math]\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) [/math], где [math] \sigma_{i} [/math] обозначает наличие или отсутствие отрицание при [math] x_{i} [/math]

Найдём инверсию левой и правой части выражения: [math] f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) [/math]

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: [math] f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) [/math]

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
[math]\triangleleft[/math]

Алгоритм построения СКНФ по таблице истинности

  1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math]0[/math].
  2. Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math]0[/math], то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
  3. Все полученные дизъюнкции связываем операциями конъюнкции.

Пример построения СКНФ для медианы

Построение СКНФ для медианы от трех аргументов

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math]0[/math].

x y z [math] \langle x,y,z \rangle [/math]
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть [math]0[/math], то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

x y z [math] \langle x,y,z \rangle [/math]
0 0 0 0 [math]( x \lor y \lor z)[/math]
0 0 1 0 [math]( x \lor y \lor \neg{z})[/math]
0 1 0 0 [math](x \lor \neg{y} \lor z)[/math]
0 1 1 1
1 0 0 0 [math](\neg{x} \lor y \lor z)[/math]
1 0 1 1
1 1 0 1
1 1 1 1

3. Все полученные дизъюнкции связываем операциями конъюнкции.

[math] \langle x,y,z \rangle = ( 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})[/math]

Построение СКНФ для медианы от пяти аргументов

[math] x_1 [/math] [math] x_2 [/math] [math] x_3 [/math] [math]x_4[/math] [math] x_5 [/math] [math] \langle x_1, x_2, x_3, x_4, x_5 \rangle [/math]
0 0 0 0 0 0 [math](x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)[/math]
0 0 0 0 1 0 [math](x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})[/math]
0 0 0 1 0 0 [math](x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)[/math]
0 0 0 1 1 0 [math](x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})[/math]
0 0 1 0 0 0 [math](x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)[/math]
0 0 1 0 1 0 [math](x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})[/math]
0 0 1 1 0 0 [math](x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)[/math]
0 0 1 1 1 1
0 1 0 0 0 0 [math](x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)[/math]
0 1 0 0 1 0 [math](x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})[/math]
0 1 0 1 0 0 [math](x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)[/math]
0 1 0 1 1 1
0 1 1 0 0 0 [math](x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)[/math]
0 1 1 0 1 1
0 1 1 1 0 1
0 1 1 1 1 1
1 0 0 0 0 0 [math](\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)[/math]
1 0 0 0 1 0 [math](\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})[/math]
1 0 0 1 0 0 [math](\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)[/math]
1 0 0 1 1 1
1 0 1 0 0 0 [math](\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)[/math]
1 0 1 0 1 1
1 0 1 1 0 1
1 0 1 1 1 1
1 1 0 0 0 0 [math](\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)[/math]
1 1 0 0 1 1
1 1 0 1 0 1
1 1 0 1 1 1
1 1 1 0 0 1
1 1 1 0 1 1
1 1 1 1 0 1
1 1 1 1 1 1

[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land \\ (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land \\ (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor \overline {x_5}) \land (x_1 \lor \overline {x_2} \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land (\overline {x_1} \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (\overline {x_1} \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) [/math]

Примеры СКНФ для некоторых функций

Стрелка Пирса: [math] x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) [/math]

Исключающее или: [math] x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)[/math]

См. также

Источники информации