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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Полные системы булевых функций)
м (rollbackEdits.php mass rollback)
 
(не показаны 53 промежуточные версии 11 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''') от <tex>n</tex> переменных — отображение <tex>B_n</tex> → <tex>B</tex>, где <tex>B = \{0, 1\}</tex> — булево множество.}}  
+
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''', англ.  ''Boolean function'') от <tex>n</tex> переменных — отображение <tex>B^n\rightarrow B</tex>, где <tex>B = \{0, 1\}</tex> — булево множество.}}  
Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения ''B''<sup>''n''</sup> называют ''булевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается ''P''<sub>2</sub>, а от ''n'' переменных — ''P''<sub>2</sub>(''n''). Булевы функции названы так по фамилии математика Джорджа Буля.
+
Элементы булева множества <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>
  
 
Названия булевых функций от одной переменной:
 
Названия булевых функций от одной переменной:
{| border=1
+
<center>
 +
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
|-align="center"
 
  !Обозначение
 
  !Обозначение
 
  !Название
 
  !Название
 
  |-
 
  |-
 
  !<tex>0</tex>
 
  !<tex>0</tex>
  |тождественный ноль, тождественная ложь, тождественное "НЕТ"
+
  |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>
 
  |-
 
  |-
 
  !<tex>x</tex>
 
  !<tex>x</tex>
  |тождественная функция, логическое "ДА", "YES"(англ.)
+
  |<font color="black">тождественная функция, логическое "ДА", "YES"(англ.)</font>
 
  |-
 
  |-
 
  !<tex>\bar x,\ \neg x,\ x'</tex>
 
  !<tex>\bar x,\ \neg x,\ x'</tex>
  |отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
+
  |<font color="black">отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)</font>
 
  |-
 
  |-
 
  !<tex>1</tex>
 
  !<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;
 
|! width="5%" | <tex>\nrightarrow</tex>
 
|! width="5%" | x
 
|! width="5%" | <tex>\nleftarrow</tex>
 
|! width="5%" | y
 
|! width="5%" | &oplus;
 
|! width="5%" | &or;
 
|! width="5%" | &darr;
 
|! width="5%" | &harr;
 
|! width="5%" | &not;y
 
|! width="5%" | &larr;
 
|! width="5%" | &not;x
 
|! width="5%" | &rarr;
 
|! width="5%" | &nabla;
 
|! width="5%" | 1
 
 
|-align="center"
 
|-align="center"
  !0||0
+
  !<font color="black">x</font>||<font color="black">y</font>
 +
|! width="5%" | <tex>0</tex>
 +
|! width="5%" | <tex>x \land y</tex>
 +
|! width="5%" | <tex>x \nrightarrow y</tex>
 +
|! width="5%" | <tex>x</tex>
 +
|! width="5%" | <tex>x \nleftarrow y</tex>
 +
|! width="5%" | <tex>y</tex>
 +
|! width="5%" | <tex>x \oplus y</tex>
 +
|! width="5%" | <tex>x \lor y</tex>
 +
|! width="5%" | <tex>x \downarrow y</tex>
 +
|! width="5%" | <tex>x = y</tex>
 +
|! width="5%" | <tex>\neg y</tex>
 +
|! width="5%" | <tex>x \leftarrow y</tex>
 +
|! width="5%" | <tex>\neg x</tex>
 +
|! width="5%" | <tex>x \rightarrow y</tex>
 +
|! width="5%" | <tex>x \triangledown y</tex>
 +
|! width="5%" | <tex>1</tex>
 +
|-align="center"
 +
!<font color="black">0</font>||<font color="black">0</font>
 
|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1
 
|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"
 
  !Обозначение
 
  !Обозначение
 
  !Другие обозначения
 
  !Другие обозначения
Строка 144: Строка 169:
 
  !<tex>0</tex>
 
  !<tex>0</tex>
 
  |
 
  |
  |тождественный ноль, тождественная ложь, тождественное "НЕТ"
+
  |<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>
 
  |-
 
  |-
  !<tex>x \wedge y</tex>
