Cтраница 2
Формула Яр совпадает с формулой Яр ь которая регулярна, так как она получена из регулярной формулы Яр 1 удалением внешнего квантора. В таком случае формула Яд операциями 1, 2, 3 приводится к регулярной формуле Яр, которая приводится в свою очередь такими же операциями к формуле, у которой все внешние множители элементарно регулярны. Отсюда следует, что формула Я регулярна. [16]
Таким образом, мы показали, что применение всех правил вывода расширенного исчисления предикатов к регулярным формулам приводит к регулярным формулам, что и требовалось доказать. [17]
В силу этого формула -, 21 или, что то же, 9И1) - регулярная формула. [18]
Импликативная формула называется позитивно тождественной, если она либо является регулярной формулой, либо получается из какой-либо регулярной формулы в результате подстановки, либо выводится из формул этого рода с помощью схемы заключения. [19]
Эта формула элементарно регулярна; следовательно, аксиома V А ( х) - А ( у) - регулярная формула. [20]
Мы ставим своей ближайшей задачей показать, что если применить одну из операций 1, 2, 3 к регулярной формуле, то формула останется регулярной. Именно, мы покажем, что если применить одну из операций 1, 2, 3 к формуле 51, являющейся частью регулярной формулы 51 V ф, то полученная формула 9Г V § останется регу лярной. [21]
Таким образом, мы показали, что применение всех правил вывода расширенного исчисления предикатов к регулярным формулам приводит к регулярным формулам, что и требовалось доказать. [22]
Пусть формула регулярна и ее внешние множители имеют вид 9Г V 5В V 33, причем ( 5 V 33 - регулярная формула. Тогда, заменив в формуле 91 все или некоторые внешние множители формулами 9Г & К V 33 V 93 и переименовав, если это нужно, переменные, получим регулярную формулу. [23]
Таким образом, мы показали, что, удалив из внешних множителей Ф0 слагаемые, происшедшие из 23, мы получим выводимые в ограниченной арифметике, следовательно, регулярные формулы. [24]
Если в регулярной формуле некоторые слагаемые внешних множителей являются произведениями, то после вычеркивания любых ( но не всех) множителей в каждом из этих произведений мы получим регулярную формулу. [25]
В самом деле, в формуле Ух % ( х) квантор Ух яв-i ляется внешним, поэтому его удаление не нарушает ре гулярности; точно так же присоединение к регулярной формуле 51 ( х) внешнего квантора не нарушает регулярности. [26]
Если регулярная формула 21 / является результатом применения одной из операций 1, 2, 3 / с формуле 21, то и формула 21 регулярна. Это непосредственно следует из определения регулярной формулы. [27]
Для отношений вида t - f - k t - f - k2, tjrk1 t kz значение истинности определяется непосредственно. Эти дополнительные операции предотвращают рост констант в регулярных формулах. [28]
& ( 9lriV 93) - - также регулярная формула, и обратно. Доказательство этого утверждения получается немедленно из лемм 1, 4 и свойства 3 регулярных формул ( стр. Из этого следует, что указанные преобразования мы можем применять и к отдельным множителям формулы, являющейся произведением, сохраняя неизменными остальные множители. Применение первого дистрибутивного закона также возможно. [29]
Очевидно, что каждая формула цепочки регулярности является регулярной формулой. В дальнейшем мы будем доказывать некоторые утверждения, касающиеся регулярных формул, применяя индукцию по цепочке регулярности. Схема рассуждений при этом следующая. Утверждение доказывается для формулы 9 ( 0, все внешние множители которой элементарно регулярны. Отсюда делается заключение, что утверждение справедливо для любой регулярной формулы. Мы ставим себе задачу доказать, что каждая формула, выводимая в ограниченной арифметике, регулярна. Но предварительно нам придется доказать ряд вспомогательных предложений. [30]