Cтраница 2
Мы пишем здесь переменные р и q, а не произвольные формулы, поскольку результат подстановки некоторых формул вместо р и q может быть выводимой формулой. [16]
Если мы запрещаем функциональные символы, то вопрос о выводимости произвольной формулы сводится к выводимости - формулы. [17]
Заменив в § V L предикат A ( t) произвольной формулой 33 ( /), мы получим формулу § V U. [18]
В самом деле-переписывая такую цепочку, заменяя каждое вхождение Л произвольной формулой Л, мы автоматически получим доказательство формулы А V - А. Последний результат правильно именовать схемой теорем ( или теоремной схемой), а его вывод-схемой доказательства. Дело в том, что само А не является формулой нашей системы, а лишь обозначает произвольную формулу, так что приведенную схему мы выдвигаем в качестве образца для построения доказательства формулы А V - А, где А обозначает некоторую фиксированную, но произвольную формулу. Теоремные схемы - - как и аксиомные схемы - удобны тем, что, заменяя каждую входящую в них букву некоторой формулой, мы получаем теорему. [19]
Формальная теория называется разрешимой, если существует алгоритм, позволяющий по произвольной формуле А выяснять, выводима ли А в этой теории или нет. Известно, что всякая формальная теория, содержащая некоторый фрагмент теории рекурсивных функций, необходимо неразрешима. Отсюда следует неразрешимость элементарной арифметики, системы Цермело-Френкеля и многих других теорий. В теории доказательств разработаны тонкие методы интерпретации одних теорий в других; с помощью таких интерпретаций можно установить неразрешимость и ряда очень простых исчислений, в которых не интерпретируются непосредственно рекурсивные вычисления. Примерами могут служить элементарная теория групп, теория двух отношений эквивалентности, элементарная теория частичного порядка. С другой стороны, имеются примеры интересных разрешимых теорий, таких как элементарная геометрия, элементарная теория действительных чисел, теория множеств натуральных чисел с единственной операцией следования. [20]
Вообще говоря, может не существовать алгоритма, с помощью которого для произвольной формулы ( р через конечное число шагов можно определить, является ли ( р выводимой в исчислении / или нет. Если такой алгоритм существует, то исчисление называется разрешимым. Исчисление называется непротиворечивым, если не все его формулы доказуемы. [21]
Соотношения (6.33) - (6.35) справедливы вообще для элемента произвольной формы и для произвольной формулы перемещений. [22]
Операция расширения может применяться к любому регулярному выражению ( и даже к произвольной формуле) над алфавитом, содержащим все буквы входного алфавита автомата и символы всех его комплексов. Крг) - произвольная формула указанного вида, то операция расширения состоит, во-первых, в замене всех символов комплексов их явными выражениями через пути, а, во-вторых, в подстановке вместо символов внутренних состояний а, в каждом из возникших таким образом путей символов комплексов высших рангов в соответствии со сформулиро-панным выше правилом замены. [23]
Покажите, что интуиционистское исчисление высказываний разрешимо: существует алгоритм, который по произвольной формуле определяет, выводима ли она в интуиционистском исчислении высказываний. Указание: оцените мощность контрмодели Крипке; можно обойтись и без этого, заметив, что и множество выводимых формул, и множество формул, имеющих конечные контрмодели, перечислимы. [24]
Определение 2.3.8. i) Для некоторого, возможно пустого, множества формул S и произвольной формулы А выводом А из S называется конечная последовательность формул логики предикатов В... Bk, где каждая формула Bi, 1 г k, либо является аксиомой, либо принадлежит S, либо получена из некоторых формул BJ, Bt, I j, I г по одному из правил - Modus Ponens или обобщения. [25]
Таким образом, алгоритм Сколема, сохраняя свойство невыполнимости ( противоречивости), приводит произвольную формулу, имеющую пренексный вид, к V-формуле. [26]
Пусть х - произвольная предметная переменная, А, В, С н D - произвольные формулы, причем D не содержит х свободно, Т - произвольный терм, свободный для х в А. Аксиомами рассматриваемого исчисления являются любые формулы следующих 10 видов ( каждый из к-рых наз. [27]
Из только что доказанного, теоремы 23.11 и теоремы 32.2 получаем сводимость вопроса о доказуемости произвольной формулы Ф в исчислении предикатов к вопросу о доказуемости пустого списка в подходящем исчислении резольвент. [28]
Всякий раз, когда в любой из этих схем X, Y, Z заменяются произвольными формулами, получается тавтология. Следовательно, эти схемы формул могут служить схемами аксиом в некоторой адекватной системе. [29]
Основную роль здесь играет такое утверждение: если Г - непротиворечивое множество, а А - произвольная формула, то хотя бы одно из множеств Г U А и Г U - А непротиворечиво. В самом деле, если оба множества Ги А и Ги - 1А противоречивы, то Г I-А и Г I-i - iА, но множество Г предполагалось непротиворечивым. [30]