Изменения

{{Определение|definition='''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''') от , англ. ''nBoolean function'' ) от <tex>n</tex> переменных — в дискретной математике отображение ''B''<suptex>''B^n''\rightarrow B</suptex> → ''B'', где ''<tex>B'' = \{0,1\} </tex> — ''булево множество''. }} Элементы булева множества <tex>1 </tex> и <tex>0 </tex> обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла.Элементы декартова произведения ''B''<suptex>''B^n''</suptex> называют ''булевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается ''P''<subtex>2P_2</subtex>, а от ''n'' переменных — ''P''<subtex>2P_2(n)</subtex>(''n''). Булевы функции названы так по фамилии математика Джорджа Буля. 

{{Определение|definition='''А́рность''' (англ. ''arity'') функции — количество ее аргументов.}} Каждая булева функция арности ''<tex>n'' </tex> полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины ''<tex>n''</tex>. Число таких векторов равно 2<suptex>''2^n''</suptex>. Поскольку на каждом векторе булева функция может принимать значение либо <tex>0</tex>, либо <tex>1</tex>, то количество всех ''n''-арных булевых функций равно 2<suptex>{2^2^{''}^n''</suptex>}. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

   {| class="wikitable" align="center" style="widthcolor:10cmblue; background-color:#ffffcc;" bordercellpadding=1"10"

!colspan="6"|Таблица истинности|-align="center" bgcolor=#EEEEFF! x<subtex>1x_1</subtex> || x<subtex>2x_2</subtex> || … || x<subtex>n\ldots</subtex> || f(x<subtex>1x_n</subtex>,x|| <sub>2</subtex>f(x_1,x_2,…\ldots,x<sub>nx_n)</subtex>)|-align="center" bgcolor=#F0F0F0| <tex>0 </tex> || <tex>0 </tex> || … <tex>\ldots</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(0,0,…\ldots,0)</tex>|-align="center" bgcolor=#F0F0F0| <tex>1 </tex> || <tex>0 </tex> || … <tex>\ldots</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(1,0,…\ldots,0)</tex>|-align="center" bgcolor=#F0F0F0| <tex>0 </tex> || <tex>1 </tex> || … <tex>\ldots</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(0,1,…\ldots,0)</tex>|-align="center" bgcolor=#F0F0F0| <tex>1 </tex> || <tex>1 </tex> || … <tex>\ldots</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(1,1,…\ldots,0)</tex>|-align="center" style="height:1.2cm" bgcolor=#F0F0F0| <mathtex>\vdots</mathtex> || <mathtex>\vdots</mathtex> || <mathtex>\vdots</mathtex> || <mathtex>\vdots</mathtex> || bgcolor=white | <mathtex>\vdots</mathtex>|-align="center" bgcolor=#F0F0F0| <tex>0 </tex> || <tex>1 </tex> || … <tex>\ldots</tex> || <tex>1 </tex> || bgcolor=white | <tex>f(0,1,…\ldots,1)</tex>|-align="center" bgcolor=#F0F0F0| <tex>1 </tex> || <tex>1 </tex> || … <tex>\ldots</tex> || <tex>1 </tex> || bgcolor=white | <tex>f(1,1,…\ldots,1)</tex>

Практически все булевы функции малых арностей (<tex>0, 1, 2 </tex> и <tex>3</tex>) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной''(англ. ''dummy variable'').

При ''<tex>n'' = 0 </tex> количество булевых функций равно 2<suptex>{2^2^{}^0}</sup> = 2<sup>^1= 2</suptex> = 2, первая из них тождественно равна <tex>0</tex>, а вторая <tex>1</tex>. Их называют булевыми константами — тождественный нуль и тождественная единица.

При ''<tex>n'' = 1 </tex> число булевых функций равно 2<suptex>{2^{^2}^1}</sup> = 2<sup>^2= 4</suptex> = 4.

 <center>  {| borderclass="1wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="5"|Функции от одной переменной|-align="center" bgcolor=#FFF8DC!x|! width="12%" | <tex>0</tex>|! width="12%" | <tex>x</tex>|! width="12%" | &not;<tex>\neg x</tex>|! width="12%" | <tex>1</tex>

|<tex>0</tex>||<tex>0</tex>||<tex>1</tex>||<tex>1</tex>

|<tex>0</tex>||<tex>1</tex>||<tex>0</tex>||<tex>1</tex>|-align="center" bgcolor=#EEEEFF ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save0|Сохраняет 0]]|1✓||1✓||0||0|-align="center" bgcolor=#EEEEFF ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]|0||1✓||0||1✓|-align="center" bgcolor=#EEEEFF ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]|0||1✓||1✓||0|-align="center" bgcolor=#EEEEFF ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]|1✓||1✓||0||1✓|-align="center" bgcolor=#EEEEFF ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]|1✓||1✓||1✓||1✓

<center>{| class="wikitable" borderalign=1"center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center"

!bgcolor=#EEEEFF |<tex>0</tex> |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>

!bgcolor=#EEEEFF |''x̅'', ¬''x'', ''<tex>x'''</tex> |отрицание, логическое <font color="НЕТblack">тождественная функция, логическое "НЕДА", "НИ", "NOT"(англ.), "NOYES"(англ.)</font>

!bgcolor=#EEEEFF |''<tex>\bar x,\ \neg x,\ x''</tex> |тождественная функция<font color="black">отрицание, логическое "ДАНЕТ", "YESНЕ", "НИ", "NOT"(англ.), "NO"(англ.)</font>

!bgcolor=#EEEEFF |<tex>1</tex> |<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>

При ''<tex>n'' = 2 </tex> число булевых функций равно 2<suptex>{2^{^2}^2}</sup> = 2<sup>^4= 16</suptex> = 16.

<center>{| borderclass="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="118"|Функции от двух переменных:|-align="center" bgcolor=#FFF8DC !<font color="black">x</font>||<font color="black">y</font>|! width="5%" | <tex>0</tex>|! width="5%" | &and;<tex>x \land y</tex>|! width="5%" | <tex>x \nrightarrowy</tex>|! width="5%" | <tex>x</tex>|! width="5%" | <tex>x \nleftarrowy</tex>|! width="5%" | <tex>y</tex>|! width="5%" | &<tex>x \oplus;y</tex>|! width="5%" | &or;<tex>x \lor y</tex>|! width="5%" | &darr;<tex>x \downarrow y</tex>|! width="5%" | &harr;<tex>x = y</tex>|! width="5%" | &not;<tex>\neg y</tex>|! width="5%" | &larr;<tex>x \leftarrow y</tex>|! width="5%" | &not;<tex>\neg x</tex>|! width="5%" | &rarr;<tex>x \rightarrow y</tex>|! width="5%" | &nabla;<tex>x \triangledown y</tex>|! width="5%" | <tex>1</tex>

!<font color="black">0</font>||<font color="black">0</font>

!<font color="black">0</font>||<font color="black">1</font>

!<font color="black">1</font>||<font color="black">0</font>

!<font color="black">1</font>||<font color="black">1</font>

!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save0|Сохраняет 0]]</font>|1✓||1✓||1✓||1✓||1✓||1✓||1✓||1✓||0||0||0||0||0||0||0||0

!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]</font>|0||1✓||0||1✓||0||1✓||0||1✓||0||1✓||0||1✓||0||1✓||0||1✓

!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]</font>|0||0||0||1✓||0||1✓||0||0||0||0||1✓||0||1✓||0||0||0

