Минимизация булевых функций

Таблица 17.1

№ п/п	x 1	x 2	x 3	F

Такая таблица называется таблица истинности.

Алгебраическая форма представления булевых функций используется для минимизации (упрощения формул) и для построения логических схем. Существует две формы алгебраических функций – дизъюнктивная и конъюнктивная. Дизъюнктивная нормальная форма представляет собой сумму элементарных произведений аргументов, например

Если каждое слагаемое содержит все аргументы или их отрицания, то получаем совершенную дизъюнктивную нормальную форму (СДФН), например

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

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

(17.4)

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

(17.5)

На основании полученных формул (17.4) или (17.5) можно построить логическую схему, состоящую из элементов "ИЛИ", "И", "НЕ". Для функции (17.4) сначала изображаются инверторы, затем ячейки "И" и потом ячейки "ИЛИ" (см. рис. 17.5).

Схемы рис. 17.4 и рис. 17.5 содержат все типы логических элементов. При проектировании всегда стремятся номенклатуру элементов. В связи с этим созданы логические элементы, способные выполнить простейшую функцию двух аргументов "ИЛИ-НЕ", а также "И-НЕ". С помощью каждого из этих элементов можно выразить все основные операции булевой алгебры, а значит реализовать любую логическую функцию. Покажем это.

Для элемента "ИЛИ-НЕ"

операция "НЕ"

операция "ИЛИ"

операция "И"

Для элемента "И-НЕ"

операция "НЕ"

операция "ИЛИ"

операция "И"

В микросхемном исполнении элементы "ИЛИ-НЕ" обозначаются индексами ЛЕ, элементы "И-НЕ" – индексами ЛА. Например, микросхема К555 ЛЕ1 имеет в своем составе четыре элемента "ИЛИ-НЕ" на два входа каждый.

Булевы функции в СДНФ и в СКНФ обычно избыточны. Поэтому этапу построения схемы должно предшествовать упрощение формул или минимизация. Цель минимизации – получить минимально необходимое количество логических элементов в схеме. В основу минимизации положены правила и законы булевой алгебры. Чаще других применяется теорема склеивания:

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

Проведем группирование и возможные склеивания:

(17.6)

Вместо четырех слагаемых третьего ранга (17.4) получили три слагаемых второго ранга. Схема, соответствующая (17.6) приведена на рис. 17.6.

В инженерной практике для минимизации логических функций, как правило, применяют карты (матрицы) Карно. Карта Карно представляет прямоугольник, разбитый на квадраты. Число квадратов равно числу возможных комбинаций, т. е. . Каждый квадрат соответствует определенной комбинации аргументов (см. рис. 17.7а). Комбинации соседних квадратов должны отличаться не более чем одним аргументом. Для примера на рис.17.7а все возможные комбинации функции Внесены в квадраты карты Карно.

В целях минимизации карта Карно заполняется "1" и "0". Знак "1" записывается в тот квадрат, комбинация которого соответствует значению F = 1. В остальные квадраты записываются "0" (рис. 17.7б). После заполнения

квадраты с "1" объединяют в контуры. Объединить можно 2, 4, 8 квадратов и т. д. Это равносильно объединению слагаемых функции для склеивания. Каждый квадрат может входить в несколько соседних контуров. Возможно объединение крайних квадратов на противоположных сторонах карты.

Объединением двух квадратов исключается один аргумент, четырех квадратов – два аргумента и т. д. В минимизированном выражении функции остаются только те аргументы, значение которых одинаково во всех квадратах контура. Например, для рис. 17.7б результат минимизации будет иметь вид

и полностью совпадает с выражением (17.6).

Дата добавления: 2013-12-11