«Прикладная логика Учебное пособие Рекомендовано Государственным комитетом Российской Федерации по высшему образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям ...»

6.1.2. Рассмотрим следующее индуктивное рассуждение.

И не только в классической математике!

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Пусть даны n джентльменов (натуральных, хорошо воспитанных, а не одесских) и k бутербродов. Докажем, что все джентльмены скорее останутся голодными, чем притронутся к бутербродам.

Базис индукции. Пусть бутерброд всегда один. Тогда приведенное утверждение очевидно, поскольку следует из благовоспитанности джентльменов, которые прежде всего думают о том, как не причинить неудобств другому джентльмену, что произошло бы, если бы джентльмен съел бутерброд и тем самым лишил других такой возможности.

Шаг индукции. Пусть предложение доказано для k бутербродов.

Добавим еще один. Тогда, если какой-то джентльмен съест бутерброд, то он сведет ситуацию к предыдущей, в которой, как уже было доказано, ни один джентльмен не притронется к бутерброду. Так что настоящий джентльмен на такой шаг не пойдет.

ОБ ИНДУКТИВНЫХ ОПРЕДЕЛЕНИЯХ

§ 6.2.

Индуктивное определение имеет следующую общую форму:

(Базис индукции) Выражения вида A есть B.

(Шаг индукции) Если мы имеем выражения A1,..., An типа B, то C, построенное из них, также есть выражение типа B.

С каждым индуктивным определением связан принцип индукции по построению объекта типа B.

(Базис индукции) Каждый объект вида A обладает свойством.

(Шаг индукции) Если A1,..., An обладают свойством, то и C им обладает.

(Заключение индукции) Тогда любой объект типа B обладает свойством.

Этот принцип является логическим выражением следующего неявного пункта, присутствующего в любом индуктивном определении: никаких других объектов типа B, кроме полученных применением правил его определения, нет. Иными словами, множество объектов типа B — минимальное из тех, которые включают базисные объекты и замкнуты относительно шага индукции. В простых определениях эту минимальность можно выразить следующим образом: объект должен получаться из базисных конечным числом применений шагов определения. Но в современной теории часто приходится рассматривать определения, которые включают шаги, опирающиеся на бесконечное множество ранее построенных объектов. Тут индукция остается единственным корректным и инвариантным способом выражения минимальности7.

Стоит отметить, что логическая индукция по построению вовсе не требует однозначности представления объекта в форме, соответствующей одному из пунктов его определения. Но для задания функций индукцией по построению такая однозначность необходима.

Теперь рассмотрим другие возможности, связанные с индуктивными определениями. Часто несколько понятий вводятся совместным индуктивным определением, в котором в каждом шаге могут участвовать уже построенные понятия разных типов. Для того чтобы превратить раздельные определения формулы и терма в совместное, достаточно ввести пункт типа: если A(x) — формула, то x A(x) — терм8. В совместных определениях индукцию и рекурсию по построению приходится вести одновременно для всех понятий. Далее, в математических теориях широко применяются определения, в шагах которых могут быть ссылки на бесконечное множество ранее построенных понятий. Они также допустимы, но, конечно, уже не могут быть прямо перенесены на представление данных в программах.

Часто отмечается возможность представления логических формул в виде дерева. На самом деле в такой же структуре представляются любые индуктивно определенные понятия. Но называть структуру данных, соответствующую индуктивным определениям, просто деревом несколько неточно.

Как известно, дерево — это ориентированный граф, в котором имеется корень и в любую другую вершину ведет ровно один путь из корня. Таким образом, по определению графа, ребра, выходящие из любой вершины дерева, равноправны. Структура же, соответствующая индуктивному понятию, является нагруженным деревом, вершинам которого сопоставлены слова, а ребра помечены согласно роли их назначения в В теории множеств часто определяют множество объектов типа B при помощи следующей процедуры: возьмем пересечение всех множеств объектов, включающих базис определения и замкнутых относительно его шага. Но такое определение, с одной стороны, включает в себя скрытый порочный круг (B определяется в том числе и через само B); с другой стороны, оно не сохраняется при переходе к неклассической логике.

Эти термы были введены Д. Гильбертом. Их семантика — выбрать такое x, что A(x), если такое x существует; в противном случае взять некоторое стандартное значение.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Рис. 6.2: Формула и соответствующее ей дерево структуре понятия. Например, на рис. 6.2 даны формула и соответствующее нагруженное дерево.

Рассмотрение деревьев, соответствующих построениям индуктивных объектов, позволяет вывести мощную и не очень зависящую от изменений взгляда на математику характеризацию минимальности класса объектов, задаваемых индуктивным определением. Дерево с конечными путями — такое, в котором нет ни одного бесконечного пути, и значит, каждый путь, который не может быть продолжен, заканчивается в листе.

Теорема 6.1. Каждому примеру индуктивно определенного понятия сопоставляется нагруженное дерево с конечными путями.

Доказательство. Рассуждаем индукцией по построению. Понятиям, построенным согласно базисам определения, сопоставляются деревья из одной вершины. Если всем Ai, участвующим в определении B, сопоставлены деревья Ti, то B сопоставляется дерево, корнем которого является построение самого B, ветви, выходящие из корня, помечены номерами i, и за i-той дугой следует дерево Ti. Любой путь, выходящий из B, проходит через какую-то i-тую ветвь и продолжается как путь в Ti, который конечен по предположению индукции.

';

Итак, индукцией по определению мы установили соответствие понятий и деревьев с конечными путями. И обратно, деревья с конечныОБ ИНДУКТИВНЫХ ОПРЕДЕЛЕНИЯХ ми путями являются одним из мощных средств определять структуры данных, по которым можно вести индукцию. Общую формулировку индукции для таких деревьев впервые установил голландский математик Брауэр (L. E. J. Brouwer) в 1928 г. средствами неклассической математики, а затем она была доказана и традиционными средствами, правда, доказательство совершенно другое и с точки зрения использования как основы для алгоритма никуда не годное9. Через a b обозначим отношение “b непосредственно следует за a”, т. е. дуга ведет из a в b; через L(a) — предикат “быть листом”.

Теорема 6.2. (Теорема Брауэра, bar-индукция) Если T — дерево с конечными путями и выполнены базис и шаг индукции:

то x (x T A(x)).

Доказательство. Действуем от противного. Предположим, что есть такое a0 T, что ¬A(a0 ). По шагу индукции, тогда существует a1, такое, что a0 a1 и ¬A(a1 ). a1 не может быть листом, поскольку для листьев A верно по базису индукции; значит, для него в свою очередь можно найти a2, a1 a2 и ¬A(a2 ). Продолжая таким образом, получаем бесконечный путь в T, чего быть не может.

Важным частным случаем деревьев с конечными путями являются веера. Дерево имеет конечное ветвление, если из каждой вершины выходит конечное число дуг. Веер — дерево с конечными путями и конечным ветвлением. Следствием bar-индукции является следующий результат, история которого также необычна. Он сначала был доказан Брауэром в нетрадиционной математике, существенно неклассическими методами, а затем передоказан классическими методами К нигом.

Лемма 6.2.1 (Теорема о веерах). Любой веер конечен.

Доказательство. Если веер состоит из одного элемента, он конечен. В противном случае веер представляется как на рисунке 6.3, где T1,..., Tn являются веерами. По предположению индукции, все они конечны, и значит, общее число элементов в веере конечно.

Но ниже приведено именно классическое доказательство; для неклассического у нас пока что не хватит ни знаний, ни техники.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Все вышесказанное не отменяет того, что индуктивное определение — достаточно опасный и тонкий прием. В частности, легко впасть в парадокс лжеца, индуктивно определив A(x) через ¬A(x). Поэтому настоятельно не рекомендуется использовать отрицания в индуктивных определениях и нужно следить за отсутствием порочных кругов, когда ответ, является ли E корректным выражением, зависит от самого себя.

Корректны ли следующие индуктивные определения? Если они формально некорректны — как их исправить? Если корректны формально — что они определяют и хороши ли они содержательно?

6.2.1. Пусть 2 — хорошее число; 3 — плохое число. Если n — хорошее, то n + 5 — хорошее; если n — плохое, то n + 7 — плохое.

6.2.2. Пусть 0 — нужное число; если n + 1 и n 1 — нужные числа, то 6.2.3. Элементарные формулы атомарны; если ¬A — атомарная формула, то и A — атомарна.

6.2.4. Пусть 0 — хорошее число; если n — хорошее, то n+1 не является хорошим числом; если n — не хорошее число, то n+1 — хорошее.

6.2.5. Один английский математик XIX в. в связи с широко обсуждавшейся в то время проблемой вымирания знатных родов утверждал, что он построил модель развития человечества, в которой оно существует вечно, но потомки по мужской линии любого мужчины через конечное время исчезнут. Возможна ли такая модель? А как по женской линии?

ТРАНСФИНИТНАЯ ИНДУКЦИЯ И ОРДИНАЛЫ

§ 6.3.

6.3.1. Построение начального отрезка ординалов Заметим, что индукция по индуктивному определению напоминает возвратную индукцию. Еще до того, как были осознаны индуктивные определения, было замечено, что возвратная индукция — гораздо более общий принцип, чем математическая, и переносится на многие другие множества.

Пример 6.3.1. Пополним множество натуральных чисел бесконечным числом, которое больше всех обычных чисел. На множестве N {} выполнен принцип возвратной индукции и, соответственно, принцип бесконечного спуска и принцип наименьшего числа.

В самом деле, для n < принцип возвратной индукции выполнен, поскольку они — натуральные числа. Значит, если выполнен шаг возвратной индукции, то выполнено n(n < A(n)). Но тогда по шагу индукции выполнено и A().

Первым предложил распространить принцип возвратной индукции на более широкое множество чисел германский математик Г. Кантор в третьей четверти XIX века. Он назвал пополнение натуральных чисел, при котором сохраняется возвратная индукция, — трансфинитными (сверхконечными) или ординальными (порядковыми) числами10, а принцип индукции для них — трансфинитной индукцией. Таким образом, трансфинитная индукция — обычная возвратная индукция, но для трансфинитных чисел. Имеет смысл, как это часто делается в математике, превратить важнейшее для нас свойство в определение.

Определение 6.3.1. Вполне упорядоченное множество — линейно упорядоченное множество, для которого выполнен принцип возвратной индукции. Фундированное (частично вполне упорядоченное) множество — чум с возвратной индукцией.

Начальный отрезок трансфинитных чисел есть смысл построить явно, поскольку он будет в дальнейшем использоваться при доказательствах индукцией.

