1632
правки
Изменения
ДНФ
,rollbackEdits.php mass rollback
==Канонические формы логических формулДНФ ==Любая логическая формула задает некоторую [[булева функция{{Определение|булеву функцию]]definition ='''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. Но для всякой [[булева функция|булевой функции]] можно привести бесконечно много формул ее представляющих''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Одной из задач алгебры логики является построение }}Простая конъюнкция* '''канонических формполная''', если в неё каждая переменная (т.е формул построенных по определенному правилуили её отрицание)входит ровно <tex> 1 </tex> раз;* '''монотонная''', если она не содержит отрицаний переменных.
Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x}) = \overline x_i \wedge f(x_1,..,x_{i-1},0</tex>,x_{i+1},то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить..,x_n) \veex_i \wedge Если же <tex> f(x_1,..,x_\vec{i-1x},1,x_{i+)=1},x_n)</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.}}
{| class="wikitable" style="width:16cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex>\overline x_1 langle x,y,z \wedge 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} \wedge ... land y \wedge 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 \wedge x_n land y \wedge f(0,0,...,0,1land z) ~\vee~</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 \vee~ neg {x_4} \land x_5)</tex>|-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 1 || 0 || 1 || <tex>(x_1 \wedge land x_2 \wedge ... land \wedge x_neg {nx_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} \wedge land x_4 \land x_5)</tex>|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \overline x_n land x_3 \wedge fland \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 \vee~land x_5)</tex>|}
<tex>\langle x_1 , x_2, x_3, x_4, x_5 \rangle = (\wedge overline {x_1} \land \overline {x_2 } \wedge ... 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 \wedge x_overline {n-1x_4} \wedge x_n land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \wedge flor (1,1,...,1x_1 \land x_2 \land x_3 \land x_4 \land x_5) </tex>.