Введение в математическую логику и теорию алгоритмов Алексей Львович Семенов Лекция 4

Определимость отношений (повт.) Множество D Семейство R отношений на D. Структура Какие отношения (элементы D N ) можно объяснить, выразить, определить через R? Объяснять можно на языке – языке логики отношений. Например, можно определить, объяснить отношение «между» на действительной прямой через отношение «меньше». Через сложение и умножение можно определить отношения на N: –z является остатком от деления x на y –y=2 x –Произвольное вычислимое (каким-то алгоритмом) отношение 2

Порядок на рациональных числах Q Структура. Какие отношения определимы? Фиксируем натуральное n. Все формулы от n переменных. Интерпретации – последовательности (цепочки) длины n рациональных чисел. Последовательная формула имеет вид: Λ x σ(i) μ i x σ(i+1), i = 1,…, n, где σ – некоторая перестановка (изоморфизм) множества {1,… n}, для каждого i: μ i - один из символов =,

4 Задача. Всякая бескванторная формула эквивалентна дизъюнкции последовательных и для каждой из них существует интерпретация, в которой и она, и исходная формулы истинны. Вопрос. Как быть с отрицанием? Д. Истинность бескванторной формулы в интерпретации однозначно определяется последовательной формулой для этой интерпретации. О. Две интерпретации эквивалентны, если их последовательные формулы совпадают. Аналогия с СДНФ Конструкция «Разбор случаев». Были: «Диагональ», «Челнок» (К – Б). Задача. Как для каждой формулы вида u Ф(x 1, x 2,..., x n ) [ u / x i ], где Ф – последовательная, построить эквивалентную ей бескванторную? Задача. Как для любой формулы построить эквивалентную ей бескванторную? Все определимое устроено просто. Что с утверждениями (формулами без свободных переменных)? Элиминация кванторов

5 Поле действительных чисел. Определимые отношения Структура: R =, p ( ) =, > 0 – для всех полиномов p с целыми коэфф., Зн Что определимо? Алгебраические отношения (множества в N ) – системы (конъюнкции) уравнений Юрий Иванович Манин ( – ): Если уравнения выбраны и зафиксированы, мы представляем себе множество всех их решений… в виде геометрического образа, формы... В одних направлениях эта форма уходит в бесконечность, а в других прихотливо замыкается на себе. Разнообразие и сложность таких форм бесконечно богаче, чем все, что можно увидеть на современных выставках абстрактного искусства. Математики научились находить регулярности, взаимосвязи и закономерности в этом огромном мире.

Поле действительных чисел. Многообразие всех отношений Полуалгебраические множества – объединения, пересечения и дополнения множеств, задаваемых уравнениями и неравенствами Применим к полу алгебраическим множествам (отношениям) проекцию. Она соответствует квантору существования для формул. Получится ли больше отношений? Нет – теорема Тарского – Зайденберга Логическая (кванторная) сложность – ограничена. 6

7 Теорема Тарского (– Зайденберга) О. эквивалентные в данной структуре формулы - задают одно и то же отношение (на D N ) Т. Существует алгоритм, который для всякой формулы сигнатуры структуры R строит эквивалентную ей в этой структуре бескванторную формулу. Следствие. Проекция полу алгебраического множества – полу алгебраическое множество. Пример. x 2 +px+q = 0 задаёт множество троек x, p, q. Его проекция вдоль оси x на плоскость p, q – p 2 - 4q 0. полу алгебраическое множество Альфред Тарский ( )

8 Доказательство теоремы Тарского – Зайденберга Для формул с единственным квантором существования u Ф ( x 1,..., x n ) [ u / x i ], где Ф – бескванторная, будем строить эквивалентную (задающую то же отношение на N ) бескванторную. Атомные формулы в Ф имеют вид p(u, x 1,..., x n ) = 0 или p(u, x 1,..., x n ) > 0, где p – многочлен с целыми коэффициентами. Многочлен p можно рассматривать как многочлен от переменной u, коэффициенты которого – многочлены от x 1,.., x n. Надо доказать, что те векторы x 1,..., x n, при которых u существует, образуют полу алгебраическое множество.

Доказательство Пол Коэн ( ) Школьный «Метод интервалов» Диаграмма – схема из метода интервалов. Вместо графика функции, или его наброска используется схема: прямая, где (обычно, без соблюдения масштаба) помечены корни и проведена пересекающая ее в корнях «змейка», там, где она выше прямой, функция положительна, где ниже – отрицательна. x 1,..., x n - параметры, из «уравнений с параметрами» 9

Диаграмма многочлена (реформ.) Знак многочлена в точке – это 0, +, -. Диаграмма – цепочка знаков от минус до плюс бесконечности «это – диаграмма x 3 u 2 +x 2 u+x 1 » x 3 0 «это – диаграмма x 2 u+x 1 » x 2 >0 Существование корня, точки положительности…- видны из диаграммы

Пример используемых соображений. Знак многочлена в корне другого многочлена Пусть p = sq + r, d – корень многочлена q(u) Нужно найти Знак p в точке d Знак p(d) = Знак r(d) Если r – остаток от деления p на q, то r проще (имеет меньшую степень), чем q Если q проще p, то r проще, чем p 11

