Cтраница 3
Пусть Г - произвольное ( возможно, бесконечное) множество формул сигнатуры П, Б - произвольная формула сигнатуры fZ, причем Г h В. [31]
Так, выражение А гз ( В э4), где под 4 и В подразумеваются произвольные формулы исчисления высказываний, является примером А. [32]
Далее мы увидим, что не существует алгоритма, позволяющего распознать общезначимость, нейтральность или невыполнимость произвольной формулы исчисления предикатов. Это связано с существованием бесконечного числа возможных интерпретаций для формул исчисления предикатов. Может ведь потребоваться обязательное рассмотрение всех интерпретаций. Частные, но интересные результаты - в этом направлении были получены Эрбраном. Они приводят к упрощенной проверке выполнимости формул. Так как каждой формуле F можно сопоставить такую кла-узальную форму SF, что формулы F и SF одновременно выполнимы ( невыполнимы), то будем рассматривать только клаузальные формы. Представленные здесь результаты относятся к исчислению предикатов без равенства. [33]
Известно ( теорема Черча, доказательство можно прочесть в [5]), что вопрос о выводимости произвольных формул языка первого порядка неразрешим: не существует алгоритма, который бы по произвольной замкнутой формуле определял бы, выводима она или нет. В предыдущем разделе мы видели, что для формул класса Si без функциональных символов такой алгоритм существует. [34]
Вот это обобщение: пусть a: MI - М % - изоморфизм, a F - произвольная формула нашей сигнатуры. Тогда она истинна в М при оценке тг тогда и только тогда, когда она истинна в М-2 при оценке а о тт. [35]
Теорема о подстановке, иными словами, утверждает, что если в доказуемой секвенции вместо пропозициональных переменных подставить произвольные формулы, то полученная секвенция будет доказуемой. [36]
Если О - произвольная совокупность формул ( в частности - может быть и пустая) и А - произвольная формула, то О - А есть предложение. Содержательные сокращенные записи, напр, ранее доказанное для пропозицион. [37]
Аксиомы системы имеют один из видов: ( р - ( р или L - у, где ( р - произвольная формула. [38]
Последовательное применение указанных выше операций к любой формуле ( операцию отрицания реализует каждый АЭ на нулевом выходе) позволяет строить АС для произвольной формулы. [39]
В, С и D не имеют особых свойств или отношений, и пусть F будет также банальной, а в других отношениях произвольной формулой. Тогда формула ( A JB J ( C & D) / / F неинформативная и одновременно возможная и относительно возможная, в то время как ее отрицание является как информативной, так и относительно глупой формулой, но не глупой. Формула А сама по себе, как и F, является и возможной, и информативной. Для непротиворечивых интеррогативов верны следующие импликации: из неинформативный следует как возможный, так и относительно возможный, а из ( одновременно) глупый и относительно глупый следует информативный; для противоречивых интеррогативов эти импликации, однако, неверны. [40]
Однако, в то время как i-символ приложим лишь к таким формулам, для которых выведены соответствующие формулы единственности, е-символ может быть определен для произвольной формулы, содержащей свободную переменную. [41]
Заметим, что следствие 1.5.4 касается только предложений, но, чтобы доказать его на основе теоремы 1.5.3, мы применили индукцию, относящуюся к произвольным формулам. В теории моделей это встречается нередко, так как понятие предложения вводится на основе рекурсивного определения формулы. Мы рассмотрим это применение нашей теоремы как одно из упражнений. [42]
А, В, С и D не имеют особых свойств или отношений, и пусть F будет также банальной, а в других отношениях произвольной формулой. Тогда формула ( А / В) / ( C & D) J V F неинформативная и одновременно возможная и относительно возможная, в то время как ее отрицание является как информативной, так и относительно глупой формулой, но не глупой. Формула А сама по себе, как и F, является и возможной, и информативной. Для непротиворечивых интеррогативов верны следующие импликации: из неинформативный следует как возможный, так и относительно возможный, а из ( одновременно) глупый и относительно глупый следует информативный; для противоречивых интеррогативов эти импликации, однако, неверны. [43]
Формула называется элементарно регулярной в слабом смысле, если она имеет вид ЭД V 93, где 91 - примитивно истинная в слабом смысле, а S3 - произвольная формула. [44]
Мы теперь можем, исходя из преобразований эквивалентности а - d, точно таким же образом доказать, что для всякой приведенной формулы ( а следовательно, и для произвольной формулы) существует эквивалентная ей нормальная формула. Доказательство при этом может быть взято из главы III. Хотя мы там и не ставили себе задачи ограничиваться конструктивными средствами, тем не менее фактически доказательство было конструктивным. [45]