Равносильные преобразования
Равносильность формул
1. Закон двойного отрицания
2. Переместительный (коммутативный) закон
3. Сочетательный (ассоциативный) закон
4. Распределительный (дистрибутивный) закон
5. Закон общей инверсии (законы де Моргана)
6. Закон идемпотентности
7. Законы исключения констант
8. Закон противоречия
9. Закон исключения третьего
10. Закон поглощения
11. Закон исключения (склеивания)
152.21K
Category: informaticsinformatics

Законы алгебры логики. Равносильные преобразования

1.

2. Равносильные преобразования

• Равносильные преобразования логических
формул имеют то же назначение, что и
преобразования формул в обычной алгебре.
• Они служат для упрощения формул или
приведения их к определённому виду путем
использования основных законов алгебры
логики.

3.

Под упрощением формулы, понимают
равносильное преобразование,
приводящее к формуле, которая
• либо содержит по сравнению с исходной
меньшее число операций конъюнкции и
дизъюнкции и инверсий
• не содержит отрицаний неэлементарных
формул, либо содержит их меньшее число

4. Равносильность формул

• Две формулы F и G называются
равносильными, если на любом наборе
пропозиционных переменных λ(F) =
λ(G).
• Обозначения: F ≡ G.

5. 1. Закон двойного отрицания

Двойное отрицание исключает
отрицание.
A A

6. 2. Переместительный (коммутативный) закон

— для логического сложения:
A B B A
— для логического умножения:
A& B B & A

7. 3. Сочетательный (ассоциативный) закон

— для логического сложения:
( A B) C A ( B C )
— для логического умножения:
( A & B) & C A & ( B & C )

8. 4. Распределительный (дистрибутивный) закон

— для логического сложения:
( A B) & ( A C ) A ( B & C )
— для логического умножения:
( A & B) ( A & C ) A & ( B C )

9. 5. Закон общей инверсии (законы де Моргана)

— для логического сложения
А В A & B
— для логического умножения:
А& В A B

10. 6. Закон идемпотентности

— для логического сложения:
A A A
— для логического умножения:
A& A A
Закон означает отсутствие показателей степени.

11. 7. Законы исключения констант

— для логического сложения:
А 0 A
А 1 1
— для логического умножения:
А &1 A
А&0 0

12. 8. Закон противоречия

Невозможно, чтобы противоречащие
высказывания были одновременно
истинными.
A&A 0

13. 9. Закон исключения третьего

Из двух противоречащих высказываний об
одном и том же предмете одно всегда
истинно, а второе — ложно, третьего не дано.
A A 1

14. 10. Закон поглощения

— для логического сложения:
— для логического умножения:
A & ( A B) A

15. 11. Закон исключения (склеивания)

— для логического сложения:
( A B) * ( A B) B
— для логического умножения:
A* B A* B B
English     Русский Rules