Булевы функции

В теории дискретных функциональных систем булевой функцией называют функцию типа $\mathsf{B}^{na}\to\mathsf{B}$, где $\mathsf{B}=\{0,1\}$ — булево множество, а $\ na$ — неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы $\mathsf{B}^{na}$ называют булевыми векторами. В случае $\ na=0$ булева функция превращается в булеву константу.

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

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

x1	x2	…	xn	f(x1,x2,…,xn)
0	0	…	0	f(0,0,…,0)
1	0	…	0	f(1,0,…,0)
0	1	…	0	f(0,1,…,0)
1	1	…	0	f(1,1,…,0)
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
0	1	…	1	f(0,1,…,1)
1	1	…	1	f(1,1,…,1)

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

Нульарные функции с унарным результатом (выходом)

Генераторы постоянных (констант) и переменных. При $\ na=0$ и $\ ma=1$ количество булевых функций сводится к двум $2^{(2^0)*1}=2^1=2$, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тоджественный нуль и тоджественная единица.

		Названия функций (операций)		Обозначения
		Рус.	Англ.
f(0,1,0)2	0	тождественный ноль, тождественная ЛОЖЬ,	FALSE	f(0,1,0)10 = $\ 0$
f(0,1,1)2	1	тождественная единица, тождественная ИСТИНА,	TRUE	f(0,1,1)10 = $\ 1$

В генераторах переменных появляется дополнительный параметр - номер выходного сигнала в последовательности выходных сигналов.
Простейшими генераторами переменных являются генераторы прямоугольных импульсов (меандра), т.е. последовательности 0 и 1.

Унарные функции с унарным результатом (выходом)

При $\ na=1$ и $\ ma=1$число булевых функций равно $2^{(2^1)*1} = 4$.
Число простейших унарных двоичных функций с унарным выходом равно числу размещений с повторениями (выборок с возвращением) при kr = nr = 2:

$\bar{A}(nr,kr)= \bar{A}_{nr}^{kr} ={nr}^{kr}=2^2=4$

Им соответствуют следующие таблицы истинности.

x	1	0	название	обозначение
f(1,1,00)2(x)	0	0	тождественный ноль, тождественная ложь, тождественное "НЕТ"	f(1,1,0)10(x) = 0
f(1,1,01)2(x)	0	1	отрицание, инвертор, линия задержки с инверсией, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.), "NICHT"(нем.), "NON"(фр.), "NO"(ит.)	f(1,1,1)10(x) = x'= ¬x = $x'$ = $\lnot x$ = $\neg x$ = $\overline{x}$
f(1,1,10)2(x)	1	0	тождественная функция, повторитель, линия задержки, логическое "ДА", "YES"(англ.), "JA"(нем.), "OUI"(фр.), "SI"(ит.)	f(1,1,2)10(x) = ДА(x) = YES(x) = x
f(1,1,11)2(x)	1	1	тождественная единица, тождественная истина, тождественное "ДА", тавтология	f(1,1,3)10(x) = 1

Двоичный номер функции равен результату действия функции.

Унарные функции с бинарным результатом (выходом)

x	1	0	название	обозначение
f(1,1,01)2(x)	0	1	не	f(1,1,1)10(x) = НЕ(x) = NOT(x)
f(1,1,10)2(x)	1	0	да	f(1,1,2)10(x) = ДА(x) = YES(x)

• f(1,10,1001)₂(x)= f(1,2,9)₁₀(x) — одноразрядный полный двоичный дешифратор (обозначения: дш, decoder, dec). Можно рассматривать как объединение двух унарных функций с унарным выходом: f(1,1,1)₁₀(x) и f(1,1,2)₁₀(x).
  

В номере функции:
первое число - число входов,
второе число - число выходов,
третье число - номер функции (операции), он же результат действия функции (операции),
четвёртое число - основание системы счисления.

Бинарные функции с унарным результатом (выходом)