Часто называют их просто трансфинитами или ординалами. В настоящее время более популярно название ординалы или ординальные числа, а вот индукцию попрежнему называют трансфинитной.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Прежде всего, если добавить непосредственно следующий за ординал +1, то получившееся множество чисел по-прежнему будет вполне упорядочено. Аналогично получится, если добавить конечное число ординалов до + n с естественным упорядочением. А за всеми + n естественно поставить ординал 2. Итак, начальный отрезок ординалов имеет следующую структуру:

Но за 2 можно продолжать в том же духе, получая:

Обобщая по всем натуральным числам, получаем следующий ряд:

Но вслед за всеми этими ординалами вида n + k естественно поставить еще больший и назвать его 2. А за 2 выстраивается ряд, изоморфный предыдущему:

Опять-таки продолжая по всем натуральным числам, получаем всевозможные ординалы вида За ними идет ординал, обозначаемый. А за ним опять-таки цепочка его “сумм” со всеми предыдущими ординалами:

Аналогично, мы приходим к 2, и далее к n. Если считать, что законы сложения степеней сохраняются (а уж мы постараемся их сохранить), то дальше идет +1. Таким образом приходим к ординалам вида А за ними идет ординал, который естественно обозначить 2. Продолжая данный процесс, мы приходим к ординалам вида А за всеми этими башнями стоит ординал, который Г. Кантор назвал и определил как наименьшее решение уравнения =. Слава Богу, в данном курсе нам не будут нужны явные выражения для ординалов, значительно больших, чем 0.

Теперь рассмотрим одно применение ординалов. Докажем, что любая программа вида заканчивается, если исполнения всех упомянутых в ней операторов S, S1, S2 заканчиваются и они не изменяют значений переменных цикла.

Пусть s — значение S1 к моменту начала нынешнего исполнения внутреннего цикла. Построим следующую функцию:

На каждом шаге любого цикла эта функция уменьшается и, по вполне упорядоченности множества ординалов, за конечное число шагов дойдет до 0, и программа закончится.

Заметим, что такой способ доказательства весьма экономен в мышлении. Нам не нужно оценивать результат каждого исполнения S1, зато мы сразу получаем все возможности, которые могут сорвать выполнение программы. Правда, мы не находим никакой явной оценки времени работы программы, но это не всегда нужно.

Проиллюстрированный выше метод называется в теории алгоритмов и теоретической информатике методом сигнализирующих функций.

Чтобы доказать конечность некоторого процесса вычисления, достаточно построить функцию со значениями в фундированном множестве, убывающую на каждом шагу процесса. Для построения сигнализирующих функций часто удобнее всего использовать ординалы. При анализе практических программ хватает ординалов до 0.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

6.3.2. Свойства вполне упорядоченных множеств Исходя из переформулировок возвратной индукции, видим, что каждое непустое подмножество вполне упорядоченного множества имеет наименьший элемент и что каждая убывающая последовательность элементов конечна. Наименьший элемент вполне упорядоченного множества X обозначается 0X или просто 0, если X однозначно определяется из контекста. Далее, если некоторое подмножество X0 вполне упорядоченного множества X ограничено сверху, то оно имеет точную верхнюю грань, а множество его строгих верхних границ — наименьший элемент, являющийся наименьшим элементом, превосходящим все элементы X0.

Этот элемент обозначим lim sup X0 и назовем верхним пределом X0.

Например, — верхний предел множества натуральных чисел.

Предложение 6.3.1. Если X и Y — два вполне упорядоченных множества, то выполнена одна и только одна из альтернатив:

a) Существует монотонно возрастающая инъекция X на начальный отрезок Y.

b) Существует монотонно возрастающая инъекция Y на начальный отрезок X.

c) X и Y изоморфны.

Доказательство. Одновременно определим трансфинитной индукцией две функции f : X Y, g : Y X. Если уже определено f () для всех, то Аналогично определяем g.

Обозначим наименьший элемент всего множества X — 0X, наименьший элемент Y — 0Y. Обозначим через X0 следующее подмножество X:

Аналогично определяем Y0.

По построению, если X0, f { | } — начальный отрезок Y. Симметрично для g. Таким образом, множества X0, Y0 являются начальными отрезками X и Y соответственно.

Докажем, что f и g являются изоморфизмами между X0 и Y0. В самом деле, на X0 f является инъекцией. Аналогично для g и Y0. Далее, трансфинитной индукцией установим, что В самом деле, пусть эта импликация выполнена для всех. Тогда, если X0, то Но f () = lim sup{f () | }. Значит, Таким образом, доказан изоморфизм начальных отрезков X и Y.

Теперь покажем, что если X изоморфно начальному отрезку Y, то этот отрезок определяется однозначно. Итак, пусть имеются два изоморфизма f1 и f2 вполне упорядоченного множества X на начальные отрезки Y1 и Y2 соответственно. По трансфинитной индукции легко доказывается, что для всех x X f1 (x) = f2 (x), а из такого равенства следует искомая однозначность.

Итак, если X изоморфно собственному начальному отрезку Y, то оно уже не может быть изоморфно самому Y, и наша трилемма доказана.

Предложение 6.3.2. Между двумя изоморфными вполне упорядоченными множествами есть только один изоморфизм.

Доказательство. Рассмотрим два изоморфизма X на Y : 1 и 2. По трансфинитной индукции докажем их тождество.

Пусть для всех выполнено 1 () = 2 (). Тогда, поскольку эти функции — изоморфизмы,

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Дадим теперь некоторые способы строить одни вполне упорядоченные множества по другим. Пусть у нас есть семейство вполне упорядоченных множеств (Xi )iI и множество индексов I также вполне упорядочено. Тогда на их прямой сумме естественно вводится линейный порядок, содержательно описываемый следующим образом: Xi располагается после Xj, если i j:

Доказательство. Докажем, что введенный порядок полный. В самом деле, возьмем произвольное непустое подмножество прямой суммы Y iI Xi. Возьмем его проекцию на I. Она непуста, значит, в ней найдется наименьшее i0, такое, что (i0, ) Y. А теперь в Xi0 найдется наименьшее 0, такое, что (i0, 0 ) Y. По определению порядка, (i0, 0 ) — наименьший элемент Y.

Функции, в которых область определения — некоторое стандартное вполне упорядоченное множество (ординал), называются ординальными последовательностями. Они сохраняют основные свойства обычных последовательностей, в частности, если множество значений упорядочено, то последовательности можно упорядочить лексикографически, поскольку для двух разных последовательностей существует первый элемент, на котором они различаются.

Определение 6.3.2. Ординальное произведение ординальной последовательности вполне упорядоченных множеств — множество ординальных последовательностей их элементов, в которых отлично от нуля лишь конечное число членов, упорядоченное следующим отношением (I — множество индексов последовательности)11 :

Предложение 6.3.3. Ординальное произведение произвольной ординальной последовательности вполне упорядоченных множеств вполне упорядочено.

Введенный порядок можно назвать антилексикографическим.

Доказательство. Прежде всего докажем, что введенный порядок линейный. Рассмотрим две не равных друг другу последовательности a и b. Поскольку в каждом конечном линейно упорядоченном множестве имеется наибольший элемент, имеется такое, что при всех a() = a() = 0. Значит, множество непусто и имеет наименьший элемент 0. Но для 0 a(0 ) = b(0 ). Этот факт требует отдельного обоснования.

В самом деле, если 0 таково, что то значения обязаны различаться по предположению, поскольку и для всех меньших, и для всех б льших индексов они равны. Если же услоо вие (6.7) не выполнено, то найдется наибольшее 1 0, на котором они различаются, и для 1 выполняется характеристическое свойство множества Iab, что противоречит определению 0.

6.3.3. Представления ординалов.

Действия над ординалами В теории множеств ординальные числа определяются как представители каждого класса изоморфных вполне упорядоченных множеств. Поскольку здесь целый класс, а не множество, приходится обходиться без аксиомы выбора и строить их явно. Здесь помогает аксиома фундированности. Из нее вытекает следующее утверждение:

Предложение 6.3.4. Если множество X линейно упорядочено отношением то оно вполне упорядочено им.

Доказательство. Пусть Y — непустое подмножество X. По аксиоме фундированности, в Y имеется элемент, не пересекающийся с самим Y. Значит, он минимален по отношению. Следовательно, каждое непустое подмножество X имеет наименьший элемент, что и требовалось доказать.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Определение 6.3.3. Множество называется транзитивным, если является на нем отношением порядка. Ординал — транзитивное линейно упорядоченное множество.

Считается, что ординал меньше ( ), если изоморфен собственному начальному отрезку.

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

Имея какое-то представление ординалов, можно доказывать результаты про них, а из этих результатов получать новые представления ординалов, может быть, не всех, но зато более применимые. Это — обычный путь разработки понятий для нужд прикладной математики.

Следующие предложения касаются именно данного конкретного представления ординалов. В них вовсю эксплуатируются некоторые удобства, получающиеся при таком представлении: равенство ординалов — просто равенство множеств, отношение выражается сразу двумя способами:,.

Предложение 6.3.5. 1. Если два ординала изоморфны, они равны.

2. Любой ординал совпадает с множеством всех меньших его ординалов.

4. Объединение произвольного множества ординалов является ординалом.

Доказательство. Первый пункт легко доказывается трансфинитной индукцией.

Докажем второй пункт. Любой элемент ординала является ординалом, и м ньшим его. В самом деле, он является, по транзитивности, мное жеством, линейно упорядоченным отношением. Далее, он определяет некоторый начальный отрезок данного ординала и, соответственно, не изоморфен ему, но вкладывается в него. Теперь докажем, что любой начальный отрезок ординала, не совпадающий с ним, принадлежит ординалу. В самом деле, если X — начальный отрезок ординала и X =, то в ординале есть элемент 0, такой, что 0 для всех X.

Но тогда, поскольку 0 = X, имеем такое 1 0, которое обладает такими же свойствами, и т. д. Итак, мы получили бесконечную убывающую последовательность, что противоречит вполне упорядоченности.

А ординалы, меньшие данного, по первому пункту совпадают с его начальными отрезками.

Следующий пункт вытекает из второго.

Последний пункт легко доказать самим.

Определение 6.3.4. 1. Ординал называется предельным, если нет наибольшего ординала, такого, что ; непредельным, если такой ординал есть.

2. Наименьший ординал, такой, что, называется следующим за и обозначается S12. Наименьший ординал обозначается 013.

Ординал S0 называется единицей и обозначается 1. Соответственно для остальных натуральных чисел. Наименьший предельный ординал, б льший 0, обозначается.

3. Пределом возрастающей ординальной последовательности ординалов называется наименьший ординал, такой, что 4. Суммой ординальной последовательности ординалов (i )i называется ординал, изоморфный ординальной сумме соответствующих вполне упорядоченных множеств. Сумма последовательности обозначается Таким образом, в теории множеств S = {}.

Таким образом, ординальный 0 — это.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

либо просто 1 + + n для конечных последовательностей.

5. Произведением ординальной последовательности ординалов называется ординал, изоморфный ее ординальному произведению.

Произведение обозначается либо просто 1 n для конечных последовательностей.

6. Степенью ординала называется ординал где все члены произведения одинаковые.

Рассмотрим некоторые свойства введенных операций. Для их формулировки понадобится один из частных видов разбиений, особенно популярный для лумов. Говорят, что лум X разбит на непересекающиеся отрезки, если дано такое его разбиение (Xi )iI, что из Xi, Xi, следует Xi. То, что разные Xi не пересекаются, имеет место по определению разбиения множества.

4. Сумма ассоциативна, и, более того, бесконечно ассоциативна. А именно, если (Yj )j — такое разбиение на непересекающиеся 6. Произведение бесконечно ассоциативно. А именно, если (Yj )j — такое разбиение на непересекающиеся отрезки, что Доказательство. Самые нетривиальные пункты здесь — 4 и аналогичный ему для произведения. Рассмотрим структуру двойной суммы. Она состоит из элементов вида (, (, )), где, Y,. Но однозначно определяется через и не влияет на порядок элементов.

Установленный изоморфизм доказывает равенство ординалов.

Для произведения мы имеем функцию, результатом которой также является функция, а именно, элементом произведения является функция, перерабатывающая каждое j в функцию из Yj в iYj i. Но в конце концов данная функция может быть представлена как множество множеств троек того же вида, что и в предыдущем абзаце. В этом множестве множеств лишь конечное число троек с отличным от нуля третьим элементом, а первый элемент однозначно определяется вторым, так что опять имеет место изоморфизм с одинарным произведением.

То, что операции над ординалами некоммутативны, легко увидеть на следующем примере. Если + 1 — следующий за ординал, который мы так и обозначаем, то 1 + =. В самом деле, если к натуральному ряду в начале присоединить еще один элемент, то полученное упорядоченное множество изоморфно натуральному ряду. Если же этот единственный элемент поместить после натурального ряда, то изоморфизма уже не будет, этот элемент будет тем, что называется.

Предложение 6.3.7. Функция сложения ординалов — единственная, удоГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ влетворяющая следующим рекурсивным уравнениям14 :

где ( ) — возрастающая ординальная последовательность ординалов.

Еще создатель теории ординалов Г. Кантор заметил, что каждое ординальное число однозначно разлагается по степеням, т. е. представляется в виде Польский математик К. Куратовский заметил, что в качестве основания разложения может быть взят любой ординал > 1 (опять полная аналогия с натуральными числами и системами счисления), но, считая -ичную систему самой удобной, предложил переопределить действия над ординалами в соответствии с действиями над натуральными числами, записанными в позиционной системе счисления. Определим сложение и умножение по Куратовскому и (см. [20]). Прежде всего разрешим нулевые коэффициенты, и тогда можно считать, что у двух чисел последовательности степеней i совпадают (в случае необходимости добавляем члены 0).

где (k ) — конечная, упорядоченная в порядке возрастания последовательность ординалов, представляемых в виде i j. Арифметика ординалов по Куратовскому обладает следующими свойствами:

Уравнение (определение функции) называется рекурсивным, если оно прямо или косвенно выражает значения функции через другие значения той же функции.

2. Обе эти операции ассоциативны.

Доказательство остается читателям.

Поскольку ординалы в основном применяются для оценок, а для оценок, как правило, удобство важнее точности, операции по Куратовскому все чаще применяются в литературе по информатике, вытесняя обычные операции над ординалами. Но, конечно же, бесплатно ничего не дается, и поэтому необходимо сделать следующее Возведение в ординальную степень по Куратовскому уже не определишь, поскольку базисные операции перестают быть непрерывными и к пределу не перейдешь.

Обратим внимание на еще одно важное свойство ординальных функций.

Определение 6.3.5. Функция из ординалов в ординалы f называется непрерывной, если она перестановочна с пределом последовательностей:

Не зря в данном определении употреблен тот же термин, что и в известном Вам определении из анализа. Если где-то появляется понятие предельного перехода, то появляется и понятие непрерывной функции, и многие другие понятия, которые образуют топологическую структуру (в частности, открытость, замкнутость, окрестность).

Теорема 6.3. (Теорема Веблена) Для любой непрерывной возрастающей функции ординалов f найдется неподвижная точка, т. е. такое f, что

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Доказательство. Рассмотрим следующую возрастающую последовательность:

Ее предел и является искомой неподвижной точкой, поскольку Эта теорема явилась первой из множества теорем о неподвижной точке, составивших в нынешнее время основу математической теории функционального программирования. Но, конечно, когда Веблен доказывал ее в 1912 г., он и не мог подумать о таком ее использовании. Зато Веблен прекрасно понимал ее приложимость к построению больших ординалов, намного б льших, чем 0, являющийся всего лишь наименьо шей неподвижной точкой функции.. Идеи такого построения см.

в упражнениях.

6.3.4. Построение функций рекурсией по определению либо параметру В приведенных выше рассмотрениях нам встречались примеры построения значений функций по трансфинитной индукции. Естественно, для построения значений можно применять и все остальные виды индукции. Функция, определяемая по индукции, в алгебраическом смысле определяется сама через себя (см., например, уравнения для ординального сложения (6.8)).

Вы скажете, зачем такие тонкости, ведь в языках программирования мы просто определяем функцию рекурсией саму через себя либо через другие функции. Да, в языке программирования так оно и записывается, но чтобы обосновать корректность такого определения15, приходится выявлять тот параметр либо то определение, по которому на самом деле Под корректностью здесь понимается не то, что транслятор не выдал ошибки, а правильная работа получившейся программы: она не зацикливается и не зависает, на приличных данных требует приличное количество ресурсов и времени и делает то, чего мы от нее хотели.

идет рекурсия. Сейчас мы ограничимся тем, что приведем заведомо корректные способы индуктивного построения функций по параметрамординалам (т. н. трансфинитная рекурсия).

Пример 6.3.2. Система рекурсивных уравнений определяет сложение натуральных чисел. Для сложения ординалов эту систему нужно пополнить еще одним уравнением:

Пример 6.3.3. Система рекурсивных уравнений определяет умножение натуральных чисел. Для умножения ординалов эту систему нужно пополнить еще одним уравнением:

Таким образом, вид трансфинитной рекурсии, соответствующий простой математической индукции, следующий:

Примитивная трансфинитная рекурсия Базис. Задаем f (0, x).

Шаг для непредельных ординалов. Определяем f (S, x) Шаг для предельных ординалов Определяем f (, x) как Параметры x, как видно из определения умножения, хотя и не участвуют в самой рекурсии, оставаясь фиксированными во всем определении, могут существенно использоваться при вычислении следующего значения f.

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Из самой формулировки примитивной трансфинитной рекурсии следует, что применима эта операция лишь для непрерывных функций, но, правда, и ведет она к непрерывным.

6.3.1. Вычислите lim sup N {}.

6.3.2. Проверьте недоказанные пункты из примера 6.3.6.

6.3.4. Всегда ли существует lim ?

6.3.5. Вычислите 2 и 2.

6.3.6. Имеет ли место закон дистрибутивности:

6.3.7. Проверьте, выполнено ли ( + ) = + 16.

6.3.8. Студент Талантов заявил, что оговорка насчет конечных кортежей совершенно излишняя и что множество вполне упорядочено лексикографическим порядком, если I и все Xi вполне упорядочены. Что Вы ему ответите?

6.3.9. Можно ли перенести ‘антилексикографический’ порядок на все ординальные последовательности?

6.3.10. А всегда ли 0 =1? А как насчет 0 ?

6.3.11. Докажите предложение Куратовского на стр. 164.

6.3.12. Можно ли обобщить операции по Куратовскому на ординальные последовательности операндов?

Подсказка. Здесь и в предыдущем упражнении рассмотрите ( + 1) ( + 1).

6.3.13. В одной работе как очевидное было упомянуть следующее тождество:

Проверьте эту ‘очевидность’.

6.3.14. Являются ли сумма и произведение по Куратовскому непрерывными по какому-то из аргументов?

6.3.15. Дайте рекурсивное определение суммы по Куратовскому.

6.3.16. Какая функция удовлетворяет следующим рекурсивным уравнениям: 6.3.17. Почему в определении сложения мы взяли произвольное, а не ограничились ?

6.3.18. Выведите формулу для наименьшей неподвижной точки непрерывной возрастающей функции ординалов f, превосходящей.

6.3.19. Пусть f — непрерывная возрастающая функция. Неперерывна ли функция, преобразующая в -тую неподвижную точку f ?

6.3.20. Для приведенных ниже пар ординалов вычислите +, +, 6.3.21. Вычислите ( + 1)n при возведении в степень по Кантору и по Куратовскому. Чему равно ( + 1) ? А почему здесь мы не упомянули два варианта умножения?

СИНТАКСИС ЛОГИЧЕСКОГО ЯЗЫКА

§ 7.1.

Синтаксис формального языка задает независимые от интерпретации определения объектов этого языка, изучает вопрос о структуре объектов, о распознавании объектов различных типов и их характеристик.

Синтаксически правильно построенные объекты могут в дальнейшем интерпретироваться и преобразовываться в соответствии с интерпретацией языка.

Чтобы обосновать применяемый в дальнейшем метод изложения, обратимся к практике как теоретических изысканий, так и их прикладного выражения — программирования.

Тот, кому приходится рецензировать достаточно много математических работ, знает, что чаще всего ошибочный переход в доказательстве кроется за словами «Очевидно» либо «Данный случай разбирается аналогично предыдущему». Ну, насчет “очевидности” все ясно1, а вот с аналогичностью приходится долго разбираться.

Тот, кому приходится программировать достаточно сложные (с точки зрения логики построения) задачи, сталкивается с неприятностью:

приходится писать множество почти одинаковых процедур для похожих друг на друга подзадач. Порою ситуация выглядит почти что издевательски: текст мог бы быть один и тот же, но изменяются типы данных и его приходится переписывать с другим заголовком процедуры и под другим именем.

Программист высочайшего класса, обладавший, вдобавок, в лучших русских традициях еще и фундаментальной математической подготовНа самом деле тут мы сталкиваемся с важным понятием дыры в доказательстве, которым нам придется заниматься далее. Но рецензенту здесь проще. Достаточно написать, скажем: «А мне неочевидно».

кой, Семен Фурман явно сформулировал следующий технологический прием2, который мы будем называть обобщение без потерь.

Пиши процедуру в частном, хорошо продуманном случае, и тщательно, но без лишней оптимизации, а затем обобщай ее на столь общий случай, насколько возможно без потери эффективности.

