Лекция 2. Элементы математической логики. Элементы математической логики
 Скачать 139.72 Kb.
|
|
Элементы математической логики Часто большинству из нас приходится делать выводы и заключе ния. На чем они основаны? На нашем опыте, интуиции. В любом случае, чтобы сделать вывод или заключение, необходимы исходные данные - посылки и правила - законы, которые обрабатывают исход ные посылки и выводят заключения. В повседневной жизни процесс вывода заключений происходит в большей степени подсознательно, интуитивно, в соответствии с на копленным индивидуальным опытом и, поэтому в существенной сте пени может иметь субъективный характер. Выводы или суждения, сделанные одним человеком в тех или иных ситуациях, могут частич но или полностью не совпадать с выводами и заключениями другого индивидуума. Тем не менее, все возрастающее число задач научной, технической и технологической направленности требует от нас однозначного при нятия решений или однозначного вывода заключений в соответствии с исходным набором посылок. К числу практически важных задач «логики» относится вывод или построение заключения на базе опре деленных правил в соответствии с исходными посылками. Термин «логика» про исходит от греческого слова логос, что означает «мысль», «разум», «слово», «понятие». Логика (или фор мальная логика) как наука изучает мышление. Но мышле ние изучается не только логикой, а и различными другими науками: психологией, физиологией, кибернетикой, педаго гикой и т. д. Каждая из них изучает какую-то одну из сторон сложного процесса мышления. Логика есть наука о законах и формах правильного мышления. Она изучает фор мы рассуждении, отвлекаясь от их конкретного содержа ния; устанавливает, что из чего следует, ищет ответ на воп рос: как мы рассуждаем? Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384-322 г. до н.э.). Он систематизировал известные до него сведения, и эта система стала впоследствии называться формаль ной или Аристотелевой логикой. Формальная логика просуществовала без серьезных изменений более двадцати столетий. Естественно, что развитие математики выявило недостаточность Аристо телевой логики и потребовало дальнейшего ее развития. Впервые в истории идеи о построении логики на математической основе были высказаны немецким ма тематиком Г. Лейбницем (1646-1716) в конце XVII века. Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам. Это позволит всякое рассуждение заменить вычислением. «Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, что бы облегчить сам процесс нашего мышления» (Лейбниц). Первая реализация идеи Лейбница принадлежит английскому ученому Д. Булю (1815-1864). Он создал ал гебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний. Введение символи ческих обозначений в логику имело для этой науки такое же решающее значение, как и введение буквенных обо значений для математики. Именно благодаря введению символов в логику была получена основа для создания новой науки — математической логики. Применение математики к логике позволило пред ставить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, малодоступных человеческому мышлению, и это, ко нечно, расширило область логических исследований. К концу XIX столетия актуальное значение для мате матики приобрели вопросы обоснования ее основных по нятий и идей. Эти задачи имели логическую природу и, естественно, привели к дальнейшему развитию мате матической логики. В этом отношении показательны работы немецкого математика Г. Фреге (1848-1925) и итальянского математика Д. Пеаво (1858-1932), кото рые применили математическую логику для обоснова ния арифметики и теории множеств. Особенности математического мышления объясняют ся особенностями математических абстракций и много образием их взаимосвязей. Они отражаются в логичес кой систематизации математики, в доказательстве ма тематических теорем. В связи с этим современную мате матическую логику определяют как раздел математи ки, посвященный изучению математических доказа тельств и вопросов оснований математики. Одной из основных причин развития математической логики является широкое распространение аксиоматичес кого метода в построении различных математических те орий, в первую очередь, геометрии, а затем арифметики, теории групп и т. д. В аксиоматическом построении математической тео рии предварительно выбирается некоторая система неоп ределяемых понятий и отношения между ними. Эти по нятия и отношения называются основными. Далее без доказательства принимаются основные положения рас сматриваемой теории - аксиомы. Все дальнейшее содер жание теории выводится логически из аксиом. Впервые аксиоматическое построение математической теории бы ло предпринято Евклидом в построении геометрии. Изложение этой теории в «Началах» Евклида не без упречно. Евклид здесь пытается дать определение исход ных понятия (точки, прямой, плоскости). В доказатель стве теорем используются нигде явно не сформулирован ные положения, которые считаются очевидными. Таким образом, в этом построении отсутствует необходимая логическая строгость, хотя истинность всех положений теории не вызывает сомнений. Отметим, что такой подход -к аксиоматическому пос троению теории оставался единственным до XIX века. Большую роль в изменении такого подхода сыграли ра боты Н. И. Лобачевского (1792-1856). Лобачевский впервые в явном виде высказал убежде ние в невозможности доказательства пятого постулата Ев клида и подкрепил это убеждение созданием новой геомет рии. Позже немецкий математик Ф. Клейн (1849-1925) доказал непротиворечивость геометрии Лобачевского, чем фактически была доказана и невозможность доказатель ства пятого постулата Евклида. Так возникли и были решены в работах Н. И. Лоба чевского и Ф. Клейна впервые в истории математики про блемы невозможности доказательства я непротиворечи вости в аксиоматической теории. Непротиворечивость аксиоматической теории явля ется одним из основных требований, предъявляемых к системе аксиом данной теории. Она означает, что из дан ной системы аксиом нельзя логическим путем вывести два противоречащих друг другу утверждения. Доказательство непротиворечивости аксиоматических теорий можно осуществить различными методами. Одним из них является метод моделирования или интерпретаций. Здесь в качестве основных понятий и отношений выбира ются элементы некоторого множества и отношения между ними, а затем проверяется, будут ли выполняться для выб ранных понятий и отношений аксиомы данной теории, то есть строится модель для данной теории. Так, аналитичес кая геометрия является арифметической интерпретацией геометрии Евклида. Ясно, что метод моделирования сво дит вопрос о непротиворечивости одной теории к проблеме непротиворечивости другой теории. Большинство интерпретаций для математических теорий (и, в частности, для арифметики) строится на базе теории множеств, в связи с этим важно доказать непротиворечивость теории множеств. Однако в конце XIX века в теории множеств были обнаружены противоречия (парадоксы теории мно жеств). Попытки устранить противоречия в теории множеств привели Цермело к необходимости построить аксиома тическую теорию множеств. Последующие видоизмене ния и усовершенствования этой теории привели к созда нию современной теории множеств. Однако средства этой аксиоматической теории не позволяют доказать ее не противоречивость. Другие методы обоснования математики были развиты Д. Гильбертом (1862-1943) и его школой. Они основывают ся на построении математических теорий как синтаксичес ких теорий, в которых все аксиомы записываются форму лами в некотором алфавите и точно указываются правила вывода одних формул из других, то есть в теорию как со ставная часть входит математическая логика. Таким образом, математическая теория, непротиво речивость которой требовалось доказать, стала предме том другой математической теории, которую Гильберт назвал метаматематикой, или теорией доказательств. В связи с этим возникает задача построения синтакси ческой, то есть формализованной аксиоматической тео рии самой математической логики. Выбирая по-разному системы аксиом и правила вывода одних формул из дру гих, получают различные синтаксические логические тео рии. Каждую из них называют логическим исчислением. XX век стал веком бурного развития математической логики, формирования многочисленных новых ее разделов. Были построены различные аксиоматические теории мно жеств, выработано несколько формализации понятия алго ритма, а сама теория алгоритмов была настолько развита, что ее методы стали проникать в другие разделы матема тической логики, а также в другие математические дис циплины. Так, на стыке математической логики и алгебры возникла теория моделей. Были созданы многочисленные новые неклассические логические системы. В XX веке началось глубокое проникно вение идей и методов математической логики в технику (и прежде всего в конструирование и создание ЭВМ), кибер нетику, вычислительную математику, структурную лингви стику. Математическая логика, или символическая логика, – это раздел математики, посвященный изучению математических доказательств и вопросов оснований математики. Простейший раздел математической логики – алгебра высказываний. Алгебра высказываний используется для решения математических задач, при написании программ и алгоритмов, разработке компьютеров, электронных устройств, автоматических систем. С применением законов алгебры логики создаются элементные базы, а на их основе создаются устройства, реализующие логические функции. Алгебра высказываний. 1. Высказывания и операции над ними 1.1 Понятие высказывания. Основным понятием математической логики является понятие «простого высказывания». Под высказыванием понимается предложение, представляющее собой такое утверждение, о котором можно судить, истинно оно или ложно. Логическими значениями высказываний являются «истина» и «ложь». Приведем примеры высказываний.
Высказывания 1), 3), 4) истинны, а высказывания 2), 5) ложны. Не всякое предложение является высказыванием. К высказываниям не относятся вопросительные и восклицательные предложения. Предложения «Математика – интересный предмет», «Осень – лучшая пора года» не являются высказываниями, так как нет единого мнения о том, истинны эти предложения или ложны. Предложения «Сегодня плохая погода», «3х<2» также не являются высказываниями, для того чтобы определить их истинность или ложность, нужны дополнительные сведения: конкретный день, о котором идет речь; значение, которое принимает х. Высказывания, представляющие собой одно утверждение, называют простым или элементарным. Из элементарных высказываний с помощью логических связок можно построить высказывания, называемые сложными или составными. Образование составного высказывания с помощью логической связки называют логической операцией. Из элементарных высказываний можно получить составные с помощью логических связок «не», «неверно, что», «и», «или», «если…, то…», «либо», «тогда и только тогда». Остальные логические связки либо близки по смыслу к каким-либо указанным, либо могут быть заменены их комбинацией. Например, союзы «а», «но» близки по смыслу союзу «и». Так, из элементарных высказываний «На улице светит солнце» и «В классе идут занятия» можно образовать следующие составные высказывания: «На улице светит солнце, и в классе идут занятия»; «В классе не идут занятия, а на улице светит солнце»; «На улице светит солнце, или в классе идут занятия»; «Если на улице светит солнце, то в классе идут занятия»; «На улице светит солнце тогда и только тогда, когда в классе идут занятия». В алгебре высказываний все высказывания рассматриваются не с точки зрения их содержания, а с точки зрения их истинности или ложности, то есть их логического значения. Каждое высказывание либо истинно, либо ложно, ни одно высказывание не может быть одновременно и истинным, и ложным. Истинное значение высказывания обозначают буквой и(истина)или символом 1, ложное значение – буквой л(ложь) или символом 0. 1.2 Логические операции над высказываниями. Над высказываниями определяются следующие основные логические операции, которые позволяют из имеющихся высказываний строить новые сложные высказывания: 1) отрицание (инверсия); 2) конъюнкция; 3) дизъюнкция; 4) импликация; 5) эквиваленция. Отрицание (инверсия). Отрицанием высказывания А называется новое высказывание, которое истинно, если исходное высказывание А ложно, и ложно, если высказы вание А истинно. Отрицание А обозначается  ( иногда обозначается А) и читает ся: «не А» или «неверно, что А». Логическое значение высказывания связано с логическим значением выска зывания А, как указано в таблице, которую называют таблицей истинности операции отрицания:
Примеры. 1. Для истинного высказывания «Число 24 делится на число 6» (А) отрицание будет ложное высказывание «Число 24 не делится на число 6» ( ) или «Неверно, что число 24 делится на число 6» (). 2. Для ложного высказывания «  » (А) отрицание будет истинное высказывание «Неверно, что », то есть высказывание « » ().Конъюнкция (логическое умножение). Конъюнкцией двух высказываний А и В, называется новое высказывание, которое истинно в единственном случае, когда истинны оба исходных высказыва ния, А и В, и ложно во всех остальных случаях. Конъюнкция высказываний А и В обозначается А /\ Вили А& В, читается «А и В». Высказывания А, В называются членами конъюнкции. Логические значения высказывания А /\ В, связанные с логическими значениями высказываний А и В, описываются таблицей, называемой таблицей истинности опе рации конъюнкции:
Примеры. 1. Для высказываний «Число 2 четное», «число 2 простое» их конъюнкцией будет высказывание «Число 2 четное и число 2 простое», которое будет истинным, так как истинны оба простых исходных высказывания. 2. Для высказываний «Омск находится на берегу Волги», «3+2=5» их конъюнкцией будет высказывание «Омск находится на берегу Волги и 3+2=5», которое будет ложным, так как ложно первое простое высказывание. Дизъюнкция (логическое сложение). Дизъюнкцией двух высказываний, А и В, называется новое высказывание, которое истинно в тех случаях, когда хотя бы одно из высказываний, А или В, истинно, и ложно в единственном случае, когда оба высказывания, А и В, ложны. Дизъюнкция высказываний А, В обозначается А \/ В и читается «А или В». Высказывания А, В называются членами дизъюнкции. Логические значения высказывания А \/ В, связанные с логическими значениями высказываний А и В, описываются таблицей, называемой таблицей истинности опе рации дизъюнкции:
Пример. Для высказываний «Число 28 делится на 7», «Число 28 делится на 5» их дизъюнкцией будет высказывание «Число 28 делится на 7 или на 5». Дизъюнкция высказываний есть истинное высказывание лишь в случае, когда по меньшей мере одно из входящих в дизъюнкцию высказываний истинно. Высказывание «Число 28 делится на 7» истинно, высказывание «Число 28 делится на 5» ложно , а дизъюнкция двух этих высказываний истинна. Импликация. Импликацией двух высказыва ний А и В, называется новое высказывание, которое ложно в единственном случае, когда высказывание А истинно, а В – ложно, а во всех остальных случаях – истинно. Импликация высказываний А, В обозначается  и читается: «если А, то В», или «из А следует В», или «А влечет В», или «А достаточно для В». Иногда импликацию обозначают символом  или  . В высказывании высказывание Аназывается условием или по сылкой , а высказывание В – следствием или заключением импликации. Логическое значение высказывания связанные с логическими значениями высказываний А и В, описываются таблицей, называемой таблицей истинности операции импликации:
Примеры. 1. Для высказываний «Число 28 делится на 7», «Число 28 делится на 4» их импликацией будет высказывание «Если число 28 делится на 7, то число 28 делится на 4». Так как высказывание-посылка «Число 28 делится на 7» истинно и высказывание-следствие «Число 28 делится на 4» истинно, то и составное высказывание на основании определения импликации также истинно. 2. Для высказываний «2+2=5», «2<3» их импликацией будет высказывание «Если 2+2=5, то 2<3». Так как высказывание-посылка «2+2=5» ложно, а высказывание-следствие «2<3» истинно, то составное высказывание на основании определения импликации истинно. Эквиваленция. Эквиваленцией (или эквивалентностью) двух высказы ваний, А и В, называется новое высказывание, которое истинно в том и только в том случае, когда одновременно оба высказыва ния, А и В, либо истинны, либо ложны, а в остальных слу чаях – ложно. Эквиваленция высказываний А, В обозначается  и читается «А эквивалентно В», или «для того, чтобы А, необходимо и достаточно, чтобы В», или «А тогда и только тогда, когда В», или «А равносильно В». Высказывания А, В называются членами эквиваленции. Логические значения высказывания , связанные с логическими значениями высказываний А и В, описываются таблицей, называемой таблицей истинности опе рации эквиваленции:
Примеры. 1. Для высказываний «Омск находится на берегу Волги», «2<3» их эквиваленцией будет высказывание «Омск находится на берегу Волги тогда и только тогда, когда 2<3». Так как высказывание «Омск находится на берегу Волги» ложно, а высказывание «2<3» истинно, то составное высказывание на основании определения эквиваленции ложно. 2. Для высказываний «9 делится на 4», «9 делится на 7» их эквиваленцией будет высказывание «9 делится на 4 тогда и только тогда, когда 9 делится на 7». Оба высказывания, к которым применяется связка «тогда и только тогда, когда», ложны. Поэтому все составное высказывание на основании определения эквиваленции истинно. 2. Формулы алгебры логики. 2.1 Формулы алгебры логики. С помощью логических операций над высказываниями из простейших высказываний можно строить высказывания более слож ные. При этом порядок выполнения операций указывается скобками. Например, можно построить такое высказывание: «Если Омск находится на берегу Волги и кислород – газ, то 2+3=5». Построенное высказывание символичес ки записывается так: (А /\В)  С. Это высказывание звучит странно, но нас интересует не содержание этого высказывания, а его логическое значение. Логическое значение составного высказывания может быть определено, исходя из логических значе ний исходных высказываний А, В, С и схемы по которой из исходных высказываний построено сложное выска зывание. Такая схема построения со ставного высказывания может быть применена к различ ным конкретным высказываниям, а не только к высказы ваниям А, В, С . Поэтому ее можно записать в виде (X/\Y) Z, где X, Y, Z–некоторые пере менные, вместо которых можно подставить любые элементарные высказывания. Перемен ные, вместо которых можно подставлять любые элементарные высказывания, называют высказывательными или пропозициональными переменными. С помощью высказывательных переменных и символов логических операций любое сложное высказывание можно формализовать, то есть заменить формулой, выражающей его логическую структуру. Эта формула называется формулой алгебры логики. Теперь сформулируем точное определение формулы ал гебры высказываний. Определение формулы алгебры высказываний. 1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний. 2. Если  и  – формулы алгебры высказываний, то выражения  ,  ,  ,  и  также являются формулами алгебры высказываний. 3. Никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1 и 2, нет. Для составления формулы сложного высказывания нужно: 1) выделить все элементарные высказывания и логические связки, образующие данное составное высказывание; 2) заменить их соответствующими символами; 3) расставить скобки в соответствии со смыслом данного высказывания. Для упрощения записи формул принят ряд соглашений: 1) скобки можно опускать, если над формулой стоит знак отрицания; 2) можно не заключать в скобки формулы, не являющиеся частями других формул; 3) скобки можно опускать, если придерживаться следующего порядка действий: первой выполняется операция отрицания, затем выполняется конъюнкция, дизъюнкция, импликация и эквиваленция. Пример. Формализовать составное высказывание «Две плоскости параллельны тогда и только тогда, когда они не имеют общих точек или совпадают». Выделим и обозначим элементарные высказывания, образующие данное составное высказывание: А: «Две плоскости параллельны»; В: «Две плоскости имеют общие точки»; С: «Две плоскости совпадают». Тогда данное высказывание в виде формулы записывается так:  .2.2 Таблица истинности. Логическое значение формулы алгебры логики можно определить, если вместо элементарных высказываний вставить символы их логических значений (0 или 1), а затем выполнить над этими символами последовательно все предписываемые формулой операции. Все вероятные логические значения формулы, в зависимости от комбинаций значений входящих в нее переменных, могут быть описаны полностью с помощью таблицы истинности. Пример. Составить таблицу истинности для фор мулы    . В первых двух столбцах таблицы выпишем всевозможные пары логических значений, которые могут принимать переменные X и Y (точнее, те высказывания, которые могут быть подставлены в формулу вместо переменных X и Y ). В последующих столбцах выписываем логические значения формул  ,  и  , пользуясь определениями логических операций импликации и эквиваленции. В результате получим таблицу:
Первые два столбца и последний столбец этой таблицы задают соответствие между логическими значения ми элементарных высказываний и логическим значением состав ного высказывания, получаемого по данной формуле. Эти три столбца образуют таблицу истинности данной форму лы. Остальные два столбца, для логических значений и , носят вспомогательный, промежуточ ный, характер.Если формула содержит nэлементарных высказываний, то таблица содержит  строк.3. Равносильные формулы алгебры логики 3.1 Классификация формул алгебры высказываний. Формула Х называется тождественно истинной (или тавтологией), если она превращается в истинное высказывание, то есть принимает значение 1, при всех наборах значений входящих в нее переменных. Тавтологии представляют собой схемы построения истинных высказываний, независимо от содержания и истинности составляющих элементарных высказываний. Формула Х называется тождественно ложной, если она принимает значение 0 при всех наборах значений входящих в нее переменных. Две формулы алгебры логики X и Y называются рав носильными, если при любых значениях входящих в них высказывательных переменных логические значения высказываний, получающихся из формул X и Y , совпадают. Для указания равносильности формул использу ют обозначение  . Существует тесная связь между понятием равно сильности формул и понятием тавтологии. Признак равносильности формул. Две формулы X и Y алгебры высказываний равносильны тогда и только тогда, когда формула  является тавто логией, и обратно, если формула – тавтология, то формулы X и Y равносильны.Отношение равносильности между формулами алгебры высказываний: а) рефлексивно:  ;б) симметрично: если , то  ;в) транзитивно: если и  , то  .3.2 Примеры равносильных формул. Равносильности формул алгебры логики часто называют законами логики. Вот наиболее важные из них:
 – коммутативность конъюнкции;  – коммутативность дизъюнкции.
 – ассоциативность конъюнкции;  – ассоциативность дизъюнкции.
 – дистрибутивность конъюнкции относительно дизъюнкции;  – дистрибутивность дизъюнкции относительно конъюнкции.
