Как упрощать логические выражения
Урок 11
Упрощение логических выражений
§21. Упрощение логических выражений
Содержание урока
Законы алгебры логики
Законы алгебры логики
Для упрощения логических выражений используют законы алгебры логики. Они формулируются для базовых логических операций — «НЕ», «И» и «ИЛИ».
Закон двойного отрицания означает, что операция «НЕ» обратима: если применить ее два раза, логическое значение не изменится. Закон исключённого третьего основан на том, что в классической (двузначной) логике любое логическое выражение либо истинно, либо ложно («третьего не дано»). Поэтому если А = 1, то А = 0 (и наоборот), так что произведение этих величин всегда равно нулю, а сумма — единице.
Операции с константами и закон повторения легко проверяются по таблицам истинности операций «И» и «ИЛИ». Переместительный и сочетательный законы выглядят вполне привычно, так же, как и в арифметике. Почти везде «работает» аналогия с алгеброй чисел, нужно только помнить, что в логике 1 + 1 = 1, а не 2.
Распределительный закон для операции «ИЛИ» — это обычное раскрытие скобок. А вот для операции «И» мы видим незнакомое выражение, в алгебре чисел это равенство неверно. Доказательство можно начать с правой части, раскрыв скобки:
(А + В) • (А + С) = А • А + А • С + В • А + В • С.
Дальше используем закон повторения (А • А = А) и заметим, что
А + А • С = А • (1 + С) = А • 1 = А.
Аналогично доказываем, что А + В • А = А • (1 + В) = А, таким образом,
(А + В) • (А + С) = А + В • С.
Равенство доказано. Попутно мы доказали также и закон поглощения для операции «И» (для операции «ИЛИ» вы можете сделать это самостоятельно). Отметим, что из распределительного закона следует полезное тождество:
А + А • В = (А + А ) • (А + В) = А + В.
Правила, позволяющие раскрывать отрицание сложных выражений, названы в честь шотландского математика и логика Огастеса (Августа) де Моргана. Обратите внимание, что при этом не просто «общее» отрицание переходит на отдельные выражения, но и операция «И» заменяется на «ИЛИ» (и наоборот). Доказать законы де Моргана можно с помощью таблиц истинности.
Теперь с помощью приведённых законов алгебры логики упростим полученное ранее логическое выражение для объединения областей 3 и 4 на диаграмме с тремя переменными (§ 20, рис. 3.15):
Здесь мы сначала вынесли общий множитель двух слагаемых за скобки, а затем применили закон исключённого третьего.
В общем случае можно рекомендовать такую последовательность действий.
1. Заменить все «небазовые» операции (исключающее ИЛИ, импликацию, эквивалентность и др.) на их выражения через базовые операции «НЕ», «И» и «ИЛИ».
2. Раскрыть отрицания сложных выражений по законам де Моргана так, чтобы операции отрицания остались только у отдельных переменных.
3. Используя вынесение общих множителей за скобки, раскрытие скобок и другие законы алгебры логики, упростить выражение.
Здесь последовательно использованы закон де Моргана, распределительный закон, закон исключённого третьего, переместительный закон, закон повторения, снова переместительный закон и закон поглощения.
Следующая страница 
Логические уравнения
Cкачать материалы урока
Упрощение логических выражений
Для написания любой логической функции может быть использовано логическое выражение, после чего можно составить логическую схему. Как правило, все логические выражения упрощают для получения максимально простой и дешевой логической схемы. В сущности, логическая схема, выражение и логическая функция, являются тремя различными языками, повествующими об одном и том же.
Логические выражения упрощают при помощи различных законов алгебры логики. Часть преобразований напоминает преобразования формул, выполняемые в классической алгебре (например, применение сочетательного и переместительного законов, вынесение за скобки равенства общего множителя и так далее). Для других преобразований используют свойства, которых лишены операции классической алгебры.
Закон двойного отрицания состоит в том, что операция НЕ является обратимой: если ее использовать два раза, логическое значение в результате останется неизменным.
Сущность закона исключенного третьего состоит в том, что каждое логическое выражение при любых условиях является истинным, либо ложным. Если A=1, тогда A=0, а также наоборот. Конъюнкция данных величин всегда равняется 0, дизъюнкция равна 1.
Закон повторения и операции с константами легко можно проверить, используя таблицы истинности операций ИЛИ и И.
Сочетательный и переместительный законы имеют такой же вид, как в математике. Аналогия с привычной всем классической алгеброй.
Для дизъюнкции распределительный закон состоит просто в раскрытии скобок. Для конъюнкции выражение неизвестно, в математике подобное равенство является неверным. Начнем доказывать с правой части. Сначала раскроем скобки:
Используем закон повторение, гласящий, что A⋅A=A,
A+A⋅B=A⋅(1+B)=A⋅1=A, следовательно, (A+B)⋅(A+C)=A+B⋅C.
Мы доказали равенство.
Правил, используемые для раскрытия инверсии сложных выражений, назвали именем известного логика и математика де Моргана. Суть состоит в том, что общее отрицание не только распространяется на отдельные выражения, а еще и дизъюнкция заменяется конъюнкцией (а также наоборот). Для доказательства данных правил используются таблицы истинности.
Основная часть аксиом и законов алгебры логики записаны попарно. Внимательно изучая пары, можно сформулировать принцип двойственности, звучащий следующим образом: если осуществить в тождестве замены конъюнкции, а также дизъюнкции. И также элементов 1 и 0 (при их наличии), получится тождество. Данное свойство именуют принципом двойственности.
Упрощения логических выражений в примерах
Формула, вытекающая из распределительного закона. При ее выведении применили вышеупомянутое правило де Моргана для дизъюнкции, а также использовали закон двойного отрицания, после чего сомножитель X, вынесли за скобку, тогда как в скобках получили закон исключённого третьего, а также применили операцию с константами.
Примеры упрощения логических выражений
Пример первый
Кто из рабочих, обозначенных, как A, B, C, D работает на заводе, а кто нет, если нам даны следующие условия:
Решение задачи. Обозначим несколько простых высказываний:
Сформулировав данные из условия при помощи этих простых высказываний, получим следующее:
Получаем следующую конъюнкцию: ((A+B)→C)⋅(B→C⋅D)⋅C.
После упрощения данной формулы получаем, что A равно 0, B равно 1, C равно 1, D равно 1.
Ответ: ученик A на заводе не работает, а ученики B, C, D играют.
В этом примере применено правило де Моргана, затем использован распределительный закон, после этого применен закон исключенного третьего, потом использован переместительный закон. За ним реализован закон повторения, потом опять применен переместительный закон и, наконец, использован закон поглощения.
Чтобы отыскать решения логического уравнения можно также применить упрощение логических выражений.
Нужно отыскать все решения данного уравнения
Применив правило де Моргана, получим
а затем применяем закон поглощения и получаем
Чтобы логическая сумма равнялась нулю, все слагаемые должны равняться нулю, из чего следует, что
A равно 1, B равно 0, C равно 0, D равно 0.
Как упрощать логические выражения
Логические операции (конъюнкция, дизъюнкция, инверсия)
Таблица истинности: К онъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В); в языках программирования обозначение «And».
Таблица истинности: Дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В);
в языках программирования обозначение «Or».
Инверсией двух высказываний называется новое высказывание, которое истинное тогда и только тогда, когда исходное высказывание ложно.
Название логической операции
Конъюнкция, логическое умножение
Дизъюнкция, логическое сложение
тогда и только тогда, когда
эквивалентность, эквиваленция, равнозначность
Соединим оба утверждения в одно высказывание:
Составим таблицу истинности на полученное высказывание:
Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание
Высказывание 
истинно только при Ш=1, А=0, Х=0.
Пусть дана таблица истинности для некоторой логической функции Z(X,Y):
Построим истинностную таблицу сложного высказывания :
Очевидно, истинностная таблица будет содержать 
строк. Скобки применяются, если нарушаются естественный порядок операций: отрицание, конъюнкция, дизъюнкция, импликация, двойная импликация. Скобки (А ® В) указывают на то, что сначала нужно выполнить импликацию, затем найти (А ® В) Ù С. Скобки в выражении 
можно опустить. Заключительной операцией в построении истинностной таблицы для S будет дизъюнкция двух высказываний: (А ® В) Ù С и .