<<
>>

Основные равносильности

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

.

Идемпотентность

, .

Коммутативность

, .

Ассоциативность

, .

Дистрибутивность

, .

Законы де Моргана

, .

Формулы с константами

, , ,

, , .

Дополнительные равносильности

,

,

,

,

,

,

,

,

, (законы склеивания),

(закон поглощения).

(закон обобщенного склеивания).

Переменная булевой функции F называется несущественной (или фиктивной), если , то есть если изменение значения в каждом наборе значений не меняет значения функции. При этом существует такая формула, реализующая эту булеву функцию, в которой отсутствует .

Пример. С помощью основных равносильностей доказать, что в булевой функции F = переменная является фиктивной.

Решение. Применяя закон поглощения и закон склеивания, получим

F =.

Так как существует такая формула, реализующая эту булеву функцию, в которой отсутствует , то эта переменная является фиктивной.

Пример. С помощью таблицы истинности убедиться в справедливости законов де Моргана .

Решение. Построим таблицу истинности для и .

0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Так как в таблице истинности булевым функциям и соответствуют одинаковые столбцы, то формулы и равносильны.

Пример. С помощью основных равносильностей доказать закон обобщенного склеивания .

Решение. Применяя закон склеивания (в обратном порядке, то есть ) и дистрибутивность (то есть вынесем за скобки и ), получим

.

Пример. С помощью основных равносильностей доказать, что .

Решение. Применяя основные равносильности, получим

.

<< | >>
Источник: БУЛЕВЫ ФУНКЦИИ. Лекция. 2016

Еще по теме Основные равносильности:

  1. Глава 11ОСНОВНЫЕ ЧЕРТЫ ДУХОВНОСТИ РУССКОГО НАРОДА
  2. § 3. Основные морфологические разряды наречий
  3. § 3. Основные морфологические разряды наречий
  4. Основные понятия
  5. 1. Основные черты философского знания
  6. КУЛЬТУРА И ЕЕ ОСНОВНЫЕ ФУНКЦИИ
  7. ПУТИ УЛУЧШЕНИЯ ИСПОЛЬЗОВАНИЯ ОСНОВНЫХ ФОНДОВ
  8. § 3. Основные морфологические разряды наречий
  9. 1.5.Векторы. Основные операции над векторами.
  10. Основные равносильности.
  11. Основные формально-логические законы
  12. з. Основные уравнения и задачи математической физики
  13. I. Основные математические понятия и факты
  14. ОСНОВНЫЕ УЗЛЫ РУССКОЙ РЕЧИ-ИДЕИ Б XIX—XX ВЕКАХ
  15. Элементарные булевы функции. Равносильности
  16. Основные равносильности
  17. 1.3. Основные тождества алгебры множеств
  18. 2.1.3. Равносильность формул логики высказываний
  19. 1.5. Равносильные формулы
  20. 3.4. Основные равносильности для предикатов