АЛГЕБРА ВЫСКАЗЫВАНИЙ

1 Урок 21 (10 класс – профильный) Алгебра высказываний Цель:     сформировать у учащихся понятия: логическое высказывание, логические величины, логические операции. I. Работа над ошибками Разбор задач контрольной работы по теме «Кодирование информации» II. Объяснение нового материала Подлинный   прогресс   науки,   называемой  математической   логикой,   был достигнут в середине XIX века прежде всего благодаря труду английского учёного математика  Джорджа Буля   «Математический анализ логики». Он перенёс на логику   законы   и   правила   алгебраических   действий,   ввёл   логические   операции, предложил способ записи высказываний в символической форме. Современная   математизированная   формальная   логика   представляет   собой обширную   научную   область   и   находит   широкое   применение   как   внутри   самой математики (исследование оснований математики), так и вне её (анализ и синтез   в   частности, автоматических   устройств,   теоретическая     кибернетика, искусственный интеллект). Алгебра   логики   (алгебра   высказываний)   –  раздел   математической логики,   изучающей   строение   (форму,   структуру)   сложных   логических высказываний   и   способы   установления   их   истинности   с   помощью алгебраических методов.   Можно определить понятия логической переменной, логической функции и логической операции. Логическая переменная  ­  это  простое   высказывание, содержащее   только одну мысль. Ее символическое обозначение ­ латинская буква (например, A,B,X,Y и т.д.). Значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (1 и 0). 2 Составное   высказывание   ­  которая   содержит несколько   простых   мыслей,   соединенных   между   собой   с   помощью   логических  логическая   функция, операций. Ее символическое обозначение —  F(A,B,...). На   основании   простых   высказываний   могут   быть   построены   составные высказывания. Логические операции ­ логическое действие. Рассмотрим три базовые логические операции ­ конъюнкцию, дизъюнкцию и отрицание и дополнительные — импликацию и эквивалентность. Пояснение: по ходу изложения материала заполните следующую таблицу: Конъюнкция  (от лат.  conjunctio —  связываю) Дизъюнкция  (от лат.  disjunctio —  различаю) Инверсия (от  лат. inversio  — перево­ рачиваю) Название Логическое умножение Обозначение А&В, А  В,  А∙ В, A and B Логическое сложение A  v  B, A + B, A or B Отрицание  или ¬А А Союз в естест­ венном языке А и В  А или В не А «Число 10  четное и от­ рицательное»  ­ЛОЖЬ «Число 10 —  четное или  отрицательное » = ИСТИНА Примеры  А ­ «Число 10 — четное»;  В ­ «Число 10 — отрицатель­ ное» «Неверно, что  число 10­чет­ ное» = ЛОЖЬ  «Неверно, что  число 10  отрица­ тельное» =  ИСТИНА Импликаци я (от лат.  implicatio — тесно связы­ вать) Логическое следование А В → А ­условие В ­следствие Если А, тоВ;  когда А,  тогда В; коль скоро А то и  В; и т.п. «Если число  10­четное, то оно является отрицатель­ ным» =  ЛОЖЬ Эквивалентнос ть (от  aequivalens —  равноценное) Логическое   ра­ венство А  B или  А   В А тогда и только тогда, когда В «Число 10 —  четное тогда и  только тогда,  когда  отрицательно» = ЛОЖЬ Логические операции.   (см. таблицу «Операции математической логики») 1. Логическое   отрицание   (инверсия)   ­  образуется   из высказывания   с   помощью   добавления   частицы  «не»  к сказуемому или использования оборота речи «неверно, что …». Делает истинное высказывание ложным и, наоборот, ложное – истинным. А 0 1 А 1 0 Обозначение: не А,   ¬А,   3 ,   not A. А Из таблицы истинности следует, что инверсия высказывания истинна, когда исходное высказывание ложно, и ложна, когда исходное высказывание истинно. 2.   Логическое   умножение   (конъюнкция)­  образуется   соединением   двух высказываний в одно с помощью союза «и». Обозначение:  А и В,    ,ВА    A & B,   А ∙ В,  A and B.  Из таблицы истинности следует, что конъюнкция двух  высказываний истинна тогда и только тогда, когда оба А 0 0 1 1 В 0 1 0 1 ВА  0 0 0 1 высказывания истинны, и ложна, когда хотя бы одно высказывание ложно. 3. Логическое сложение (дизъюнкция) ­ образуется соединением двух высказываний в одно с помощью союза «или». Обозначение:  А или В,      A + B,    A or B. ,ВА   Из таблицы истинности следует, что дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно. 4. Операция «Исключающее ИЛИ»  Операция   «исключающее   ИЛИ»   отличается   от обычного «ИЛИ» только тем, что её результат равен 0, если оба значения равны 1 (последняя строка в таблице истинности). То есть результат этой операции – истина в том и только в том случае, когда два значения не равны. А 0 0 1 1 А 0 0 1 1 В 0 1 0 1 В 0 1 0 1 ВА  0 1 1 1 ВА  0 1 1 0 Операции «исключающее ИЛИ» соответствует русская пословица «Либо пан, либо пропал», где выполнение обоих условий одновременно невозможно. Операция «исключающее ИЛИ» в алгебре логики обозначается знаком   4 , в языке Паскаль  xor: (А xor В), а в языке Си ­ знаком ^ (А ^ В). Эту операцию можно представить через базовые операции (НЕ, И, ИЛИ) следующим образом:  ВАВАВА Операция «исключающее ИЛИ» иначе называется  разделительной дизъюнкцией (это значит «один или другой, но не оба вместе») или сложением по модулю два. Второе   название   связано   с   тем,   что   её   результат   равен   остатку   от   деления арифметической суммы А + В на 2:     =(А+В) mod 2. ВА  5. Логическое   следование   (импликация)­  образуется   соединением   двух высказываний в одно с помощью оборота речи «если …, то…» Обозначение:  А   В,   →  . А  В  Из таблицы истинности следует, что импликация двух высказываний   ложна   тогда   и   только   тогда,   когда   из истинного   высказывания   следует   ложное   (когда истинная предпосылка ведёт к ложному выводу). А 0 0 1 1 В 0 1 0 1 В А  1 1 0 1 6. Логическое   равенство   (эквивалентность)­  образуется   соединением   двух высказываний в одно с помощью оборота речи «… тогда и только тогда, когда ….». Обозначение:      ,   А   ~  В,  A   B А  В               Из   таблицы   истинности   следует,   что эквивалентность   двух   высказываний   истинна   тогда   и только тогда, когда оба высказывания истинны или оба А 0 0 1 1 В 0 1 0 1 В А  1 0 0 1 ложны III. Решение задач 5 IV. Дома: § ­ 18, 19   № 1, 2 с.176 (закончить)