Содержание к диссертации
Введение
1. Предварительные сведения 7
1.1. Сведения из логики 7
1.1.1. Основные определения 7
1.1.2. Логика слабого закона исключённого третьего 11
1.1.3. Свойства позитивных формул 15
1.2. Алгоритмы и количество информации 28
1.2.1. Алгоритмы 28
1.2.2. Количество информации 30
2. Алгоритмические задачи 33
2.1. Определение и основные свойства 33
2.1.1. Операции над множествами 33
2.1.2. Интерпретация классической логики 34
2.1.3. Интуиционистская логика и реализуемость . 35
2.1.4. Сложность алгоритмических задач 36
2.1.5. Простейшие логические свойства 39
2.2. Оценки на сложность задач 42
2.2.1. Нижняя оценка для критических импликаций 42
2.2.2. Классификация формул по сложности порождаемых алгоритмических задач 46
2.2.3. Верхние оценки для критических импликаций 49
2.2.4. О мощности множеств, на которых достигается нижняя оценка сложности 59
3. Финитные задачи 62
3.1. Основные свойства финитных задач 63
3.1.1. Определение 63
3.1.2. Утверждения о корректности 64
3.1.3. Финитные задачи и логика 69
3.2. Достаточное множество решений 71
3.2.1. Определение и простейшие свойства 71
3.2.2. Нижняя оценка для критических импликаций 76
3.2.3. Классификация формул по мощности достаточного множества решений 79
3.2.4. Об оптимальности оценки для критических импликаций 82
3.3. Колмогоровская сложность финитных задач 85
3.3.1. Определение и простейшие свойства 85
3.3.2. Классификация формул по сложности порождаемых финитных задач 88
Литература 91
- Логика слабого закона исключённого третьего
- Интуиционистская логика и реализуемость
- Верхние оценки для критических импликаций
- Нижняя оценка для критических импликаций
Введение к работе
Классическая логика изучает истинность и ложность высказываний, полученных из некоторых исходных элементарных высказываний при помощи логических операций V, Л, —>, -і, называемых также логическими связками.
А.Н.Колмогоров в своей статье [16], написанной в 1932 году, предложил рассматривать аналогичные операции не над высказываниями, а над задачами. Логические связки в этом случае используются для построения составной задачи из нескольких исходных элементарных задач. Например, для задач А и В их конъюнкция А А В есть задача „решить обе задачи А и Б", а импликация А —> В — „указать общий метод, позволяющий из решения задачи А получить решение задачи В".
В некоторых случаях решение составной задачи можно указать, даже не зная использованных элементарных задач, а зная лишь структуру составной задачи, то есть задающую её формулу. Такова, например, задача вида А —> А. Колмогоров в статье [16] указывал, что множество формул, для которых можно указать заранее некоторое решение составной задачи, естественно назвать конструктивной логикой. Так определённое „исчисление задач" он рассматривал как новый подход к построению интуиционистской логики, отличный от философских рассмотрений Брауэра.
Колмогоров ограничился лишь несколькими примерами элементарных задач и неформальным описанием операций, но не сформулировал математически строгой семантики, подобной той, которую булевы функции предоставляют для классической логики. Впоследствии было предложено несколько вариантов семантики, следующей этим идеям. Первым было понятие реализуемости, предложенное С. К. Клини (1945). На несколько других принципах
основывались интерпретации, введённые Ю. Т. Медведевым — исчисление массовых проблем (1955) и финитная общезначимость (1961).
Логика реализуемости (точнее, разные варианты такой логики) и логика финитных задач активно изучались разными исследователями. Довольно быстро было установлено, что эти логики расширяют интуиционистскую логику высказываний, но не совпадают с ней, и встал вопрос об их синтаксическом описании. Для логики финитных задач была доказана невозможность конечной аксиоматизации, для логики реализуемости этот вопрос остаётся открытым. Также не доказана и не опровергнута ни разрешимость, ни перечислимость этих логик.
Настоящая диссертация посвящена подходу, основанному на некоторой модификации исходной идеи Колмогорова. Этот подход был предложен А. Шенем (см. [19]) и опирается на понятие количества информации, рассмотренное Колмогоровым в 1965 году. Основная идея подхода состоит в следующем.
У любой задачи есть важный параметр — минимальное количество информации, достаточное для её решения. Пропозициональная формула, понимаемая как операция над задачами, задаёт некоторую связь между значениями этого параметра для задач-аргументов и задачи-результата. Рассмотрим те формулы, для которых у любой задачи, полученной подстановкой каких-то задач в эту формулу, количество информации, достаточное для её решения, очень мало по сравнению с количеством информации, необходимым для решения подставленных задач (например, ограничено единой константой для всех подставляемых задач). Естественно сказать, что такие формулы задают задачи, которые можно „почти решить" заранее.
Конечно, формулы колмогоровского „исчисления задач" обла-
дают рассматриваемым свойством: для них существует общее решение, и количество информации в нём никак не зависит от подставляемых задач. Однако этим свойством могут обладать и другие формулы. Представим себе, например, что мы можем заранее указать два каких-то объекта, и для любой задачи, полученной подстановкой в данную формулу, по меньшей мере один из этих объектов будет решением.
Таким образом, возникает следующий вопрос: каков класс пропозициональных формул, для которых некоторое решение задачи, полученной подстановкой в эту формулу, всегда можно указать, используя „небольшое" количество информации?
Для ответа на этот вопрос нужно строго определить, что понимается под задачей, какие операции над задачами сопоставлены логическим связкам, как измеряется количество информации, наконец, каков точный смысл слова „небольшое".
В диссертации рассмотрены два подхода к определению задач и операций над ними: реализуемость (соответствующие задачи названы здесь алгоритмическими) и финитные задачи по Медведеву. Для измерения количества информации в случае алгоритмических задач используется колмогоровская сложность, а в случае финитных задач — мощность „достаточного множества решений" и колмогоровская сложность (это соответствует двум подходам к определению количества информации из статьи [5], комбинаторному и алгоритмическому). Доказано, что для разнообразных ограничений на количество информации в решении (в случае кол-могоровской сложности — для всех естественных ограничений) возникает один и тот же класс формул — логика слабого закона исключённого третьего 3- Доказательства используют характери-зацию логики 3 при помощи формул специального вида — критических импликаций — вытекающую из работ Янкова и Медведева.
Диссертация разбита на три главы.
В первой главе изложены некоторые определения и утверждения, нужные для получения основных результатов. Она в основном содержит ранее известные факты. В первой части главы приведены используемые далее результаты из логики. В первом параграфе собраны основные определения и обозначения, относящиеся к логическим формулам и исчислениям. Во втором и третьем параграфах приведены необходимые факты о логике слабого закона исключённого третьего. Во второй части главы введены используемые далее термины и обозначения из теории алгоритмов и кол-могоровской сложности.
Во второй главе изучается интерпретация логических связок как операций над алгоритмическими задачами. В первой части главы даны основные определения, описана связь рассматриваемого понятия с понятием реализуемости, и доказаны простые оценки на сложность задач. Во второй части главы доказаны основные результаты, и в частности, нижняя оценка сложности для критических импликаций. Также приведены некоторые оценки, дополняющие основные результаты.
Третья глава посвящена операциям над финитными задачами. В первой части главы дано определение финитных задач и доказаны утверждения, обосновывающие корректность последующих определений. Во второй части главы изложены результаты, связанные с комбинаторной мерой сложности финитных задач, а в третьей части — с алгоритмической мерой сложности.
Автор глубоко благодарен своему научному руководителю Н. К. Верещагину за постановку задачи и последующее постоянное участие и помощь в работе. Автор благодарит А. Шеня, В. Е. Плиско и особенно Д. П. Скворцова за полезные обсуждения. Автор признателен В. А. Успенскому, С. И. Адяну и всем сотрудникам кафедры математической логики и теории алгоритмов механико-математического факультета МГУ за благожелательное внимание к работе.
Логика слабого закона исключённого третьего
Классическая логика изучает истинность и ложность высказываний, полученных из некоторых исходных элементарных высказываний при помощи логических операций V, Л, — , -і, называемых также логическими связками. А.Н.Колмогоров в своей статье [16], написанной в 1932 году, предложил рассматривать аналогичные операции не над высказываниями, а над задачами. Логические связки в этом случае используются для построения составной задачи из нескольких исходных элементарных задач. Например, для задач А и В их конъюнкция А А В есть задача „решить обе задачи А и Б", а импликация А — В — „указать общий метод, позволяющий из решения задачи А получить решение задачи В". В некоторых случаях решение составной задачи можно указать, даже не зная использованных элементарных задач, а зная лишь структуру составной задачи, то есть задающую её формулу. Такова, например, задача вида А — А. Колмогоров в статье [16] указывал, что множество формул, для которых можно указать заранее некоторое решение составной задачи, естественно назвать конструктивной логикой. Так определённое „исчисление задач" он рассматривал как новый подход к построению интуиционистской логики, отличный от философских рассмотрений Брауэра. Колмогоров ограничился лишь несколькими примерами элементарных задач и неформальным описанием операций, но не сформулировал математически строгой семантики, подобной той, которую булевы функции предоставляют для классической логики. Впоследствии было предложено несколько вариантов семантики, следующей этим идеям. Первым было понятие реализуемости, предложенное С. К. Клини (1945). На несколько других принципах основывались интерпретации, введённые Ю. Т. Медведевым — исчисление массовых проблем (1955) и финитная общезначимость (1961). Логика реализуемости (точнее, разные варианты такой логики) и логика финитных задач активно изучались разными исследователями. Довольно быстро было установлено, что эти логики расширяют интуиционистскую логику высказываний, но не совпадают с ней, и встал вопрос об их синтаксическом описании. Для логики финитных задач была доказана невозможность конечной аксиоматизации, для логики реализуемости этот вопрос остаётся открытым. Также не доказана и не опровергнута ни разрешимость, ни перечислимость этих логик.
Настоящая диссертация посвящена подходу, основанному на некоторой модификации исходной идеи Колмогорова. Этот подход был предложен А. Шенем (см. [19]) и опирается на понятие количества информации, рассмотренное Колмогоровым в 1965 году. Основная идея подхода состоит в следующем. У любой задачи есть важный параметр — минимальное количество информации, достаточное для её решения. Пропозициональная формула, понимаемая как операция над задачами, задаёт некоторую связь между значениями этого параметра для задач-аргументов и задачи-результата. Рассмотрим те формулы, для которых у любой задачи, полученной подстановкой каких-то задач в эту формулу, количество информации, достаточное для её решения, очень мало по сравнению с количеством информации, необходимым для решения подставленных задач (например, ограничено единой константой для всех подставляемых задач). Естественно сказать, что такие формулы задают задачи, которые можно „почти решить" заранее. Конечно, формулы колмогоровского „исчисления задач" обла дают рассматриваемым свойством: для них существует общее решение, и количество информации в нём никак не зависит от подставляемых задач. Однако этим свойством могут обладать и другие формулы. Представим себе, например, что мы можем заранее указать два каких-то объекта, и для любой задачи, полученной подстановкой в данную формулу, по меньшей мере один из этих объектов будет решением. Таким образом, возникает следующий вопрос: каков класс пропозициональных формул, для которых некоторое решение задачи, полученной подстановкой в эту формулу, всегда можно указать, используя „небольшое" количество информации? Для ответа на этот вопрос нужно строго определить, что понимается под задачей, какие операции над задачами сопоставлены логическим связкам, как измеряется количество информации, наконец, каков точный смысл слова „небольшое". В диссертации рассмотрены два подхода к определению задач и операций над ними: реализуемость (соответствующие задачи названы здесь алгоритмическими) и финитные задачи по Медведеву. Для измерения количества информации в случае алгоритмических задач используется колмогоровская сложность, а в случае финитных задач — мощность „достаточного множества решений" и колмогоровская сложность (это соответствует двум подходам к определению количества информации из статьи [5], комбинаторному и алгоритмическому). Доказано, что для разнообразных ограничений на количество информации в решении (в случае кол-могоровской сложности — для всех естественных ограничений) возникает один и тот же класс формул — логика слабого закона исключённого третьего 3- Доказательства используют характери-зацию логики 3 при помощи формул специального вида — критических импликаций — вытекающую из работ Янкова и Медведева.
Интуиционистская логика и реализуемость
По мысли Колмогорова из [16], формула должна считаться интуиционистски приемлемой, если соответствующая задача не просто всегда имеет решение, а имеет единое решение для всех подстановок элементарных задач. То есть для формулы Ф(і,... ,&) существует такое слово х, что х Є Ф{Х\,... ,Xk) для любых множеств Xi,... ,Xk. Это определение в более общей ситуации (для предикатных, а не пропозициональных формул) впервые исследовал Плиско в [11], назвавший такие формулы абсолютно реализуемыми. Этот вариант реализуемости был введён с целью приспособить реализуемость по Клини (см. [15] и [4, 82]) для описания конструктивной логики в наиболее общей форме. Очевидно, что всякая абсолютно реализуемая формула реализуема по Клини. Неизвестно, совпадают ли классы реализуемых и абсолютно реализуемых пропозициональных формул (пример реализуемой, но не абсолютно реализуемой предикатной формулы построил Плиско в [11].) Тем не менее, основные факты о реализуемых формулах, доказанные в работах Клини ([4, 82]) и Роуза ([18]), переносятся и на случай абсолютной реализуемости. Следующий факт является аналогом теоремы Нельсона из [4] и точно так же доказывается индукцией по выводу. Предложение 2.2. По каждой формуле Ф( і,... ,&), выводимой в Зпі, можно эффективно построить такое слово х, что Множество реализуемых формул содержит логику 3nt, но не исчерпывается ей. Примером абсолютно реализуемой, но интуиционистски невыводимой пропозициональной формулы служит формула Роуза ((—і—іФ -» Ф) -» (-іФ V -і-іФ)) - (-іФ V ——»Ф), где Ф = -iti V -і 2 (ее абсолютная реализуемость доказывается точно так же, как её реализуемость в статье Роуза [18]). Неизвестно, является ли класс всех абсолютно реализуемых пропозициональных формул разрешимым (или хотя бы перечислимым). Перейдём, наконец, к рассмотрению модифицированного подхода к реализуемости, основанного понятии количества информации. Сложностью Ks(X) множества двоичных слов X называет-ся минимум колмогоровских сложностей его элементов, то есть Ks(X) = тт{К(х) \ х Є X}; сложность пустого множества бесконечно велика: Ks(0) = со.
Таким образом, сложностью задачи называется сложность её простейшего решения. Докажем два несложных, но фундаментальных неравенства между сложностями задач, соответствующих формулам. Предложение 2.3. Пусть Ф(і,..., ) — произвольная пропози-циональная формула. Существует такая константа Сф, что для любых множеств Х\,..., Xk, если Ф(А"і,..., Xk) Ф 0, то Константа Сф зависит только от вида формулы Ф, количества переменных к и выбора оптимального способа описания. (Если все ХІ пусты, можно считать, что в правой части есть только Сф.) Доказательство. Чтобы доказать неравенство, мы предъявим вычислимую функцию, которая по любому элементу множества ДХ./0Х; строит элемент множества Ф(Хі,... ,Xk), и применим свойство 3 колмогоровской сложности, приведённое на странице 32. Сначала для каждой формулы Ф(і,... , ) мы построим вычислимую функцию /ф, которая получает в качестве аргументов к двоичных слов, и обладает следующим свойством. Пусть Xi,... ,Xk — произвольные множества, а слова у і,..., у к таковы, что для каждого і выполнено одно из двух: либо у-г = 0х{ и ХІ Є Х{, либо /,- = 1 и ХІ = 0. Тогда если Ф(Хі,... ,Хк) ф 0, то МУи---,Ук) = Оя и х Є Ф(Л"і,...,Хй), а если Ф(ХЬ...,Х ) = 0, то /«(2/i,...,2/ft) = 1. Функцию /ф определим индукцией по построению формулы Ф. ма, вычисляющая функцию, тождественно равную х). Пусть дан элемент множества Лх- о i- Зная, какие из Х( пусты, можно построить кортеж т/1,..., г/Аг с требуемым свойством (для каждого і выполнено одно из двух: либо у\ = OXJ и Х{ Є ХІ, либо у І — 1 и X,- = 0). Теперь, используя функцию /ф, можно построить элемент множества Ф(Хі,... ,Xk). В построенном вычислимом отображении использовалась толь ко информация о виде формулы Ф, и к битов, сообщающих, пусто ли соответствующее Х{. Предложение 2.4. Для произвольных множеств X и Y имеет место неравенство где константа С зависит только от выбора оптимального способа описания. Доказательство. Если множество X или множество X — Y пусто, то правая часть неравенства бесконечна, и поэтому оно выполнено. Пусть множества X и X — Y непусты. Заметим, что в этом случае Y тоже непусто. Возьмём элементы р Є X — У и # Є X, на которых достигается минимум в определении сложности множества, то есть такие, что К(р) = Ks(X — Y) и К{х) = Ks(X). По определению импликации значение \р]{х) определено и принадлежит У, поэтому С, где последнее неравенство следует из свойств 2 и б колмогоровской сложности, а предпоследнее — из свойства 3, применённого к вычислимой функции Предложение 2.1 можно переформулировать в терминах сложности: формула Ф(і,... ,jt) является классической тавтологией тогда и только тогда, когда Ks( fr(Xi,..., Хк)) конечна для любых множеств Х\,... ,Хк- Таким образом, классическая логика описывает тривиальное понимание „малости" количества информации, достаточной для решения задачи — конечная величина мала по сравнению с бесконечной. Другой крайний вариант понимания „малости" — сложность всех задач, соответствующих данной формуле, ограничена некоторой константой. То есть рассматривается множество к таких формул Ф(і,... ,tk), для которых найдётся такая константа С, что для любых множеств Х\,..., Хк Определение множества к можно переформулировать и без использования понятия колмогоровской сложности, в духе обычного определения реализуемости. Формула Ф(і,..., tk) принадлежит множеству к, если найдутся такие слова х\,... ,х\ (их количество может зависеть от формулы), что для любых множеств Х\,.. . , Хк (определение абсолютной реализуемости получится, если потребовать / = 1). Эквивалентность этих двух определений очевидна. Если для некоторой формулы Ф сложность Ks( &(Xi,... ,Хк)) всегда меньше С, то в качестве x\,...,xi можно взять все элементы множества {х К(х) С} (в силу свойства 5 колмогоровской сложности / оказывается меньше 2е). Наоборот, если множеству Ф(Хі,..., Хк) все
Верхние оценки для критических импликаций
В статье [19] рассматривалась также следующая задача. Пусть даны двоичные слова х\,... ,#&. Подставим одноэлементные множества {xi},...,{xk} в формулу Ф(і,... ,fc). В [19] для нескольких формул были найдены равенства (с точностью до константы и до логарифма), которые связывают сложность получающегося множества со сложностями слов x\,...,Xk и их условными сложностями относительно друг друга. В частности, это было сделано для критической импликации ((s\ — S2) - $2) - si V S2. Обобщение использованного там метода позволило доказать нижнюю оценку сложности задач, получающихся при подстановке одноэлементных множеств в произвольную критическую импликацию (теорема 2.1). Для многих (хотя не для все доказанная оценка точна, если заключение критической импликации имеет вид Vli sh а слова xi,...,xm независимы (то есть сложность любого из них не уменьшится, если станут известны все остальные; именно такие слова использованы в доказательстве теоремы 2.2): Почти так же легко убедиться, что эта оценка верна для критической импликации Jm и произвольных х\,... ,хт. Лемма 2.8. Для каждого т существует такая константа С, что для произвольных слов х\,..., хт верна оценка Доказательство. Зафиксируем какое-нибудь j Є {1,.. ,77г} и докажем, что Очевидно, отсюда будет следовать утверждение леммы. Пусть слово у позволяет найти Xj при известных остальных Очевидно, по / можно построить программу / Є (Лі/ " жі) и - (/) - (у)+ (1)» гДе слагаемое О(І) зависит только от выбора функции К. Для / построим следующую программу р/ Є «Лп({#і},..., {#m})-Эта программа получает на вход кортеж элементов, принадлежащих посылкам критической импликации Jm. Заметим, что среди этих посылок есть формула ((ЛІ І S") "" sj) " si Обозначим через г тот элемент входного кортежа, который соответствует этой посылке (для корректных входов он принадлежит множеству ((Лг Ч }) {xj}) {xj})- Программа р/ выдаёт значение (j,[r](f)) (если оно определено). Очевидно, что доказательство изложенной леммы проходит для любой критической импликации от переменных si,... ,5m, у которой заключение имеет вид VLi si? а среди посылок есть формулы ((Лш Sj) si) — si для всех J {!» т1- Однако и в Т0М случае, если для какого-то одного j посылка указанного вида отсут ствует, утверждение остаётся верным, хотя с меньшей точностью, а доказательство становится существенно сложнее. Теорема 2.3. Пусть J(s\,... ,sm) — критическая импликация, т 2. Пусть существует такое I, что для всех j Є {1,...,т}, j ф I среди посылок J есть формула ((Л -з;) — Sj) — Sj. Тогда существует такая константа С, что для произвольных слов xi,...,xm верна оценка где V — множество индексов тех переменных, которые входят в дизъюнкцию R, являющуюся заключением критической импликации.
Доказательство. Для упрощения обозначений будем считать, что I = т. Если это не так, переименуем переменные, это приведёт только к замене формулы J на другую критическую импликацию с указанными в условии свойствами. Доказательство разобьём на две х) критических импликаций удаётся доказать и соответствующую верхнюю оценку. В частности, доказанная оценка точна, если заключение критической импликации имеет вид Vli sh а слова xi,...,xm независимы (то есть сложность любого из них не уменьшится, если станут известны все остальные; именно такие слова использованы в доказательстве теоремы 2.2): Почти так же легко убедиться, что эта оценка верна для критической импликации Jm и произвольных х\,... ,хт. Лемма 2.8. Для каждого т существует такая константа С, что для произвольных слов х\,..., хт верна оценка Доказательство. Зафиксируем какое-нибудь j Є {1,.. ,77г} и докажем, что Очевидно, отсюда будет следовать утверждение леммы. Пусть слово у позволяет найти Xj при известных остальных Очевидно, по / можно построить программу / Є (Лі/ " жі) и - (/) - (у)+ (1)» гДе слагаемое О(І) зависит только от выбора функции К. Для / построим следующую программу р/ Є «Лп({#і},..., {#m})-Эта программа получает на вход кортеж элементов, принадлежащих посылкам критической импликации Jm. Заметим, что среди этих посылок есть формула ((ЛІ І S") "" sj) " si Обозначим через г тот элемент входного кортежа, который соответствует этой посылке (для корректных входов он принадлежит множеству ((Лг Ч }) {xj}) {xj})- Программа р/ выдаёт значение (j,[r](f)) (если оно определено). Очевидно, что доказательство изложенной леммы проходит для любой критической импликации от переменных si,... ,5m, у которой заключение имеет вид VLi si? а среди посылок есть формулы ((Лш Sj) si) — si для всех J {!» т1- Однако и в Т0М случае, если для какого-то одного j посылка указанного вида отсут ствует, утверждение остаётся верным, хотя с меньшей точностью, а доказательство становится существенно сложнее. Теорема 2.3. Пусть J(s\,... ,sm) — критическая импликация, т 2. Пусть существует такое I, что для всех j Є {1,...,т}, j ф I среди посылок J есть формула ((Л -з;) — Sj) — Sj. Тогда существует такая константа С, что для произвольных слов xi,...,xm верна оценка где V — множество индексов тех переменных, которые входят в дизъюнкцию R, являющуюся заключением критической импликации. Доказательство. Для упрощения обозначений будем считать, что I = т. Если это не так, переименуем переменные, это приведёт только к замене формулы J на другую критическую импликацию с указанными в условии свойствами. Доказательство разобьём на две леммы. Их можно назвать обратными к леммам из доказательства теоремы 2.1. Используемая здесь операция Лт определена на странице 43. Начнём с более простой леммы, обратной к лемме 2.7. Лемма 2.9. Для всякого т существует такая константа С , что для любого j Є {1,..., m} Доказательство. Для данного j возьмём формулы Р = Дш 5» и Q = Sj и рассмотрим соответствующие множества Р = Д, ,{ ,} и
Нижняя оценка для критических импликаций
Теорема 3.2. Пусть J(si,... ,sm) — критическая импликация с т переменными, a Gi,...,Gm — произвольные конечные множества, содержащие по крайней мере два элемента. Пусть множество X С Тогда Доказательство. Чтобы избежать громоздких обозначений, всюду в этом доказательстве будем считать, что р[Щ есть тип, который получается в результате подстановки в некоторую формулу Ф типов Gi,... ,Gm вместо переменных 5i,...,sm, а Ф(Хі,... ,Хт) — сокращение для x№i(GuXi},..., (GmjXm))]. Пусть G — множество таких наборов {х\,... ,Х2т} Є G\ х G\ х х G2 х G2 х ... х Gm х Gm, что Х2і-\ Ф Х2І для любых і Є {1,..., га}. Каждому набору х G G поставим в соответствие двухэлементные МНОЖеСТВа Х{{х) = {х2г _Ь#2і} С G{. Скажем, что элемент р, принадлежащий типу у?[«7], является решением для набора х Є G, если р Є «7(-Х"і,..., Хт) для X,- = Л"г(х). Мы покажем, что любое р является решением только для небольшой доли всех наборов из G. С этой целью для каждого р рассмотрим двудольный граф, вершинами которого являются элементы множества G. Элементы, для которых р является решением, принадлежат первой доле, все остальные — второй. Условие, при котором две вершины соединены ребром, будет сформулировано ниже. При этом будет обеспечено следующее свойство графа: из каждой вершины первой доли исходит не меньше (min,- G, — 2) рёбер, а из каждой вершины второй доли исходит не больше 2т рёбер. Пусть в первой доле Mi вершин, а во второй доле М% вершин. Оценим число рёбер графа: с одной стороны, из первой доли исходит не меньше (min,- \Gj\ — 2)Mi рёбер, а с другой стороны, из второй доли исходит не больше 2тМ2 рёбер. Из соотношений Мі + Mi = \G\ и (min; G, — 2)Mi ImMi получаем, что Mi G-2m/(miiii G;+2m—2), то есть не более чем для такого количества наборов из G элемент р является решением. Множество X с указанным в условии свойством должно для каждого набора из G содержать решениер, поэтому X-G-2m/(min,- G,+2m—2) G, то есть Х min,- G,-/(2m) + 1 — 1/m, что и требовалось.
Осталось объяснить, как следует провести рёбра в графе, соответствующем р. Критическая импликация J имеет вид Д; Ф,(«і,..., sm) — V sj. Элемент р типа (p[J] является функцией, определенной на кортеже элементов типа [Ф{]. Формулы Ф,- имеют вид (Р — Q) — Q, где Р — непустая конъюнкция, a Q — непустая дизъюнкция некоторых из si,..., sm, причём общих переменных у них нет. Пусть Ф — формула описанного вида. Для каждого набора х Є G определим функцию / Є р[&]. Пусть Р1(х) — единственный элемент множества Р({х\}, {#з}5 5 {#2m-i}), Р2{х) — единственный элемент множества Р({#2},{#4}5 ііяїт}), и наконец, Q{x) = Q(Xi(х),... ,Хт(х)). Значение функции / на элементе г Є р[(Р — Q)] определяется так: жит также множеству Ф(А"і(ж ),... ,Хт(х )) для таких х Є G, которые отличаются от х только в одной координате, то есть ж,- = х\ для всех г, кроме одного. Действительно, пусть г Є (Р —ї Q)(X\(x ),... ,Хт(х )). Тогда по определению г(Р1(х )) Є Q{x ) и г(Р2(х )) Є Q{x ). Поскольку формулы Р и Q не имеют общих переменных, замена х на х может повлиять либо на значение Р1, либо на значение Р2, либо на значение Q, но не на какие два из них сразу, то есть возможны три случая. Пусть р является решением для некоторого набора х. Рассмотрим значение р на кортеже тех /f, которые соответствуют формулам Фг- из посылки критической импликации. Это значение принадлежит множеству \/jXj(x) (где дизъюнкция берётся по всем j из заключения критической импликации) и имеет вид (bii...(bm ,xc}...}, где 6і,...,Ьт/ Є {0,1} и однозначно определяются по с. В графе, соответствующем р, вершину х соединим рёбрами со всеми такими х , что Х{ = х\ при г ф с и хс ф х с. Покажем, что х и х1 лежат в разных долях графа.
Действительно, возьмём j = [с/2] — номер того множества из дизъюнкции, которому должен принадлежать элемент хс. Одно из чисел 2j — 1 и 2j равно с, второе обозначим через d, и рассмотрим множество Xj(x ) = {x c,x d}. Элемент хс не принадлежит этому множеству, поскольку х с ф хси x d = Xd Ф хс (напомним, что рассматриваются только такие х, у которых Х2І-\ Ф Х2І). Поэтому в силу отмеченного свойства функций fg элемент р, являясь решением для х, не может быть решением для х . Количество элементов х рассматриваемого вида равно \Gj\ — 2, поэтому из каждой вершины первой доли исходит по крайней мере (mini \G{\ — 2) рёбер. Предположим, что из какой-то вершины х второй доли исходит больше 2т рёбер. Тогда некоторые две вершины из первой доли от личаются от х в одной и той же координате, то есть найдутся два таких набора х1 их2, что р на кортежах функций вида /fi и j&. вы даёт соответственно (&i,... {Ьт ,х}} ...) и (Ьь... (Ьт ,х2} ...). Но для і ф I имеем х\ = х\ = х2, поэтому х1 и х2 должны находиться в разных долях; противоречие. Теорема 3.3. Пусть формула Q(t\, ..., ) невыводима в $. Тогда найдётся такое т, что для любого N существуют такие типы F\,..., Fk, что их мощности не превышают (4mN)m и для любого множества X С [0](Fi,..., Fk) выполнено следующее: если при любых Х\,...,Xk Доказательство. Для невыводимой в 3 формулы 0 возьмём число т и формулы Ті,..., Т&, построенные в теореме 1.3. Для данного JV возьмём любые множества Gi,...,Gm мощности 2mN каждое, и определим множества F\,...,Fk посредством равенств Fi = (p[Ti](Gi,..., Gm). Если Тг- = _L, то F, = 1. В противном случае Т; является дизъюнкцией некоторых конъюнкций переменных si,..., sm. Конъюнкция не более чем т множеств мощности 2mN каждое имеет мощность не более (2miV)m, различных таких конъюнкций тоже существует не более 2т, поэтому \Fi\ 2т (2mN)m = (4miV)m. Рассмотрим все финитные задачи А\,..., Ак вида
