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