Булева алгебра

Булевы функции двух переменных. Все 16 функций двух переменных приведены в табл. 6, где указаны условные обозначения, названия и чтения функций (в скобках даны встречающиеся в литературе варианты).

Шесть из приведенных функций не зависят от x₁ или x₂ (или от обоих вместе). Это две константы (у₀ = 0 и у₁₅ = 1), повторения (у₃ = х₁ и у₅ = х₂) и отрицания (у₁₀ = и у₁₂ = ), являющиеся функциями одной переменной (х₁ или x ₂). Из остальных десяти функций две (y₄ и y₁₁) отличаются от соответствующих им (y₂ и y₁₃) лишь порядком расположения аргументов и поэтому не являются самостоятельными. Поэтому из 16 булевых функций двух переменных только восемь являются оригинальными (у₁, у₂, у₆, у₇, у₈, у₉, у₁₃, у₁₄).

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

Таблица 6

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

x1 x2	0 0 1 1 0 1 0 1	Обозначения	Названия	Чтение
y0	0 0 0 0		Константа 0 (тождественный нуль, всегда ложно)	Любое 0
y1	0 0 0 1	x1x2; (; )	Конъюнкция (совпадение, произведение, пересечение, логическое «и»)	x1 и x2 (и x1 и x2)
y2	0 0 1 0	(; )	Отрицание импликации (совпадение с запретом, антисовпадение, запрет)	x1, но не x2
y3	0 0 1 1	X1	Повторение (утверждение, доминация) первого аргумента	Как x1
y4	0 1 0 0	(; )	Отрицание обратной импликации (обратное антисовпадение)	Не x1, но x2
y5	0 1 0 1	x2	Повторение (утверждение, доминация) второго аргумента	Как x2
y6	0 1 1 0	x1 + x2 (; )	Сумма по модулю 2 (неравнозначность, антиэквивалентность)	x1 не как x2 (или x2 или x1)
y7	0 1 1 1	(x1 + x2; )	Дизъюнкция (разделение, логическая сумма, сборка, логическое «или»)	x1 или x2 (x1 или хотя бы x2)
y8	1 0 0 0	(; )	Стрелка Пирса (функция Вебба, отрицание дизъюнкции, логическое «не – или»)	Ни x1,ни x2
y9	1 0 0 1	x1 ~ x2 (; )	Эквиваленция (равнозначность, эквивалентность, взаимозависимость)	x1 как x2 (x1, если и только если x2)
y10	1 0 1 0	(x2; ~ x2; x2)	Отрицание (инверсия) второго аргумента (дополнение к первой переменной)	Не x2
y11	1 0 1 1	(; )	Обратная импликация (обратное разделение с запретом, обратная селекция)	Если x2, то x1 (x1 или не x2)
y12	1 1 0 0	(x1; ~ x1; x1)	Отрицание (инверсия) первого аргумента (дополнение к первой переменной)	Не x1
y13	1 1 0 1	(; )	Импликация (разделение с запретом, следование, селекция)	Если x1, то x1 (не x1 или x2)
y14	1 1 1 0	x1 / x2 (; )	Штрих Шеффера (отрицание конъюнкции, несовместность, логическое «не – и»)	Не x1 или не x2
y15	1 1 1 1		Константа 1 (тождественная единица, всегда истино)	Любое 1

зависящиеот всех переменных, являются невырожденными. Так, среди функций одной переменной имеются две вырожденные (константы 0 и 1, которые можно рассматривать как функции от нуля переменных), функции двух переменных содержат те же константы и четыре функции одной переменной и т. д.

Зависимость между булевыми функциями. Из табл. 6 видно, что между функциями имеются зависимости (i = 0, 1,......, 15), на основании которых можно записать соотношения для констант и , для функции одной переменной х = и для функций двух переменных:

x₁x₂ = ; = ; x₁ + x₂ = ; = ,

или

x₁ / x₂ = ; = ; x₁ ~ x₂ = ; = .

Из этих зависимостей следует, что любая функция двух переменных (включая константы) выражается в аналитической форме через совокупность шести функций, содержащей отрицание и любую из каждой пары функций { y₀, y₁₅ },{ y₁, y₁₄ },{ y₂, y₁₃ }, { y₆, y₉ }, { y₇, y₈ }. Например, такой совокупностью могут служить функции: константа 0, отрицание` х, конъюнкция х₁x₂, дизъюнкция ,эквиваленция х₁ ~ x₂ и импликация . Как уже упоминалось в (1. 5. 8), они используются в исчислении высказываний.

Выбранная таким способом совокупность шести функций является избыточной. Можно показать, что импликация и эквиваленция выражаются через остальные функции этой совокупности:

;

.

Для этого достаточно построить таблицу соответствия и сравнить ее с табл. 6:

x1 x2

Таким образом, комплект элементарных функций сокращается до четырех: константа 0, отрицание , конъюнкция x₁x₂ и дизъюнкция . Этот комплект обладает существенными удобствами и часто применяется на практике, но и он может быть сокращен. Так, из законов де Моргана и свойства двойного отрицания вытекают тождества:

; x₁x₂ = .

Отсюда следует, что булевы функции выражаются через отрицание и конъюнкцию или через отрицание и дизъюнкцию.

Более того, для записи любой булевой функции достаточно только одной из двух элементарных функций — стрелки Пирса или штриха Шеффера. Это вытекает из соотношений (их доказательство приводится аналогично с помощью таблиц соответствия):

;

x₁x₂ = (x₁ / x₂)/(x₁ / x₂); .

Булевы функции многих переменных. С помощью суперпозиции функций, т. е. подстановки в логические формулы вместо переменных некоторых булевых функций, можно получить более сложные функции от любого числа переменных. Например, подставляя в выражение аb формулы и , а также , получаем . Таблица соответствия для сложных формул записывается на основании общей таблицы для элементарных функций. Для данного примера она имеет вид:

x1 x2 x3

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

Например, ; ; ; и т. п.