Скажем, появление функционального анализа и топологии позволило обобщить без потерь множество частных теорем Коши в несколько общих утверждений. Появление теории категорий позволило превратить расплывчатое понятие алгебраической аналогии в точное и затем использовать его, в частности, в теории абстрактных типов данных, призванной решить ту практическую трудность, которая была обрисована выше.

Мы проведем такую операцию обобщения для языка классической логики, с тем чтобы, в частности, не говорить расплывчатые слова “аналогично” при переходе к построенным по такому же принципу языкам неклассических логик. При обобщении мы выделим следующие черты логического языка:

• Более сложные конструкции образуются из более простых четырьмя способами:

– Применение одноместной (унарной) операции к выражению.

Эта операция ставится перед выражением.

– Применение двуместной операции к двум выражениям. Она ставится между выражениями, и получившееся выражение – Применение квантора, который включает подкванторное выражение и переменную, по которой он навешен. Этот пункт мы немедленно обобщим, чтобы включить и выражения вида Формулировка была дана в личной беседе с автором; нам неизвестно, опубликовал ли он что-либо по данному поводу.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Рассмотрим обобщенные кванторы следующей формы:

Выражения E1,..., Ek называются ограничениями подкванторной переменной, а A1,..., Al — подкванторными выражениями. Содержательно область действия подкванторной переменной распространяется лишь на подкванторные выражения, ограничения остаются вне ее • Выражения строго разделяются по типам (скажем, термы обозначают предметы, формулы — высказывания). Каждая операция применяется к выражениям строго определенных типов и однозначно определено, какого типа выражение получается после ее применения.

• Исходные понятия не фиксированы; заданы лишь способы образования более сложных из исходных.

Сразу заметим, что пункт, касающийся строгого разделения по типам, сплошь и рядом нарушается в современных языках программирования. Скажем, операция + применяется и к целым, и к действительным, и к комплексным числам различной точности. Такая перегрузка Именно разница между ограничениями и подкванторными выражениями приводит к встречающимся в математическом анализе выражениям вида В данной формуле верхнее x — свободная переменная, предел интегрирования, неизвестное нам, но фиксированное значение. В f (x) x имело бы тот же смысл, если бы оно не попало в контекст, ограничиваемый квантором dx. Вот это вхождение x (подкванторная переменная) в первую очередь влияет на понимание всех других возможных вхождений x в квантифицируемое выражение, именно оно заставляет x в f (x) пробегать все значения в интервале 0 xверхнее, и оно же делает эти две переменные абсолютно не имеющими друг к другу никакого отношения, кроме случайного (?) соxf впадения обозначений.

операций вызвала к жизни целую теорию разрешения возникающих неоднозначностей, да и мы, грешные, воспользуемся перегрузкой в нескольких местах, явно ее оговорив.

Пожалуй, Вам самим понятно, насколько коварным средством является перегрузка, но иногда она просто стучится в двери, если имеется полное совпадение необходимых нам свойств операций над различными данными. Разница между использованием перегрузки в логике либо алгебре и в искусственном интеллекте либо программировании состоит в том, что “теоретики” точно обосновывают сохранение необходимых свойств, а “практики” все время нарываются на неприятности, либо просто не дав себе труда уяснить и проверить эти свойства, либо забыв, что в алгоритмическом языке перегрузка применяется уже не к математическим сущностям, а к их неточным реализациям.

Другая особенность языка логики, принципиально отличающая его от имеющихся языков программирования и искусственного интеллекта, да и от языка, скажем, математического анализа, — отсутствие фиксированного базиса понятий. Если в “конкретных” языках нижний уровень закреплен как фундамент, на котором можно постепенно вырастить нужные нам построения, то в математической логике есть построения и преобразования, которые можно “опустить” на любой подходящий нам фундамент и, соответственно, сразу получить целый город.

Таким образом, с синтаксической точки зрения язык классической логики можно охарактеризовать как строго типизированный язык без нижнего уровня с функциональными, унарными и бинарными операциями и кванторами.

Прежде всего, поскольку выражения у нас делятся на типы, нужно определить необходимые нам конструкции над типами. Эти конструкции были введены польскими логиками в 20-х годах под названием синтаксических категорий. Мы изложим их в форме, принятой в большинстве современных работ по теории алгоритмических и других формальных языков, по философии и математической лингвистике.

Пусть задано некоторое множество исходных типов T0.

Определение 7.1.1. (Иерархия функциональных типов) Множество типов T задается следующим индуктивным определением:

a) Исходные типы T0 — типы.

c) Других типов в T нет.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Язык без нижнего уровня определяется относительно словаря, или сигнатуры рассматриваемого конкретного приложения (в случае логического языка — конкретной теории). Дадим наиболее общее понятие сигнатуры, базирующейся на иерархии типов T. Для этого сначала определим, какие типы из иерархии для каких целей подходят.

Определение 7.1.2. (Классификация типов) a) Тип (1,..., n ) называется типом функции, если все i, — b) Тип (1,..., n ) называется типом функционала, если содержит.

c) Тип (1,..., n ) называется высшим типом, если в нем больше одной.

d) Тип (1 ) называется типом унарной операции.

e) Тип (1, 2 ) называется типом бинарной операции.

Как и следовало ожидать, здесь наиболее сложен пункт, касающийся кванторов. Но вспомним уже известные нам кванторы. Разве, скажем, x имеет дело с отдельными значениями A(x)? Как обычно расплывчато выражаются математики и философы4, квантор имеет дело “со всей совокупностью значений выражения A(x)”. Всю эту совокупность значений лучше всего выражает функция, перерабатывающая каждое значение x в значение A(x). Соответственно, является здесь типом переменной x, каждое из j — типом соответствующего подкванторного выражения, зависящего от x. А вот типы ограничений берутся в “голом” виде, поскольку ограничения не подпадают под область действия переменной квантора.

Определение 7.1.3. (Обобщенная) сигнатура — множество символов s, каждому из которых сопоставлен один из признаков — константа, унарная операция, бинарная операция, квантор, и задана функция, Да и мы прибегли к подобному выражению при описании кванторных конструкций естественного языка.

сопоставляющая каждому s тип T таким образом, что операциям сопоставляются типы операций соответствующей арности, кванторам — типы кванторов.

Помимо сигнатуры, при определении языка с кванторами используют переменные. Чаще всего переменные бывают лишь по объектам исходных типов, да и то не по всем; если же у нас есть переменные и кванторы по типам, содержащим, то говорят, что определяемый язык высшего порядка. Переменные по различным типам не пересекаются.

Для единообразия переменные типа обозначаются x, y, z и т. д.

Cчитается, что переменных каждого типа потенциально бесконечный запас. Как обычно, если у нас всего один тип, по которому разрешено иметь переменные, тип переменных опускается. Подмножество типов, по которым имеются переменные, обозначается Tv.

Заметим одну тонкость в данном определении. Функциональные символы входят в число констант, они просто имеют тип функции. Могут быть и константы высших типов, они применяются в языке так же, как функциональные символы, но по крайней мере один из их аргументов либо же получаемое значение должны быть сложного типа. Приведем несколько примеров.

Пример 7.1.1. В теории групп исходные типы данных o — объекты, t — истинностные значения. Сигнатура состоит из логических связок, логических кванторов, бинарных операций =, и унарной Inv, константы e.

Их типы следующие.

Переменные имеются лишь по типу o.

Предикат = стандартно интерпретируется как равенство, константа e как единица группы, a b как умножение, Inv a как обратный элемент Пример 7.1.2. Можно несколько видоизменить сигнатуру из предыдущего примера, добавив к e еще две константы: Mult и Inv и удалив операции и Inv. Тип Mult есть (o, o o). Этот пример показывает возможность перехода между одноместными и двуместными функциями и операциями.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Пример 7.1.3. Фрагменты математического анализа можно описывать в языке со следующей сигнатурой:

Имеется три исходных типа: r, i, t, интерпретируемые, соответственно, как действительные числа, целые числа и логические значения.

Логические связки остаются теми же самыми.

Для работы с действительными и целыми числами имеются следующие бинарные операции: +,,, /,,,,, =r, >r, =i, >i и унарные Кроме того, зададим следующие константы: e,, 0, 1, 0, 1.

exp, sin, cos, ln, real, round.

Кванторы данной сигнатуры следующие: r, i, r, i,,. Типы всех перечисленных выше операций, констант и кванторов следующие:

Здесь видно, что мы вынуждены вводить кванторы всеобщности и существования по отдельности для каждого типа объектов, по которым имеются переменные. Поскольку тип квантора однозначно определяется типом переменной, следующей непосредственно за ним, перегрузка кванторов легко разрешается и используется практически везде, в том числе и нами. Аналогично перегрузка напрашивается и для общеупотребительных предикатов типа = или >, и для операций типа + или.

Но здесь ситуация намного сложнее, поскольку допущение перегрузки сразу приводит к соблазну перемешивать выражения разных типов.

Несколько иной тип перегрузки мог бы возникнуть при применении квантора суммирования к выражениям типа i. Здесь подкванторная переменная в любом случае имеет тип i, и разрешение двусмысленности зависит от типа подкванторного выражения. Это уже похуже, и на подобных примерах в теоретическом программировании выросла целая теория.

Теперь можно определить язык над обобщенной сигнатурой. Его выражения строятся из констант и переменных как обобщенные термы, обозначающие и предметы, и формулы, и многое другое. Они вводятся индуктивными определениями, задающими способы построения более сложных объектов через более простые. Синтаксис логического языка был первым местом, где осознанно использовался этот класс определений, ныне занимающий центральное место в формальных языках (в том числе в языках программирования и искусственного интеллекта).

Определение 7.1.4. Выражения типизированного языка с кванторами.

a) Константа c сигнатуры — выражение типа (c).

b) Переменная типа — выражение типа.

c) Если E1,..., En — выражения типов 1,...,n соответственно, E — выражение типа (1,..., n ), то E(E1,..., En ) — выражение типа.

d) Если A и B — выражения типов 1, 2, — бинарная операция сигнатуры, такая, что ( ) = (1, 2 ) то (A B) — выражение типа.

e) Если A — выражение типа 1, — унарная операция сигнатуры f) Если K — квантор сигнатуры, x — переменная типа, D1,..., Dk, E1,..., El — выражения типов 1,..., k, 1,..., l, соответственно, то Чтобы данное индуктивное определение было корректным, необходимо доказать единственность анализа выражений, т. е. что каждое выражение представляется в одном и только в одном из перечисленных видов и что соответствующие операции и компоненты определяются однозначно. Здесь это достаточно тривиально, поскольку мы использовали скобки во всех сомнительных случаях. Тем не менее доказательство однозначности будет проведено в следующем параграфе как для того, чтобы показать технику индуктивных рассуждений, так и для того, чтобы выявить некоторые неявные, но практически важные предположения.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Пример 7.1.4. В языке теории групп имеются следующие выражения:

(оно имеет тип o), (оно имеет тип t). Как говорилось в части 1, в математической логике выражения предметного типа называются термами, а выражения логического типа — формулами. В стандартной теоретико-групповой и логической записи первое и второе выражения представляются как соответственно.

Пример 7.1.5. Рассмотрим теперь, как представляются в нашей форме выражения языка математического анализа.

или же в обычной форме представления Из данных примеров видно, к чему приводит строгое различение типов. Случайно взяв не ту константу 1, мы вынуждены явно преобразовать ее к другому типу. Далее, показывается один из способов, как действовать с величинами, не попавшими в сигнатуру. 2 было просто представлено как (1+1). Анализируя определения и рассматривая примеры, можно сделать вывод, что мы не рассматриваем операции, кванторы и функции с переменным числом аргументов. Это соответствует и соглашениям большинства языков программирования, а там, где переменное число аргументов появляется, оно, как правило, влечет неприятности.

Далее, мы не разрешаем произвольным образом пополнять теорию новыми константами, что также находится, в частности, в соответствии с традициями языков спецификаций и языка Пролог. Конечно же, для расширения возможностей теорий и методов работы с ними мы обязаны предусмотреть средства расширения теорий, но это — отдельная и достаточно интересная тема, развившаяся в целую теорию в традиционной логике и приближающаяся к такому состоянию в математической. А чтобы квалифицированно применять теорию определений, мы обязаны уметь хорошо различать, что же можно выразить исходными средствами.

В искусственном интеллекте свободно вводятся подходящие сигнатуры для конкретных классов задач или даже отдельных задач. Например, для задачи, связанной с описанием родства, можно ввести предикаты Отец(a, b), Родственник(a, b). В таких формализациях константы соответствуют собственным именам.

В современной лингвистике вынуждены вводить весьма сложные типы данных для придания математического смысла таким, казалось бы, элементарным понятиям, как местоимения.

Переходим к доказательству формальных теорем.

КОРРЕКТНОСТЬ СИНТАКСИЧЕСКИХ ОПРЕДЕЛЕНИЙ

§ 7.2.

Предложение 7.2.1. Любое выражение типизированного языка однозначно представляется в виде, соответствующем пп. 1) – 6) определения 7.1.4.

Доказательство. Предложение опирается на следующие леммы о счете скобок.

Лемма 7.2.2. В любом выражении число открывающих скобок равно числу закрывающих.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Доказательство. Индукцией по построению. Переменные и константы скобок вообще не содержат. Если выражение A имеет вид F (t1,..., tn ), то, поскольку по предположению индукции все ti сбалансированы по скобкам, в нем также число открывающих равно числу закрывающих.

Точно так же для всех пунктов определения выражений.

Лемма 7.2.3. В любом начале выражения открывающих скобок не меньше, чем закрывающих.

Доказательство. Индукцией по построению выражения.

Определим скобочный баланс слова как число открывающих скобок число закрывающих.

Переменные и константы скобок вообще не содержат. Если t получен как f (t1,..., tn ), то любое его начало имеет одно из следующих представлений. Оно либо есть ‘f ’, либо имеет вид ‘f (’, либо ‘f (, i ’, либо ‘f ( i,’, либо есть сам t. Здесь есть последовательность выражений, разделенных запятыми, i есть начало выражения. По предыдущей лемме, в выражении открывающих скобок столько же, сколько закрывающих. Значит, скобочный баланс есть 0. По предположению индукции, скобочный баланс i 0. Следовательно, скобочный баланс начала больше 0, если оно не является f либо не совпадает с самим t.

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

Следствие. Начало выражения, содержащее скобку и сбалансированное по скобкам, совпадает с самим выражением.

Скобочным уровнем некоторого вхождения подвыражения в выражение называется число пар скобок, в область действия которых оно попадает. Таким образом, если выражение не имеет окружающих его скобок, то его уровень — 0, если имеет одну — 1, и т. д.

Лемма 7.2.4. Лемма о разделителях на первом скобочном уровне.

1. Если на первом скобочном уровне встречается символ ‘,’, то выражение является применением последовательности5 унарных операций к функциональному либо к кванторному выражению.

Возможно, пустой.

2. Если на первом скобочном уровне встречается символ ‘|’, то выражение является применением последовательности унарных операций к кванторному выражению.

3. На нулевом скобочном уровне ни запятая, ни | не встречаются.

Доказательство. Все три пункта доказываются одновременной индукцией по построению выражения.

В константу либо переменную ни скобки, ни запятая, ни | не входят.

Значит, базис индукции состоит из импликаций с ложной посылкой и тривиально верен.

Если выражение E является функциональным, то запятые, входящие в него, либо оказываются разделителями Ei и Ei+1, либо входят в Ei. В первом случае они оказываются на первом скобочном уровне, во втором, по предположению индукции, они оказываются не менее чем на первом внутри Ei, а значит, не менее чем на втором внутри самого E.

Символ | обязан входить в одно из Ei и, таким образом, ни на нулевом, ни на первом скобочном уровне не появляется.

Если выражение E является применением бинарной операции, то оно имеет вид (E1 E2 ). В нем, применяя предположение индукции, на первом скобочном уровне ни запятых, ни | не встретится, поскольку тогда они были бы вынуждены входить на нулевом уровне в E1 либо в E2. А то, что их нет и на нулевом уровне, видно непосредственно.

Если E получается применением унарной операции, т. е. имеет вид E1, то все сводится к рассмотрению E1, для которого все три пункта леммы выполнены по предположению индукции.

И, наконец, если E — кванторное выражение, то рассмотрение проводится аналогично пункту для функционального.

Теперь заметим, что любое выражение, более сложное, чем последовательность унарных операций, примененная к константе либо переменной, содержит скобки.

Докажем однозначность анализа выражений.

Пусть выражение построено применением бинарной операции (A B). Тогда оно не может представляться ни как функциональное, ни как применение унарной операции, ни как переменная либо константа, поскольку начинается со скобки. Остается исключить лишь случай применения квантора, что производится при помощи леммы о разделителях.

Кванторное выражение содержит | на первом скобочном уровне, а другие содержать его на этом уровне не могут.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Значит, оно может представляться лишь в виде (C D), где — бинарная операция. Если C совпадает с A, то это — то же самое представление. Если же оно не совпадает с A, то оно может быть либо началом A, либо включать в себя начало B. Если это начало A либо C содержит хотя бы одну скобку, то выражение не сбалансировано по скобкам и формулой не является. Таким образом, оба этих случая исключаются.

Значит, остается случай рассмотреть начало, не содержащее скобок и сводящееся к последовательности унарных операций, возможно, заканчивающейся переменной либо константой. Это сразу же исключает случай, когда C содержит начало B, поскольку “по дороге” оно прихватит и бинарную операцию. Если эта последовательность не заканчивается переменной либо константой, то она не является выражением, поскольку ни одно выражение унарной операцией не заканчивается. Остается единственный возможный случай — C является началом A, заканчивающимся переменной либо константой, до нее включающим лишь знаки бинарных операций и не совпадающим с самим A. Следовательно, A заканчивается функциональным выражением, поскольку лишь функциональное выражение начинается с переменной либо константы. Но в функциональном выражении непосредственно за начальной переменной либо константой следует открывающая скобка, а за C должна следовать бинарная связка. И этот случай приведен к противоречию, и рассмотрение бинарных операций закончено.

Случаи унарных операций, функциональных выражений и кванторов рассматриваются проще. Большую роль играет здесь лемма о разделителях, исключающая все нежелательные разбиения функциональных и кванторных выражений.

Конец доказательства теоремы.

Анализ доказательства позволяет сделать вывод, что обозначения для переменных, констант и функций должны четко отличаться друг от друга6.

В работах по логике часто встречается другое, специализированное для логического языка с одним типом объектов определение сигнатуры, Сделаем еще одно ехидное и важное замечание о приложениях математики. На практике теорема почти никогда не применяется в условиях, когда выполнена ее посылка, поскольку она просто не может быть в точности выполнена в реальном мире. Поэтому анализ доказательства необходим гораздо чаще, чем этого хотелось бы нам. Лишь он позволяет понять, когда же можно до некоторой степени полагаться на теорему вне области, где она была доказана.

которое интересно для нас используемым в нем способом задания.

Определение 7.2.1. Сигнатурой называется тройка непересекающихся множеств (P, C, F), где:

• P — непустое множество предикатных символов. Каждому предикатному символу (сокращенно предикату) P P сопоставляется его арность a(P ) — натуральное число, указывающее количество его аргументов.

• C — множество (возможно, пустое) констант.

• F — множество (возможно, пустое) функциональных символов, или функций. Каждой функции f F также сопоставляется ее арность Заметим, что логическое определение легко получается из общего специализацией7 и опусканием фиксированных частей (например, определений логических связок и кванторов).

Теперь рассмотрим еще один практически важный момент, вокруг которого в информатике к настоящему времени наросло немало теоретических работ. Мы заметили, что представление выражений в нашей форме заставляет писать много скобок. На практике порою пишут все скобки подряд8, но гораздо чаще стараются побольше скобок опустить, конечно же, без ущерба для понимаемости выражения и, не дай Бог, без того, чтобы допустить двусмысленность.

Например, в логических формулах скобки опускаются согласно следующим соглашениям.

1. Внешние скобки в формуле могут быть опущены.

2. применяется после & и.

3. Если подряд идет несколько одинаковых связок & либо, то скобки внутри данного выражения могут опускаться.

Специализация — фиксация конкретных значений неизменных в данном контексте переменных, сокращение в соответствии с контекстом областей значений других переменных и проведение после этого упрощений.

Особенно “отличился” в данном отношении язык ЛИСП. Там программисты уже просто запоминают, сколько скобок (например, пять) нужно ставить в начале и в конце того или иного стандартного выражения.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Таким образом, в первую очередь формула либо подформула в скобках делится на посылку и заключение импликации. Взаимное старшинство & и не фиксируется; здесь скобки необходимо использовать. Следовательно, формула читается “Из A и B следует C или D”, и наши сокращения согласуются также с грамматикой русского языка. Еще одно часто используемое сокращение — связка. (A B) определяется как (A B) & (B A) и читается “A и B эквивалентны”. Связка связывает так же слабо, как.

Итак, на данном примере мы видим, что некоторые бинарные операции считаются ‘сильнее’ других, но это отношение не является полным порядком: порою разные операции могут не сравниваться по силе и каждая из них требует скобок при сочетании с другой; далее, порою скобки опускаются внутри выражений с несколькими применениями одной и той же операции, скажем, A & B & C & D является сокращением и для ((A & B) & (C & D)), и для (((A & B) & C) & D), и для других подобных выражений. Но, конечно же, никому не придет9 в голову опускать скобки при сочетании нескольких, поскольку эта операция неассоциативна. Итак, ассоциативность операции кажется необходимым условием для того, чтобы опускать скобки в последовательности операций.

Здесь язык логики раскрывает еще одну ловушку, в которую легко угодить. Так и подмывает сейчас заявить, что скобки могут опускаться в последовательности любых ассоциативных операций. Но рассмотрим пример операции эквивалентности. Она в классической логике ассоциативна; в самом деле, постройте таблицу истинности для Но практически любой, увидев запись A B C, подумает, что она выражает равенство значений всех трех формул A, B, C. А формула, скажем, (A B) C истинна не во всех таких случаях и не только в таких, как можно убедиться, рассмотрев ее таблицу истинности.

(Пупышев В. В.):

— Тогда сам виноват!

(Автор):

7.2. КОРРЕКТНОСТЬ СИНТАКСИЧЕСКИХ ОПРЕДЕЛЕНИЙ Итак, математики понимают под A B C нечто совсем другое, а именно: (A B) & (B C). Бог им судья, но предусматривать такие несистематические “сокращения” мы просто не можем.

Итак, проанализировав практическое использование опускания скобок, мы приходим к любопытной структуре на бинарных операциях, промежуточной между строгим и нестрогим частичным порядком. Ее можно назвать частично нестрогим порядком. Это — транзитивное отношение, антирефлексивность которого опущена.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

Определение 7.2.2. (Формулы) a) Если P P — n-арный предикат, t1,..., tn — термы, то P (t1,..., tn ) — элементарная формула.

c) Если A — формула, x — переменная, то xA и xA — формулы.

Формула, входящая в другую формулу, называется ее подформулой.

Аналогично терм, входящий в другой терм, называется его подтермом.

Практическая работа Обучение работе с программой “Мир Тарского”. Нахождение синтаксических ошибок, работа с простейшими высказываниями (предложения Абеляра, Аккермана, Аристотеля, Буля, Бернайса, Бозо, де Моргана, Доджсона, Джона Рассела, Лестрейда, Людвига, Пирса, Уайтхеда, Шейнфинкеля, Шерлока, условные).

Упражнения к § 7. 7.2.1. Студент Чудаков использовал при формализации этнографического материала следующие предикаты:

удмурт(), отец(), жена(, ), брат(), Выскажите свои замечания.

7.2.2. Правильно ли сокращены формулы:

7.2.3. Что имел в виду студент, написавший:

7.2.4. Покажите, что опустив скобки вокруг кванторных выражений, можно получить неоднозначное представление.

7.2.5. Покажите, что после опускания скобок кванторные выражения остаются однозначными, если любой квантор содержит не более одного ограничения10.

7.2.6. Покажите, что ни одно типизированное выражение не может быть началом другого11.

СВОБОДНЫЕ И СВЯЗАННЫЕ ПЕРЕМЕННЫЕ.

ПОДСТАНОВКА

§ 7.3.

Как известно, статус переменных изменяется после того, как они связываются квантором. В формуле A(x) вместо x может быть подставлено конкретное значение, чего нельзя сделать в x A(x). Более того, одна и та же переменная может быть свободна для подстановок в некоторых местах выражения и связана кванторами (причем разными) в других.

Поэтому статус приписывается не самой по себе переменной, а ее конкретному вхождению в выражение (т. е. тексту выражения, в котором выделен один из экземпляров переменной). В свою очередь, если она связана, то мы должны указать конкретное вхождение квантора, воздействовавшее на данный экземпляр переменной. Все эти тонкости отражаются следующим определением.

Определение 7.3.1. (Свободные и связанные вхождения) 1. Вхождение переменной в переменную (т. е. в саму себя) свободно.

2. Если переменная x входит свободно (связанно) в A либо B, бинарный оператор, то соответствующее ее вхождение в (A также свободно (связано соответствующим квантором).

3. Если переменная y отлична от x, K — квантор, то ее вхождение в имеет тот же статус, что и ее вхождение в Ai, Bj.

Именно поэтому в логике предикатов обычно уже в исходном определении формулы опускают скобки вокруг кванторных выражений. То же делают в -исчислении.

Здесь есть скрытая ловушка в выражениях, начинающихся с унарных операций. Найдите ее. Ее не обойти без привлечения иерархии типов.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

4. Если x была связана в Ai, Bk, то она остается связанной тем же вхождением квантора в 5. Если x была свободна в Bj (x), то она становится связанной самым внешним вхождением квантора в 6. Если x была свободна в Ai (x), то она остается свободной и в Определение 7.3.2. (Замкнутые выражения) Переменная x называется свободной в выражении A, если у нее есть хотя бы одно свободное вхождение в A. Выражение A замкнуто (является постоянным12 ), если у нее нет свободных переменных.

Только замкнутые выражения могут иметь при интерпретации точно определенное значение, независимое от значений входящих в них переменных.

При установлении семантики важное значение приобретает операция подстановки, позволяющая подставлять конкретные значения свободных переменных. Ее определение требует аккуратности, поскольку связанные переменные считаются локальными. Поэтому свободные переменные, входящие в выражение, подставляемое вместо переменной, не должны быть связаны каким-либо квантором, и связанные переменные, оказавшиеся одноименными со свободными переменными подставляемого выражения, должны быть переименованы во избежание коллизии.

Неприятное явление коллизии было обнаружено почти сразу после того, как в математике появились первые кванторы — символы суммирования, произведения и интегрирования. Например, при попытке прямой замены переменной y на x + y в В случае формул говорят предложением.

получаем неверный результат Определение 7.3.3. Подстановка терма t вместо свободных вхождений переменной x в выражение E.

i) Если E есть константа c, то Subst(c, x, t) = c.

ii) Если E есть переменная y = x, то Subst(y, x, t) = y.

