Cтраница 3
Чтобы показать от противного, что класс F0 непротиворечив, допустим, что для, некоторой А обе формулы А и - i А выводимы в исчислении высказываний ( при употреблении предикатных формул с цифрами) из формул Fn. [31]
В силу § § 37, 72, 73, 75, доказуемость в исчислении предикатов с равенством равносильна тождественности в каждой непустой области; следовательно, не существует разрешающей процедуры для распознавания тождественности предикатной формулы с равенством. [32]
Так как предикат Г2 ( и, 6, х, у) примитивно-рекурсивен, то, по следствию из теоремы I § 49, он является арифметическим по Геделю ( § 48), а значит можно ( заменяя, и их представляющими предикатами) найти предикатную формулу Т2 ( а, Ь, х, у) из, Р0, Р1 ( Р2, которая выражает этот предикат при рассматриваемом распределении значений. [33]
Если для любой интерпретации / предикат 1 ( Щ является тождественно истинным, то формула 91 наз. Каждая общезначимая предикатная формула выражает логич. Согласно Геделя теореме о полноте, все общезначимые предикатные формулы и только они выводимы в классич. [34]
F выполнима ( в теоретико-множественном смысле) в некоторой непустой области. Рассмотрение предикатной формулы в качестве системы аксиом представляет интерес только для выполнимых, но не тождественных предикатных формул. Тождественная предикатная формула не ограничивает и не описывает индивидуумы и предикаты, которые выражаются ее свободными переменными и предикатными буквами, а Выражает закон логики, применимый ко всякому выбору этих индивидуумов и предикатов в любой непустой области. [35]
Сколемовская теоретико-доказательственная ( теоретико-выполнительная) нормальная форма-это предваренная формула ( теорема 19 § 35), в которой все кванторы существования ( общности) стоят вначале. Для любой данной предикатной формулы G можно эффективно указать предикатную формулу М ( N) этого вида, такую, что М доказуема в исчислении предикатов ( N выполнима в данной области) тогда и только тогда, когда это справедливо для G. [36]
Ps аксиоматической теории определены лишь постольку, поскольку они охарактеризованы аксиомами. Каждую предикатную формулу можно рассматривать как систему аксиом и считать, что входящие в нее свободные переменные и предикатные буквы представляют неопределенные индивидуумы и предикаты. [37]
Пусть S - предикатная формула, выводимая с помощью аксиом равенства. Тогда S выводима и в исчислении предикатов ( Гильберт и Бернайс [ 1934, стр. [38]
Но тогда в этой формуле можно исключить все знаки импликации ( заменяя А Э В через - А V В) и привести ее после этого к дизъюнктивной нормальной форме. Подобное преобразование приводит исходную предикатную формулу к некоторой эквивалентной ей предикатной формуле. В ряде случаев в понятие нормальной формы предикатной формулы включается не только условие предварения кванторов, но и обязательное приведение ее бескванторной части к совершенной дизъюнктивной нормальной форме. [39]
Формула Щ в ы-водима в П.и., или является теоремой, если можно построить вывод этой формулы. Согласно Геделя теореме о полноте, все общезначимые предикатные формулы и только они выводимы в классич. [40]
Эта задача может быть сведена к решению более простых подзадач, когда траектория Т представляется единственной вершиной, описывающей определенную область в пространстве состояний. В общем случае такое описание может иметь вид предикатной формулы G ( x), где х - набор определенных предметных переменных. [41]
Это обстоятельство представляет собой простое следствие того факта, что для установления выполнимости или невыполнимости формулы, содержащей п одноместных предикатов, достаточно ограничиться рассмотрением предметных областей, состоящих не более чем из 2 объектов. В результате проверка выполнимости ( или тождественной истинности) предикатной формулы сводится ( после замены кванторов дизъюнкциями и конъюнкциями) к проверке выполнимости ( или, соответственно, тождественной истинности) соответствующей формулы исчисления высказываний. [42]
Сколемовская теоретико-доказательственная ( теоретико-выполнительная) нормальная форма-это предваренная формула ( теорема 19 § 35), в которой все кванторы существования ( общности) стоят вначале. Для любой данной предикатной формулы G можно эффективно указать предикатную формулу М ( N) этого вида, такую, что М доказуема в исчислении предикатов ( N выполнима в данной области) тогда и только тогда, когда это справедливо для G. [43]
Но тогда в этой формуле можно исключить все знаки импликации ( заменяя А Э В через - А V В) и привести ее после этого к дизъюнктивной нормальной форме. Подобное преобразование приводит исходную предикатную формулу к некоторой эквивалентной ей предикатной формуле. В ряде случаев в понятие нормальной формы предикатной формулы включается не только условие предварения кванторов, но и обязательное приведение ее бескванторной части к совершенной дизъюнктивной нормальной форме. [44]
Отметим еще, что если для обозначения формул в предикатной формуле пользоваться кодами из 5, то есть возможность определить порядок применения формул по адресу. Если предикатная функция Р тождественно равна 1, то в соответствующей предикатной формуле второй индекс опускается. [45]