12 Диаграмма семейства многочленов. Все семейства в этом доказательстве - конечные. Пусть задано семейство многочленов. Прямая разбивается всеми корнями многочленов семейства на сегменты (включая одноточечные): (-, a 1 ), [a 1 ], (a 1, a 2 ), [a 2 ],…, [a n ], (a n, + ) Построим таблицу: имена строк – многочлены, имена столбцов – сегменты. В клетке – знак многочлена на сегменте (он постоянен). Пример. Семейство: u 2 -1 и u(u-1)(u-2). Корни: -1, 0, 1, 2. (-, -1) [-1](-1, 0)[0][0](0, 1)[1][1](1, 2)[2][2] (2, + ) u –––0+++ u(u-1)(u-2) –––0+0–0+

13 Диаграмма семейства многочленов Выбросим из таблицы имена сегментов Диаграмма семейства многочленов в точке a – наборе значений x 1,..., x n. Это – диаграмма семейства u 2 -x 1 x 2, u(u-x 2 )(u-x 1 ) в точке. Задача. Дать определение диаграммы семейства. Таблица для семейство многочленов: имена строк – все элементы семейства, количество столбцов – не больше удвоенного возможного числа корней (степени по u ) плюс 1, в клетках – знаки. Таких таблиц – много. Среди них есть все диаграммы семейства в разных точках, но могут быть и не диаграммы. u –––0+++ u(u-1)(u-2) –––0+0–0+ u2-x1u2-x1 +0–––0+++ x 1 u(u-x 2 )(u-x 1 ) –––0+0–0+

14 Доказательство теоремы Тарского – Зайденберга. Задача. Различных таблиц для данного семейства многочленов – конечное число. Фиксируема формулу Ф(u, x 1,..., x n ). Пусть F – семейство всех многочленов, входящих в Ф(u, x 1,…, x n ), a – набор значений переменных x 1,..., x n Тогда по диаграмме F в точке a можно определить истинность формулы u Ф(u, x 1,..., x n ) в этой точке. пространство n точек – значений для x 1,..., x n разбивается на конечное число частей, отвечающих всем возможным диаграммам (по u ). Нужно доказать, что эти части – полу алгебраические.

Доказательство теоремы Тарского – Зайденберга Определим 4 операции на семействах многочленов. 1. Модифицированный остаток Дано: пара p,q многочленов от u (с коэффициентами из [x 1,..., x n ]). Пусть k = степень p(u) – степень q(u) + 1, a – старший коэффициент q(u). Получаем: модифицированный остаток от деления p(u) на q(u) = остаток от деления a k p(u) на q(u). Вопрос. Что дает домножение на a k ? Степень (по u) модифицированного остатка меньше степени q. 15

Доказательство теоремы Тарского – Зайденберга Определяем еще 3 операции на семействах многочленов. 2. Отбрасывание старшего члена 3. Взятие старшего коэффициента 4. Дифференцирование по u В результате применения операции 1 к паре многочленов положительной степени получаем многочлен степени меньшей, чем максимум степеней в паре. В результате применения операций к многочлену положительной степени эта степень уменьшается. Применение операции к многочлену нулевой степени дает его самого или 0. Поэтому замыкание конечного семейства многочленов относительно этих операций конечно. Задача. Оценить, сколько. 16

17 Доказательство теоремы Тарского – Зайденберга. Пусть F 0 – часть F, состоящая только из многочленов степени 0 по u (они представляют собой многочлены из[ x 1,..., x n ] ). Диаграмма для множества F 0 состоит из одного столбца. Лемма. Пусть F – семейство многочленов из ([ x 1,..., x n ])[ u ], замкнутое относительно перечисленных операций 1-4. Тогда диаграмма множества F в данной точке может быть построена по диаграмме множества F 0 в той же точке. То, что диаграмма множества F 0 данная, записывается бескванторной формулой (конъюнкцией знаков многочленов от x 1,..., x n ).

18 Доказательство теоремы Тарского – Зайденберга. Доказательство Леммы Добавляем начиная с F 0 многочлены из F в порядке неубывания их степеней (то есть можем добавить многочлен, если все многочлены меньшей степени уже добавлены), пока не получим всё множество F. (действуем снизу вверх) Покажем, что на каждом шаге диаграмма расширенного множества (с новым многочленом) может быть однозначно восстановлена по диаграмме предыдущего множества. Задача. Завершить доказательство Леммы.

Доказательство теоремы Тарского – Зайденберга. Доказательство Леммы Задача. Добавляем многочлен p. Что происходит с диаграммой? Какие появляются строки? Какие появляются столбцы? Как искать Знак p в корнях уже рассмотренных многочленов? Использование операций 1 – 4. пример соображения: Если в соседних корнях уже рассмотренных многочленов p(u) имеет одинаковые знаки, то между этими корнями нет корней p(u) (иначе между корнями был бы корень производной, входящей в диаграмму), и знак в промежутке тот же 19

