Cтраница 2
Доказательство аналогично, если G является конъюнкцией или другой булевой комбинацией более простых предложений или получается навешиванием фиктивных кванторов на более простое предложение. [16]
Если класс 6 замкнут относительно операции ограниченного минимума и подстановки, то класс отношений класса 6 замкнут относительно операции навешивания ограниченного квантора существования. [17]
Переменная, к которой был применен квантор, стала связанной, а другая переменная осталась свободной; благодаря этому после навешивания квантора на одну из переменных двухместный предикат р ( х, у) преобразуется в одноместный, зависящий только от свободной переменной. [18]
Также можно доказать, что если класс 6 замкнут относительно операций исчисления высказываний, то класс 6 замкнут относительно операции навешивания ограниченного квантора общности. [19]
Теперь легко видеть, что класс § замкнут относительно двух операций максимума, поскольку они определяются посредством операций ограниченного минимума и навешивания ограниченных кванторов. [20]
В выражениях ( 1), ( 2), ( 3), ( 4) буква х является связанной переменной: навешивание квантора связывает переменную. [21]
V Gn, где каждая формула d является конъюнкцией атомарных формул, результатов навешивания кванторов на булеву комбинацию атомарных формул, отрицания атомарных формул и описанных результатов навешивания кванторов. [22]
Чтобы доказать справедливость этой формулы для всех функций высказывания рассматриваемого типа, достаточно показать, что она справедлива для функции высказывания, полученной из Ф с помощью навешивания квантора общности. [23]
Пусть, наконец, Я есть ( п - Н) - местное отношение; тогда говорят, что ( п - Н) - местное отношение S получено из Я навешиванием ограниченного квантора общности2, если ( для любых р, j) Sp j имеет место тогда и только тогда, когда Vi j Rp, i. Если R Рекурсивно и S получается из Я навешиванием ограниченного квантора общности, то S Рекурсивно. [24]
Назовем формулу хорноеской, если она получается из формул вида - 1 Д ( А В), В, где А - конъюнкция атомных формул, а В - атомная формула, при помощи операций конъюнкции и навешивания кванторов. Доказать, что хорновские формулы условно фильтруются по любому фильтру. [25]
Таким образом, чтобы завершить описание процедуры по замене формулы F формулой G, мы должны лишь показать, как найти бескванторную формулу, обладающую тем свойством, что () она коэкстенсивна с данной формулой, полученной навешиванием квантора существования ( по х) из непустой конъюнкции, содержащей не более одного нижнего неравенства s jx ( здесь j 1 и х не входит в s), не более одного верхнего неравенства kx и не более одной конгруэнции вида Dm ( x - i), не содержащей свободных вхождений переменных. [26]
Далее, всякое предложение, содержащее п 1 вхождений логических операторов, является либо отрицанием предложения, содержащего п таких вхождений, либо дизъюнкцией двух предложений, каждое из которых содержит не более п таких вхождений, либо получено операцией навешивания квантора общности из формулы, содержащей п таких вхождений. Кроме того, если F - формула, содержащая п вхождений операторов, то любое предложение, полученное из F подстановкой нумерала m вместо свободных вхождений переменных в F, также содержит п вхождений операторов. [27]
Оно основано на том, что каждая формула а либо является элементарной, либо однозначно представляется как дизъюнкция двух формул, ити как конъюнкция двух формул, или как импликация двух формут, или как отрицание некоторой формулы, либо же, наконец, однозначно представляется как результат навешивания квантора па некоторую формулу. [28]
В § 2 мы видели ( см. ( 5) - ( 7)), что операции конъюнкции, дизъюнкции и отрицания очень просто влияют на области истинности форм, к которым они применяются. Операция навешивания квантора существования также очень просто влияет на область истинности. [29]
Из теоремы 2.2 Ь следует лишь замкнутость относительно операции навешивания ограниченного квантора существования. Замкнутость % п относительно операции навешивания ограниченного квантора общности следует из дальнейшего. [30]