Cтраница 2
В духе работ [5, 82] введем еще два семейства классов булевых функций, которые сохраняют свойство принадлежать классу вида Рр, q при подстановке констант вместо переменных. [16]
Тогда каждый предикат класса М будет входить в класс В А, поскольку в силу (1.33) любой предикат получается из графика своей характеристической функции подстановкой константы 1 вместо одной из переменных. [17]
Так, термы f ( X, XY c Y) и f ( с, X, Y t X, Y) эквивалентны, поскольку после подстановки констант х и у вместо X и У соответственно мы получим сопоставимые основные термы. С другой стороны, нетрудно видеть, что термы f ( X, X, У, с, Y) и f ( с, Z, У, Z, У) не эквивалентны. Отметим, в частности, что два сопоставимых основных терма также эквивалентны. [18]
Определение 7.1. Будем говорить, что функция / получена из системы Ф при помощи расширенной суперпозиции, если она получается из Ф при помощи операций суперпозиции ( определение 2.3) и подстановки констант. [19]
Условия полноты относительно суперпозиций, удовлетворяющих условиям задачи, и обычных суперпозиций совпадают. Учесть, что подстановка констант всегда является сокращающей подстановкой. [20]
Пусть в произвольном каноническом дереве бесповторной функции f листья иг и va смежны с различными внутренними вершинами. Тогда среди подфункций, получаемых подстановкой констант на место всех остальных переменных функции /, найдутся либо существенно зависящая ровно от одной переменной, либо две различные подфункции, существенно зависящие от обеих переменных и не являющиеся отрицанием друг друга. [21]
Этот метод был использован ван Воорисом [11] для доказательства нижней оценки вида Q ( nlogn) для системы функций сортировки. Ламанья [1] соединил теоретико-графовый подход с методом подстановки констант и исключения элементов. [22]
Как верхняя, так и нижняя оценки устанавливаются здесь очень просто. Из этого свойства и свойства функции Ап ( Ап) сохранять при подстановке константы вместо переменной существенную зависимость от всех остальных переменных вытекает, что в схеме для функции Ап ( Ап) обе переменные, поступающие на входы первого элемента схемы, поступают еще на какие-нибудь элементы. [23]
Присоединим к какой-то части входов схемы выходы элементов, реализующих константы ( их можно считать не имеющими входов), а остальные входы отождествим. Получим схему с задержкой v, реализующую функцию от одной переменной, полученную из ф подстановкой констант вместо соответствующих переменных и отождествлением остальных. Тогда сигнал на выходе в момент времени t зависит только от х и не зависит от сигналов на входе схемы в другие моменты времени. Как и при решении предыдущей задачи, будем подавать в момент времени / - v & сигнал х, если k четно, и х, если k нечетно. Тогда на выходах всех элементов схемы либо будет всегда один и тот же сигнал, либо сигнал, совпадающий с тем, который подается на вход в данный момент времени. Доказательство проводится так же, как и в предыдущей задаче. Нужно заметить только, что при подстановке константы в какой-либо аргумент функции Шеффера мы получим либо константу, лаСо отрицание. В результате схема S реализует или константу ( если на ее выходе всегда один и тот же сигнал), либо х, если v четно, либо х, если v нечетно. [24]
В противном случае обозначение Ф ( с) может допускать разночтения. Например, если ф - формула со свободными переменными х т у, то необходимо указать, как получено ф ( с): в результате подстановки константы с вместо переменной х или вместо переменной у. Мы, однако, предпочитаем пользоваться обозначением ф ( с) вместо более громоздкого ф ( с / я), полагаясь в отношении ясности на контекст. [25]
Из определения существенной зависимости видно, что при вычислении значений функции реально используются лишь значения существенных переменных. В связи с этим возникает желание освободиться от ненужных фиктивных переменных. Это соответствует подстановке константы 0 на места переменных xm i... [26]
На множестве предикатов определим нелогические операции, операции логики высказываний и операции ограниченной квантификации. Они включают в себя операции введения фиктивных переменных, перестановки и отождествления переменных, подстановки констант ( из N) вместо переменных. [27]
Начиная доказывать теорему Тарского, предположим, что множество номеров всех истинных арифметических формул ( без параметров) арифметично. Рассмотрим формулу с единственным параметром х, утверждающую, что результат подстановки константы х в ж-ую формулу с параметром ложен. [28]
Присоединим к какой-то части входов схемы выходы элементов, реализующих константы ( их можно считать не имеющими входов), а остальные входы отождествим. Получим схему с задержкой v, реализующую функцию от одной переменной, полученную из ф подстановкой констант вместо соответствующих переменных и отождествлением остальных. Тогда сигнал на выходе в момент времени t зависит только от х и не зависит от сигналов на входе схемы в другие моменты времени. Как и при решении предыдущей задачи, будем подавать в момент времени / - v & сигнал х, если k четно, и х, если k нечетно. Тогда на выходах всех элементов схемы либо будет всегда один и тот же сигнал, либо сигнал, совпадающий с тем, который подается на вход в данный момент времени. Доказательство проводится так же, как и в предыдущей задаче. Нужно заметить только, что при подстановке константы в какой-либо аргумент функции Шеффера мы получим либо константу, лаСо отрицание. В результате схема S реализует или константу ( если на ее выходе всегда один и тот же сигнал), либо х, если v четно, либо х, если v нечетно. [29]
Вслед за Пуанкаре Вейль считает законными только те свойства, которые явно определимы в некотором языке. Его понимание смысла свойств интенсионально; поэтому совпадение логического смысла свойств - это по определению совпадение их описаний. Для множеств, определяемых свойствами, равенство вводится экстенсионально: два свойства определяют одно и то же множество, если им удовлетворяют одни и те же элементы. Общепринятое в математике со времен Дирихле и вплоть до нашего времени определение функции ( как множества пар) представляется Вейлю нечетким, по-видимому, из-за того, что оно не предполагает никакого языка для явного задания соответствующих свойств. По сходной причине Вейль отвергает в конце § 4 главы II возможность существования единой, независимой от языка определения, шкалы кардинальных и ординальных чисел. В § 2 главы II Вейль описывает вариант языка логики первого порядка, предвосхищающий некоторые идеи Шейнфинкеля, Куайна и Бурбаки. Его суждения строятся из атомарных символов, т.е. символов отношений, с помощью операций 1 - 6, то есть отрицания, отождествления аргументов, конъюнкции, дизъюнкции, подстановки константы и квантора существования, который выражается с помощью символа, подлежащего расшифровке. Более подробное индуктивное определение требует вводить наряду с суждением также перечень его аргументных мест. [30]