Логические равносильности

Формулы А и В называются равносильными, если во всех интерпретациях формул А и В, содержащих все атомы формул А и В, все истинностные значения этих формул совпадают.

Равносильность формул А и В обозначают .

Равносильные формулы имеют одинаковые истинностные таблицы, и наоборот, если истинностные таблицы совпадают, то они равносильны.

Теорема: (признак равносильности формул). Две формулы А и В алгебры высказываний равносильны тогда и только тогда, когда формула является тавтологией.

Следствие. Отношение равносильности между формулами алгебры высказываний:

· Рефлексивно: ;

· Симметрично: если , то ;

· Транзитивно: если , то , т.е. отношение равносильности является отношением эквивалентности.

Примеры равносильных формул:

1. коммутативность конъюнкции

2. коммутативность дизъюнкции

3. ассоциативность конъюнкции

4. ассоциативность дизъюнкции

5. дистрибутивность конъюнкции

6. дистрибутивность дизъюнкции

7. свойство поглощения

8. свойство поглощения

9. отрицание конъюнкции

10. отрицание дизъюнкции

11.

12.

13. удаление эквиваленции

14.

15. идемпотентность конъюнкции

16. идемпотентность дизъюнкции

17. 18.

19. 20.

21. 22.

23.

24. склеивание

25. обобщенное склеивание

26.