Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf

128] выполнил такое построение лишь для k = 3. Поэтому теорема Кузнецова не является практическим руководством при определении полноты систем многозначных функций.

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

1281.

Теорема. Для того чтобы система функций из множества Р к, {к > 3), содержащая все функции одного переменного, не прини­ мающие хотя бы одно значение из множества Е к, была полна, необхо-

димо и достаточно, чтобы она содержала функцию f (х) £ Рк, которая существенно зависит более чем от одного аргумента и принимает к значений. В некоторых случаях удобнее пользоваться теоремой, яв­ ляющейся следствием предыдущей (теорема Слупецкого).

Теорема. Система, которая содержит все функции одного перемен­

ного из множества Р к и функцию / (х) £ Рк, существенно завися­ щую более от одного переменного и принимающую к значений, полна.

С ростом к число kk функций одного переменного быстро увеличи­ вается, что затрудняет практическое использование приведенных тео­ рем. Поэтому целесообразнее строить такие системы функций одного переменного, на основе каждой из которых можно формировать все функции одного переменного. Например, все функции из множества Р к при п — 1 можно сформировать на основе функций [281

функций тесно связаны с понятием предполного класса. Класс функ­ ций N, принадлежащий замкнутому классу М из множества Рк, на­ зывается предполным в классе М, если класс N представляет непол­ ную в классе М систему. Однако присоединение к этой системе любой

функции f £ М и f £ N обращает N в полную систему в классе М. Каждый замкнутый во множестве Рк класс М, М Ф Рк можно рас­ ширить до предполного во множестве Рк класса, причем число таких предполных классов конечно. Необходимое и достаточное условие пол­ ноты системы функций из множества Рк можно сформулировать в сле­ дующем виде [28].

38

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

Представляет интерес проблема функциональной полноты систем, состоящих только из одной функции. По аналогии с двузначными функциями такие функции называют функциями Шеффера. Но в отли­ чие от случая k = 2, когда существует всего две функции Шеффера, число многозначных функций Шеффера очень быстро растет по мере увеличения k. Например, при k = 3 насчитывается 3774 таких функ­ ций [17]. В связи с этим важно определить те свойства функций, ко­ торыми они должны обладать, чтобы быть функциями Шеффера. Можно показать, что многозначная функция будет функцией Шеффера тогда и только тогда, когда на базе этой функции можно сформиро­ вать все функции одного переменного.

Важное значение для теории многозначных функций и ее практи­ ческих приложений имеет проблема оценки числа полных систем во множестве Р к. Число различных базисов во множестве Рк бесконечно. Базис называется простым, если при любом отождествлении аргумен­ тов функций, образующих этот базис, получающаяся система функций не является базисом. Число простых базисов при k >■ 3 не превосхо­

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

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

Функционирование комбинационных схем с многозначным струк­ турным алфавитом можно описать некоторой системой многозначных

где i — 1,2, ..., т\ т и п — соответственно число выходных и входных полюсов комбинационной схемы; xt £ Ек.

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

39

возникает проблема представления функций ft посредством суперпо­ зиций базисных операций, реализуемых полным набором логических элементов. Решение этой проблемы упрощается, если каноническая фор­ ма представления произвольной многозначной функции имеет вид суперпозиции базисных операций.

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

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

§2.2. Система Россера — Тьюкетта

Вработах, относящихся к синтезу многозначных схем, очень часто встречаются ссылки именно на систему Россера — Тьюкетта [28], что связано с относительной простотой представления про­ извольной fe-значной функции в этой системе. Система Россера—Тью­

*1 V*2

Приведем некоторые тождественные соотношения, характерные для рассматриваемой системы

40

Таблица 6 Таблица 7 Таблица 8

J 0 (x) A M J-i W

где х — двоичная операция инверсии.

В булевой алгебре есть несколько методов синтеза переключатель­ ных функций, основанных на известной формуле разложения, позволя­ ющей сделать переход от функции п переменных к функции п — 1 переменных

которая при к — 2 сводится к предыдущей.

41