При $\ n=2$ число булевых функций равно $2^{(2^2)} = 16$. Им соответствуют следующие таблицы истинности. Другое название этих функций - двоичные бинарные (двухоперандные, двухразрядные) шифраторы (кодеры, coder, encoder) с унарным (одноразрядным) выходом.
У каждой функции есть свой порядковый номер. Двоичный номер функции равен результату действия функции из таблицы истиности, при этом порядковый номер двоичного разряда в номере функции равен значению операндов (первый операнд - младший значащий разряд, второй операнд - старший значащий разряд).

x	1	0	1	0
y	1	1	0	0	названия	обозначения
f(10,1,0000)2(x,y)	0	0	0	0	тождественный ноль, тождественная ложь, тождественное "НЕТ"	f(2,1,00)10(x,y) = 0(x,y) = 0
f(10,1,0001)2(x,y)	0	0	0	1	НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса	f(2,1,01)10(x,y) = $(x\downarrow y$) = (x ИЛИ-НЕ y) = ИЛИ-НЕ(x,y) = (x NOR y) = NOR(x,y)
f(10,1,0010)2(x,y)	0	0	1	0	больше, инверсия прямой импликации	f(2,1,02)10(x,y) = $\ (x>y)$ = $\lnot$(x$\rightarrow$y) = (x GT y) = GT(x,y)
f(10,1,0011)2(x,y)	0	0	1	1	отрицание (негация, инверсия) второго операнда	f(2,1,03)10(x,y) = НЕ2(x,y) = NOT2(x,y) = y' = $\neg y$ = $\bar{y}$
f(10,1,0100)2(x,y)	0	1	0	0	меньше, инверсия обратной импликации	f(2,1,04)10(x,y) = $\ (x<y)$ = $\lnot$(x$\leftarrow$y) = (x LT y) = LT(x,y)
f(10,1,0101)2(x,y)	0	1	0	1	отрицание (негация, инверсия) первого операнда	f(2,1,05)10(x,y) = НЕ1(x,y) = NOT1(x,y) = x' = $\neg x$ = $\bar{x}$,
f(10,1,0110)2(x,y)	0	1	1	0	сложение по модулю 2, не равно, измена, исключающее «или»	f(2,1,06)10(x,y) = $(x \oplus y)$ = $(x+_2y)$ = $(x\ne y)$ = (x><y) = (x<>y) = (x XOR y) = XOR(x,y)
f(10,1,0111)2(x,y)	0	1	1	1	НЕ-2И, 2И-НЕ, антиконъюнкция, штрих Ше́ффера	f(2,1,07)10(x,y) = $(x \mid y)$ = (x NAND y) = NAND(x,y) = (x И-НЕ y) = И-НЕ(x,y)
f(10,1,1000)2(x,y)	1	0	0	0	2И, конъюнкция	f(2,1,08)10(x,y) = (x&y) = $(x\cdot y)$ = $\ (xy)$ = $(x\land y)$ = (x AND y) = AND(x,y) = (x И y) = И(x,y) = min(x,y)
f(10,1,1001)2(x,y)	1	0	0	1	равенство, эквивалентность	f(2,1,09)10(x,y) = (x=y) = (x EQV y) = EQV(x,y) = $(x\sim y)$ = $(x\equiv y)$ = $(x\leftrightarrow y)$
f(10,1,1010)2(x,y)	1	0	1	0	первый операнд	f(2,1,10)10(x,y) = ДА1(x,y) = YES1(x,y) = x
f(10,1,1011)2(x,y)	1	0	1	1	больше или равно, обратная импликация (от второго аргумента к первому)	f(2,1,11)10(x,y) = $\ (x>=y)$ = $(x\ge y)$ = $(x\leftarrow y)$ = $(x \subset y)$ = (x GE y) = GE(x,y)
f(10,1,1100)2(x,y)	1	1	0	0	второй операнд	f(2,1,12)10(x,y) = ДА2(x,y) = YES2(x,y) = y
f(10,1,1101)2(x,y)	1	1	0	1	меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)	f(2,1,13)10(x,y) = $\ (x<=y)$ = $(x\le y)$ = $(x\rightarrow y)$ = $(x\supset y)$ = (x LE y) = LE(x,y)
f(10,1,1110)2(x,y)	1	1	1	0	2ИЛИ, дизъюнкция	f(2,1,14)10(x,y) = $(x\lor y)$ = $\ (x+y)$ = (x ИЛИ y) = ИЛИ(x,y) = (x OR y) = OR(x,y) = max(x,y)
f(10,1,1111)2(x,y)	1	1	1	1	тождественная единица, тождественная истина, тождественное "ДА", тавтология	f(2,1,15)10(x,y) = 1(x,y) = 1

