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

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

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

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

Переменная	Функции
x	g₁	g₂	g₃	g₄
0	0	0	1	1
1	0	1	0	1

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

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

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

Переменные	x₁	1	1	0	0
Переменные	x₂	1	0	1	0
Функции
f₀		0	0	0	0
f₁		1	0	0	0
f₂		0	1	0	0
f₃		1	1	0	0
f₄		0	0	1	0
f₅		1	0	1	0
f₆		0	1	1	0
f₇		1	1	1	0
f₈		0	0	0	1
f₉		1	0	0	1
f₁₀		0	1	0	1
f₁₁		1	1	0	1
f₁₂		0	0	1	1
f₁₃		1	0	1	1
f₁₄		0	1	1	1
f₁₅		1	1	1	1

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

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

Количество входных переменных	1	2	3	...	n
Число входных наборов	2¹	2²	2³	...	2ⁿ
Число логических функций	2¹	2⁴	2⁸	...	₂2ⁿ

Логическая функция определяется как 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. Содержательная таблица функций двух переменных в АЛ

Функция в аналити-ческом выражении	Наименование	Словестное выражение	Выражение в элементарном базисе	Функциональ-ное обозна-чение
f₀=0	Константа “0”	Всегда ложно	x₁x₁v x₂x₂	рис. 1.1.а
f₁=x₁x₂ f₁=x₁&x₂	Конъюнкция, И	x₁ и x₂	x₁&x₂	рис. 1.1.б
f₂=x₁ x₂	Запрет x₁	Запрет по x₂	x₁x₂	рис. 1.1.в
f₃=x₁	Повторение x₁	Повторение x₁	x₁	рис. 1.1.г
f₄=x₂ x₁	Запрет x₂	Запрет по x₁	x₁x₂	рис. 1.1.д
f₅=x₂	Повторение x₂	Повторение x₂	x₂	рис. 1.1.е
f₆=x₁x₂	Сложение по модулю 2, неравнозначность, исключающее ИЛИ	x₁ неравно-значно x₂	x₁x₂v x₁x₂	рис. 1.1.ж
f₇=x₁v x₂ f₇=x₁+x₂	Дизъюнкция, ИЛИ	x₁ или x₂	x₁v x₂	рис. 1.1.з
f₈=x₁x₂	Стрелка Пирса¹, ИЛИ-НЕ	не x₁ и не x₂	x1 v x2	рис. 1.1.и
f₉=x₁x₂	Равнозначность, эквивалентность	x₁ равно-значно x₂	x₁x₂v x₁x₂	рис. 1.1.к
f₁₀=x₂	Инверсия, отрицание x₂	Не x₂	x₂	рис. 1.1.л
f₁₁=x₂x₁	Импликация x₁	Если x₂, то x₁	x₁v x₂	рис. 1.1.м
f₁₂=x₁	Инверсия, отрицание x₁	Не x₁	x₁	рис. 1.1.н
f₁₃=x₁x₂	Импликация x₂	Если x₁, то x₂	x₁v x₂	рис. 1.1.о
f₁₄=x₁\| x₂	Штрих_Шеффера², И-НЕ	Не x₁ или не x₂	x1 x2	рис. 1.1.п
f₁₅=1	Константа “1”	Всегда истинно	(x₁v x₁) (x₂v x₂)	рис. 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.р

¹ Пирс Ч.С. (Pierce) (1839 - 1914) - американский математик, философ и естествоиспытатель.

² Шеффер Г. (Sheffer) - американский математик


	Предыдущая страница \| Следующая страница В начало \| Введение \| Содержание \| Предметный указатель \| О создателях





	© 1999 Vologda, VSTU