Конспект урока «Математическая логика»

МАТЕМАТИЧЕСКАЯ ЛОГИКА 10 класс ГОУ средняя школа Фрунзенского района г.Санкт-Петербурга № 212 Учитель информатики Селезнева Р.С.

Математическая логика представляет собой математический аппарат, изучающий различные способы логический рассуждений. Основным объектом изучения являются простые высказывания. Высказыванием называется повествовательное предложение, которое является (или может являться) либо истинным, либо ложным. Каждое высказывание может принимать одно из двух возможных значений, которыми являются «Истина» или «Ложь». Вопросительное или повелительное предложение не является высказыванием. Пример: высказывание «монитор - устройство вывода информации» является истинным. Теоретическую основу математической логики составляет булева алгебра, называемая в честь английского математика Дж. Буля. Отличие от обычной алгебры заключается в том, что логические аргументы (переменные) могут принимать лишь два значения «истина»(TRUE) и «ложь»(FALSE), иногда их называют «ДА» и «НЕТ», а чаще обозначают 0 и 1.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ Операция «отрицание»(«инверсия») соответствует частице «не». Для обозначения отрицания используется знак ¬ или ¯ . Используем для обозначения высказываний буквы латинского алфавита. Например, обозначим высказывание «на улице светит солнце» буквой «p». Тогда запись ¬p представляет «не верно, что на улице светит солнце». Итак, если p – истинно (равно1), то ¬p - ложно (равняется 0). Действие отрицание можно представить в виде таблице истинности. Операция «дизъюнкция». Это логическое сложение соответствует слову «или». Дизъюнкция обозначается ν. В таблице ниже перечислены различные значения двух переменных и результат дизъюнкции. p ¬p 0 1 1 1 p q pνq 0 0 0 0 1 1 1 0 1 1 1 1

Дизъюнкция ложна (равна 0) тогда и только тогда, когда оба высказывания ложны (равны 0). В других ситуациях результат дизъюнкции двух переменных приводит к единицею Операция «конъюнкция». Для обозначения используется символ Λ или &. Конъюнкция истинна (равна 1) тогда и только тогда когда оба высказывания истинны (равны 1). Операция «импликация» (следование), которая обозначается →. Посредством этой операции устанавливаются причинно-следственные связи: «p требует выполнения q», или «p имплицирует q», или «из p следует q», или «если p, то q». Пример, p – высказывание «на улице светит солнце», а q – высказывание «очень жарко», то p → q означает «если на улице светит солнце, то очень жарко». p q pΛq 0 0 0 0 1 0 1 0 0 1 1 1

Таблица истинности для импликации Операция – «эквивалентность» (равнозначность). Обозначается ↔ Эквивалентность истинна в двух случаях: Если p истинно и q истинно Если p ложно и q ложно p q p→q 0 0 1 0 1 1 1 0 0 1 1 1 P q p↔q 0 0 1 0 1 0 1 0 0 1 1 1

Операция «исключающее или» Обозначается знаком Свойства логических операций: ¬( ¬а Λ а) экививалентно 1 (никакое высказывание не может быть одновременно и истинным, и ложным) аν¬а эквивалентно1 (это закон исключительного третьего – каждое высказывание или истинно, или ложно) (а →b)=(¬b→¬ а) – закон контрапозиции ¬¬а=a – закон двойного отрицания (двойное отрицание а эквивалентно а) (а ν b)=(b ν а) – коммутативность дизъюнкции (aΛb)=(bΛa) – коммутативность конъюнкции aν(bνc)=(aνb)νc – ассоциативность дизъюнкции aΛ(bΛc)=(aΛb)Λc – ассоциативность конъюнкции Законы де Моргана ¬(aνb)=(¬aΛ¬b) Законы дистрибутивности p q pq 0 0 0 0 1 1 1 0 1 1 1 0

¬(aΛb)=(¬aν¬b) Законы дистрибутивности aΛ(bνc)=(aΛb)ν(aΛc) aν(bΛc)=(aνb)Λ(aνc) Примеры заданий: Пример 1. Дан фрагмент таблицы истинности функции F Какое из перечисленный выражений соответствуетF? 1.A→¬Aν¬B 3.¬A→B 2.AνB 4.¬AΛ¬B Решение: Необходимо последовательно составить таблицы истинности для всех возможных вариантов выражений. А B F 0 0 1 0 1 1 1 0 1 1 1 0

Таким образом, результат (значение в последней колонке) соответствует функции F, приведенной в первой таблице. Правильный ответ расположен под номером 1. Пример 2. Укажите, для какого слова истинно следующее логическое выражение: (Первая буква гласная ν Пятая буква согласная) →Вторая буква гласная Варианты ответов арбуз 3. кресло ответ 4. привет Решение: Данное выражение представляет собой импликацию. Так как первая часть (вторая буква гласная) ложна для всех представленных вариантов, то для того чтобы выражение было истинным, необходима ложность левой части. Для этого и первая буква не должна быть гласной и пятая буква не должна быть согласной. Это выполняется только для четвертого варианта. Ответ – 4. A B ¬A ¬B Z=¬Aν¬B A→Z 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0

Пример 3. Укажите, какое логическое выражение равносильно следующему выражению: Аν¬(¬ВΛ¬С) Варианты: 1. ¬Аν¬Вν¬С 3. АΛ¬(ВΛС) Аν¬Вν¬С 4.АνВνС Решение: Используя закон де Моргана, запишем: Аν¬(¬ВΛ¬С)=Аν(¬¬Вν¬¬С) Далее используем закон двойного отрицания: Аν(¬¬Вν¬¬С)=АνВνС Таким образом, верный вариант располагается под номером 4.