iii) Если E есть переменная x, то Subst(x, x, t) = t.

iv) Если E есть выражение F (t1,..., tn ), то vi) Если E есть B, где — унарная связка, то vii) Если E есть то рассматриваются следующие подслучаи:

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

c) x = y и y входит свободно в t (случай коллизии), то где z — переменная, отличная от x и не входящая в t.

Данное определение корректно, поскольку каждый раз мы ссылаемся на подстановку для выражений меньшей длины, чем исходная (хотя в пункте 7 и дважды). Оно не уточняет конкретного выбора переменной z в том же пункте, но это необязательно, поскольку связанная переменная должна пробежать весь универс. Более того, эта недоговоренность служит ключом к важному для приложений и самой логики понятию конгруэнтности выражений, отличающихся лишь заменой связанных переменных13 (обозначается A B).

Определение 7.3.4. (Конгруэнтность) Точнее, приводимых к одному и тому же виду заменами связанных переменных.

e) Если y — переменная того же типа, что и x, то Конгруэнтность введена таким образом, чтобы она являлась отношением эквивалентности и в результате замены в E одного конгруэнтного подвыражения на другое у нас получалось выражение, конгруэнтное E. При определении семантики логических языков практически обязательным является требование, чтобы конгруэнтные формулы были эквивалентны.

И наконец, одновременная подстановка термов t1,..., tn вместо переменных x1,..., xn в A обозначается Практическая работа Работа с программой “Мир Тарского”. Нахождение ошибок в определении свободных и связанных переменных и работа с более сложными высказываниями (предложения Бернштейна, Бозо, Клини, Финслера, Шейнфинкеля, Сколема). Преобразование предложений в конгруэнтную форму.

Упражнения к § 7. 7.3.1. Сколько переменных, имеющих различный смысл, в формуле 7.3.2. Подберите формулу, конгруэнтную предыдущей, и имеющую максимальное число различных переменных.

7.3.3. Подставьте x + y c в формулу из упражнения 7.3.1 вместо x.

ГЛАВА 7. ВВЕДЕНИЕ В СИНТАКСИС

7.3.4. Произведите замену x на x + y + z, y на x y в интеграле 7.3.5. Произведите замену x на x + y, y на x z и i на round(x) в выражении 7.3.6. Покажите, что могут быть две конгруэнтные формулы, из которых ни одна не преобразуется в другую подстановками одних связанных переменных вместо других, если при подстановках использовать лишь переменные, входящие хотя бы в одну из исходных формул (Подсказка: рассмотрите формулы. в которых переставляются одни и те же связанные переменные).

Глава 8. Семантика классической логики Любой формальный язык должен иметь точно определенные синтаксис и семантику. С точки зрения математики:

Семантика — отображение, сопоставляющее некоторым из синтаксически правильных объектов языка их значения при заданной интерпретации.

Таким образом, мы должны определить, во-первых, какие из синтаксических объектов являются интерпретируемыми и, соответственно, какие служат лишь для удобства преобразований интерпретируемых объектов; во-вторых, что является интерпретацией и как “вычисляется” значение объекта в интерпретации.

Семантика классической логики основывается на жестких эпистемологических допущениях:

1. Значение высказывания зависит лишь от значений его компонент, 2. Незнанием можно пренебречь либо рассматривать его как разновидность знания.

3. Свойства предметов неизменны, правила не имеют исключений.

4. Имеются лишь два логических значения — истина и ложь.

Это сопоставление отнюдь не обязательно эффективно вычислимо; чаще всего значения существуют лишь с математической точки зрения, но вычислены быть не могут.

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Удивительно то, насколько широка оказывается сфера применимости этих жестоких ограничений и насколько беспомощно выглядят попытки их умеренного ослабления, например, введением промежуточных истинностных значений2. Нижеследующие определения выражают перечисленные философские принципы. Для удобства истину мы часто будем обозначать 1 либо, а ложь — 0 либо.

С семантикой языка высших порядков дело обстоит не так гладко, как с синтаксисом и с семантикой языка первого порядка. Тем не менее мы можем задать интерпретацию в “стандартном случае”, который на самом деле скрывает немало подводных камней и уже не столь универсален, как синтаксис языка конечных порядков.

ИНТЕРПРЕТАЦИЯ ЯЗЫКА

КОНЕЧНЫХ ТИПОВ

§ 8.1.

Пусть F (A, B) — множество функций из A в B.

Определение 8.1.1. Интерпретация сигнатуры — функция, сопоставляющая каждому исходному типу множество значений U = ( ), каждому сложному типу = (1,..., n ) его универс каждой константе c C типа (c) ее значение из U (c), каждой операции и квантору — значение соответствующего типа.

Таким образом, в данной интерпретации задаются лишь значения исходных символов; значения сложных выражений вычисляются. Но для вычисления необходимо расширить сигнатуру, поскольку у нас просто может не найтись обозначений для элементов универса.

Вернее, тут стоит вспомнить дзэнское (точнее, чаньское) изречение:

Когда я не думал о просветлении, горы были горами и реки были реками. Когда я стал на путь к просветлению, горы перестали бытьь горами, а реки перестали быть реками. Когда я достиг просветления, горы опять стали горами, а реки — реками.

