Данная теорема утверждает, что инверсия любой функции в АЛ
получается путем замены каждой переменной ее инверсией и
одновременно взаимной заменой символов конъюнкции и дизъюнкции.
Справедливость любого закона АЛ можно доказать разными
методами. Законы (1-5) доказываются путем прямой подстановки
вместо переменной значений 0 и 1. Ряд законов доказывается
методом перебора всех возможных значений переменных, для которых
проверяется справедливость закона. Для доказательства закона
достаточно показать тождественность выражений, образующих левую
и правую стороны доказываемого соотношения при всех наборах
переменных, принимающих значения 0 или 1. Общий формальный метод
доказательства законов АЛ состоит в том, что справедливость
каждого закона доказывается на основе аксиом и ранее доказанных
законов. Доказательство заключается в приведении обеих частей
выражения к одному виду с помощью последовательных преобразований.
Для доказательства законов инверсии следует воспользоваться
методом математической индукции.
Рассмотрим следующие примеры:
Пример 1.1.
Доказать справедливость закона нулевого множества.
Рассмотрим запись закона в виде 0 v x = x. Проверим
справедливость этого равенства для всех возможных значений x.
При x = 0 получаем равенство 0 v 0 = 0, справедливое по
аксиоме 3. При x = 1 имеем 0 v 1 = 1 также в соответствии
с аксиомой 3. Таким образом, равенство 0 v x = x
выполняется при всех возможных значениях переменной x,
следовательно является теоремой.
Рассмотрим запись закона в виде 0 & x = 0.
При x = 0 имеем 0 & 0 = 0, в соответствии с аксиомой 4.
При x = 1 имеем 0 & 1 = 0 также по аксиоме 4,
следовательно закон выполняется.
Рассмотрим запись закона в виде:
0 & x1& x2 ... xn ... = 0.
Воспользуемся методом индукции. Первым этапом данного метода
является доказательство истинности теоремы при n = 1. Это положение
уже было доказано нами выше. Теперь предположим, что теорема
справедлива при некотором n и докажем, что она справедлива и при
n+1.
Действительно, при некотором n будем иметь равенство:
0 & x1& x2 ... xn = 0.
Для n+1 выражение примет вид:
0 & x1& x2 ...
xn& xn+1 = 0.
Но на основании предположения индукции можно записать
0 & xn+1 = 0, то есть мы вернулись к
рассмотренному выше случаю одной переменной. Таким образом,
справедливость закона нулевого множества доказана для
произвольного числа переменных.
Пример 1.2.
Доказать справедливость закона поглощения. Будем считать, что
справедливость законов (1-8) уже доказана. В
процессе преобразований над знаком равенства будем ставить номер
формулы использованного закона или аксиомы.
.gif){kind=spacer}
= x.