 |
|
|
|
Странная формула. Часть 3. Правила хорошего тона
Странная формула Для передачи информации люди используют различные языки (письмо, жесты, рисунки и т.п.). В математике тоже существуют свои языки – они могут быть очень разными, но все используют принципы рассуждений, кодифицируемые математической логикой Когда кончается логика, начинаются ритуалы. Сериал «Доктор Хаус» (сезон 7, эпизод 8) Зачем вообще что-то доказывать Знаменитый трактат группы французских математиков, выступавших под псевдонимом Николя Бурбаки, начинается словами: «Со времен греков говорить «математика» значит говорить «доказательство». Выдающему физику Льву Давидовичу Ландау (1908-1968) приписывается (и не без оснований) афоризм, который в одном из вариантов звучит так: «Науки бывают естественные (биология, физика, химия, геология и проч.), противоестественные (преимущественно гуманитарные) и, наконец, математика». О противоестественных науках (в классификации Ландау) мы говорить не станем, поговорим о математике. Почему в математике столь высокие требования к точности, строгости и полноте умозаключений? Причина проста: математика оперирует абстрактными понятиями, т.е. понятиями, лишенными материального содержания (точками, прямыми, числами, множествами, функциями и т.п.). А раз нет материального содержания, значит, нет и экспериментальной (опытной) проверки, которая может подтвердить или опровергнуть ту или иную теорию. В естественных науках критерием истинности служит эксперимент: ставятся опыты и на основе полученных данных делается вывод об истинности или ложности теории по ее соответствию наблюдаемым эффектам. Если непосредственный эксперимент по каким-либо причинам невозможен, о правильности теории судят по косвенным данным (никаким зондом, щупом или телескопом невозможно заглянуть внутрь черной дыры, но оценить правильность теории можно по электромагнитным излучениям и поведению материи в окрестностях черной дыры). Математики, увы, всего этого лишены. Единственный критерий правильности их теорий – доказательство. А для того, чтобы доказательство было убедительным, оно должно быть исчерпывающе точным и полным. Несть числа доказательствам великой теоремы Ферма, и все они были отвергнуты, пока наконец Эндрю Уайлс в 1995-м не доказал ее; представленное им доказательство было тщательно исследовано ведущими специалистами в теории чисел и признано верным. Аналогичная ситуация случилась совсем недавно в топологии, когда российский математик Григорий Перельман решил исключительно сложную задачу – доказал гипотезу Пуанкаре. Некоторые теоремы, ранее не поддававшиеся усилиям математиков, удается доказать с применением компьютеров (такова, например, знаменитая гипотеза четырех красок о том, что любую карту на сфере можно раскрасить не более чем в четыре цвета так, чтобы любые две области с общей границей были окрашены по-разному). Многие математики принимают такие доказательства, но многие – нет. Это сложный вопрос, и каждый математик решает его для себя по-своему, но, по-видимому, дело идет к тому, что компьютерные доказательства (точнее, доказательства, полученные с использованием компьютерных расчетов и моделирования) будут приниматься все большим и большим числом математиков. Для того чтобы доказательства были полными, строгими и убедительными, нужно соблюдать определенные правила рассуждений. А без надлежащей формализации достичь этого невозможно. Всякая формализация начинается с определений. Дать емкое, по возможности краткое и точное определение не всегда легко. Очень важно, чтобы определение не ссылалось на самого себя (попробуйте, например, дать определение понятию «между», не используя и не ссылаясь на само это понятие). Многие понятия настолько первичны, что дать их удовлетворительное определение практически невозможно (таково, скажем, понятие «множество»). Может показаться, что требования формализации способов рассуждений лишают математику важнейших черт, присущих всякому творчеству, – фантазии и воображения, но, по счастью, это не так. Выдающий немецкий математик Давид Гильберт (1862-1943), больше чем кто-либо сделавший для формализации способов рассуждений, отозвался об одном из своих учеников, который оставил математику и стал поэтом, словами: «Ах, этот? Для математики у него было слишком слабое воображение». Без фантазии и творчества математика, как и любой другой вид интеллектуальной деятельности, давно бы выродилась и остановилась в развитии. Назначение математической логики (далее, для краткости, мы будем использовать просто слово «логика», подразумевая под ним именно математическую логику, т.е. логику, используемую в математике), краткий обзор которой представлен в этой статье, как раз и состоит в изучении принципов и способов рассуждений, применяемых в математике. Понятно, что охватить все, что есть в логике, в рамках журнальной статьи невозможно, поэтому мы рекомендуем читателю обратиться к библиографии в конце статьи. Вероятно, многое из того, о чем мы сейчас будем говорить, большинству читателей знакомо, но не зря говорят, что повторение – мать учения, поэтому не стоит пренебрегать мудрой поговоркой. Высказывания – содержательный подход Начнем с понятия «высказывание». Под высказыванием в логике понимается утвердительное (но не вопросительное и не побудительное) предложение, содержащее некоторую законченную мысль, оно может быть охарактеризовано либо как истинное, либо как ложное (другие значения истинности в классической логике, а мы говорим здесь только о ней, не допускаются). Это, разумеется, не может считаться строгим определением, но, по счастью, в математике это почти всегда так, а немногочисленные исключения (например, фразы вроде «окружность – это множество точек, равноудаленных от одной точки – ее центра») легко обнаруживаются и устраняются из рассуждений. Что общего между высказываниями «сумма углов треугольника на плоскости равна двум прямым углам», «кошка видит в темноте» и «скорость света в вакууме постоянна»? На первый взгляд – ничего, т.к. все эти высказывания относятся к различным областям (соответственно к математике, биологии и физике). Однако их объединяет то, что все они истинны, т.е. каждое из них выражает некий верный факт. Совершенно аналогично высказывания «2+2=5», «пингвин – млекопитающее» и «вечный двигатель существует» выражают некие ложные факты. Будем обозначать истину как «И», а ложь как «Л» (часто используются соответствующие английские буквы «T(rue)» и «F(alse)» или «1» и «0»). Вместо термина «высказывание» в логике часто употребляется термин «пропозициональная форма», но мы в дальнейшем будем использовать только первый термин, а именно «высказывание». Отдельные высказывания, каждое из которых имеет значение И или Л, называются элементарными высказываниями. Для обозначения таких высказываний мы будем использовать прописные латинские буквы (возможно, с индексами): A, B, C, ... X, Y, Z. Элементарные высказывания можно объединять в сложные высказывания посредством логических операций (связок) и получать тем самым формулы, напоминающие по структуре алгебраические. Начальный раздел логики, называемый исчислением высказываний, изучает свойства высказываний и формул, составленных из высказываний, безотносительно к их содержанию и смыслу и – это важно помнить – не учитывая то, как, собственно, само высказывание составлено, из чего высказывание состоит и как соотносится с другими высказываниями (это уже относится к исчислению предикатов). Высказывания (напомним, что речь идет о классической логике) подчиняются двум основным принципам:
Определения основных связок приведены в следующей таблице (таблица истинности), которая, безусловно, многим хорошо известна (см. таблицу 1). Таблица 1. Таблица истинности
Связки носят следующие наименования:
Первые четыре связки бинарные (т.е. связывают два высказывания), последняя – сингулярная. Часто используются и другие обозначения связок: например, вместо «&» пишут «∧», а вместо «→» пишут «⊃»; это надо иметь в виду, читая книги по логике. Легко подсчитать, что для двух высказываний возможны четыре варианта сочетания И и Л. В общем случае для n высказываний возможны 2n вариантов (попробуйте доказать это самостоятельно). Одним словом, высказывания представляют собой функции, определенные на множестве {И, Л} и принимающие значения в этом же множестве. Теперь несколько слов о равносильности высказываний. Высказывания называются равносильными, если они принимают одни и те же значения истинности при любых значениях входящих в них переменных. Рассмотрим, к примеру, формулы X→Y и ¬X∨Y и сведем их значения истинности в одну таблицу (проверьте) (см. таблицу 2). Таблица 2. Таблица значений истинности для выражений X→Y ¬X∨Y
Видно, что обе формулы принимают одинаковые значения при всех распределениях значений истинности переменных X и Y. Следовательно, эти формулы равносильны, что обозначается так: X→Y ≡ ¬X∨Y Понятие равносильности позволяет заменять одни части сложного высказывания равносильными им. Так, сложное высказывание: (A → B) & (C → D) можно преобразовать в равносильное высказывание, в котором обе импликации уже устранены: (¬A ∨ B) & (¬C ∨ D) В качестве упражнения постройте таблицу истинности и докажите, что оба приведенных сложных высказывания равносильны, т.е. принимают одни и те же значения истинности при всех комбинациях элементарных составляющих. В следующей таблице приведено несколько важных равносильностей (рекомендуем проверить их путем построения соответствующих таблиц истинности) (см. таблицу 3). Конечно, список равносильностей не исчерпывается этой таблицей, но эти – наиболее часто используемые. Таблица 3. Таблица важных равносильностей
Перед тем, как следовать дальше, укажем порядок старшинства связок, что позволяет сокращать в записи выражений количество скобок (аналогично тому, как это делается в арифметике, где умножение имеет более высокий приоритет, чем сложение): «¬», «&», «∨», «→», «~». Таким образом, высказывание (X&Y)∨Z можно записать просто как X&Y∨Z. Еще пример: вторая формула устранения эквиваленции из таблицы равносильностей может быть переписана в виде: X&Y∨¬Y&¬X. В то же время убрать скобки из первой формулы устранения эквиваленции уже нельзя. Вообще же, если есть сомнения в порядке старшинства связок, используйте скобки – они всегда помогут. Внимательно изучив равносильности, можно заметить, что для определения всех логических связок достаточно только двух: & и ¬ или ∨ и ¬, или → и ¬. Чуточку повозившись с равносильностями, можно преобразовать любую формулу исчисления высказываний в такую форму, в которой из связок будут присутствовать только две выбранные. Пусть, например, в качестве основных связок выбраны ∨ и ¬. Импликация X→Y, как мы уже убедились ранее может быть выражена через ¬X∨Y. Теперь нужно выразить конъюнкцию, для чего воспользуемся вторым законом де Моргана. Сначала заметим, что из этого закона следует, что: ¬¬X&¬¬Y ≡ ¬ (¬X∨¬Y) Проверьте! После снятия двойного отрицания в первой из формул окончательно получим: X&Y ≡ ¬ (¬X∨¬Y) Итак, импликация и конъюнкция могут быть выражены через ∨ и ¬. Остается только эквиваленция (оставляем читателю задачу выразить эту связку через пару ∨ и ¬ в качестве несложного упражнения). Таким образом пять исходных связок всегда можно свести к двум, одна из которых ¬, а другая – любая из &, → или ∨. Поскольку в любом высказывании число элементарных высказываний и логических связок конечно, то исчисление высказываний разрешимо; это означает, что существует способ (т.е. алгоритм) определения значения истинности любого сколь угодно сложного высказывания: все, что нужно, – построить соответствующую таблицу истинности. Но для сложных высказываний, включающих в себя множество элементарных высказываний, построение такой таблицы может оказаться технически очень сложным (например, для формулы, содержащей 10 элементарных высказываний, таблица истинности будет состоять из 1024 строк и проверка всех вариантов может занять много времени). Следовательно, нужен какой-то другой способ проверки истинности высказываний. Такой способ, действительно, существует и носит название нормальных форм. Нормальные формы бывают двух видов:
Первая нормальная форма называется конъюнктивной нормальной формой (КНФ), вторая – дизъюнктивной нормальной формой (ДНФ). Но сначала несколько слов о всегда истинных и всегда ложных высказываниях. Если построить таблицу истинности для высказывания X∨¬X, то легко убедиться, что это высказывание всегда тождественно истинно, т.е. всегда принимает значение И. Такие высказывания часто называют тавтологиями (термин введен австрийским логиком и философом Людвигом Витгенштейном (1889-1951), создателем знаменитого «Логико-философского трактата», вокруг которого уже почти 100 лет не стихают жаркие дискуссии и споры). Напротив, высказывание X&¬X всегда тождественно ложно; такие высказывания для краткости называют противоречиями. Очевидно, что отрицание тавтологии есть противоречие и наоборот. Вернемся к нормальным формам. Если каждый член КНФ (т.е. каждая дизъюнкция) истинна, то и вся КНФ, разумеется, истинна (т.е. является тавтологией). Следовательно, чтобы убедиться в том, что какое-либо сложное высказывание является тавтологией, надо преобразовать его в КНФ и просмотреть один за другим все его члены. Если все они тавтологии, то и КНФ – тавтология, а, следовательно, и исходное выражение – тавтология. Если хотя бы один член в КНФ – не тавтология, то и вся КНФ не тавтология, а, следовательно, и исходное выражение – не тавтология (хотя и не обязательно, что оно противоречиво). Схожим образом можно использовать ДНФ, с тем только отличием, что эта последняя «предназначена» не для проверки на тождественную истинность, а для проверки на противоречивость (читателю предлагается самостоятельно поразмышлять над этим). Мы не будем более останавливаться на нормальных формах, ни на том, как преобразовывать высказывания к нормальным формам: обо всем этом можно прочитать в любой приличной книге по логике (список некоторых из них приведен в библиографии к статье), к которым мы и отсылаем читателя. Заметим только, что приведение к нормальным формам начинается с устранения импликаций и эквиваленций; неоценимую роль в этих преобразованиях играет ранее приведенная таблица равносильностей. В целом преобразования высказываний в логике не многим сложнее алгебраических преобразований школьной математики. Метод истинностных таблиц, безусловно, надежен, нагляден и прост (не считая, конечно, собственно технических трудностей, вызванных необходимостью построения самих таблиц). Но этот метод не дает ответа на важный вопрос: «Какие в принципе высказывания могут быть построены, или, проще, сколько можно образовать различных высказываний?» Интуитивно видно, что их можно образовать очень и очень много. Достаточно, например, к любому высказыванию приписать тавтологию X∨¬X и вновь получить высказывание, равносильное исходному, и так до бесконечности. Ясно, что это, конечно, не решение, и мы никак не ответили на вопрос полноты исчисления высказываний. Далее метод истинностных таблиц не дает ответа на другой и, пожалуй, более важный вопрос непротиворечивости исчисления высказываний. Противоречивое исчисление позволяет вывести из исходных посылок тавтологию и одновременно отрицание тавтологии (т.е. противоречие). В противоречивых исчислениях мы, следовательно, не можем отличить истину от лжи, и эти исчисления ничего не описывают. Сложность в том, что, хотя любое отдельно взятое высказывание легко проверяется, нужен способ проверки множества всех высказываний. Метод истинностных таблиц, при всей его наглядности, не способен «справиться» с вопросами полноты и непротиворечивости, и нужно отыскать другие, более общие способы построения исчисления высказываний. Это необходимо для того, чтобы убедиться, что исчислением высказываний можно, во-первых, описывать возможно наибольший класс математических утверждений и, во-вторых, пользоваться им без опасений вывести из него противоречие. Такой способ построения математической теории существует и был открыт почти две с половиной тысячи лет назад великим математиком древности Евклидом. Это способ аксиоматического описания. Можно ли построить исчисление высказываний аксиоматически и что в итоге это даст? Появляются аксиомы Под аксиомами понимаются такие высказывания, из которых посредством правил вывода можно получить все остальные высказывания. Понятно, что в качестве аксиом должны применяться не произвольные высказывания, а лишь тождественно истинные (т.е. тавтологии). Кроме того, необходимо убедиться в том, что:
Первая удачная попытка аксиоматизации исчисления высказываний принадлежит немецкому математику Готлобу Фреге (1848-1925). Это имя, к сожалению, мало известно даже математикам, но без его многолетней и кропотливой работы, никак не оцененной большинством его современников, современная логика не получила того развития и значения, какие она приобрела. Хотя аксиоматика Фреге была не без недостатков (в частности, в ней были лишние аксиомы), а некоторые основные посылки оказались даже ложными (которые привели к знаменитому парадоксу Рассела в наивной теории множеств), она дала мощный толчок дальнейшим исследователям. В их числе следует упомянуть прежде всего Бертрана Рассела (1872-1970), чей совместный труд с Альфредом Уйтхедом (1861-1947) под названием Principia Mathematica составил целую эпоху и по праву считается одной из важнейших книг в истории математики. Не мог обойти своим вниманием аксиоматический подход и Давид Гильберт, предложивший (вместе с учеником Паулем Бернайсом) наиболее распространенную систему аксиом исчисления высказываний. Хотя есть и более компактные системы аксиом (у того же Гильберта), эта система наиболее наглядна и удобна в использовании. Cистема аксиом исчисления высказываний Д. Гильберта и П. Бернайса: A→(B→A) (A→(B→C))→((A→B)→(A→C)) A&B→A A&B→B (A→B)→((A→C)→(A→B&C)) A→A∨B B→A∨B (A→C)→((B→C)(A∨B→C)) (A→B)→(B→A) A¬¬→A ¬¬A→A Читателю рекомендуется путем построения таблиц истинности убедиться в том, что представленные аксиомы являются тавтологиями. Нужно иметь в виду, что все предложенные системы аксиом исчисления высказываний эквиваленты в том смысле, что каждая из них удовлетворяет перечисленным ранее требованиям и математик волен выбрать ту из них, которая ему кажется более удобной. Однако самих по себе аксиом еще недостаточно для того, чтобы строить исчисление; нужны еще и правила вывода, в соответствии с которыми из аксиом и уже доказанных с их помощью теорем выводить новые теоремы. О правилах вывода мы поговорим буквально через несколько строк, а пока выясним, что в логике (да и в математике в целом) понимается под доказательствами и теоремами. Доказательство – это последовательность (часто говорят «вывод» или «цепочка») утверждений, каждое из которых либо аксиома, либо одна или несколько ранее уже доказанных теорем. Теорема – это последнее утверждение в такой цепочке рассуждений. Исходным пунктом (своего рода «затравкой») доказательства служат, разумеется, либо аксиомы, либо ранее доказанные теоремы. Поскольку аксиомы и ранее доказанные теоремы – тавтологии, то выводимые из них следствия также тавтологии. Постепенно цепочка следствий удлиняется и удлиняется, а конечное звено этой цепочки и есть теорема. Схематично это выглядит как последовательность: A B C ... T где каждая из готических букв (так в логике, да и в математике обычно изображают понятия и объекты той или иной области без их конкретизации) означает либо аксиому, либо ранее доказанную теорему. Таким образом, начиная с A математик доводит цепочку к T; это последнее и есть теорема. Важно понимать, что аксиомы – тавтологии по определению (их истинность доказывается, например, таблицами истинности), а теоремы – тавтологии по доказательству (их истинность устанавливается путем построения цепочки выводов). Цепочка должна быть предъявлена другим математикам, и если они не находят в ней изъянов, сомнительных или недоказанных утверждений и ложных посылок, то вся эта цепочка считается подтвержденным доказательством, а последнее утверждение цепочки – теоремой. Именно так математика обеспечивает присущую ей строгость: доказательство должно быть предъявлено в явном виде, доступном всякому, кто желает его проверить. Любые сомнения должны быть устранены. Если хотя бы одно звено вызывает сомнения (не говоря уж о том, что оно может содержать ошибку), то теорема считается недоказанной. Вспомогательные или промежуточные результаты в цепочке доказательств обычно называются леммами, но никакой разницы между леммой и теоремой нет – и та, и другая обязаны соответствовать всем критериям строгости и точности: любая лемма с «изъяном» делает ничтожным все основанные на ней доказательства. И, наконец, небольшое замечание о терминологии: в книгах и статьях по логике вместо терминов «тождественно истинное» или «тавтология» (в исчислении высказываний) часто говорят о выводимых утверждениях. Правила вывода – это правила, указывающие, как можно применять ранее полученные теоремы (начиная с аксиом) для получения новых. Правил вывода в исчислении высказываний два – подстановка и правило заключения.
Этих правил вывода вместе с ранее приведенными аксиомами достаточно для полного и строгого построения исчисления высказываний. Правило MP поначалу может показаться слишком сложным и даже надуманным, но на самом деле оно подчиняется уже знакомым нам законам логики. Обосновать это можно следующим образом (доказательство от противного): Пусть посылка правила, т.е. A&(A→B) есть тавтология, и, следовательно, оба конъюнктивных члена имеют значение И. Допустим, что при некотором распределении букв, входящих в A и B, значение B равно Л., т.к. A – тавтология, т.е. имеет значение И, то A→B (согласно таблице истинности для импликации) принимает значение Л. Посылка, таким образом, принимает форму И&Л, что согласно таблице истинности равно Л, а это противоречит первоначальному предположению, что A→B – тавтология. Следовательно, B имеет значение И, что и требовалось доказать. В заключение раздела приведем небольшой пример, демонстрирующий использование правил вывода. Необходимо доказать, что формула A&B→B&A выводима в исчислении высказываний (конечно, ее можно доказать и с помощью знакомой уже таблицы истинности, но мы поступим новым способом). В списке аксиом имеется аксиома: (A→B)→((A→C) (A→B&C)) Заменим в ней A на A&B (т.е. подставим A&B на место A): (A&B→B)→((A&B→C)→(A&B→B&C)) Полученная формула остается выводимой. Посылка этой формулы (т.е. A&B→B) – аксиома. Согласно правилу MP мы можем заключить, что (A&B→C) (A&B→B&C) – выводимая формула. Произведем в последней формуле замену (подстановку) буквы C на букву A: (A&B→A)→(A&B→B&A) которая остается выводимой формулой. Вновь посылка формулы (т.е. A&B→A) – аксиома. Повторно применяя MP, окончательно находим, что A&B→B&A – выводимая формула, что и требовалось доказать. Кажется, что такой способ доказательства более сложен, чем простые и понятные истинностные таблицы. Может, это и так, но у нового способа есть совершенно неоспоримое преимущество: универсальность. С его помощью нетрудно доказать и полноту исчисления высказываний (т.е то, что можно породить все выводимые формулы), и его непротиворечивость, и независимость системы аксиом. Доказательства в исчислении высказываний обычно технически несложны, хотя порой и громоздки. Математики разработали много способов, упрощающих доказательства (все они – правила, производные от MP), но на этом мы останавливаться не будем. В заключение статьи мы кратко обсудим еще одно исчисление, представляющее собой дальнейшее развитие исчисления высказываний и имеющее почти непосредственное отношение к теме этого цикла. Предикаты Исчисление высказываний, как читатель только что мог убедиться, ставит и решает многие весьма интересные задачи. Однако у него есть существенные ограничения, которые обусловлены тем, что в исчислении высказываний невыразимы многие математические понятия. Это неудивительно, т.к. при разработке исчисления высказываний мы намеренно отказались от рассмотрения структуры составляющих высказывания частей и их отношений друг к другу: достаточно было только, что они могли иметь два истинностных значения И и Л и не более того. Исчисление высказываний не способно выразить даже такие простые (и, безусловно, необходимые) отношения, как, например, «больше» или «равно», а также рассуждать о совокупностях (множествах) величин и их свойствах. Без этого математика обойтись, конечно, не может, и поэтому логика нуждается в расширении. Это расширение производится путем введения понятия предикатов, или логических функций. Мы не будем давать строгих определений (библиография вам в помощь), а, как обычно, продемонстрируем основную идею на примерах. Предикат – это функция, принимающая значения на множестве {И, Л}. В отличие от функций исчисления высказываний, где аргументы могут принимать значения только из множества {И, Л}, аргументами предикатов могут быть любые объекты. Несколько примеров лучше продемонстрируют, что такое предикаты и чем они отличаются от высказываний. Пусть даны предикаты P(x), G(x,y), S(x,y,z). Аргументы всех предикатов – натуральные числа. Первый предикат P(x) является истинностной функцией, принимающей значение И, если ее аргумент – простое число, и Л в противном случае, т.о. P(3) и P(11) принимают значения И, а P(4) и P(100) – значение Л. Предикат от одного аргумента иногда называют свойством, т.к. такой предикат обычно характеризует какое-то свойство аргумента (в нашем примере это свойство «являться простым числом»). Второму предикату G(x,y) припишем значение И, если выполнено неравенство x<y, и Л в противном случае. Предикаты от двух аргументов обычно называются «отношение», поскольку они выражают связь (отношение) между своими аргументами. Третий предикат S(x,y,z) принимает значение И, если сумма x и y равна z, и Л в противном случае. Исчисление предикатов – это дальнейшее развитие исчисления высказываний и содержит исчисление высказываний как составную часть. Таким образом, в исчислении предикатов можно строить формулы, состоящие как из предикатов, так и формул исчисления высказываний: A→P(x), ¬F(x,y)&(C∨S(x,y,z)) и т.д. При разработке исчисления предикатов необходимо помнить о том, что аргументы логических функций уже не могут быть произвольными величинами. Например, ранее встречавшийся предикат P(x) имеет смысл, только если его аргумент (т.е. x) принимает значения из множества натуральных чисел. Этот предикат становится бессмыслицей, если попытаться применить его к рациональному числу, логическому значению или строке символов: P(0.625), P(И) или P(«теорема»). Давайте наведем небольшой порядок в обозначениях. Пусть M не пустое множество (безразлично, конечное или бесконечное): M = {a, b, c, ...}. Далее пусть P(x) – предикат, принимающий значение И или Л для некоторых элементов этого множества. Если, скажем, P(x) – это предикат, выражающий свойство «быть простым числом», а множество M – множество натуральных чисел больших 0, то легко видеть, что P(2)=И, P(3)=И, P(4)=Л и т.д. Под выражением ∃x P(x) понимается высказывание истинное, если существует элемент области M, для которого P(x) истинно, и как ложное, для которого P(x) ложно. Знак ∃x называется квантором существования. Под выражением ∀x N(x) понимается высказывание истинное, если предикат N(x) принимает значение И для всех элементов области M и Л в противном случае. Знак ∀x называется квантором всеобщности. Если, например, N(x) означает, что за каждым натуральным числом есть следующее на единицу большее (т.е. за 1 следует 2, за 2 следует 3 и т.д.), то, очевидно, на области M предикат истинен. Говорят, что в формулах ∃x P(x) и ∀x N(x) переменная x связана соответствующим квантором и называется связанной. Если переменная не относится ни к какому квантору, то она называется свободной. Например, в формуле ∀x G(x,y) переменная x – связанная, а переменная y – свободная. А вот в формуле ∀x ∃y G(x,y) обе переменные – связанные (каждая своим квантором), и формула читается так: «для всех x существует y, такой что G(x,y) истинно» (если, например, предикат G(x,y) означает, что для любого натурального числа x существует натуральное число y, большее, чем x). В отношении кванторов существования и всеобщности надо твердо помнить следующее. Квантор существования говорит о том, что существует по крайней мере один элемент из области M, для которого предикат (логическая функция) принимает значение И. Таких элементов может быть и не один (в предельном случае – даже все элементы области), но он обязательно должен быть (принцип «хотя бы один»). Квантор всеобщности говорит о том, что для всех элементов из области M предикат (логическая функция) принимает значение И. Если хотя бы для одного-единственного элемента из области M этот предикат принимает значение Л, то он тождественно ложен (принцип «все или ничего»). Кванторы ∀x и ∃x не являются независимыми. Несложное логическое рассуждение, оставляемое в качестве интересного упражнения, показывает, что эти кванторы связаны соотношением ¬∀x A(x) ≡ ∃x ¬A(x) Таким образом, можно в качестве основного выбрать любой из кванторов; тогда переход к другому квантору осуществляется в соответствии с указанной равносильностью. Для исчисления предикатов основной проблемой является проблема разрешимости: указать способ (алгоритм) для определения по произвольной формуле исчисления предикатов, выполнима она или нет. В отличие от исчисления высказываний, где эта проблема решается элементарно (например, путем составления таблицы истинности или приведения к КНФ), в исчислении предикатов возникают существенные трудности. Сразу же скажем, что в общем случае (для предикатов с числом переменных, большим одной) эта проблема неразрешима. Это был самый первый пример доказательства неразрешимости проблемы в математике, и этот результат (полученный с разницей в несколько месяцев американцем Алонсо Черчем (1903-1995) и англичанином Аланом Тьюрингом (1912-1954) в 1936 году) оказал сильное влияние на математику. Выяснилось, что в математике можно доказать, что для той или иной проблемы не существует алгоритма решения в общем виде. Частные случаи иногда имеют решение, но общий случай – нет. Для предикатов с одной переменной проблема разрешения решается положительно, т.е. можно указать алгоритм (говоря современным языком – написать программу), который за конечное время выдаст ответ, выполнима ли данная формула исчисления предикатов или не выполнима. Здесь основная заслуга принадлежит немцу Леопольду Левенгейму и норвежцу Торальфу Сколему. Доказательство этого факта (со всеми необходимыми предварительными результатами) технически не сложно, но довольно громоздко и заинтересованный читатель может найти его в любой книге из библиографии к статье. Так ли важны для математики предикаты более чем с одним аргументом? Да, и причина в том, что предикаты с одной переменной не способны описать все математические утверждения. Предикаты с одной переменной вполне пригодны для описания свойств математических объектов (например, «быть простым», «являться элементом множества», «иметь предел»), но их никак не достаточно для описания отношений между объектами (например, «больше», «следует за», «делиться на»). Предикатов с двумя переменными уже достаточно для формализации всей математики, но, как указывалось чуть выше, для таких предикатов проблема разрешимости не имеет решения. Плохо это или хорошо? По-моему, все-таки хорошо. Это означает, что в математике всегда будут существовать трудные, но интересные задачи, для решения которых нужна не только техника владения теми или иными понятиями, но и творчество, и фантазия. *** На этом, пожалуй, мы и закончим. Следующая статья цикла будет проще первых и посвящена программированию одного небольшого компьютера. Аннотированная библиография Существует и легко доступно немало хороших книг по математической логике. Ниже приводится список некоторых из них (расположены в порядке возрастания сложности). Читатель должен иметь в виду, что математическая логика оперирует довольно абстрактными понятиями, и приготовиться к серьезной работе. Новиков П.С. Элементы математической логики. – Превосходный учебник для начинающих, написанный крупным советским математиком, решившим ряд сложных проблем в математической логике и теории множеств. Рассматривается не такой широкий круг вопросов, как в книге Мендельсона (см. далее), но зато детально и зачастую «на пальцах». Клини С.К. Математическая логика. – Книга написана одним из создателей современной логики и теории рекурсивных функций (о них у нас еще пойдет речь). Является переработкой лекций, прочитанных автором в ряде университетов. Упражнений немного, но все они содержательные. Круг рассматриваемых вопросов не очень широкий, но то, что рассматривается, рассматривается до мельчайших деталей. Мендельсон Э. Введение в математическую логику. – Классический и поистине неувядающий учебник. Изложение сжатое, что может представлять известные трудности для начинающих. Много упражнений (в основном простых, но встречаются и действительно трудные). Можете использовать любое издание, кроме первого, в котором немало досадных опечаток. Черч А. Введение в математическую логику. – Необычная и чрезвычайно глубокая книга одного из корифеев этой области математики. Множество очень интересных мыслей и оригинальных способов подачи материала. Много упражнений. Чтение затрудняется тем, что значительная часть содержания вынесена в примечания, и читатель вынужден постоянно «скакать» по книге и держать две закладки: в основном тексте и в примечаниях. Лучше все-таки читать после более традиционных курсов. Шефердсон Дж. Математическая логика. – Фундаментальный курс, охватывающий практически все аспекты, включая теорию множеств и рекурсивные функции. Книга сложная и насыщенная. Часть материала вынесена в упражнения, которые нужно решать, иначе дальнейшее изложение станет непонятным. Для начинающих мало пригодна, но для освоивших любую из ранее указанных книг – очень полезна.
Ключевые слова: математическая логика, логические операции, предикаты. |
АЛЕКСЕЙ ВТОРНИКОВ, ведущий программист, ЗАО КБ «Ростовский Универсальный», Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
