14. Логические операции следования и равносильности. Законы алгебры логики

Логические операции следования и равносильности. Свойства логических операций

Мы уже знаем, что алгебра логики работает с логическими переменными — такими, которые могут принимать всего два значения: «истина» или «ложь». Кроме того, мы подробно изучили базовые логические операции — И, ИЛИ, НЕ.

Теперь поговорим ещё о нескольких важных операциях, с алгебраическими аналогами которых вы хорошо знакомы по урокам математики, — следование и равносильность. Например, в математике можно встретить такую запись:

 То есть выраженияиэквивалентны.

Если же говорить об операции следования, то можно привести такой пример: .

Данная запись говорит о том, что еслито

Но в обратную сторону мы не можем составить верное логическое утверждение, ведь еслито это совершенно не означает, что

может быть равен и –3, о чём нам говорит уже рассмотренная эквивалентность.

Несложно заметить, что эквивалентность — это двустороннее следование:— это то же самое, что

Рассмотрим пример. Будем считать истинным утверждение, что если летом светит солнце, то на улице тепло.

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

Если же солнце летом светит, то должно быть тепло. Если мы будем утверждать обратное, то логическое выражение будет ложным.

Теперь обозначим входные условия именами логических переменных: солнце светит — A, на улице тепло — B, результат — C.

Составим таблицу истинности логического выражения «Условия А достаточно, чтобы выполнялось В».

1. Выражение «Если солнце не светит, то на улице может быть прохладно» будет означать, что А = 0, В = 0. В этом случае противоречия не возникает, и в результате мы имеем С = 1.

2. Выражение «Если солнце не светит, то на улице может быть тепло» также в результате даёт истину. Таким образом, при А = 0 и В = 1 получаем С = 1.

3. Выражение «Если солнце светит, то на улице может быть прохладно» летом даст нам противоречие, отсюда при А = 1 и В = 0 получаем С = 0.

4. И, наконец, выражение «Если солнце светит, то на улице может быть тепло» даст истину, то есть при А = 1 и В = 1 получаем С = 1.

Как видно из таблицы истинности, логическое выражение ложно только в единственном случае: когда А = 1 и В = 0, во всех остальных случаях логическое выражение истинно. Глядя на таблицу истинности, можно также сказать, что мы фактически получили таблицу значений логического выражения «А не больше В». При этом если обратить внимание на строки, где А = 0, мы увидим, что результат всегда будет истинным. Поэтому здесь уместно говорить о том, что из ложного утверждения следует что угодно.

Из ложного выражения следует что угодно

Существует исторический анекдот, который иногда называют теоремой о том, что из ложного утверждения следует что угодно.

Однажды на лекции Бертрана Рассела его студент усомнился в данном утверждении и попросил представить доказательство того, что если 2 + 2 = 5, то лектор — Папа Римский.

Рассел предложил такой ход рассуждений:

1) Предположим, что 2 + 2 = 5.

2) Вычтем из обеих частей по 2, получим 2 = 3.

3) Переставим правую и левую части: 3 = 2.

4) Вычтем из обеих частей по 1, 2 = 1.

Папа Римский и я — нас двое. Так как 2 = 1, то Папа Римский и я — одно лицо. Следовательно, я — Папа Римский.

Те логические выражения, которые мы сейчас рассмотрели, являются примерами логической операции импликации, или следования.

Также стоит отметить, что первую часть импликации называют основанием импликации, а вторую — следствием импликации.

Импликация аналогов в традиционной арифметике не имеет, но у неё есть аналог в алгебре: следование, которое мы используем при записи решений уравнений.

По своей смысловой нагрузке импликация в алгебре логики приближена к союзу «если…  то», по сути являясь условным высказыванием. Данная операция обозначается символом

Пример записи:

 Также импликацию можно выразить через операции И, ИЛИ и НЕ следующим образом:или

Данные формулы можно прочитать так: результат импликации равен сумме инверсного значения А и В. Вторую формулу можно прочитать так: отрицание импликации равно логическому произведению А и инверсного В.

Рассмотрим другое логическое выражение: мама отпускает нас на прогулку тогда и только тогда, когда выполнено домашнее задание. По аналогии с примером про импликацию разделим выражение на более простые: мама отпускает на прогулку — А, домашнее задание выполнено — В, результат — C.

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

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

Операция эквивалентности также имеет аналог в алгебре — мы используем её, например, при записи решений уравнений и называем равносильностью.

Эквивалентность по своей смысловой нагрузке приближена к связке «тогда и только тогда, когда». Она может обозначаться следующими символами:

Пример записи эквивалентности:

Как и другие более сложные операции, равносильностьможно выразить через операции более простые: И, ИЛИ и НЕ. Сделать это можно так:

или

Первая запись в нашем примере может означать такое логическое выражение: «Мы сделали уроки И идём гулять или мы не сделали уроки И не идём гулять».

Можно также сказать, что эквивалентность — это одновременная импликация в обе стороны. Эквивалентность— это то же самое, что и ()().

Свойства логических операций. Законы алгебры логики

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

• Коммутативный (переместительный)

• Ассоциативный (сочетательный)

• Дистрибутивный (распределительный)

• Двойного отрицания

• Исключённого третьего

• Повторения

• Закон операций с 0 и 1

• Законы де Моргана

Некоторые законы эквивалентны законам арифметики.

1. Пример коммутативного закона: A B = BA, что по сути схоже с арифметическим законом А × В = В × А. Это означает, что порядок входных логических выражений не влияет на результат. Например, выражение «Сегодня понедельник И хорошая погода» будет давать такой же результат, как и выражение «Сегодня хорошая погода И понедельник».

