дискретная математика

21. Элементарные переключательные функции

Переключательные (логические) функции, соответствующие логическим операциям В²В, называют элементарными. Количество переключательных (логических) функций от n переменных определяется выражением 2²ⁿ, поскольку |Bⁿ|=2ⁿ, а на каждом из 2ⁿ наборов переключательная (логическая) функция может принимать одно из значений из того же множества В (табл. 23).

Таблица 23

Переключательные функции от n переменных

№	Набор	Номер логической функции
п/п	значений переменных	0	1	2	3	...	2²ⁿ-1
1	00...00	0	1	0	1	...	1
2	00...01	0	0	1	1	...	1
3	00...10	0	0	0	0	...	1
4	00...11	0	0	0	0	...	1
. . .	. . .	. . .	. . .	. . .	. . .	...	. . .
2²	11...11	0	0	0	0	...	1

Например, рассмотрим все переключательные (логические) функции одной переменной (табл. 24).

Таблица 24

Переключательные функции одной переменной

	Переключательная (логическая) функция
х	f₀(x)	f₁(x)	f₂(x)	f₃(x)
0	0	1	0	1
1	0	0	1	1

Поскольку 2²¹=4, то имеется четыре логических функции одной переменной, две из них – константы: f₀(x)=0, f₃(x)=1 (f₀(x) – константа нуля, f₃(x) – константа единицы). Здесь номер функции означает десятичное число, соответствующее двоичному числу, записанному в соответствующем столбце табл. 24.

Функция f₂(x)=х, т.е. совпадает со значением переменной. Эта функция называется функцией повторения. Функция нам уже известна – это инверсия.

Можно заметить, что для каждой функции одной переменной существует инверсная ей функция:

Элементарные переключательные (логические) функции двух переменных

Рассмотрим все функции двух переменных (табл. 25).

Таблица 25

Переключательные функции двух переменных

		2⁰	2¹	2²	2³
		Набор					Название		Формула
2⁰	х₁	0	1	0	1	функции
2¹	х₂	0	0	1	1
	f₀	0	0	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	Сложение (сумма) по mod2		х₁х₂=
	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		1

Всего таких функций имеется 2²²=2⁴=16. Есть функции, зависящие только от одной переменной. Есть функции, не зависящие от переменных, – константы 0, 1. Такие функции называют вырожденными:

f₃(x₁x₂)=;f₅(x₁x₂)=;f₁₀(x₁x₂)=х₁; f₁₂(x₁x₂)=х₂;

f₀(x₁x₂)=0; f₁₅(x₁x₂)=1.

Некоторые функции мы тоже уже знаем: конъюнкцию f₈(x₁x₂)=х₁х₂ (точку между х₁ и х₂ опускаем); эквиваленцию (эквивалентность) f₉(x₁x₂)=х₁х₂=х₁х₂ (здесь эквиваленция представлена в виде дизъюнкции двух конъюнкций, что можно доказать, составив таблицу истинности); импликацию f₁₁(x₁x₂)=х₂х₁=х₁, f₁₃(x₁x₂)=х₁х₂=х₂; дизъюнкцию f₁₄(x₁x₂)=х₁х₂.

Кроме этого, имеются другие функции, зависящие от двух переменных: f₁(x₁x₂)=– функция Пирса (Вебба) («стрелка Пирса»);f₂(x₁x₂)=– запрет х₂; f₄(x₁x₂)=– запрет х₁; f₆(x₁x₂)=x₁x₂ –сложение по модулю 2 (функция, инверсная эквиваленции); f₇(x₁x₂)=– функция Шеффера («штрих Шеффера»).

Содержание