Многие глубокие и сильные предположения при поверхностном некритическом (либо в худшем смысле схоластическом, когда критикуют, но лишь чужое) взгляде кажутся очевидными; если начинаешь разбираться, поражаешься их смелости; а при еще более глубоком анализе они встают на свое место и становятся совершенно естественными, но зато ты уже знаешь их возможные альтернативы.

Определение 8.1.2. Сигнатура U — сигнатура, в которой множество констант пополнено обозначениями для всех элементов всех U, для всех Tv, т. е. типов, по которым имеются переменные. Константа, обозначающая элемент a, будет изображаться ca, или просто a, если это не вызывает недоразумений.

Определение 8.1.3. Значение замкнутых выражений сигнатуры U (обозначается (A))3.

4. (A B)) = ()((A), (B)).

То, что A истинна в M, обозначается M |= A, а то, что A ложна — M = A.

Предложение 8.1.1. В интерпретации M любое замкнутое выражение E имеет значение.

Доказательство. Индукцией по построению E.

Базис. Замкнутыми исходными выражениями могут быть лишь константы, которые имеют значения.

Функциональные выражения. Если E1,..., En имеют значения, то вычисляется и значение F (E1,..., En ). Таким образом, любой замкнутый терм имеет значение.

В данном определении придется воспользоваться -квантором для образования функции, перерабатывающей выражение E(x) со свободной переменной x в его значения при всевозможных x.

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Рассмотрим теперь конкретизацию общего определения интерпретации для сигнатур классической логики.

Определение 8.1.4. (Интерпретация логической сигнатуры ) Интерпретация сигнатуры — четверка M = (U, C, P, F), где:

U — непустое множество (называемое универсом).

C — функция, сопоставляющая каждой константе c C ее значение из P — функционал, сопоставляющий каждому предикату P P функцию из Un в {, }, где n — арность P.

F — функционал, сопоставляющий каждому функциональному символу f F функцию F(f ) из Un в U, где n — арность f.

Определение истинности следует таблицам истинности для пропозициональных связок и стандартному пониманию истинности для кванторов. Но оно полезно в следующих отношениях:

i) Точно определяется, как переносится интерпретация символов на более сложные объекты.

ii) Устанавливается, что говорить об истинности или ложности можно лишь для замкнутых формул и лишь в заданной интерпретации.

iii) Можно оценить количество операций, необходимых для вычисления логического значения формулы. Вычисление бескванторной формулы производится за n шагов, где n — количество логических связок. Для бесконечного универса и формул, содержащих кванторы, прямое вычисление требует бесконечного времени, и необходимо искать средства косвенной оценки значений формул.

Для конечного универса с n элементами и формул, включающих k этажей вложенных друг в друга кванторов, оценка числа действий есть nk. Таким образом, даже при небольшом n вычисление сложных формул оказывается слишком трудоемким, а при большом n (соответствующем, например, числу элементов в средней практической базе данных — порядка миллиона) уже вычисление формулы, содержащей два квантора x y, может оказаться непомерно долгим.

Предложение 8.1.2. В интерпретации M замкнутая формула A имеет значение Истина либо Ложь.

Доказательство. Индукцией по построению формулы. При этом достаточно проверить для каждого пункта определения истинности, что разобранные в нем случаи исчерпывающие и взаимно исключающие.

Например, для x A(x) либо при всех значениях x из U A(x) ложно, либо для какого-то из них оно истинно.

Практическая работа Работа с программой “Мир Тарского”. Работа со сложными высказываниями и их интерпретацией (предложения Вайнера, Монтегю, Поста, Рассела, Шредера, Цорна).

Упражнения к § 8. На интерпретациях из двух предметов, варьируя значение R, проверьте, всегда ли истинны следующие формулы:

8.1.1. x y R(x, y) y x R(x, y).

8.1.2. x y R(x, y) x y R(x, y).

8.1.3. x y R(x, y) x y R(x, y).

8.1.4. y R(y, y) x y R(x, y).

8.1.5. x y R(x, y) & y x R(x, y) x y(R(x, y) & R(y, x)).

8.1.6. Если универс — множество всех людей, Мать(x, y) означает, что x является матерью y, то верно ли утверждение y x Мать(x, y)?

8.1.7. Приведите пример формулы в сигнатуре из одного предиката R(, ), которая не может быть истинна ни на какой интерпретации с конечным универсом, но истинна при некоторой интерпретации с бесконечным.

8.1.8. Пусть an — последовательность действительных чисел. Когда верна формула ( > 0 n (n N & |an | < ))?

8.1.9. Пусть — функция из R в R. Когда верна формула

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

8.1.10. Пусть универс — множество натуральных чисел, >, + интерпретируются обычным образом. Для каких A(x) истинна формула 8.1.11. Аналогично предыдущему для x (A(x) y (y > x & A(y)))?

8.1.12. Аналогично предыдущему для 8.1.13. Для x y (A(y) & y > x) & x (A(x + 1) A(x))?

8.1.14. Для x (A(x) y (x > y & A(y)))?

8.1.15. Докажите, что M |= (A B) тогда и только тогда, когда A и B имеют одинаковые значения.

ТЕОРИЯ, МОДЕЛЬ, ЛОГИЧЕСКОЕ СЛЕДСТВИЕ

§ 8.2.

Формализация задается не только синтаксисом и семантикой формального языка (эти компоненты как раз чаще всего берутся традиционными, из хорошо известного крайне ограниченного набора), но и множеством утверждений, которые считаются истинными. Именно эта формулировка базисных свойств, аксиом, описывающих некоторую предметную область, обычно рассматривается как математическое описание объектов. Таким образом, практически всегда нас интересуют не все интерпретации данной сигнатуры, а лишь те из них, на которых выполнены аксиомы.

Определение 8.2.1. Теория Th — множество замкнутых формул сигнатуры. Если A Th, то A — аксиома Th. Модель Th — интерпретация, в которой истинны все ее аксиомы.

Пример 8.2.1. Теория отношения близости задается следующими аксиомами:

Любое отношение, удовлетворяющее этим аксиомам (например, заданное формулой |x y| < ), является отношением близости, т. е. рефлексивным и симметричным, и наоборот, любое отношение близости удовлетворяет этим аксиомам. Заметим, что чаще всего, несмотря на все старания, достичь такой идеальной ситуации просто невозможно: теория либо будет описывать не все имевшиеся в виду системы объектов и отношений, либо не только подразумевавшиеся. В математике стремятся избежать хотя бы первой неприятности. Поэтому для некоторых теорий принято говорить еще и о стандартных моделях, являющихся моделями в смысле нашего определения, но не исчерпывающих класса всех моделей4.

Определение 8.2.2. (Теоремы) Формула A является теоремой (или следствием) теории Th, если A истинна во всех моделях Th. B — следствие A, если B — теорема {A}. Отношение “A является теоремой Th” обозначается Th A. называется отношением логического следования.

Таким образом, истинность аксиом необходимо влечет истинность теорем. B — следствие A, если B истинно во всех моделях, в которых истинно A. Так, например, x A(x, x) — следствие x y A(x, y).

Предложение 8.2.1. (Свойства отношения ) Доказательство. Рефлексивность очевидна.

Транзитивность. Пусть M — модель Th. Если из Th следуют все аксиомы Th1, то любая из них истинна в M. Значит, M является и моделью Th1. Следовательно, M |= A. Таким образом, A истинна в произвольной модели Th и является теоремой Th.

Монотонность. Поскольку любая модель Th Th1 является моделью Th, теорема Th является и теоремой Th Th1.

Математические логики не были бы сами собой, если бы не извлекли из такой неприятности и новые положительные возможности. Мы показываем некоторые из них в гл. 10.

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Теорема дедукции. Пусть Th {A} B. Пусть M — произвольная модель Th. Тогда в ней либо истинна, либо ложна A. Разберем оба случая.

M |= A. Тогда M является моделью Th {A}. Следовательно, в ней истинно B. А поскольку ( ) =, в M истинна A B.

M = A. Тогда, поскольку из лжи следует все что угодно, M |= A Перечисленные в предложении 8.2.1 важнейшие свойства отношения следования были впервые систематизированы Тарским в 1930 г. Они выполнены не только для классической логики, но и для других традиционных логических систем. В самом деле, при доказательстве всех свойств, за исключением теоремы дедукции, мы даже не использовали классического определения истины. Достаточно лишь, чтобы теорема принимала значение истина во всех моделях теории и чтобы от добавления новых формул истинность не разрушалась (для монотонности). Поэтому Тарский счел возможным постулировать рефлексивность, транзитивность и монотонность как общие свойства отношения следования.

Теорема дедукции не включалась в стандартную аксиоматику следования, но рассматривалась (и рассматривается) как крайне желательное свойство, нарушение которого без фундаментальных причин служит показателем ущербности формализма.

В связи с необходимостью формализации сложных и нетрадиционных знаний в последнее время стали рассматриваться логики, нарушающие аксиоматику Тарского.

В частности, если наши ресурсы ограничены, то не всегда удается сохранить транзитивность (для получения аксиом Th1 может потребоваться столько “сил”, что на вывод B их уже не хватит).

Несколько другая ситуация с монотонностью. В жизни часто случается, что новое знание перечеркивает старое. Например, зная, что Маня вышла замуж за Ваню, мы заключаем, что она замужняя женщина, а узнав, что Ваня умер, мы заключаем, что она — не замужняя, а вдова5.

Эту ситуацию отразил польский логик и искусственный интеллектуал Ежи Павлак.

Попав в снежную бурю во время восхождения на гору как раз посредине скалы, он произнес стихотворение:

Biedna pani Pawakowa Weczor — zona, utrom — wdowa!

Для учета изменения фактов и выводов по умолчанию в искусственном интеллекте стали развиваться логики немонотонного вывода6.

И наконец, если наши действия необратимы (для этого достаточно, чтобы в рассмотрение было введено время), то не всегда целесообразно сохранять рефлексивность следования.

Вернемся к классической логике. Как видно, все, что следует из теории с пустым множеством аксиом, истинно в любой интерпретации и следует из любой теории данной сигнатуры. И наоборот, если теория вообще не имеет моделей, то из нее следует все, что угодно. Эти два важных частных случая отражаются следующим определением.

Определение 8.2.3. (Логика предикатов, тавтологии, противоречия) Логика предикатов сигнатуры — теория с пустым множеством аксиом.

Тавтология — теорема логики.

Противоречивая теория — теория, не имеющая моделей.

Противоречие — такая формула A, что {A} противоречива.

Формулы A и B логически эквивалентны, если A B — тавтология.

Итак, противоречие ложно в любой интерпретации. В противоречивой теории в любой интерпретации ложна хотя бы одна из аксиом.

Эквивалентные формулы имеют одинаковые значения в любой интерпретации.

