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

Правило замены подформулы. Мы приведем три его формулировки:

1. В любой формуле можно заменить подформулу на равноистинную ей подформулу - и в результате получится формула, равноистинная исходной.

2. Если формулы f(...) и g(...) равноистинны, то формулы A(...) f(...) B(...) и A(...) g(...) B(...) - равноистинны.

3. Если f(...) g(...) - тавтология, то A(...) f(...) B(...) A(...) g(...) B(...) - тавтология.

Обозначение A(...) f(...) B(...) символизирует некую булеву формулу, в которую входит формула f(...) в качестве подформулы. Слева и справа от f(...) могут быть необязательные дополнительные фрагменты формулы, которые обозначены как A(...) и B(...).

Заметьте, что A(...) и B(...) не являются корректно построенными формулами, согласно ранее описанным правилам, а лишь фрагментами такой формулы. Зато f(...), g(...), A(...) f(...) B(...) и A(...) g(...) B(...) должны быть корректно построенными булевыми формулами.

Формулировки 2 и 3, согласно правилу равноистинности, означают одно и то же. Формулировка 1 - это просто пересказ словами формулировки 2. Таким образом, все три формулировки взаимозаменяемы.

Рассмотрим примеры. Возьмем тавтологию

X & Y Y & X

Эта тавтология позволяет нам заменять в любой формуле X & Y на Y & X, получая равноистинную формулу. Например, если у нас есть формула

~(X & Y) Z,

- мы можем изменить ее на формулу

~(Y & X) Z

- с уверенностью, что обе формулы будут равноистинными. Можно делать целые цепочки из формул, так что каждая последующая равноистинна предыдущей (как следствие, все они равноистинны между собой).