Законы алгебры логики.
Законы алгебры логики достаточно просто доказываются с применением различных способов.
Пример 1. Докажем второй закон де Моргана с помощью таблицы истинности. Построим таблицу истинности для левой и правой части закона.
| x | y | x ∨ y | ¬ (x ∨ y) | ¬ x | ¬ y | ¬ x ∧ ¬ y |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Заметим, что результирующие столбцы в таблице истинности совпали. Таким образом, формулы в левой и правой части закона равносильны.
Пример 2. Докажем второй закон дистрибутивности (который несправедлив в алгебре чисел) путем тождественных преобразований.
1) Для доказательства раскроем скобки в правой части закона:
(x + y) • (x + z) = x • x + x • z + y • x + y • z
2) Используем закон идемпотентности: x • x = x . В результате имеем,
x + x • z + y • x + y • z
3) Применим закон поглощения x + x • z = x . После преобразования получим,
x + y • x + y • z
4) Применим закон поглощения x + y • x = x. Окончательно получаем,
x + y • z
Таким образом, (x + y) • (x + z) = x + y • z
Равенство доказано.
Copyright © 2014-2021, Урок информатики
Все права защищены
Законы алгебры логики
В булевой алгебре существуют только два значения – это истина и ложь. В английском языке правда – это True , ложь – это False . Оба этих значения являются логическими. Обычно значению True сопоставляют единицу, значению False сопоставляют ноль.
Для логических значений существует три базовых операции:
- Конъюнкция, или логическое умножение, – операция И
- Дизъюнкция, или логическое сложение, – операция ИЛИ
- Логическое отрицание – операция НЕ
Логические выражения можно преобразовывать в соответствии с законами алгебры логики.
Законы рефлексивности
Если a равно логической единице, то a И a также даст 1, так как оба операнда являются логической истиной.
В случае ИЛИ если 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 и 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 .
Алгебра логики назначение основные законы
Итак, мы познакомились с понятием логического выражения и увидели, каким образом его строить по высказыванию на русском языке. Следующий шаг – изучение преобразований логических выражений.
Определение 5
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.
Законы алгебры логики
это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность. Начнём с самых простых законов:
1) Законы поглощения констант
2) Законы поглощения переменных
3) Законы идемпотентности
4) Закон двойного отрицания
5) Закон противоречия
6) Закон исключённого третьего
Приведённые законы ещё называют аксиомами алгебры логики. Истинность этих и всех последующих законов легко можно установить, построив таблицу истинности для левого и правого логического выражения.
Переходим к группе законов, которые практически аналогичны законам алгебры чисел.
7) Законы коммутативности
Здесь стоит сделать замечание, что помимо конъюнкции и дизъюнкции свойством коммутативности также обладают эквивалентность и строгая дизъюнкция. Импликация – единственная из изучаемых операций, которая имеет два операнда и не обладает свойством коммутативности.
8) Законы ассоциативности
(x & y) & z = x & (y & z),
(x`vv`y) `vv` z = x `vv` (y `vv` z);
9) Законы дистрибутивности
Первый из законов дистрибутивности аналогичен закону дистрибутивности в алгебре чисел, если конъюнкцию считать умножением, а дизъюнкцию – сложением. Второй же закон дистрибутивности отличается от алгебры чисел, поэтому рекомендуется обратить на него особое внимание и в дальнейшем использовать при решении задач на упрощение выражений.
Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.
особые законы алгебры логики.
10) Законы де Моргана
11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)
Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.
Так как результирующие столбцы совпали, то выражения, стоящие в левой и правой частях закона, равносильны.
В алгебре при решении задач на упрощение выражений большой популярностью пользовалась операция вынесения общего множителя за скобки. В алгебре логики эта операция также является легитимной, благодаря законам дистрибутивности и закону поглощения константы `1`. Продемонстрируем этот приём на простом примере: докажем первый закон поглощения, не используя таблицу истинности.
Наше начальное выражение: x `vv` (x & y) . Выносим `x` за скобки и получаем следующее выражение:
x &(1 `vv` y) . Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x .
В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой , а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.
12) Закон преобразования импликации
Необходимо ещё отметить, что в сложных логических выражениях у операций есть порядок приоритетов.
3) Дизъюнкция, строгая дизъюнкция, эквивалентность
Основные положения и законы алгебры логики
В середине XIX века ирландский математик Джордж Буль разработал алгебру логики («Исследование законов мышления»). Поэтому алгебру логики называют также булевой алгеброй.
Давая высказываниям буквенные обозначения, выражая операции логических преобразований в символах действий и пользуясь установленными для этих действий правилами и аксиомами, алгебра логики позволяет процесс рассуждений при решении задачи, заданной в условиях логики высказываний, полностью описать в алгоритмах, т. е. иметь математически записанную программу решения данного вопроса.
Для обозначения истинности или ложности высказываний (т. е. для введения значений оценки высказываний) алгебра логики пользуется удобной в данном случае двоичной системой. Если высказывание истинно, оно принимает значение 1, если ложно — 0. В отличие от двоичных чисел, логические 1 и 0 выражают не количество, а состояние.
Так, в электрических схемах, описанных с помощью булевой алгебры, где 1 — наличие напряжения, а 0 — отсутствие его, подача напряжений от нескольких источников в один узел схемы (т. е. поступление на него нескольких логических единиц) отображается также логической единицей, которая указывает не на суммарное напряжение в узле, а только на наличие его.
При описании входных и выходных сигналов логических схем используются переменные, которые принимают значения только логического 0 или 1. Зависимость выходных сигналов от входных определяется логической операцией (функцией). Обозначим входные переменные Х1 и Х2, а выходную, полученную путем логической операции над ними — у.
Рассмотрим три основные элементарные логические операции, с помощью которых могут быть описаны все более сложные.
1. Операция ИЛИ — логическое сложение:
Рассматривая все возможные значения переменных, можно определить операцию ИЛИ, как достаточность хотя бы одной единицы на входе для получения единицы на выходе. Название операции объясняется смысловым значением союза ИЛИ во фразе: «Если ИЛИ один вход, ИЛИ второй — единицы, то выход — единица».
2. Операция И — логическое умножение:
Из рассмотрения полного набора значений переменных операция И определяется, как необходимость совпадения всех единиц на входах для получения единицы на выходе: «Если И один вход, И второй — единицы, то выход— единица».
3. Операция НЕ — логическое отрицание или инверсия. Обозначается чертой над переменной.
При инверсии значение переменной заменяется на обратное.
Основные законы алгебры логики:
1. Закон нулевого множества: произведение любого числа переменных обращается в нуль, если какая-либо одна из переменных имеет значение нуль, независимо от значений других переменных:
2. Закон универсального множества — сумма любого числа переменных обращается в единицу, если хотя бы одна из переменных имеет значение единицы, независимо от других переменных:
3. Закон повторения — повторяющиеся переменные в выражении могут быть опущены (иначе говоря, в алгебре Буля возведения в степень и умножения на числовой коэффициент нет):
4. Закон двойной инверсии — дважды выполненная инверсия является пустой операцией:
5. Закон дополнительности — произведение любой переменной и ее инверсии есть нуль:
6. Сумма любой переменной и ее инверсии есть единица:
7. Переместительные законы — результат выполнения операций умножения и сложения не зависит от того, в каком порядке следуют переменные:
8. Сочетательные законы — при операциях умножения и сложения переменные можно группировать в любом порядке:
9. Распределительные законы — допускается вынесение общего множителя за скобки:
10. Законы поглощения — указывают способы упрощения выражений при участии переменной во всех сомножителях и слагаемых:
11. Законы де Моргана — инверсия произведения есть сумма инверсий переменных:
инверсия суммы есть произведение инверсий переменных:
Присоединяйтесь к нашему каналу в Telegram «Автоматика и робототехника»! Узнавайте первыми о захватывающих новостях и увлекательных фактах из мира автоматизации: Автоматика и робототехника в Telegram
Если Вам понравилась эта статья, поделитесь ссылкой на неё в социальных сетях. Это сильно поможет развитию нашего сайта!
Не пропустите обновления, подпишитесь на наши соцсети: