3.2. Функции в алгебре логики

Функции и аргументы в алгебре логики определены на множестве {0, 1} и, следовательно, могут принимать только два значения. Как и в обычной алгебре, функции и аргументы обозначаются буквами выбранного алфавита. Все возможные комбинации значений аргументов называются наборами. Число наборов для N аргументов составляет 2N. На каждом наборе аргументов функция может принимать два значения, следовательно, для N аргументов можно получить 2^2N различных функций.

Рассмотрение понятия функции в алгебре логики (АЛ) можно начать с функций одной переменной х (N = 1). Она имеет 2¹ = 2 набора (0 и 1) и соответственно четыре функции y_i (табл. 3.1).

Таблица 3.1 Функции одной переменной в АЛ

Переменная	Функции
x	y1	y2	y3	y4
0	0	0	1	1
1	0	1	0	1

Очевиден и содержательный смысл этих функций: y₁ – константа нуля, y₂ – повторение x, y₃ – инверсия, x и y₄ – константа единицы.

Для двух переменных может быть введено уже 16 функций (табл. 3.2). В табл. 3.3 дано условное обозначение логических элементов, реализующих эти функции.

Таблица 3.2 Функции двух переменных в АЛ

Переменные	x1	1	1	0	0
	x2	1	0	1	0
Функции
f0		0	0	0	0
f1		0	0	0
f2		0	1	0	0
f3		1	1	0	0
f4		0	0	1	0
f5		1	0	1	0
f6		0	1	1	0
f7		1	1	1	0
f8		0	0	0	1
f9		1	0	0	1
f10		0	1	0	1
f11		1	1	0	1
f12		0	0	1	1
f13		1	0	1	1
f14		0	1	1	1
f15		1	1	1	1

Функции двух переменных, рассмотренные в табл. 3.3, играют важную роль в алгебре логики и могут быть названы элементарными (рис 3.1).

К элементарным функциям обычно относят: функцию инверсии (отрицания), конъюнкцию, дизъюнкцию, импликацию, штрих Шеффера и стрелку Пирса.

Таблица 3.3. Содержательная таблица функций двух переменных в АЛ

Функция в аналитическом выражении >	Наименование	Словесное выражение	Выражение в элементарном базисе	Функциональное обозначение
f0=0	Константа “0”	Всегда ложно		см.рис. 3.1, а
f1=x1&x2	Конъюнкция, И	x1 и x2		см.рис. 3.1, б
f2=x1 x2	Запрет x1	Запрет по x2		см.рис. 3.1, в
f3=x1	Повторение x1	Повторение x1		см.рис. 3.1, г
f4=x2 x1	Запрет x2	Запрет по x1		см.рис. 3.1, д
f5=x2	Повторение x2	Повторение x2		см.рис. 3.1, е
f6=x1Åx2	Исключающее ИЛИ	x1 неравнозначно x2		см.рис. 3.1, ж
f7=x1v x2 f7=x1+x2	Дизъюнкция, ИЛИ	x1 или x2		см.рис. 3.1, з
f8=x1↓x2	Стрелка Пирса, ИЛИ-НЕ	Отрицание дизъюнкции		см.рис. 3.1, и
f9=x1~x2	Равнозначность, эквивалентность	x1 равнозначно x2	g border=0 width=89 height=23 src=https://electrono.ru/wp-content/image_post/elektrotex2/pic66_11.gif>	см.рис. 3.1, к
f10=x2	Инверсия, отрицание x2	Не x2		см.рис. 3.1, л
f11=x2x1	Импликация x1	Если x2, то x1		см.рис. 3.1, м
f12=x1	Инверсия, отрицание x1	Не x1		см.рис. 3.1, н
f13=x1x2	Импликация x2	Если x1, то x2		см.рис. 3.1, о
f14=x1 x2	Штрих Шеффера, И-НЕ	Отрицание конъюнкции		см.рис. 3.1, п
f15=1	Константа “1”	Всегда истинно		см.рис. 3.1, р

Рис 3.1 Обозначение логических элементов

Для трёх переменных существует уже 2³ = 8 наборов, дающих 256 логических функций. С целью получения новых функций можно использовать принцип суперпозиции, позволяющий подставлять одни функции вместо аргументов в другие функции. При этом возникает вопрос – какой номенклатурой логических элементов можно ограничиться, чтобы можно было реализовывать любые, сколь угодно сложные функции.

Система булевых функций называется функционально-полной, если произвольная булева функция вида f (x₁, x₂, …, x_n) может быть представлена суперпозицией конечного числа функций системы, а набор элементов реализующих данные функции – функционально полным набором или базисом.

В качестве простейших принято рассматривать следующие пять базисов:

1) дизъюнкция (x_ivx_j), конъюнкция (x_i&x_j), инверсия ();

2) дизъюнкция (x_ivx_j), инверсия ();

3) конъюнкция (x_i&x_j), инверсия ();

4) стрелка Пирса (x_i ↓x_j = );

5) штрих Шеффера (x_i  x_j = ).

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

элементов одного типа (например, Пирс