Глава 19. Булевы функции. Элементарные булевы функции

Функции F : ЕN2 ® E2, Где E2 = {0, 1}, называются Функциями алгебры логики, Или Булевыми функциями. Множество булевых функций от П Переменных обозначим Рп, Рп = {F | F : ЕN2 ®Е2}.

Булеву функцию от П Переменных можно задать Таблицей истинности:

X1, …, XN-1, XN	F(X1,…,XN)
0 … 0 0 0 … 0 1 0 … 1 0 … … … … 1 … 1 1

Если число переменных П, То в таблице истинности имеется 2N строк, соответ­ствующих всем различным комбинациям значений переменных, которым мож­но сопоставить различных столбцов, соответствующих различным функциям. Таким образом, число булевых функций от П Переменных с ростом N растет весь­ма быстро:

|Pn| = .

Булевы функции одной переменной:

Переменная Х	0	1
Название	Обозначение
Нуль	0	0	0
Тождественная	X	0	1
Отрицание	Ø х, х'	1	0
Единица	1	1	1

Булевы функции двух переменных:

Переменная Х Переменная У	0 0	0 1	1 0	1 1
Название	Обозначение
Нуль	0	0	0	0	0
Конъюнкция	×, &,	0	0	0	1
		0	0	1	0
		0	0	1	1
		0	1	0	0
		0	1	0	1
Сложение по модулю2 2	+, ¹ , Å, D	0	1	1	0
Дизъюнкция		0	1	1	1
Стрелка Пирса	¯	1	0	0	0
Эквивалентность	~, º, «, Û	1	0	0	1
		1	0	1	0
		1	0	1	1
		1	1	0	0
Импликация	®, Þ, É	1	1	0	1
Штрих Шеффера	|	1	1	1	0
Единица	1	1	1	1	1

< Предыдущая		Следующая >