Эквивалентные преобразования формул логики высказываний

Определение. Две формулы пропозициональной логики называются эквивалентными (равносильными), если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в эти формулы.

Обозначение: F ~ G.

Таким образом, F ~ G тогда и только тогда, когда |= F G.

Отношение эквивалентности обладает следующими свойствами:

1) А~ А (рефлексивность)

2) Если А~ В, то В ~ А (симметричность)

3) Если А~ В и В~ С, то А~ С (транзитивность)

Теорема (об эквивалентной замене). Если формула F(B) содержит подформулу B, и для некоторой формулы C справедливо B ~ C, то F(B) ~ F(C), где F(C) образованна из F(B) заменой B на С.

Доказательство. Индукцией по сложности формулы F, используя очевидные эквивалентности:

Если В~ С, то ØB ~ ØC

D&B ~ D&C, B&D ~ C&D,

D v B ~ D v C, B v D ~ C v D,

D®B ~ D®C, B®D ~ C®D,

DÅB ~ DÅC, BÅD ~ CÅD,

D B ~ D C, B D ~ C D,

где D – произвольная формула логики высказываний.