§ 7. Свойства операций штрих Шеффера, стрелка Пирса и сложения по модулю два

Из определений операций  (штрих Шеффера) и ↓ (стрелка Пирса) следует, что:

$x| y = ¬(x\&y)$

$x↓ y = ¬(x∨y)$

Теорема 3.6.Для каждой формулы существует равносильная ей формула, содержащая только связку | , либо только связку ↓.

Доказательство. Докажем, что можно оставить только связку | . По теореме 3.5 для каждой формулы существует равносильная ей формула, содержащая только ¬ и ∨. Далее легко убедиться, например, с помощью таблиц истинности или, используя (3.10), что $¬x ~ x|x, x∨y ~ (x| x)|(y|y)$

Таким образом, ¬ и ∨ можно исключить и оставить только связку |.

Теперь покажем, что можно оставить только ↓. Согласно теореме 3.5 можно оставить только связки ¬ и &. С помощью таблиц истинности или по (3.11) легко показать, что $¬x ~ x↓ x; x\&y ~ (x↓ x)↓(y↓ y)$, следовательно, остается только связка ↓ . Теорема доказана.

Теперь покажем, что нет другой бинарной связки, кроме ¬, ↓, обладающей тем свойством, что через нее можно выразить все остальные.

Теорема 3.7. Единственными бинарными связками, каждой из которых достаточно для выражения всех формул, являются связки ↓ и |.

Доказательство. Предположим, что ° является достаточной в указанном смысле связкой. Если бы 1°1 было 1, то любая формула, построенная с помощью только лишь °, принимала бы значения 1, когда все входящие в нее переменные принимают значение 1. Следовательно, формула x&¬x не могла быть выраженной только через °. Итак, 1°1 = 0.

Далее выясним, чему равняется 0° 0. Если бы 0° 0 = 0, то любая формула, построенная с помощью только лишь °, принимала бы значение 0, когда значения переменных равны 0. Следовательно, формула  x не могла бы быть выражена только через °. Поэтому 0° 0 = 0. Таким образом, имеем таблицу:

Если второе и третье места в столбце значений этой таблицы заняты соответственно значениями 1, 1 или 0, 0, то получаем x° y = x↓y либо x° y = x|y . Если же на этих местах стоит 0, 1 или 1, 0, то получаем соответственно x ° y равносильно ¬y либо ¬x. В обоих случаях функция ° выражена через ¬ . Однако связка ¬ не является достаточной для выражения любой формулы, ибо с помощью ¬ можно получать формулы только вида ¬x, ¬(¬x) и т.п., а например формулу, тождественно равную 1, получить нельзя. Теорема доказана.

Для операции сложения по модулю два имеем: x+y=¬(x≡y).

Эта операция, очевидно, коммутативна: x+y=y+x. Легко убедиться, что конъюнкция дистрибутивна относительно сложения по модулю два, т.е.$x\&(y+z) ~ (x\&y)+(x\&z), (y+z)\&x~(y\&x)+(z\&x)$. Также просто показать, что $x+x ~ 0, x + x + x ~ x$. Более обще: если суммировать одинаковые слагаемые чётное число раз, то получим нуль, если же число одинаковых слагаемых, например x, нечётно, то эта сумма равносильна x.