Реализация произвольной булевой функции.

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

Минтерм - элементарная конъюнкция. Выражение представляет собой конъюнкцию (&) любого конечного множества попарно-различных булевых переменных ( ).

Макстерм - элементарная дизъюнкция. Выражение представляет собой дизъюнкцию (1) любого конечного множества попарно-различных булевых переменных ( ).

НКФ - нормальная конъюнктивная форма - конъюнкция любого конечного множества макстермов ( ).

НДФ - нормальная дизъюнктивная форма - дизъюнкция любого конечного множества минтермов ( ).

СДНФ - совершенная дизъюнктивная нормальная форма. Это ДНФ в которой все минтермы содержат полный набор всех булевых переменных в прямом или инверсном виде. Все минтермы должны состоять из одного количества элементов ( ).

СКНФ - КНФ, где все макстермы состоят из одного количества элементов.

Существуют два способа реализации булевых функций: с помощью СДНФ (если на выходе логической функции необходимо получить единицу) и с помощью СКНФ (если на выходе логической функции необходимо получить нуль). Рассмотрим реализацию логических функций на примере как СДНФ, так и СКНФ. Пусть задана логическая функция с помощью приведённой ниже таблицы:

Для реализации логических функций с помощью СДНФ необходимо:

1. Отметить все наборы аргументов, когда логическая функция принимает единичное значение (У=1). В данном случае таких вариантов у нас 4 шт.

2. Все аргументы, присутствующие в выделенных наборах необходимо привести к единичным значениям и собрать на элементах «И». Т.е получить следующие выражения:

У1 = , У2 = , У3 = , У4 = .

3. Полученные четыре промежуточных значения логической функции необходимо собрать на элементе «ИЛИ», т.е получить следующую функцию: У = .

В соответствии с приведёнными выражениями составим принципиальную схему данной функции.

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

Для реализации логических функций с помощью СКНФ необходимо:

1. Отметить все наборы аргументов, когда логическая функция принимает нулевое значение (У=0). В данном случае таких вариантов у нас 4 шт.

2. Все аргументы, присутствующие в выделенных наборах необходимо привести к нулевым значениям и собрать на элементах «ИЛИ». Т.е получить следующие выражения:

У1 = , У2 = , У3 = , У4 = .

3. Полученные четыре промежуточных значения логической функции необходимо собрать на элементе «И», т.е получить следующую функцию: У = .

В соответствии с приведёнными выражениями составим принципиальную схему данной функции.

Выбор способа реализации логической функции зависит от количества нулей и единиц в значении логической функции. Если меньше единиц, то выбирают СДНФ, если меньше нулей, то, соответственно, выбирают СКНФ. Таким образом, выбирают тот вариант, при котором требуется наименьшее количество деталей для построения схемы.

Необходимо отметить, что, из-за изобилия логических элементов «И-НЕ», логические функции реализуют именно на них, заменяя по теореме Де Моргана элементы «НЕ» и «ИЛИ». В этом случае, справедлива следующая замена: