Математический аппарат инженера

Число всевозможных булевых функций n переменных v = 2ⁿбыстро возрастает с увеличением n (при n = 3 оно равно 256, а при n = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при n = 2).

5. Булевы функции одной переменной. Общая таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций):

x	0	1
y0 = 0	0	0
y1 = x	0	1
y2 = x̅	1	0
y3 = 1	1	1

Две функции у₀ = 0 и у₃ = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y₁ = х повторяет значения переменной х и потому просто совпадает с ней.

Единственной нетривиальной функцией является у₂ = x̅ , называемая отрицанием или инверсией ( x̅ читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

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

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

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

- 507 -

Таблица 6

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

x1 x2	0011 0101	Обозначения	Названия	Чтение
y0	0000		Константа 0 (тождественный нуль, всегда ложно)	Любое 0
y1	0001	x1x2; x1 ∧ x2 ( x1 & x2 ; x1 ∩ x2 )	Конъюнкция (совпадение, произведение, пересечение, логическое «и»)	x1 и x2 (и x1 и x2)
y2	0010	x1←x2 ( x1⊃x2 ; x1\x2 )	Отрицание импликации (совпадение с запретом, антисовпадение, запрет)	x1, но не x2
y3	0011	x1	Повторение (утверждение, доминация) первого аргумента	Как x1
y4	0100	x2⊃x1 ( x2 ⊄ x1 ; x2 \ x1 )	Отрицание обратной импликации (обратное антисовпадение)	Не x1, но x2
y5	0101	x2	Повторение (утверждение, доминация) второго аргумента	Как x2
y6	0110	x1 + x2 ( x2 ⊕ x1 )	Сумма по модулю 2 (неравнозначность, антиэквивалентность)	x1 не как x2 (или x2 или x1)
y7	0111	x1 ∨ x2 (x1 + x2; x1 ∪ x2 )	Дизъюнкция (разделение, логическая сумма, сборка, логическое «или»)	x1 или x2 (x1 или хотя бы x2)
y8	1000	x1 ↓ x2 ( x1 ∨̅ x2 ; x1 ○ x2 )	Стрелка Пирса (функция Вебба, отрицание дизъюнкции, логическое «не – или»)	Ни x1,ни x2

- 508 -

Продолжение табл. 6