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

Рассмотрение понятия функции в алгебре логики (АЛ) можно начать с функций одной переменной. Нетрудно видеть, что таких функций можно построить четыре (табл. 1.1).

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

Переменная	Функции
x	g1	g2	g3	g4

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

Для двух переменных может быть введено уже 16 функций (табл. 1.2).

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

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

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

 

Таблица 1.3. Зависимость числа логических функций от числа входных переменных

Количество входных переменных				...	n
Число входных наборов	21	22	23	...	2n
Число логических функций	21	24	28	...	22n

 

Логическая функция определяется как n-местная функция, определенная на множестве истинных значений <Истина (True), Ложь (False)> и принимающая значения в этом множестве.

Если последовательность логических переменных обозначить как X=(x₁, x₂, ..., x_n) и назвать двоичным набором, то под функцией алгебры логики следует понимать однозначное отображение множества всевозможных наборов * на множествоY=<0,1>.

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

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

 

 

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

Функция в аналити-ческом выражении	Наименование	Словестное выражение	Выражение в элементарном базисе	Функциональ-ное обозна-чение
f0=0	Константа “0”	Всегда ложно	x1x1v x2x2	рис. 1.1.а
f1=x1x2 f1=x1&x2	Конъюнкция, И	x1 и x2	x1&x2	рис. 1.1.б
f2=x1 x2	Запрет x1	Запрет по x2	x1x2	рис. 1.1.в
f3=x1	Повторение x1	Повторение x1	x1	рис. 1.1.г
f4=x2 x1	Запрет x2	Запрет по x1	x1x2	рис. 1.1.д
f5=x2	Повторение x2	Повторение x2	x2	рис. 1.1.е
f6=x1x2	Сложение по модулю 2, неравнозначность, исключающее ИЛИ	x1 неравно-значно x2	x1x2v x1x2	рис. 1.1.ж
f7=x1v x2 f7=x1+x2	Дизъюнкция, ИЛИ	x1 или x2	x1v x2	рис. 1.1.з
f8=x1x2	Стрелка Пирса1, ИЛИ-НЕ	не x1 и не x2	x1 v x2	рис. 1.1.и
f9=x1x2	Равнозначность, эквивалентность	x1 равно-значно x2	x1x2v x1x2	рис. 1.1.к
f10=x2	Инверсия, отрицание x2	Не x2	x2	рис. 1.1.л
f11=x2x1	Импликация x1	Если x2, то x1	x1v x2	рис. 1.1.м
f12=x1	Инверсия, отрицание x1	Не x1	x1	рис. 1.1.н
f13=x1x2	Импликация x2	Если x1, то x2	x1v x2	рис. 1.1.о
f14=x1| x2	Штрих_Шеффера2, И-НЕ	Не x1 или не x2	x1 x2	рис. 1.1.п
f15=1	Константа “1”	Всегда истинно	(x1v x1) (x2v x2)	рис. 1.1.р

 

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

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

Функция АЛ, полученная из функций f₁, f₂, ..., f_k с помощью этих правил, называется суперпозицией функций f₁, f₂, ..., f_k. В табл. 1.4 приведено представление различных функций через суперпозицию конъюнкции, дизъюнкции и отрицания.

 

Рис. 1.1.а	Рис. 1.1.б	Рис. 1.1.в
Рис. 1.1.г	Рис. 1.1.д	Рис. 1.1.е
Рис. 1.1.ж	Рис. 1.1.з	Рис. 1.1.и
Рис. 1.1.к	Рис. 1.1.л	Рис. 1.1.м
Рис. 1.1.н	Рис. 1.1.о	Рис. 1.1.п
	Рис. 1.1.р

 

В приложении 3 ТО даны основные параметры и изменения в наименованиях применяемых микросхем.

 

133ЛА3четыре логических элемента «2И-НЕ»