Регулярная формула

Cтраница 1

Регулярная формула, которая ложна для всех возможных значений входящих в нее переменных, называется тождественно равной нулю, например: р-р. Путем просмотра таблицы истинности может быть установлено, что любая логическая функция, не являющаяся тождественно равной нулю, эквивалентна дизъюнкции тех элементарных конъюнкций переменных, для которых значение ее истинно. [1]

Цифровой элемент, реализующий функцию / ( Р - Ч. [2]

Регулярная формула исчисления высказываний, которая истинна для любых возможных значений переменных, входящих в нее, называется тождественно равной единице. [3]

Всякая регулярная формула выводима в ограниченной арифметике. [4]

Если регулярная формула 21 / является результатом применения одной из операций 1, 2, 3 / с формуле 21, то и формула 21 регулярна. Это непосредственно следует из определения регулярной формулы. [5]

Если в регулярной формуле некоторые слагаемые внешних множителей являются произведениями, то после вычеркивания любых ( но не всех) множителей в каждом из этих произведений мы получим регулярную формулу. [6]

Каждый внешний множитель регулярной формулы сам есть регулярная формула. [7]

Удаление любого квантора всеобщности из регулярной формулы приводит к регулярной формуле. [8]

Если к слагаемым внешних, множителе регулярной формулы присоединить любые слагаемые: формула останется регулярной. [9]

Всякая формула арифметики, выводи-мая из регулярных формул посредством правил вывода арифметики, регулярна. [10]

Каждый внешний множитель регулярной формулы сам есть регулярная формула. [11]

Очевидно, что каждая формула цепочки регулярности является регулярной формулой. В дальнейшем мы будем доказывать некоторые утверждения, касающиеся регулярных формул, применяя индукцию по цепочке регулярности. Схема рассуждений при этом следующая. Утверждение доказывается для формулы 9 ( 0, все внешние множители которой элементарно регулярны. Отсюда делается заключение, что утверждение справедливо для любой регулярной формулы. Мы ставим себе задачу доказать, что каждая формула, выводимая в ограниченной арифметике, регулярна. Но предварительно нам придется доказать ряд вспомогательных предложений. [12]

Удаление любого квантора всеобщности из регулярной формулы приводит к регулярной формуле. [13]

Импликативная формула называется позитивно тождественной, если она либо является регулярной формулой, либо получается из какой-либо регулярной формулы в результате подстановки, либо выводится из формул этого рода с помощью схемы заключения. [14]

Из доказанных лемм вытекает, что применение дистрибутивных, преобразований к регулярным формулам также приводи. [15]

Страницы: 1 2 3