+
  !<tex>x \land y</tex>
  |align = center|<tex>x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y),</tex> ''x И y, И(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>
 
  |-
 
  |-
 
  !<tex>x \nrightarrow y</tex>
 
  !<tex>x \nrightarrow y</tex>
 
  |align = center|<tex>x > y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ 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>
 
  !<tex>x</tex>
  |align = center|<tex>YES1(x,y),</tex> ''ДА1(x, y)''
+
  |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>
 
  !<tex>x \nleftarrow y</tex>
 
  |align = center|<tex>x < y,\ \neg(x \leftarrow y),\ x\ LT\ y,\  LT(x, 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>
 
  !<tex>y</tex>
  |align = center|<tex>YES2(x, y),</tex> ''ДА2(x, y)''
+
  |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>
 
  !<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>
 
  |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>
 
  |-
 
  |-
  !<tex>x \vee y</tex>
+
  !<tex>x \lor y</tex>
  |align = center|<tex>x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),</tex> ''x ИЛИ y, ИЛИ(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>
 
  |-
 
  |-
 
  !<tex>x \downarrow y</tex>
 
  !<tex>x \downarrow y</tex>
  |align = center|<tex>x\ NOR\ y,\ NOR(x,y)</tex> ''x ИЛИ-НЕ y, ИЛИ-НЕ(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>
 
  |-
 
  |-
 
  !<tex>x = y</tex>
 
  !<tex>x = y</tex>
 
  |align = center|<tex>x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow 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>\bar{y}</tex>
+
  !<tex>\neg y</tex>
  |align = center|<tex>NOT2(x, y),\ y',\ \neg y,</tex> ''НЕ2(x, y)''
+
  |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>
 
  !<tex>x \leftarrow y</tex>
 
  |align = center|<tex>x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)</tex>
 
  |align = center|<tex>x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)</tex>
  |больше или равно, обратная импликация (от второго аргумента к первому)
+
  |<font color="black">больше или равно, обратная импликация (от второго аргумента к первому)</font>
 
  |-
 
  |-
  !<tex>\bar{x}</tex>
+
  !<tex>\neg x</tex>
  |align = center|<tex>NOT1(x,y),\ x',\ \neg x,</tex> ''НЕ1(x, y)''
+
  |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>
 
  !<tex>x \rightarrow y</tex>
 
  |align = center|<tex>x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,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>
 
  !<tex>x \triangledown y</tex>
  |align = center|<tex>x \mid y,\ x\ NAND\ y,\ NAND(x,y),</tex> ''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>
 
  |-
 
  |-
 
  !<tex>1</tex>
 
  !<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"
 +
|+
 +
!colspan="14"|Таблица истинности некоторых тернарных функций
 +
|-align="center"
 
  !class="dark" style="font-weight:normal"| <tex>x</tex>
 
  !class="dark" style="font-weight:normal"| <tex>x</tex>
 
  !class="dark" style="font-weight:normal"| <tex>y</tex>
 
  !class="dark" style="font-weight:normal"| <tex>y</tex>
Строка 226: Строка 255:
 
  !style="font-weight:normal"| <tex>max(x,y,z)</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"
 
  !Обозначения
 
  !Обозначения
 
  !Другие обозначения
 
  !Другие обозначения
Строка 276: Строка 308:
 
  !<tex>x \downarrow y \downarrow z</tex>  
 
  !<tex>x \downarrow y \downarrow z</tex>  
 
  |align = center|<tex>\downarrow (x,y,z) = Webb_2 (x,y,z)</tex>
 
  |align = center|<tex>\downarrow (x,y,z) = Webb_2 (x,y,z)</tex>
  |3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
+
  |<font color="black"> 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса</font>
 
  |-
 
  |-
 
  !<tex>\neg (\geq 2(x,y,z))</tex>
 
  !<tex>\neg (\geq 2(x,y,z))</tex>
 
  |
 
  |
  |Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
+
  |<font color="black">Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией</font>
 
  |-
 
  |-
 
  !<tex>x \not = y \not = z</tex>
 
  !<tex>x \not = y \not = z</tex>
 
  |align = center|<tex>[\not =(x,y,z)] = NE(x,y,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>
 
  !<tex>x \mid y \mid z</tex>
 
  |align = center|<tex>\mid(x,y,z)</tex>
 
  |align = center|<tex>\mid(x,y,z)</tex>
  |3-И-НЕ, штрих Шеффера
+
  |<font color="black">3-И-НЕ, штрих Шеффера</font>
 
  |-
 
  |-
  !<tex>x \wedge y \wedge z</tex>
+
  !<tex>x \land y \land z</tex>
  |align = center|<tex>\wedge (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z)</tex> ''= (x И y И z) = И(x,y,z)''
+
  |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>
  |3-И, минимум
+
  |<font color="black">3-И, минимум</font>
 
  |-
 
  |-
 
  !<tex>x=y=z</tex>
 
  !<tex>x=y=z</tex>
 
  |align = center|<tex>[=(x,y,z)]  = EQV(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>
 
  !<tex>x \oplus y \oplus z</tex>
 
  |align = center|<tex>x +_2 y +_2 z =  \oplus (x,y,z) = +_2 (x,y,z)</tex>
 
  |align = center|<tex>x +_2 y +_2 z =  \oplus (x,y,z) = +_2 (x,y,z)</tex>
  |Тернарное сложение по модулю 2
+
  |<font color="black">Тернарное сложение по модулю 2</font>
 
  |-
 
  |-
 
  !<tex>\geq 2(x,y,z)</tex>
 
  !<tex>\geq 2(x,y,z)</tex>
  |align = center|''(x И y) ИЛИ (y И z) ИЛИ (z И x)''
+
  |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>
  |переключатель по большинству, 3-ППБ, мажоритарный клапан
+
  |<font color="black">переключатель по большинству, 3-ППБ, мажоритарный клапан</font>
 
  |-
 
  |-
 
  !<tex>f_1</tex>
 
  !<tex>f_1</tex>
 
  |
 
  |
  |Разряд займа при тернарном вычитании
+
  |<font color="black">Разряд займа при тернарном вычитании</font>
 
  |-
 
  |-
 
  !<tex>f_2</tex>
 
  !<tex>f_2</tex>
 
  |
 
  |
  |Разряд переноса при тернарном сложении
+
  |<font color="black">Разряд переноса при тернарном сложении</font>
 
  |-
 
  |-
 
  !<tex>x+y+z</tex>
 
  !<tex>x+y+z</tex>
  |align = center|<tex>+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) =</tex> ''(x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)''
+
  |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>
  |3-ИЛИ, максимум
+
  |<font color="black">3-ИЛИ, максимум</font>
 
|}
 
|}
  
== Полные системы булевых функций ==
+
</center>
  
=== Суперпозиции ===
+
=== Представление функции формулой ===
  
{{main|Суперпозиции}}
+
{{Определение
 +
|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>
  
 
=== Тождественность и двойственность ===
 
=== Тождественность и двойственность ===
Строка 329: Строка 364:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения.}}
+
Две булевы функции '''тождественны''' (англ. ''identical'') друг другу, если на любых одинаковых наборах аргументов они принимают равные значения.}}
 
Тождественность функций f и g можно записать, например, так:<br />
 
Тождественность функций f и g можно записать, например, так:<br />
<math>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</math>
+
<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=
 
|definition=
Функция <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>.}}
+
Функция <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>.}}
Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
+
Легко показать, что в этом равенстве <tex>f</tex> и <tex>g</tex> можно поменять местами, то есть функции <tex>f</tex> и <tex>g</tex> двойственны друг другу. Из простейших функций двойственны друг другу константы <tex>0</tex> и <tex>1</tex>, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
  
 
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
 
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
 +
 +
=== Суперпозиции ===
 +
{{main|Суперпозиции}}
 +
{{Определение
 +
|definition =
 +
'''Суперпозиция функций, композиция функций''' (англ. ''function composition'') {{---}} функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
 +
}}
 +
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.
 +
 +
Пусть нам дан некоторый набор булевых функций <tex>K</tex>. Получить новую функцию, являющеюся композицией функций из <tex>K</tex>, мы можем следующими способами:
 +
*Подстановкой одной функции в качестве некоторого аргумента для другой;
 +
*Отождествлением аргументов функций.
  
 
=== Полнота системы, критерий Поста ===
 
=== Полнота системы, критерий Поста ===
  
 
{{main|Теорема Поста о полной системе функций}}
 
{{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|Представление функции формулой, полные системы функций}}
+
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
 
 
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <math>\Sigma = \{f_1,\ldots,f_n\}</math>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <math>\Sigma</math>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
 
 
* Как построить по данной функции представляющую её формулу?
 
* Как построить по данной функции представляющую её формулу?
 
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
 
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
Строка 379: Строка 439:
 
=== Дизъюнктивная нормальная форма (ДНФ) ===
 
=== Дизъюнктивная нормальная форма (ДНФ) ===
  
{{main|СДНФ}}
+
{{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|СКНФ}}
+
{{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|Полином Жегалкина}}
 
{{main|Полином Жегалкина}}
 +
{{Определение
 +
|definition =
 +
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или.
 +
}}
 +
Полином Жегалкина имеет следующий вид:
  
 +
<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0}  x_2 \oplus \ldots \oplus a_{00\ldots01}  x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11\ldots1} x_1 x_2 \ldots x_n  </tex>
 +
 +
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций:  <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.
 +
 +
'''Примеры:'''
 +
 +
<tex>f(x_1,x_2) =  1 \oplus x_1 \oplus x_1 x_2  </tex>
 +
 +
<tex>f(x_1,x_2,x_3) =  x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex>
 +
 +
<tex>f(x_1,x_2,x_3,x_4) =  1 \oplus x_1  \oplus x_4  \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 </tex>
 +
 +
