Cтраница 1
Бескванторная формула выводима ( общезначима) тогда и только тогда, когда ее прототип является тавтологией. [1]
Бескванторная формула Ф доказуема в исчислении G тогда и только тогда, когда ее пропозициональная форма ФР доказуема в исчислении высказываний. [2]
Справа стоит бескванторная формула. [3]
Доказать, что бескванторная формула истинна тогда и только тогда, когда она может быть получена подстановкой из некоторой тождественно истинной формулы исчисления высказываний. [4]
Заменим вхождения кванторов существования описанной формы вхождениями подходящих коэкстенсивных бескванторных формул. [5]
Показать, что результат применения квантора к бескванторной формуле с индивидуальными одноместными предикатами может быть записан через те же предикаты в бескванторной форме. Дальнейшее доказательство проводится по индукции. [6]
S - функция прибавления единицы) эквивалентна некоторой бескванторной формуле. Как говорят, ( Z, , S) допускает элиминацию кванторов. [7]
Покажем обратное, пусть на некоторой алгебре Л, у-зави-симая бескванторная формула ( х, у) является у-функциональ-ной. [8]
В некоторых случаях рассуждение упрощается, если использовать приведение бескванторной формулы к дизъюнктивной нормальной форме. [9]
Всякая формула в ( Q, , ) эквивалентна некоторой бескванторной формуле. [10]
BxJV ( x z) - эрбранова форма Ф, где Т - бескванторная формула. [11]
А теперь процедура последовательного внесения истинностных значений, распределенных по элементарным формулам какой-либо собственной бескванторной формулы § с номером т - если это распределение характеризуется числом п - может быть представлена следующим образом. Обозначим эту формулу посредством gb и пусть тх - ее номер. [12]
Тем не менее класс выразимых предикатов весьма ограничен: это предикаты, выразимые бескванторными формулами. Будем называть две формулы ( рассматриваемой нами сигнатуры) эквивалентными ( в данной интерпретации), если они выражают один и тот же предикат, то есть истинны при одних и тех же значениях переменных. [13]
Для всякой формулы сигнатуры (, , 0 1, , х) существует бескванторная формула, задающая тот же предикат на множестве действительных чисел. [14]
Конструктивность нумерованной модели ( ЗИ, v), очевидно, равносильна разрешимости множества бескванторных формул из ТЬ1 ( ЗЯ, v), так что всякая сильно конструктивная модель является конструктивной. [15]