Изменения

==Канонические формы логических формулДНФ ==Любая логическая формула задает некоторую [[булева функция{{Определение|булеву функцию]]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=Для любой булевой функции <mathtex>f(\vec{x})</mathtex> от n переменных называется , не равной тождественному нулю, существует СДНФ, ее задающая.|proof = Для любой булевой функции выполняется следующее соотношение, называемое '''совершенно дизъюктивной нормальной формой(СДНФ)разложением Шеннона''', если она обладает следующими свойствами :

# <mathtex>f(\vec {x})</math> является ДНФ= \neg x_i \wedge f(x_1, \ldots , в которой каждая элементарная конъюнкция есть конъюнкция n переменных x_{x_{i-1}},0, x₂x_{i+1},...\ldots ,x_nx_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<math/tex> за знак <tex>f(\vec{x})</mathtex>, не равной тождественному нулюполучаем следующую формулу: <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>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <mathtex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x}) = \overline x_i \bigwedge 0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(x_1,..,x_\vec{i-1x},0,x_{i+)=1}</tex>,то в соответствующем конъюнкте само значение функции можно опустить.В результате для произвольной функции была построена СДНФ.,x_n) \bigveex_i \bigwedge f(x_1,..,x_{i-1},1,x_{i+1},x_n)</math>

Данное соотношение легко проверить подстановкой всевозможных значений x== Алгоритм построения СДНФ по таблице истинности ==# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <subtex>i1 </subtex>(0 и 1). Эта формула позволяет выносить x# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <subtex>i1 </subtex> за знак , то в конъюнкцию включаем саму переменную, иначе ее отрицание.# Все полученные конъюнкции связываем операциями дизъюнкции. == Пример построения СДНФ для медианы===== Построение СДНФ для медианы от трех аргументов ===1. В таблице истинности отмечаем те наборы переменных, на которых значение функции. Последовательно вынося xравно <subtex>1</subtex>. {| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex>, x<sub/tex>||<tex>2y </subtex>,.., x||<subtex>nz </subtex> за знак || <mathtex>f(\vec{langle x}),y,z \rangle </mathtex>, получаем следующую формулу : <math> f(\vec{x}) |-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= \overline x_1 \bigwedge \overline x_2 \bigwedge ...\bigwedge \overline x_{n#FFFFFF! 0 || 1 || 1 || 1|-align="center" bgcolor=#FFFFFF| 1} \bigwedge \overline x_n \bigwedge f(|| 0 || 0,|| 0,...,|-align="center" bgcolor=#FFFFFF! 1 || 0,|| 1 || 1|-align="center" bgcolor=#FFFFFF! 1 || 1 || 0)~\bigvee~|| 1|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 1|} 2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </mathtex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x </tex>||<tex> y <math/tex>||<tex> z </tex>|| <tex>\overline x_1 langle x,y,z \bigwedge 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>(\overline x_2 neg {x} \bigwedge ... land y \bigwedge land z)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || <tex>(x \land \overline x_neg {ny} \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 \bigwedge x_n land y \bigwedge f(0,0,...,0,1land z) ~\bigvee~</mathtex>|}

3. Все полученные конъюнкции связываем операциями дизъюнкции: <mathtex>... \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})</mathtex>.

=== Построение СДНФ для медианы от пяти аргументов ==={| 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 || <mathtex>~(x_1 \land \neg {x_2} \land \bigvee~ 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 \bigwedge land \neg {x_2 } \land x_3 \bigwedge ... land \bigwedge x_neg {nx_4} \land x_5)</tex>|-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || 0 || 1|| <tex>(x_1 \land \neg {x_2} \bigwedge land x_3 \overline x_n land x_4 \bigwedge fland \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 \bigvee~land x_5)</mathtex>|}

<mathtex>\langle x_1 , x_2, x_3, x_4, x_5 \rangle = (\bigwedge overline {x_1} \land \overline {x_2 } \bigwedge ... 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 \bigwedge x_overline {n-1x_4} \bigwedge x_n land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \bigwedge flor (1,1,...,1x_1 \land x_2 \land x_3 \land x_4 \land x_5) </mathtex>.

Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то ==Примеры СДНФ для функции от n переменных мы имеем 2некоторых функций==Стрелка Пирса: <suptex>nx \downarrow y = (\neg {x} \land \neg {y})</suptex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из 2 Исключающее или: <suptex>n</sup> возможных наборов значений n переменных. Если на некотором наборе <math>fx \oplus y \oplus z = (\vecoverline{x}\land \overline{y} \land z)=0</math>, то весь соответствующий дизъюнктивный член также равен 0 и из представления данной функции его можно исключить. Если же <math> f\lor (\vecoverline{x} \land y \land \overline{z})=1\lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</mathtex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена '''СДНФ''' == См.также == * [[Сокращенная и минимальная ДНФ]]* [[КНФ]] ==Алгоритм построения СДНФ по таблице истинностиИсточники информации ==# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу * [http: если значение некоторой переменной есть 1//dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, то в конъюнкцию включаем саму переменную, иначе ее отрицание Ю.Б.Фарфоровская — Дискретная математика]# Все полученные конъюнкции связываем операциями дизъюнкции.[[Категория: Дискретная математика и алгоритмы]] [[Категория: Булевы функции ]]