3-6. СИНТЕЗ СХЕМ ДЛЯ НЕКОТОРЫХ КЛАССОВ СОБСТВЕННЫХ ФУНКЦИЙ

При синтезе схем, работа которых описывается симметричными функциями или функциями, принадлежащими к некоторым другим классам, рассмотренным в § 1-6, можно указать частные методы и приемы синтеза, дающие лучший результат, чем синтез с помощью общих приемов, описанных в предыдущих параграфах этой главы.

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

переименовации аргументов этой функции. Из этого сразу же вытекает основное свойство всякой симметричной функции.

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

Основные результаты по синтезу функциональных схем для симметричных функций были получены Эпштейном и Г. Н. Поваровым. Следуя Эпштейну, введем понятие фундаментальных симметричных функций.

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

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

Пример 3-22. Написать ДСНФ для функции Исходя из определения 3-5, получаем:

Теорема 3-2. Любая симметричная функция есть дизъюнкция фундаментальных симметричных функций, индекс которых определяется однозначно заданной симметричной функцией.

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

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

Пример 3-23. Записать в ДСНФ функцию

Рассмотрим теперь следующие симметричные функции аргументов:

Эти функции будем называть простыми симметричными функциями. Имеет место следующая теорема.

Теорема 3-3. Для любой имеет место равенство

Справедливость (3-6) вытекает из следующих соображений:

Тогда

Применяя формулы де Моргана, получаем:

Теперь ясно, что при конъюнкции выражеяий, стоящих в скобках, все члены, в которые одновременно входят исчезнут. Оставшиеся после гаеремножения конъюнкции будут содержать ровно по букв без отрицания. Теорема доказана.

Из справедливости доказанной теоремы вытекает следующее интересное для задачи синтеза утверждение.

Следствие. Любая может быть реализована при использовании только одного элемента отрицания.

Пример 3-24.

Заметим, что Применяя теорему 3-3, получаем:

Введем понятие фундаментального симметричного многополюсника.

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

Имеет место следующая теорема (В. М. Глушков).

Теорема 3-4. Фундаментальный симметричный многополюсник для переменных может быть реализован при использовании элементов ИЛИ и элементов И.

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

теперь, что утверждение теоремы верно для некоторого

Здесь — числа, необходимые для реализации фундаментального многополюсника элементов типов И и ИЛИ.

Покажем, что теорема остается справедливой и для Имеют место следующие очевидные соотношения:

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

Теорема доказана.

Теоремы 3-2 - 3-4 дают возможность производить синтез схем для симметричных функций более простым способом, чем с помощью описанных выше универсальных методов синтеза. Следует подчеркнуть, что синтез схем на основании теорем 3-2 - 3-4 часто не будет оптимальным.

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

Теорема 3-5. Сокращенная ДНФ для монотонной функции, отличной от константы, совпадает с МДНФ для этой функции.

Эта теорема показывает, что при синтезе схем с монотонными собственными функциями нет необходимости проводить полную минимизацию аналитической записи этих функций. Для получения МДНФ в этом случае достаточно получить СДНФ, используя для этого, например, метод Блека — Порецкого, описанного в § 2-5.