Планета Информатики

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

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

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

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

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

a ∧ a = a

a ∨ a = a

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

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

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

a ∧ b = b ∧ a

a ∨ b = b ∨ a

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

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

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

(a ∧ b) ∧ c = a ∧ (b ∧ c)

(a ∨ b) ∨ c = a ∨ (b ∨ c)

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

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

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

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Рассмотрим левую часть верхней формулы. В случае если между операндами в скобках стоит ИЛИ, а за скобками И, результат всего выражения определяется значением 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) = a

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

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

¬ (a ∧ b) = ¬ a ∨ ¬ b

¬ (a ∨ b) = ¬ a ∧ ¬ b

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

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

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

a ∧ (a ∨ b) = a

a ∨ (a ∧ b) = a

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

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