17
правок
Изменения
Нет описания правки
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''') от ''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''). Булевы функции названы так по фамилии математика Джорджа Буля.
== Основные сведения ==
Каждая булева функция арности ''n'' полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины ''n''. Число таких векторов равно 2<sup>''n''</sup>. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех ''n''-арных булевых функций равно 2<sup>2<sup>''n''</sup></sup>. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название [[Таблица истинности|таблиц истинности]] и в общем случае имеют вид:
<center>
{| class="wikitable" align="center" style="width:10cm"
|+
|-align="center" bgcolor=#EEEEFF
! 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" bgcolor=#F0F0F0
| 0 || 0 || … || 0 || bgcolor=white | f(0,0,…,0)
|-align="center" bgcolor=#F0F0F0
| 1 || 0 || … || 0 || bgcolor=white | f(1,0,…,0)
|-align="center" bgcolor=#F0F0F0
| 0 || 1 || … || 0 || bgcolor=white | f(0,1,…,0)
|-align="center" bgcolor=#F0F0F0
| 1 || 1 || … || 0 || bgcolor=white | f(1,1,…,0)
|-align="center" style="height:1.2cm" bgcolor=#F0F0F0
| <math>\vdots</math> || <math>\vdots</math> || <math>\vdots</math> || <math>\vdots</math> || bgcolor=white | <math>\vdots</math>
|-align="center" bgcolor=#F0F0F0
| 0 || 1 || … || 1 || bgcolor=white | f(0,1,…,1)
|-align="center" bgcolor=#F0F0F0
| 1 || 1 || … || 1 || bgcolor=white | f(1,1,…,1)
|}
</center>
Практически все булевы функции малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной''.
=== Нульарные функции ===
При ''n'' = 0 количество булевых функций сводится к двум 2<sup>2<sup>0</sup></sup> = 2<sup>1</sup> = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.
=== Унарные функции ===
При ''n'' = 1 число булевых функций равно 2<sup>2<sup>1</sup></sup> = 2<sup>2</sup> = 4. Определение этих функций содержится в следующей таблице.
Таблица значений булевых функций от одной переменной:
{| class="standard"
!class="dark" style="font-weight:normal" | ''x''
!style="font-weight:normal" | 0
!style="font-weight:normal" | ''x̅''
!style="font-weight:normal" | ''x''
!style="font-weight:normal" | 1
|- align="center"
!class="shadow" style="font-weight:normal" | 0
|0||1||0||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
|0||0||1||1
|}
Названия булевых функций от одной переменной:
{| class="standard"
!Обозначение
!Название
|-
|0
|тождественный ноль, тождественная ложь, тождественное "НЕТ"
|-
|''x̅'', ¬''x'', ''x'''
|отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
|-
|''x''
|тождественная функция, логическое "ДА", "YES"(англ.)
|-
|1
|тождественная единица, тождественная истина, тождественное "ДА", тавтология
|}
=== Бинарные функции ===
При ''n'' = 2 число булевых функций равно 2<sup>2²</sup> = 2<sup>4</sup> = 16.
Таблица значений булевых функций от двух переменных:
{| class="standard" width="100%"
!class="dark" style="font-weight:normal" width="1%"| ''x''
!class="dark" style="font-weight:normal" width="1%"| ''y''
!style="font-weight:normal" width="4%"| 0
!style="font-weight:normal" width="4%"| ''x''↓''y''
!style="font-weight:normal" width="4%"| {{overline|''x''←''y''}}
!style="font-weight:normal" width="4%"| ''x̅''
!style="font-weight:normal" width="4%"| {{overline|''x''→''y''}}
!style="font-weight:normal" width="4%"| ''y̅''
!style="font-weight:normal" width="4%"| ''x''⊕''y''
!style="font-weight:normal" width="4%"| ''x''<nowiki>|</nowiki>''y''
!style="font-weight:normal" width="4%"| ''x'' & ''y''
!style="font-weight:normal" width="4%"| ''x'' ≡ ''y''
!style="font-weight:normal" width="4%"| ''y''
!style="font-weight:normal" width="4%"| ''x''→''y''
!style="font-weight:normal" width="4%"| ''x''
!style="font-weight:normal" width="4%"| ''x''←''y''
!style="font-weight:normal" width="4%"| ''x'' ∨ ''y''
!style="font-weight:normal" width="4%"| 1
|- align="center"
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 0
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
|- align="center"
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 1
|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 0
|0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 1
|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1
|}
Названия булевых функций от двух переменных:
{| class="standard"
!Обозначение
!Название
|-
|0
|тождественный ноль, тождественная ложь, тождественное "НЕТ"
|-
|''x'' ↓ ''y'', ''x'' ИЛИ-НЕ ''y'', ИЛИ-НЕ(''x'',''y''), ''x'' NOR ''y'', NOR(''x'',''y'')
|НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
|-
|''x'' < ''y'', {{overline|''x'' ← ''y''}}, ''x'' LT ''y'', LT(''x'',''y'')
|меньше, инверсия обратной импликации]
|-
|''x̅'', НЕ1(''x'',''y''), NOT1(''x'',''y''), ''x''', ¬''x''
|отрицание (негация, инверсия) первого операнда
|-
|''x'' > ''y'', {{overline|''x'' → ''y''}}, ''x'' GT ''y'', GT(''x'',''y'')
|больше, инверсия прямой импликации
|-
|''y̅'', НЕ2(''x'',''y''), NOT2(''x'',''y''), ''y''', ¬''y''
|отрицание (негация, инверсия) второго операнда
|-
|''x'' ⊕ ''y'', ''x'' +<sub>2</sub> ''y'', ''x'' ≠ ''y'', ''x'' >< ''y'', ''x'' <> ''y'', ''x'' XOR ''y'', XOR(''x'',''y'')
|сложение по модулю 2, не равно, , исключающее «или»
|-
|''x'' <nowiki>|</nowiki> ''y'', ''x'' NAND ''y'', NAND(''x'',''y''), ''x'' И-НЕ ''y'', И-НЕ(''x'',''y'')
|НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера
|-
|''x'' & ''y'', ''x'' · ''y'', ''x''<span></span>''y'', ''x'' ∧ ''y'', ''x'' AND ''y'', AND(''x'',''y''), ''x'' И ''y'', И(''x'',''y''), min(''x'',''y'')
|2И, конъюнкция
|-
|''x'' ≡ ''y'', ''x'' = ''y'', ''x'' EQV ''y'', EQV(''x'',''y''), ''x'' ~ ''y'', ''x'' ↔ ''y''
|равенство, эквивалентность
|-
|''y'', ДА2(''x'',''y''), YES2(''x'',''y'')
|второй операнд
|-
|''x'' → ''y'', ''x'' ≤ ''y'', ''x'' ⊃ ''y'', ''x'' LE ''y'', LE(''x'',''y'')
|меньше или равно, прямая (материальная) [[импликация]] (от первого аргумента ко второму)
|-
|''x'', ДА1(''x'',''y''), YES1(''x'',''y'')
|первый операнд
|-
|''x'' ← ''y'', ''x'' ≥ ''y'', ''x'' ⊂ ''y'', ''x'' GE ''y'', GE(''x'',''y'')
|больше или равно, обратная импликация (от второго аргумента к первому)
|-
|''x'' ∨ ''y'', ''x'' + ''y'', ''x'' ИЛИ ''y'', ИЛИ(''x'',''y''), ''x'' OR ''y'', OR(''x'',''y''), max(''x'',''y'')
|2ИЛИ, дизъюнкция
|-
|1
|тождественная единица, тождественная истина, тождественное "ДА", тавтология
|}
=== Тернарные функции ===
При ''n'' = 3 число булевых функций равно 2<sup>2³</sup> = 2<sup>8</sup> = 256. Некоторые из них определены в следующей таблице:
{| class="standard"
|-
!class="dark" style="font-weight:normal" | ''x''
!class="dark" style="font-weight:normal" | ''y''
!class="dark" style="font-weight:normal" | ''z''
!style="font-weight:normal" | ''x''↓''y''↓''z''
!style="font-weight:normal" | {{overline|≥2(x,y,z)}}
!style="font-weight:normal" | x≠y≠z
!style="font-weight:normal" | x<nowiki>|</nowiki>y<nowiki>|</nowiki>z
!style="font-weight:normal" | min(x,y,z)
!style="font-weight:normal" | x=y=z
!style="font-weight:normal" | ''x''⊕''y''⊕''z''
!style="font-weight:normal" | ≥2(x,y,z)
!style="font-weight:normal" | ''f<sub>1</sub>''
!style="font-weight:normal" | ''f<sub>2</sub>''
!style="font-weight:normal" | max(x,y,z)
|- align="center"
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 0
|1||1||0||1 ||0||1||0||0||0||0 ||0
|- align="center"
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 1
|0||1||1||1 ||0||0||1||0||0||0 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 0
|0||1||1||1 ||0||0||1||0||0||0 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 1
|0||0||1||1 ||0||0||0||1||1||1 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 0
|0||1||1||1 ||0||0||1||0||1||0 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 0
!class="shadow" style="font-weight:normal" | 1
|0||0||1||1 ||0||0||0||1||0||1 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 0
|0||0||1||1 ||0||0||0||1||1||1 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 1
!class="shadow" style="font-weight:normal" | 1
|0||0||0||0 ||1||1||1||1||1||1 ||1
|}
Названия булевых функций трех переменных:
{| class="standard"
|-
!Обозначения
!Названия
|-
|x<math>\downarrow</math>y<math>\downarrow</math>z = <math>\downarrow</math>(x,y,z) = Webb<sub>2</sub>(x,y,z)
|3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
|-
|<math>\neg(> = 2(x,y,z))</math>
|Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
|-
|x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v)
|Неравенство
|-
|x<math>\mid</math>y<math>\mid</math>z = <math>\mid</math>(x,y,z)
|3-И-НЕ, штрих Шеффера
|-
|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)
|3-И, минимум
|-
|(x=y=z) = [=(x,y,z)] = EQV(x,y,z,v)
|Равенство
|-
|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)
|Тернарное сложение по модулю 2
|-
|[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x)
|переключатель по большинству, 3-ППБ, мажоритарный клапан
|-
|''f<sub>1</sub>''
|Разряд займа при тернарном вычитании
|-
|''f<sub>2</sub>''
|Разряд переноса при тернарном сложении
|-
|(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)
|3-ИЛИ, максимум
|}
