1 - Алгебра высказываний. Введение. Алгебра логики. Тавтологии и эквивалентность формул. Функции алгебры логики (Конспект лекций)

ÔÍ-12ÔÍ-12ÌÃÒÓМосковский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»ÌÃÒÓÀ.Í. ÊàíàòíèêîâÈ ÒÅÎÐÈß ÀËÃÎÐÈÒÌÎÂÊîíñïåêò ëåêöèéÔÍ-12Москва2009ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12Äëÿ ñòóäåíòîâ êàôåäðû ÈÓ9ÌÃÒÓÌÃÒÓÌÀÒÅÌÀÒÈ×ÅÑÊÀß ËÎÃÈÊÀÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ1. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-121ÌÃÒÓМатематическая логика — математическая дисциплина о законах правильного мышления.Можно выделить два первоисточника этой дисциплины. Первый — аристотелевская логика, представляющая собой науку о правильном построении суждений, о структуре сужденийи о построении умозаключений, т.е.

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

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

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

Неевклидова геометрия как раз и была создана как набор логических выводовиз системы аксиом, в которых вместо пятого постулата было взято его отрицание. Пытаясьприйти к противоречию, Лобачевский старался вывести пятый постулат из других аксиом, авзамен получил развитую логически непротиворечивую теорию.Создание неевклидовой геометрии — это первый поворотный момент в развитии аксиоматического метода (в литературе иногда именно это событие считают моментом созданияаксиоматического метода). Следующий поворотный момент на рубеже 19–20 вв. вызван открытием противоречий (их называют антиномиями) в теории множеств. Опять ситуация возниклаиз-за произвольного использования понятия бесконечности.

Интуитивно ясно, что противоречия возникают, когда о том или ином понятии судят, еще не определив его толком. ПарадоксРассела состоит в рассмотрении множества всех множеств, не принадлежащих самому себе. НоÔÍ-12ÔÍ-12Феномен математического доказательства. Теоремы и аксиомы. Аксиоматический метод иего развитие. Понятие исчисления. Цели формализации в математике.ÌÃÒÓÌÃÒÓ1.1. ВведениеÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓна бытовом уровне должно быть ясно, что для того, чтобы говорить о принадлежности какого-либо объекта множеству, этот объект должен быть однозначно определен. Значит, говоритьо принадлежности множества самому себе неправомерно.

Но тогда что такое множество, какдать формально строгое определение этого понятия, исключающее подобные парадоксы?Беда однако не приходит одна. Найденные парадоксы касаются не только множеств, но инекоторых определений. Парадокс Рассела можно квалифицировать как плохое определение“,”при котором объект определяется рекурсивно, через себя самого. Это говорит о том, что иприемы конструирования логических суждений, без которых математика невозможна, такжедолжны быть подвергнуты точному математическому исследованию. Основой для такого исследования явилась символика, подобная алгебраической, в которой математические сужденияи связи между ними записываются в виде математических формул. Эти формулы подчиняются определенным правилам преобразований и соединений, а логика может быть превращена внекую алгебру, подобную алгебре арифметических выражений или уравнений.Эти соображения привели к дальнейшему уточнению понятия аксиоматический метод“.”Аксиоматический метод — это формальное описание математический теорий, при котором всетеоремы теории являются логическим следствием аксиом, при этом содержательный смыслаксиом не является существенным: лишь такие следствия не были взаимоисключающими.Поскольку насчет правил логического вывода возникли разногласия, сами эти правила тожедолжны быть формализованы.

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

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

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

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

Метатеория формирует свой язык, расширяющий языкформальной теории, который называется метаязыком.ÌÃÒÓÔÍ-12ÌÃÒÓ2ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓВысказывания и их истинностные значения. Понятие логической операции. Логические операции ∨, ∧, →, ∼, ¬. Пропозициональные формулы: пропозициональные переменные и шагиндукции (X ∨Y , X ∧Y , X →Y , ¬X). Истинностные функции и пропозициональные формулы.ÔÍ-12ÌÃÒÓÔÍ-12Напомню, что под высказыванием понимается любое предложение, относительно которогоможно сказать истинно оно или нет, т.е. утвердительное предложение. Строго говоря, сказанноене следует рассматривать как настоящее математическое определение — лишь как указание нате реальные объекты, которые могут служить иллюстрацией к точной математической теории.Формирование предложений в естественном языке указывает на то, что высказывания могутобъединяться с помощью связывающих союзов.

С математической точки зрения эти союзыреализуют операции над высказываниями. В математической логике рассматривают толькотакие операции над высказываниями, для которых истинность результирующего высказыванияможно определить исходя из истинности исходных независимо от смысла этих высказываний,т.е. независимо от того, что именно утверждают эти высказывания.Вообще говоря, под операцией на множестве A понимают любое отображение ϕ: An → A,которое любому упорядоченному набору из n элементов множества A (кортежу) ставит в соответствие элемент того же множества. Натуральный показатель n называют арностью этойоперации.

Ясно, что множество всех операций на заданном множестве бесконечно, даже еслисамо множество конечно. Однако на практике ограничиваются операциями небольшой арности:унарными (n = 1), бинарными (n = 2), тернарными (n = 3). Кроме того, практическиеважные операции обладают определенными свойствами (например, свойство коммутативностидля бинарных операций).Ассоциация операция — функция“ наталкивает на мысль о введении нульарных операций”(функций без аргументов). С точки зрения математики нульарная операция — это постояннаяфункция или, иными словами, некоторый фиксированный элемент множества A.