§ 6. Зависимости между булевыми функциями

Операции (связки) $¬ , \&, ∨, =>, ≡ ,+, |$ и $↓ $ не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие так, что при этом получаются равносильные формулы.

Легко видеть, что

$x+ y ~ ¬(x≡ y).$

Связка ≡ может быть выражена через связки ⇒ и & на основании соотношения

$x≡ y ~ (x⇒ y) \& (y⇒ x).$

Для доказательства этой равносильности достаточно составить таблицы истинности и убедиться, что результирующие столбцы этих таблиц совпадают.

Для импликации имеем:

$x⇒ y ~ ¬x∨y.$

Таким образом, связку ≡ можно выразить через ¬ , & и ∨ :

$x ≡ y ~ (¬x∨y) \& (¬y∨x)$

Так как x равносильно ¬(¬x), то x&y равносильно ¬(¬x)&¬(¬y), а последнее согласно закону де Моргана равносильно ¬(¬x ∨ ¬y), следовательно,

$x\&y ~ ¬(¬x ∨ ¬y)$

Аналогичным образом можно получить следующее:

$x∨y ~ ¬(¬x \& ¬y)$

Из соотношения (3.2) заменой ¬x на x получаем, что

$x∨y ~ ¬x⇒ y$

Также легко убедиться, что:

$x|y ~ ¬(x\&y), x↓y ~ ¬(x∨y)$

Имеют место следующие теоремы.

Теорема 3.3. Для каждой формулы А существует равносильная ей формула, содержащая только связки ¬ , &, ∨, причем связка ¬ относится только к переменным.

Доказательство Связки ⇒, ≡,+, | и ↓ можно исключить согласно соотношениям (3.2), (3.3), (3.1) и (3.7). При этом останутся только связки ¬ , &, ∨. Если связка  стоит перед некоторой скобкой, то на основании законов де Моргана можно внести ¬ под скобки, при этом связка & меняется на ∨, а ∨ на &, а связки, отличные от ¬ , &, ∨, не появятся. Внеся ¬ под скобки, перед которыми они стоят, добьемся, чтобы ¬ относилась только к переменным. Теорема доказана.

Теорема 3.4. Для каждой формулы А существует равносильная ей формула, содержащая либо только связки ¬ , &, либо только ¬ , ∨, либо только ¬ , ⇒.

Доказательство. Покажем, что можно оставить только связки ¬ и &. По предыдущей теореме можно оставить только связки ¬ , &, ∨. Связку ∨. исключим по (3.5). В результате останутся только ¬ и &. Остальные утверждения теоремы доказываются аналогичным образом.

Рассмотрим формулы, содержащие только связки ¬ , &, ∨. Как уже установлено, всякая формула может быть приведена преобразованиями равносильности к формуле, содержащей только ¬ , &, ∨.

Будем говорить, что связка & двойственна связке ∨ и наоборот.

Формулы А и А* называются двойственными, если одна получается из другой заменой каждой связки & и ∨ на двойственную.

Например, если $А =(x∨¬y)\&z, то А* =(x \& ¬y)∨z.$

Отношение двойственности взаимно: если А двойственно А*, то А* двойственно А. Следующую теорему считают законом двойственности.

Теорема 3.5. Если формулы А и В равносильны, то и двойственные им формулы А* и В* также равносильны.

Доказательство. Пусть А и В равносильны, а $x_1,x_2,...,x_n$ – переменные, входящие в А или В. Будем считать, что $x_1,x_2,...,x_n$ входят и в А, и в В. Если бы это было не так, например, В не содержала бы $x_k(1≤ k≤ n)$, входящего в А, то В можно заменить равносильной формулой $В∨x_k\&¬x_k$, содержащей эту переменную.

Таким образом, всегда можем добиться, чтобы А и B содержали все переменные $x_1,x_2,...,x_n$.

По условию

$А(x_1,x_2,...,x_n) ~ В(x_1,x_2,...,x_n)$

Если формулы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (3.8) получим, что

В формулах последнего соотношения добьемся, чтобы  относилась только к переменным. При этом согласно законам де Моргана связки & и ∨ поменяются на двойственные. Следовательно, получим

Равносильность формул $А*(¬x_1,¬x_2,...,¬x_n)$ и $B*(¬x_1,¬x_2,...,¬x_n).$означает, что они принимают одинаковые значения при любых совокупностях значений переменных $x_1,x_2,...,x_n$. Поэтому, если вместо переменных $x_1,x_2,...,x_n$ подставить $¬x_1,¬x_2,...,¬x_n$, то формулы останутся равносильными. Учитывая, что ¬¬х равносильно х, из (3.9) получим

$А*(x_1,x_2,...,x_n) ~ B*(x_1,x_2,...,x_n)$

что и требовалось доказать.