Минимизация алгебраических преобразований.
Цель работы
Научиться минимизировать формулы алгебры высказываний.
Теоретическая часть
Очень часто СДНФ и СКНФ, которые строятся по таблице истинности, оказываются весьма сложными. Поэтому возникает проблема построения минимальных форм для данной функции.
Импликант булевой функции f - булева функция g, такая, что для любых наборов значений аргументов этих функций из равенства g=1 следует, что f=1. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестает быть импликантом, то такой импликант называется простым.
Сокращенная ДНФ функции f есть дизъюнкция всех простых импликантов функции f. Всякая функция реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
Алгоритм построения сокращенной ДНФ с помощью СКНФ.
- По таблице истинности строим СКНФ функции f.
- В СКНФ раскрываем скобки, удаляем дублирующие элементы (А ˄ А=А, А ˅ А=А) и элементы, которые содержат переменную с её отрицание (А ˄ Ā=0)
- Проводим поглощение (А ˅ АВ=А) и удаляем дублирующие элементы. Получаем сокращенную ДНФ для функции f.