Основные равносильности булевых формул.
Для любых формул A, B, C справедливы следующие равносильности: 1. Коммутативность. а) A б) AÚB º BÚA (для дизъюнкции). 2. Ассоциативность. а) A б) AÚ(BÚC) º (AÚB)ÚC (для дизъюнкции). 3. Дистрибутивность. а) A б) AÚ(B 4. Закон де Моргана. а) ( б) ( 5. Идемпотентность. а) A б) AÚA º A (для дизъюнкции). 6. Поглощение. а) A б) AÚA 7. Расщепление (склеивание). а)(A б) (AÚB) 8. Двойное отрицание.
9. Свойства констант. а)A 10. Закон противоречия. A 11. Закон “исключенного третьего”. AÚ Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “º”. Докажем, например, равносильность 4а. Для этого составим таблицу 10. Таблица 10
Из таблицы 5 видно, что Следующие важные равносильности показывают, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания: 12. A®B º 13. A«B º (A®B) Используя равносильности 3а и 3б и метод математической индукции, нетрудно получить также следующие равносильности (обобщенные законы дистрибутивности): 14. (A1ÚA2Ú...ÚAn) A1 15. (A1 (A1ÚB1) Используя равносильности 4а и 4б и метод математической индукции, можно получить также следующие равносильности (обобщенные законы де Моргана): 16. ( 17. ( В равносильностях 1 – 17 в качестве A, B, Ai, Bi могут быть подставлены любые формулы и, в частности, переменные. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|