Попробуйте этот же закон использовать для логической операции ИЛИ.

Результат: AB = BA. Выражение «Сегодня понедельник ИЛИ хорошая погода» равнозначно выражению «Сегодня хорошая погода ИЛИ понедельник».

2. Пример ассоциативного закона: (AB)C = A(BC), что по сути схоже с арифметическим законом (А × В) × C = А × (B × C). Это означает, что порядок действий в данном случае не влияет на результат. Выражение «(Сегодня понедельник И хорошая погода) И я получил хорошую оценку в школе» равнозначно выражению «Сегодня понедельник И (хорошая погода И я получил хорошую оценку в школе)».

Попробуйте использовать закон для логической операции ИЛИ.

Результат: (AB)C = A(BC). Выражение «(Сегодня понедельник ИЛИ хорошая погода) ИЛИ я получил хорошую оценку в школе» равнозначно выражению «Сегодня понедельник ИЛИ (хорошая погода ИЛИ я получил хорошую оценку в школе)».

3. Пример дистрибутивного закона: A(BC) = (AB)(AC), что по сути схоже с арифметическим законом А × (В + C) = (A × B) + (A × C).

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

Результат: A(BC) = (AB)(AC). Выражение «У меня хорошее настроение ИЛИ (я решил задачу и сделал уборку дома)» равнозначно выражению «(У меня хорошее настроение ИЛИ я решил задачу) и (у меня хорошее настроение ИЛИ я сделал уборку дома)».

4. Закон двойного отрицания: двойное отрицание исключает отрицание. Пример: «Сейчас не не утро» — то же самое, что и «Сейчас утро», т.е.  

5. Пример закона исключённого третьего:

Пример: «Я голоден И я НЕ голоден» — на выходе имеем противоречие во всех случаях. Для логической операции ИЛИ выражение «Я голоден или я не голоден» во всех случаях не даёт противоречия, а значит, всегда верно. То есть

6. Пример закона повторения: AА = А. Пример: выражение «Я люблю учиться И я люблю учиться» можно сократить до «Я люблю учиться» без потери смысла. Попробуйте этот же закон использовать для логической операции ИЛИ.

Результат: AА = А. Выражение «Я люблю учиться ИЛИ я люблю учиться» равнозначно выражению «Я люблю учиться».

7. Законы операций с 0 и 1. Можно привести такие примеры: A0 = 0, A1 = А. Пример: выражение «Дома тепло (А) Ив нашем суждении есть противоречие (0)» даёт нам во всех случаях противоречие, то есть ноль. А выражение «Дома тепло (А) Ив нашем суждении нет противоречия (1)» будет зависеть уже от того, тепло дома или нет. Попробуйте его использовать для логической операции ИЛИ. Получаем результат: A0 = A, A1 = 1.

Истинность высказывания «Дома тепло (А) ИЛИв нашем суждении есть противоречие (0)» зависит от значения A. «Дома тепло (А) ИЛИв нашем суждении нет противоречия (1)» — истинное высказывание.

 8. Ещё одна группа законов алгебры логики — законы де Моргана. Их аналогов нет в арифметике. Звучат они так: отрицание конъюнкции равно дизъюнкции отрицаний, а также наоборот — отрицание дизъюнкции есть конъюнкция отрицаний.

Пример: выражение «Неправда, что я люблю смотреть телевизор И бегать стометровку» означает «Я НЕ люблю смотреть телевизор или я не люблю бегать стометровку». Попробуйте использовать другой закон де Моргана для логической операции ИЛИ самостоятельно. Получаем результат: выражение «Неправда, что я люблю смотреть телевизор ИЛИ бегать стометровку» равнозначно выражению «Я НЕ люблю смотреть телевизор и я не люблю бегать стометровку».

Итоговая таблица законов алгебры логики:

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

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

Рассмотрим это на примере доказательства дистрибутивного закона:

A(BC) = (AB)(AC).

Для этого сначала нужно записать в таблицу все возможные варианты значений A, B и С, затем произвести по отдельности действия в правой и левой части равенства в соответствии с приоритетами. Попробуйте сделать это самостоятельно. В итоге вы должны получить следующую таблицу.

Видим, что получили одинаковые результаты в колонках A(BC) и (AB)(AC), что по сути является доказательством данного закона алгебры логики.

Подведём итоги. Мы рассмотрели ещё две важные логические функции в алгебре логики — импликацию и эквивалентность. Обе эти операции являются бинарными (от лат. binarius — двойной), то есть выполняются с двумя входными параметрами.

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

Операция равносильности же помогает понять, равны ли входные параметры друг другу. Если равны, то в результате получится истина, иначе — ложь. Представьте, как можно применить эту операцию к электрическому чайнику, если можно сказать, что чайник должен включиться, если вода внутри холодная и кнопка включения нажата.

Рекомендованная литература

1. Информатика: 8 класс: базовый уровень: учебник / Л. Л. Босова, А. Ю. Босова. — Москва: Просвещение, 2024.

Проверь себя

1. Что такое импликация? На каком наборе переменных импликация ложна?

2. В каком случае значения переменных можно считать эквивалентными?

3. В каком случае эквивалентность двух переменных ложна?

4. Какие законы алгебры логики не имеют аналогов в математике?

5. Докажите справедливость соотношения

Список использованных источников:

1. Иллюстратор Бумастрова А. В.

2. Источник: wikipedia.org / название: Bertrand Russell photo (cropped 7-9) / атрибуция: public domain, автор: Bassano Ltd