Образовательные процессы и ресурсы высшей школы в области радиоэлектроники. Лидия Коловская

Чтение книги онлайн.

СКАЧАТЬ разрешимость. Эти регулятивы определенным образом оцениваются, и в этой связи вырабатываются идеалы логического знания. Обратимся в этой связи к логике предикатов первого порядка, основной теории современной логики. В первопорядковой логике имеется лишь один тип квантифицируемых переменных – индивидуальные переменные. В логике предикатов второго порядка переменные пробегают по признакам индивидов. В логике предикатов третьего порядка переменные пробегают по признакам признаков.

      Метатеоремы логики предикатов имеет смысл разделить на два класса – «положительные» (или неограничительные) и «отрицательные» (или ограничительные). Чаще других среди «положительных» метатеорем логики предикатов называются следующие.

      Для логики предикатов существует независимость некоторого множества аксиом (теорема Дж. Маккинси).

      Классическое исчисление предикатов первого порядка семантически непротиворечиво, то есть каждая его формула универсально общезначима.

      Исчисление предикатов также синтаксически непротиворечиво, то есть нет такой формулы А, что доказуемо и А, и не – А.

      Всякая общезначимая формула доказуема (теорема о полноте К. Гёделя).

      Но наряду с «положительными» существует также целый ряд ограничительных теорем первопорядковой логики предикатов.

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

      Далеко не очевидно содержание теоремы К. Гёделя о неполноте. Если все формулы теории Т общезначимы, то она неполна, то есть существует такая формула А, что ни А, ни не – А не доказуемы в Т.

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

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

      Теорема А. Чёрча: не существует алгоритма, позволяющего для произвольной формулы логики предикатов решить вопрос, является ли она доказуемой в данной теории.

      Наличие как ограничительных, так и не ограничительных теорем логики предикатов резко усложняет вопрос с оценкой ее статуса. На первый взгляд, кажется, что ограничительные теоремы являются «плохими», а не ограничительные «хорошими». Такое мнение поверхностное. Во-первых, мы вообще не в состоянии правильно оценить статус логики предикатов без указания ее ограничительных теорем. Во-вторых, ограничительные теоремы не лишены явных достоинств. Так, в прикладной логике очень часто используется неполнота синтаксиса первопорядковой логики: к логическим аксиомам присоединяются нелогические постулаты, не нарушающие синтаксическую непротиворечивость теории. Наличие неполноты синтаксиса логики СКАЧАТЬ