Для элемента "или-не"

Для элемента "и-не"

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

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

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

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

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

(29.6)

Вместо четырех слагаемых третьего ранга в (29.4) получили три слагаемых второго ранга в выражении (29.6). Схема, соответствующая (29.6) приведена на рис. 29.3,б. Количество логических элементов уменьшилось в два раза. В этом и заключается суть минимизации.

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

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

Для примера на рис.29.4, а все возможные комбинации переменных из таблицы 29.1 внесены в квадраты карты Карно. При таком заполнении карта оказывается загроможденной и не наглядной.

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

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

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

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

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАЧИ

29.1. Поясните значение терминов: цифровой сигнал, состояние, алфавит, кодовая комбинация, разряд, длина кодовой комбинации.

29.2. Приведите формулу представления произвольного числа десятичной системы счисления двоичным кодом.

29.3. Представьте число 753

а) в двоичном коде,

б) в двоично–десятичном коде.

Какой из вариантов более удобен?

29.4. Приведите схемные обозначения и правила выполнения логических операций для логических элементов ИЛИ, И, ИЛИ – НЕ, И – НЕ.

29.5. Приведите определение булевой функции и перечислите возможные формы ее представления. В каких целях применяется каждая из форм представления?

29.6. В чем заключается суть минимизации булевых функций?

29.7. С помощью теорем алгебры логики упростите логическое выражение:

. Постройте схему, реализующую упрощенную функцию.

29.8. Методом карт Карно минимизируйте функцию:

Постройте схему.

29.9. Минимизируйте функцию: Постройте схему.