Отметим несколько часто используемых отношения между интерпретациями.

Определение 8.2.4. Если M и N — интерпретации одной и той же сигнатуры, универсы M являются подмножествами соответствующих универсов N, интерпретации констант совпадают, а интерпретации функций и предикатов в M являются сужениями соответствующих интерпретаций в N, то M — подинтерпретация (соответственно, подмодель) N, а N — расширение (надинтерпретация, надмодель) M. В этом случае пишут M N.

Если все множества сигнатуры вложены в соответствующие множества из 1, то называется сужением (подсигнатурой, обеднением) 1, а 1 — расширением (обогащением, надсигнатурой). Обозначается 1.

Впрочем, первым их создал бразильский философ Ньютон да Коста для формализации рассуждений, базирующихся на противоречивых посылках.

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Интерпретация M сигнатуры является сужением (обеднением) интерпретации N сигнатуры 1, такой, что 1, если для всех понятий из интерпретации в M и N совпадают. В этом случае N называется обогащением M.

Семантика чаще всего определяет функцию, задающую значения формул в интерпретации.

Интерпретация называется моделью теории Th, если в ней истинны все аксиомы Th.

Семантика задает между теорией и формулой отношение, называемое семантическим следованием: формула следует из теории, если она истинна во всех ее моделях.

Основные свойства следования — рефлексивность, монотонность, транзитивность и теорема дедукции. Все они иногда нарушаются в современных неклассических системах, но для их нарушения нужны серьезные основания.

Чтобы применять классическую логику, необходимо быть уверенным как минимум в том, что имеющиеся ресурсы достаточно велики либо расходуемые достаточно малы, чтобы пренебречь их ограниченностью; что новое знание не может перечеркнуть старое, что мы можем пренебречь временем либо, по крайней мере, его необратимостью.

Практическая работа Работа с программой “Мир Тарского”. Работа со сложными высказываниями и их интерпретацией, составление многокванторных высказываний и миров, их опровергающих либо подтверждающих.

Упражнения к § 8. 8.2.1. Студентка Примерная задала теорию со следующей единственной аксиомой: x (A(x) B(x)). Опишите модели этой теории.

8.2.2. Следует ли из теории {x y A(x, y)} формула 8.2.3. Следует ли из теории {¬x yA(x, y), x A(x, x)} формула 8.2.4. Если множество констант есть {0, 1,..., n,... } для всех натуральных чисел, то следует ли из теории {A(0), A(1),..., A(n),... } 8.2.5. Рассмотрим теорию Q сигнатуры 0, S(), +(, ), (, ), = (, ), где 0 — константа, S, +, — функции, равенство — предикат, c аксиомами:

a) Показать, что множество натуральных чисел N c обычными b) Показать, что N является подмоделью любой модели Q.

c) Построить модель Q с универсом N {}, N.

d) Аналогично предыдущему с добавлением двух элементов.

e) Аналогично с добавлением бесконечного числа элементов.

f) Докажите, что x ¬(x = S(x)) не является теоремой Q.

8.2.6. Рассмотрим теорию OS со следующими аксиомами.

Противоречива ли данная теория?

8.2.7. Покажите, что всякая модель OS является обогащением модели теории частичного порядка. Почему данное упражнение практически независимо от предшествующего (точнее, почему нет условия «Если теория OS непротиворечива, то... »)?

8.2.8. Могут ли быть у теории OS конечные модели, если могут, то какие? От какого из предыдущих упражнений зависит данное?

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

ТЕОРЕМА О ЗАМЕНЕ ЭКВИВАЛЕНТНЫХ

§ 8.3.

Теорема 8.1. (Теорема о замене эквивалентных) Пусть A, B — формулы, имеющие одни и те же свободные переменные x1,..., xn, и — теорема Th. Пусть C{A} — формула с выделенным вхождением подформулы A; C{B} — результат замены в ней этого вхождения A на B. Пусть y1,..., yk — список всех свободных переменных C{A}. Тогда y1... yk (C{A} C{B}) является теоремой Th.

Доказательство. Индукцией по построению C.

Базис индукции. Если C элементарна, то C{A} есть A, C{B} есть B, свободные переменные C{A} — это x1,..., xn ; следовательно, есть сама Шаг индукции. Пусть теорема доказана для компонент C. Если A совпадает с самой C, то поступаем как в базисе индукции. Если же нет, то разбираем случаи, соответствующие построению C. Пусть C есть (C1 & C2 ). Тогда A входит либо в C1, либо в C2. В первом случае пользуемся тавтологией (4.50), во втором — аналогичной ей с перестановкой членов конъюнкции. Все остальные пункты определения рассматриваются подобно же.

Доказанная теорема может показаться слишком тривиальной, но рассмотрение неклассических логик показывает, как легко ее можно нарушить. Другое дело, что наличие свойства замены эквивалентных является весьма желательным для любой логики, а если уж его нет, надо подумать, чем его заменить. Например, можно ввести понятие “сильного отрицания”, когда предикат задается парой непересекающихся множеств — множества истинности и множества опровержимости. В этом случае эквивалентность формул не означает их взаимозаменяемости, поскольку при совпадении множеств истинности множества опровержимости могут различаться, но тогда можно доказать взаимозаменяемость таких формул A, B, что где — операция взятия опровержения формулы. Такие формулы естественно назвать сильно эквивалентными. Итак, если нарушается свойство замены эквивалентных, ищите, какую сильную эквивалентность нужно ввести для его спасения.

Упражнения к § 8. 8.3.1. Покажите, что формула является тавтологией.

БУЛЕВЫ АЛГЕБРЫ И

АЛГЕБРАИЧЕСКАЯ СЕМАНТИКА

§ 8.4.

Систему булевых операций можно охарактеризовать аксиоматически.

Определение 8.4.1. Булева алгебра — множество B c бинарными операциями, и унарной, удовлетворяющими следующим аксиомам:

Мы стремились не к формальной минимальности системы аксиом, а к их удобству. Очевидно, что аксиомам булевой алгебры удовлетворяет система всех подмножеств некоторого множества и, более того, любая алгебра множеств, т. е. система множеств, замкнутая относительно обычных операций объединения, пересечения и дополнения. Если определены пересечения и объединения произвольного (в том числе и бесконечного) множества элементов, то булева алгебра называется полной.

Теорема 8.2. (Теорема Стоуна о представлении) Любая булева алгебра изоморфна некоторой алгебре множеств.

В курсе математической логики эта теорема доказываться не будет.

Для нас важнее другое соотношение, установленное польскими логиками Линденбаумом и Тарским.

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Рассмотрим отношение Th A B. Оно транзитивно, рефлексивно, симметрично и, согласно теореме о замене эквивалентных, согласуется с логическими операциями. Таким образом, можно определить алгебру Линденбаума-Тарского теории Th как фактор-множество множества замкнутых формул сигнатуры по отношению Th Пересечению соответствует в ней &, объединению —, дополнению — отрицание. Отметим, что конструкция алгебры Линденбаума-Тарского переносится и на неклассические логики, лишь бы сохранялась теорема о замене эквивалентных.

Очевидно, что алгебра Линденбаума-Тарского классической теории является булевой. И обратно, любая булева алгебра может быть использована, чтобы интерпретировать классические теории.

Определение 8.4.2. Булевозначная модель сигнатуры — пятерка где B — полная булева алгебра, универс, константы и функции — как в двузначной модели, предикаты интерпретируются как функции из U n в булеву алгебру истинностных значений B. Определение значений формул аналогично определению истинности, соответствие операциям — как в алгебре Линденбаума-Тарского, квантору всеобщности соответствует бесконечное пересечение, квантору существования — бесконечное объединение.

Преимущество булевозначных моделей в том, что они дают возможность строить точные модели теорий, в которых формула истинна тогда и только тогда, когда она является теоремой. Двузначных точных моделей не удается построить даже для теории {A B, B C}. Заодно булевозначные модели развеивают предрассудок, что классическая логика предполагает наличие всего двух значений истинности. Хорошее и глубокое изложение взаимосвязи булевых алгебр с логикой можно найти в книге [26].

Классическая логика не обязательно требует двузначности интерпретаций. Достаточно, чтобы множество истинностных значений образовывало булеву алгебру.

Наоборот, если множество истинностных значений — булева алгебра, то логика данной интерпретации — классическая либо ее расширение дополнительными связками.

Любая логика (не только классическая), в которой есть свойство замены эквивалентных, задает для каждой теории свою алгебру логических значений — алгебру Линденбаума-Тарского, алгебру эквивалентных формул.

Для того, чтобы строить точную модель, в которой формула истинна тогда и только тогда, когда следует из аксиом, необходимо переходить к булевым алгебрам. Для этой цели двузначных моделей недостаточно.

Упражнения к § 8. 8.4.1. Построить булеву алгебру с четырьмя элементами.

8.4.2. Студент Интеллектуалов построил булеву алгебру с четырьмя элементами следующим образом: он взял диаграмму Эйлера и сказал, что изображенные на ней три множества плюс пустое составляют такую алгебру. Сравните его решение с Вашим.

8.4.3. Доказать, что отношение X Y = X (обозначается Y является отношением порядка в булевой алгебре.

8.4.4. Доказать, что в булевой алгебре имеются наибольший элемент и наименьший элемент 0.

8.4.5. Доказать, что в алгебре Линденбаума-Тарского единица соответствует классу всех теорем, ноль — классу всех противоречий.

8.4.6. Доказать, что (A B) тогда и только тогда, когда B A в алгебре Линденбаума-Тарского.

8.4.7. Доказать, что X Y является точной нижней гранью X и Y относительно определенного нами порядка.

8.4.8. Показать, что нет булевых алгебр с тремя элементами.

8.4.9. Построить точную модель для теории

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

8.4.10. Пусть A — алгебра, удовлетворяющая следующим аксиомам:

8.4.11. Чтобы непустое подмножество булевой алгебры было ее подалгеброй, достаточно его замкнутости относительно и.

8.4.12. Постройте булевозначную модель, в которой для некоторых A, B формула A B истинна, но ни одна из элементарных формул истинной не является.

8.4.13. Какое минимальное количество элементов должна иметь булева алгебра логических значений для точной модели теории 8.4.14. Можно ли для всех пропозициональных теорий в данной сигнатуре подобрать единую булеву алгебру, которая может служить алгеброй логических значений для их точных моделей? В каких случаях эту булеву алгебру можно взять конечной?

8.4.15. Во время математического боя студент Гениалькис, обосновывая свое решение, заявил, что поскольку булева алгебра B конечна, она полна. Ссылки на книгу, откуда он взял эту теорему, он не дал. Будете ли Вы опротестовывать его доказательство на основании данного утверждения?

ЯЗЫКИ ВЫСШИХ ПОРЯДКОВ

§ 8.5.

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