Cтраница 1
Формулы исчисления предикатов строятся из свободных и связанных индивидных переменных, формульных переменных с аргументами и без них1), а также из символов исчисления высказываний и кванторов всеобщности и существования. [1]
Формула исчисления предикатов, не содержащая вхождений индивидных переменных, называется формулой исчисления высказываний. Тождественно истинные, или, как мы иногда для краткости говорим, тождественные формулы исчисления высказываний, среди прочих формул характеризуются при помощи следующей процедуры вычисления их значений. [2]
Формула исчисления предикатов, которая не содержит кванторов, может быть в известном смысле рассмотрена как формула исчисления высказываний и как формула алгебры высказываний. [3]
Формулы исчисления предикатов представляются словами подобно формулам пропозиционального исчисления. [4]
Каждая формула исчисления предикатов представляет собой некоторую конечную последовательность символов этого исчисления. [5]
Если формула исчисления предикатов выполнима на какой-либо бесконечной предметной области, то она выполнима также и на счетной предметной области. [6]
Однако формулы исчисления предикатов состоят не только из подформул, но также и из термов. Следовательно, необходимо будет интерпретировать также термы. Терм интуитивно означает объект. Таким образом, интерпретация должна специфицировать множество объектов, называемое областью интерпретации. [7]
Определение формулы исчисления предикатов имеет тот же индуктивный характер, как и определение формулы исчисления высказываний. Оно может быть высказано следующим образом. [8]
Для всякой формулы исчисления предикатов существует дедуктивно эквивалентная ей нормальная формула Сколема. [9]
Если некоторая формула исчисления предикатов содержит свободные переменные, то ее называют открытой формулой. Формулы, не содержащие свободных переменных, принято называть замкнутыми. Любая формула 23 оказывается дедуктивно эквивалентной своему замыканию sP, и потому эти две формулы являются либо одновременно тождественно истинными, либо одновременно не тождественно истинными. [10]
Процедура приведения формул исчисления предикатов к минисферному виду часто оказывается достаточно простой. [11]
Пусть 91 - формула исчисления предикатов, не со-держащая кванторов. Допустим, что эта формула, рассмотренная как формула алгебры высказываний, является выполнимой. Это значит, что при некоторых значениях переменных высказываний она принимает значение И. Тогда можно так заменить переменные выска зывания и переменные предикаты значениями И и Л, соблюдая условие, что одинаковые высказывания и предикаты заменяются одинаковым образом, что получится формула, принимающая значение И. [12]
Теорема 1.11. Произвольная совокупность формул исчисления предикатов выполнима тогда и только тогда, когда все ее конечные подмножества выполнимы. [13]
Назовем не содержащую кванторов формулу исчисления предикатов правильной, если при любых заменах свободных переменных числами 1 и 2 она является выводимой формулой исчисления высказываний. Докажем, что для каждой выводимой формулы ЭД исчисления предикатов поставленная ей в соответствие формула И является выводимой формулой исчисления высказываний. [14]
Поставим в соответствие каждой формуле исчисления предикатов формулу 51 по следующему закону: переменному высказыванию ставим в соответствие это же переменное высказывание. [15]