Определение булевой функции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Бинарные функции)
м (rollbackEdits.php mass rollback)
 
(не показано 70 промежуточных версий 13 участников)
Строка 1: Строка 1:
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''') от ''n'' переменных — в дискретной математике отображение ''B''<sup>''n''</sup> → ''B'', где ''B'' = {0,1} — ''булево множество''. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла.Элементы декартова произведения ''B''<sup>''n''</sup> называют ''булевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается ''P''<sub>2</sub>, а от ''n'' переменных — ''P''<sub>2</sub>(''n''). Булевы функции названы так по фамилии математика Джорджа Буля.
+
{{Определение
 +
|definition=
 +
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''', англ.  ''Boolean function'') от <tex>n</tex> переменных — отображение <tex>B^n\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>. Булевы функции названы так по фамилии математика Джорджа Буля.
 +
 
 
== Основные сведения ==
 
== Основные сведения ==
Каждая булева функция арности ''n'' полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины ''n''. Число таких векторов равно 2<sup>''n''</sup>. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех ''n''-арных булевых функций равно 2<sup>2<sup>''n''</sup></sup>. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
+
{{Определение
 +
|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>
 
<center>
{| class="wikitable" align="center" style="width:10cm" border=1
+
 
 +
 
 +
 
 +
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 
|+
 
|+
|-align="center" bgcolor=#EEEEFF
+
!colspan="6"|Таблица истинности
! x<sub>1</sub> || x<sub>2</sub> || … || x<sub>n</sub> || f(x<sub>1</sub>,x<sub>2</sub>,,x<sub>n</sub>)
+
|-align="center"
|-align="center" bgcolor=#F0F0F0
+
! <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>
| 0 || 0 || || 0 || bgcolor=white | f(0,0,,0)
+
|-align="center"
|-align="center" bgcolor=#F0F0F0
+
| <tex>0</tex> || <tex>0</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(0,0,\ldots,0)</tex>
| 1 || 0 || || 0 || bgcolor=white | f(1,0,,0)
+
|-align="center"
|-align="center" bgcolor=#F0F0F0
+
| <tex>1</tex> || <tex>0</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(1,0,\ldots,0)</tex>
| 0 || 1 || || 0 || bgcolor=white | f(0,1,,0)
+
|-align="center"
|-align="center" bgcolor=#F0F0F0
+
| <tex>0</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(0,1,\ldots,0)</tex>
| 1 || 1 || || 0 || bgcolor=white | f(1,1,,0)
+
|-align="center"
|-align="center" style="height:1.2cm" bgcolor=#F0F0F0
+
| <tex>1</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(1,1,\ldots,0)</tex>
| <math>\vdots</math> || <math>\vdots</math> || <math>\vdots</math> || <math>\vdots</math> || bgcolor=white | <math>\vdots</math>
+
|-align="center"  
|-align="center" bgcolor=#F0F0F0
+
| <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex>
| 0 || 1 || || 1 || bgcolor=white | f(0,1,,1)
+
|-align="center"
|-align="center" bgcolor=#F0F0F0
+
| <tex>0</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>1</tex> || <tex>f(0,1,\ldots,1)</tex>
| 1 || 1 || || 1 || bgcolor=white | f(1,1,,1)
+
|-align="center"
 +
| <tex>1</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>1</tex> || <tex>f(1,1,\ldots,1)</tex>
 
|}
 
|}
 
</center>
 
</center>
Практически все булевы функции малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной''.
+
Практически все булевы функции малых арностей (<tex>0, 1, 2</tex> и <tex>3</tex>) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной'' (англ. ''dummy variable'').
  
 
=== Нульарные функции ===
 
=== Нульарные функции ===
При ''n'' = 0 количество булевых функций равно 2<sup>2<sup>0</sup></sup> = 2<sup>1</sup> = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.
+
При <tex>n = 0</tex> количество булевых функций равно <tex>{2^2}^0 = 2^1 = 2</tex>, первая из них тождественно равна <tex>0</tex>, а вторая <tex>1</tex>. Их называют булевыми константами — тождественный нуль и тождественная единица.
  
 
=== Унарные функции ===
 
=== Унарные функции ===
При ''n'' = 1 число булевых функций равно 2<sup>2<sup>1</sup></sup> = 2<sup>2</sup> = 4.
+
При <tex>n = 1</tex> число булевых функций равно <tex>{2^2}^1 = 2^2 = 4</tex>.
  
 
Таблица значений булевых функций от одной переменной:
 
Таблица значений булевых функций от одной переменной:
{| border="1"
+
 
|-align="center" bgcolor=#FFF8DC
+
<center>
!x
+
 
|! width="12%" | 0
+
 
|! width="12%" | x
+
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|! width="12%" | &not;x
+
|+
|! width="12%" | 1
+
!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"
 
|-align="center"
 
!0
 
!0
|0||0||1||1
+
|<tex>0</tex>||<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
 
|-align="center"
 
|-align="center"
 
!1
 
!1
|0||1||0||1
+
|<tex>0</tex>||<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|-align="center" bgcolor=#EEEEFF
+
|-align="center"  
  !Сохраняет 0
+
  ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save0|Сохраняет 0]]
|1||1||0||0
+
||||| ||  
|-align="center" bgcolor=#EEEEFF
+
|-align="center"  
  !Сохраняет 1
+
  ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#save1|Сохраняет 1]]
|0||1||0||1
+
| |||| ||
|-align="center" bgcolor=#EEEEFF
+
|-align="center"  
  !Самодвойственная
+
  ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#selfDual|Самодвойственная]]
|0||1||1||0
+
| ||||||  
|-align="center" bgcolor=#EEEEFF
+
|-align="center"  
  !Монотонная
+
  ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#monotone|Монотонная]]
|1||1||0||1
+
||||| ||
|-align="center" bgcolor=#EEEEFF
+
|-align="center"  
  !Линейная
+
  ![[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]
|1||1||1||1
+
|||||||
 
|}
 
|}
 +
</center>
  
 
Названия булевых функций от одной переменной:
 
