Математическая логика и теория алгоритмов. Стенюшкина В.А. - 39 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

14 Свойства исчисления предикатов
14.1 Теорема Геделя о полноте исчисления предикатов
Имеют место следующие метатеоремы.
Теорема 14.1 Всякая теорема классического исчисления предикатов пер-
вого порядка есть тавтология.
Теорема 14.2 Всякая тавтология является теоремой классического исчис-
ления предикатов первого порядка.
Вторая из этих теорем доказана К. Геделем (1930) и является утвержде-
нием о полноте классического исчисления предикатов первого порядка.
14.2 Непротиворечивость
Теория К непротиворечива. Доказательство следует из теоремы 14.1 и
аналогично доказательству о теории L.
14.3 Проблема разрешения в логике предикатов
Исчисление предикатов непротиворечиво, полно, но не разрешимо. Про-
цедура вычисления истинностного значения предикатных формул в общем слу-
чае может оказаться бесконечной из-за бесконечности предметной области.
14.4 Исчисление предикатов первого порядка
Исчисление предикатов, в котором кванторы могут связывать только
предметные переменные, но не могут связывать предикаты или функторы, на-
зывается исчислением первого порядка. Исчисления, в которых кванторы могут
связывать не только предметные переменные, но и предикаты, функторы или
иные множества объектов называются исчислениями высших порядков. 
      14 Свойства исчисления предикатов

      14.1 Теорема Геделя о полноте исчисления предикатов

      Имеют место следующие метатеоремы.
      Теорема 14.1 Всякая теорема классического исчисления предикатов пер-
вого порядка есть тавтология.
      Теорема 14.2 Всякая тавтология является теоремой классического исчис-
ления предикатов первого порядка.
      Вторая из этих теорем доказана К. Геделем (1930) и является утвержде-
нием о полноте классического исчисления предикатов первого порядка.

      14.2 Непротиворечивость

     Теория К непротиворечива. Доказательство следует из теоремы 14.1 и
аналогично доказательству о теории L.

      14.3 Проблема разрешения в логике предикатов

      Исчисление предикатов непротиворечиво, полно, но не разрешимо. Про-
цедура вычисления истинностного значения предикатных формул в общем слу-
чае может оказаться бесконечной из-за бесконечности предметной области.

      14.4 Исчисление предикатов первого порядка

     Исчисление предикатов, в котором кванторы могут связывать только
предметные переменные, но не могут связывать предикаты или функторы, на-
зывается исчислением первого порядка. Исчисления, в которых кванторы могут
связывать не только предметные переменные, но и предикаты, функторы или
иные множества объектов называются исчислениями высших порядков.

Страницы