Головна |
При вирішенні багатьох логічних задач часто доводиться спрощувати формули, отримані при формалізації їх умов. Спрощення формул в алгебрі логіки виробляється на основі еквівалентних перетворень, що спираються на основні логічні закони. Закони алгебри логіки - це тавтології (або теореми).
1. Закон тотожності:
А = А
2. Закон несуперечливий:
3. Закон виключення третього:
4. Закон подвійного заперечення:
5. Закони істини і брехні (властивості констант):
6. Закони ідемпотентності:
7. Комутативні закони:
8. Асоціативні закони:
- диз'юнкції
- кон'юнкції
9. Дистрибутивні закони:
- 1-ий дистрибутивний закон
- 2-ий дистрибутивний закон
10. Закони поглинання:
11. Закони де Моргана:
12. Закон імплікації:
13. Закон еквівалентності:
14. Властивості додавання «по модулю два»:
Справедливість цих законів можна довести за допомогою таблиць істинності складних логічних зв'язків описуваних законів.
Наслідки з законів алгебри логіки (часто використовуються при спрощення логічних виразів).
1. Правило поглинання. Дане правило є наслідком з дистрибутивного закону. Воно може бути записано в наступному вигляді:
.
2. Правило згортки. Правило є наслідком з другого дистрибутивного закону. Запис правила:
а) ;
б) .
3. Правило розширення. Правило записується в наступному вигляді:
.
4. Правило склеювання. Базується на понятті сусідніх кон'юнкція. Сусідніми називаються кон'юнкції, що відрізняються поданням однієї змінної. Наприклад, кон'юнкції и , и є попарно сусідніми. У першій парі кон'юнкції відрізняються поданням х2, А в другій - поданням х1. За цим змінним кон'юнкції склеюються.
Формулювання правила: дві сусідні кон'юнкції склеюються з утворенням однієї кон'юнкції меншого рангу; зникає та змінна, по якій кон'юнкція склеюється.
, .
Контрольні питання
1. Перерахуйте основні закони алгебри логіки. Як дозивается їх справедливість?
2. Перерахуйте слідства із законів алгебри логіки.
Дискретна математика | Введення в алгебру логіки | Основні функції алгебри логіки | Побудова формул алгебри логіки по заданій таблиці істинності | Деякі замкнуті класи (класи Посту). поняття базису | Алгебра Жегалкина і лінійні функції | Методи мінімізації логічних функцій | Неповністю певні логічні функції | Бінарні діаграми рішень (БДР) | Побудова логічних схем |