Названия булевых функций от одной переменной:
{| class="wikitable" border=1
+
<center>
 +
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
|-align="center"
 
  !Обозначение
 
  !Обозначение
 
  !Название
 
  !Название
 
  |-
 
  |-
  !bgcolor=#EEEEFF |0
+
  !<tex>0</tex>
  |тождественный ноль, тождественная ложь, тождественное "НЕТ"
+
  |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF |''x''
+
  !<tex>x</tex>
  |тождественная функция, логическое "ДА", "YES"(англ.)
+
  |<font color="black">тождественная функция, логическое "ДА", "YES"(англ.)</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF |''x̅'', ¬''x'', ''x'''
+
  !<tex>\bar x,\ \neg x,\ x'</tex>
  |отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
+
  |<font color="black">отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF |1
+
  !<tex>1</tex>
  |тождественная единица, тождественная истина, тождественное "ДА", тавтология
+
  |<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>
 
|}
 
|}
 +
</center>
  
 
=== Бинарные функции ===
 
=== Бинарные функции ===
При ''n'' = 2 число булевых функций равно 2<sup>2<sup>2</sup></sup> = 2<sup>4</sup> = 16.
+
При <tex>n = 2</tex> число булевых функций равно <tex>{2^2}^2 = 2^4 = 16</tex>.
  
 
Таблица значений булевых функций от двух переменных:
 
Таблица значений булевых функций от двух переменных:
{| border="1"
+
<center>
|-align="center" bgcolor=#FFF8DC
+
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
  !x||y
+
|+
|! width="5%" | 0
+
!colspan="18"|Функции от двух переменных:
|! width="5%" | &and;
+
|-align="center"
|! width="5%" | <tex>\nrightarrow</tex>
+
  !<font color="black">x</font>||<font color="black">y</font>
|! width="5%" | x
+
|! width="5%" | <tex>0</tex>
|! width="5%" | &notlarr;
+
|! width="5%" | <tex>x \land y</tex>
|! width="5%" | y
+
|! width="5%" | <tex>x \nrightarrow y</tex>
|! width="5%" | &oplus;
+
|! width="5%" | <tex>x</tex>
|! width="5%" | &or;
+
|! width="5%" | <tex>x \nleftarrow y</tex>
|! width="5%" | &darr;
+
|! width="5%" | <tex>y</tex>
|! width="5%" | &harr;
+
|! width="5%" | <tex>x \oplus y</tex>
|! width="5%" | &not;y
+
|! width="5%" | <tex>x \lor y</tex>
|! width="5%" | &larr;
+
|! width="5%" | <tex>x \downarrow y</tex>
|! width="5%" | &not;x
+
|! width="5%" | <tex>x = y</tex>
|! width="5%" | &rarr;
+
|! width="5%" | <tex>\neg y</tex>
|! width="5%" | &nabla;
+
|! width="5%" | <tex>x \leftarrow y</tex>
|! width="5%" | 1
+
|! 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"
 
|-align="center"
  !0||0
+
  !<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
 
|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1
 
|-align="center"
 
|-align="center"
  !0||1
+
  !<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
 
|0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1
 
|-align="center"
 
|-align="center"
  !1||0
+
  !<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
 
|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1
 
|-align="center"
 
|-align="center"
  !1||1
+
  !<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
 
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
 
|-align="center" bgcolor=#EEEEFF
 
|-align="center" bgcolor=#EEEEFF
  !colspan="2"|Сохраняет 0
+
  !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
 
|-align="center" bgcolor=#EEEEFF
  !colspan="2"|Сохраняет 1
+
  !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
 
|-align="center" bgcolor=#EEEEFF
  !colspan="2"|Самодвойственная
+
  !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
 
|-align="center" bgcolor=#EEEEFF
  !colspan="2"|Монотонная
+
  !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
 
|-align="center" bgcolor=#EEEEFF
  !colspan="2"|Линейная
+
  !colspan="2"|<font color="black">[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#linear|Линейная]]</font>
|1||0||0||1||0||1||1||0||0||1||1||0||1||0||0||1
+
||| || |||| |||||| || |||||| |||| || ||
 
|}
 
|}
 
+
</center>
 
Названия булевых функций от двух переменных:
 
Названия булевых функций от двух переменных:
{| class="standard" border=1
+
<center>
 +
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
|-align="center"
 
  !Обозначение
 
  !Обозначение
 
  !Другие обозначения
 
  !Другие обозначения
 
  !Название
 
  !Название
 
  |-
 
  |-
  !bgcolor=#EEEEFF|<tex>0</tex>
+
  !<tex>0</tex>
 
  |
 
  |
  |тождественный ноль, тождественная ложь, тождественное "НЕТ"
+
  |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|<math>x \And y</math>
+
  !<tex>x \land y</tex>
  |''x'' · ''y'', ''x''<span></span>''y'', ''x'' ∧ ''y'', ''x'' AND ''y'', AND(''x'',''y''), ''x'' И ''y'', И(''x'',''y''), min(''x'',''y'')  
+
  |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>
  |2И, конъюнкция
+
  |<font color="black">2И, конъюнкция</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' <tex>\nrightarrow</tex> ''y''
+
  !<tex>x \nrightarrow y</tex>
  |''x'' > ''y'', <math>\neg</math>(''x'' → ''y''), ''x'' GT ''y'', GT(''x'',''y'')
+
  |align = center|<tex>x > y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)</tex>
  |больше, инверсия прямой импликации
+
  |<font color="black">больше, инверсия прямой импликации</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x''
+
  !<tex>x</tex>
  |ДА1(''x'',''y''), YES1(''x'',''y'')
+
  |align = center|<tex>YES1(x,y),</tex> <font color="black">ДА1</font><tex>(x, y)</tex>
  |первый операнд
+
  |<font color="black">первый операнд</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' <tex>\nleftarrow</tex> ''y''
+
  !<tex>x \nleftarrow y</tex>
  |''x'' < ''y'', <math>\neg</math>(''x'' ← ''y''), ''x'' LT ''y'',  LT(''x'',''y'')
+
  |align = center|<tex>x < y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)</tex>
  |меньше, инверсия обратной импликации]
+
  |<font color="black">меньше, инверсия обратной импликации</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''y''
+
  !<tex>y</tex>
  |ДА2(''x'',''y''), YES2(''x'',''y'')
+
  |align = center|<tex>YES2(x, y),</tex> <font color="black">ДА2</font><tex>(x, y)</tex>
  |второй операнд
+
  |<font color="black">второй операнд</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' ⊕ ''y''
+
  !<tex>x \oplus y</tex>
  |''x'' +<sub>2</sub> ''y'', ''x'' ≠ ''y'', ''x'' >< ''y'', ''x'' <> ''y'', ''x'' XOR ''y'', XOR(''x'',''y'')
+
  |align = center|<tex>x + _2 y,\ x \not = y,\ x >< y,\ x <> y,\ x\ XOR\ y,\ XOR(x,y)</tex>
  |сложение по модулю 2, не равно, , исключающее «или»
+
  |<font color="black">сложение по модулю 2, не равно, ксор, исключающее «или»</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' ∨ ''y''
+
  !<tex>x \lor y</tex>
  |''x'' + ''y'', ''x'' ИЛИ ''y'', ИЛИ(''x'',''y''), ''x'' OR ''y'', OR(''x'',''y''), max(''x'',''y'')
+
  |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>
  |2ИЛИ, дизъюнкция
+
  |<font color="black">2ИЛИ, дизъюнкция</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' ↓ ''y''
+
  !<tex>x \downarrow y</tex>
  |''x'' ИЛИ-НЕ ''y'', ИЛИ-НЕ(''x'',''y''), ''x'' NOR ''y'', NOR(''x'',''y'')
+
  |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>
  |НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
+
  |<font color="black">НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' = ''y''
+
  !<tex>x = y</tex>
  |''x'' ≡ ''y'', ''x'' EQV ''y'', EQV(''x'',''y''), ''x'' ~ ''y'', ''x'' ↔ ''y''
+
  |align = center|<tex>x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y</tex>
  |равенство,  эквивалентность
+
  |<font color="black">равенство,  эквивалентность</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''y̅''
+
  !<tex>\neg y</tex>
  |НЕ2(''x'',''y''), NOT2(''x'',''y''), ''y''', ¬''y''
+
  |align = center|<tex>NOT2(x, y),\ y',\ \bar{y},</tex> <font color="black">НЕ2</font><tex>(x, y)</tex>
  |отрицание (негация, инверсия) второго операнда
+
  |<font color="black">отрицание (негация, инверсия) второго операнда</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' ← ''y''
+
  !<tex>x \leftarrow y</tex>
  |''x'' ≥ ''y'', ''x'' ⊂ ''y'', ''x'' GE ''y'', GE(''x'',''y'')
+
  |align = center|<tex>x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)</tex>
  |больше или равно, обратная импликация (от второго аргумента к первому)
