Цепочки формул

[предыдущая глава]  [оглавление]  [следующая глава]

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

Один из самых распространенных приемов обычной алгебры - это цепочка формул, связанных знаками равенства. Что-нибудь вроде:

(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) - после перестановки вокруг значка "&"

Конечно, подобные перестановки и подстановки легко делаются в уме, поэтому так подробно этот процесс мы расписали в первый и последний раз.

1. Упростите формулу ~~~~~B, получив равноистинную ей.
   Посмотреть ответ

   Дважды заменяя подформулу ~~B на подформулу B, получаем:

   ~~~~~B = ~~~B = ~B.

2. Определите, какие замены подформул были сделаны в цепочке: ~~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.

3. Определите, какая тавтология (из рассмотренных ранее) могла применяться для перехода между звеньями цепочки, и какие замены переменных были сделаны для получения этой тавтологии: ... = (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.

4. Определите, какая тавтология (из рассмотренных ранее) могла применяться для перехода между звеньями цепочки, и какие замены переменных были сделаны для получения этой тавтологии: ... = (A R) & B C & D Q = ~(C & D) ~((A R) & B) Q = ...
   Посмотреть ответ

   Ответ точно такой же, как в предыдущем примере, только после преобразования к наглядному виду формула будет выглядеть иначе:

   ((~a(...) ~c(...)) Q) ((c(...) a(...)) Q)

   Если в предыдущем примере делалась замена всей формулы целиком, то здесь заменяется только часть формулы, не включающая в себя фрагмент " Q".

5. Найдите ошибку в этом фрагменте цепочки: = ... 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) = ...

   Увы, нет. Дело в том, что операция "" не разрешает произвольный порядок выполнения, как например операция "&", поэтому мы не имеем права менять порядок путем другой расстановки скобок.

   На первых порах можно перестраховываться и расставлять по-больше скобок, чтобы не делать подобных ошибок.

6. Избавьтесь от операции "" в формуле A B C и упростите полученую формулу.
   Посмотреть ответ

   От материальной импликации избавляемся с помощью тавтологии (X Y) (~X Y). Применяем ее дважды, делая замену подформулы:

   A B C =

   (~A B) C =

   ~(~A B) C =

   далее раскрываем скобки после знака "~":

   = (~~A & ~B) C =

   и убираем двойное отрицание:

   = (A & ~B) C.