Булевы функции (лабораторные работы) — страница 2

  • Просмотров 10304
  • Скачиваний 851
  • Размер файла 470
    Кб

приведенных ниже формул являются тавтологиями, противоречиями, выполнимыми 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) VI. Упростить 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) VII. Равносильны ли следующие формулы 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Контрольные вопросы Булевы функции. Таблицы истинности. Число булевых функций от Элементарные булевы функции. Формулы алгебры логики. Классификация формул. Равносильные формулы. Законы равносильости. Логические уравнения. Лабораторная работа №2

Нормальные формы булевых функций Введем обозначение Формула Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (сокращенно ДНФ). Элементарная конъюнкция называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания). Правильная элементарная конъюнкция называется полной относительно переменных Совершенной дизъюнктивной нормальной

формой (СДНФ) относительно переменных Всякую булеву функцию Пример 1. Найти ДНФ для формулы Пример 2. Найти СДНФ для формулы 1 способ (табличный). Данный способ основан на разложении (1). Суть его состоит в следующем: 1. составляется таблица истинности для данной формулы; 2. в таблице истинности выделяются наборы 3. для каждого такого набора составляются элементарные конъюнкции; 4. составляем дизъюнкции построенных элементарных

конъюнкций. 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 2 способ (аналитический). Формула вида Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ). Элементарная дизъюнкция называется правильной, если у нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания). Правильная элементарная конъюнкция называется полной относительно переменных

Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных Всякую функцию где символ Пример 3. Найти КНФ для формулы Пример 4. Найти СКНФ для формулы 1 способ (табличный). Данный способ основан на разложении (2). Суть его состоит в следующем: 1. составляется таблица истинности для данной формулы; 2. в таблице истинности выделяются наборы 3. для каждого такого набора составляются элементарная дизъюнкция 4. составляем

конъюнкцию элементарных дизъюнкций. 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 2 способ (аналитический). Полиномом Жигалкина называется полином вида причем в каждом наборе Справедливы следующие равносильности: 21. 22. 23. 24. 25. Каждая булева функция может быть единственным образом выражена при помощи полинома Жегалкина. Пример 5. Выразить формулу 1 способ (метод неопределенных коэффициентов). При При При При Отсюда 2 способ.