В лекции сформулируем основные понятия, связанные с булевыми функциями, а также представим алгоритм построения сокращённой булевой функции.
Заметим, что:
Способы задания булевых функций
Способ 1. При задании булевых функций удобно пользоваться таблицами истинности, которые перечисляют всевозможные комбинации истинности и ложности булевых функций:
Минимизация дизъюнктивных нормальных форм
Определение. Булеву функцию G назовем импликантом булевой функции F, если для любых наборов значений аргументов этих функций из равенства G = 1 следует равенство F = 1.
Определение. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестает быть импликантом, то такой импликант называется простым.
Определение. Сокращенная ДНФ функции F (сокр. ДНФ F) есть дизъюнкция всех простых импликантов функции F.
Замечание: всякая булева функция F реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
Алгоритм построения сокращенной дизъюнктивной нормальной формы с помощью совершенной конъюнктивной нормальной формы
Пример. Для булевой функции, заданной вектором значений, запишите сокращенную ДНФ: F = (01100100).
Порядок решения примера.
Таблица истинности, соответствующая булевой функции F = (01100100):
Шаг 1. Запишем для неё совершенную конъюнктивную нормальную форму (для этого см. алгоритм в https://zen.yandex.ru/media/id/603a418d1684900aa2499416/62451b2ec3c4ec4ac74b9369):
Шаг 2. Раскроем скобки и произведём эквивалентные преобразования.
Шаг 3. Произведём поглощение и удалим дублирующие элементы.
Шаг 4. Повторим шаги 2 и 3 до тех под, пока не получим ДНФ.
В качестве Упражнения запишите сокращённую дизъюнктивную нормальную форму для булевых функций, векторы значений которых указаны в таблице:
