Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
7. КОРРЕКТНОСТЬ АКСИОМАТИЧЕСКОГО ИСЧИСЛЕНИЯ.
(Знаки |– «выводимо» и |= «истинно при» изображайте линии слитно).
(вода): Допустим, мы хотим механически, не задаваясь вопросами о семантике, получать результаты об общезначимости формул. Таким механическим способом мог бы стать вывод в некотором исчислении, но при условии, что любая выводимая формула является общезначимой. Поэтому к любому исчислению, предназначенному для получения общезначимых формул, предъявляется естественное требование корректности: любая выводимая в этом исчислении формула должна быть общезначимой.
Тогда можно сказать: Исчисление корректно относительно некоторой семантики тогда и только тогда, когда всякая его теорема является семантически общезначимой формулировкой.
Теорема: Для всякой формулы А верно: |– A ⇔ |= A (Всякая выводимая формула общезначима).
Доказательство:
Пусть для произвольной формулы Логики Предикатов А верно |– А. По определениям вывода и выводимой формулы АИП формула А является теоремой тогда, когда существует вывод, заканчивающийся формулой А. Всякая формула этого вывода есть либо аксиома, либо получена из вышестоящих формул по правилам вывода. Если мы установим, что все аксиомы являются общезначимыми формулами л.п., а все правила вывода сохраняют общезначимость (т.е. при наличии общезначимой формулы в качестве посылки всегда выдают общезначимую формулу в качестве заключения), то мы установим, что всякая формула любого доказательства общезначима, а значит, общезначима и любая теорема.
С этим док-вом мы рассматриваем случаи 1, 2, 3
Случай 1. Аксиомы ИВ. Известно, что аксиомы АВ – тавтологии, а потому они общезначимы.
Случай 2. Кванторные аксиомы. Допускаем, что формула <какая-нибудь> (см. билет 3) не общезначима. Действуем по определению истинности и в итоге получаем противоречие, опровергающее существование модели М и означивания v таких, что формула <какая-нибудь> не общезначима.
Случай 3. Правила вывода. Доказывается аналогично случаю 2.
В общем, Каждый раз мы допускаем, что формула не является общезначимой и на выходе получаем противоречие.