Упростить логические формулы используя законы алгебры логики

Упростить логические формулы используя законы алгебры логики

Содержание урока

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

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

Для упрощения логических выражений используют законы алгебры логики. Они формулируются для базовых логических операций — «НЕ», «И» и «ИЛИ».

Закон двойного отрицания означает, что операция «НЕ» обратима: если применить ее два раза, логическое значение не изменится. Закон исключённого третьего основан на том, что в классической (двузначной) логике любое логическое выражение либо истинно, либо ложно («третьего не дано»). Поэтому если А = 1, то А = 0 (и наоборот), так что произведение этих величин всегда равно нулю, а сумма — единице.

Операции с константами и закон повторения легко проверяются по таблицам истинности операций «И» и «ИЛИ». Переместительный и сочетательный законы выглядят вполне привычно, так же, как и в арифметике. Почти везде «работает» аналогия с алгеброй чисел, нужно только помнить, что в логике 1 + 1 = 1, а не 2.

Распределительный закон для операции «ИЛИ» — это обычное раскрытие скобок. А вот для операции «И» мы видим незнакомое выражение, в алгебре чисел это равенство неверно. Доказательство можно начать с правой части, раскрыв скобки:

(А + В) • (А + С) = А • А + А • С + В • А + В • С.

Дальше используем закон повторения (А • А = А) и заметим, что

А + А • С = А • (1 + С) = А • 1 = А.

Аналогично доказываем, что А + В • А = А • (1 + В) = А, таким образом,

(А + В) • (А + С) = А + В • С.

Равенство доказано. Попутно мы доказали также и закон поглощения для операции «И» (для операции «ИЛИ» вы можете сделать это самостоятельно). Отметим, что из распределительного закона следует полезное тождество:

Читайте также:  Видеокарта ati radeon x1600 pro

А + А • В = (А + А ) • (А + В) = А + В.

Правила, позволяющие раскрывать отрицание сложных выражений, названы в честь шотландского математика и логика Огастеса (Августа) де Моргана. Обратите внимание, что при этом не просто «общее» отрицание переходит на отдельные выражения, но и операция «И» заменяется на «ИЛИ» (и наоборот). Доказать законы де Моргана можно с помощью таблиц истинности.

Теперь с помощью приведённых законов алгебры логики упростим полученное ранее логическое выражение для объединения областей 3 и 4 на диаграмме с тремя переменными (§ 20, рис. 3.15):

(А • В • C ) + А • В • C = (А + А ) • В • C = В • C .

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

В общем случае можно рекомендовать такую последовательность действий.

1. Заменить все «небазовые» операции (исключающее ИЛИ, импликацию, эквивалентность и др.) на их выражения через базовые операции «НЕ», «И» и «ИЛИ».

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

3. Используя вынесение общих множителей за скобки, раскрытие скобок и другие законы алгебры логики, упростить выражение.

(А + B ) • ( А + B ) • ( А + С)=(А + B ) • А • B • ( А + C = (А • А + B • А ) • B • ( А + С) = B • А • B • ( А + С) = А • B • B • ( А + С) = B • А • ( А + С) = B • ( А .

Здесь последовательно использованы закон де Моргана, распределительный закон, закон исключённого третьего, переместительный закон, закон повторения, снова переместительный закон и закон поглощения.

Следующая страница Логические уравнения

Cкачать материалы урока

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Читайте также:  Как открыть документ ворд с паролем

Примеры логических выражений

С применением отрицания

Со знаком "эквивалентно"

Со знаком "следствие"

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн

Законы алгебры логики и правила преобразования логических выражений

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

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

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Закон

Формулировка

1. Закон тождества

Всякое высказывание тождественно самому себе.

2. Закон исключенного третьего

Высказывание может быть либо истинным, либо ложным, третьего не дано. Следовательно, результат логического сложения высказывания и его отрицания всегда принимает значение “истина”.

3. Закон непротиворечия

Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно.

4. Закон двойного отрицания

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

Читайте также:  Родительский контроль гугл аккаунт

5. Переместительный (коммутативный) закон

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

6. Сочетательный (ассоциативный) закон

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

5. Распределительный (дистрибутивный) закон

(X / Y) / Z= (X / Z) / (Y / Z)

(X / Y) / Z = (X / Z) / (Y / Z)

Определяет правило выноса общего высказывания за скобку.

7. Закон общей инверсии Закон де Моргана

Закон общей инверсии.

8. Закон равносильности (идемпотентности)

от латинских слов idem — тот же самый и potens —сильный

9. Законы исключения констант:

10. Закон поглощения:

11. Закон исключения (склеивания):

12. Закон контрапозиции

14. А В = (А / В) / (¬A / ¬B);

15. А В = (¬A / В) / (А /¬B).

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

1) (A/B) / (A/¬B) = A / (B / B)= A / 1 = A

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

¬ (X / Y) / (X / ¬Y) = ¬ X / ¬Y / (X / ¬Y) = ¬ X / X/¬Y /¬Y= 0 ¬Y /¬Y

3) применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией

4) ¬ X / Y / ¬ (X / Y) / X = ¬ X / Y / ¬ X / ¬Y / X= ¬ X / (Y / ¬Y) / X= ¬ X / X= 1

Ссылка на основную публикацию
Adblock detector