Бинарные функции с бинарным результатом

Двоичный полусумматор

X	Y		P=X&Y	S=X $\oplus$ Y
0	0		0	0
1	0		0	1
0	1		0	1
1	1		1	0

S - бит суммы по модулю 2
P - бит переноса в n+1 разряд
f(10,10,10000110)₂(x,y)=f(2,2,134)₁₀(x,y)

Двоичный полувычитатель

X	Y		R=X $\oplus$ Y =f(2,1,06)10(x,y)	Z(N+1) =f(2,1,04)10(x,y)
0	0		0	0
1	0		1	0
0	1		1	1
1	1		0	0

R - бит разности по модулю 2
Z - бит займа из n+1 разряда
f(10,10,01000110)₂(x,y)=f(2,2,70)₁₀(x,y)

Тернарные (тринарные) функции с унарным результатом (выходом)

При $\ n=3$ число булевых функций равно $2^{(2^3)} = 2^8 = 256$. Им соответствует 256 двоичных трёхвходовых (тернарных, тринарных, трёхоперандных) логических элемента. Из них наибольшую значимость имеют: f(11,1,10010110)₂(x,y,z)=f(3,1,150)₁₀(x,y,z) - трёхоперандное (тринарное) логическое сложение по модулю 2 и f(11,1,11101000)₂(x,y,z)=f(3,1,232)₁₀(x,y,z) - разряд переноса при трёхоперандном (тринарном) сложении по модулю 2.

x	1	0	1	0	1	0	1	0
y	1	1	0	0	1	1	0	0
z	1	1	1	1	0	0	0	0	названия	обозначения
f(11,1,00000000)2(x,y,z)	0	0	0	0	0	0	0	0	тождественный ноль, тождественная ложь, тождественное "НЕТ"	f(3,1,0)10(x,y,z) = 0(x,y,z) = 0
f(11,1,00000001)2(x,y,z)	0	0	0	0	0	0	0	1	3ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса	f(3,1,1)10(x,y,z) = x$\downarrow$y$\downarrow$z = $\downarrow$(x,y,z) = Webb2(x,y,z)
f(11,1,00001111)2(x,y,z)	0	0	0	0	1	1	1	1	Инверсия третьего операнда	f(3,1,15)10(x,y,z) = НЕ3(x,y,z) = z' = $\neg{z} = \bar{z}$
f(11,1,00101111)2(x,y,z)	0	0	1	0	1	1	1	1	Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией	f(3,1,47)10(x,y,z) = $\neg(> = 2(x,y,z))$
f(11,1,00110011)2(x,y,z)	0	0	1	1	0	0	1	1	Инверсия второго операнда	f(3,1,51)10(x,y,z) = НЕ2(x,y,z) = y' = $\neg{y} = \bar{y}$
f(11,1,01010101)2(x,y,z)	0	1	0	1	0	1	0	1	Инверсия первого операнда	f(3,1,85)10(x,y,z) = НЕ1(x,y,z) = x' = $\neg{x} = \bar{x}$
f(11,1,01111110)2(x,y,z)	0	1	1	1	1	1	1	0	Неравенство	f(3,1,126)10(x,y,z) = x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v)
f(11,1,01111111)2(x,y,z)	0	1	1	1	1	1	1	1	3И-НЕ, штрих Шеффера	f(3,1,127)10(x,y,z) = x$\mid$y$\mid$z = $\mid$(x,y,z)
f(11,1,10000000)2(x,y,z)	1	0	0	0	0	0	0	0	3И, минимум	f(3,1,128)10(x,y,z) = 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)
f(11,1,10000001)2(x,y,z)	1	0	0	0	0	0	0	1	Равенство	f(3,1,129)10(x,y,z) = (x=y=z) = [=(x,y,z)] = EQV(x,y,z,v)
f(11,1,10010110)2(x,y,z)	1	0	0	1	0	1	1	0	Тринарное сложение по модулю 2	f(3,1,150)10(x,y,z) = x⊕2y⊕2z = x+2y+2z = ⊕2(x,y,z) = +2(x,y,z)
f(11,1,10101010)2(x,y,z)	1	0	1	0	1	0	1	0	Повторение первого операнда	f(3,1,170)10(x,y,z) = ДА1(x,y,z) = x
f(11,1,11001100)2(x,y,z)	1	1	0	0	1	1	0	0	Повторение второго операнда	f(3,1,204)10(x,y,z) = ДА2(x,y,z) = y
f(11,1,11010000)2(x,y,z)	1	1	0	1	0	0	0	0	переключатель по большинству, 3ППБ, мажоритарный клапан	f(3,1,208)10(x,y,z) = [>=2(x,y,z)]
f(11,1,11011000)2(x,y,z)	1	1	0	1	1	0	0	0	Разряд займа при тринарном вычитании	f(3,1,216)10(x,y,z)
f(11,1,11101000)2(x,y,z)	1	1	1	0	1	0	0	0	Разряд переноса при тринарном сложении	f(3,1,232)10(x,y,z)
f(11,1,11110000)2(x,y,z)	1	1	1	1	0	0	0	0	Повторение третьего операнда	f(3,1,240)10(x,y,z) = ДА3(x,y,z) = z
f(11,1,11111110)2(x,y,z)	1	1	1	1	1	1	1	0	3ИЛИ, максимум	f(3,1,254)10(x,y,z) = (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)
f(11,1,11111111)2(x,y,z)	1	1	1	1	1	1	1	1	тождественная единица, тождественная истина, тождественное "ДА", тавтология	f(3,1,255)10(x,y,z) = 1(x,y,z) = 1

В номере функции:
первое число - число входов,
второе число - число выходов,
третье число - номер функции (операции), он же результат действия функции (операции),
четвёртое число - основание системы счисления.
Двоичный номер функции равен результату действия функции из таблицы истиности. Порядковый номер разряда в номере функции определяется значениями аргументов, первый аргумент - нулевой разряд, второй аргумент - первый разряд, третий аргумент - второй разряд номера результата действия функции в номере функции.

Тринарное сложение по модулю 2

X	Y	Z		X $\oplus$ Y $\oplus$ Z
0	0	0		0
1	0	0		1
0	1	0		1
1	1	0		0
0	0	1		1
1	0	1		0
0	1	1		0
1	1	1		1

f(11,1,10010110)₂(x,y,z)=f(3,1,150)₁₀(x,y,z)

Разряд переноса при тринарном сложении по модулю 2

X	Y	Z		P(N+1)
0	0	0		0
1	0	0		0
0	1	0		0
1	1	0		1
0	0	1		0
1	0	1		1
0	1	1		1
1	1	1		1

f(11,1,11101000)₂(x,y,z)=f(3,1,232)₁₀(x,y,z)

Тетрарные (четырёхоперандные) функции с унарным результатом (выходом)

При $\ n = 4$ число булевых функций равно $2^{(2^4)} = 2^{16} = 65536$. Им соответствует 65536 двоичных четырёхвходовых (тетрарных, четырёхоперандных) логических элемента.

