Если a º b и b º g, то a º g (свойство транзитивности)

Доказательство непосредственно вытекает из определения. Три приведённых свойства означают, что отношение равносильности является отношением эквивалентности.

Теорема. Для любых переменных высказываний А, В, С справедливы равносильности:

1). (АÚВ)ÚС º АÚ(ВÚС); 1)` (АÙВ) ÙС º АÙ (ВÙС) (ассоциативность операций Ù и Ú);

2). АÚВ º ВÚА; 2)` АÙВ º ВÙА (коммутативность операций Ù и Ú);

3). АÚ(ВÙС) º(АÚВ)Ù(АÚС); 3)` АÙ(ВÚС) º(АÙВ)Ú(ВÙС) (дистрибутивность дизъюнкции относительно конъюнкции (3)) и конъюнкции относительно дизъюнкции (3)`);

4). АÚЛ º А; 4).` АÙИ º А;

5). АÚИ º И; 5)` АÙЛ º Л;

6). АÚА º А; 6)` АÙА º А (идемпотентность дизъюнкции и конъюнкции);

7). Ø(ØА) º А (закон двойного отрицания);

8). `Л º И; 8)` `И º Л;

9). АÚВ º`А Ù`В; 9)` АÙВ º`А Ú`В (теоремы А. де Моргана).

Доказательство каждой из этих равносильностей можно провести с помощью таблиц истинности. Докажем, например, 9):

Четвёртый и седьмой столбцы таблицы совпадают. Это показывает, что при каждом наборе значений переменных А и В формулы Ø(АÚВ) и (ØА)Ù(ØВ) принимают соответственно одинаковые значения, т.е., по определению, являются равносильными.

Как видим, алгебра высказываний, как и алгебра множеств, является булевой алгеброй.

Если в любой из равносильностей последней теоремы любое переменное высказывание заменить всюду и одинаково одной и той же формулой, то получим новую равносильность. Например, первая теорема де Моргана после замены А на a и В на b даёт равносильность Ø(aÚb) º (Øa)Ù(Øb), где a и b - произвольные формулы.

Далее. Заменяя в любой формуле любую её часть равносильной этой части формулой, получим формулу, равносильную данной. При этом предполагается, что эта часть формулы сама должна быть формулой. Возьмём, например, формулу СÞØ(АÚВ). Согласно последней теореме Ø(АÚВ) º (ØА)Ù(ØВ). Поэтому, выполнив указанную выше замену, имеем равносильность С ÞØ(АÚВ) º С Þ (ØА)Ù(ØВ).

Законы логики. Виды теорем.

Методы математических доказательств.