Булевы функции и построение сокращённой булевой функции

В лекции сформулируем основные понятия, связанные с булевыми функциями, а также представим алгоритм построения сокращённой булевой функции.

Формальное определение булевой функции

Теорема о числе булевых функций

Заметим, что:

Теорема о числе строк таблицы истинности

Способы задания булевых функций

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

Таблицы истинности для булевых функций двух переменных

Варианты задания булевых функций

Минимизация дизъюнктивных нормальных форм

Определение. Булеву функцию G назовем импликантом булевой функции F, если для любых наборов значений аргументов этих функций из равенства G = 1 следует равенство F = 1.

Определение. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестает быть импликантом, то такой импликант называется простым.

Определение. Сокращенная ДНФ функции F (сокр. ДНФ F) есть дизъюнкция всех простых импликантов функции F.

Замечание: всякая булева функция F реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Алгоритм построения сокращенной дизъюнктивной нормальной формы с помощью совершенной конъюнктивной нормальной формы

Перечень шагов для построения сокращённой дизъюнктивной нормальной формы

Пример. Для булевой функции, заданной вектором значений, запишите сокращенную ДНФ: F = (01100100).

Порядок решения примера.

Таблица истинности, соответствующая булевой функции F = (01100100):

Таблица истинности заданной булевой функции

Шаг 1. Запишем для неё совершенную конъюнктивную нормальную форму (для этого см. алгоритм в https://zen.yandex.ru/media/id/603a418d1684900aa2499416/62451b2ec3c4ec4ac74b9369):

Совершенная конъюнктивная нормальная форма для булевой функции F = (01100100)

Шаг 2. Раскроем скобки и произведём эквивалентные преобразования.

Раскрытие скобок в СКНФ для булевой функции F = (01100100)

Шаг 3. Произведём поглощение и удалим дублирующие элементы.

Поглощение для булевой функции F = (01100100)

Шаг 4. Повторим шаги 2 и 3 до тех под, пока не получим ДНФ.

Повторения 2 и 3 шага алгоритма

В качестве Упражнения запишите сокращённую дизъюнктивную нормальную форму для булевых функций, векторы значений которых указаны в таблице:

Варианты булевых функций для самостоятельного решения