В информатике есть раздел под названием алгебра логики. Он описывает, как работать с логическими выражениями: преобразовывать их, раскладывать в более простые и находить ответы. Это делается по определенным правилам и законам, в том числе законам де Моргана.
Рассказываем, что такое законы де Моргана в алгебре логики — и какие еще правила помогают работать с логическими выражениями.
Зачем в информатике нужна логика
В программировании часто приходится работать с логическими выражениями. Чтобы это было проще, используют основные законы алгебры логики. Вот в каких ситуациях их применяют:
- Необходимость упростить выражение. Бывают сложные логические конструкции — если написать их в коде как есть, его будет тяжело читать и работать он станет хуже. С помощью законов алгебры логики то же самое можно написать понятнее и короче.
- Реализация некоторых алгоритмов. Многие алгоритмы, работающие с логическими выражениями, используют алгебру логики для преобразований.
- Работа с искусственным интеллектом. Нейросетевые модели активно используют булевы, или логические переменные. Соответственно, их нужно обрабатывать — и тут пригождается алгебра логики.
Это не исчерпывающий список. Сфера применения законов алгебры логики намного шире: их используют в схемотехнике, в математике и аналитике, при создании поисковых систем.
С какими понятиями работают законы де Моргана
Чтобы понимать формулы де Моргана, нужно разбираться в основных понятиях алгебры логики:
- Конъюнкция — логическое «и». В большинстве языков программирования его обозначают оператором and. Выдает результат «истина», только если обе переменные в выражении равны «истине» или больше нуля. В остальных случаях выдает 0 — ложь.
- Дизъюнкция — логическое «или». Оно же or в программировании. В нем результат «истина» получается, если хотя бы одна из переменных в выражении больше нуля или равна «истине». 0 получается, только если обе переменных нулевые или имеют значение «ложь».
В качестве примера возьмем выборку людей, которые могут работать и учиться.
Применение конъюнкции будет выглядеть так: «работает» и «учится» окажется истиной, только если человек и работает, и учится одновременно. В остальных случаях ответ будет «ложь».
Применение дизъюнкции будет выглядеть так: «работает» или «учится» окажется истиной, если человек делает хоть что-то из этого. «Ложью» ответ будет только для тех, кто и не работает, и не учится.
Как звучат законы де Моргана
Правила де Моргана помогают превратить «и» в «или» — и наоборот. В них есть два постулата, с помощью которых и преобразовываются выражения. Вот как они звучат.
Отрицание конъюнкции превращается в дизъюнкцию отрицаний. Если записывать это высказывание как логическую формулу, получится так:
– (А И Б) = –А ИЛИ –Б
Это выражение называют первым законом де Моргана. Как пример, если не оба человека любят мороженое, значит, или один, или второй не любит мороженое. То есть:
- – (А И Б): не оба человека любят мороженое;
- –А ИЛИ –Б: или один, или второй не любит мороженое.
Высказывания эквивалентны — и в обычной жизни нам легко это понять. В алгебре логики правило работает так же.
Отрицание дизъюнкции превращается в конъюнкцию отрицаний. Это второй закон де Моргана, и он выглядит так:
– (А ИЛИ Б) = –А И –Б
Например, высказывание «Ни кошка, ни собака не полосатые» означает «Кошка не полосатая, и собака не полосатая». То есть:
- – (А ИЛИ Б): ни кошка, ни собака не полосатые;
- –А И –Б: кошка не полосатая, собака тоже не полосатая.
Применять эти законы в программировании нужно, например, при обработке массивов информации. С помощью преобразований легче найти среди данных те, которые отвечают каким-то условиям. Например, «фамилия начинается не на А и не на Б», «не старше 50 и не младше 20 лет» и так далее.
Какие еще законы есть в алгебре логики
Математическая логика не ограничивается законами де Моргана. Существует еще много правил — иногда можно услышать про 10 законов алгебры логики или даже о большем числе. Некоторые из них довольно простые:
- Закон идемпотентности: А И А = А, А ИЛИ А = А.
- Закон двойного отрицания: – (–А) = А.
- Закон противоречия: А И –А = 0.
- Закон исключенного третьего: А ИЛИ –А = 1.
- Закон коммутативности: А И Б = Б И А, А ИЛИ Б = Б ИЛИ А.
Другие законы немного сложнее — разберем их отдельно и покажем, как с ними работать.
Закон поглощения констант. Это правило показывает, как конъюнкция и дизъюнкция работают в отношении констант:
- А И 1 = А;
- А ИЛИ 0 = А.
Постоянное значение — 1 или 0 — просто отбрасывается. Остается только исходная переменная А. В программировании это упрощает запись логических выражений.
Например, можно написать не «если у пользователя есть аккаунт и пароль», а просто «если у пользователя есть аккаунт». Ведь наличие аккаунта автоматически значит, что пароль тоже есть — это значение будет константой.
Закон поглощения переменных. Это похожее правило, только вместо постоянных значений тут отбрасываются переменные:
- А И 0 = 0;
- А ИЛИ 1 = 1.
Общий закон поглощения. Часто законы поглощения констант и переменных объединяют. Получается единый закон, формула которого выглядит так:
- А ИЛИ (А И Б) = А;
- А И (А ИЛИ Б) = А.
Например, если условие звучит как «человек имеет аккаунт или имеет аккаунт и пароль» — его можно сократить до «человек имеет аккаунт».
Закон ассоциативности. Это первое правило, где появляется третья переменная. Закон описывает, как вынести ее за скобку и рассматривать отдельно:
- (А И Б) И В = А И (Б И В);
- (А ИЛИ Б) ИЛИ В = А ИЛИ (Б ИЛИ В).
Например, условие «человек учится и работает, а еще состоит в отношениях» можно переделать как «человек состоит в отношениях и работает, а еще учится».
Закон дистрибутивности. В этом законе тоже используют третью переменную. Но на этот раз описывается, как раскладывать выражение, если операции за скобками и в скобках — разные:
- А И (Б ИЛИ В) = (А И Б) ИЛИ (А И В);
- А ИЛИ (Б И В) = (А ИЛИ Б) И (А ИЛИ В).
Например, условие звучит как «человек имеет питомца и при этом учится или работает». Его можно разложить как «человек имеет питомца и учится или человек имеет питомца или работает».
Закон преобразования импликации. Этот закон часто используют в программировании. Он интересен тем, что тут появляется еще одна логическая операция — следование. Операция обозначается как А → Б: истинность Б зависит от того, истинно или ложно А.
Например, «если идет дождь, то на улице лужи» — это следование.
Закон преобразования позволяет разделить следование на более простые операции: конъюнкцию и дизъюнкцию. Вот как раскрывается импликация:
А → Б = –А ИЛИ Б
Возьмем для примера ту же фразу «Если идет дождь, то на улице лужи». Ее можно преобразовать как «Дождь не идет, или на улице лужи».
Все перечисленные формулы для логических выражений работают в обе стороны. То есть преобразования можно выполнить наоборот — превратить конъюнкцию отрицаний в отрицание дизъюнкции. Или сложить выражение с логическим «или» и получить следование. Это позволяет гибко и по-разному использовать формулы в алгоритмах.
Законы де Моргана — главное
- Алгебра логики в программировании — это правила, по которым работают с логическими выражениями. Например, преобразуют их и раскрывают.
- Законы де Моргана — два закона, по которым логическое «и» можно преобразовать в «или» и наоборот.
- Кроме законов де Моргана, есть еще около десятка правил, по которым преобразовывают логические операции.
- Законы можно использовать в обратном направлении и выполнять преобразования наоборот.