Доказательство теоремы Тарского – Зайденберга Для всякой формулы u B(u, x 1,..., x n ), где B – бескванторная, мы строим эквивалентную бескванторную: Выписываем семейство всех многочленов из B. Строим замыкание F семейства (относительно 4-ех операций). Берем в замыкании часть нулевой степени F 0. Строим (восстанавливаем) таблицу для F, из таблицы для F 0 (из одного столбца), Отбираем из таблиц для F те, которые обращают u B(u, x 1,..., x n ) в истину. Берем те таблицы из F 0, из которых они получились. Для каждой взятой таблицы из F 0 записываем бескванторную формулу, (конъюнкция утверждений о каждой клетке). Искомая – дизъюнкция построенных формул. 20

. Доказательство теоремы Тарского – Зайденберга Преобразование произвольной формулы в бескванторную идет индукцией по построению («изнутри») Если при построении мы навешивали квантор, то теперь мы его навешиваем и сразу избавляемся. Мы заменяем всякую формулу u B(u, x 1,..., x n ) на эквивалентную u B(u, x 1,..., x n ). Со связками – очевидно. 21

22 Пример. Формула x(x 2 +px+q = 0) Множество F 0 составляют 8 многочленов (4) – (11). (1)x 2 +px+q – соответствует атомной формуле, (2)px+q – (1) без старшего члена, (3)2x+p2x+p – производная от (1), (4)1 – старший коэффициент (1), (5)q – (2) без старшего члена, (6)p – ст. коэфф. (2) = произв.(2) = (3) без ст.чл., (7)2 – старший коэфф. (3) = произв. от (3), (8)q2q2 – остаток деления p 2 (1) на (2), (9)4q - p 2 – остаток деления 4 (1) на (3), (10) 2q - p 2 – остаток деления 2 (2) на (3), (11)p2 - 2qp2 - 2q – остаток деления p (3) на (2).

23 Пример. Формула x(x 2 +px+q = 0) Для сокращения перебора можно не рассматривать противоречивые диаграммы. Знаки многочленов, тождественно равных 1 и 2, – известны. Также, зная знак q, знаем и знак q 2. Зная знак 2q - p 2, знаем знак p 2 - 2q. Для построения диаграмм D оставляем только многочлены q, p, 4q - p 2, 2q - p 2. Количество диаграмм D равно 3 4 =81. Для примера рассмотрим одну диаграмму D: Строим по ней диаграмму D, добавляя по очереди многочлены 2x+p, px+q, x 2 +px+q. Добавляем многочлен 2x+p. Единственному столбцу диаграммы соответствует интервал (-, + ). При - многочлен отрицателен, при + – положителен. Значит, на интервале есть корень, и столбец разбивается на три столбца. q+ p– 4q - p 2 – 2q - p 2 –

24 Пример. Формула x(x 2 +px+q = 0) Добавляем многочлен px+q. Каков его знак в нуле многочлена 2x+p ? Деление: 2(px+q) = p(2x+p) + 2q - p 2. Знак px+q равен знаку остатка 2q - p 2 (–). Так как p < 0, то при - многочлен px+q положителен, а при + – отрицателен. Корень имеется в первом столбце. Добавляем многочлен x 2 +px+q. Его знак в нуле многочлена 2x+p ? 4(x 2 +px+q) = (2x+p)(2x+p) + 4q - p 2. Знак равен знаку остатка 4q - p 2 (–). Его знак в нуле многочлена px+q ? p 2 (x 2 +px+q) = (px+p 2 -q)(px+q) + q 2. Так как p 2 > 0, знак равен знаку остатка q 2 (+). q+++ p––– 4q - p 2 ––– 2q - p 2 ––– 2x+p2x+p–0+ q+++++ p––––– 4q - p 2 ––––– 2q - p 2 ––––– 2x+p2x+p–––0+ px+q+0–––

25 Пример. Формула x(x 2 +px+q = 0) Во 2 и 4 столбцах знаки разные. Значит, в 3 столбце – корень. 3-й столбец делим на три столбца. При - и при + многочлен x 2 +px+q положителен. Корень – в последнем столбце, последний столбец делим на три столбца. Расставляем знаки. Диаграмма D по диаграмме D построена. Видим, что при условиях q>0, p

26 Поле действительных чисел Что дает алгоритм для формул без свободных переменных? Он отвечает на вопрос об истинности формул. Следствие Теоремы Тарского – Зайденберга. Теория R разрешима: существует алгоритм, который по утверждению в нашей сигнатуре (многочлены…), выясняет, истинная ли она в нашей структуре (действительные числа…).

27 Геометрия С помощью метода координат большинство геометрических утверждений можно записать как утверждения о действительных числах. Исключение. Не получится говорить об n-угольниках без указания конкретного n. Пример. Гипотеза 13 шаров: спор между Ньютоном и Грегори: "Сколько материальных шаров равных радиусов можно "прислонить" к фиксированному шару того же радиуса?" Существование решения у системы уравнений с 39 неизвестными. Невозможность (правота Ньютона) доказана Л. Ван дер Варденом и К. Шютте в 1953 году (без теоремы Тарского).