+
  |<font color="black">больше или равно, обратная импликация (от второго аргумента к первому)</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x̅''
+
  !<tex>\neg x</tex>
  |НЕ1(''x'',''y''), NOT1(''x'',''y''), ''x''', ¬''x''
+
  |align = center|<tex>NOT1(x,y),\ x',\ \bar{x},</tex> <font color="black">НЕ1</font><tex>(x, y)</tex>
  |отрицание (негация, инверсия) первого операнда
+
  |<font color="black">отрицание (негация, инверсия) первого операнда</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' → ''y''
+
  !<tex>x \rightarrow y</tex>
  |''x'' ≤ ''y'', ''x'' ⊃ ''y'', ''x'' LE ''y'', LE(''x'',''y'')
+
  |align = center|<tex>x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)</tex>
  |меньше или равно,  прямая (материальная) импликация (от первого аргумента ко второму)
+
  |<font color="black">меньше или равно,  прямая (материальная) импликация (от первого аргумента ко второму)</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''x'' &nabla; ''y''
+
  !<tex>x \triangledown y</tex>
  |''x'' <nowiki>|</nowiki> ''y'', ''x'' NAND ''y'', NAND(''x'',''y''), ''x'' И-НЕ ''y'', И-НЕ(''x'',''y'')  
+
  |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>
  |НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера
+
  |<font color="black">НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|1
+
  !<tex>1</tex>
 
  |
 
  |
  |тождественная единица, тождественная истина, тождественное "ДА", тавтология
+
  |<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>
 
|}
 
|}
 +
</center>
  
 
=== Тернарные функции ===
 
=== Тернарные функции ===
При ''n'' = 3 число булевых функций равно 2<sup>2³</sup> = 2<sup>8</sup> = 256. Некоторые из них определены в следующей таблице:
+
При <tex>n = 3</tex> число булевых функций равно <tex>{2^2}^3 = 2^8 = 256</tex>. Некоторые из них определены в следующей таблице:
{| class="standard" border=1
+
<center>
|-
+
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
  !class="dark" style="font-weight:normal" bgcolor=#EEEEFF| ''x''
+
|+
  !class="dark" style="font-weight:normal" bgcolor=#EEEEFF| ''y''
+
!colspan="14"|Таблица истинности некоторых тернарных функций
  !class="dark" style="font-weight:normal" bgcolor=#EEEEFF| ''z''
+
|-align="center"
  !style="font-weight:normal" bgcolor=#EEEEFF| ''x''↓''y''↓''z''
+
  !class="dark" style="font-weight:normal"| <tex>x</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| <math>\neg</math>(≥2(x,y,z))
+
  !class="dark" style="font-weight:normal"| <tex>y</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| x≠y≠z
+
  !class="dark" style="font-weight:normal"| <tex>z</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| x<nowiki>|</nowiki>y<nowiki>|</nowiki>z
+
  !style="font-weight:normal"| <tex>x \downarrow y \downarrow z</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| min(x,y,z)
+
  !style="font-weight:normal"| <tex>\neg (\geq 2(x,y,z))</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| x=y=z
+
  !style="font-weight:normal"| <tex>x \not = y \not = z</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| ''x''⊕''y''⊕''z''
+
  !style="font-weight:normal"| <tex>x \mid y \mid z</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| ≥2(x,y,z)
+
  !style="font-weight:normal"| <tex>min(x,y,z)</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| ''f<sub>1</sub>''
+
  !style="font-weight:normal"| <tex>x=y=z</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| ''f<sub>2</sub>''
+
  !style="font-weight:normal"| <tex>x \oplus y \oplus z</tex>
  !style="font-weight:normal" bgcolor=#EEEEFF| max(x,y,z)
+
  !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"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" |<font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
 
  |1||1||0||1 ||0||1||0||0||0||0 ||0
 
  |1||1||0||1 ||0||1||0||0||0||0 ||0
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
 
  |0||1||1||1 ||0||0||1||0||0||0 ||1
 
  |0||1||1||1 ||0||0||1||0||0||0 ||1
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
 
  |0||1||1||1 ||0||0||1||0||0||0 ||1
 
  |0||1||1||1 ||0||0||1||0||0||0 ||1
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
 
  |0||0||1||1 ||0||0||0||1||1||1 ||1
 
  |0||0||1||1 ||0||0||0||1||1||1 ||1
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
 
  |0||1||1||1 ||0||0||1||0||1||0 ||1
 
  |0||1||1||1 ||0||0||1||0||1||0 ||1
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
 
  |0||0||1||1 ||0||0||0||1||0||1 ||1
 
  |0||0||1||1 ||0||0||0||1||0||1 ||1
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 0
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
 
  |0||0||1||1 ||0||0||0||1||1||1 ||1
 
  |0||0||1||1 ||0||0||0||1||1||1 ||1
 
  |- align="center"
 
  |- align="center"
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
  !class="shadow" style="font-weight:normal" | 1
+
  !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
 
  |0||0||0||0 ||1||1||1||1||1||1 ||1
 
  |0||0||0||0 ||1||1||1||1||1||1 ||1
 
|}
 
|}
  
 +
</center>
 
Названия булевых функций трех переменных:
 
Названия булевых функций трех переменных:
{| class="standard" border=1
+
<center>
|-
+
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
|-align="center"
 
  !Обозначения
 
  !Обозначения
 +
!Другие обозначения
 
  !Названия
 
  !Названия
 
  |-
 
  |-
  !bgcolor=#EEEEFF|x<math>\downarrow</math>y<math>\downarrow</math>z = <math>\downarrow</math>(x,y,z) = Webb<sub>2</sub>(x,y,z)
+
  !<tex>x \downarrow y \downarrow z</tex>  
  |3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
+
|align = center|<tex>\downarrow (x,y,z) = Webb_2 (x,y,z)</tex>
 +
  |<font color="black"> 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|<math>\neg</math>(> = 2(x,y,z))
+
  !<tex>\neg (\geq 2(x,y,z))</tex>
  |Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
+
  |
 +
|<font color="black">Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|x≠y≠z = [(x,y,z)] = NE(x,y,z,v)
+
  !<tex>x \not = y \not = z</tex>
  |Неравенство
+
|align = center|<tex>[\not =(x,y,z)] = NE(x,y,z)</tex>
 +
  |<font color="black">Неравенство</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|x<math>\mid</math>y<math>\mid</math>z = <math>\mid</math>(x,y,z)
+
  !<tex>x \mid y \mid z</tex>
  |3-И-НЕ, штрих Шеффера
+
|align = center|<tex>\mid(x,y,z)</tex>
 +
  |<font color="black">3-И-НЕ, штрих Шеффера</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z)
+
  !<tex>x \land y \land z</tex>
  |3-И, минимум
+
|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>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|(x=y=z) = [=(x,y,z)]  = EQV(x,y,z,v)
+
  !<tex>x=y=z</tex>
  |Равенство
+
|align = center|<tex>[=(x,y,z)]  = EQV(x,y,z)</tex>
 +
  |<font color="black">Равенство</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|x⊕<sub>2</sub>y⊕<sub>2</sub>z =  x+<sub>2</sub>y+<sub>2</sub>z =  ⊕<sub>2</sub>(x,y,z) = +<sub>2</sub>(x,y,z)
+
  !<tex>x \oplus y \oplus z</tex>
  |Тернарное сложение по модулю 2
+
|align = center|<tex>x +_2 y +_2 z =  \oplus (x,y,z) = +_2 (x,y,z)</tex>
 +
  |<font color="black">Тернарное сложение по модулю 2</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x)
+
  !<tex>\geq 2(x,y,z)</tex>
  |переключатель по большинству, 3-ППБ, мажоритарный клапан
+
|align = center|<tex>(x </tex> <font color="black">И</font> <tex>y) </tex><font color="black">ИЛИ </font><tex>(y</tex><font color="black"> И</font><tex> z)</tex><font color="black"> ИЛИ</font> <tex>(z </tex><font color="black">И</font><tex> x)</tex>
 +
  |<font color="black">переключатель по большинству, 3-ППБ, мажоритарный клапан</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''f<sub>1</sub>''
+
  !<tex>f_1</tex>
  |Разряд займа при тернарном вычитании
+
  |
 +
|<font color="black">Разряд займа при тернарном вычитании</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|''f<sub>2</sub>''
+
  !<tex>f_2</tex>
  |Разряд переноса при тернарном сложении
+
  |
 +
|<font color="black">Разряд переноса при тернарном сложении</font>
 
  |-
 
  |-
  !bgcolor=#EEEEFF|(x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)
+
  !<tex>x+y+z</tex>
  |3-ИЛИ, максимум
+
|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>
  
 
=== Тождественность и двойственность ===
 
=== Тождественность и двойственность ===
Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:<br />
+
 
<math>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</math>
+
{{Определение
 +
|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"
 
{| style="width:15cm"
 
|-
 
|-
| <math>\overline{0}=1</math> || <math>\overline{1}=0</math> || <math>\overline{\overline{x}}=x</math>
+
| <tex>\overline{0}=1</tex> || <tex>\overline{1}=0</tex> || <tex>\overline{\overline{x}}=x</tex>
|| <math>xy=yx\!</math> || <math>x\lor y=y \lor x</math>
+
|| <tex>x \land y=y \land x\!</tex> || <tex>x\lor y=y \lor x</tex>
 
|-
 
|-
|| <math>0x=0\!</math> || <math>1x=x\!</math> || <math>0\lor x=x</math> || <math>1\lor x=1</math> || <math>xx=x\lor x=x</math>
+
|| <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:15cm"
+
{| style="width:9cm"
 
|-
 
|-
| <math>x\overline{x}=0</math> || <math>x\lor\overline{x}=1</math>
+
| <tex>x \land \overline{x}=0</tex> ||<tex>x \lor \overline{x}=1</tex>
 
|}
 
|}
 
{| style="width:15cm"
 
{| style="width:15cm"
 
|-
 
|-
| <math>\overline{x\cdot y}=\overline{x}\lor\overline{y}</math>
+
| <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex>
|| <math>\overline{x}\cdot\overline{y}=\overline{x\lor y}</math> || (законы де Моргана)
+
|| <tex>\overline{x}\land\overline{y}=\overline{x\lor y}</tex>|| (законы де Моргана)
 
|}
 
|}
<math>x(y\lor z)=xy\lor xz</math><br />
+
<tex>x \land (y\lor z)=(x \land y)\lor (x \land z)</tex><br />
<math>x\lor yz=(x\lor y)(x\lor z)</math> (дистрибутивность конъюнкции и дизъюнкции)
+
<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>, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
  
Функция <math>g(x_1,x_2,\dots,x_n)</math> называется двойственной функции <math>f(x_1,x_2,\dots,x_n)</math>, если <math>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</math>. Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
+
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
  
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
+
=== Суперпозиции ===
 +
{{main|Суперпозиции}}
 +
{{Определение
 +
|definition =
 +
'''Суперпозиция функций, композиция функций''' (англ. ''function composition'') {{---}} функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
 +
}}
 +
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.
 +
 
 +
Пусть нам дан некоторый набор булевых функций <tex>K</tex>. Получить новую функцию, являющеюся композицией функций из <tex>K</tex>, мы можем следующими способами:
 +
*Подстановкой одной функции в качестве некоторого аргумента для другой;
 +
*Отождествлением аргументов функций.
  
 
=== Полнота системы, критерий Поста ===
 
=== Полнота системы, критерий Поста ===
  
Система булевых функций называется ''полной'', если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.
+
{{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>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
+
== Представление булевых функций ==
* Самодвойственные функции <math>S</math>;
 
* Монотонные функции <math>M</math>;
 
* Линейные функции <math>L</math>.
 
Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с <math>P_2</math>, целиком содержится в одном из этих пяти так называемых ''предполных классов'', но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.
 
  
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
+
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
== Представление булевых функций ==
 
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <math>\Sigma = \{f_1,\ldots,f_n\}</math>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <math>\Sigma</math>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
 
 
* Как построить по данной функции представляющую её формулу?
 
* Как построить по данной функции представляющую её формулу?
 
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
 
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
Строка 357: Строка 438:
  
 
=== Дизъюнктивная нормальная форма (ДНФ) ===
 
=== Дизъюнктивная нормальная форма (ДНФ) ===
''Простой конъюнкцией'' или ''конъюнктом'' называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. ''Дизъюнктивной нормальной формой'' или ''ДНФ'' называется дизъюнкция простых конъюнкций.
 
Элементарная конъюнкция
 
* '''правильная''', если в неё каждая переменная входит не более одного раза (включая отрицание);
 
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
 
* '''монотонная''', если она не содержит отрицаний переменных.
 
Например <math>a \overline{b} c\lor b c\lor\overline{a}</math>&nbsp; — является ДНФ.
 
  
''Совершенной дизъюнктивной нормальной формой'' или ''СДНФ'' относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: <math>a \overline{b} c\lor a b c\lor\overline{a} b\overline{c}</math>.
+
{{main|ДНФ}}
 +
{{Определение
 +
|definition =
 +
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.
 +
}}
 +
Любая булева формула благодаря использованию  закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.
  
Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора <math>b=(b_1,b_2,\ldots,b_n)</math> построить конъюнкцию <math>x_1^{b_1} x_2^{b_2}\ldots x_n^{b_n}</math>, где <math>x_i^1 = x_i</math> <math>x_i^0 = \overline{x_i}</math>. Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации <math>x\to y</math> результатом является <math>\overline{x} y \lor \overline{x}\, \overline{y}\lor x y</math>, что можно упростить до <math>\overline{x}\lor y</math>.
+
'''Примеры ДНФ:'''
  
 +
<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>
<center><math>a (b\lor c)\to a b\lor a c</math></center>
 
которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило
 
<center><math>a\lor b c\to (a \lor b)(a \lor c)</math></center>
 
выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.
 
  
 +
<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|Полином Жегалкина}}
 
{{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|Реализация булевой функции схемой из функциональных элементов}}
 
{{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.
 
* ''Гаврилов Г. П., Сапоженко А. А.'' Сборник задач по дискретной математике. — М.: Наука, 1969.
 
* ''Кузнецов О. П., Адельсон-Вельский Г. М.'' Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
 
* ''Кузнецов О. П., Адельсон-Вельский Г. М.'' Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
Строка 395: Строка 692:
 
* ''Яблонский С. В.'' Введение в дискретную математику. — М.: Наука, 1986.
 
* ''Яблонский С. В.'' Введение в дискретную математику. — М.: Наука, 1986.
 
* ''Алексеев В. Б.'' Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
 
* ''Алексеев В. Б.'' Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
 
== Ссылки ==
 
<references/>
 
 
* [http://ido.tsu.ru/iop_res/bulevfunc/index.html ''Быкова С. В., Буркатовская Ю. Б.'', Булевы функции, учебно-методический комплекс, Томск, 2006]
 
* [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
 
* http://psi-logic.narod.ru/bool/bool.htm
* [http://mathcyb.cs.msu.su/books.html Учебные пособия кафедры математической кибернетики ВМиК МГУ]
+
* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]
+
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Булевы функции ]]

Текущая версия на 19:10, 4 сентября 2022

Определение:
Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики, англ. Boolean function) от [math]n[/math] переменных — отображение [math]B^n\rightarrow B[/math], где [math]B = \{0, 1\}[/math] — булево множество.

Элементы булева множества [math]1[/math] и [math]0[/math] обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения [math]B^n[/math] называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается [math]P_2[/math], а от n переменных — [math]P_2(n)[/math]. Булевы функции названы так по фамилии математика Джорджа Буля.

Основные сведения

Определение:
А́рность (англ. arity) функции — количество ее аргументов.

Каждая булева функция арности [math]n[/math] полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины [math]n[/math]. Число таких векторов равно [math]2^n[/math]. Поскольку на каждом векторе булева функция может принимать значение либо [math]0[/math], либо [math]1[/math], то количество всех n-арных булевых функций равно [math]{2^2}^n[/math]. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:


Таблица истинности
[math]x_1[/math] [math]x_2[/math] [math]\ldots[/math] [math]x_n[/math] [math]f(x_1,x_2,\ldots,x_n)[/math]
[math]0[/math] [math]0[/math] [math]\ldots[/math] [math]0[/math] [math]f(0,0,\ldots,0)[/math]
[math]1[/math] [math]0[/math] [math]\ldots[/math] [math]0[/math] [math]f(1,0,\ldots,0)[/math]
[math]0[/math] [math]1[/math] [math]\ldots[/math] [math]0[/math] [math]f(0,1,\ldots,0)[/math]
[math]1[/math] [math]1[/math] [math]\ldots[/math] [math]0[/math] [math]f(1,1,\ldots,0)[/math]
[math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math]
[math]0[/math] [math]1[/math] [math]\ldots[/math] [math]1[/math] [math]f(0,1,\ldots,1)[/math]
[math]1[/math] [math]1[/math] [math]\ldots[/math] [math]1[/math] [math]f(1,1,\ldots,1)[/math]

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

Нульарные функции

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

Унарные функции

При [math]n = 1[/math] число булевых функций равно [math]{2^2}^1 = 2^2 = 4[/math].

Таблица значений булевых функций от одной переменной:


Функции от одной переменной
[math]0[/math] [math]x[/math] [math]\neg x[/math] [math]1[/math]
0 [math]0[/math] [math]0[/math] [math]1[/math] [math]1[/math]
1 [math]0[/math] [math]1[/math] [math]0[/math] [math]1[/math]
Сохраняет 0
Сохраняет 1
Самодвойственная
Монотонная
Линейная

Названия булевых функций от одной переменной:

Обозначение Название
[math]0[/math] тождественный ноль, тождественная ложь, тождественное "НЕТ"
[math]x[/math] тождественная функция, логическое "ДА", "YES"(англ.)
[math]\bar x,\ \neg x,\ x'[/math] отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
[math]1[/math] тождественная единица, тождественная истина, тождественное "ДА", тавтология

Бинарные функции

При [math]n = 2[/math] число булевых функций равно [math]{2^2}^2 = 2^4 = 16[/math].

Таблица значений булевых функций от двух переменных:

Функции от двух переменных:
x y [math]0[/math] [math]x \land y[/math] [math]x \nrightarrow y[/math] [math]x[/math] [math]x \nleftarrow y[/math] [math]y[/math] [math]x \oplus y[/math] [math]x \lor y[/math] [math]x \downarrow y[/math] [math]x = y[/math] [math]\neg y[/math] [math]x \leftarrow y[/math] [math]\neg x[/math] [math]x \rightarrow y[/math] [math]x \triangledown y[/math] [math]1[/math]
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Сохраняет 0
Сохраняет 1
Самодвойственная
Монотонная
Линейная

Названия булевых функций от двух переменных:

Обозначение Другие обозначения Название
[math]0[/math] тождественный ноль, тождественная ложь, тождественное "НЕТ"
[math]x \land y[/math] [math]x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y), x [/math] И [math]y,[/math] И[math](x, y)[/math] 2И, конъюнкция
[math]x \nrightarrow y[/math] [math]x \gt y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)[/math] больше, инверсия прямой импликации
[math]x[/math] [math]YES1(x,y),[/math] ДА1[math](x, y)[/math] первый операнд
[math]x \nleftarrow y[/math] [math]x \lt y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)[/math] меньше, инверсия обратной импликации
[math]y[/math] [math]YES2(x, y),[/math] ДА2[math](x, y)[/math] второй операнд
[math]x \oplus y[/math] [math]x + _2 y,\ x \not = y,\ x \gt \lt y,\ x \lt \gt y,\ x\ XOR\ y,\ XOR(x,y)[/math] сложение по модулю 2, не равно, ксор, исключающее «или»
[math]x \lor y[/math] [math]x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),[/math] [math]x [/math]ИЛИ [math]y,[/math] ИЛИ[math](x, y)[/math] 2ИЛИ, дизъюнкция
[math]x \downarrow y[/math] [math]x\ NOR\ y,\ NOR(x,y)[/math] [math]x [/math]ИЛИ-НЕ [math]y,[/math] ИЛИ-НЕ[math](x, y)[/math] НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
[math]x = y[/math] [math]x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y[/math] равенство, эквивалентность
[math]\neg y[/math] [math]NOT2(x, y),\ y',\ \bar{y},[/math] НЕ2[math](x, y)[/math] отрицание (негация, инверсия) второго операнда
[math]x \leftarrow y[/math] [math]x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)[/math] больше или равно, обратная импликация (от второго аргумента к первому)
[math]\neg x[/math] [math]NOT1(x,y),\ x',\ \bar{x},[/math] НЕ1[math](x, y)[/math] отрицание (негация, инверсия) первого операнда
[math]x \rightarrow y[/math] [math]x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)[/math] меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)
[math]x \triangledown y[/math] [math]x \mid y,\ x\ NAND\ y,\ NAND(x,y),[/math] [math]x [/math] И-НЕ [math]y,[/math] И-НЕ[math](x, y)[/math] НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера
[math]1[/math] тождественная единица, тождественная истина, тождественное "ДА", тавтология

Тернарные функции

При [math]n = 3[/math] число булевых функций равно [math]{2^2}^3 = 2^8 = 256[/math]. Некоторые из них определены в следующей таблице:

Таблица истинности некоторых тернарных функций
[math]x[/math] [math]y[/math] [math]z[/math] [math]x \downarrow y \downarrow z[/math] [math]\neg (\geq 2(x,y,z))[/math] [math]x \not = y \not = z[/math] [math]x \mid y \mid z[/math] [math]min(x,y,z)[/math] [math]x=y=z[/math] [math]x \oplus y \oplus z[/math] [math]\geq 2(x,y,z)[/math] [math]f_1[/math] [math]f_2[/math] [math]max(x,y,z)[/math]
0 0 0 1 1 0 1 0 1 0 0 0 0 0
0 0 1 0 1 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 0 0 1 0 0 0 1
0 1 1 0 0 1 1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 0 0 1 0 1 0 1
1 0 1 0 0 1 1 0 0 0 1 0 1 1
1 1 0 0 0 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 1 1 1 1 1 1 1

Названия булевых функций трех переменных:

Обозначения Другие обозначения Названия
[math]x \downarrow y \downarrow z[/math] [math]\downarrow (x,y,z) = Webb_2 (x,y,z)[/math] 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
[math]\neg (\geq 2(x,y,z))[/math] Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
[math]x \not = y \not = z[/math] [math][\not =(x,y,z)] = NE(x,y,z)[/math] Неравенство
[math]x \mid y \mid z[/math] [math]\mid(x,y,z)[/math] 3-И-НЕ, штрих Шеффера
[math]x \land y \land z[/math] [math]\land (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z) = \lt br/\gt (x[/math] И[math] y[/math] И[math] z) = [/math] И[math](x,y,z)[/math] 3-И, минимум
[math]x=y=z[/math] [math][=(x,y,z)] = EQV(x,y,z)[/math] Равенство
[math]x \oplus y \oplus z[/math] [math]x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)[/math] Тернарное сложение по модулю 2
[math]\geq 2(x,y,z)[/math] [math](x [/math] И [math]y) [/math]ИЛИ [math](y[/math] И[math] z)[/math] ИЛИ [math](z [/math]И[math] x)[/math] переключатель по большинству, 3-ППБ, мажоритарный клапан
[math]f_1[/math] Разряд займа при тернарном вычитании
[math]f_2[/math] Разряд переноса при тернарном сложении
[math]x+y+z[/math] [math]+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) = (x [/math] ИЛИ[math] y [/math] ИЛИ[math] z) = [/math] ИЛИ[math](x,y,z)[/math] 3-ИЛИ, максимум

Представление функции формулой

Определение:
Если выбрать некоторый набор булевых функций [math]A[/math], то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula).

Например, если [math]A = \left\{\land,\neg\right\}[/math], то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]

Тождественность и двойственность

Определение:
Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения.

Тождественность функций f и g можно записать, например, так:
[math]f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)[/math]

Просмотрев таблицы истинности булевых функций, легко получить такие тождества:

[math]\overline{0}=1[/math] [math]\overline{1}=0[/math] [math]\overline{\overline{x}}=x[/math] [math]x \land y=y \land x\![/math] [math]x\lor y=y \lor x[/math]
[math]0 \land x=0\![/math] [math]1 \land x=x\![/math] [math]0 \lor x=x[/math] [math]1\lor x=1[/math] [math]x \land x=x \lor x=x[/math]

А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:

[math]x \land \overline{x}=0[/math] [math]x \lor \overline{x}=1[/math]
[math]\overline{x \land y}=\overline{x}\lor\overline{y}[/math] [math]\overline{x}\land\overline{y}=\overline{x\lor y}[/math] (законы де Моргана)

[math]x \land (y\lor z)=(x \land y)\lor (x \land z)[/math]
[math]x \lor (y \land z)=(x\lor y) \land (x\lor z)[/math] (дистрибутивность конъюнкции и дизъюнкции)


Определение:
Функция [math]g(x_1,x_2,\dots,x_n)[/math] называется двойственной (англ. duality) функции [math]f(x_1,x_2,\dots,x_n)[/math], если [math]f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}[/math].

Легко показать, что в этом равенстве [math]f[/math] и [math]g[/math] можно поменять местами, то есть функции [math]f[/math] и [math]g[/math] двойственны друг другу. Из простейших функций двойственны друг другу константы [math]0[/math] и [math]1[/math], а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.

Суперпозиции

Основная статья: Суперпозиции
Определение:
Суперпозиция функций, композиция функций (англ. function composition) — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.

Пусть нам дан некоторый набор булевых функций [math]K[/math]. Получить новую функцию, являющеюся композицией функций из [math]K[/math], мы можем следующими способами:

  • Подстановкой одной функции в качестве некоторого аргумента для другой;
  • Отождествлением аргументов функций.

Полнота системы, критерий Поста

Определение:
Замыкание множества функций (англ. сlosure) — подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества.


Определение:
Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций.

Американский математик Эмиль Пост [1] сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

  • функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math],
  • самодвойственныые функции [math]S[/math],
  • монотонные функции [math]M[/math],
  • линейные функции [math]L[/math].

Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math], иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Представление булевых функций

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

  • Как построить по данной функции представляющую её формулу?
  • Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
    • В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
  • Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?

Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.

Дизъюнктивная нормальная форма (ДНФ)

Основная статья: ДНФ
Определение:
Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов.

Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.

Примеры ДНФ:

[math]f(x,y,z) = (x \land y) \lor (y \land \neg {z})[/math].

[math]f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) [/math].

Конъюнктивная нормальная форма (КНФ)

Основная статья: КНФ
Определение:
Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.

Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.

Пример КНФ:

[math]f(x,y,z) = (x \lor y) \land (y \lor \neg{z})[/math]

[math]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)[/math]

[math]f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})[/math]

Полином Жегалкина

Основная статья: Полином Жегалкина
Определение:
Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида [math]0[/math] и [math]1[/math], где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или.

Полином Жегалкина имеет следующий вид:

[math]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 [/math]

С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math], который, в свою очередь, по теореме Поста является полным.

Примеры:

[math]f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 [/math]

[math]f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 [/math]

[math]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 [/math]

Тождественные функции. Выражение функций друг через друга

Определение:
Тождественные функции — функции, которые при любых одинаковых аргументах принимают равные значения.

Приведение тождественной функции есть выражение булевой функции через другие.

Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.

Пример:
Выразим следующие функции через систему функций [math]\{\land, \lor, \lnot \} [/math].

[math] 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 )[/math]

[math] x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y[/math]

[math]\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 )[/math]

Подстановка одной функции в другую

Определение:
Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math]-того аргумента функции [math]f[/math] значением функции [math]g[/math]:
[math]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})[/math]

Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.

При подстановке функции [math]g[/math] вместо [math]i[/math]-того аргумента функции [math]f[/math], результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:

1. [math] x_{1}, \ldots, x_{i-1}[/math] — аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math]
2. [math] x_{i}, \ldots, x_{i+m-1} [/math] — используются как аргументы для вычисления значения функции [math]g(y_{1}, \ldots, y_{m})[/math]
3. [math] x_{i+m}, \ldots, x_{n+m-1} [/math] — аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math]
Пример:
Исходные функции:
  1. [math] f(a,b) = a \vee b [/math]
  2. [math] g(a) = \neg a [/math]
[math] h(a,b) = f(a,g(b)) = a \vee \neg b [/math] — подстановка функции [math]g[/math] вместо второго аргумента функции [math]f[/math]. В данном примере при помощи подстановки мы получили функцию [math]h(a,b)=a \leftarrow b[/math].

Отождествление переменных

Определение:
Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math]-того аргумента функции [math]f[/math] вместо [math]j[/math]-того аргумента:
[math]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})[/math]

Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math].

Пример:
[math] f(a,b) = a \vee b [/math] — исходная функция

[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию [math]P_{1}[/math] — проектор единственного аргумента.

Схемы из функциональных элементов

Определение:
Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе [math]B[/math], в котором:

1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);

2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса [math]B[/math]). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса [math]B[/math].

Отождествление переменных осуществляется при помощи ветвления проводников.

Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.

Некоторые логические элементы:

И ИЛИ НЕ Штрих Шеффера Стрелка Пирса
AND logic element.png OR logic element.png NOT logic element.png NAND logic element.png NOR logic element.png

Стандартный базис

Определение:
Стандартный базис — система булевых функций: [math]\{\land, \lor, \lnot \} [/math]


Если рассматривать множество бинарных булевых функций [math]P_2(2)[/math], то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы [math] 0 [/math] с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:

[math] x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) [/math]

[math] x \rightarrow y = \lnot x \lor y [/math]

[math] 0 = x \land \lnot x [/math]

Функции [math] \mid \ и \downarrow[/math] являются отрицаниями функций [math] \land \ и \ \lor[/math] соответственно.

[math] x \mid y = \lnot \left ( x \land y \right )[/math]

[math] x \downarrow y = \lnot \left ( x \lor y \right )[/math]

Тождественность функций можно доказать с помощью таблицы истинности.

Пример:

Выразим через стандартный базис обратную импликацию [math] \left (x \leftarrow y \right ) [/math].

[math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]

Полнота стандартного базиса

Утверждение:
Стандартный базис является полной системой булевых функций
[math]\triangleright[/math]
Данное утверждение - следствие теоремы об СДНФ. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.
[math]\triangleleft[/math]

Замечание:

По закону де Моргана:

[math] x \land y = \lnot \left (\lnot x \lor \lnot y \right ) [/math]

[math] x \lor y = \lnot \left (\lnot x \land \lnot y \right ) [/math]

Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:

[math] \{ \land , \lnot \} [/math] (конъюнктивный базис Буля)

[math] \{ \lor , \lnot \} [/math] (дизъюнктивный базис Буля)

Теоремы о числе функций в базисе

Теорема:
Максимально возможное число булевых функций в безызбыточном базисе — четыре.
Доказательство:
[math]\triangleright[/math]

Рассмотрим произвольный безызбыточный базис [math] X[/math]. Тогда по теореме Поста [math]X[/math] содержит следующие функции (не обязательно различные):

[math]f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L[/math], где [math] T_0, T_1, S, M, L[/math] — классы Поста.

Значит, так как [math]X[/math] — безызбыточный базис, а система [math]\{f_0, f_1, f_s, f_m, f_l \}[/math] — полная, то [math]\left | X \right | \le 5[/math]

Рассмотрим [math]f_0[/math]. Возможны два случая:

1. [math] f_0(1, 1, \ldots, 1) = 0 [/math], тогда [math]f_0[/math] также не сохраняет единицу и немонотонная, т.е.

[math] f_0 = f_1 = f_m [/math]. Значит, [math]\left | X \right | \le 3[/math].

2. [math] f_0(1, 1, \ldots, 1) = 1 [/math], тогда [math]f_0[/math] несамодвойственная, т.е.

[math] f_0 = f_s [/math]. Значит, [math]\left | X \right | \le 4[/math].
[math]\triangleleft[/math]
Теорема:
Для любого числа [math]k, 1 \le k \le 4 [/math] найдётся базис [math] X[/math], что [math]\left | X \right | = k[/math].
Доказательство:
[math]\triangleright[/math]

Приведём примеры базисов для каждого [math]k[/math]:

[math]k = 1 \Rightarrow X = \{ \downarrow \}[/math];

[math]k = 2 \Rightarrow X = \{ \lnot, \land \}[/math];

[math]k = 3 \Rightarrow X = \{ \land, \oplus, 1\}[/math];

[math]k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}[/math];

Докажем, что последняя система является базисом:

[math] 0 \notin T_1[/math];

[math] 1 \notin T_0[/math];

[math] x\land y \notin L\ и\ S[/math];

[math] x\oplus y\oplus z \notin M[/math]

(доказывается с помощью таблицы истинности).
[math]\triangleleft[/math]

См. также

Примечания

Источники информации