ДНФ — различия между версиями
(→СДНФ) |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 7 участников) | |||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Простой конъюнкцией или конъюнктом называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. | + | '''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. |
}} | }} | ||
Простая конъюнкция | Простая конъюнкция | ||
− | * '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 раз; | + | * '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз; |
* '''монотонная''', если она не содержит отрицаний переменных. | * '''монотонная''', если она не содержит отрицаний переменных. | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | ДНФ ( | + | '''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов. |
}} | }} | ||
Пример ДНФ: | Пример ДНФ: | ||
− | <tex>f(x,y) = (x \land y) \lor (y \land \neg {z})</tex> | + | <tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>. |
== СДНФ == | == СДНФ == | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | СДНФ ( | + | '''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — ДНФ, удовлетворяющая условиям: |
− | * в ней нет одинаковых простых конъюнкций | + | * в ней нет одинаковых простых конъюнкций, |
− | * каждая простая конъюнкция полная | + | * каждая простая конъюнкция полная. |
}} | }} | ||
Пример СДНФ: | Пример СДНФ: | ||
− | <tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex> | + | <tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>. |
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю | + | Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая. |
|proof = | |proof = | ||
− | Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''' | + | Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''': |
− | <tex>f(\vec{x}) = \neg x_i \wedge f(x_1, | + | <tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \vee |
− | x_i \wedge f(x_1, | + | x_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)</tex>. |
− | Данное соотношение легко проверить подстановкой | + | Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу: |
− | <tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge | + | <tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~</tex> |
− | <tex>\neg x_1 \wedge \neg x_2 \wedge | + | <tex>\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,\ldots,0,1) ~\vee~ \\ |
− | \ | + | \ldots \\ |
− | ~\vee~ x_1 \wedge x_2 \wedge | + | ~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\ |
− | x_1 \wedge x_2 \wedge | + | x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,\ldots,1) </tex> |
Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ. | Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ. | ||
Строка 47: | Строка 47: | ||
== Алгоритм построения СДНФ по таблице истинности == | == Алгоритм построения СДНФ по таблице истинности == | ||
− | # В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1. | + | # В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>. |
− | # Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание. | + | # Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание. |
# Все полученные конъюнкции связываем операциями дизъюнкции. | # Все полученные конъюнкции связываем операциями дизъюнкции. | ||
== Пример построения СДНФ для медианы== | == Пример построения СДНФ для медианы== | ||
− | 1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1. | + | === Построение СДНФ для медианы от трех аргументов === |
+ | 1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>. | ||
{| class="wikitable" style="width:10cm" border=1 | {| class="wikitable" style="width:10cm" border=1 | ||
|+ | |+ | ||
|-align="center" bgcolor=#EEEEFF | |-align="center" bgcolor=#EEEEFF | ||
− | | x || y || z || <tex> \langle x,y,z \rangle </tex> | + | |<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> |
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
| 0 || 0 || 0 || 0 | | 0 || 0 || 0 || 0 | ||
Строка 65: | Строка 66: | ||
| 0 || 1 || 0 || 0 | | 0 || 1 || 0 || 0 | ||
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
− | + | ! 0 || 1 || 1 || 1 | |
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
− | + | | 1 || 0 || 0 || 0 | |
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
! 1 || 0 || 1 || 1 | ! 1 || 0 || 1 || 1 | ||
Строка 76: | Строка 77: | ||
|} | |} | ||
− | 2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание. | + | 2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание. |
{| class="wikitable" style="width:16cm" border=1 | {| class="wikitable" style="width:16cm" border=1 | ||
|+ | |+ | ||
|-align="center" bgcolor=#EEEEFF | |-align="center" bgcolor=#EEEEFF | ||
− | | x || y || z || <tex> \langle x,y,z \rangle </tex> || | + | |<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> || |
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
| 0 || 0 || 0 || 0 || | | 0 || 0 || 0 || 0 || | ||
Строка 89: | Строка 90: | ||
| 0 || 1 || 0 || 0 || | | 0 || 1 || 0 || 0 || | ||
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
− | + | ! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex> | |
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
− | + | | 1 || 0 || 0 || 0 || | |
|-align="center" bgcolor=#FFFFFF | |-align="center" bgcolor=#FFFFFF | ||
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex> | ! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex> | ||
Строка 100: | Строка 101: | ||
|} | |} | ||
− | 3. Все полученные конъюнкции связываем операциями дизъюнкции | + | 3. Все полученные конъюнкции связываем операциями дизъюнкции: |
− | <tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex> | + | <tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \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 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 0 || 0 || 0 || 1 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 0 || 0 || 1 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 0 || 0 || 1 || 1 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 0 || 1 || 0 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 0 || 1 || 0 || 1 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 0 || 1 || 1 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 0 || 0 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 1 || 0 || 0 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 1 || 0 || 0 || 1 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 1 || 0 || 1 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 0 || 1 || 0 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 0 || 1 || 1 || 0 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 0 || 1 || 1 || 0 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 0 || 1 || 1 || 1 || 0 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 0 || 1 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 1 || 0 || 0 || 0 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 1 || 0 || 0 || 0 || 1 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 1 || 0 || 0 || 1 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 0 || 0 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 1 || 0 || 1 || 0 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 0 || 1 || 0 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 0 || 1 || 1 || 0 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 0 || 1 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | | 1 || 1 || 0 || 0 || 0 || 0 || | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 0 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 0 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_5})</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 0 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land \neg {x_5})</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 1 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 1 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex> | ||
+ | |-align="center" bgcolor=#FFFFFF | ||
+ | ! 1 || 1 || 1 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex> | ||
+ | |} | ||
+ | |||
+ | <tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (\overline {x_1} \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>. | ||
==Примеры СДНФ для некоторых функций== | ==Примеры СДНФ для некоторых функций== | ||
− | Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex> | + | Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>. |
+ | |||
+ | Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>. | ||
+ | |||
+ | == См. также == | ||
− | + | * [[Сокращенная и минимальная ДНФ]] | |
+ | * [[КНФ]] | ||
− | == | + | ==Источники информации == |
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия] | * [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия] | ||
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика] | * [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика] |
Текущая версия на 19:35, 4 сентября 2022
Содержание
ДНФ
Определение: |
Простой конъюнкцией (англ. inclusive conjunction) или конъюнктом (англ. conjunct) называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. |
Простая конъюнкция
- полная, если в неё каждая переменная (или её отрицание) входит ровно раз;
- монотонная, если она не содержит отрицаний переменных.
Определение: |
Дизъюнктивная нормальная форма, ДНФ (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов. |
Пример ДНФ:
.СДНФ
Определение: |
Совершенная дизъюнктивная нормальная форма, СДНФ (англ. perfect disjunctive normal form, PDNF) — ДНФ, удовлетворяющая условиям:
|
Пример СДНФ:
.
Теорема: |
Для любой булевой функции , не равной тождественному нулю, существует СДНФ, ее задающая. |
Доказательство: |
Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона: . Данное соотношение легко проверить подстановкой возможных значений ( и ). Эта формула позволяет выносить за знак функции. Последовательно вынося , ,.., за знак , получаем следующую формулу:Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от переменных мы имеем конъюнктов. Каждый из них соответствует значению функции на одном из возможных наборов значений переменных. Если на некотором наборе , то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же , то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ. |
Алгоритм построения СДНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно .
- Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть , то в конъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные конъюнкции связываем операциями дизъюнкции.
Пример построения СДНФ для медианы
Построение СДНФ для медианы от трех аргументов
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно
.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. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть
, то в конъюнкцию включаем саму переменную, иначе ее отрицание.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 |
3. Все полученные конъюнкции связываем операциями дизъюнкции:
.
Построение СДНФ для медианы от пяти аргументов
0 | 0 | 0 | 0 | 0 | 0 | |
0 | 0 | 0 | 0 | 1 | 0 | |
0 | 0 | 0 | 1 | 0 | 0 | |
0 | 0 | 0 | 1 | 1 | 0 | |
0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | |
0 | 0 | 1 | 1 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 1 | |
---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | |
0 | 1 | 0 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 0 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | |
0 | 1 | 1 | 0 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | |
1 | 0 | 0 | 0 | 0 | 0 | |
1 | 0 | 0 | 0 | 1 | 0 | |
1 | 0 | 0 | 1 | 0 | 0 | |
1 | 0 | 0 | 1 | 1 | 1 | |
1 | 0 | 1 | 0 | 0 | 0 | |
1 | 0 | 1 | 0 | 1 | 1 | |
1 | 0 | 1 | 1 | 0 | 1 | |
1 | 0 | 1 | 1 | 1 | 1 | |
1 | 1 | 0 | 0 | 0 | 0 | |
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 |
.
Примеры СДНФ для некоторых функций
Стрелка Пирса:
.Исключающее или:
.