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

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

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

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

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

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

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

Функции двух переменных, рассмотренные в табл. 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		см.рис. 3.1, к
f10=x2	Инверсия, отрицание x2	Не x2		см.рис. 3.1, л
f11=x2 x1	Импликация x1	Если x2, то x1		см.рис. 3.1, м
f12=x1	Инверсия, отрицание x1	Не x1		см.рис. 3.1, н
f13=x1 x2	Импликация 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 = ).

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