Определение. Булева функция (формула логики высказываний) F называется частично (не всюду) определённой, если не для всех возможных наборов значений входящих в функцию F переменных указаны её значения.
Алгоритм минимизации частично определенных функций в классе дизъюнктивных нормальных форм (ДНФ) включает в себя следующие шаги.
Шаг 1. Доопределить булеву функцию F нулями на тех наборах значений переменных, где она не определена. Полученную булеву функцию обозначить через F0.
Шаг 2. Построить совершенную дизъюнктивную нормальную форму (СДНФ) булевой функции F0.
Шаг 3. Доопределить булеву функцию F единицами на тех наборах значений переменных, где она не определена. Полученную булеву функцию обозначить через F1.
Шаг 4. Построить сокращенную ДНФ функции F1. Занумеровать в любом порядке слагаемые сокращенной ДНФ функции F1.
Шаг 5. Составить таблицу покрытий по следующему правилу: слагаемые СДНФ функции F0 записать в первой строке, а слагаемые сокращенной ДНФ функции F1 вместе с номерами - в первом столбце. Если слагаемое сокращенной ДНФ функции F1 целиком входит в слагаемое СДНФ функции F0, то на пересечении соответствующих строки и столбца записать номер слагаемого сокращенной ДНФ функции F1.
Шаг 6. Составить решеточное выражение по следующему правилу: в каждом столбце таблицы покрытий номера, полученные в пункте 5, соединить знаком дизъюнкции и взять конъюнкцию этих дизъюнкций.
Шаг 7. Раскрыть скобки в решеточном выражении и, если необходимо, воспользоваться правилом поглощения.
Шаг 8. Каждое слагаемое в полученном выражении соответствует тупиковой ДНФ булевой функции F. Для восстановления тупиковой ДНФ булевой функции F необходимо взять дизъюнкции тех слагаемых, номера которых указаны в полученном выражении.
Шаг 9. Из тупиковых ДНФ функции F выбрать минимальные ДНФ функции F.
Заметим, что при минимизации функции F в классе конъюнктивных нормальных форм (КНФ) необходимо использовать функции
Пример построения тупиковых и минимальных ДНФ для булевых функций.
Задание. Получите тупиковые и минимальные ДНФ для частично определенной булевой функции F = (1110**01).
Решение. Для получения тупиковых и минимальных ДНФ частично определенной булевой функции F = (1110**01) воспользуется алгоритмом минимизации частично определенных булевых функций в классе ДНФ, описание которого показано выше.
Запишем частично определённую булеву функцию F = (1110**01) в виде следующей таблицы истинности:
Вместо * в таблице истинности напишем 0. Получим функцию f0 (x, y, z) (в следующей таблице показана в столбце 5).
Заменим * в первоначальной таблице истинности на 1. Получим функцию f1 (x, y, z) (в следующей таблице показана в столбце 6).
Построим СДНФ функции f0 (x, y, z):
Для построения сокращённой дизъюнктивной нормальной формы булевой функции f1 построим совершенную конъюнктивную нормальную форму (СКНФ) функции f1(x, y, z):
Раскроем скобки в выражении для СКНФ f1(x, y, z) и проведём эквивалентные преобразования. Получим следующую сокращенную ДНФ функции f1(x, y, z):
Составим следующую таблицу покрытий:
Запишем решеточное выражение, преобразуем его, раскрыв скобки, получаем единственное слагаемое, которое восстанавливаем согласно описанию в шаге 8, получим:
Найдена тупиковая ДНФ частично определенной булевой функции F = (1110**01). Эта единственная полученная тупиковая ДНФ является и минимальной ДНФ для частично определенной булевой функции F = (1110**01).
Упражнение. Для частично-определенной булевой функции из таблицы ниже, заданной вектором значений, определите минимальную ДНФ.
Запишите в комментарии под лекцией: Если частично-определенная булева функция F = (вектор из задания), то её минимальная ДНФ равняется: далее запись соответствующей минимальной ДНФ. Пример Упражнения. Если частично-определенная булева функция F = (1110**01), то её минимальная ДНФ равняется: НЕzНЕx ИЛИ НЕy ИЛИ НЕхНЕz.
