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

x1 x2	0011 0101	Обозначения	Названия	Чтение
y9	1001	x1 ~ x2 ( x1 ≡ x2 ; x1 ↔ x2)	Эквиваленция (равнозначность, эквивалентность, взаимозависимость)	x1 как x2 (x1, если и только если x2)
y10	1010	x̅2 (x'2; ~x2; ¬ x2)	Отрицание (инверсия) второго аргумента (дополнение к первой переменной)	Не x2
y11	1011	x2 → x1 ( x1 ⊂ x2 ; x1 < x2 )	Обратная импликация (обратное разделение с запретом, обратная селекция)	Если x2, то x1 (x1 или не x2)
y12	1100	x̅1 (x1; ~x1; ¬ x1)	Отрицание (инверсия) первого аргумента (дополнение к первой переменной)	Не x1
y13	1101	x1→x2 ( x1⊃x2 ; x1 > x2 )	Импликация (разделение с запретом, следование, селекция)	Если x1, то x1 (не x1 или x2)
y14	1110	x1 / x2 ( x1 ∧̅ x2 ; x1 &̅ x2 )	Штрих Шеффера (отрицание конъюнкции, несовместность, логическое «не – и»)	Не x1 или не x2
y15	1111	1	Константа 1 (тождественная единица, всегда истино)	Любое 1

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

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

x₁x₂ = ¬(x₁ / x₂) ; x₁←x₂ = ¬(x₁ → x₂) ; x₁ + x₂ = ¬(x₁ ~ x₂) ; x₁ ∨ x₂ = ¬(x₁ ↓ x₂) ,

или

x₁/x₂ = ¬(x₁x₂) ; x₁→x₂ = ¬(x₁←x₂) ; x₁ ~ x₂ = ¬(x₁ + x₂) ; x₁ ↓ x₂ = ¬(x₁ ∨ x₂) .

- 509 -

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

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

x₁ → x₂ = x̅₁ ∨ x₂

x₁ ~ x₂ = (x₁ ∨ x̅₂)(x̅₁ ∨ x₂).

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

x1	0	0	1	1
x2	0	1	0	1
x̅1	1	1	0	0
x̅2	1	0	1	0
(x̅1 ∨ x2)	1	1	0	1	x1→x2
(x1 ∨ x̅2)	1	0	1	1
(x1 ∨ x̅2)(x̅1 ∨ x2)	1	0	0	1	x1 ~ x2

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

x₁ ∨ x₂ = ¬(x̅₁x̅₂); x₁x₂ = ¬(x̅₁ ∨ x̅₂).

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

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

x̅ = x ↓ x = x/x;

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

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

- 510 -

функции от любого числа переменных. Например, подставляя в выражение аb формулы a = x₁ ∨ x₂ и b = x₂ → c, а также c=x̅₃, получаем (x₁ ∨ x₂)(x₂ → x̅₃) . Таблица соответствия для сложных формул записывается на основании общей таблицы для элементарных функций. Для данного примера она имеет вид: