Отношение эквивалентности

Определим эквивалентность формул в исчислении высказываний.

Определение 1. Формулы U и B называются эквивалентными, что обозначается ú- , если

ú- (1)

Рассмотрим некоторые простые свойства отношения эквивалентности.

1. Рефлексивность: ú- .

2. Симметричность: если ú- , то ú- .

3. Транзитивность: если ú- и ú- , то ú- .

Задание 1. Доказать свойство симметричности отношения эквивалентности.

Решение.

1. ú-

2. ú-

3. ú-

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

В исчислении высказываний имеют место следующие эквивалентности, которые соответствуют аналогичным свойствам отношения эквивалентности алгебры высказываний.

1. ú- .

2. ú-

3. ú-

4. ú-

5. ú-

6. ú-

7. ú-

8. ú-

9. ú-

10. ú-

11. ú-

12. ú-

Для того чтобы доказать эквивалентность ú- в исчислении высказываний достаточно построить выводы ú- и ú- . Покажем, что если ú- и ú- , то ú- .

1. ú-	по условию
2. ú-	по условию
3. ú-	5 (1)
4. ú-	5 (2)
5. , ú-
6. ú-	4 (3, 4, 5)

Последняя формула, в силу определения, означает ú- .

Теорема эквивалентности. Если и - формулы, полученные заменой некоторых (одних и тех же) вхождений какой-либо высказывательной переменной в формуле U соответственно формулами и , то

ú- .

Следствие. Если есть некоторая подформула формулы U и эквивалентна формуле , то формула, полученная заменой в формуле U на , эквивалентна U. Иными словами, если , то .

Свойства 2, 4, 10 и теорема эквивалентности позволяют формулу, составленную из высказывательных переменных лишь с помощью операции дизъюнкции, преобразовать к виду

.

Аналогично формула, составленная из с помощью операции конъюнкции эквивалентна формуле

.

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

Теорема 3.1. Для каждой формулы исчисления высказываний существуют эквивалентные ей дизъюнктивная и конъюнктивная нормальные формы.

Варианты заданий.

1. Доказать свойство рефлексивности отношения эквивалентности.

2. Доказать свойство транзитивности отношения эквивалентности.

3. Доказать, что если ú- и ú- , то ú- .

4. Доказать, что если ú- , то ú- и ú- .

5. Доказать, что если ú- , то ú- и ú- .

6. Доказать, что если ú- и ú- , то ú- .

Доказать эквивалентность формул в исчислении высказываний (7 – 21).

7. ú-

8. ú-

9. ú-

10. ú-

11. ú- ~

12. ú-

13. ú-

14. ú- ~

15. ú-

16. ú-

17. ú- ((P Ù (P Ú Q)) Ù (R Ú Q)) ~ ((P Ù R) Ú (P Ù Q))

18. ú- ((P Ú Q) Ù (P Ú Ø Q)) ~ P

19. ú- ((P Ù Q) Ú (P Ù Ø Q)) ~ P

20. ú- ~ (P Ú Q)

21. ú-

22. Доказать, что если Т ú- U ® B и Т ú- P ® Q, то

a) Т ú- (U Ù P) ® (B Ù Q)

b) Т ú- (U Ú P) ® (B Ú Q)

c) Т ú- (В ® P) ® (U ® Q)

Дата добавления: 2015-06-27