Доказательство

Пусть у нас формула имеет вид:

A(...) (c(...) & d(...)) B(...)    (1)

- где A(...) и B(...) обозначают обрамляющие фрагменты формулы (сами - не формулы, а c(...) и d(...) - формулы). Нам неважно, какой они имеют вид, лишь бы все вместе образовывало булеву формулу.

Берем тавтологию

(X & Y) (Y & X)    (2)

Дважды применяем правило замены переменной: X на c(...) и Y на d(...). В результате получаем тавтологию:

(c(...) & d(...)) (d(...) & c(...))

Эта формула показывает равноистинность двух подформул. Левая подформула (c(...) & d(...)) присутствует также и в формуле (1). Значит, по правилу замены подформулы мы можем заменить ее на (d(...) & c(...)):

A(...) (d(...) & c(...)) B(...)

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

Тем самым мы доказали возможность перестановки для операции &. Для трех других операций доказательство очень похоже, только в доказательстве надо заменить значок "&" на один из трех других значков. Подходящие формулы (2) были доказаны в главе "Тавтологии".

Доказательство

Рассмотрим случай операции &. Для трех других операций доказательство будет отличаться только заменой значка "&" на один из трех других значков.

Пусть в формуле есть фрагмент из двух операций &, идущих подряд:

A(...) (c(...) & d(...) & e(...)) B(...)

- где A(...) и B(...) обозначают обрамляющие части формулы. Нам неважно, какой они имеют вид, лишь бы все вместе образовывало булеву формулу.

Итак, у нас есть две операции & в этом фрагменте. Нам надо доказать, что порядок вычисления их неважен. Укажем с помощью скобок этот порядок. Первый вариант: сначала вычисляется левая конъюнкция:

A(...) ((c(...) & d(...)) & e(...)) B(...)    (3)

Второй вариант: сначала вычисляется правая конъюнкция:

A(...) (c(...) & (d(...) & e(...)) B(...)    (4)

Возьмем тавтологию:

(X & (Y & Z)) ((X & Y) & Z)

Сделаем ней три замены переменных: X на c(...), Y на d(...), Z на e(...). Получим:

((c(...) & d(...)) & e(...)) (c(...) & (d(...) & e(...))

Левая часть этой формулы присутствует в формуле (3) в качестве подформулы. По правилу замены подформулы мы можем ее заменить на правую часть. Но тогда получится формула (4). По правилу замены подформулы обе формулы (3) и (4) будут равноистинными.