Cтраница 1
Выводимость формулы ( р из 0 ( h p) равносильна тому, что ( f - теорема ИВ. [1]
В отношении выводимости формул описанное этими правилами ограниченное исчисление предикатовг) - в силу ранее проведенного нами рассуждения, связанного с теоремой Эрбрана, - равносильно обычному исчислению предикатов. Но эта равносильность не распространяется на выводы формул из других формул. [2]
Аналогичным образом из выводимости формулы f - ф следует выводимость формулы 3 у. [3]
В некоторых интеллектуальных задачах факт выводимости заданной формулы В ( трактуемой как задание или вопрос) из системы формул At f ( трактуемых как аксиоматическое описание знаний и накопленного опыта) оказывается недостаточным. Примером может служить задача планирования поведения робота. Иными словами, нужно выяснить, следует ли логически формула дсо б ( со) из заданной системы аксиом и, если следует, то при каком значении переменной со т это достигается. [4]
Ьц, откуда по производному правилу следует выводимость формулы А - В. [5]
Аналогичным образом из выводимости формулы f - ф следует выводимость формулы 3 у. [6]
Точно так же, как и в PL, символ h обозначает выводимость формул в аксиоматической системе. [7]
Этот несколько неудачный термин исторически впервые появился в связи с проблемой распознавания выводимости формул в классическом исчислении предикатов. [8]
Если сигнатура не содержит функциональных символов, то теорема Эрбрана позволяет алгоритмически проверить выводимость формул класса EI, поскольку число возможных подстановок конечно. Это же можно сказать и про формулы класса Щ, так как внешние кванторы всеобщности можно отбросить, не меняя выводимости. [9]
Если мы примем во внимание, что во всех утверждениях 1 - 4 речь идет о выводимости формул без формульных переменных, то у нас получится еще один результат, касающийся сферы действия этих утверждений. В самом деле, замену общей аксиомы равенства ( J2) соответствующими специальными аксиомами при переходе от системы ( Z) к системе ( Z) мы с самого начала произвели с учетом того, что при исследовании вопроса о непротиворечивости эта замена не накладывает на результат никаких ограничений, так как по отношению к выводимости формул без формульных переменных общие аксиомы равенства равносильны этим специальным. [10]
Этой формализации можно будет придать несколько более элементарный вид, если мы удовлетворимся тем, что вместо выводимости формулы Ind ( А ( х), п) с формульной переменной А ( с) получим только выводимость формулы lndx ( % ( x), п) для каждой отдельно взятой формулы 91 ( с), не содержащей формульных переменных. [11]
При этом предполагается, что имеется некоторое хорошее описание предметной области, позволяющее сводить проблему истинности предложений к подходящей проблеме выводимости формул в чистом исчислении предикатов. [12]
Этой формализации можно будет придать несколько более элементарный вид, если мы удовлетворимся тем, что вместо выводимости формулы Ind ( А ( х), п) с формульной переменной А ( с) получим только выводимость формулы lndx ( % ( x), п) для каждой отдельно взятой формулы 91 ( с), не содержащей формульных переменных. [13]
Если мы теперь еще заметим, что, согласно предположению ах), для любой цифры I выводима либо формула 23 ( 1, q), которая является нумерической, либо ее отрицание 1 33 ( I, q) и что одновременно с выводимостью формулы 33 ( 1, q) имеет место отношение 93 ( 1, q), а одновременно с выводимостью формулы 133 ( 1, q) имеет место отношение 1 33 ( I, q), то получим следующий результат: если формализм F непротиворечив, то для любой цифры имеет место отношение 133 ( 1, q) и формула 133 ( 1, q) выводима в F, между тем как формула 133 ( m, q) в F невыводима. То, что отношение 133 ( 1, q) имеет место для любой цифры I, означает, что формула 193 ( m, q) верифицируема. Будучи рекурсивной, эта формула переводима в некоторое равенство f ( m) 0, где f - рекурсивно введенный функциональный знак с одним аргументом. [14]
Если мы теперь еще заметим, что, согласно предположению ах), для любой цифры I выводима либо формула 23 ( 1, q), которая является нумерической, либо ее отрицание 1 33 ( I, q) и что одновременно с выводимостью формулы 33 ( 1, q) имеет место отношение 93 ( 1, q), а одновременно с выводимостью формулы 133 ( 1, q) имеет место отношение 1 33 ( I, q), то получим следующий результат: если формализм F непротиворечив, то для любой цифры имеет место отношение 133 ( 1, q) и формула 133 ( 1, q) выводима в F, между тем как формула 133 ( m, q) в F невыводима. То, что отношение 133 ( 1, q) имеет место для любой цифры I, означает, что формула 193 ( m, q) верифицируема. Будучи рекурсивной, эта формула переводима в некоторое равенство f ( m) 0, где f - рекурсивно введенный функциональный знак с одним аргументом. [15]