Cтраница 1
Аксиомы исчисления предикатов, выраженные в виде схем. [1]
Аксиомам исчисления предикатов соответствуют выводимые формулы исчисления высказываний. [2]
Все аксиомы исчисления предикатов и все правил вывода, кроме правила подстановки в свободные пред. [3]
Регулярность второй аксиомы исчисления предикатов устанавливается таким же способом. [4]
Так как аксиомам исчисления предикатов соответствуют выводимые форм уш исчисления высказываний, то отсюда следует, что всякой выводимой формуле не-числения предикатов соответствует выводимая формула исчисления высказываний. [5]
Допустим теперь, что формула ( 5) присоединена к аксиомам исчисления предикатов. [6]
Для всех г от 1 до п проверяем, верно ли, что Ai - аксиома исчисления предикатов, или Ai Е В. [7]
Однако можно дать и вполне строгое доказательство того, что формула ( 1) не может быть формально выведена из аксиом исчисления предикатов. Мы не будем приводить этого доказательства подробно, а ограничимся тем, что изложим основную идею. [8]
Говорят, что замкнутая формула ( р выводима в теории Т ( является теоремой теории Т), если формула ( f получается из аксиом исчисления предикатов и формул теории Т по правилам вывода. [9]
Как и в исчислении высказываний, в исчислении предикатов также предполагается, что в множестве всех формул Ф с заданным Ф выделен определенный набор, состоящий из аксиом исчисления предикатов первой ступени, и указаны правила вывода, позволяющие из аксиом выводить некоторые другие формулы. Соответствующие списки мы здесь не приводим - их можно найти в любом учебнике математической логики. Все аксиомы являются тавтологиями, и все, что выводится из аксиом, - это также тавтологии. Теорема полноты набора аксиом исчисления предикатов утверждает, что из аксиом выводятся все тавтологии. [10]
Из сказанного ясно, что в исчислении предикатов - йельзя вывести никакое сколько-нибудь содержательное. Однако если к аксиомам исчисления предикатов присоединить какие-либо невыводимые формулы в качестве новых аксиом ( сохраняя те же правила вывог да), то получится другое исчисление, в котором выводимы, помимо тождественно истинных формул, и другие формулы. [11]
В противоположность содержательной полноте, называемой также полнотой в широком смысле, полнота в узком смысле уже не имеет места в исчислении предикатов. Действительно, к числу аксиом исчисления предикатов может быть присоединена формула ЗхР ( х) Э VxP ( x), невыводимая в этом исчислении и не приводящая к возникновению противоречия. Непротиворечивость возникающей в результате указанного присоединения системы аксиом становится ясной при рассмотрении предметной области, состоящей из единственного объекта. Вновь присоединенная аксиома обращается при этом в тождественно истинную формулу. В то же время для предметной области, состоящей уже из двух объектов х и у, указанная аксиома превращается в формулу Р ( х) V Р ( у) Р ( х) Л Р ( у) не являющуюся тождественно истинной и потому не выводимую из остальных аксиом. [12]
Однако из теоремы 1 легко следует, что все выводимые в ограниченной арифметике формулы регулярны. Рассмотрим сперва общелогические аксиомы, Они состоят из аксиом исчисления высказывании и двух аксиом исчисления предикатов. [13]
Существенное продвижение в этом направлении предпринял Грин [11], продемонстрировавший в качестве генератора планов законченную систему доказательства теорем методом резолюции. Согласно этому подходу, начальная ситуация, целевая ситуация и результаты применения имеющихся операторов описываются в виде множества аксиом исчисления предикатов первого порядка. Далее с помощью принципа резолюции доказывается предположение, что существует ситуация, удовлетворяющая описанию цели. Побочным результатом успешно проведенного доказательства является план последовательного преобразования начальной ситуации в целевую. [14]
Условимся считать некоторые определенные формулы, заданные в конеч -; ном числе, выводимыми и будем их называть аксиомами исчисления предикатов. Затем укажем правила образования новых выводимых формул из тех, которые: уже получены, или же из аксиом. [15]