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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Суперпозиции)
(Полнота системы, критерий Поста)
Строка 411: Строка 411:
  
 
{{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>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
  
 
== Представление булевых функций ==
 
== Представление булевых функций ==

Версия 18:11, 28 декабря 2017

Определение:
Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики, англ. 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]F[/math]. Получить новую функцию, являющеюся композицией функций из [math]F[/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..1} 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]

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

Определение:
Схема из функциональных элементов, логическая схема (англ. 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

См. также

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

  • Эмиль Пост
  • Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Определение_булевой_функции&oldid=63194»