Законы алгебры логики

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

Для логических значений существует три базовых операции:

• Конъюнкция, или логическое умножение, – операция И

• Дизъюнкция, или логическое сложение, – операция ИЛИ

• Логическое отрицание – операция НЕ

Логические выражения можно преобразовывать в соответствии с законами алгебры логики.

Законы рефлексивности

Если a равно логической единице, то a И a также даст 1, так как оба операнда являются логической истиной.

В случае ИЛИ если a равно нулю, то все выражение будет равно логическому нулю, так как оба операнда выражения являются нулями.

Законы коммутативности

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

В случае ИЛИ также не важно, первым или вторым операндом является логическая истина. Все выражение в этом случае вернет истину.

Законы ассоциативности

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

Также она неважна и при ИЛИ. Если хотя бы один операнд является истиной, все выражение вернет истину.

Законы дистрибутивности

Рассмотрим левую часть верхней формулы. В случае если между операндами в скобках стоит ИЛИ, а за скобками И, результат всего выражения определяется значением a, если оно равно нулю. Что возвращает при этом выражение в скобках не важно. Если же a = 1, значение выражения зависит от результата выражения в скобках. Оно вернет единицу, если хотя бы одна из переменных равна 1.

В правой части верхнего формулы также значение всего выражения зависит исключительно от a, если a = 0. Если же a = 1, то результат выражения зависит от значений b и c.

Во второй формуле дистрибутивности, когда a соединяется с выражением в скобках через оператор ИЛИ, значение всего выражения зависит от a, только если a = 1. Если a = 0, значение всего выражения зависит от того, что вернет подвыражение в скобках.

Опять же после знака равно, если a = 1, то значения b и c не важны, так как они "соединяются" с a через ИЛИ. В итоге получается выражение a ∧ a. Если же a = 0, то значение всего выражения зависит от значений b и c. Если хотя бы одна из этих переменных равна 0, все выражение вернет 0.

Закон отрицания отрицания

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

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

Если a и b равны 1, то выражение a И b возвращает единицу, а ее отрицание приведет к нулю. Это равносильно тому, как если мы будет отрицать a и b по отдельности, объединяя их через логическое ИЛИ. Если хотя бы один из операндов равен нулю, то выражение слева вернет истину, как и выражение справа.

Во второй формуле истину в выражении слева можно получить только, если оба операнда равны нулю. То же самое касается и выражения справа. Отрицая нули по обе стороны от оператора И, мы получаем 1 И 1 = 1.

Законы поглощения

В данных логических выражениях значение b роли не играет. В верхней формуле если a = 0, то логический И заставит все выражение быть равным нулю. Если же a = 1, то подвыражение в скобках с логическим ИЛИ вернет единицу, независимо от того, чему равно b. После выполнения выражения в скобках получим 1 И 1.

Во второй формуле если a = 0, то выражение в скобках вернет 0. В итоге получаем 0 ИЛИ 0. Если a = 1, выражение в скобках может вернуть 0, только если b = 0. Однако после выполнения выражения в скобках получаем 1 ИЛИ 0 = 1. Другими словами, и тут результат всего выражения определяется только значением a.