Задать вопрос юристу

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

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

.

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

, .

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

, .

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

, .

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

, .

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

, .

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

, , ,

, , .

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

,

,

,

,

,

,

,

,

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

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

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

Переменная булевой функции 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. 3.4. Основные равносильности для предикатов
  2. Основные равносильности.
  3. 1.5. Равносильные формулы
  4. 2.4.9. Равносильность формул логики предикатов
  5. 2.1.3. Равносильность формул логики высказываний
  6. Элементарные булевы функции. Равносильности
  7. Два заблуждения не равносильны двум правдам
  8. 1.11. Равносильность и следствия в задачах с квадратным трехчленом
  9. 1. Линейные операторы в линейных нормированных пространствах. Равносильность непрерывности и ограниченности линейного оператора. Понятие нормы ограниченного оператора. Различные формулы для вычисления норм. Примеры линейных ограниченных операторов.
  10. §11.3. Понятие, сущность и основные черты конституции как основного государства
  11. Основное содержание работы В. Франкла «Основные понятия логотерапии»
  12. ЛЕКЦИЯ 3 ОСНОВНЫЕ МОДЕЛИ ОЦЕНКИ АКТИВОВ Основные понятия:
  13. Основные принципы «новой свободы» В.Вильсона. Основные социально-экономические реформы накануне и в годы первой мировой войны.
  14. Питання 2.Перевірка стану бухгалтерського обліку основних засобів, правильності та своєчасності відображення операцій руху основних засобів
  15. Основные обязанности и основные права
  16. 1.1. ОСНОВНЫЕ НАПРАВЛЕННЯ СОЗДАНИЯ СИСТЕМЫРЕАБИЛИТАЦИИ ИНВАЛИДОВ В РФ. ДЕФИНИЦИИ ОСНОВНЫХ ИСПОЛЬЗУЕМЫХ ТЕРМИНОВ. ПРИНЦИПЫ И МЕТОДЫ РЕАБИЛИТАЦИИ ИНВАЛИДОВ
  17. § 1. Структура ОАО «РЖД», его основные экономические показатели. Инвестиционный процесс, сложившийся на предприятиях железнодорожного транспорта, его основные криминалистически значимые элементы
  18. 511. Как установить, может ли требование к основному должнику быть удовлетворено (погашено) «путем зачета встречного требования к основному должнику» (п.2 ст.399 ГК)?
  19. ЛЕКЦИЯ 2 РИСК И ДОХОДНОСТЬ: ОСНОВНЫЕ ПОНЯТИЯ И МЕТОДЫ АНАЛИЗА Основные понятия:
  20. 105. Правове регулювання організації виробництва в основних галузях сільського господарства: рослинництва, тваринництва, птаховодства тощо. Права та обов'язки сільськогосподарських організацій по організації і веденню основних видів діяльності.