Законы алгебры логики и правила преобразования логических выражений
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
| Закон | Формулировка |
| 1. Закон тождества Х = Х | Всякое высказывание тождественно самому себе. |
| 2. Закон исключенного третьего X \/ X = 1 | Высказывание может быть либо истинным, либо ложным, третьего не дано. Следовательно, результат логического сложения высказывания и его отрицания всегда принимает значение "истина". |
| 3. Закон непротиворечия X/\ X = 0 | Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно. |
| 4. Закон двойного отрицания X = X | Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание. |
| 5. Переместительный (коммутативный) закон X /\ Y = Y /\ X, X /\ Y = Y/\X | Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания. |
| 6. Сочетательный (ассоциативный) закон (X \/Y) \/Z = X \/ (Y \/Z) (X/\Y)/\Z=X/\(Y/\Z) | При одинаковых знаках скобки можно ставить произвольно или вообще опускать. |
| 5. Распределительный (дистрибутивный) закон (X/\Y)\/Z= (X/\Z) \/ (Y/\Z) (X /\ Y) \/ Z = (X\/Z) /\ (Y\/Z) | Определяет правило выноса общего высказывания за скобку. |
| 7. Закон общей инверсии Закон де Моргана (X\/Y) = X/\ Y (X/\Y) = X\/Y | Закон общей инверсии. |
| 8. Закон равносильности (идемпотентности) A\/A= A; A/\A = A. | от латинских слов idem - тот же самый и potens - сильный |
| 9. Законы исключения констант: A\/1=1, A\/0=A; A/\1=A, A/\0 =0. | |
| 10. Закон поглощения: A\/(A/\B)=A; A/\(A\/B) = A. | |
| 11. Закон исключения (склеивания): (A/\B) \/ (A/\B) =B; (A\/B)/\(A\/B) = B. | |
| 12. Закон контрапозиции (правило перевертывания): (A=>B) = (B=>A). | |
| 13. А => В = A \/ В;14. (A=>B)=A/\B | |
| 14. А<=>В = (А/\В)\/(A/\B); | |
| 15. А<=>В= (A\/В)/\(А\/B). |
Применим законы алгебры логики. Покажем на примере как можно упростить логическое выражение:
|
|
|
|
|
|
1) (A/\B)\/(A/\B) = A/\(B \/ B)= A/\1 = A,
2) (X\/Y)/\(X/\Y).
Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами.
(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.
Решение логических
Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:
· средствами алгебры логики;
· табличный;
· с помощью рассуждений.
Познакомимся с ними поочередно.
Решение логических задач средствами алгебры логики.
Обычно используется следующая схема решения:
1. изучается условие задачи;
2. вводится система обозначений для логических высказываний;
3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
|
|
|
4. определяются значения истинности этой логической формулы;
5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.
Пример 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.
- Вот увидишь, Шумахер не придет первым, - сказал Джон. Первым будет Хилл.
- Да нет же, победителем будет, как всегда, Шумахер, - воскликнул Ник. - А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
- Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?
Решение. Введем обозначения для логических высказываний: Ш - победит Шумахер; Х - победит Хилл; А - победит Алези.
Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей: Джон: Ш/\Х, Ник: Ш/\А, Питер: Х.
Высказывание Ш /\ А/\ Х истинно только при Ш=1, А=0, Х=0.
Ответ. Победителем этапа гонок стал Шумахер.
Дата добавления: 2019-09-08; просмотров: 357; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!