О расшифровке логических функций

• Автор: Осокин, Виктор Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 117 с. : ил.

Посвящается

моим родителям Осокину Владимиру Викторовичу Осокиной Алле Васильевне

моим школьным учителям математики Звавичу Леониду Исааковичу Шляпочнику Леониду Яковлевичу

Слова благодарности

Данная диссертация не могла бы появиться на свет без помощи и поддержки множества людей. Я рад воспользоваться возможностью поблагодарить всех тех, кто направлял и поддерживал меня все годы моего обучения в аспирантуре механико-математического факультета МГУ.
Прежде всего, я благодарю коллектив кафедры Математической теории интеллектуальных систем, возглавляемой д.ф.-м.н., профессором, академиком Кудрявцевым Валерием Борисовичем, за постоянный интерес и обсуждение моих научных результатов и атмосферу, способствующую исследовательской работе.
Своим научным и профессиональным ростом я в первую очередь обязан моему научному руководителю д.ф.-м.н., профессору Гасанову Эльяру Эльдаровичу. С одной стороны, он давал мне возможность погружаться с головой в новые интересные направления и задачи, никак не ограничивая область интересов. С другой, — всегда направлял и корректировал меня, когда я начинал тонуть во всем многообразии областей теории интеллектуальных систем, расшифровки функций и информационного поиска.
Именно Эльяр Эльдарович познакомил меня с теорией сложности, научил комплексно подходить к математическим проблемам, показал, какую роль в решении задач играет их корректная постановка, привил интерес к работе со студентами. Я благодарен проф. Гасанову за поддержку моего стремления заниматься прикладными задачами. Он способствовал моему участию в организации и проведении специальных семинаров на факультете.
На мое научное мировоззрение и взгляды сильнейшее влияние оказал д.ф.-м.н., профессор, академик Кудрявцев Валерий Борисович. Несмотря на свою занятость он всегда находил время на личные и, что особенно приятно, неформальные беседы, которые кардинально изменили мое понимание теории автоматов и интеллектуальных систем в целом. Валерий Борисович всегда призывал интересоваться не только научными результатами, но и людьми, стоящими за этими результатами. Он привил мне уважение

к точности формулировок и строгости доказательств, в частности, путем неоднократных правок текстов моих статей и предоставления ценных комментариев и оценок моих выступлений на кафедральном семинаре под его руководством.
На мое желание заниматься расшифровкой функций существенное влияние оказали работы д.ф.-м.н., профессора Подколзина Александра Сергеевича по созданию компьютерного решателя задач. Мне вдвойне приятно выразить ему свою благодарность, поскольку он никогда не оставался равнодушным на моих докладах и всегда умел повернуть все так, чтобы я под новым углом посмотрел на решаемую задачу.
Мой научный кругозор и знания по тематике расшифровки функций стали шире благодаря общению с д.ф.-м.н. Воронцовым Константином Вячеславовичем по вопросам теории вычислительного обучения. Мне близки манера и принципы его работы со студентами.
В области кодирования и защиты информации, напрямую связанной с расшифровкой функций, большое влияние на меня оказали сотрудники нашей кафедры математической теории интеллектуальных систем к.ф,-м.н., вед.н.с. Носов Валентин Александрович, к.ф.-м.н. Галатенко Алексей и к.ф.-м.н. Пантелеев Павел. Спасибо им за постоянную готовность отвечать на мои вопросы и вникать в суть моих научных проблем.
Я благодарен аспирантам нашей кафедры Пивоварову Александру и Шуткину Юрию. Они всегда следили за моими научными результатами, читали и редактировали мои статьи, высказывали ценные предложения на моих докладах. Наконец, просто спорили со мной о том, как должен выглядеть и звучать тот или иной результат. А главное, всегда были рядом и готовы поддержать. В научной сфере я всегда также чувствовал поддержку Моисеева Станислава и Жука Дмитрия. Спасибо им за живые обсуждения и постоянный интерес к моей работе. Отдельная признательность Титовой Елене и Муравьевой Анне: они помогали мне по множеству организационных и административных вопросов.
Среди друзей, которых мне подарил МехМат, особое место занимают Захаров Сергей, Столяр Вероника, Колосов Дмитрий, Зинченко Валентин,

Предположим теперь, что таких і не нашлось. Другими словами, пусть /(-В?) ф /{В}) для всех г. Б.о.о. считаем, что /(Нгс) = с для всех г. Если это не так, поменяем г-ю компоненту каждого слова на противоположную.
Пусть теперь Ь{ — П^=1В} для всех г, Ьо = V. Заметим, что множество Ьг содержит в точности одну переменную. Будем последовательно запрашивать значения / на наборах 6*. Так как функция / монотонная, ДЬі) > І(рі+1). Вспомним, что /(Ь0) = 1.
Если /(Ьг) — 1> то, поскольку /(0) = 0, имеем что переменная в Ьг — существенная. Далее считам, что /(6Г) Д 1, т.е. существует і, такое что /(&г) — 1) №>і+і) — 0. В примере ниже 1 = 2.
В}: 0 0 0 0 1 1 1 1 1
В: 1 1 0 0 1 1 0 о 1
в-- 0 1 0 1 0 1 0 1 1
В$: 1 0 1 0 1 0 1 0 1
Ьг : 0 0 0 0 1 1 1 1 1
^2 • 0 0 0 0 1 1 0 0 1
ъ.з: 0 0 0 0 0 1 0 0 I
&2Ьз : 0 0 0 0 1 0 0 0 1
Сразу видим, что множество ЬДЬі+і содержит существенную переменную. Поскольку /(И?+1) = 0, ЬДЬг+1 С Д?+1 и / является монотонной, имеем /(ЬДЬі+і) = 0. Отсюда Ьг+1 тол<е содержит существенную переменную (т.к. 6і+і — Ьі(ЬіЬі+і)). Мы снова получили два непересекающихся множества переменных, каждое из которых содержит существенную переменную.
Суммируя сказанное выше, получаем что в результате наших действий мы либо нашли существенную переменную, либо нашли два непересека-ющиеся множества, каждое из которых содержит существенную переменную. Во втором случае у нас имеется фиксация, позволяющая повторить предложенные шаги для проекции исходной функции, т.е. для функции от меньшего числа переменных.
Применяя описанный процесс рекурсивно, получаем бинарное дерево, каждый лист которого содержит найденную существенную переменную.