!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]</font>|1✓||1✓||0||1✓||0||1✓||0||1✓||0||0||0||0||0||0||0||1✓

!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]</font>|1✓||0||0||1✓||0||1✓||1✓||0||0||1✓||1✓||0||1✓||0||0||1✓

<center>{| class="standardwikitable" borderalign=1"center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center"

!bgcolor=#EEEEFF<tex>0</tex> |0 |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>

!bgcolor<tex>x \land y</tex> |align =#EEEEFFcenter|''<tex>x \cdot y,\ xy,\ x \And y,\ x'' ↓ ''\ AND\ y'', ''\ AND(x'' ИЛИ-НЕ '', y''), ИЛИ-НЕ\ min(''x'',''y''), ''x'' NOR ''</tex> <font color="black">И</font> <tex>y'', NOR</tex> <font color="black">И</font><tex>(''x'',''y'')</tex> |НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба<font color="black">2И, стрелка Пи́рсаконъюнкция</font>

!bgcolor<tex>x \nrightarrow y</tex> |align =#EEEEFFcenter|''<tex>x'' < ''> y'', <math>\ \neg</math>(''x'' ← ''\rightarrow y''), ''\ x'' LT ''\ GT\ y'', LT\ GT(''x'',''\ y'')</tex> |меньше<font color="black">больше, инверсия обратной прямой импликации]</font>

!bgcolor<tex>x</tex> |align =#EEEEFFcenter|''x̅'', НЕ1<tex>YES1(''x'',''y''), NOT1</tex> <font color="black">ДА1</font><tex>(''x'',''y''), ''x''', ¬''x''</tex> |отрицание (негация, инверсия) первого операнда<font color="black">первый операнд</font>

!bgcolor<tex>x \nleftarrow y</tex> |align =#EEEEFFcenter|''<tex>x'' > ''< y'', <math>\ \neg</math>(''x'' → ''\leftarrow y''), ''\ x'' GT ''\ LT\ y'', \ GTLT(''x'',''y'')</tex> |больше<font color="black">меньше, инверсия прямой обратной импликации</font>

!bgcolor<tex>y</tex> |align =#EEEEFFcenter|''y̅'', НЕ2<tex>YES2(''x'',''y''), NOT2</tex> <font color="black">ДА2</font><tex>(''x'',''y''), ''y''', ¬''y''</tex> |отрицание (негация, инверсия) второго операнда<font color="black">второй операнд</font>

!bgcolor=#EEEEFF|''<tex>x'' ⊕ ''\oplus y'', ''x'' +<sub/tex>2 |align = center|</subtex> ''x + _2 y'', ''\ x'' ≠ ''\not = y'', ''\ x'' >< ''y'', ''\ x'' <> ''y'', ''\ x'' \ XOR ''\ y'', \ XOR(''x'',''y'')</tex> |<font color="black">сложение по модулю 2, не равно, ксор, исключающее «или»</font>

!bgcolor=#EEEEFF|''<tex>x'' \lor y<nowiki/tex> |align = center|</nowikitex> ''x + y,\ x\ OR\ y'', ''\ OR(x'' NAND '',y''), NAND\ max(''x'',''y''), ''</tex> <tex>x'' И-НЕ ''</tex><font color="black">ИЛИ </font><tex>y'', И-НЕ</tex><font color="black"> ИЛИ</font><tex>(''x'',''y'') </tex> |НЕ-2И<font color="black">2ИЛИ, 2И-НЕ, антиконъюнкция, Штрих Шефферадизъюнкция</font>

!bgcolor=#EEEEFF|''<tex>x'' &amp; ''\downarrow y'', ''x'' · ''y'', ''x''<span/tex> |align = center|</spantex>''y'', ''x'' ∧ ''\ NOR\ y'', ''x'' AND ''y'', AND\ NOR(''x'',''y''), ''</tex> <tex>x'' И ''</tex><font color="black">ИЛИ-НЕ</font> <tex>y'', И</tex> <font color="black">ИЛИ-НЕ</font><tex>(''x'',''y''), min(''x'',''y'') </tex> |2И<font color="black">НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, конъюнкциястрелка Пи́рса</font>

!bgcolor<tex>x = y</tex> |align =#EEEEFFcenter|''<tex>x'' ≡ ''\equiv y'', ''x'' = ''y'', ''x'' EQV ''y'', EQV(''x'',''y''), ''x'' ~ ''\sim y'', ''x'' ↔ ''\leftrightarrow y''</tex> |<font color="black">равенство, эквивалентность</font>

!bgcolor<tex>\neg y</tex> |align =#EEEEFFcenter|''<tex>NOT2(x, y''), ДА2(''x'\ y',''\ \bar{y'')}, YES2</tex> <font color="black">НЕ2</font><tex>(''x'',''y'')</tex> |второй операнд<font color="black">отрицание (негация, инверсия) второго операнда</font>

!bgcolor<tex>x \leftarrow y</tex> |align =#EEEEFFcenter|''x'' → ''y'', ''<tex>x'' ≤ ''\geq y'', ''\ x'' ⊃ ''\subset y'', ''\ x'' LE ''\ GE\ y'', LE\ GE(''x'',''y'')</tex> |меньше <font color="black">больше или равно, прямая (материальная) обратная импликация (от первого второго аргумента ко второмук первому)</font>

!bgcolor<tex>\neg x</tex> |align =#EEEEFFcenter|''<tex>NOT1(x'', ДА1(''y),\ x'',''y'')\ \bar{x}, YES1</tex> <font color="black">НЕ1</font><tex>(''x'',''y'')</tex> |первый операнд<font color="black">отрицание (негация, инверсия) первого операнда</font>

!bgcolor<tex>x \rightarrow y</tex> |align =#EEEEFFcenter|''<tex>x'' ← ''\leq y'', ''\ x'' ≥ ''\supset y'', ''\ x'' ⊂ ''\ LE\ y'', ''x'' GE ''y'', GE\ LE(''x'',''y'')</tex> |больше <font color="black">меньше или равно, обратная прямая (материальная) импликация (от второго первого аргумента к первомуко второму)</font>

!bgcolor<tex>x \triangledown y</tex> |align =#EEEEFFcenter|''<tex>x'' ∨ ''\mid y'', ''\ x'' + ''\ NAND\ y'', ''x'' ИЛИ ''y'', ИЛИ\ NAND(''x'',''y''), ''</tex> <tex>x'' OR ''</tex> <font color="black">И-НЕ </font><tex>y'', OR(''x'',''y''), max</tex> <font color="black">И-НЕ</font><tex>(''x'',''y'')</tex> |2ИЛИ<font color="black">НЕ-2И, 2И-НЕ, антиконъюнкция, дизъюнкцияШтрих Шеффера</font>

!bgcolor=#EEEEFF<tex>1</tex> |1 |<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>

При ''<tex>n'' = 3 </tex> число булевых функций равно 2<sup>2³</suptex> {2^2}^3 = 2<sup>^8= 256</suptex> = 256. Некоторые из них определены в следующей таблице:<center>{| class="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" bordercellpadding=1"10"|+!colspan="14"|Таблица истинности некоторых тернарных функций |-align="center" !class="dark" style="font-weight:normal" bgcolor=#EEEEFF| ''<tex>x''</tex> !class="dark" style="font-weight:normal" bgcolor=#EEEEFF| ''<tex>y''</tex> !class="dark" style="font-weight:normal" bgcolor=#EEEEFF| ''<tex>z''</tex> !style="font-weight:normal" bgcolor=#EEEEFF| ''<tex>x''↓''\downarrow y''↓''\downarrow z''</tex> !style="font-weight:normal" bgcolor=#EEEEFF| <mathtex>\neg</math>(≥2\geq 2(x,y,z))</tex> !style="font-weight:normal" bgcolor| <tex>x \not = y \not =#EEEEFF| x≠y≠zz</tex> !style="font-weight:normal" bgcolor=#EEEEFF| x<nowiki>|</nowikitex>x \mid y<nowiki>|\mid z</nowikitex>z !style="font-weight:normal" bgcolor=#EEEEFF| <tex>min(x,y,z)</tex> !style="font-weight:normal" bgcolor=#EEEEFF| <tex>x=y=z</tex> !style="font-weight:normal" bgcolor=#EEEEFF| ''<tex>x''⊕''\oplus y''⊕''\oplus z''</tex> !style="font-weight:normal" bgcolor=#EEEEFF| ≥2<tex>\geq 2(x,y,z)</tex> !style="font-weight:normal" bgcolor=#EEEEFF| ''f<subtex>1f_1</subtex>'' !style="font-weight:normal" bgcolor=#EEEEFF| ''f<subtex>2f_2</subtex>'' !style="font-weight:normal" bgcolor=#EEEEFF| <tex>max(x,y,z)</tex>

!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>

!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>

<center>{| class="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" bordercellpadding=1"10"|+ |-align="center"

!bgcolor=#EEEEFF|x<mathtex>x \downarrow</math>y<math>\downarrowz</mathtex>z |align = center|<mathtex>\downarrow</math>(x,y,z) = Webb₂Webb_2 (x,y,z)</tex> |<font color="black"> 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса</font>

!bgcolor=#EEEEFF|<mathtex>\neg</math>(> = \geq 2(x,y,z))</tex> | |<font color="black">Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией</font>

!bgcolor<tex>x \not =#EEEEFFy \not = z</tex> |x≠y≠z align = center|<tex>[≠\not =(x,y,z)] = NE(x,y,z,v)</tex> |<font color="black">Неравенство</font>

!bgcolor=#EEEEFF|x<mathtex>x \mid</math>y<math>\midz</mathtex>z |align = center|<mathtex>\mid</math>(x,y,z)</tex> |<font color="black">3-И-НЕ, штрих Шеффера</font>

!bgcolor=#EEEEFF|<tex>x&\land y&\land z </tex> |align = &center|<tex>\land (x,y,z) = (x \ AND \ y \ AND \ z) = AND(x,y,z) = min(x И ,y И ,z) = И<br/> (x,</tex> <font color="black"> И</font><tex> y,</tex> <font color="black"> И</font><tex> z) = min</tex> <font color="black">И</font><tex>(x,y,z)</tex> |<font color="black">3-И, минимум</font>

!bgcolor=#EEEEFF|(<tex>x=y=z) </tex> |align = center|<tex>[=(x,y,z)] = EQV(x,y,z,v)</tex> |<font color="black">Равенство</font>

!bgcolor=#EEEEFF|x⊕<subtex>2x \oplus y \oplus z</subtex>y⊕<sub>2 |align = center|</subtex>z = x+₂_2 y+₂_2 z = ⊕₂\oplus (x,y,z) = +₂_2 (x,y,z)</tex> |<font color="black">Тернарное сложение по модулю 2</font>

!bgcolor=#EEEEFF|[<tex>=\geq 2(x,y,z)] </tex> |align = center|<tex>(x </tex> <font color="black">И </font> <tex>y) </tex><font color="black">ИЛИ </font><tex>(y </tex><font color="black"> И </font><tex> z) </tex><font color="black"> ИЛИ </font> <tex>(z </tex><font color="black">И </font><tex> x)</tex> |<font color="black">переключатель по большинству, 3-ППБ, мажоритарный клапан</font>

!bgcolor=#EEEEFF|''f<subtex>1f_1</subtex>'' | |<font color="black">Разряд займа при тернарном вычитании</font>

!bgcolor=#EEEEFF|''f<subtex>2f_2</subtex>'' | |<font color="black">Разряд переноса при тернарном сложении</font>

!bgcolor=#EEEEFF|(<tex>x+y+z) </tex> |align = center|<tex>+(x,y,z) = max(x,y,z) = (x \ OR \ y \ OR \ z) = OR(x,y,z) = (x </tex> <font color="black">ИЛИ </font><tex> y </tex><font color="black"> ИЛИ </font><tex> z) = </tex><font color="black"> ИЛИ</font><tex>(x,y,z)</tex> |<font color="black">3-ИЛИ, максимум</font>

 </center> == Полные системы = Представление функции формулой === {{Определение|definition=Если выбрать некоторый набор [[Определение булевой функции|булевых функций ]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой''' (англ. ''formula'').}} Например, если <tex>A ==\left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>

 {{Определение|definition=Две булевы функции '''тождественны ''' (англ. ''identical'') друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. }}Тождественность функций f и g можно записать, например, так:<br /><mathtex>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</mathtex>

| <mathtex>\overline{0}=1</mathtex> || <mathtex>\overline{1}=0</mathtex> || <mathtex>\overline{\overline{x}}=x</mathtex>|| <mathtex>xyx \land y=yxy \land x\!</mathtex> || <mathtex>x\lor y=y \lor x</mathtex>

|| <mathtex>0x0 \land x=0\!</mathtex> || <mathtex>1x1 \land x=x\!</mathtex> || <mathtex>0\lor x=x</mathtex> || <mathtex>1\lor x=1</mathtex> || <mathtex>xxx \land x=x\lor x=x</mathtex>

{| style="width:15cm9cm"

| <mathtex>x\land \overline{x}=0</mathtex> || <mathtex>x\lor\overline{x}=1</mathtex>

| <mathtex>\overline{x\cdot land y}=\overline{x}\lor\overline{y}</mathtex>|| <mathtex>\overline{x}\cdotland\overline{y}=\overline{x\lor y}</mathtex> || (законы де Моргана)

<mathtex>x\land (y\lor z)=xy(x \land y)\lor xz(x \land z)</mathtex><br /><mathtex>x\lor yz(y \land z)=(x\lor y)\land (x\lor z)</mathtex> (дистрибутивность конъюнкции и дизъюнкции)

Функция <math>g(x_1,x_2,\dots,x_n)</math> называется двойственной функции <math>f(x_1,x_2,\dots,x_n)</math>, если <math>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</math>. Легко показать, что Если в этом равенстве f и g можно поменять местамибулевом тождестве заменить каждую функцию на двойственную ей, то есть функции f и g двойственны друг другуснова получится верное тождество. Из простейших функций двойственны В приведённых выше формулах легко найти двойственные друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себепары.

Если === Суперпозиции ==={{main|Суперпозиции}}{{Определение|definition ='''Суперпозиция функций, композиция функций''' (англ. ''function composition'') {{---}} функция, полученная из некоторого множества функций путем подстановки одной функции в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождестводругую или отождествления переменных. В приведённых выше формулах легко найти двойственные }}Множество всех возможных не эквивалентных друг другу парысуперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций. Пусть нам дан некоторый набор булевых функций <tex>K</tex>. Получить новую функцию, являющеюся композицией функций из <tex>K</tex>, мы можем следующими способами:*Подстановкой одной функции в качестве некоторого аргумента для другой;*Отождествлением аргументов функций.

Система {{main|Теорема Поста о полной системе функций}}{{Определение|definition='''Замыкание множества функций''' (англ. ''сlosure'') {{---}} подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества.}}{{Определение|id=def1|definition=Множество булевых функций называется '''полнойсистемой'''(англ. ''complete set''), если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы этого множества совпадает с множеством всех функций.}}Американский математик Эмиль Пост <ref> [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D1%82,_%D0%AD%D0%BC%D0%B8%D0%BB%D1%8C_%D0%9B%D0%B5%D0%BE%D0%BD Эмиль Пост]</ref> сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:* функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,* самодвойственныые функции <Tex>S</Tex>,* монотонные функции <Tex>M</Tex>,* линейные функции <mathTex>P_2L</mathTex>.

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы Набор булевых функций:* Функции, сохраняющие константу <mathtex>T_0K</mathtex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <math>T_1</math>;* Самодвойственные функции <mathtex>S</math>;* Монотонные функции <math>,M</math>;* Линейные функции <math>,L</math>.Им было доказано, что любой замкнутый класс булевых функцийT_0, не совпадающий с <math>P_2T_1 </mathtex>, целиком содержится иными словами, когда в одном из этих пяти так называемых ''предполных классов''нем имеется хотя бы одна функция, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснениюсохраняющая ноль, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся хотя бы одна функция, не входящая в негосохраняющая один, то такая система будет полнойхотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и с помощью входящих в неё хотя бы одна нелинейная функция.== Представление булевых функций можно будет получить любую другую булеву функцию.==

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.== Представление булевых функций ==Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <mathtex>\Sigma = \{f_1,\ldots,f_n\}</mathtex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <mathtex>\Sigma</mathtex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

{{main|ДНФ}}{{Определение|definition =''Совершенной дизъюнктивной нормальной формой'Дизъюнктивная нормальная форма (ДНФ)' или ''СДНФ(англ. '' относительно некоторого заданного конечного набора переменных называется такая ДНФdisjunctive normal form, у которой в каждую конъюнкцию входят все переменные данного набораDNF'') {{---}} нормальная форма, причём в одном и том же порядкекоторой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов. Например: <math>a \overline{b} c\lor a b c\lor\overline{a} b\overline{c}</math>Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ. '''Примеры ДНФ:'''

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора <mathtex>b=f(b_1x,b_2y,\ldots,b_nz)</math> построить конъюнкцию <math>x_1^{b_1} x_2^{b_2}\ldots x_n^{b_n}</math>, где <math>x_i^1 = x_i</math> <math>x_i^0 = \overline{x_i}</math>. Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации <math>(x\to y</math> результатом является <math>\overline{x} land y ) \lor \overline{x}\, \overline{(y}\lor x y</math>, что можно упростить до <math>land \overlineneg {xz}\lor y)</mathtex>.

{{main|КНФ}}{{Определение|definition ='''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.}}Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ. '''Пример КНФ:''' <tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex> <tex>f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)</tex> <tex>f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x}) определяется двойственно к ДНФ. </tex> === Полином Жегалкина === {{main|Полином Жегалкина}}{{Определение|definition ='''Полином Жегалкина'Простой дизъюнкцией'' или (англ. ''дизъюнктомZhegalkin polynomial'' называется дизъюнкция одной ) {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или нескольких переменных или их отрицаний. }}Полином Жегалкина имеет следующий вид: <tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11\ldots1} x_1 x_2 \ldots x_n </tex> С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкцийсвою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным. '''Примеры:''' <tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex>

''Совершенной конъюнктивной нормальной формой'' <tex>f(СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФx_1, у которой в каждую дизъюнкцию входят все переменные данного набораx_2, причём в одном и том же порядке. Поскольку (Сx_3)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».= x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex>

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:<centertex><math>a f(b\lor cx_1,x_2,x_3,x_4)= 1 \to a boplus x_1 \lor a c</math></center>которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило<center><math>aoplus x_4 \lor b coplus x_1 x_2 \to (a oplus x_1 x_4 \lor b)(a oplus x_2 x_4 \lor c)</math>oplus x_1 x_2 x_4 </centertex>выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

{{Определение|definition === Полиномы Жегалкина ==='''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.}}Приведение тождественной функции есть '''выражение булевой функции через другие'''.

Полином Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина это полином с коэффициентами вида 0 и 1— способы выражения одних булевых функций через другие.{{Пример|example=Выразим следующие функции через систему функций <tex>\{\land, где в качестве произведения берется конъюнкция\lor, а в качестве сложения исключающее или\lnot \} </tex>.

<br tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex> <tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex> <mathtex>P \langle x, y, z \rangle = a \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \oplus lor z \bigoplus_right )</tex>}}=== Подстановка одной функции в другую === {{Определение|definition ='''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>: <center><tex>h(x_{1}, \beginldots, x_{arrayn+m-1}) = f(x_{c1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})</tex></center>}} Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя. При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки: {| |1. <tex> x_{1}, \leq i_1ldots, x_{i-1}</tex> |{{---}} аргументы функции <tex>f< /tex> до подставленного значения функции <tex>g</tex> |- |2. <tex> x_{i}, \ldots, x_{i+m-1} </tex> |{{---}} используются как аргументы для вычисления значения функции <i_ktex>g(y_{1}, \leq ldots, y_{m})</tex> |- |3. <tex> x_{i+m}, \ldots, x_{n +m-1} </tex> |{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex> |}{{Пример|example=Исходные функции:#<tex> f(a,b) = a \vee b </tex>#<tex> g(a) = \neg a </tex> k<tex> h(a,b) = f(a,g(b)) = a \invee \overlineneg b </tex> {{0---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,nb)=a \leftarrow b</tex>.}} === Отождествление переменных ==={{Определение|definition='''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента: <center><tex>h(x_{1}, \endldots, x_{arrayj-1}, x_{j+1}a_{i_1,\ldots,i_kx_{n}) = f(x_{1}, \wedge ldots, x_{i_1i}\wedge, \ldots \wedge , x_{i_kj-1}, \quad ax_{i}, a_x_{i_1j+1},\ldots,i_kx_{n})</tex></center>}}Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.{{Пример|example=<tex> f(a,b) = a \in vee b </tex> {{---}} исходная функция <tex> h(a) = a \vee a </tex> {{0---}} функция с отождествленными первым и вторым аргументами Очевидно,в данном примере мы получили функцию <tex>P_{1\}.</mathtex>{{---}} проектор единственного аргумента.}}

<tex>k =2 \Rightarrow X = Литература \{ \lnot, \land \}</tex>; <tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>; <tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>; Докажем, что последняя система является базисом: <tex> 0 \notin T_1</tex>; <tex> 1 \notin T_0</tex>; <tex> x\land y \notin L\ и\ S</tex>; <tex> x\oplus y\oplus z \notin M</tex>  (доказывается с помощью таблицы истинности).}} == См. также ==* [[Специальные формы КНФ]]* [[Сокращенная и минимальная ДНФ]]* [[Пороговая функция]]* [[Cумматор]]* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций. Теорема Поста о полной системе функций]]== Примечания ==<references/> == Источники информации ==

* [http[Категория://mathcyb.cs.msu.su/books.html Учебные пособия кафедры математической кибернетики ВМиК МГУДискретная математика и алгоритмы]]* [http[Категория://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедияБулевы функции ]]