Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Основные эквивалентности

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности




     Приводимые основные эквивалентности часто оказываются полезными при оперировании с булевыми функциями.
     Ниже H, H1, H2 ... означают некоторые булевы функции.
     1. Закон двойного отрицания:
         H=¬(¬H)
     2. Идемпотентность:
         H&H=H
         HvH=H
     3. Коммутативность:
         H1*H2=H2*H1, где символ * означает одну из связок &, v, ⊕, ∼, |, ↓
     4. Ассоциативность:
         H1*(H2*H3)=(H1*H2)*H3, где символ * означает одну из связок &, v, ⊕, ∼
     5. Дистрибутивность:
         H1&(H2vH3)=(H1&H2)v(H1&H3)
         H1v(H2&H3)=(H1vH2)&(H1vH3)
         H1&(H2⊕H3)=(H1&H2)⊕(H1&H3)
     6. Законы де Моргана:
         ¬(H1&H2)=¬H1v¬H2
         ¬(H1vH2)=¬H1&¬H2
     7. Правила поглощения:
         H1v(H1&H2)=H1
         H1&(H1vH2)=H1
     8. Законы склеивания:
         H1&H2vH1&¬H2=H1
         (H1vH2)&(H1v¬H2)=H1
     9. Законы инверсий:
         Hv¬H=1
         H&¬H=0
     10. Правила операций с константами:
         Hv1=1
         H&1=H
         Hv0=H
         H&0=0
     Для проверки истинности приведенных эквивалентностей достаточно построить соответствующие таблицы истинности.
     Отметим, что свойство ассоциативности операции позволяет распространить эту операцию для любого количества переменных. Так, например, запись XvYvZvW корректна, т.к. любая расстановка скобок приводит к одной и той же функции. Коммутативность операции позволяет менять местами переменные в формуле. Например, X&Y&Z&W=W&Y&X&Z.

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru