Cтраница 2
Несколько особое место в работах по синтезу 1, Л - полюсников занимают методы синтеза частного класса бесповторных структур. Однако эти работы имеют скорее теоретическое, чем практическое, значение, поскольку неизвестен удобный критерий распознавания бесповторных функций по их первоначальному заданию. [16]
В работе [4] была получена конечная полная система тождеств для бесповторных формул. Ее использование позволяет упростить доказательство основной леммы, однако промежуточные леммы представляют самостоятельную ценность для решения задач тестирования бесповторных функций. [17]
В дальнейшем при вьтчисленгш h ( х) применяем всюду последовательное выполнение операций без раскрытия скобок и тем сокращаем количество операций. Для распространения указанных форм перехода к замещению на весь класс булевых функций достаточно представить всякую / ( х) суммой ортогональных бесповторных функций. [18]
Статья построена следующим образом. В первой части рассматривается специальный тип деревьев - канонические деревья - и доказывается взаимно однозначное соответствие между этими деревьями и бесповторными функциями. После этого вводятся понятия помеченно-раскрашенного дерева и связно-несвязного графа и строится взаимно однозначное отображение на множествах этих объектов. Затем показывается, что отдельные части канонического дерева представляют собой помеченно-раскрашенные деревья, а ребра соответствующих им связно-несвязных графов определяются так называемыми квадратами существенности бесповторной функции. [19]
Необходимые определения вводимых автором понятий даются ниже по мере их использования. Стандартные понятия, используемые в настоящей работе, перечислены в приложении. В конце работы приведен также пример канонического дерева и множества квадратов существенности для одной бесповторной функции. [20]
Статья построена следующим образом. В первой части рассматривается специальный тип деревьев - канонические деревья - и доказывается взаимно однозначное соответствие между этими деревьями и бесповторными функциями. После этого вводятся понятия помеченно-раскрашенного дерева и связно-несвязного графа и строится взаимно однозначное отображение на множествах этих объектов. Затем показывается, что отдельные части канонического дерева представляют собой помеченно-раскрашенные деревья, а ребра соответствующих им связно-несвязных графов определяются так называемыми квадратами существенности бесповторной функции. [21]