Изменения

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

ДНФ

7685 байт добавлено, 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 \neg {z})</tex>.
== СДНФ ==
{{Определение
|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>.
 
 
{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':
 
<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, \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 \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 \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 \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>
{{Определение|definition = Формула Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>f(\vec{x})n</tex> от n переменных называется '''совершенно дизъюктивной нормальной формой (СДНФ) ''', если мы имеем <tex>f(\vec x)2^n</tex> является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> переменных возможных наборов значений <tex>x_1n </tex>, переменных. Если на некотором наборе <tex>x_2f(\vec{x})=0</tex>,то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить...,Если же <tex>x_nf(\vec{x})=1</tex>, причем на <tex>i</tex>-ом месте этой конъюнкции стоит <tex>i</tex>-ый термто в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}
==Теорема об Алгоритм построения СДНФпо таблице истинности =='''Теорема''' # В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.# Все полученные конъюнкции связываем операциями дизъюнкции. == Пример построения СДНФ для медианы===== Построение СДНФ для медианы от трех аргументов ===1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>. {| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>|-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0|-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 1|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1|-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 1|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 1|} 2. Для любой булевой функции каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание. {| class="wikitable" style="width:16cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> || |-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 1 || <tex>f(\vecneg {x}\land y \land z)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>|-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>|} 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>. === Построение СДНФдля медианы от пяти аргументов ==={| 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>fx \downarrow y = (\vecneg {x}) = \overline x_i land \wedge f(x_1,..,x_neg {i-1y},0,x_{i+1},..,x_n) \veex_i \wedge f(x_1,..,x_{i-1},1,x_{i+1},x_n)</tex>.
Данное соотношение легко проверить подстановкой всевозможных значений Исключающее или: <tex>x_i</tex>(0 и 1). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>fx \oplus y \oplus z = (\vecoverline{x}\land \overline{y} \land z)</tex>, получаем следующую формулу : <tex> f\lor (\vecoverline{x}) = \overline x_1 land y \wedge land \overline x_2 {z}) \wedge ...lor (x \wedge land \overline x_{n-1y} \wedge land \overline x_n {z}) \wedge flor (0,0,...,0,0x \land y \land z)~\vee~</tex>.
<tex>\overline x_1 \wedge \overline x_2 \wedge == См... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~</tex>также ==
<tex>... </tex>* [[Сокращенная и минимальная ДНФ]]* [[КНФ]]
<tex>~\vee~ x_1 \wedge x_2 \wedge ==Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]* [http://dvo. \wedge x_{n-1} \wedge \overline x_n \wedge f(1,1,sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин,1,0) ~\vee~</tex> Ю.Б. Фарфоровская — Дискретная математика]
<tex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </tex>[[Категория: Дискретная математика и алгоритмы]]
Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений n переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий дизъюнктивный член также равен 0 и из представления данной [[Категория: Булевы функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена '''СДНФ'''.==Алгоритм построения СДНФ по таблице истинности==# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.# Все полученные конъюнкции связываем операциями дизъюнкции.]]
Maintenance script
1632
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/3500...85541»

Навигация