x	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0
y	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0
z	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0
u	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	названия	обозначения
f(100,1,0000000000000000)2(x,y,z,u)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	тождественный ноль, тождественная ложь, тождественное "НЕТ"	f(4,1,0)10(x,y,z,u) = 0(x,y,z,u) = 0
f(100,1,0000000000000001)2(x,y,z,u)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	4ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса	f(4,1,1)10(x,y,z,u) = x$\downarrow$y$\downarrow$z$\downarrow$u = $\downarrow$(x,y,z,u) = Webb2(x,y,z,u)
f(100,1,0000000011111111)2(x,y,z,u)	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	Инверсия четвёртого операнда	f(4,1,255)10(x,y,z,u) = не4(x,y,z,u) = u' = $\neg{u}= \bar{u}$
f(100,1,0000111100001111)2(x,y,z,u)	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	Инверсия третьего операнда	f(4,1,3855)10(x,y,z,u) = не3(x,y,z,u) = z' = $\neg{z} = \bar{z}$
f(100,1,0011001100110011)2(x,y,z,u)	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	Инверсия второго операнда	f(4,1,13107)10(x,y,z,u) = не2(x,y,z,u) = y' = $\neg{y} = \bar{y}$
f(100,1,0101010101010101)2(x,y,z,u)	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	Инверсия первого операнда	f(4,1,21845)10(x,y,z,u) = не1(x,y,z,u) = x' = $\neg{x} = \bar{x}$
f(100,1,0111111111111110)2(x,y,z,u)	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	Неравенство	f(4,1,32766)10(x,y,z,u) = (x≠y≠z≠u) = [≠(x,y,z,u)]
f(100,1,0111111111111111)2(x,y,z,u)	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	4И-НЕ, штрих Шеффера	f(4,1,32767)10(x,y,z,u) = x$\mid$y$\mid$z$\mid$u = $\mid$(x,y,z,u)
f(100,1,1000000000000000)2(x,y,z,u)	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	4И, минимум	f(4,1,32768)10(x,y,z,u) = x&y&z&u = &(x,y,z,u) = min(x,y,z,u)
f(100,1,1000000000000001)2(x,y,z,u)	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	Равенство	f(4,1,32769)10(x,y,z,u) = (x=y=z=u) = [=(x,y,z,u)]
f(100,1,0110100110010110)2(x,y,z,u)	0	1	1	0	1	0	0	1	1	0	0	1	0	1	1	0	Тетрарное сложение по модулю 2	f(4,1,27030)10(x,y,z,u) = x⊕2y⊕2z⊕2v = x+2y+2z+2u = ⊕2(x,y,z,u) = +2(x,y,z,u)
f(100,1,1010101010101010)2(x,y,z,u)	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	Повторение первого операнда	f(4,1,43690)10(x,y,z,u) = да1(x,y,z,u) = x
f(100,1,1100110011001100)2(x,y,z,u)	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	Повторение второго операнда	f(4,1,52428)10(x,y,z,u) = да2(x,y,z,u) = y
f(100,1,1111000011110000)2(x,y,z,u)	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	Повторение третьего операнда	f(4,1,61680)10(x,y,z,u) = да3(x,y,z,u) = z
f(100,1,1111111100000000)2(x,y,z,u)	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	Повторение четвёртого операнда	f(4,1,65280)10(x,y,z,u) = да4(x,y,z,u) = u
f(100,1,1111111111111110)2(x,y,z,u)	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	4ИЛИ, максимум	f(4,1,65534)10(x,y,z,u) = x+y+z+u = +(x,y,z,u) = max(x,y,z,u)
f(100,1,1111111111111111)2(x,y,z,u)	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	тождественная единица, тождественная истина, тождественное "ДА", тавтология	f(4,1,65535)10(x,y,z,u) = 1(x,y,z,u) = 1

Тринарные (тернарные) функции с бинарным (двухразрядным) результатом (выходом)

