1632
правки
Изменения
м
|x!<mathtex>x \downarrow</math>y<math>\downarrowz</mathtex>z |align = center|<mathtex>\downarrow</math>(x,y,z) = Webb<sub>2</sub>Webb_2 (x,y,z)</tex> |<font color="black"> 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса</font>
|!<mathtex>\neg(> = \geq 2(x,y,z))</mathtex> | |<font color="black">Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией</font>
|x!<mathtex>x \mid</math>y<math>\midz</mathtex>z |align = center|<mathtex>\mid</math>(x,y,z)</tex> |<font color="black">3-И-НЕ, штрих Шеффера</font>
|!<tex>x&\land y&\land z </tex> |align = ¢er|<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>
|(!<tex>x=y=z) </tex> |align = center|<tex>[=(x,y,z)] = EQV(x,y,z,v)</tex> |<font color="black">Равенство</font>
|x⊕!<subtex>2x \oplus y \oplus z</subtex>y⊕ |align = center|<subtex>2</sub>z = x+<sub>2</sub>_2 y+<sub>2</sub>_2 z = ⊕<sub>2</sub>\oplus (x,y,z) = +<sub>2</sub>_2 (x,y,z)</tex> |<font color="black">Тернарное сложение по модулю 2</font>
|[!<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>
|''f!<subtex>1f_1</subtex>'' | |<font color="black">Разряд займа при тернарном вычитании</font>
|''f!<subtex>2f_2</subtex>'' | |<font color="black">Разряд переноса при тернарном сложении</font>
|(!<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 /><tex>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</tex> Просмотрев таблицы истинности булевых функций, легко получить такие тождества:{| style="width:15cm"|-| <tex>\overline{0}=1</tex> || <tex>\overline{1}=0</tex> || <tex>\overline{\overline{x}}=x</tex>|| <tex>x \land y=y \land x\!</tex> || <tex>x\lor y=y \lor x</tex>|-|| <tex>0 \land x=0\!</tex> || <tex>1 \land x=x\!</tex> || <tex>0 \lor x=x</tex> || <tex>1\lor x=1</tex> || <tex>x \land x=x \lor x=x</tex>
rollbackEdits.php mass rollback
{{Определение|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<sup>''}^n''</suptex></sup>. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
<center>
{| 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>
|}
</center>
Практически все булевы функции малых арностей (<tex>0, 1, 2 </tex> и <tex>3</tex>) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной''(англ. ''dummy variable'').
=== Нульарные функции ===
При ''<tex>n'' = 0 </tex> количество булевых функций сводится к двум 2равно <suptex>{2^2<sup>}^0</sup></sup> = 2<sup>^1= 2</suptex> = 2, первая из них тождественно равна <tex>0</tex>, а вторая <tex>1</tex>. Их называют булевыми константами — тождественный нуль и тождественная единица.
=== Унарные функции ===
При ''<tex>n'' = 1 </tex> число булевых функций равно 2<suptex>{2<sup>^2}^1</sup></sup> = 2<sup>^2= 4</suptex> = 4. Определение этих функций содержится в следующей таблице.
Таблица значений булевых функций от одной переменной:
<center> {| class="wikitable" border=1 !classalign="darkcenter" style="fontcolor: blue; background-weightcolor:normal#ffffcc;" bgcolorcellpadding=#EEEEFF "10"| ''x''+ !stylecolspan="font5"|Функции от одной переменной|-weight:normalalign="center" bgcolor!|! width=#EEEEFF "12%" | <tex>0</tex> |!stylewidth="font-weight:normal12%" bgcolor=#EEEEFF | ''x̅''<tex>x</tex> |!stylewidth="font-weight:normal12%" bgcolor=#EEEEFF | ''<tex>\neg x''</tex> |!stylewidth="font-weight:normal12%" bgcolor=#EEEEFF | <tex>1</tex> |- align="center" !class0|<tex>0</tex>||<tex>0</tex>||<tex>1</tex>||<tex>1</tex>|-align="shadowcenter" style!1|<tex>0</tex>||<tex>1</tex>||<tex>0</tex>||<tex>1</tex>|-align="font-weight:normalcenter" bgcolor= ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#EEEEFF save0| Сохраняет 0]]|✓||✓|| || |-align="center" ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]|0||1✓||0||1✓ |- align="center" !class[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]| ||✓||✓|| |-align="shadowcenter" style ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]|✓||✓|| ||✓|-align="font-weight:normalcenter" bgcolor= ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#EEEEFF linear| 1Линейная]] |0✓||0✓||1✓||1✓
|}
</center>
Названия булевых функций от одной переменной:
<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>
|}
</center>
=== Бинарные функции ===
При ''<tex>n'' = 2 </tex> число булевых функций равно 2<sup>2²</suptex> {2^2}^2 = 2<sup>^4= 16</suptex> = 16.
Таблица значений булевых функций от двух переменных:
<center>{| class="standardwikitable" widthalign="100%" border=1 !class="darkcenter" style="fontcolor: blue; background-weightcolor:normal#ffffcc;" widthcellpadding="1%10" bgcolor=#EEEEFF| ''x''+ !classcolspan="dark18" style="font|Функции от двух переменных:|-weight:normal" widthalign="1%center" bgcolor=#EEEEFF| ''y'' !style<font color="black">x</font-weight:normal>||<font color="black" >y</font>|! width="45%" bgcolor=#EEEEFF| <tex>0</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x''↓''\land y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| <mathtex>x \negnrightarrow y</mathtex>(''x''←''y'') |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''x̅''<tex>x</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| <mathtex>x \negnleftarrow y</mathtex>(''x''→''y'') |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''y̅''<tex>y</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x''⊕''\oplus y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''x''<nowikitex>|x \lor y</nowikitex>''y'' |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x'' & ''\downarrow y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x'' ≡ ''= y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>\neg y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x''→''\leftarrow y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>\neg x''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x''←''\rightarrow y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| ''<tex>x'' ∨ ''\triangledown y''</tex> |!style="font-weight:normal" width="45%" bgcolor=#EEEEFF| <tex>1</tex> |- align="center" !class<font color="shadowblack" style>0</font>||<font color="black">0</font>|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1|-weight:normalalign="center" | 0 !class<font color="shadowblack" style>0</font>||<font color="black">1</font-weight:normal" >| 0 ||0||10||0||1||01||1||01||10||0||10||0||1||01||1||0||1 |- align="center" !class<font color="shadowblack" style>1</font>||<font color="black">0</font>|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1|-weight:normalalign="center" | 0 !class<font color="shadowblack" style>1</font>||<font color="font-weight:normalblack" | >1</font> |0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1|-align="center" bgcolor=#EEEEFF !colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save0|Сохраняет 0]]</font>|✓||✓||✓||✓||✓||✓||✓||✓|| || || ||1||0||0||1||1 |- align="center"bgcolor=#EEEEFF !classcolspan="shadow2" style|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]</font>| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|-weight:normalalign="center" | 1bgcolor=#EEEEFF !classcolspan="shadow2" style|<font color="font-weight:normalblack" >[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual| 0Самодвойственная]]</font> |0||0||0||0✓||1||1✓||1||1||0||0||0✓||0||1✓||1||1||1 |- align="center"bgcolor=#EEEEFF !classcolspan="shadow2" style|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]</font>|✓||✓|| ||✓|| ||✓|| ||✓|| || || || || || || ||✓|-weight:normalalign="center" | 1bgcolor=#EEEEFF !classcolspan="shadow2" style|<font color="font-weight:normalblack" >[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear| 1Линейная]]</font> |0✓||0||0||0✓||0||0✓||0✓||0||1||1✓||1✓||1||1✓||1||1||1✓
|}
</center>
Названия булевых функций от двух переменных:
<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'' & ''\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>
|}
</center>
=== Тернарные функции ===
При ''<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;" cellpadding="10" |+!colspan="14"|Таблица истинности некоторых тернарных функций|-align="center" !class="dark" style="font-weight:normal" | ''<tex>x''</tex> !class="dark" style="font-weight:normal" | ''<tex>y''</tex> !class="dark" style="font-weight:normal" | ''<tex>z''</tex> !style="font-weight:normal" | ''<tex>x''↓''\downarrow y''↓''\downarrow z''</tex> !style="font-weight:normal" | <mathtex>\neg</math>(≥2\geq 2(x,y,z))</tex> !style="font-weight:normal" | x≠y≠z<tex>x \not = y \not = z</tex> !style="font-weight:normal" | x<nowiki>|</nowikitex>x \mid y<nowiki>|\mid z</nowikitex>z !style="font-weight:normal" | <tex>min(x,y,z)</tex> !style="font-weight:normal" | <tex>x=y=z</tex> !style="font-weight:normal" | ''<tex>x''⊕''\oplus y''⊕''\oplus z''</tex> !style="font-weight:normal" | ≥2<tex>\geq 2(x,y,z)</tex> !style="font-weight:normal" | ''f<subtex>1f_1</subtex>'' !style="font-weight:normal" | ''f<subtex>2f_2</subtex>'' !style="font-weight:normal" | <tex>max(x,y,z)</tex>
|- align="center"
!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>
|1||1||0||1 ||0||1||0||0||0||0 ||0
|- align="center"
!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>
|0||1||1||1 ||0||0||1||0||0||0 ||1
|- align="center"
!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>
|0||1||1||1 ||0||0||1||0||0||0 ||1
|- align="center"
!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>
|0||0||1||1 ||0||0||0||1||1||1 ||1
|- align="center"
!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>
|0||1||1||1 ||0||0||1||0||1||0 ||1
|- align="center"
!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>
|0||0||1||1 ||0||0||0||1||0||1 ||1
|- align="center"
!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>
|0||0||1||1 ||0||0||0||1||1||1 ||1
|- align="center"
!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>
|0||0||0||0 ||1||1||1||1||1||1 ||1
|}
</center>
Названия булевых функций трех переменных:
<center>{| class="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10" |+|-align="center"
!Обозначения
!Другие обозначения
!Названия
|-
|-
|-
!<tex>x \not = y \not = z</tex> |x≠y≠z align = center|<tex>[≠\not =(x,y,z)] = NE(x,y,z,v)</tex> |<font color="black">Неравенство</font>
|-
|-
|-
|-
|-
|-
|-
|-
|}
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
{| style="width:9cm"
|-
| <tex>x \land \overline{x}=0</tex> ||<tex>x \lor \overline{x}=1</tex>
|}
{| style="width:15cm"
|-
| <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex>
|| <tex>\overline{x}\land\overline{y}=\overline{x\lor y}</tex>|| (законы де Моргана)
|}
<tex>x \land (y\lor z)=(x \land y)\lor (x \land z)</tex><br />
<tex>x \lor (y \land z)=(x\lor y) \land (x\lor z)</tex> (дистрибутивность конъюнкции и дизъюнкции)
{{Определение
|definition=
Функция <tex>g(x_1,x_2,\dots,x_n)</tex> называется '''двойственной''' (англ. ''duality'') функции <tex>f(x_1,x_2,\dots,x_n)</tex>, если <tex>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</tex>.}}
Легко показать, что в этом равенстве <tex>f</tex> и <tex>g</tex> можно поменять местами, то есть функции <tex>f</tex> и <tex>g</tex> двойственны друг другу. Из простейших функций двойственны друг другу константы <tex>0</tex> и <tex>1</tex>, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
=== Суперпозиции ===
{{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>,
* линейные функции <Tex>L</Tex>.
Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
== Представление булевых функций ==
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
* Как построить по данной функции представляющую её формулу?
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
=== Дизъюнктивная нормальная форма (ДНФ) ===
{{main|ДНФ}}
{{Определение
|definition =
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.
}}
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.
'''Примеры ДНФ:'''
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.
<tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>.
=== Конъюнктивная нормальная форма (КНФ) ===
{{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>
<tex>f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 </tex>
===Тождественные функции. Выражение функций друг через друга===
{{Определение
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.
}}
Приведение тождественной функции есть '''выражение булевой функции через другие'''.
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
{{Пример
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.
<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>
<tex>\langle x, y, z \rangle = \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 \lor z \right )</tex>
}}
=== Подстановка одной функции в другую ===
{{Определение
|definition =
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:
<center><tex>h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \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}, \ldots, x_{i-1}</tex>
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex>
|-
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex>
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \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>
<tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.
}}
=== Отождествление переменных ===
{{Определение
|definition=
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:
<center><tex>h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})</tex></center>
}}
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.
{{Пример
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.
}}
=== Схемы из функциональных элементов ===
{{main|Реализация булевой функции схемой из функциональных элементов}}
{{Определение
|definition =
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.
}}
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
'''Некоторые логические элементы:'''
{| class = "wikitable" border = "1"
!-align="center" |И
!-align="center" |ИЛИ
!-align="center" |НЕ
!Штрих Шеффера
!Стрелка Пирса
|-
|[[Image:AND_logic_element.png]]
|[[Image:OR_logic_element.png]]
|[[Image:NOT_logic_element.png]]
|[[Image:NAND_logic_element.png]]
|[[Image:NOR_logic_element.png]]
|}
==Стандартный базис==
{{Определение
|id = def1
|definition = '''Стандартный базис''' — система булевых функций:
<tex>\{\land, \lor, \lnot \} </tex>
}}
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex>
<tex> x \rightarrow y = \lnot x \lor y </tex>
<tex> 0 = x \land \lnot x </tex>
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.
<tex> x \mid y = \lnot \left ( x \land y \right )</tex>
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex>
Тождественность функций можно доказать с помощью таблицы истинности.
'''Пример:'''
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex>
==Полнота стандартного базиса==
{{Утверждение
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.
}}
'''Замечание:'''
По [[Множества|закону де Моргана]]:
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
==Теоремы о числе функций в базисе==
{{Теорема
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex>, где <tex> T_0, T_1, S, M, L</tex> — классы Поста.
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex>
Рассмотрим <tex>f_0</tex>. Возможны два случая:
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.
}}
{{Теорема
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.
|proof=Приведём примеры базисов для каждого <tex>k</tex>:
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;
<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/>
== Источники информации ==
* ''Гаврилов Г. П., Сапоженко А. А.'' Сборник задач по дискретной математике. — М.: Наука, 1969.
* ''Кузнецов О. П., Адельсон-Вельский Г. М.'' Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
* ''Марченков С. С.'' Замкнутые классы булевых функций. — М.: Физматлит, 2000.
* ''Яблонский С. В.'' Введение в дискретную математику. — М.: Наука, 1986.
* ''Алексеев В. Б.'' Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
* [http://ido.tsu.ru/iop_res/bulevfunc/index.html ''Быкова С. В., Буркатовская Ю. Б.'', Булевы функции, учебно-методический комплекс, Томск, 2006]
* [http://mathcyb.cs.msu.su/books.html Учебные пособия кафедры математической кибернетики ВМиК МГУ]
* [http://ru.wikipedia.org/wiki/Булева_функция Булева функция — Википедия]
* http://psi-logic.narod.ru/bool/bool.htm
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
