Зачем нужна математическая логика?
Представьте, что вы общаетесь с другом по поводу предстоящей вечерней прогулки. Вы говорите: «Если будет хорошая погода, то я точно пойду». Друг отвечает: «Но что такое хорошая погода? Для тебя это солнце и ясное небо, для меня — просто отсутствие дождя». И вот вы уже теряетесь в мыслях: просто назвать друга «душным» или принять, что ваше изречение содержит некую неоднозначность.
Именно для того, чтобы избежать подобных неоднозначностей, и существует математическая логика — наука о правильных рассуждениях, использующая строгие формальные методы. В отличие от обычной логики, где одно и то же утверждение можно интерпретировать по-разному, математическая логика требует абсолютной чёткости: любое высказывание должно быть либо истинным, либо ложным. Никаких «может быть», «наверное» или «смотря как посмотреть».
Где же применяется математическая логика? Да практически везде в современном мире! В программировании она лежит в основе всех условных конструкций и алгоритмов. В базах данных помогает формулировать сложные запросы. Даже когда вы ищете что-то в вашем любимом поисковике, используя несколько ключевых слов, поисковая система применяет законы логики для обработки вашего запроса.
Ранее мы подробно разбирали историю алгебры логики и основные логические операции — конъюнкцию (И), дизъюнкцию (ИЛИ), инверсию (НЕ) и парочку других. Если вы ещё не читали её, настоятельно советуем это сделать — там много интересного о том, как развивалась эта наука и какие операции мы можем использовать. А сегодня мы углубимся в саму структуру логических высказываний и познакомимся с законами, которые помогают упрощать сложные логические выражения.
Элементы математической логики
Заголовок
В основе математической логики лежат высказывания — утверждения, которые можно однозначно оценить как истинные или ложные. Звучит просто, но давайте разберёмся подробнее.
Возьмём простое утверждение: «Идёт дождь». Это классический пример элементарного логического высказывания. Почему элементарного? Потому что мы не можем разбить его на более мелкие логические части, сохранив смысл. Либо дождь идёт (высказывание истинно), либо не идёт (высказывание ложно). Всё предельно ясно.
А вот предложение «Возможно, завтра будет дождь» — это уже не логическое высказывание в строгом смысле, потому что оно неопределённое. Мы не можем сказать про него истинное оно или ложное. Ведь это лишь предположение, а математическая логика с такими вещами не работает.
Составные высказывания
Из элементарных высказываний, как из кубиков лего, можно собирать более сложные конструкции. Например:
«Если идёт дождь, то земля мокрая»
Здесь мы взяли два простых высказывания («Идёт дождь» и «Земля мокрая») и соединили их логической операцией импликации (логического следования). Получилось составное высказывание.
Можно строить и совсем сложные конструкции. Представим, что у нас есть такие высказывания:
- A: «Идёт дождь»
- B: «Я промок»
- C: «Я взял зонт»
- D: «Я остался дома»
Теперь составим из них выражение:
F = (A ∧ ¬B) → (C ∨ D)
Разберём логические операции в нашем выражении:
- Инверсия ¬B: «Я НЕ промок»
- Конъюнкция A ∧ ¬B: «Идет дождь, И я не промок»
- Дизъюнкция C ∨ D: «Я взял зонт ИЛИ остался дома»
- Импликация (A ∧ ¬B) → (C ∨ D): «ЕСЛИ идет дождь, и я не промок, ТО я взял зонт или остался дома»
В итоге получаем такое логическое выражение: «Если идёт дождь, и я не промок, то я взял зонт или остался дома». Вполне жизненная ситуация, правда? Если на улице ливень, а вы сухой, значит, вы либо предусмотрительно захватили зонтик, либо еще более предусмотрительно вообще никуда не пошли.
Проблема сложных выражений
Чем сложнее логическое выражение, тем труднее его анализировать и понимать. Попробуйте с ходу оценить истинность вот такого монстра:
(A ∨ B) ∧ (¬C → D) ∧ (E ∨ ¬F == A)
Голова идёт кругом, верно? Именно поэтому математики придумали специальные законы, которые помогают упрощать и оптимизировать логические выражения, делая их более понятными и удобными для работы. Эти законы называются законами алгебры логики, и сейчас мы их подробно разберём.
Законы алгебры логики
Закон двойного отрицания
Начнём с самого простого и интуитивно понятного закона. Он гласит: двойное отрицание высказывания эквивалентно самому высказыванию. В математической записи:
¬(¬A) = A
Что это значит на практике? Возьмём высказывание: «Сегодня идёт дождь» (A). Его отрицание будет звучать так: «Сегодня НЕ идёт дождь» (¬A). А теперь попробуем отрицать ещё раз: «Сегодня НЕ НЕ идёт дождь» (¬¬A).
Согласитесь, последняя фраза звучит странно и неестественно. В русском языке мы так не говорим. Вместо этого мы просто возвращаемся к исходному утверждению: «Сегодня идёт дождь». Вот это и есть закон двойного отрицания в действии. Первое отрицание переворачивает значение истинности (истина становится ложью, ложь — истиной). Второе отрицание переворачивает его обратно. Как если бы вы дважды перевернули картинку — в итоге она окажется в исходном положении.
Законы де Моргана
Эти законы названы в честь британского математика Огастеса де Моргана (1806-1871), который внёс огромный вклад в развитие математической логики. Интересный факт: де Морган был наставником Ады Лавлейс — той самой, которая была первым программистом в истории!
Законы де Моргана он сформулировал в середине XIX века, хотя некоторые идеи были известны ещё со времён Средневековья. Эти законы показывают, как можно преобразовывать отрицания сложных выражений, и они невероятно полезны в программировании.
Записываются они так:
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
То есть, когда мы отрицаем конъюнкцию (И), она превращается в дизъюнкцию (ИЛИ) отрицаний, и наоборот. При этом операция как бы «переворачивается».
Представьте такой прогноз погоды: «+22℃, Ясно». Теперь составим пессимистичные высказывания:
- A: «Сегодня идёт дождь»
- B: «Сегодня холодно»
Выражение ¬(A ∨ B) читается как: «Неверно, что сегодня идёт дождь ИЛИ холодно». Звучит правдиво для нашего прогноза, но как-то запутанно.
Применим закон де Моргана и получим ¬A ∧ ¬B: «Сегодня НЕ идёт дождь И сегодня НЕ холодно». Вот теперь всё ясно! Мы сразу понимаем, что погода хорошая: сухо и тепло. Когда мы говорим «неверно, что A или B», это означает, что и A неверно, и B неверно — оба утверждения ложны одновременно. Именно это и выражает конъюнкция отрицаний.
Дистрибутивный закон
Дистрибутивный закон в логике работают подобно одноимённому из привычной вам школьной алгебры.
Вспомним, как дистрибутивный закон выглядит для умножения: (a + b) × c = a × c + b × c. В логике действуют похожие правила, только вместо умножения и сложения у нас конъюнкция и дизъюнкция:
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
Предположим, что у нас есть три высказывания:
- A: «Я пойду гулять»
- B: «На улице тепло»
- C: «Светит солнце»
Выражение A ∧ (B ∨ C) означает: «Я пойду гулять И (на улице тепло ИЛИ светит солнце)». То есть для прогулки нам нужно, чтобы было хотя бы что-то одно: либо тепло, либо солнечно.
Применим дистрибутивный закон: (A ∧ B) ∨ (A ∧ C) — «(Я пойду гулять И на улице тепло) ИЛИ (Я пойду гулять И светит солнце)». Смысл тот же, но выражено иначе: мы идём гулять в двух случаях — когда тепло или когда солнечно. Если A истинно, то всё выражение зависит только от (B ∨ C).
Если же A ложно, то всё выражение будет ложным независимо от B и C. Дистрибутивный закон просто по-другому группирует эти условия, сохраняя логический смысл.
Коммутативный закон
Помните поговорку «от перемены мест слагаемых сумма не меняется»? Коммутативный закон (или переместительный) утверждают то же самое для логических операций: порядок операндов не влияет на результат.
Записывается это следующим образом:
A ∧ B = B ∧ A
A ∨ B = B ∨ A
Высказывания «Светит солнце И дует ветер» и «Дует ветер И светит солнце» абсолютно эквивалентны. Порядок, в котором мы перечисляем условия, не влияет на истинность всего утверждения. Логические операции И и ИЛИ симметричны по своей природе. Для конъюнкции важно, чтобы оба условия выполнялись, но неважно, в каком порядке мы их проверяем. То же самое с дизъюнкцией — достаточно истинности хотя бы одного условия.
Ассоциативный закон
Ассоциативный (или сочетательный) закон показывает, что в цепочке одинаковых операций порядок группировки не важен. Это работает точно так же, как в обычной арифметике: (2 + 3) + 5 = 2 + (3 + 5) = 10.
Математическая запись:
(A ∧ B) ∧ C = A ∧ (B ∧ C)
(A ∨ B) ∨ C = A ∨ (B ∨ C)
Возьмём три высказывания:
- A: «Я выспался»
- B: «Я позавтракал»
- C: «Я в хорошем настроении»
Выражение (A ∧ B) ∧ C можно группировать как угодно — смысл не изменится. Для отличного дня нужны все три условия, и неважно, в каком порядке мы их проверяем. Когда все операции одинаковые (только И или только ИЛИ), результат зависит только от значений самих переменных, а не от порядка их обработки. Скобки здесь лишь меняют последовательность вычислений, но не влияют на итоговый результат.
Закон идемпотентности
Закон идемпотентности утверждает, что применение одной и той же операции к одному и тому же высказыванию не меняет результат. Название происходит от латинских слов «idem» (то же самое) и «potentia» (сила).
Записать это можно вот так:
A ∧ A = A
A ∨ A = A
Согласитесь, фраза «Сегодня понедельник И сегодня понедельник» звучит странно и бессмысленно. Мы просто дважды повторяем одно и то же, что не добавляет никакой новой информации. Достаточно просто один раз сказать: «Сегодня понедельник».
Закон дополнения
Закон дополнения описывает, что происходит, когда мы комбинируем высказывание с его отрицанием. Этот закон показывает две логические крайности: абсолютное противоречие и абсолютную истину.
Выглядит запись этого закона следующим образом:
A ∧ ¬A = 0 (ложь)
A ∨ ¬A = 1 (истина)
Возьмём высказывание «Сегодня идёт дождь И сегодня НЕ идёт дождь». Что-то здесь явно не так! Дождь не может идти и в то же время не идти. Поэтому такое выражение всегда ложно.
А вот фраза «Сегодня идёт дождь ИЛИ сегодня НЕ идёт дождь» звучит как философская истина от человека, которому этот мир абсолютно понятен. Это утверждение описывает вообще любой возможный день — ведь дождь либо идёт, либо не идёт, третьего не дано. Поэтому такое выражение всегда истинно.
Высказывание и его отрицание имеют противоположные значения истинности. При конъюнкции (И) нужно, чтобы оба были истинны, что невозможно — отсюда всегда ложь. При дизъюнкции (ИЛИ) достаточно, чтобы хотя бы одно было истинно, что всегда выполняется — отсюда всегда истина.
Закон поглощения
Закон поглощения демонстрирует интересный эффект: более сильное условие может «поглощать» более слабое, делая сложное выражение эквивалентным простому. Звучит запутанно, но сейчас разберёмся.
Запишем этот закон так:
A ∨ (A ∧ B) = A
A ∧ (A ∨ B) = A
В качестве примера рассмотрим такие высказывания:
- A: «У меня есть компьютер»
- B: «У меня есть принтер»
Выражение A ∨ (A ∧ B) читается так: «У меня есть компьютер ИЛИ (у меня есть компьютер И у меня есть принтер)».
Подумайте: если у вас есть компьютер, то первая часть выражения (A) уже истинна, и всё выражение истинно независимо от того, есть ли принтер. Если же компьютера нет, то вторая часть (A ∧ B) тоже будет ложна (ведь там тоже требуется компьютер). Получается, всё сводится просто к A.
Рассмотрим оба возможных случая: если A истинно, то A ∨ (что угодно) всегда даёт истину, потому что для дизъюнкции достаточно одного истинного условия.
Если A ложно, то A ∧ B тоже будет ложно, и выражение A ∨ ложь = ложь = A. В обоих случаях мы получаем просто A, что и доказывает закон поглощения.
Итоги
Законы алгебры логики — это не просто абстрактные математические формулы. Это мощные инструменты, которые помогают упрощать сложные логические выражения, делая их более понятными и удобными для анализа. Программисты используют эти законы каждый день, оптимизируя код и создавая эффективные алгоритмы.
Освоив эти законы, вы сможете не только лучше понимать логику работы программ, но и развить своё логическое мышление в целом. А это пригодится не только в информатике, но и в повседневной жизни — когда нужно принять взвешенное решение или выстроить цепочку аргументов в споре.
Но, а мы же будем применять их при решении 15 заданий ЕГЭ по информатике, чему и посвящена следующая статья.