Всего возможны $2^{(2^3)*2}=65 536$ тринарных логических функций с бинарным результатом. Из них наибольшую значимость имеет логическая функция полного тринарного (трёхоперандного, трёхчислового) двоичного сложения.

Полное двоичное сложение

При полном двоичном сложении учитывается значение разряда переноса из предыдущего разряда многоразрядного сумматора, а результат, кроме суммы по модулю 2, имеет разряд переноса в следующий разряд многоразрядного сумматора.
Функция полного двоичного сложения - f(3,2,59542)₁₀ является объединением двух более простых тринарных функций с унарными результатами: f(3,1,150)₁₀ - трёхоперандное (тринарное, трёхчисловое) сложение по модулю 2 и f(3,1,232)₁₀ - разряд переноса при полном трёхоперандном (тринарном, трёхчисловом) сложении.

X	Y	P(N-1)		S=X $\oplus$ Y $\oplus$ P(N-1)= f(3,1,150)10(X,Y,P(N-1))	P(N+1)= f(3,1,216)10(X,Y,P(N-1))
0	0	0		0	0
1	0	0		1	0
0	1	0		1	0
1	1	0		0	1
0	0	1		1	0
1	0	1		0	1
0	1	1		0	1
1	1	1		1	1

f(11,10,1110100010010110)₂=f(3,2,59542)₁₀
Функции полного двоичного сложения соответствует электронное логическое устройство f(3,2,59542)₁₀ - одноразрядный полный двоичный сумматор.

Полное двоичное вычитание

f(11,10,110100010010110)₂(X,Y,Z(N-1))=f(3,2,55446)₁₀(X,Y,Z(N-1))

X	Y	Z(N-1)	R=X $\oplus$ Y $\oplus$Z(N-1)= f(3,1,150)10(X,Y,Z(N-1))	Z(N+1)= f(3,1,216)10(X,Y,Z(N-1))
0	0	0	0	0
1	0	0	1	0
0	1	0	1	0
1	1	0	0	1
0	0	1	1	1
1	0	1	0	0
0	1	1	0	1
1	1	1	1	1

Z(N-1) - бит займа в N-1 разряд, второе вычитаемое
Z(N+1) - бит займа из N+1 разряда

N-арные функции с унарным результатом (выходом)

К этим функциям относятся двоичные шифраторы c n входами и одним выходом.

N-арные функции с m-арным выходом

К этим функциям относятся шифраторы, мультиплексоры, дешифраторы и демультиплексоры.

Полный демультиплексор имеет $\ n + 1$ входов (n-адресных и 1 сигнальный) и $\ m=2^n$ выходов. В неполном демультиплексоре число выходов меньше $\ m=2^n$.

Полный дешифратор имеет $\ n$ входов (сигнального входа нет) и $\ m=2^n$ выходов. В неполном дешифраторе число выходов меньше $\ m=2^n$.

Так как и число входов и число выходов демультиплексоров и дешифраторов может быть любым, то число возможных демультиплексоров и дешифраторов равно бесконечности.

Логические n-арные пустые функции ("чёрные дыры")

Логические n-арные элементы (функции) с n входами без выходов (число выходов равно нулю).

Простейшие двоичные логические функции с обратными связями

Генераторы

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

Полные системы булевых функций

Суперпозиция и замкнутые классы функций

Результат вычисления булевой функции может быть использован в качестве одного из агрументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции $f{(3,1,79)_{10}}(x,y,z)=\overline{x(\overline{y}\lor z)}$ (суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:

$x$	$y$	$z$		$f{(3,1,79)_{10}}(x,y,z)$
0	0	0		1
1	0	0		1
0	1	0		1
1	1	0		1
0	0	1		0
1	0	1		0
0	1	1		1
1	1	1		0

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

В качестве простейших примеров замкнутых классов булевых функций можно назвать множество $\{x\}$, состоящее из одной тождественной функции, или множество $\{0\}$, все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций $\{x,\overline{x}\}$ и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы $\{0\}$ и $\{x,\overline{x}\}$, мы с помощью суперпозиции $\overline{0}$ сможем получить константу 1, которая в исходных классах отсутствовала.

Разумеется, множество $P_2$ всех возможных булевых функций тоже является замкнутым.

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

Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
$f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)$

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

