Практическая работа № 6

Минимизация алгебраических преобразований.

Цель работы

Научиться минимизировать формулы алгебры высказываний.

Теоретическая часть

Очень часто СДНФ и СКНФ, которые строятся по таблице истинности, оказываются весьма сложными. Поэтому возникает проблема построения минимальных форм для данной функции.

Импликант булевой функции f - булева функция g, такая, что для любых наборов значений аргументов этих функций из равенства g=1 следует, что f=1. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестает быть импликантом, то такой импликант называется простым.

Сокращенная ДНФ функции f есть дизъюнкция всех простых импликантов функции f. Всякая функция реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Алгоритм построения сокращенной ДНФ с помощью СКНФ.

1. По таблице истинности строим СКНФ функции f.
2. В СКНФ раскрываем скобки, удаляем дублирующие элементы (А ˄ А=А, А ˅ А=А) и элементы, которые содержат переменную с её отрицание (А ˄ Ā=0)
3. Проводим поглощение (А ˅ АВ=А) и удаляем дублирующие элементы. Получаем сокращенную ДНФ для функции f.