Сложность и строение минимальных схем для линейных булевых функций

• Автор: Комбаров, Юрий Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 129 с. : ил.

Содержание
Введение
Глава 1. Минимальные схемы в базисах, содержащих инверторы нулевого веса.
1. Определения н вспомогательные утверждения
2. Сложность линейных функции
3. Структура минимальных схем, реалнзуюпх пшенные функции.
Глава 2. Минимальные схемы в классическом базисе.
1. Определения и вспомогательные утверждения
2. Основная лемма
3. Доказательство теоремы
Глава 3. Минимальные схемы в базисе Шеффера.
1. Определения п вспомогательные утверждения
2. Основная лемма
3. Доказательства теорем
Глава 4. Минимальные схемы в базисе „импликация — отрицание“.
1. Определения п вспомогательные утверждения
2. Основная лемма
3. Доказательства теорем
Глава 5. Сложность линейных функций в неизбыточных базисах из двухвходовых элементов.
ВвСД( НПО
Введение
ІІлчеіше свойств схем ІП фміКШІОПсІ ІЬПЬІХ элементов ЯВЧЯРГСЯ OTIIOII II і павпых задач математической кибернетики Схемы in фмткцпоиатъпых элементов представтяісп собой математические модечп реа іьпьіх фнвлче-СКПХ ( тропе LB ПС ПО ТЬ 1еМЫХ ДІЯ ПЫЧПС ІРІПІ1І Наряде с б тевымп фор-м іамп КОП1ЛК1ПЫМП схемами конечными автоматами и 'машинами Тыо-])иига схемы из нкционатьных элементов являются примерами дпе-к])етиых справляющих систем
В книге [9] О Б 1 иапов опредетяех схеме из ф икциопа іьиьіх ; юмеп-іов пользеяев вспомоіадетьньїм понятием сені П])иведем соответсіїл-гоїипе опреде ІСІШЯ
Определение. Сіть — объект СОСІОЯЩШІ in ПОІКНОЬ П )Ul 1 Понос ССІЬ сеть Он ЯВТЯСЧСЯ єдине 1ВСТШОП вершиной ион семи
2 Естн S[ и S> — сені бет общих вершин то их обьодипенпе есіь
сеть Вершинами угон сети являются вершины пехотных Се 1 Oil
3 Ее III 6 — сеть и Ь — элемент ВЫХО I ко юрою не является вор шпион сели S торсмсльтат прпсоедшклшя всех входов элемента L к иекоюрьш вершинам сети 5 осів сеїв при полі к одной вершине сети могут присоединяться pa s пгчпые входы по каждвш вхо і присоединяете Я TO 1BKO к отпои вершине Вершинами повои сені являются вершины сети Б и выход і іемеша £
Определение. Сіємои т фупьционо іьнш і >т иекгпоь называемся сеть в ко юрой
1 каждомс по нос приписана одна из переменных щ с„ прп-чем ра )Пым по исхам — разные переменные По нос а называются іак-ЯЄ в і одами ( icмы
Ввод< нпо
2 каждому элементе Е с ? входами нос іаьюпа в соотвотс і вне некоторая бе лева фе пкцпя оьф (/,) сеществешю зависящая от / аріемец тов (при і = 0 функция Ol рсгь константа) и называемая с1)пкшіен э лемеша Е элемент Е ( сопостав іеппон ему ф нкцпеп oj_ на зывасмся фуиыхдтпа іьііьім j к ментом
3 некоторой вершине пршпкапо МПС ю 1 некоюроп вершине (бьпв може і соинадающеп с первон) припікало чисто 2 и гд некоюроп вершине приписано чис то т Вершины которым приписано хоія бы одно из чисел отмечены символом * Эл.п ве])шнпы называются выходами схемы
Каждоые входе п каж юеіе э гемеше схемы с іедмощнм обра зом сопос ыв-ляется реа їй немая ны санкция
1 каждеш входу схемы сопос іавляечся санкция равная перемешюп припне ашюп этоме входе
2 несгв всем вершинам к которым прпсое ишены вхолы оіемеїпа L
схемы яче с оносл авлены ф нкцпн Тен да выходе этою эюмепысо
IIOC ЫН ІЯЄ1С Я с})Є1ІКЦІІЯ Ol(j^ Z*'-1) где Оь — фепкция э лемеша Е а — фепкцня сопос тав іеішая тон вершине с которой соединен у-н вход элемента Е
Схема по сэнре к'лепшо реатніееі еноря кэчелше ю системе фепкшш (сэпе рагор)
(tl(n В.) /т(ч 1 Vu))
где //■—фепкция сопоставленная /-ме выходе
Ее ли (]эепкцин всех элементов схемві S принадлежал множестве' В ю бедем юворшь ню схема S есть с гс ма о вахте В (п ш иод В) Базис В па іьшасгся
а) иотым с'стн всякая бе лева фепкция допескает реализацию схемсш в базис е В
б) иси хбыточиым естн банк В — по шып но перестав быть по ніьіеі посте еда тения ні нею тюбоп с]энкцпп
Г IriUel

самом дечр ес ні бы иыход лтемеша Еі быт бы связан со входом леко-торого 'ломота E.t стичної о ся Е* lo подав па вход (її) необходимый конм aim (чакыо что па соотвек гв iouuni вход Е подаекя злбпваюшая Koiuiaina) мы могчп бы да инь чосыре -помета Еі Ei Е Е чао противоречит іеореме
Зтемепг Et, рСМТІІІЄЧ санкцию существенно МПІІСЯЩС 10 Ol дв\ пере меппых В противном с чуіае его можно бито бы удатпть птп мчешпь па инвертор чго противоречите» бід мшіпма ндюс і и схемы Бо іее uuo атемепт Ei pea тне ет Tiiueiiiivio фмікдпю. ведь ес ти бы on pea гш зОвывл т клмю-тпбо др і ю фмікцшо от діях церемонных мы мої ти бы выбран, такое шачеппе переменной ij что момент Е- рел шзовыилт бы копе ; нп-т. а значит выходное значение схемы не чашке то бы оі о (ведь выходы а іеменгов Еі її Ei < вя іапьі чотько со входами Е$)
Таким образом в схеме можно выдеппь < іапдаріпьш бток содержл-щпп моменты Е Ei. Е>, п входящпп в схеме правтыю с іедоваїо іьно схема couve каем операцию с ілпдлріпоіі редкцпн Темма 9 дока іапа