$\overline{0}=1$	$\overline{1}=0$	$\overline{\overline{x}}=x$	$xy=yx\!$	$x \lor y = y \lor x$
$0x=0\!$	$1x=x\!$	$0\lor x=x$	$1\lor x=1$	$xx=x\lor x=x$

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

$x\overline{x}=0$

$x\lor\overline{x}=1$

$\overline{x\cdot y}=\overline{x}\lor\overline{y}$

$\overline{x}\cdot\overline{y}=\overline{x\lor y}$

(законы де Моргана)

$x(y\lor z)=xy\lor xz$
$x\lor yz=(x\lor y)(x\lor z)$ (дистрибутивность конъюнкции и дизъюнкции)

Функция $g(x_1,x_2,\dots,x_n)$ называется двойственной функции $f(x_1,x_2,\dots,x_n)$, если $f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}$. Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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

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

Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством $P_2$.

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

• Функции, сохраняющие константу $T_0$ и $T_1$;
• Самодвойственные функции $S$;
• Монотонные функции $M$;
• Линейные функции $L$.

Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с $P_2$, целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.

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

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

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

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

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

Простой конъюнкцией, или конъюнктом, называется конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция

• правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);
• полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
• монотонная, если она не содержит отрицаний переменных.

Например $a \overline{b} c\lor b c\lor\overline{a}$  — является ДНФ.

Совершенной дизъюнктивной нормальной формой, или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: $a \overline{b} c\lor a b c\lor\overline{a} b\overline{c}$.

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, и даже СДНФ. Для этого достаточно взять таблицу истинности этой функции и найти все булевы векторы, на которых её значение равно 1. Для каждого такого вектора $b=(b_1,b_2,\ldots,b_n)$ строится конъюнкция $x_1^{b_1} x_2^{b_2}\ldots x_n^{b_n}$, где $x_i^1 = x_i$ $x_i^0 = \overline{x_i}$. Если взять дизъюнкцию этих конъюнкций, то результатом очевидно будет СДНФ. Поскольку на всех булевых векторах её значения совпадают со значениями исходной функции, она будет СДНФ этой функции. Например, для импликации $x\to y$, результатом будет $\overline{x} y \lor \overline{x}\, \overline{y}\lor x y$, что можно упростить до $\overline{x}\lor y$.

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

Конъюнктивная нормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ, путём раскрытия скобок по правилу:

$a (b\lor c)\to a b\lor a c$

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого, необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом, результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также, можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

$a\lor b c\to (a \lor b)(a \lor c)$

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать способом, описанным выше, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

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

Полином Жегалкина это форма представления логической функции с помощью Функции Жегалкина (Исключающее ИЛИ). Для получения полинома Жегалкина следует выполнить следуюющие действия:

1. Получить ДНФ функции
2. Все ИЛИ заменить на Исключающее ИЛИ
3. Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1)
4. Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы

Двоичные логические функции с обратными связями

Изучением логических функций с обратными связями и устройств выполняющих эти функции занимается кибернетика.
Функции с обратными связями выполняют такие известные устройства, как генераторы, триггеры, счётчики, регистры, АЛУ, процессоры, память, ЭВМ (компьютеры).

См. также

• Алгебра логики
• Булева алгебра
• Исчисление высказываний
• Битовые операции
• Двоичная логика
• Комбинационная логика
• Секвенциальная логика
• Троичная логика

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит. — 2000
• Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука. — 1969
• Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов

Ссылки

• Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
• http://olddesign.isu.ru/~slava/do/disc/fr_bools.htm
• Учебные пособия кафедры математической кибернетики ВМиК МГУ

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Булевы функции. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---