Изменения

Перейти к: навигация, поиск

ДНФ

5628 байт добавлено, 19:35, 4 сентября 2022
м
rollbackEdits.php mass rollback
== Определение ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией ''' (англ. ''inclusive conjunction'') или '''конъюнктом ''' (англ. ''conjunct'') называется конъюнкция некоторого конечного набора одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Элементарная Простая конъюнкция* '''правильная''', если в неё каждая переменная входит не более одного раза (включая отрицание);* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.
{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ ''' (Дизъюнктивная Нормальная Формаангл. ''disjunctive normal form, DNF'') — {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \overlineneg {z})</tex>.
== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ ''' (Совершенная Дизъюнктивная Нормальная Форма)англ. ''perfect disjunctive normal form, PDNF'' ) — это такая ДНФ, которая удовлетворяет удовлетворяющая условиям:* в ней нет одинаковых элементарных простых конъюнкций* в каждой конъюнкции нет одинаковых переменных,* каждая элементарная простая конъюнкция содержит каждый из аргументов функцииполная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \overlineneg {y} \land z) \lor (x \land y \land \overlineneg {z})</tex>.
{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.:
<tex>f(\vec{x}) = \overline neg x_i \wedge f(x_1,..\ldots ,x_{i-1},0,x_{i+1},..\ldots ,x_n) \veex_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}) = \overline neg x_1 \wedge \overline neg x_2 \wedge ...\ldots \wedge \overline neg x_{n-1} \wedge \overline neg x_n \wedge f(0,0,...\ldots,0,0)~\vee~</tex>
<tex>\overline neg x_1 \wedge \overline neg x_2 \wedge ... \ldots \wedge \overline neg x_{n-1} \wedge x_n \wedge f(0,0,...\ldots,0,1) ~\vee~\\\ldots \\~\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 \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>~\vee~ x_1 \wedge x_2 \wedge ..переменных. Если на некотором наборе <tex>f(\wedge x_vec{n-1x} \wedge \overline x_n \wedge f(1,1,...,1,)=0) ~\vee~</tex> , то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex>x_1 f(\wedge x_2 \wedge ... \wedge x_vec{n-1x} \wedge x_n \wedge f(1,1,...,)=1) </tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.}}
Т.к применение данного соотношения к каждой из == Алгоритм построения СДНФ по таблице истинности ==# В таблице истинности отмечаем те наборы переменных увеличивает количество дизъюнктивных членов в два раза, то для на которых значение функции от равно <tex>n</tex> переменных мы имеем <tex>2^n1 </tex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений n # Для каждого отмеченного набора записываем конъюнкцию всех переменных. Если на некотором наборе <tex>f(\vec{x})=0по следующему правилу: если значение некоторой переменной есть </tex>, то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем дизъюннктивном члене само значение функции можно опуститьконъюнкцию включаем саму переменную, иначе ее отрицание. В результате для произвольной функции была построена СДНФ# Все полученные конъюнкции связываем операциями дизъюнкции.}}
== Пример построения СДНФ для медианы===== Построение СДНФ для медианы от трех аргументов ===1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1</tex>.
<center>{| class="wikitable" align="left" style="width:29cm10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! |<tex> x </tex>|| <tex> y </tex>|| <tex> z </tex>|| <xyztex> \langle x,y,z \rangle </tex>|-align="center" bgcolor=#F0F0F0FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#F0F0F0FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#F0F0F0FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#F0F0F0FFFFFF
! 1 || 1 || 1 || 1
|}
</center>
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1</tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
<center>{| class="wikitable" align="left" style="width:29cm16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! |<tex> x </tex>|| <tex> y </tex>|| <tex> z </tex>|| <xyztex> \langle x,y,z \rangle </tex> || |-align="center" bgcolor=#F0F0F0FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#F0F0F0FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#F0F0F0FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#F0F0F0FFFFFF! 0 || 1 || 1 || 1 || <tex>(\overlineneg {x} \land y \land z)</tex>|-align="center" bgcolor=#F0F0F0FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#F0F0F0FFFFFF! 1 || 0 || 1 || 1 || <tex>(x \land \overlineneg {y} \land z)</tex>|-align="center" bgcolor=#F0F0F0FFFFFF! 1 || 1 || 0 || 1 || <tex>(x \land y \land \overlineneg {z})</tex>|-align="center" bgcolor=#F0F0F0FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}
</center>
3. Все полученные конъюнкции связываем операциями дизъюнкции.:
<tex>med(\langle x,y,z) \rangle = (x \land y \land z) \lor (\overlineneg {x} \land y \land z) \lor (x \land \overlineneg {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{zx_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 \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>. == См. также ==
Медиана трёх: <tex>f(x,y,z) = (x \land y \land z) \lor (\overline{x} \land y \land z) \lor (x \land \overline{y} \land z) \lor (x \land y \land \overline{z})</tex>* [[Сокращенная и минимальная ДНФ]]* [[КНФ]]
== Ссылки Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия — свободная энциклопедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Булевы функции ]]
Maintenance script
1632
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/11234...85541»

Навигация