Как избавиться от импликации
С помощью тождественных преобразований максимально упростить следующее логическое выражение:
`bar C vv` (`A` & `С`) `vv` (`bar(A vv C vv bar(B)`)
Максимально упростить, это значит довести выражение до такого вида, когда невозможно применить ни один из законов алгебры логики, которые сокращают длину выражения.
Для того, чтобы не запутаться, можно использовать общую стратегию упрощения логических выражений.
1) Избавиться от операций импликации.
2) Продвинуть отрицание вглубь выражения. То есть применять законы де Моргана, и закон двойного отрицания пока знак отрицания не будет стоять только над переменными (но не над операциями).
После пункта 2 наступает относительная свобода действий. Можно использовать тождества поглощения или раскрывать скобки.
В нашей задаче операция импликации отсутствует, поэтому первый пункт мы пропускаем. Переходим к пункту 2. Применяем два раза второй закон де Моргана (для дизъюнкции) и закон двойного отрицания к правой скобке и получаем следующее логическое выражение:
`bar C vv ` (`A` & `C`) `vv` (`bar A` & `bar C` & `B`)
Если теперь внимательно посмотреть на выражение, то очевидно, что к первому и третьему слагаемому можно применить первый закон поглощения, так как отрицание переменной `C` является первым слагаемым и входит в третье в качестве множителя.
Поскольку дизъюнкцию ещё называют логическим сложением, её операнды называют слагаемыми, аналогично конъюнкция – это логическое умножение, и её операнды называют множителями.
После применения первого закона поглощения получается следующее логическое выражение:
Применим второй (нестандартный для алгебры) закон дистрибутивности. Получаем:
(`bar C vv A`) & (`bar C vv C`)
Ко второй скобке применяем закон исключённого третьего, превращаем её в единицу, а затем применяем закон поглощения константы `1` и в итоге получаем выражение: `bar C vv A`, которое упростить уже нельзя.
Для лучшего понимания, рекомендуется выписать исходное логическое выражение, последовательно применить к нему все описанные действия и сравнить свой результат с приведённым в конце решения задачи.
Обратите внимание, что исходное логическое выражение зависело от трёх переменных (`A, B, C`) , в то время как упрощённое в итоге зависит от двух логических переменных (`A` и `C`). При этом выражения всё равно остаются равносильными! Это происходит потому, что в процессе упрощения применялись законы поглощения. Аналогичный результат мог бы получиться, если в процессе упрощения выражения используются законы поглощения переменных константами. Исчезновение переменной при упрощении означает, что в исходном выражении она является несущественной.
Укажите значения переменных `K`, `L`, `M`, `N`, при которых логическое выражение `(L vv M) ^^ (¬ K -> M) ^^ ¬ N ^^ ¬ M` истинно.
Будем следовать стратегии, описанной в предыдущем примере. Первым делом избавляемся от операции импликации. Получаем следующее выражение:
`(L vv M) ^^ ( K vv M) ^^ ¬ N ^^ ¬ M`
Отрицание вглубь продвигать не надо. Теперь раскроем скобки. Для упрощения условимся операцию конъюнкции никак не обозначать (по аналогии с алгеброй чисел).
`(LK vv LM vv MK vv M) ( ¬ N) ( ¬ M)`
В первой скобке можно применить тождество поглощения, и «съесть» второе и третье слагаемое, которые содержат M в качестве множителя. Получается такое выражение:
`(LK vv M) ( ¬ N) ( ¬ M)`
Выполнив оставшиеся операции умножения, получим следующий результат:
Получили одну конъюнкцию. Следовательно, существует всего один набор значений переменных, при котором получится значение «1»: `L=1`, `K=1`, `N=0`, `M=0`.
Сколько решений имеет уравнение:
`(((K¬L¬N) (¬L -> M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M))) (K`\/`N)=1`
Исходное выражение достаточно сложное, поэтому будем его упрощать. Первым делом избавимся от импликаций, получим:
`(((K¬L¬N) (L`\/ `M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M))) (K`\/`N) = 1`
Теперь раскроем скобки. Для упрощения условимся не записывать слагаемые, куда одновременно входят некоторая переменная и её отрицание (они всё равно равны нулю):
`(K¬L¬NM` \/ `¬K¬L¬M` \/ `N¬L¬M) (K`\/`N) = 1`
Продолжаем раскрытие скобок. Получаем:
`K¬L¬NM` \/ `¬K¬L¬MN` \/ `KN¬L¬M` \/ `N¬L¬M = 1`
Ко второму, третьему и четвёртому слагаемому можно применить тождество поглощения. В итоге получится:
`K¬L¬NM` \/ `N¬L¬M = 1`
На этом упрощение закончено, теперь будем анализировать. Дизъюнкция равна единице, если хотя бы одно из слагаемых равно единице. Первое слагаемое равно единице на единственном наборе переменных: (`K=1`, `L=0`, `N=0`, `M=1`). Второе слагаемое равно единице на двух наборах: (`N=1`, `L=0`, `M=0`, `K` – любое (или `0` или `1`)). Соответственно, уравнение имеет три различных решения.
В нарушении правил обмена валюты подозреваются четыре работника банка — Антипов (`A`), Борисов (`B`), Цветков (`C`) и Дмитриев (`D`). Известно, что:
1) Если `А` нарушил, то и `В` нарушил правила обмена валюты.
2) Если `B` нарушил, то и `C` нарушил или `A` не нарушал.
3) Если `D` не нарушил, то `A` нарушил, а `C` не нарушал.
4) Если `D` нарушил, то и `A` нарушил.
Кто из подозреваемых нарушил правила обмена валюты?
Чтобы решить эту задачу, необходимо провести процесс формализации условия, сформировать единое логическое выражение и провести его упрощение. Выделим из условия четыре простых высказывания: «`A` нарушил правила», «`B` нарушил правила», «`C` нарушил правила», и «`D` нарушил правила». Обозначим их соответственно буквами `A`, `B`, `C`, `D`. Тогда высказывания из условия формализуются следующим образом (конъюнкция не обозначается никак):
Нам известно, что выполняются все 4 высказывания, следовательно, нужно объединить их знаками конъюнкции и найти наборы, при которых получившееся общее высказывание будет истинным. Эти наборы и покажут нам, какие возможны ситуации (правила обмена нарушил тот, у кого переменная в итоговом наборе имеет значение «1»).
Итак, строим логическое выражение:
`(A -> B)( B -> C` \/ `¬A)( ¬D -> A¬C)( D -> A)`.
Теперь будем его упрощать. По алгоритму первым делом избавляемся от операции импликации. Получаем следующее выражение:
`(¬A` \/ `B)( ¬B` \/ `C` \/ `¬A)( D` \/ `A¬C)( ¬D` \/ `A)`.
Раскрываем скобки. Первую перемножаем со второй, а третью с четвёртой.
`(¬A¬B` \/ `¬AC` \/ `¬A` \/ `BC` \/ `B¬A) ( DA` \/ `A¬C¬D` \/ `A¬C)`.
Напомним, что слагаемые, равные нулю по причине того, что в них входит сразу и переменная и её отрицание, мы не записываем. В первой скобке теперь можно применить тождество поглощения, и «съесть» все слагаемые, имеющие в своём составе `A` с отрицанием. Во второй скобке можно также применить тождество поглощения, и «съесть» второе слагаемое. В итоге получаем:
`( ¬A` \/ `BC ) ( DA` \/ `A¬C)`.
При раскрытии оставшихся скобок три из четырёх слагаемых окажутся равными нулю, а последнее будет выглядеть следующим образом: `ABCD`. Из этого следует, что все четверо работников банка нарушили правило обмена валюты. (Только в этой ситуации предположения из условия задачи одновременно выполняются).
Правила обмена валюты нарушили все.
Известно, что обе надписи на дверях либо истинны, либо ложны одновременно. Надпись на первой двери – «Клад за другой дверью», на второй двери – «Клада за этой дверью нет, а за другой – есть». Где находится клад?
По сути нас интересуют два простых высказывания: «Клад есть за первой дверью» и «Клад есть за второй дверью». Обозначим первое из них буквой `A`, а второе буквой `B`. Тогда изначальные предположения формализуются следующим образом:
В этой задаче в отличие от предыдущей у нас две возможные ситуации относительно комбинирования начальных предположений – они либо оба истинны, либо оба ложны. Предположим, что они оба истинны, тогда при их перемножении получится тождественный ноль, что означает невозможность данной ситуации.
Предположим, что оба высказывания ложны, тогда необходимо перед перемножением на каждое из них «навесить» отрицание (рассматривать истинность противоположных высказываний) В итоге получится следующее логическое выражение:
Упрощаем его по алгоритму: отрицание продвигаем вглубь, применяя тождество Де Моргана. Получаем:
`¬B (B` \/ `¬A)`.
Раскроем скобки. Первое слагаемое сокращается, а второе выглядит следующим образом: `¬B¬A`.
Полученный результат означает, что условия задачи выполняются, только в случае, когда оба высказывания ложны, а это означает, что клада нет ни за одной дверью. Не повезло нам `J`.
Клада нет ни за одной дверью.
В заключение приведём общую схему решения текстовых логических задач, которую мы уже применяли на практике при разборе примеров.
1) Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.
2) Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций.
3) Составить единое логическое выражение для всех требований задачи (возможно не одно).
4) Используя законы алгебры логики попытаться упростить полученное выражение и вычислить все его значения либо построить таблицу истинности для рассматриваемого выражения (Таблицу можно строить, если в выражении не более трёх логических переменных).
5) Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным;
6) Проверить, удовлетворяет ли полученное решение условию задачи.
Среди задач алгебры логики часто встречаются задачи на определение количества решений систем логических уравнений. Рассмотрим примеры некоторых их них.
Найдите количество решений системы уравнений:
`(x2-=x1)+x2&x3+ not x2& not x3=1`
`(x3-=x1)+x3&x4+ not x3& not x4=1`
`(x9-=x1)+x9 & x10+ not x9 & not x10=1`
где `x1 … x10` — неизвестные логические величины
Упростим исходные уравнения, заметив, что, `(x2&x3+ not x2& notx3=(x2-=x3)`. Исходную систему запишем в виде:
В первом уравнении используются три переменных `x1`, `x2` и `x3`. Значения `x1` и `x2` могут быть выбраны произвольно четырьмя способами:
Источник
Упрощение логических выражений
Основная образовательная задача урока – научить учащихся умению упрощать логические выражения, правильно определять порядок выполнения операций в логическом выражении, устанавливать связи между различными частями сложных логических выражений, умение выбирать лучший вариант решения.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Обозначим: 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 |
Как видно из сравнения таблиц истинности формулы являются равносильными.
Источник