Как упростить логическую формулу
Как упростить логическую формулу
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:
1)
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);
2)
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);
4)
( вводится вспомогательный логический сомножитель ( ); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);
5)
(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);
6)
(выносятся за скобки общие множители; применяется правило операций с константами);
7)
(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);
8)
(общий множитель x выносится за скобки, комбинируются слагаемые в скобках первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);
9)
(используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);
10)
(используются правило де Моргана, закон двойного отрицания и закон поглощения).
Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.
Как упростить логическую формулу
Логические операции (конъюнкция, дизъюнкция, инверсия)
Таблица истинности: К онъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В); в языках программирования обозначение «And».
Таблица истинности: Дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В);
в языках программирования обозначение «Or».
Инверсией двух высказываний называется новое высказывание, которое истинное тогда и только тогда, когда исходное высказывание ложно.
Название логической операции
Конъюнкция, логическое умножение
Дизъюнкция, логическое сложение
тогда и только тогда, когда
эквивалентность, эквиваленция, равнозначность
Соединим оба утверждения в одно высказывание:
Составим таблицу истинности на полученное высказывание:
Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание
Высказывание 
истинно только при Ш=1, А=0, Х=0.
Пусть дана таблица истинности для некоторой логической функции Z(X,Y):
Построим истинностную таблицу сложного высказывания :
Очевидно, истинностная таблица будет содержать 
строк. Скобки применяются, если нарушаются естественный порядок операций: отрицание, конъюнкция, дизъюнкция, импликация, двойная импликация. Скобки (А ® В) указывают на то, что сначала нужно выполнить импликацию, затем найти (А ® В) Ù С. Скобки в выражении 
можно опустить. Заключительной операцией в построении истинностной таблицы для S будет дизъюнкция двух высказываний: (А ® В) Ù С и .
Информатика. 10 класс
Конспект урока
Информатика, 10 класс. Урок № 12.
Тема — Преобразование логических выражений
Перечень вопросов, рассматриваемых в теме: основные законы алгебры логики, преобразование логических выражений, логические функции, построение логического выражения с данной таблицей истинности и его упрощение, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ).
Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса
— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)
Открытые электронные ресурсы по теме:
Теоретический материал для самостоятельного изучения.
Способ определения истинности логического выражения путем построения его таблицы истинности становится неудобным при увеличении количества логических переменных, т.к. за счет существенного увеличения числа строк таблицы становятся громоздкими. В таких случаях выполняются преобразования логических выражений в равносильные. Для этого используют свойства логических операций, которые иначе называют законами алгебры логики.
Основные законы алгебры логики
Справедливость законов можно доказать построением таблиц истинности.
Пример 1. Упростим логическое выражение 
Последовательно применим дистрибутивный закон и закон исключенного третьего:
В общем случае можно предложить следующую последовательность действий:
Пример 2. Упростим логическое выражение 
.
Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.
Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:
Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат 
становился истинным высказыванием при любых значениях x.
Преобразуем исходное выражение, избавившись от импликации:
A, B, C — множества. Для них можно записать 
(U — универсальное множество).
Будем считать, что
.
Тогда 
, причем это минимально возможное множество А.
Так как множество B — это отрезок [2;12], а множество 
— это промежутки 
и
, то пересечением этих множеств будет служить промежуток 
. В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.
Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение
тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.
Перепишем исходное выражение в наших обозначениях и преобразуем его:
Рассмотрим предикат 
. В числе 2810=111002 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание 
будет ложным.
Рассмотрим предикат 
. В числе 4510=1011012 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание 
будет ложным.
Рассмотрим предикат 
. В числе 1710=100012 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.
По условию задачи надо, чтобы 
.
Запишем это выражение для рассмотренных множеств истинности:
Так как 
, примем 
.
Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.
Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: 
, и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 1011002 = 4410.
Значение любого логического выражения определяется значениями входящих в него логических переменных. Тем самым логическое выражение может рассматриваться как способ задания логической функции.
Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.
Упрощение логических выражений
Основная образовательная задача урока – научить учащихся умению упрощать логические выражения, правильно определять порядок выполнения операций в логическом выражении, устанавливать связи между различными частями сложных логических выражений, умение выбирать лучший вариант решения.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Обозначим: X – логическое высказывание, 
– инверсия, & – конъюнкция, 
– дизъюнкция, 
– импликация, 
– эквиваленция.
Применение основных законов логики для упрощения логических выражений.
Представленные примеры демонстрируют основные приемы упрощения логических выражений.
Упростить логическое выражение:
1) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций:
Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией.
Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией, затем операцией с константами.
2) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных дизъюнкцией. Сначала преобразуем выражения в скобках.
В первой скобке воспользуемся распределительным законом, во второй скобке – раскроем инверсию по правилу де Моргана и избавимся от инверсии по закону двойного отрицания.
Воспользуемся операцией переменной с ее инверсией.
3) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных конъюнкцией. Сначала преобразуем выражения в скобках.
Раскроем инверсию по правилу де Моргана, избавимся от инверсии по закону двойного отрицания.
Воспользуемся переместительным законом и поменяем порядок логических сомножителей.
Применим закон склеивания 
Воспользуемся распределительным законом, затем операцией переменной с ее инверсией, затем операцией с константами.
4) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
В выражении присутствует импликация. Сначала преобразуем импликацию 
.
Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.
Применим закон идемпотенции и перегруппируем логические слагаемые.
Воспользуемся распределительным законом и вынесем за скобки общий логический множитель.
Воспользуемся операцией с константами.
5) 
Рассмотрим 3 способа упрощения этого логического выражения.
1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.
Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией и законом идемпотенции.
Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией.
Воспользуемся законом идемпотенции.
2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.
Воспользуемся законом склеивания 
Воспользуемся операцией переменной с ее инверсией.
3 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.
Повторим второй сомножитель 
, что разрешено законом идемпотенции.
Сгруппируем два первых и два последних сомножителя.
Воспользуемся законом склеивания 
6) 
Рассмотрим 2 способа упрощения этого логического выражения.
1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
Воспользуемся распределительным законом и вынесем общий логический множитель за скобки.
2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
Введем вспомогательный логический сомножитель 
Сгруппируем 1 и 4, 2 и 3 логические слагаемые. Вынесем общие логические множители за скобки.
Воспользуемся операцией с константами и операцией переменной с ее инверсией.
Получили два логических выражения:
Теперь построим таблицы истинности и посмотрим, правильно ли упрощено логическое выражение
| X | Y | Z |  |  |  |  |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| X | Y | Z |  |  |  |  |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| X | Y | Z |  |  |  |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 |
| X | Y | Z |  |  |  |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Как видно из сравнения таблиц истинности формулы являются равносильными.