Cтраница 2
Как и в случае исчисления высказываний, при построении исчисления предикатов недостаточно указать лишь способ записи формул. Необходимо задать еще правила преобразования формул, выражаемые аксиомами. В число аксиом исчисления предикатов включаются все 11 аксиом исчисления высказываний, выписанные в § 5 гл. [16]
Первые четыре группы аксиом представляют собой не что иное, как аксиомы исчисления высказываний ( см. стр. К ним добавляются еще две новые аксиомы, составляющие группу V. Этим и исчерпывается система аксиом исчисления предикатов. [17]
Поставим вопрос о соотношении между понятием выводимой формулы описанного исчисления и рассмотренным в главе III содержательным понятием тождественно истинной формулы. Нетрудно видеть, что каждая выводимая формула исчисления предикатов является в то же время и тождественно истинной в наивном теоретико-множественном смысле. Во-первых, очевидно, что аксиомы исчисления предикатов тождественно истинны. Во-вторых, применение правил вывода исчисления предикатов к тождественно истинным формулам приводит к тождественно истинным формулам. Это очевидно для правила заключения. Для правил переименования свободных и связанных переменных это также очевидно. [18]
В приложениях часто бывает важно, чтобы в схеме языка исчисления предикатов присутствовал знак равенства. Предикат равенства можно вводить в систему символов отношений Ф и одновременно в аксиомы исчисления предикатов добавляются аксиомы равенства. Равенство можно определить и для произвольных алгебр Халмоша, и делается это следующим образом. [19]
Схема доказательства непротиворечивости состоит в следующем. При такой интерпретации все формулы исчисления предикатов заменяются формулами исчисления высказываний. При этом все аксиомы исчисления предикатов будут выводимыми формулами исчисления высказываний, а правила исчисления предикатов преобразуются в правила исчисления высказываний, основные или выводимые. Если бы в исчислении предикатов была доказуема формула, являющаяся буквой А то в преобразованной системе она также была бы доказуема. Но тогда преобразованная система была бы противоречива. Но преобразованная система является исчислением высказываний, которое, как известно ( см. § 9 главы II), непротиворечиво. [20]
Как и в исчислении высказываний, в исчислении предикатов также предполагается, что в множестве всех формул Ф с заданным Ф выделен определенный набор, состоящий из аксиом исчисления предикатов первой ступени, и указаны правила вывода, позволяющие из аксиом выводить некоторые другие формулы. Соответствующие списки мы здесь не приводим - их можно найти в любом учебнике математической логики. Все аксиомы являются тавтологиями, и все, что выводится из аксиом, - это также тавтологии. Теорема полноты набора аксиом исчисления предикатов утверждает, что из аксиом выводятся все тавтологии. [21]
Если 91 и 33 эквивалентны в исчислении предикатов, то они и дедуктивно эквивалентны. Это значит, что формула % - 33 выводима в исчислении предикатов. В таком случае формула Щ - 33 также выводима. Если мы присоединим к аксиомам исчисления предикатов формулу Я, то из формул 91 и 91 - 33, применив правило заключения, можно вывести формулу S. Отсюда следует что эквивалентные формулы 51 и 33 являются также дедуктивно эквивалентными. [22]
Если две формулы дедуктивно эквивалентны, то из того, что одна из них тождественно истинна, следует, что и другая также тождественно истинна. В самом деле, пусть 91 и 23 - дедуктивно эквивалентные формулы и 91 - тождественно истинная формула. Как мы видели, все формулы, выводимые из тождественно истинных формул, также являются тождественно истинными формулами. В силу дедуктивной эквивалентности 23 выводима из аксиом исчисления предикатов и формулы 91; поэтому 23 также является тождественно истинной формулой. Кроме того, если 91 и 23 дедуктивно эквивалентны и 91 - выводимая в исчислении предикатов формула, то 23 также выводима в исчислении предикатов. Последнее вытекает из определения дедуктивной эквивалентности. [23]