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

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

Определение 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. Для Отношение эквивалентности в ИВ каждой формулы исчисления выражений есть эквивалентные ей дизъюнктивная и конъюнктивная обычные формы.

Исчисление секвенций ИС

Исчисление выражений генценовского типа именуется исчислением секвенций ИС.

Алфавит ИС состоит из знаков алфавита ИВ, дополненных эмблемой |-. Допустимые последовательности знаков – формулы определяются также как и в ИВ, не считая того, в ИС вводится понятие секвенция.

Пусть Отношение эквивалентности в ИВ U1, U2, . . . ,Un, V – формулы ИС. Секвенциями именуются конечные последовательности последующих 2-ух видов:

1) U1, U2, . . . ,Un |- V (из истинности U1, U2, . . . ,Un следует истинность V);

2) U1, U2, . . . ,Un |- (система формул U1, U2, . . . ,Un противоречива).

Огромное количество аксиом ИС определяется единственной схемой секвенций U |- U. Правила вывода ИС определяются последующими записями, где T, T1 – конечное огромное количество формул (может быть пустое).

1. (введение Ù).

2. (удаление Ù).

3. (удаление Отношение эквивалентности в ИВ Ù).

4. (введение Ú).

5. (введение Ú).

6. (удаление Ú либо правило разбора 2-ух случаев).

7. (введение ®).

8. (удаление ®).

9. (удаление Ø либо подтверждение от неприятного).

10. (выведение противоречия).

11. (перестановка посылок).

12. (уточнение либо правило излишней посылки).

Исчисления ИВ и ИС эквивалентны.


otnosheniya-sredstv-massovoj-informacii-s-grazhdanami-i-organizaciyami.html
otnosheniya-v-diagrammah-klassov.html
otnosheniya-v-seme-referat.html