Изменения

{{Определение|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> обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла.Элементы декартова произведения <tex>B^n</tex> называют ''Bбулевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается <tex>P_2<sup/tex>, а от ''n''переменных — <tex>P_2(n)</suptex> называют . Булевы функции названы так по фамилии математика Джорджа Буля. == Основные сведения =={{Определение|definition='''А́рность''' (англ. ''булевыми векторамиarity'') функции — количество ее аргументов. Множество }} Каждая булева функция арности <tex>n</tex> полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины <tex>n</tex>. Число таких векторов равно <tex>2^n</tex>. Поскольку на каждом векторе булева функция может принимать значение либо <tex>0</tex>, либо <tex>1</tex>, то количество всех ''n''-арных булевых функций равно <tex>{2^2}^n</tex>. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид: <center>   {| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="6"|Таблица истинности|-align="center"! <tex>x_1</tex> || <tex>x_2</tex> || <tex>\ldots</tex> || <tex>x_n</tex> || <tex>f(x_1,x_2,\ldots,x_n)</tex>|-align="center"| <tex>0</tex> || <tex>0</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(0,0,\ldots,0)</tex>|-align="center"| <tex>1</tex> || <tex>0</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(1,0,\ldots,0)</tex>|-align="center"| <tex>0</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(0,1,\ldots,0)</tex>|-align="center"| <tex>1</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(1,1,\ldots,0)</tex>|-align="center" | <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex>|-align="center"| <tex>0</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>1</tex> || <tex>f(0,1,\ldots,1)</tex>|-align="center"| <tex>1</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>1</tex> || <tex>f(1,1,\ldots,1)</tex>|}</center>Практически все булевы функции малых арностей (<tex>0, 1, 2</tex> и <tex>3</tex>) сложились исторически и имеют конкретные имена. Если значение функции не зависит от любого числа одной из переменных часто обозначается (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной'' (англ. ''Pdummy variable''). === Нульарные функции ===При <tex>n = 0</tex> количество булевых функций равно <subtex>{2^2}^0 = 2^1 = 2</subtex>, первая из них тождественно равна <tex>0</tex>, а вторая <tex>1</tex>. Их называют булевыми константами — тождественный нуль и тождественная единица. === Унарные функции ===При <tex>n = 1</tex> число булевых функций равно <tex>{2^2}^1 = 2^2 = 4</tex>. Таблица значений булевых функций от одной переменной: <center>  {| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="5"|Функции от одной переменной|-align="center"!|! width="12%" | <tex>0</tex>|! width="12%" | <tex>x</tex>|! width="12%" | <tex>\neg x</tex>|! width="12%" | <tex>1</tex>|-align="center"!0|<tex>0</tex>||<tex>0</tex>||<tex>1</tex>||<tex>1</tex>|-align="center"!1|<tex>0</tex>||<tex>1</tex>||<tex>0</tex>||<tex>1</tex>|-align="center" ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save0|Сохраняет 0]]|✓||✓|| || |-align="center" ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]| ||✓|| ||✓|-align="center" ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]| ||✓||✓|| |-align="center" ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]|✓||✓|| ||✓|-align="center" ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]|✓||✓||✓||✓|}</center> Названия булевых функций от одной переменной:<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center" !Обозначение !Название |- !<tex>0</tex> |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font> |- !<tex>x</tex> |<font color="black">тождественная функция, логическое "ДА", "YES"(англ.)</font> |- !<tex>\bar x,\ \neg x,\ x'</tex> |<font color="black">отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)</font> |- !<tex>1</tex> |<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>|}</center> === Бинарные функции ===При <tex>n = 2</tex> число булевых функций равно <tex>{2^2}^2 = 2^4 = 16</tex>. Таблица значений булевых функций от двух переменных:<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="18"|Функции от двух переменных:|-align="center" !<font color="black">x</font>||<font color="black">y</font>|! width="5%" | <tex>0</tex>|! width="5%" | <tex>x \land y</tex>|! width="5%" | <tex>x \nrightarrow y</tex>|! width="5%" | <tex>x</tex>|! width="5%" | <tex>x \nleftarrow y</tex>|! width="5%" | <tex>y</tex>|! width="5%" | <tex>x \oplus y</tex>|! width="5%" | <tex>x \lor y</tex>|! width="5%" | <tex>x \downarrow y</tex>|! width="5%" | <tex>x = y</tex>|! width="5%" | <tex>\neg y</tex>|! width="5%" | <tex>x \leftarrow y</tex>|! width="5%" | <tex>\neg x</tex>|! width="5%" | <tex>x \rightarrow y</tex>|! width="5%" | <tex>x \triangledown y</tex>|! width="5%" | <tex>1</tex>|-align="center" !<font color="black">0</font>||<font color="black">0</font>|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1|-align="center" !<font color="black">0</font>||<font color="black">1</font>|0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1|-align="center" !<font color="black">1</font>||<font color="black">0</font>|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1|-align="center" !<font color="black">1</font>||<font color="black">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>|✓||✓||✓||✓||✓||✓||✓||✓|| || || || || || || || |-align="center" bgcolor=#EEEEFF !colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]</font>| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|| ||✓|-align="center" bgcolor=#EEEEFF !colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]</font>| || || ||✓|| ||✓|| || || || ||✓|| ||✓|| || || |-align="center" bgcolor=#EEEEFF !colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]</font>|✓||✓|| ||✓|| ||✓|| ||✓|| || || || || || || ||✓|-align="center" bgcolor=#EEEEFF !colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]</font>|✓|| || ||✓|| ||✓||✓|| || ||✓||✓|| ||✓|| || ||✓|}</center>Названия булевых функций от двух переменных:<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center" !Обозначение !Другие обозначения !Название |- !<tex>0</tex> | |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font> |- !<tex>x \land y</tex> |align = center|<tex>x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y), x </tex> <font color="black">И</font> <tex>y,</tex> <font color="black">И</font><tex>(x, y)</tex> |<font color="black">2И, конъюнкция</font> |- !<tex>x \nrightarrow y</tex> |align = center|<tex>x > y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)</tex> |<font color="black">больше, инверсия прямой импликации</font> |- !<tex>x</tex> |align = center|<tex>YES1(x,y),</tex> <font color="black">ДА1</font><tex>(x, y)</tex> |<font color="black">первый операнд</font> |- !<tex>x \nleftarrow y</tex> |align = center|<tex>x < y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)</tex> |<font color="black">меньше, инверсия обратной импликации</font> |- !<tex>y</tex> |align = center|<tex>YES2(x, y),</tex> <font color="black">ДА2</font><tex>(x, y)</tex> |<font color="black">второй операнд</font> |- !<tex>x \oplus y</tex> |align = center|<tex>x + _2 y,\ x \not = y,\ x >< y,\ x <> y,\ x\ XOR\ y,\ XOR(x,y)</tex> |<font color="black">сложение по модулю 2, не равно, ксор, исключающее «или»</font> |- !<tex>x \lor y</tex> |align = center|<tex>x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),</tex> <tex>x </tex><font color="black">ИЛИ </font><tex>y,</tex><font color="black"> ИЛИ</font><tex>(x, y)</tex> |<font color="black">2ИЛИ, дизъюнкция</font> |- !<tex>x \downarrow y</tex> |align = center|<tex>x\ NOR\ y,\ NOR(x,y)</tex> <tex>x </tex><font color="black">ИЛИ-НЕ</font> <tex>y,</tex> <font color="black">ИЛИ-НЕ</font><tex>(x, y)</tex> |<font color="black">НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса</font> |- !<tex>x = y</tex> |align = center|<tex>x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y</tex> |<font color="black">равенство, эквивалентность</font> |- !<tex>\neg y</tex> |align = center|<tex>NOT2(x, y),\ y',\ \bar{y},</tex> <font color="black">НЕ2</font><tex>(x, y)</tex> |<font color="black">отрицание (негация, инверсия) второго операнда</font> |- !<tex>x \leftarrow y</tex> |align = center|<tex>x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)</tex> |<font color="black">больше или равно, обратная импликация (от второго аргумента к первому)</font> |- !<tex>\neg x</tex> |align = center|<tex>NOT1(x,y),\ x',\ \bar{x},</tex> <font color="black">НЕ1</font><tex>(x, y)</tex> |<font color="black">отрицание (негация, инверсия) первого операнда</font> |- !<tex>x \rightarrow y</tex> |align = center|<tex>x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)</tex> |<font color="black">меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)</font> |- !<tex>x \triangledown y</tex> |align = center|<tex>x \mid y,\ x\ NAND\ y,\ NAND(x,y),</tex> <tex>x </tex> <font color="black">И-НЕ </font><tex>y,</tex> <font color="black">И-НЕ</font><tex>(x, y)</tex> |<font color="black">НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера</font> |- !<tex>1</tex> | |<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>|}</center> === Тернарные функции ===При <tex>n= 3</tex> число булевых функций равно <tex>{2^2}^3 = 2^8 = 256</tex>. Некоторые из них определены в следующей таблице:<center>{| class="wikitable" 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"| <tex>\neg (\geq 2(x,y,z))</tex> !style="font-weight:normal"| <tex>x \not = y \not = z</tex> !style="font-weight:normal"| <tex>x \mid y \mid z</tex> !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"| <tex>\geq 2(x,y,z)</tex> !style="font-weight:normal"| <tex>f_1</tex> !style="font-weight:normal"| <tex>f_2</tex> !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="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center" !Обозначения !Другие обозначения !Названия |- !<tex>x \downarrow y \downarrow z</tex> |align = center|<tex>\downarrow (x,y,z) = Webb_2 (x,y,z)</tex> |<font color="black"> 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса</font> |- !<tex>\neg (\geq 2(x,y,z))</tex> | |<font color="black">Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией</font> |- !<tex>x \not = y \not = z</tex> |align = center|<tex>[\not =(x,y,z)] = NE(x,y,z)</tex> |<font color="black">Неравенство</font> |- !<tex>x \mid y \mid z</tex> |align = center|<tex>\mid(x,y,z)</tex> |<font color="black">3-И-НЕ, штрих Шеффера</font> |- !<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) = </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)</tex> |<font color="black">Равенство</font> |- !<tex>x \oplus y \oplus z</tex> |align = center|<tex>x +_2 y +_2 z = \oplus (x,y,z) = +_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> |- !<tex>f_1</tex> | |<font color="black">Разряд займа при тернарном вычитании</font> |- !<tex>f_2</tex> | |<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>|}А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:{| 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 =''P'Подстановкой''' (англ. ''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>, результирующая функция <subtex>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} </subtex> |{{---}} используются как аргументы для вычисления значения функции <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 [[Категория: Дискретная математика и алгоритмы]] [[Категория: Булевы функции ]]