Элементы и законы алгебры логики

Представьте, что вы общаетесь с другом по поводу предстоящей вечерней прогулки. Вы говорите: «Если будет хорошая погода, то я точно пойду». Друг отвечает: «Но что такое хорошая погода? Для тебя это солнце и ясное небо, для меня — просто отсутствие дождя». И вот вы уже теряетесь в мыслях: просто назвать друга «душным» или принять, что ваше изречение содержит некую неоднозначность.

Именно для того, чтобы избежать подобных неоднозначностей, и существует математическая логика — наука о правильных рассуждениях, использующая строгие формальные методы. В отличие от обычной логики, где одно и то же утверждение можно интерпретировать по-разному, математическая логика требует абсолютной чёткости: любое высказывание должно быть либо истинным, либо ложным. Никаких «может быть», «наверное» или «смотря как посмотреть».

Где же применяется математическая логика? Да практически везде в современном мире! В программировании она лежит в основе всех условных конструкций и алгоритмов. В базах данных помогает формулировать сложные запросы. Даже когда вы ищете что-то в вашем любимом поисковике, используя несколько ключевых слов, поисковая система применяет законы логики для обработки вашего запроса.

Ранее мы уже разбирали историю алгебры логики и основные операции: И, ИЛИ, НЕ, импликацию и эквивалентность. Теперь углубимся в структуру высказываний и законы, которые помогают упрощать выражения.

Элементы математической логики

Высказывания

В основе математической логики лежат высказывания — утверждения, которые можно однозначно оценить как истинные или ложные. Звучит просто, но давайте разберёмся подробнее.

Возьмём простое утверждение: «Идёт дождь». Это классический пример элементарного логического высказывания. Почему элементарного? Потому что мы не можем разбить его на более мелкие логические части, сохранив смысл. Либо дождь идёт (высказывание истинно), либо не идёт (высказывание ложно). Всё предельно ясно.

А вот предложение «Возможно, завтра будет дождь» — это уже не логическое высказывание в строгом смысле, потому что оно неопределённое. Мы не можем сказать про него истинное оно или ложное. Ведь это лишь предположение, а математическая логика с такими вещами не работает.

Составные высказывания

Из элементарных высказываний, как из кубиков лего, можно собирать более сложные конструкции. Например:

«Если идёт дождь, то земля мокрая»

Здесь мы взяли два простых высказывания («Идёт дождь» и «Земля мокрая») и соединили их логической операцией импликации (логического следования). Получилось составное высказывание.

Можно строить и совсем сложные конструкции. Представим, что у нас есть такие высказывания:

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

Полезная подсказка звучит так: отрицание «заходит» в скобки, меняет знак каждой части и переворачивает связку. И превращается в ИЛИ, а ИЛИ — в И.

Например, отрицание фразы «У ученика есть пропуск И паспорт» означает: «У ученика нет пропуска ИЛИ нет паспорта». Чтобы исходная конъюнкция была ложной, достаточно отсутствия хотя бы одного документа.

А отрицание фразы «Ученик решает задачу на Python ИЛИ вручную» означает: «Ученик не решает её на Python И не решает вручную». Здесь должны не выполняться сразу оба варианта.

Закон работает и для длинных цепочек: ¬(A ∨ B ∨ C) = ¬A ∧ ¬B ∧ ¬C. Отрицание затрагивает каждое высказывание, а все связки ИЛИ превращаются в И.

То есть, когда мы отрицаем конъюнкцию (И), она превращается в дизъюнкцию (ИЛИ) отрицаний, и наоборот. При этом операция как бы «переворачивается».

Представьте такой прогноз погоды: «+22℃, Ясно». Теперь составим пессимистичные высказывания:

A: «Сегодня идёт дождь»
B: «Сегодня холодно»

Выражение ¬(A ∨ B) читается как: «Неверно, что сегодня идёт дождь ИЛИ холодно». Звучит правдиво для нашего прогноза, но как-то запутанно.

Применим закон де Моргана и получим ¬A ∧ ¬B: «Сегодня НЕ идёт дождь И сегодня НЕ холодно». Вот теперь всё ясно! Мы сразу понимаем, что погода хорошая: сухо и тепло. Когда мы говорим «неверно, что A или B», это означает, что и A неверно, и B неверно — оба утверждения ложны одновременно. Именно это и выражает конъюнкция отрицаний.

Почему законы действительно работают?

Проверим первый закон без заучивания. Если A и B истинны, выражение A ∧ B истинно, а его отрицание ложно. Справа оба отрицания ложны, поэтому ¬A ∨ ¬B тоже ложно.

Если хотя бы одно из высказываний ложно, конъюнкция A ∧ B уже ложна, а её отрицание истинно. Справа отрицание хотя бы одного высказывания истинно, поэтому истинна и дизъюнкция.

Мы рассмотрели все возможные ситуации: либо истинны обе части, либо хотя бы одна ложна. Левая и правая стороны закона всегда совпадают, а значит, равносильны.

Законы де Моргана в неравенствах и отрезках

В заданиях 15 отрицание часто стоит не перед буквой, а перед сравнением. Тогда меняется сам знак: ¬(x > 5) означает x ≤ 5, а ¬(x ≥ 5) означает x < 5.

Граница обязательно переходит на другую сторону. Поэтому ¬(x = 5) превращается в x ≠ 5, а ¬(x ≠ 5) — в x = 5. Именно здесь школьники чаще всего теряют равенство.

Теперь посмотрим на отрезок. Принадлежность x ∈ [2; 7] означает одновременно x ≥ 2 И x ≤ 7. Отрицаем всю конструкцию по закону де Моргана:

¬((x ≥ 2) ∧ (x ≤ 7)) = (x < 2) ∨ (x > 7)

Получается дополнение отрезка: число находится левее 2 или правее 7. Эту же идею мы подробно используем в статье о четвёртом типе задания 15.

Дистрибутивный закон

Дистрибутивные законы в логике работают похоже на одноимённый закон из школьной алгебры.

Вспомним, как дистрибутивный закон выглядит для умножения: (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 ∨ (что угодно) всегда даёт истину, потому что для дизъюнкции достаточно одного истинного условия.

В задании 15 особенно полезны ещё две замены: A → B = ¬A ∨ B, а A ≡ B = (A ∧ B) ∨ (¬A ∧ ¬B). Они помогают убрать импликацию и эквивалентность из сложной формулы.

Мини-тренировка

Давайте попробуем вместе раскрыть отрицание ¬((x < 10) ∨ (x = 15)).

Сначала меняем ИЛИ на И, затем отрицаем обе части: x ≥ 10 И x ≠ 15. То есть подходят все числа от 10, кроме 15 (10, 11, 12, 13, 14, 16 …).

Теперь раскроем ¬((x ≥ 3) ∧ (x ≤ 9)).

Аналогичным образом получаем x < 3 ИЛИ x > 9. Это все числа, которые не входят в отрезок [3; 9].

Наконец, ¬(A → B) удобно читать через единственный ложный случай импликации: A истинно, а B ложно. Поэтому ¬(A → B) = A ∧ ¬B.

Итоги

В этой статье мы разобрали, из чего строятся логические формулы и почему их можно преобразовывать, не меняя смысла. Высказывания стали для нас не абстрактными буквами, а условиями, каждое из которых бывает истинным или ложным.

Главный инструмент — законы де Моргана: отрицание меняет каждую часть и одновременно меняет И на ИЛИ или ИЛИ на И. В неравенствах вместе со знаком меняется строгость, поэтому ¬(x > a) — это x ≤ a.

Не пытайтесь преобразовать всю длинную формулу за один шаг. Выберите самые внутренние скобки, перепишите только их и проверьте себя обычной фразой на русском языке.

В следующей статье применим эти законы к первому типу задания 15 ЕГЭ по информатике.