Изменения
Нет описания правки
{{Определение
|definition=
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''', англ. ''Boolean function'') от <tex>n</tex> переменных — отображение <tex>B^n</tex> → <tex>\rightarrow B</tex>, где <tex>B = \{0, 1\}</tex> — булево множество.}} Элементы булева множества <tex>1 </tex> и <tex>0 </tex> обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения <tex>B^n</tex> называют ''булевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается <tex>P_2</tex>, а от ''n'' переменных — <tex>P_2(n)</tex>. Булевы функции названы так по фамилии математика Джорджа Буля.
== Основные сведения ==
{{Определение
|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="widthcolor: blue; background-color:10cm#ffffcc;" bordercellpadding=1"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" style="height:0.9cm"
| <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>) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной''(англ. ''dummy variable'').
=== Нульарные функции ===
При <tex>n = 0</tex> количество булевых функций равно <tex>{2^2}^0 = 2^1 = 2</tex>, первая из них тождественно равна <tex>0</tex>, а вторая <tex>1</tex>. Их называют булевыми константами — тождественный нуль и тождественная единица.
=== Унарные функции ===
Таблица значений булевых функций от одной переменной:
<center> {| borderclass="1wikitable"align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="5"|Функции от одной переменной
|-align="center"
!Диапазон
|! width="12%" | <tex>0</tex>
|! width="12%" | <tex>x</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" 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>
Названия булевых функций от одной переменной:
<center>{| borderclass=1"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>
=== Бинарные функции ===
Таблица значений булевых функций от двух переменных:
<center>{| borderclass="1wikitable"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>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>|1✓||1✓||1✓||1✓||1✓||1✓||1✓||1✓||0||0||0||0||0||0||0||0
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 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">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]</font>|0||0||0||1✓||0||1✓||0||0||0||0||1✓||0||1✓||0||0||0
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]</font>|1✓||1✓||0||1✓||0||1✓||0||1✓||0||0||0||0||0||0||0||1✓
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]</font>|1✓||0||0||1✓||0||1✓||1✓||0||0||1✓||1✓||0||1✓||0||0||1✓
|}
</center>
Названия булевых функций от двух переменных:
<center>{| class="standardwikitable" borderalign=1"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> ''x <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="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10" border|+!colspan=1"14"|Таблица истинности некоторых тернарных функций |-align="center"
!class="dark" style="font-weight:normal"| <tex>x</tex>
!class="dark" style="font-weight:normal"| <tex>y</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="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" bordercellpadding=1"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= (x "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> ''(x <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:15cm9cm"
|-
| <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 />
{{Определение
|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'') {{---}} функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
}}
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.
=== Полнота системы, критерий Поста ===
{{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>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
== Представление булевых функций ==
=== Дизъюнктивная нормальная форма (ДНФ) ===
{{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]]|} ==Стандартный базис== {main{Определение|Реализация 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 с.
* ''Яблонский С. В.'' Введение в дискретную математику. — М.: Наука, 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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
