Вопросы для самоконтроля

1. Каково максимальное число ПФ, зависящих от n переменных?

2. Какие способы задания ПФ вам известны?

3. Какие элементарные логические функции вам известны и для чего они используются?

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

5. Какие канонические формы аналитического представления ПФ вам известны и как они формируются?

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

7. Что понимают под рисками сбоя и каковы причины их появления?

4. Минимизация переключательных функций

Рассмотрим СДНФ некоторой функции и выполним ряд элементарных преобразований, воспользовавшись соотношениями, приведенными в разделе 3.3.

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

Для технической реализации функции по исходной СДНФ в каноническом базисе И-ИЛИ-НЕ необходимо использовать шесть трехвходовых элементов «И», реализующих конъюнкции переменных, три элемента «НЕ», реализующих инверсии переменных, и один шестивходовый элемент «ИЛИ», реализующий дизъюнкцию всех заданных конъюнкций входных переменных. Для реализации той же ПФ по аналитической записи, полученной после выполнения преобразований, потребуются два двухвходовых элемента «И», три инвертора и один трехвходовый элемент «ИЛИ».

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

Для рассмотренной ПФ цена схемы, синтезируемой по СДНФ, составляет (без учета инверторов): С₁ = 6+(6∙3)+1+6 = 31. Цена схемы, синтезируемой по упрощенной форме представления ПФ, составляет (также без учета инверторов): С₂ = 2+(2∙2)+1+3 = 10.

Задача минимизации ПФ заключается в отыскании минимальных форм представления функций, поскольку им соответствуют наиболее простые технические реализации (с наименьшей ценой схемы). Иными словами, при решении задачи минимизации ПФ требуется найти аналитическое выражение заданной ПФ или системы ПФ, содержащее наименьшее число переменных и логических функций. Решение этой задачи в общем случае затруднено. Наиболее подробно исследовано решение задачи минимизации для канонического базиса И-ИЛИ-НЕ. Также известны подходы к решению этой задачи для ПФ, заданных в базисах И-НЕ, ИЛИ-НЕ.

Введем ряд определений.

Элементарной конъюнкцией называется конъюнкция конечного числа различных переменных, входящих в нее в прямом или инверсном значении.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

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

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

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

Проиллюстрируем последние два определения примером. В табл. 4.1 заданы функция f и ее импликанты g₁, g₂, …, g₇.

Таблица 4.1

x1	x2	x3	f	g1	g2	g3	g4	g5	g6	g7
0	0	0	0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1	1
0	1	0	1	0	1	1	0	0	1	1
0	1	1	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0
1	0	1	1	1	0	1	0	1	0	1
1	1	0	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0

Из приведенных определений следует, что импликанты g₂ и g₅ являются простыми, а, например, импликанта g₄ не является простой, так как ее часть также является импликантой функции f.

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

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

Для ПФ из рассмотренного выше примера сокращенная ДНФ запишется следующим образом:

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

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

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

Процесс отыскания минимальных ДНФ состоит из двух этапов: нахождения простых импликант и исключения лишних импликант.