Высшая математика Питерцева. высшая математика питерцева. Курс лекций для дистанционного обучения студентов гуманитарных специальностей москва 2012 Авторы составители
 Скачать 2.77 Mb.
|
1.2. Алгебра высказываний. Основные законы математической логики.Высказывание. Простые высказывания. Составные высказывания. Операции отрицания, конъюнкции, дизъюнкции, эквивалентности, импликации. Порядок старшинства операций. Основные законы математической логики. Парадоксы логики, или семантические парадоксы Что есть высказывание. Под высказыванием понимают всякое утверждение, о котором имеет смысл говорить, что оно истинно или ложно. Например, « » или «В неделе семь дней» - истинные высказывания, а « » или «В современном русском языке 35 букв» - ложные высказывания. Высказывания могут быть образованы с помощью слов или символов. Синонимами слова «высказывание» считаются «логическое высказывание», «булевское выражение», «суждение» и «утверждение». Однако далеко не каждый набор слов или символов, даже, на первый взгляд, осмысленный, является математическим «высказыванием». Например, фразы: «Ура, у нас математика!» или «Который час?» или выражение « » высказываниями не являются, т.к. судить об их истинности или ложности невозможно. Таким образом, каждое математическое высказывание или истинно, или ложно; одновременно быть и истинным и ложным высказывание не может. Если высказывание истинное, то ему предписывается значение «истина» (другие обозначения: «1», «ДА», «И», «+», «true»). Ложному высказыванию предписывается значение «ложь» (другие обозначения: «0», «НЕТ», «Л», «-», «false»). Для обозначения высказываний обычно используют заглавные буквы латинского алфавита A, B, C и т.д. Например, пишут , . Это означает, что высказывание В заключается в утверждении, что число 6 – простое, а высказывание А – в том, что . Знак заменяет слова «есть высказывание», или «тождественно равно». Простые и составные высказывания. Есть два вида высказываний: 1) простые и 2) составные, или сложные. Под простым высказыванием будем понимать такое высказывание, которое не может быть разбито на более простые высказывания. Высказывания А и В предыдущего примера – простые высказывания. Про простое высказывание всегда однозначно можно сказать, что оно истинно или ложно, не интересуясь его структурой. Из простых высказываний при помощи так называемых логических связок или логических операций, например, союзов «и», «или», слов «если…, то…», «тогда и только тогда, когда…», можно строить сложные высказывания. Например, из высказываний ; , используя логические операции, можно образовать следующие сложные высказывания: , , . Отметим, что сложные высказывания можно образовывать и из таких высказываний, которые не связаны между собой по смыслу. Например, высказывание: {если слон – насекомое, то Антарктида покрыта тропическими лесами} составлено при помощи логической операции «если…, то…» из двух высказываний, между которыми нет никакой смысловой связи. Сложные высказывания, как и простые, всегда или только истинны, или только ложны. Истинность или ложность сложного высказывания полностью определяется, во-первых, тем, какие логические связки (операции) использованы для образования сложного высказывания. Во-вторых, истинность или ложность сложного высказывания определяется тем, какие из простых высказываний, образующих сложное высказывание, истинны, а какие – ложны. Логические операции Операции над высказываниями – логические операции – обычно задают в виде таблиц, называемых таблицами истинности. Операция отрицания, или отрицание высказыванияДля каждого высказывания А может быть сформировано новое высказывание (читается «не А», или «не верно, что А») – это отрицание высказывания А. Высказывание истинно, когда А – ложно, и ложно, когда А – истинно. Таблица истинности для операции отрицания:
Отрицание – одноместная, или унарная, операция. Последующие операции – двухместные, или бинарные. Например, если - истинное высказывание, то - ложное высказывание (отрицание А). Отметим, что если {в комнате холодно}, то {в комнате не холодно}, но при этом высказывание {в комнате жарко} отрицанием В не является. Операция конъюнкции, или конъюнкция высказываний.Высказывание С, составленное из двух высказываний А и В при помощи союза «и», называют конъюнкцией (логическим произведением) этих высказываний: (выражение читается: «А и В»). Логическое произведение истинно только в том случае, когда и А, и В одновременно истинны. Таблица истинности для операции конъюнкции:
Пусть, например, , . Тогда высказывание С– истинно, т. к. истинно каждое из высказываний А и В, составляющих высказывание С. Операцию конъюнкции можно определить и для нескольких высказываний, как связку высказываний, объединённых союзом «и». Конъюнкция из n высказываний – новое высказывание, причём высказывание А = Аi ; где i = 1; 2; …; n имеет значение «истина», если и А1, и А2, и … Аn одновременно истинны. Во всех других случаях эта конъюнкция имеет значение «ложь». Пусть, например, А1 , А2 , А3 , А4 . Тогда высказывание А2 А3 А4 {(8 = 3) и (отец старше сына) и (Мурманск севернее Смоленска)} – ложное, в то время как высказывание А1 А3 А4 {(5 > 3) и (отец старше сына) и (Мурманск севернее Смоленска)} – истинное. Операция дизъюнкции, или дизъюнкция высказываний.Высказывание С, составленное из двух высказываний А, В при помощи союза «или», называют дизъюнкцией (логической суммой) этих высказываний: (выражение читается: «А или В»). Сумма является истинным высказыванием тогда, когда, по крайней мере, одно из слагаемых истинно. Таблица истинности для операции дизъюнкции:
Пусть, например, , . Тогда высказывание или – истинно, т.к. истинно каждое из высказываний А и В, составляющих высказывание С. Операцию дизъюнкции можно определить и для нескольких высказываний как связку высказываний, объединённых союзом «или»: А = Аi ; где i = 1; 2; …; n В этом случае высказывание А истинно, если истинно хотя бы одно из высказываний, входящих в связку. Операция эквивалентности, или эквивалентность высказываний.Высказывание С, составленное из двух высказываний А, В при помощи слов «тогда и только тогда, когда…», называют эквивалентностью высказываний А и В: . Для эквивалентности используют знак (или ). Эквивалентность представляет собой истинное высказывание, когда высказывания и А, и В оба истинны или оба ложны. Таблица истинности для операции эквивалентности:
Пусть {число 3n является чётным}, {число n является чётным}. Высказывание {число 3n является чётным тогда и только тогда, когда n – чётное число} есть эквивалентность высказываний А и В: . Операция импликации, или импликация высказываний.Высказывание С, составленное из двух высказываний А, В при помощи слов «если…, то…», называют импликацией высказываний А и В: (выражение читается «из А следует В», или «если А, то В»). Импликация ложна только в том случае, когда А – истинное высказывание, а В – ложное. Во всех других случаях импликация имеет значение «истина». Таблица истинности для операции импликации:
Первый член импликации – высказывание А – называется посылкой, или условием, второй член В – заключением. Обратите внимание, что таблица истинности для импликации, в отличии от таблиц для конъюнкции, дизъюнкции и эквивалентности, изменяется при перестановке столбцов для А и В. Отметим также, что импликация не полностью соответствует обычному пониманию слов «если…, то…» и «следует». Из третьей и четвёртой строк таблицы истинности для импликации вытекает, что если А – ложно, то, каково бы ни было В, высказывание считается истинным. Таким образом, из неверного утверждения следует всё что угодно. Например, утверждения «если 6 – простое число, то » или «если , то существуют ведьмы» являются истинными. Истинным является и рассмотренное ранее высказывание: «если слон – насекомое, то Антарктида покрыта тропическими лесами». Для иллюстрации содержательного смысла импликации рассмотрим ещё один пример. Пусть {папа завтра получит премию}, {папа завтра купит сыну велосипед}. Импликация может быть сформулирована так: «если папа завтра получит премию, то купит сыну велосипед». Пусть А и В – истинны. Тогда папа, получив премию, покупает сыну велосипед. Естественно считать это истинным высказыванием. Если же папа, получив премию (А – истинно), не купит сыну велосипед (В – ложно), то это, можно сказать, – не логичный поступок, и импликация имеет значение «ложь». Если папа не получит премию (А – ложно), но купит велосипед (В – истинно), то результат положителен (импликация истинна). Наконец, в том случае, если, не получив премии (А – ложно), папа не купит велосипед (В – ложно), то обещание не нарушено, импликация истинна. Задача 1. Даны два высказывания и . В чём заключаются высказывания , , , ? Какие из этих высказываний истинны и какие ложны? Решение. 1) Высказывание , очевидно, ложно. Для того чтобы произведение двух высказываний было истинным, нужно чтобы оба высказывания были истинными. 2) Высказывание истинно, т.к. одно из слагаемых является истинным высказыванием. Высказывание можно записать в виде одного верного нестрогого неравенства . 3) Эквивалентность ( тогда и только тогда, когда ) представляет собой ложное высказывание, т.к. А – ложно, а В – истинно. 4) Импликация то является истинным высказыванием. В самом деле, импликация согласно определению ложна только тогда, когда А – истинно, а В – ложно. Порядок старшинства операцийНовые высказывания могут быть образованы при помощи нескольких или даже всех пяти логических операций, причём каждая из операций может применяться несколько раз. Если в выражении встречаются различные логические операции, то порядок старшинства операций (их приоритет) следующий (понижение приоритета слева направо): . Это означает, что сначала выполняются операции отрицания, затем конъюнкции и т.д. Для нарушения порядка выполнения логических операций служат скобки. Истинность или ложность сложного высказывания можно установить, решая задачу «по действиям». Рассмотрим примеры. Задача 2. Пусть высказывания А и В имеют значения «истина», а высказывания C и D – «ложь». Какое значение имеет высказывание? Решение. В соответствии с порядком старшинства логических операций будем решать задачу «по действиям», используя таблицы истинности логических операций. 1) - «истина». 2) - «ложь». 3) - «истина». 4) - «ложь». 5) - «ложь». Задача 3. Пусть высказывания А и В имеют значения «истина», а высказывания C и D – «ложь». Какое значение имеет высказывание ? Решение. 1) - «истина». 2) - «ложь». 3) - «ложь». 4) - «истина». 5) - «истина». Если в выражении присутствуют арифметические операции, операции сравнения и логические операции, то приоритет следующий: сначала выполняются арифметические операции; порядок старшинства арифметических операций (слева направо): умножение, деление, сложение, вычитание; затем – операции , и операции сравнения (, , , ) в том порядке, в каком они встречаются в выражении; наконец – логические операции в соответствии с приоритетом (понижение приоритета слева направо): . 5. Основные законы математической логики. Коммутативность: , . Ассоциативность: , . Дистрибутивность: , . Законы де Моргана: , . Закон поглощения: . Закон идемпотентности: . «истина» = А, «ложь» = «ложь» «истина» = «истина», «ложь» = А. Закон противоречия: «ложь». Закон исключения третьего: «истина». Закон двойного отрицания: . 6. Парадоксы логики (семантические парадоксы), или «правдоподобные» рассуждения, приводящие к противоречивым результатам. Хотя логика и является основой всех остальных наук, тем не менее, присущее ей, наряду с фундаментальностью, свойство самоочевидности привело к отсутствию глубоких исследований вплоть до XIX столетия, когда интерес к логике оживился под влиянием неевклидовых геометрий (геометрии Лобачевского), а также необходимости строгого обоснования математического анализа. Особый же всплеск внимания к логике возник на исходе XIX века: мир был поражён открытием парадоксов логики, то есть рассуждений, приводящих к противоречиям. Эти парадоксы обычно называют семантическими парадоксами. Парадокс лжеца.Некто утверждает: «Я лгу». Если утверждение «я лгу» истинно («я лгу» = «истина»), то это означает, что он действительно лжёт о том, что лжёт, т.е. утверждение «я лгу» – ложно. Получается, что высказывание «я лгу» и истинно, и ложно одновременно. Парадокс брадобрея. Командир полка назначает одного из солдат брадобреем, приказывая при этом брить тех и только тех солдат, которые не бреются сами. Что же делать брадобрею с самим собой? Если он – брадобрей – будет бриться сам, то это означает, что брадобрей бреет того, кто бреется сам. Он нарушит приказ командира. Но если он не будет сам бриться, значит, его должен побрить брадобрей, т.е. он сам. Получается, что он должен брить и не брить себя одновременно. 7. Основная цель математической логики – обеспечить систему формальных обозначений для рассуждений, встречающихся не только в математике, но и в повседневной жизни. Решим следующую задачу, используя законы сложения и умножения высказываний. Задача 4. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники были на синем «Бьюике»; Джонс сказал, что это был чёрный «Крайслер», а Смит утверждал, что это был «Форд Мустанг» и ни в коем случае не синий. Стало известно, что, желая запутать следствие, каждый из них указал правильно либо только марку машины, либо её цвет. Какого цвета был автомобиль и какой марки? Решение. 1) Перечислим все имеющиеся высказывания: A{машина синего цвета} – 1-е показание Брауна, B{машина марки «Бьюик»} – 2-е показание Брауна, C{машина чёрного цвета} – 1-е показание Джонса, D{машина марки «Крайслер»} – 2-е показание Джонса, Eмашина марки «Форд Мустанг»} – 1-е показание Смита, – 2-е показание Смита. 2) По условию задачи каждый из подозреваемых сказал правду или только про марку машины, или про её цвет. Т.к. Браун дал показания А, В, то А или В – правда, что в записи математической логики будет выглядеть: «истина». Джонс дал показания C, D, т.е. С или D – правда, что есть «истина». Смит дал показания E, , т.е. Е или – правда, что есть «истина». 3) Следствие имеет показания Брауна и Джонса и Смита, т.е. и и , что в записи математической логики есть «истина», т.к. истинно каждое из высказываний , , . 4) Имеем: «истина». Перепишем последнее выражение, учитывая, что является логической суммой, а есть логическое произведение: «истина». Раскроем скобки: «истина». 5) Проанализируем каждое из слагаемых полученного выражения: «ложь», т.к. в этом выражении одновременно утверждается, что машина и синего и не синего цвета; «ложь», т.к. в этом выражении одновременно утверждается, что машина и синего и чёрного цвета; «ложь», т.к. в этом выражении одновременно утверждается, что машина и синего и не синего цвета; «ложь», т.к. в этом выражении одновременно утверждается, что машина «Крайслер» и машина «Форд Мустанг» ; машина марки «Бьюик» и машина чёрного цвета и машина не синего цвета} – в этом выражении внутренних противоречий нет, но мы пока что не знаем, истинно оно или ложно; «ложь», т.к. в этом выражении одновременно утверждается, что машина «Бьюик» и машина «Форд Мустанг» ; «ложь», т.к. в этом выражении одновременно утверждается, что машина «Бьюик» и машина «Крайслер» ; «ложь», т.к. в этом выражении одновременно утверждается, что машина «Бьюик» и машина «Крайслер» . 6) Получили: «ложь» «ложь» «ложь» «ложь» «ложь» «ложь» «ложь» = «ложь» = = = «истина», т.е. преступники скрылись на чёрном «Бьюике». Задачи для самостоятельного решения Задача 1. Докажите формулу: AB =AB. Задача 2. На вопрос, кто из трёх студентов изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй. Кто из студентов изучал логику? Задача 3. «Вернувшись домой, комиссар Мегрэ позвонил в полицейский отдел на набережную Орфевр. - Говорит Мегрэ. Есть новости? - Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжёт. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать Вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжёт. Затем звонила … - Всё. Спасибо. Этого достаточно. – Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжёт. Теперь он знал всё». Какой вывод сделал комиссар Мегрэ? Указания. 1. Рассмотрите следующие высказывания: A {Франсуа был пьян}, B {Этьен убийца}, C {Франсуа лжёт}, D {убийство произошло после полуночи}. 2. Запишите, используя логические операции, высказывания инспекторов Торранса, Жуссье и Люка. Составьте произведение этих трёх высказываний и упростите его. Задача 4. Разбирается дело Брауна, Джонса и Смита. Один из них совершил преступление. На следствии каждый из них сделал два заявления. Браун. Я не делал этого. Смит сделал это. Джонс. Смит не виновен. Браун сделал это. Смит. Я не делал этого. Джонс не делал этого. Суд установил, что один из них дважды солгал, другой – дважды сказал правду, третий – один раз солгал, один раз сказал правду. Кто совершил преступление? |