===Тождественные функции. Выражение функций друг через друга===
 +
 +
{{Определение
 +
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.
 +
}}
 +
Приведение тождественной функции есть '''выражение булевой функции через другие'''.
 +
 +
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
 +
{{Пример
 +
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.
 +
 +
<tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex>
 +
 +
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex>
 +
 +
<tex>\langle x, y, z \rangle =  \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )</tex>
 +
}}
 +
=== Подстановка одной функции в другую ===
 +
 +
{{Определение
 +
|definition =
 +
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:
 +
 +
<center><tex>h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})</tex></center>
 +
}}
 +
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
 +
 +
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:
 +
 +
{|
 +
|1. <tex> x_{1}, \ldots, x_{i-1}</tex>
 +
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex>
 +
|-
 +
|2. <tex> x_{i}, \ldots, x_{i+m-1}  </tex>
 +
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex>
 +
|-
 +
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex>
 +
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex>
 +
|}
 +
{{Пример
 +
|example=Исходные функции:
 +
#<tex> f(a,b) = a \vee b </tex>
 +
#<tex> g(a)  = \neg a </tex>
 +
 +
<tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.
 +
}}
 +
=== Отождествление переменных ===
 +
{{Определение
 +
|definition=
 +
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:
 +
 +
<center><tex>h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})</tex></center>
 +
}}
 +
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.
 +
{{Пример
 +
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция
 +
 +
<tex> h(a)  = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами
 +
 +
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.
 +
}}
 
=== Схемы из функциональных элементов ===
 
=== Схемы из функциональных элементов ===
 +
{{main|Реализация булевой функции схемой из функциональных элементов}}
 +
{{Определение
 +
|definition =
 +
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>,  в котором:
 +
 +
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
 +
 +
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.
 +
}}
 +
Отождествление переменных осуществляется при помощи ветвления проводников.
 +
 +
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
 +
 +
'''Некоторые логические элементы:'''
 +
 +
{| class = "wikitable" border = "1"
 +
!-align="center" |И
 +
!-align="center" |ИЛИ
 +
!-align="center" |НЕ
 +
!Штрих Шеффера
 +
!Стрелка Пирса
 +
|-
 +
|[[Image:AND_logic_element.png]]
 +
|[[Image:OR_logic_element.png]]
 +
|[[Image:NOT_logic_element.png]]
 +
|[[Image:NAND_logic_element.png]]
 +
|[[Image:NOR_logic_element.png]]
 +
|}
 +
 +
==Стандартный базис==
 +
 +
{{Определение
 +
|id = def1
 +
|definition = '''Стандартный базис''' — система булевых функций:
 +
<tex>\{\land, \lor, \lnot \} </tex>
 +
}}
 +
 +
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
 +
 +
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex>
 +
 +
<tex> x \rightarrow y = \lnot x \lor y </tex>
 +
 +
<tex> 0 = x \land \lnot x </tex>
 +
 +
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.
 +
 +
<tex> x \mid y = \lnot \left ( x \land y \right )</tex>
 +
 +
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex>
 +
 +
Тождественность функций можно доказать с помощью таблицы истинности.
 +
 +
'''Пример:'''
 +
 +
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.
 +
 +
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex>
 +
 +
==Полнота стандартного базиса==
 +
 +
{{Утверждение
 +
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]
 +
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.
 +
}}
 +
 +
'''Замечание:'''
 +
 +
По [[Множества|закону де Моргана]]:
 +
 +
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
 +
 +
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
 +
 +
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
 +
 +
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
 +
 +
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
 +
 +
==Теоремы о числе функций в базисе==
 +
{{Теорема
 +
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.
 +
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):
 +
 +
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex>, где <tex> T_0, T_1, S, M, L</tex> — классы Поста.
  
{{main|Реализация булевой функции схемой из функциональных элементов}}
+
Значит, так как <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 с.
Строка 399: Строка 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://psi-logic.narod.ru/bool/bool.htm
 
 
* [http://mathcyb.cs.msu.su/books.html Учебные пособия кафедры математической кибернетики ВМиК МГУ]
 
* [http://mathcyb.cs.msu.su/books.html Учебные пособия кафедры математической кибернетики ВМиК МГУ]
 
* [http://ru.wikipedia.org/wiki/Булева_функция Булева функция — Википедия]
 
* [http://ru.wikipedia.org/wiki/Булева_функция Булева функция — Википедия]
 +
* http://psi-logic.narod.ru/bool/bool.htm
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Булевы функции ]]
 
[[Категория: Булевы функции ]]

Текущая версия на 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]

См. также

Примечания

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