Два правила замены во многом похожи на правила замены в обычной алгебре, если проводить параллели между понятием "тавтология" и
понятием "тождество". В результате многие приемы, доступные в обычной алгебре, оказываются доступны и в булевой. Только надо определить, какие именно.
Один из самых распространенных приемов обычной алгебры - это цепочка формул, связанных знаками равенства. Что-нибудь вроде:
(a + b)
c - a
c = a
c + b
c - a
c = b
c = b
c + (с - с)
В этом примере цепочка из четырех формул соединена тремя знаками равенства. Это - сокращенная запись для трех тождеств:
(a + b)
c - a
c = a
c + b
c - a
c
a
c + b
c - a
c = b
c
b
c = b
c + (с - с)
В каждом тождестве левая часть тождественна правой, а правая часть повторяет левую часть следующего тождества.
В результате, любые две формулы из цепочки тождеств могут образовать тождество. Например, можно объединить в тождество
самую первую и самую последнюю формулы:
(a + b)
c - a
c = b
c + (с - с)
Подобный же прием работает и с тавтологиями со значком "
". Возьмем такие формулы:
1. (a
b) & c
a & c
(a & c
b & c)
a & c
2. (a & c
b & c)
a & c
(b & c
a & c)
a & c (1)
3. (b & c
a & c)
a & c
b & c
(a & c
a & c)
4. b & c
(a & c
a & c)
b & c
a & c
Нетрудно убедиться (например, составив таблицы истинности), что все эти формулы - тавтологии.
Каждая имеет вид f(...)
g(...).
В каждой тавтологии левая часть равноистинна правой, а правая часть повторяет левую часть следующей тавтологии.
В результате все формулы по обе стороны от знаков
равноистинны и
любые две из них могут образовать новую тавтологию. Например, самая первая левая часть и самая последняя правая
образуют тавтологию:
(a
b) & c
a & c
b & c
a & c
Наконец, для всей серии тавтологий (1) можно использовать сокращенную запись, соединив формулы в цепочку знаками равенства:
(a
b) & c
a & c =
(a & c
b & c)
a & c =
(b & c
a & c)
a & c =
b & c
(a & c
a & c) =
b & c
a & c
Для подобных цепочек мы будем использовать знак равенства "=",
а значок равноистинности "
" - в качестве обычной булевой операции.
Итак, тавтологии вида f(...)
g(...) можно объединять в цепочки. Для чего это можно использовать?
Во-первых, для получения новых тавтологий. Любые два звена цепочки могут образовать новую тавтологию. Во-вторых, для поэтапного
упрощения формул. Если самая первая левая часть сложнее, чем самая последняя правая, то получится как раз упрощение.
Поскольку сложная и простая формулы равноистинны, то для вычисления значения сложной формулы достаточно будет вычислить значение простой.
Точно так же цепочки формул используются в обычной алгебре. Тем же путем можно поэтапно доказывать равноистинность
самых разных формул.
Для перехода от одной формулы цепочки к другой удобно использовать правила замены. Это проще и быстрее, чем доказывать
каждую тавтологию таблицей истинности. Обычно на каждом шаге делается одна замена подформулы или сразу серия таких замен.
Возьмем пример (1). На 1-м шаге подформула (a
b) & c
была заменена на (a & c
b & c). На 2-м шаге подформула a & c
b & c
была заменена на b & c
a & c. На 3-м шаге формула была заменена целиком.
На 4-м шаге подформула (a & c
a & c) заменена на подформулу a & c.
Для замены старой подформулы на новую надо сначала доказать, что они равноистинны. И вот тут уже понадобится
правило второе правило - замена переменной. Например, на 1-м шаге нужно доказать, что
(a
b) & c
(a & c
b & c).
Для этого берется одна из формул-тавтологий, и в ней делается 4 перестановки и 3 подстановки:
(X & Y)
(X & Z)
X & (Y
Z) - исходная формула
X & (Y
Z)
(X & Y)
(X & Z) - после перестановки вокруг значка "
"
(Y
Z) & X
(X & Y)
(X & Z) - после перестановки вокруг значка "&"
(a
Z) & X
(X & a)
(X & Z) - после замены Y на a
(a
b) & X
(X & a)
(X & b) - после замены Z на b
(a
b) & c
(c & a)
(c & b) - после замены X на c
(a
b) & c
(a & c)
(c & b) - после перестановки вокруг значка "&"
(a
b) & c
(a & c)
(b & c) - после перестановки вокруг значка "&"
Конечно, подобные перестановки и подстановки легко делаются в уме, поэтому так подробно этот процесс мы расписали
в первый и последний раз.
- Упростите формулу ~~~~~B, получив равноистинную ей.
Дважды заменяя подформулу ~~B на подформулу B, получаем:
~~~~~B = ~~~B = ~B.
- Определите, какие замены подформул были сделаны в цепочке:
~~A & ~~B & A & C & C =
A & ~~B & A & C & C =
A & ~~B & A & C =
A & B & A & C =
B & A & A & C =
B & A & C =
A & B & C.
~~A на A,
C & C на C,
~~B на B,
A & B на B & A,
A & A на A,
B & A на A & B.
- Определите, какая тавтология (из рассмотренных ранее) могла применяться для перехода между звеньями цепочки, и
какие замены переменных были сделаны для получения этой тавтологии:
... = (A
R) & B
C & D = ~(C & D)
~((A
R) & B) = ...
В принципе, после недолгой тренировки ответ можно дать сразу. Если есть трудности, то можно
расписать этот процесс детально.
Сначала ищем повторяющиеся фрагменты в формулах. Несколько
раз встречается C & D и несколько раз (A
R) & B.
Обозначим первую формулу как c(...), а вторую как a(...):
... = ~c(...)
~a(...) = a(...)
c(...) = ...
Теперь формула стала более обозримой. Вторым шагом выпишем тавтологию, которая образуется этим фрагментом:
(~a(...)
~c(...))
(c(...)
a(...)) (2)
Ищем похожую формулу в таблице тавтологий. Обнаруживаем такую:
(X
Y)
(~Y
~X)
Для большего сходства нужно поменять местами две половинки формулы:
(~Y
~X)
(X
Y)
Теперь получилась формула, в которой переменные соответствуют фрагментам нашей исходной формулы (2).
Значит, эта тавтология могла быть применена.
Осталось только указать, что на что заменялось.
Переменной Y соответствует a(...), а так мы обозначили формулу (A
R) & B.
Другими словами, переменная Y заменяется на (A
R) & B.
Аналогично переменная X заменяется на c(...), то есть на C & D.
- Определите, какая тавтология (из рассмотренных ранее) могла применяться для перехода между звеньями цепочки, и
какие замены переменных были сделаны для получения этой тавтологии:
... = (A
R) & B
C & D
Q = ~(C & D)
~((A
R) & B)
Q = ...
- Найдите ошибку в этом фрагменте цепочки:
= ... W
A
B = W
~B
~A
Казалось бы, есть подходящая тавтология:
(X
Y)
(~Y
~X) (3)
Однако давайте раставим скобки в исходной формуле, согласно порядку выполнения операций:
= ... (W
A)
B = (W
~B)
~A = ... (4)
Теперь мы видим, что переменной X в тавтологии (3) соответствует фрагмент "A)" в тавтологии (4),
который не является правильной булевой формулой из-за непарной скобки.
Но мы можем заменять только правильную булеву формулу на другую правильную.
А могли ли мы расставить скобки в более походящем порядке?
Например, так:
= ... W
(A
B) = W
(~B
~A) = ...
Увы, нет. Дело в том, что операция "
" не разрешает произвольный порядок выполнения, как например
операция "&", поэтому мы не имеем права менять порядок путем другой расстановки скобок.
На первых порах можно перестраховываться и расставлять по-больше скобок, чтобы не делать
подобных ошибок.
- Избавьтесь от операции "
" в формуле A
B
C и упростите полученую формулу.
От материальной импликации избавляемся с помощью тавтологии (X
Y)
(~X
Y). Применяем
ее дважды, делая замену подформулы:
A
B
C =
(~A
B)
C =
~(~A
B)
C =
далее раскрываем скобки после знака "~":
= (~~A & ~B)
C =
и убираем двойное отрицание:
= (A & ~B)
C.