Т. А. Сливина математическая логика и теория алгоритмов

§ 6. Замечание об аксиоматическом исчислении предикатов

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

1. 
   Определение формулы исчисления предикатов совпадает с определением формулы логики предикатов, которое вводилось нами ранее.
   
2. 
   Выбор системы аксиом исчисления предикатов, как и в случае исчисления высказываний, может осуществляться по-разному. Одной из таких систем аксиом может быть система, в которую включены одиннадцать аксиом исчисления высказываний, использованные нами, и две дополнительные аксиомы:
   

;
;
где t не содержит переменной х.
3. К правилам вывода, которые использовались в исчислении высказываний, добавляются еще два правила:
а) Правило введения квантора общности
;
б) Правило введения квантора существования
;
если F не зависит от х.
4. Понятие вывода и доказуемой формулы определяются аналогично этим понятиям в исчислении высказываний.
5. Как и во всякой аксиоматической теории, рассматриваются проблемы:
а) разрешимости,
б) непротиворечивости,
в) полноты,
г) независимости.


Задачи и упражнения

1. Даны предикаты Р(х): «х² – 9 = 0» и Q(х): «5х – 3 = 18». Найти области истинности этих предикатов, если их область определения есть: 1) R; 2) N.

2. Изобразите на диаграммах Эйлера-Венна области истинности предикатов:
а) ;
б) .
3. Показать, что кванторы общности и существования не перестановочны, то есть высказывания и могут иметь различные значения.
4. Доказать равносильности:
а) ;
б) ;
в) .
5. Доказать, что формулы и не равносильны.


Глава 4