Функция f от n переменных такая что f x y z y

Дискретная математика, кроссворд

Функция f от n переменных, такая, что f(x, …, y, … z) = y- (13 букв)
Функция f (x, y, z) представлена строкой своих значений: (1,1,0,0,0,0,1,1). Переменная z -(9 букв)
Способ задания булевой функции от n переменных — (7 букв)
На булевом кубе можно определить отношение порядка следующим образом: для двух наборов a = (x,…,y,…,z) и b = (p,…,q,…,r) первый не превосходит второго тогда и только тогда, когда x (5 букв)

Голосование за лучший ответ

1. проектирующая
2. фиктивная
3. таблица
4. булев

Светлана КассемУченик (129) 8 месяцев назад

Определение булевой функции

Элементы булева множества [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]^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]^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.

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

При [math]n = 1[/math] число булевых функций равно [math]^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^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,[/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,[/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]^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=1[/math]	[math]\overline=0[/math]	[math]\overline<\overline>=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=0[/math]

[math]x \lor \overline=1[/math]

[math]\overline=\overline\lor\overline[/math]

[math]\overline\land\overline=\overline[/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,\overline,\dots,\overline)=\overline[/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 = \[/math] . Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре [math]\Sigma[/math] , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

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

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

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

  Основная статья: ДНФ

  Определение:

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

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

  Примеры ДНФ:

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

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

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

  Основная статья: КНФ

  Определение:

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

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

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

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

  [math]f(x,y,z,t,m) = (x \lor m \lor \neg) \land (y \lor \neg) \land (y \lor t \lor \neg)[/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_ 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]

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

  Определение:

  Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_, \ldots, x_) = f(x_, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math]

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

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

  1. [math] x_, \ldots, x_[/math]	— аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math]
  2. [math] x_, \ldots, x_ [/math]	— используются как аргументы для вычисления значения функции [math]g(y_, \ldots, y_)[/math]
  3. [math] x_, \ldots, x_ [/math]	— аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math]

  1. [math] f(a,b) = a \vee b [/math]
  2. [math] g(a) = \neg a [/math]

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

  Определение:

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

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

  Основная статья: Реализация булевой функции схемой из функциональных элементов

  Определение:

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

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

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

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

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

  И	ИЛИ	НЕ	Штрих Шеффера	Стрелка Пирса

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

  Определение:

  Стандартный базис — система булевых функций: [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] 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] 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]\[/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]k, 1 \le k \le 4 [/math] найдётся базис [math] X[/math] , что [math]\left | X \right | = k[/math] .

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

  [math]k = 1 \Rightarrow X = \< \downarrow \>[/math] ;

  [math]k = 2 \Rightarrow X = \< \lnot, \land \>[/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]

  См. также

  • Специальные формы КНФ
  • Сокращенная и минимальная ДНФ
  • Пороговая функция
  • Cумматор
  • Полные системы функций. Теорема Поста о полной системе функций

  Примечания

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

  • Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
  • Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
  • Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
  • Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
  • Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
  • Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
  • Учебные пособия кафедры математической кибернетики ВМиК МГУ
  • Булева функция — Википедия
  • http://psi-logic.narod.ru/bool/bool.htm
  • Дискретная математика и алгоритмы
  • Булевы функции