Контрольные вопросы

1. Что называется безынверсной(нормальной) формой логической функции?

2. Дайте определение дизъюнктивной нормальной формы логической функции.

3. Дайте определение конъюнктивной нормальной формы логической функции.

4. Укажите способы приведения логической функции к нормальной форме.

5. Что такое минитерм k-того ранга?

6. Что называется совершенной дизъюнктивной нормальной формой логической функции?

7. Что называется совершенной конъюнктивной нормальной формой логической функции?

8. Перечислите способы перехода от нормальных к совершенным нормальным формам БФ.

9. В чем смысл аналитического способа перехода к совершенной нормальной форме логической функции?

10. Что представляет собой графический способ перехода к совершенной нормальной форме логической функции?

11. Опишите принципы составления карт Карно.

12. Что представляет собой алгебра Жегалкина?

13. Перечислите пять типов логических функций.

14. Какая система функций называется функционально полной?

15. Дайте определение функциональной полноты.

16. Приведите теорему о функциональной полноте.

Задания для самостоятельной работы

1. Приведите заданную булеву функцию к нормальной(безынверсной) форме:

а) Y₁ = ;

б) Y₂ = ;

в) Y₃ = ;

г) Y₄ = ;

д) Y₅ = .

2. Преобразовать следующие логические функции в совершенную нормальную форму аналитическим способом:

а) Y = A   C   B  ;

б) Y =  B  A    C;

в) Y = A   B C       B   D;

г) Y = (A   ) (  C  D) (  B  );

д) Y = (A  ) (  C  ) (B  D);

е) Y =  (A  D) (   ).

3. Преобразовать логические функции, заданные в предыдущем пункте, к совершенной нормальной форме с использованием карт Карно.

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

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

Глава 14. Логические схемы

Бог сотворил мир на основе математических принципов.

И. Ньютон

Методы минимизации логических функций, основные элементы реализующие логические функции, карты Карно, метод Квайна, метод Блейка-Порецкого

ЦЕЛИ

Освоив эту главу, учащиеся должны знать и уметь:

• типы логических элементов, реализующих булевы функции;

• применять методы минимизации логических функций;

• строить логические схемы булевых функций.

14.1. Реализация булевых функций

Устройства, реализующие элементарные БФ, называются логическими элементами. Их входы соответствуют булевым переменным, а выходы – реализуемой функции.

На рис. 14.1 приведены логические элементы, реализующие элементарные БФ и примеры соответствия логических элементов и БФ.

Рис. 14.1. Соответствие логических элементов и булевых функций

По европейским и американским стандартам основные логические элементы обозначаются несколько иначе. Основные типы вентилей с точки зрения логических функций представлены в табл. 14.1.

Таблица 14.1

Название вентиля	Символ логической схемы	Логическая функция
И
ИЛИ
НЕТ
И-НЕ
ИЛИ-НЕ
ИСКЛЮЧАЮЩЕЕ ИЛИ
СОЕДИНИТЕЛЬ

В таблице наряду с названием логического элемента и логическим символом приведена его функция в виде логического выражения. Следует обратить внимание на то, что кружок означает логическое отрицание. Три типа логических схем — И, ИЛИ, НЕ, — представленные в табл. 14.1, соответствуют операциям булевой алгебры — конъюнкции, дизъюнкции и инверсии. С точки зрения возможности реализации произвольной логической функции эти три типа элементов образуют полный набор. Как следует из рис. 14.2, используя только элементы И и НЕ, можно получить элемент ИЛИ, поэтому сами по себе элементы И и НЕ составляют полный набор.

Рис. 14.2. Пример получения логического элемента ИЛИ

Подобно суперпозиции функций логические схемы образуются суперпозицией элементов посредством объединения их внешних узлов.

Задачи применения ЛС состоят в том, чтобы обеспечить экономичную реализацию БФ в некотором базисе.

Например, ЛС, реализующая функцию,

Y = (x₁ | x₂)(  x₁).

Переведем в базис (НЕ, И, ИЛИ) (рис.14.3):

y = (x₃  x₁) = .

а)

Рис. 14.3. Схема логической функции

Та же ЛС, но упрощенная (рис.14.4).

б)

Рис. 14.4. Логическая схема функции после минимизации

Всегда можно построить много различных ЛС, соответствующих данной ЛФ, они все эквивалентны. Из множества эквивалентных ЛС можно выделить экономичную.

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

Логические функции, заданные булевыми выражениями, которые содержат операции логического произведения, суммы и исключающей суммы, а также операцию логического отрицания, легко могут быть реализованы комбинациями логических элементов. Булевы выражения, как показано на рис. 14.5, могут быть подвергнуты разложению по «дереву вычислений» в соответствии со скобками и приоритетом операций.

Рис. 14.5. Пример синтеза логической схемы по булевой функции

Разложение по дереву вычислений начинается с последней вычисляемой операции булевого выражения. В примере, приведенном на рис. 14.5, последней в булевом выражении вычисляется операция исключающей суммы ( ), поэтому можно получить частичное разложение, показанное на рис. 14.5, б. Поскольку операция представляет собой двухместную операцию, на дереве вычислений имеются 2 операнда. Один из этих двух операндов –   – представляет собой переменную и дальнейшему разложению не подлежит. Другой операнд –   – представляет собой булево выражение и может быть разложен дальше. Последней вычисляемой операцией в выражении является операция логического отрицания, и разложение принимает вид, показанный на рис. 14.5, в. Дальнейшие аналогичные операции разложения приводят к виду, показанному на рис. 14.5, г. Когда операнд логического отрицания (–) представляет собой переменную и дополнение (отрицание) этой переменной может быть использовано в схеме, то в разложении нет необходимости.

Для того чтобы по дереву разложения, соответствующему булеву выражению, сформировать цепь логических элементов, на дереве следует произвести замену операции логического произведения на элемент И, логической суммы — на элемент ИЛИ, исключающей логической суммы — на элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и операции логического отрицания — на элемент НЕ. На рис. 14.6 показан результат такой подстановки, выполненной по дереву (рис. 14.5, г). Корень исходного дерева становится выходом, а его ветви — входами.

Рис. 14.6. Реализация логической схемы по булевой функции