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

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

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

|- (1)

Cвойства отношения эквивалентности:

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

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

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

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

Решение.

1. |-

2. |-

3. |-

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

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

1. |-.

2. |-

3. |-

4. |-

5. |-

6. |-

7. |-

8. |-

9. |-

10. |-

11. |-

12. |-

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

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

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

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

|-.

Дата добавления: 2014-01-11