Доказать эти равносильности можно, например, с помощью таблиц истинности. Пример. Докажем равносильность  – закон де Моргана. При любых комбинациях значений, от которых зависят формулы X и Y , эти формулы принимают некоторые логические значения. Всего будет четыре способа распределения логических значений X и Y . Надо показать, что в каждом из этих случаев значения левой и правой части равносильности совпадают.
Логические значения в последних двух столбцах совпадают, следовательно, закон де Моргана справедлив. Имеют место равносильности, выражающие одни логические операции через другие. Импликация выражается через:
Эквиваленция выражается через:
Из этих равносильностей следует вывод, что любую формулу алгебры логики можно заменить равносильной ей формулой, которая будет содержать только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание. Дальнейшее исключение логических операций невозможно. Существует логическая операция, через которую можно выразить любую из пяти логических операций, которыми мы пользуемся: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Эта операция называется «штрих Шеффера», обозначается символом  и определяется таблицей истинности
Согласно таблице, имеем:  ;  .3.3 Равносильные преобразования формул. Используя равносильности, приведенные выше, можно заменить часть формулы или всю формулу равносильной ей формулой. Это преобразование называют равносильным преобразованием данной формулы. Равносильные преобразования применяются, прежде всего, для упрощения формул. Полученная в результате упрощений формула не должна содержать знаки и , отрицания неэлементарных формул, например, двойных отрицаний. Она должна содержать меньше, чем исходная, знаков конъюнкции и дизъюнкции.Равносильные преобразования формул применяются также для приведения формул к специальному виду или к специальной форме, к так называемой совершенной дизъюнктивной нормальной форме или к совершенной конъюнктивной нормальной форме. Отметим, что если некоторая формула является тавтологией, то и всякая равносильная ей формула также является тавтологией. Сделанное замечание позволяет обнаружить еще одну сферу применения равносильных преобразований: доказа тельство тождественной истинности тех или иных формул. Для этого данную формулу нужно равносильными преобра зованиями свести к формуле, очевидно являющейся тавто логией. Пример. Упростить формулу  .Запишем последовательность равносильных формул  Решение логических задач методами алгебры логики. Суть применения методов алгебры логики к решению логических задач состоит в том, что, имея конкретные условия логической задачи, стараются записать их в виде формулы алгебры логике. В дальнейшем путем равносиль ных преобразований упрощают полученную формулу. Простейший вид формулы, как правило, приводит к от вету на все вопросы задачи. |
– закон тождества.
– закон противоречия.
– закон исключенного третьего.
– закон двойного отрицания.
.
.
.
.
; 
– законы идемпотентности.
; 
– законы поглощения.
; 
– законы склеивания.
– законы де Моргана.
– дизъюнкцию и отрицание;
– конъюнкцию и отрицание.
– конъюнкцию и импликацию;
– конъюнкцию, дизъюнкцию и отрицание;
– конъюнкцию и отрицание.