Разнообразие Булевых функций

1. Булева функция от одной переменной.

Обозначение аргумента и функции	Значения аргумента и функции	Наименование функции
x
			Логический ноль
			Повторение x
			Инверсия x
			Логическая единица

2. Возможные функции от двух переменных.

Обозначение аргументов и функций	Значение аргументов и функций	Обозначение функций	Наименование	Вырожденность	Представление функции в булевом базисе
					“0”	Логический ноль	+	-
					x1&x2	Конъюнкция	-	x1 x2
					x1Dx2	Запрет x1 по x2	-	x1 2
					x1	Повторение x1	+	-
					x2Dx1	Запрет x2 по x1	-	x2 1
					x2	Повторение x2	+	-
					x1Åx2	Сумма по модулю 2 неравнозначная (исключительное или) XOR	-	1 x2 Ú x1 2
					x1Úx2	Дизъюнкция	-	x1 Ú x2
					x1¯x2	Функция Вебба	-	x1Úx2
					x1ºx2	Равнозначность	-	1 2 Ú x1 x2
					2	Отрицание x2	+	-
					x2®x1	Импликация от x2 к x1	-	2 Ú x1
					1	Отрицание x1	+	-
					x1®x2	Импликация x1 к x2	-	1 Ú x2
					x1 | x2	Штрих Шеффера	-
					“1”	Логическая единица	+	-

Определение: Булева функция от n аргументов fⁿ(x) называется вырожденной по аргументу x_i, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство:

f(x₁, x₂,..., x_i-1, 0, x_i+1,..., x_n) = f(x₁, x₂, x_i-1, 1, x_i+1,..., x_n).

Функция запрета x₁Dx₂ принимает значение, равное нулю при равенстве запрещающей переменной (x₂) единице и повторяет значение аргумента x₁ при равенстве запрещающей переменной нулю.

Понятие импликации в Булевой алгебре отождествляется с выражением следования (если... то...).

Пример: Имеют место два простых высказывания.

А. На небе тучи.

В. Идет дождь. В®А

А	В	В®А
f	f	t
f	t	f
t	f	t
t	t	t

Из истины не может следовать ложь!

Дата добавления: 2014-11-29