Сложность и алгоритмы нахождения представлений многовыходных функций алгебры логики в классах полиномов и обратимых схем тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Францева Анастасия Сергеевна

• Францева Анастасия Сергеевна
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Францева Анастасия Сергеевна

ЕН

§ 2. Функция Шеннона сложности представлений функций алгебры логики в классах расширенных двупорожденных операторных форм ЕН

§ 3. Функция Шеннона сложности представлений функций алгебры логики в классе расширенных двупорожденных операторных форм ЕН

Глава 2. Сложность обратимых реализаций функций алгебры логики в классе обратимых схем RS

§ 4. Способы задания многовыходных обратимых функций. Понятие

обратимой схемы

§ 5. Представление функций алгебры логики многовыходными обратимыми функциями. Метод построения обратимых схем класса

RS

§ 6. Функция Шеннона сложности обратимых реализаций ^^Е-полиномов функций алгебры логики в классе обратимых схем RS

Глава 3. Алгоритмы нахождения сложности представлений многовыходных функций алгебры логики в классах полиномов и обратимых схем

§ 7. Алгоритм нахождения сложности представлений функции алгебры логики в классах расширенных двупорожденных операторных

форм

§ 8. Алгоритм нахождения сложности обратимых реализаций ZhE-

полиномов функций алгебры логики в классе обратимых схем RS 74 § 9. Алгоритмы нахождения сложности представлений многовыходных

обратимых функций в классе обратимых схем R

Заключение Список литературы

Введение диссертации (часть автореферата) на тему «Сложность и алгоритмы нахождения представлений многовыходных функций алгебры логики в классах полиномов и обратимых схем»

Введение

Актуальность темы исследования и степень ее разработанности.

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

Впервые исследования представлений функций алгебры логики полиномиальными нормальными формами были опубликованы в работах И.И. Жегал-кина в 30-х годах прошлого столетия [8]; описанные представления получили название полиномов Жегалкина.

В дальнейшем, в 1954 году был введен новый класс полиномиальных форм, расширяющий класс полиномов Жегалкина - класс поляризованных полиномов Жегалкина или форм Рида-Маллера. Данный класс полиномов связан с теорией кодирования и с соответствующими задачами построения кодов Рида-Маллера [49], [51].

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

Интерес к задачам обратимых вычислений возник благодаря работе, в которой связывается логическая необратимость вычислений, производимых компьютером, с таким физическим явлением, как выделение теплоты [46]. Затем в 1973 году Ч. Беннет доказал необратимость универсальной ЭВМ (машины Тьюринга), построил обратимую машину Тьюринга [33]. В последние десятилетия активно исследуются как способы синтеза обратимых схем, реализующих обратимые функции, так и способы обратимой реализации функций алгебры логики.

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

Обозначим через а двоичный набор (а1,..., ап) длины п, где а € {0,1} - компоненты двоичного набора, г € {1,...,п}. Нулевой и единичный наборы обозначаются: 0, 1. В дальнейшем при необходимости набор а будет ассоции-

роваться с целым положительным числом X = 2n-1a1 + ... + 20an, а множество наборов {0,1}n = {a0,..., ¿r2n-i} будет упорядочено согласно ассоциируемыми с ними числами.

Многовыходной (n, к)-фупкцией f будем называть отображение из множества наборов {0,1}n в множество {0,1}k.

( n, 1) f

классическом понимании. В диссертации в зависимости от контекста будут ис-

( n, 1)

чим через Bn.

В диссертации удобно задавать (n, 1)-функцию f G Bn двоичным набором (ао,..., ai) длины 2n, называемым вектором значений, где о^ = f (а) по всем наборам а G {0,1}n.

( n, 1) f

символами: x, y, возможно, с индексами. Если наборы переменных обозначить следующим образом: X = (x1,...,xn) Xj = (xi,...,xj), то в тексте возможна сокращенная запись: f (x1,..., xn) = f (x), F(x0, x1,..., xn) = F(хП).

xa означает x, если а = 1 и x, если а = 0. Символами 0 и ^ обозначается сложение по модулю 2, символ конъюнкции в виде «•» может быть опущен.

При исследовании вопросов синтеза, нахождения коэффициентов разложения и сложности представлений функций алгебры логики в классах полиномиальных нормальных форм свою эффективность доказал операторный подход, введенный в 90-е годы Винокуровым С.Ф. совместно с Перязевым H.A. [4].

В 1993 году класс операторов кратной и частной производной, подстановки и расстановки отрицаний над переменными позволил получить эффективные описания канонических форм функций алгебры логики в некоторых классах полиномиальных нормальных форм [3]. Обзор классов операторных форм функций алгебры логики рассматриваются в [15].

Для описания результатов диссертационных исследований потребуются определения основных понятий и свойства дифференциального исчисления функций алгебры логики [16] и операторного подхода [12].

Производной функции алгебры логики f (x1,..., xn) то перемен ной Xi называется функция:

fX i (x1 , ..., Xn) f (x1,...,xi- 1 , ^ Xi+1 , ..., Xn) 0 f (x1 , ..., Xi-1 , 1 , Xi + 1 , ..., Xn) .

/ж 1,...,ж8 (х1,...,хп) = (/ж 1,...,х8_1 (х1,..., хп))Жя.

Из определения производной следует, что

/х 1,...,жя (ж1, ..., хп) = /г^ ,...,жг„ (ж1, ..., хп),

^гй

где (¿1,..., г5) - произвольная перестановка (1,..., й).

,

всех булевых функций Вп в Вп :

Оператор представляется в виде последовательности Ь = £ь..£п, компоненты которой принадлежат множеству специальных символов е,^,р; п - длина оператора.

Компонента оператора Ъ действует на функцию / (ж) по перемен ной жг следующим образом:

/

/(ж), если = е, (ж) = \ /(Ж1, ..., Хг, ..., Жп), если ¿г = р, (ж), если = <1

Действие оператора Ъ = на функцию /(Ж) то переменным ж1, ...,жп

определяется так:

¿(/(ж)) = *1(*2...*п/(ж)).

Для описания результатов второй главы будет использоваться следующая операторная запись производной:

^жь...,,жП/(ж1, ..., жп),

которая обозначает производную функции /(ж1,..., жп) то тем переменным жг, для которых соответствующее т = 0.

Набор Т = {ъ0, ...,Ът, ..^"Ь1} из 2п операторов, где каждый оператор имеет п

{ъ °д (Х),...,ъ ?д(Х),...,ь ?д(Х)}

образуют базис пространства Вп, как линейного векторного пространства; функция д(Х) называется базисной.

Без специальной оговорки в тексте диссертации в качестве функции д(Х) будет использоваться функция произведениях! •... • хп. В [12] показано, что она является базисной.

Операторный пучок А = (а°,... , ат,..., а1) называется двупорожденным, если существуют такие операторы Ь = Ь!... 6П и с = с!... сп, 6 = с для любого г, что оператор а1 = а!... ап пучка А определяется следующим образом:

если Т = 0, Сг, если т = 1.

Любой дву порожден н ы 11 операторный пучок является базисным [12]. Пусть А = (а°, ...,ат, ...,а!) - двупорожденный операторный пучок. Тогда функция алгебры логики / имеет следующую операторную форму по пучку А:

о^(/)= Е а?а?д(Х), (1)

1е{°,!}"

где а? Е {0,1}.

Для удобства записи в дальнейшем изложении будем обозначать через ^? сумму следующего вида ^ 1е{° !}п, через и? объединение и?е{°д}п, по всем наборам т.

,

цнп /(Х) верно следующее равенство:

с/(Х) = а/ (Х) 0Ъ/(Х).

Далее удобно записывать так: с = а 0 Ь.

В [12] доказано, что для любого двупорожденного операторного пучкаТ? = (Ч°,т, ...,"Ъ1,Т) существует оператор

а? =

Е

В форме (1) для всех а = 1 вместо оператора ат подставим сумму операторов соответствующего пучка "IV, проведем операцию сокращения пар одинаковых слагаемых (операцию Я) и получим для функции /(ж) следующее представление:

В [2] доказано, что данное представление единственно с точностью до порядка слагаемых; будем называть его специальной операторной формой и обозначать через (/). Пусть М(50Е(/)) - множество слагаемых в (/).

В диссертационных исследованиях используются классы Иъ двупорожден-ных операторных пучков, где Ь - оператор длины п. Классы И состоят из пучков вида А = (а0,..., ат,..., ав которых а0 = Ь. Через И обозначается класс всех двупорожденных операторных пучков. ИИ

ных нормальных форм. Классы операторных форм редуцируются в классы полиномиальных нормальных форм, если в качестве базисной функции д(ж) рассматривать функцию произведения ж1 • ... • жп. Таким образом класс всех операторных форм ОР редуцируется в класс полиномиальных нормальных

И

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

В [12] рассматривались схожие с классом И^..^ два класса Ие...е и Ир...р, один из которых содержит базис совершенной полиномиальной нормальной формы. В [20] вводятся 3п классов вида Иъ. Эти классы имеют строение подобное классу и аналогичные свойства, которые привели к тому, что сложности пред-

И

В рамках диссертационных исследований рассматриваются расширения классов И и И: классы ЕИЪ и ЕИ. Эти классы состоят из расширений ЕА двупорожденных операторных пучков А. Классы ЕА и ЕИ вводились в [12]. ЕИ

Жегалкина ^^Е, ранее не исследовался. Этот класс используется в диссерта-

Рисунок 1 Фрагмент диаграммы классов операторных форм

Сложность представлений функций алгебры логики в классах операторных форм характеризуется функцией Шеннона [25].

Сложностью /(/) операторной формы О Г(/) вида (1) функции / называется число

/(/)= £ а,.

т€{0,1}"

Пусть К - класс базисных операторных пучков. Тогда сложность функции / в классе К равна:

Ьк (;)=¿т1?)(/(/))

по всем операторным формам ОГ(/) функции /, построенным по пучкам клас-К

Функция Шеннона сложности представления всех функций алгебры логи-

Известны следующие значения функции Шеннона в перечисленных выше классах операторных форм:

¿я,., = [ 2 21 [17];

¿я(п) = ¿я^.^(п) [1]; = 12п [12

А 2'

L№ , = 12n [74

d...d 2' 32n < Leh(n) < 22n [12];

Lop (n) < 2n 2(1°ё2Пп)+1) [14].

В 2004 году Рябец Л. В. и Винокуров С.Ф. разработали способ вычисления сложности представления специальной операторной формы функций алгебры логики в классе двупорожденных операторных пучков Иъ и алгоритм нахождения минимального представления функций алгебры логики в классе И [6], [20], [21]. Предлагаемый способ был продолжен для разработки алгоритмов нахождения сложности представлений функций алгебры логики в классах ЕИЪ, ЕИ и в классе обратимых схем RS.

В [13] исследовалась задача минимизации представлений функций алгебры логики в классе полиномиальных нормальных форм. Был разработан алгоритм нахождения минимальных полиномиальных форм функций и получена библиотека представителей классов LP- эквивалентности для функций 5 переменных [18], [19]. Данные результаты также использовалась при получении представлений в классах ZhE, ЕИЪ, ЕИ самых сложных функций.

В терминологии многовыходной (n, к)-функции следует отметить (n, 2)-функции, которым соответствуют функции четырехзначной логики. Интерес к таким функциям связан с их применением в области разработки интеллектуальных систем поддержки принятия решений [5], [7], [30], [44], [60].

( n, n)

функцию F(x1, ...,xn) = (f1(x1,..., xn),..., fn(x1,..., xn)), что отображение

является однозначным.

Множество всех обратимых функций обозначим через В^. Для двух обратимых функций Г(х) = (/1(ж),..., /п(х)) и С(х) = (д1(х),..., дп(х)) функция

Н (X) = С(Г (X)) = (д1(/1,...,/п),...,дп(/1,...,/п))

называется суперпозицией функций Г и С.

В работе [37] сформулированы основополагающие принципы обратимой или консервативной (в терминологии авторов) логики. Данные принципы демонстрируют отличия между обратимым и необратимым вычислением:

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

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

- допускаются функции константы, которые применяются к определенным блокам (частям) вычислений.

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

Т0 (хЪ) • (х15 ."5 хЪ 5 ."5 хп) ^ (х15 ...; х« 5 ...; хп) 5

для любого г Е {15 ...5 п} 5

Т^Ь { гр . гр . Т* • 1 * ( 'У* 1 'У* ■ Т* I _V 'У* • ГТ^ Т* ■ • 'У* ■ 'У* 1

к V ' • • • 5 «к > 3 / V 1 ' " ' ' 3 ' " ' ' п/ V 1 1 "' 1 3 ^ «1 Ък! "'1 '^п) 1

где к < п5 {г15 ...5 гк} С {15 ...5 п}5 для любого ^ Е {15 ...5 п}5 ] Е {г15 ...5 гк}.

Пусть задано некоторое подмножество В множества Тогда замыканием [В] называется такое множество всех обратимых функций, которые представиВ.

В [58] доказано, что [Т] = В^.

Т

ли.

В работах [32], [36] связывается модель обратимых вычислений с моделью квантовых с использованием функций Тоффоли. Данная связь осуществляется через матричное описание конечномерных линейно-нормированных пространств состояний квантовой системы; в работах [22], [23], [24] описаны на языке матриц известные квантовые алгоритмы Дойча-Йоджа, Саймона и Гровера [34], [41], [56].

Обратимая функция может иметь различные представления. К ним относятся: таблица значений, подстановка, матричное представление и обратимая логическая схема. Впервые понятие обратимой схемы вводится в [59]. Обратимая схема представляет собой логическую сеть, состоящую из п входов и п выходов. Разные значения на входах в схеме дают разные значения на выходах. По значениям на выходах однозначно можно восстановить значения на входах. Элементам (вентилям) схемы соответствуют функции Тоффоли множества Т. Над обратимыми схемами возможна только одна операция - операция склейки схем, в результате применения которой выходы одной схемы становятся соответствующими входами другой. Склейке схем соответствует операция суперпозиции обратимых функций, реализуемых склеиваемыми схемами.

Т

Отметим работу [32], в которой предлагается метод построения обратимой схе-

Т

соответствующие функциям вида Т0, Т2, Тп_ 1.

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

Пусть сложность ¿(б1) обратимой схемы S равна числу элементов схемы. Обозначим через Я некоторый класс обратимых схем, реализующих обратимые функции Е (ж). Тогда сложи ость ¿д (Е) обратимой фун кции Е в классе Я определяется:

¿д(Е ) = ш1п(£(£)),

по всем схемам $ из Я реализующим функцию Е.

Функция Шеннона ¿д(п) для класса всех обратимых функций определяется так:

¿д(п) = шах(Ьд(Е)).

Я1

^ (Вп/2) >

П'

где В^/2 С Вп - подмножество обратимых функций, представленных четными перестановками.

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

1. Конструирование таблиц значений обратимых функций [47], [48], [50], [64]. Использование определенным образом сконструированных таблиц значений обратимых функций присутствует в работе [47]. Авторы [62], одни из первых, предлагают алгоритм синтеза обратимых схем, реализующих четные подстановки соответствующих обратимых функций. В алгоритме подстановка сначала преобразуется в произведение 3-циклов, затем каждый 3-цикл преобразуется в 3-цикл, состоящий из элементов, в бинарной записи которых отличаются только 2 бита. Каждый такой 3-цикл реализуется с помощью элементов Тоффо-ли Тп-2 и Т0. Аналогичный подход используется в [9], здесь предложен новый быстрый алгоритм синтеза, в котором цикл четной подстановки раскладывается в произведение транспозиций, затем каждая транспозиция приводится к определенному виду через изменение значений битов чисел, составляющих транспозицию. [10] является продолжением работы [9], здесь представлены оценки сложности обратимых схем, реализованные с дополнительными входами и без. В [52] предложена идея хранения в библиотеке схем различных циклов и использование алгоритма декомпозиции тех циклов, которых нет в библиотеке.

2. Использование диаграмм решений (ВББ) [61]. Этот метод позволяет получить обратимые схемы для функций большой размерности; сокращение сложности схем осуществляется за счет использования дополнительных входов.

3. Использование элементов (вентилей) обратимой логической схемы. Здесь ведется конструирование минимальных обратимых логических схем, содержащих различного вида элементы — элементы, имеющие непосредственную техническую реализацию [53], использующиеся в различных прикладных областях [42] или построенные с помощью элементов Тоффоли [31].

Анализ упомянутых выше работ позволил сделать следующие общие выводы. В основном работы в этой области связаны с разработкой конкретных

алгоритмов минимизации различных представлений обратимых функций. Данные представления выбираются в зависимости от способа задания обратимой функции, с одной стороны, и от выбора некоторого универсального множества примитивов, из которых в дальнейшем конструируется оптимальное по тем или иным признакам представление обратимой функции, с другой. В качестве примитивов могут выступать элементы обратимых схем, вентили (например, элементы соответствующие множеству функций Тоффоли) или определенного вида подстановки (например, такие подстановки, которые реализуют 3-циклы или транспозиции), или специальным образом сконструированные таблицы значений обратимых функций. Помимо упомянутых выше способов существуют другие модели, представляющие обратимую функцию, например, ветвящиеся программы и двоичные диаграммы решений (ВОБ), и имеются работы, в которых основой для построения алгоритма минимизации является техническая реализация тех или иных обратимых функций. Для работ, появившихся в последнее время, характерно использование сразу нескольких вариантов решения данной задачи, например, использование функций Тоффоли и специальным образом сконструированных таблиц значений обратимых функций.

В диссертации исследуется направление, связанное с использованием элементов логической обратимой схемы при конструировании минимальных представлений обратимых функций, где в качестве элементов схемы рассматриваются функции Тоффоли. Такой выбор обоснован тем, что наиболее интенсивно исследуются именно эти функции, которые имеют техническую реализацию и представление вентилями в квантовых схемах. В работах [32] и [35] вычислено число квантовых элементов необходимых для построения 2-х и 3-х-битового

п

ли.

В [54] приводится алгоритм синтеза обратимых логических схем, использующий элементы Тоффоли; здесь впервые осуществлено построение библиотеки всех обратимых схем на 3 входах. В [40] предложен алгоритм вычисления сложности произвольной обратимой (4,4)-функции. В алгоритме используют разбивку множества всех обратимых функций на классы эквивалентности по перестановкам входов и симметричности схем.

В исследовании задачи минимизации обратимых представлений (п, 1)-функций опорной является идея (введенная совместно Т. Тоффоли и Э. Фред-

киным в 1982-м году) конструирования обратимой схемы с использованием дополнительных входов, называемых источником (source) и дополнительных выходов, называемых мусором (sink) при условии, что число входов равно числу выходов в схеме [37].

Обзор работ, содержащих алгоритмы минимизации обратимых представлений (n, 1)-функций, позволил выделить следующие особенности:

1) конструируются схемы обратимых функций, реализующие подмножества функций алгебры логики, имеющие конкретные технические приложения [63], [65];

2) в предлагаемых алгоритмах реализуются полиномы Жегалкина (n, 1)-функций [43], [65]; обобщенные формы Рида-Маллера [64];

3) алгоритмы минимизации предполагают использование более одного дополнительного входа [43], [57].

Следует отметить работы [26], [27], [28], [29], в которых осуществляется реализация характеристического полинома булевой функции в виде квантовой OBDD, с использованием технологии fingerprinting и функции квантового хэширования; здесь приводятся оценки схемной сложности предлагаемых реализаций, приводятся вычислительные результаты, полученные после запуска соответствующих алгоритмов. Предлагаемый авторами метод непосредственно связан с дизъюнктивными нормальными формами булевых функций.

( n, 1)

функций в классе обратимых схем будет использоваться подмножество Tr С T следующих функций Тоффоли:

T0 (xi) • (x0, x1, , xn) ^ (x0, x1, xi, xn) ,

Tk (xii, xik , x0) • (x0, x1, xn) ^ (x0 ф Хч • ... • xik , x1, xn) ,

k < n, {¿1, ...,ik} С {1, ...,n}.

Функции множества Тr позволяют реализовать полиномиальные нормальные формы (n, 1)-фупкций па одном дополнительном входе.

Пусть (n, 1)-функции полиномами класса ZhE. Через RS

обозначим класс обратимых схем, построенных на элементах множества Tr и реализующих обратимые (n + 1,n + 1)-фупкции, которые представляют (n, 1)-

функций вида Т0, ТП, 1 и реализующих все обратимые функции.

Цели и задачи диссертационной работы. Диссертация посвящена исследованию сложности представлений многовыходных функций алгебры логики в классах полиномов и обратимых схем. В диссертации рассматриваются следующие задачи:

- нахождение сложности представлений функций алгебры логики в классах расширенных двупорожденных операторных форм ЕНЪ и ЕН;

- исследование сложности обратимых реализаций полиномов функций алгебры логики в классе обратимых схем Я^;

- разработка и реализация алгоритмов нахождения сложности представлений функций алгебры логики в классах расширенных двупорожденных операторных форм ЕНЪ и ЕН;

- разработка и реализация алгоритма нахождения сложности обратимых реализаций полиномов функций алгебры логики в классе обратимых схемЯ^, алгоритма нахождения сложности представлений многовыходных обрати-

Я

Методология и методы исследования. В диссертации применяются методы линейной алгебры при использовании операторного подхода в представлении функций алгебры логики в классах расширенных полиномиальных нормальных форм и в классе обратимых схем методы комбинаторики при поиске «сложных» функций в классах расширенных полиномиальных нормальных форм, методы теории функций алгебры логики при получении границ значения функции Шеннона сложности представлений функций алгебры логики в указанных классах, методы теории функциональных систем в конструировании обратимых схем, технология параллельного программирования при получении

Я

Положения, выносимые на защиту, и научная новизна. Основные научные результаты диссертации следующие:

- получено точное значение функции Шеннона сложности представлений функций алгебры логики в классах расширенных двупорожденных операторных форм ЕНЪ;

- получено асимптотически точное значение функции Шеннона сложности обратимых реализаций полиномов функций алгебры логики в классе обратимых схем Яб1;

- разработан алгоритм нахождения сложности представлений функций алгебры логики в классах расширенных двупорожденных операторных форм ЕНЪ и ЕН, разработан алгоритм нахождения сложности обратимых реализаций полиномов функций алгебры логики в классе обратимых схем

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

Основные результаты диссертации являются новыми.

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

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

1) Международный российско-китайский семинар «Алгебра и логика» (Иркутск, 2007);

2) Международная конференция «Алгебра и ее приложения» (Красноярск,

2007)

3) Российская школа-семинар, посвященная 60-летию со дня рождения Ю. Е. Шишмарева «Синтаксис и семантика логических систем» (Владивосток,

2008);

5) Российская 3-я школа-семинар, посвященная 80-летию со дня рождения А. И. Кокорина «Синтаксис и семантика логических систем» (Иркутск, 2010);

6) XIX международная конференция по мягким вычислениям и измерениям SCM'2016 (Санкт-Петербург, 2016);

7) XX международная конференция по мягким вычислениям и измерениям SCM'2017 (Санкт-Петербург, 2017);

8) 5-я российская школа-семинар «Синтаксис и семантика логических систем» (Улан-Удэ, 2017);

9) XXI международная конференция по мягким вычислениям и измерениям SCM'2018 (Санкт-Петербург, 2018);

10) X международная конференция «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 2018);

11) Международная конференция «Мальцевские чтения» (Новосибирск, 2018).

Публикации автора по теме диссертации. По теме диссертации опубликовано 20 научных работ [66]-[85], отражающих основное содержание диссертации. В том числе 4 работы [71], [74], [81], [83] в журналах, рекомендованных ВАК РФ, 3 работы [83], [84], [85] опубликованы в сборнике научных трудов, входящим в базу данных международного цитирования Scopus. Имеются также 3 свидетельства [72], [73], [76] о государственной регистрации программ для ЭВМ.

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

Первая глава посвящена задаче нахождения сложности представлений функций алгебры логики в классах расширенных двупорожденных операторных форм EHb и EH

В первом параграфе через рассмотрение классов H пучков вида А = (а0,..., ат,..., ав которых а0 = b, построен класс расширенных двупорожденных операторных форм

EH = U E,

АбЯь

' ' с = ^ ат.

Е = и {тт}и{А}

т€{0,1}"

называется расширением двупорожденного операторного пучка А, если операторный пучок Тт = (ъ0, ..., Ът, 1) строится следующим образом:

ат, если т = т, с, если т = т; Н

то

ЕН = и Е

АеН

обозначает класс всех расширенных двупорожденных операторных форм.

Во втором параграфе получено точное значение функции Шеннона сложности представлений функций алгебры логики в любом из классов расширенных двупорожденных операторных форм ЕНЪ. Для этого предварительно доказывается следующее предложение:

Предложение 1. Для любого класса ЕНЬ, где Ъ оператор длины и, сложность ЬЕНъ(/) функции /(ж) равна:

Ьещ(/) = шт{ тт {/(/)}; 2П - тах{/(/)} + 1},

по всем, операторным формам ОЕ(/), построенным по пучкам класса Нь.

Следствием предложения 1 является значение верхней границы функции ЕН

Следствие 1. Значение функции Шеннона сложности представлений

ЕН

венству:

Ьвнъ(и) < V.

Для получения значения нижней границы функции Шеннона были получены 6 последовательностей множеств функций

МП = {рп(ж),яП(£),#(*)}, и > 3, ] е {1,2,..., 6},

функции которых определяются индуктивно. При и = 3 функции р3(ж, ж2, ж3), я3(жьж2,ж3), ¿3(х1,ж2, ж3) представлены в таблице 1.

3 р3(Ж1,Ж2,Жз) ^з (Х1,Ж2,Жз) ¿з(х1,Ж2,Жз)

Список литературы диссертационного исследования кандидат наук Францева Анастасия Сергеевна, 2019 год

Список литературы

[1] Балюк, А. С. Функция Шеннона для некоторых классов операторных полиномиальных форм / А. С. Балюк, С. Ф. Винокуров // Оптимизация, управление, интеллект. — 2000. — Выи 5. — С. 167-180.

[2] Винокуров, С. Ф. Перечисление операторных классов булевых функций / С. Ф. Винокуров, А. С. Казимиров // Известия Иркутского государственного университета. — Серия : Математика. — 2009. — Том 2, № 2. — С. 40-55.

[3] Винокуров, С. Ф. Полиномиальная декомпозиция булевых функций / С. Ф. Винокуров, Н. А. Перязев // Матем. заметки. — 1993. — Том 53, выпуск 2.

- С. 25-29.

[4] Винокуров, С. Ф. Полиномиальные разложения булевых функций / С. Ф. Винокуров, Н. А. Перязев // Киберн. и системный анализ. — 1993. — № 6.

- С. 34-47.

[5] Винокуров С. Ф. Система поддержки принятия решений при врачебных назначениях на основе четырехзначной логики / С.Ф. Винокуров, A.C. Казимиров, Н.Ю. Пустовойтов, A.C. Францева // Материалы XIX Международной конференции по мягким вычислениям и измерениям : сб. докл. — Санкт-Петербург, 2016. - С. 10-12.

[6] Винокуров, С. Ф. Специальная операторная форма булевых функций и некоторые ее приложения / С.Ф. Винокуров / / Международная школа-семинар "Синтез и сложность управляющих систем". — Новосибирск, 2004.

- С. 26-29.

[7] Винокуров С. Ф. Четырехзначная логика с мультиинтерпретациями как модель для системы принятия решений / С.Ф. Винокуров, A.C. Казимиров, В.И. Пантелеев, Л.В. Рябец // Материалы XVIII Международной конференции по мягким вычислениям и измерениям : сб. докл. — Том 2. — Санкт-Петербург, 2015. — С. 82-85.

[8] Жегалкин, И. И. Арифметизация символической логики / И. И. Жегалкин // Матем. сборник. - 1928. - Т.35 - С. 311-377.

[10] Закаблуков, Д. В. О сложности обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT / Д.В. Закаблуков // Дискрет, матем. — 2016. — том 28, выпуск 2. — С. 12-26.

[11] Иркутский суперкомпьютерный центр СО РАН [Электронный ресурс]: сайт.

— Иркутск: ИДСТУ СО РАН. — URL: http://hpc.icc.ru (дата обращения: 08.09.2017).

[12] Избранные вопросы теории булевых функций / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков, О. В. Зубков, К. Д. Кириченко, В. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева ; под ред. С. Ф. Винокурова и Н. А. Перязева.

— М. : Физматлит, 2001. — 192 с.

[13] Казимиров, А. С. Оценка числа классов LP-эквивалентности булевых функций / А. С. Казимиров // Вестник Бурятского университета : Математика и информатика. — 2005. — Серия 13, выпуск 2. — С. 17-22.

[14] Кириченко, К.Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К.Д. Кириченко // Дискретная математика. — 2005. - Том 17, № 3. - С. 80-88.

[15] Пантелеев, В. П. Об операторах булевых функций / В. И. Пантелеев, H.A. Перязев // Синтез и сложность управляющих систем : Материалы XI Межгосударственной школы-семинара (Нижний Новгород, 20-25 ноября 2000 г.). - 2001. - Часть 2. - С. 141-146.

[16] Перязев П. А. Основы теории булевых функций / Н. А. Перязев. — М. : Физматлит, 1999. — 112 с.

[17] Перязев, П. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. — 1995. — Т. 34, № 3. - С. 323-326.

[18] Пат. 20176ЦЗ63 Российская Федерация, МПК Реестр программ для ЭВМ Программа алгоритма поиска всех 1р-классов булевых функций 5 переменных : / Казимиров A.C., Ильин Б.П., Пантелеев В.И., Реймеров С.Ю.,

Францева A.C. ; заявитель и патентообладатель Федеральное государственное бюджетное образовательное учреждение высшего образования «Иркутский государственный университет» (ФГБОУ ВО «ИГУ») (RU). — № заявки 2017611544; заявл. 20.02.2017; опубл. 14.04.2017, Бюл. ..V" 4. 1 с.

[19] Пат. 2017616762 Российская Федерация, МПК Реестр программ для ЭВМ Программа точной минимизации полиномиальных представлений булевых функций 6 переменных : / Казимиров A.C., Ильин Б.П., Пантелеев В.И., Францева A.C. ; заявитель и патентообладатель Федеральное государственное бюджетное образовательное учреждение высшего образования «Иркутский государственный университет» (ФГБОУ ВО «ИГУ») (RU). — № заявки 2017611542; заявл. 22.02.2017; опубл. 13.06.2017, Бюл. №6.-1 с.

[20] Рябец, Л. В. Алгоритм точной минимизации булевых функций в классе кронекеровых форм / С. Ф. Винокуров, Л. В. Рябец // Алгебра и теория моделей 4. — Новосибирск, 2003. — С. 148-159.

[21] Рябец, Л. В. Получение минимальных кронекеровых форм булевых функций / С. Ф. Винокуров, Л. В. Рябец // Вестник Иркутского университета. Специальный выпуск : Материалы ежегодной научно-теоретической конференции молодых ученых. — Иркутск, 2004. — С. 100-101.

[22] Францева, A.C. Квантовый алгоритм поиска на языке линейных пространств / A.C. Францева // Математика и проблемы ее преподавания в вузе : Труды III межвузовской зональной конференции, посвященной памяти профессора Б.А. Бельтюкова. — Иркутск, 2007. — С. 136-140.

[23] Францева, A.C. Квантовые вычисления на языке линейных пространств / A.C. Францева, С.Ф. Винокуров // Вестник Бурятского университета : Математика и информатика. — 2006. — Серия 13, выпуск 3. — С. 15-22.

[24] Францева, A.C. О преобразованиях линейных пространств / A.C. Францева // Синтаксис и семантика логических систем : материалы российской школы-семинара, посвященной 100-летию со дня рождения К. Геделя. — Иркутск, 2006. - С. 104-108.

[25] Яблонский С. В. Введение в дискретную математику : Учеб. пособие для вузов / под ред. В. А. Садовничего / С. В. Яблонский. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.

[26] Ablayev, F. Computing Boolean Functions via Quantum Hashing / F. Ablayev, A. Vasiliev // Computing with New Resources, C.S. Calude et al. (Eds.) : Gruska Festschrift, Lecture Notes in Computer Science. — Springer Berlin / Heidelberg, 2014 - Vol. 8808. - P. 149-160.

[27] Ablayev, F. Algorithms for quantum branching programs based on fingerprinting / F. Ablayev, A. Vasiliev // Electronic Proceedings in Theoretical Computer Science. - 2009. - 9. - P. 1-11.

[28] Ablayev, F. On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions / F. Ablayev, A. Khasianov, A. Vasiliev, // Electronic Colloquium on Computational Complexity. — 2008. — TR08-085. — 10 p.

[29] Ablayev, F. On the computational power of probabilistic and quantum branching program / F. Ablayev, A. Gainutdinova, M. Karpinski, C. Moore, C. Pollett //Information and Computation. — 2005. — Vol. 203, Iss. 2. — P. 145-162.

[30] BaMuk, A.S. Mathematical logic models for decision support systems in the case of incomplete information / A.S. Baliuk, A.I. Gaidukov, N.A. Peryazev, Yu.V. Peryazeva // Proceedings of International Conference on Soft Computing and Measurements SCM'2015, May 19-21, St.Petersburg, Russia. - 2015. - P. 217218. https://doi.org/10.1109/SCM.2015.7190461.

[31] Banerjee, A. Minimal Designs of Reversible Sequential Elements / A. Banerjee, A. Pathak, G. W. Dueck // Reversible Computation: 6th International Conference, Proceedings.^ Springer International Publishing. — 2014. — P. 137-148. https://doi.org/10.1007/978-3-319-08494-7_ll.

[32] Barenco, A. Elementary gates for quantum computation / A. Barenco, C. H. Bennett, R. Cleve and oth. // Physical Review A. — 1995. — Vol. 52, Iss. 5. — P. 3457-3467. https://doi.org/10.1103/PhysRevA.52.3457.

[33] Bennett, C. H. Logical Reversibility of Computation / C. H. Bennett // IBM Journal of Research and Development. — 1973. — Vol. 17, Iss. 6. — P. 525-532. https://doi.org/10.1147/rd.176.0525.

[34] Deutsch, D. Rapid Solution of Problems by Quantum Computation / D. Deutsch, R. Jozsa // Proceedings of the Royal Society of London A:

[35] DiVincenzo, D. P. Two-bit gates are universal for quantum computation / D. P. DiVincenzo // Physical Review A. - 1995. - Vol. 51, Iss. 2. - P. 1015-1022.

[36] Feynman, R. P. Simulating Physics with Computers / Richard P. Feynman // International Journal of Theoretical Physics. — 1982. — Vol. 21, No. 6/7. — P. 467-488.

[37] Fredkin, E. Conservative Logic / E. Fredkin, T. Toffoli // International Journal of Theoretical Physics. - 1982. - Vol. 21, Iss. 3. - P. 219-253.

[38] Fujita, M.. Sasao, T. Representations of Discrete Functions. Kluwer Academic Publishers Norwell, MA, USA. - 1996. - 450 p.

[39] Golubitsky, 0. A Study of Optimal 4-Bit Reversible Toffoli Circuits and Their Synthesis / O. Golubitsky, D. Maslov // IEEE Transactions on Computers. — 2012. - Vol. 61, No 9. - P. 1341-1353.

[40] Golubitsky, O. Synthesis of the Optimal 4-bit Reversible Circuits / O. Golubitsky, S. M. Falconer, D. Maslov // Proceedings of the 47th Design Automation Conference, Anaheim, California. — 2010. — P. 653-656.

[41] Grover, Lov K. Quantum Mechanics Helps in Searching for a Needle in a Haystack / Lov K. Grover // Phys. Rev. Lett. - 1997. - Vol. 79, Iss. 325.

- P. 325-328. https://doi.org/10.1103/PhysRevLett.79.325.

[42] Islam, Md. Saiful Realization of a Novel Fault Tolerant Reversible Full Adder Circuit in Nanotechnology / Md Saiful Islam, Muhammad Mahbubur Rahman, Zerina Begum, Mohd. Zulfiquar Hafiz // Int. Arab J. Inf. Technol. — 2010. — Vol. 7, Iss. 3. - P. 317-323.

[43] Iwama, K. Transformation Rules for Designing CNOTbased Quantum Circuits / K. Iwama, Y. Kambayashi, S. Yamashita. // DAC '02 Proceedings of the 39th annual Design Automation Conference. — 2002. — P. 419-424.

[44] Kazimirov, A. Decision support system based on 4-valued logic with multi-interpretations / A. Kazimirov, V. Panteleyev, L. Riabets, S. Vinokurov // Proceedings of XVIII International Conference on Soft Computing and

[45] Knuth, D. E. MMIXware: A RISC Computer for the Third Millennium / Donald E. Knuth // Springer Heidelberg New York Dordrecht London. — 2003. — LNCS Sublibrary: SL 2 - Programming and Software Engineering. ^550 p. https://doi.org/10.1007/3-540-46611-8.

[46] Landauer, R. Irreversibility and Heat Generation in the Computing Process / R. Landauer // Journal IBM Journal of Research and Development. — 1961. — Vol. 5, Iss. 3. - P. 183-191. https://doi.org/10.1147/rd.53.0183.

[47] Maslov, D. Reversible logic synthesis : A thesis submitted in partial fulfillment of the requirements for the degree of doctor of philosophy in the faculty of computer science / Maslov Dmitri. — The University of New Brunswick, 2003. _ 155 p_

[48] Maslov, D. Techniques for the Synthesis of Reversible Toffoli Networks / D. Maslov, D. M. Miller, G. W. Dueck // ACM Transactions on Design Automation of Electronic Systems. — Vol. 12, Iss. 4. — 2007. — Article No. 42. https://doi.org/10.1145/1278349.1278355.

[49] Muller, D. E. Application of Boolean algebra to switching circuit design and error detection / D. E. Muller // Transactions of the I.R.E. Professional Group on Electronic Computers. — 1954. — Vol. EC-3, No. 3. — P. 6-12. https://doi.org/10.1109/IREPGELC.1954.6499441.

[50] Patel, K. N. Optimal Synthesis of Linear Reversible Circuits / K. N. Patel, I. L. Markov, J. P. Hayes // Quantum Information and Computation. — 2008. Vol. 8, No. 3/4. - P. 282-294.

[51] Reed, I. S. A class of multiple-error-correcting codes and decoding scheme / I. S. Reed // Transactions of the IRE Professional Group on Information Theory. — 1954. - Vol. 4, No. 4. - P. 38-49. https://doi.org/10.1109/TIT.1954.1057465.

[52] Saeedi, M. A Library-Based Synthesis Methodology for Reversible Logic / M. Saeedi, M. Sedighi, M. S. Zamani // Microelectronics Journal. — Vol. 41, Iss. 4. - 2010. - P. 185-194.

[54] Shende, V. V. Synthesis of Reversible Logic Circuits / V. V. Shende, A. K. Prasad and oth. // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - Vol. 22, No. 6. - 2003. - P. 710-722. https://doi.org/10.1109/TCAD.2003.811448.

[55] Shor, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer / Peter W. Shor // SIAM Journal on Computing. - 1997. - Vol. 26, Iss. 5. - P. 1484-1509. https://doi.org/10.1137/S0097539795293172.

[56] Simon, D. On the power of quantum computation, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science / D. Simon // IEEE Computer Society Press, Los Alamitos, CA. - 1994. - P. 116-123. https://doi.org/10.1109/SFCS.1994.365701.

[57] Soeken, M. Embedding of Large Boolean Functions for Reversible Logic / Soeken M., Wille R., Keszocze O. and oth. // ACM Journal on Emerging Technologies in Computing Systems (JETC) - Regular Papers. — 2016. — Vol. 12, Iss. 4, Article No. 41.

[58] Toffoli, T. Bicontinuous Extensions of Invertible Combinatorial Functions / T. Toffoli // Mathematical Systems Theory. - 1981. - Vol. 14. - P. 13-23.

[59] Toffoli, T. Reversible Computing / T. Toffoli // Automata, Languages and Programming (Series: Lecture Notes in Computer Science). — Springer Berlin Heidelberg. - 1980. - Vol. 85. - P. 632-644.

[60] Vinokurov, S. Decision Support System for Medical Prescriptions Based on 4-Valued Logic / S. Vinokurov, A. Kazimirov, N. Pustovoytov, A. Frantseva // Proceeding of the 19th International Conference on Soft Computing and Measurement (SCM), St. Petersburg, Russia. — 2016. — P. 307-308. https://doi.org/10.1109/SCM.2016.7519764.

[61] Wille, R. BDD-based Synthesis of Reversible Logic for Large Functions / R. Wille, R. Drechsler // Electronic Notes in Theoretical Computer Science. — 2010. - Vol. 253, Iss. 6. - P. 57-70.

[62] Yang, G. Group Theory Based Synthesis of Binary Reversible Circuits / G. Yang, X. Song, W. N. N. Hung, F. Xie, M. A. Perkowski // Theory and Applications of Models of Computation Vol. — 2006. — 3959 of the series Lecture Notes in Computer Science. — P. 365-374.

[63] Younes, A. A Fast Quantum Algorithm for the Affine Boolean Function Identification / A. Younes // The European Physical Journal Plus 130 (2). _ 2015. - P. 1-9.

[64] Younes, A. Representation of Boolean Quantum Circuits as Reed-Muller Expansions / A. Younes, J. Miller // International Journal of Electronics. — 2004. - No.7 - P. 431-444.

[65] Younes, A. Synthesis and Optimization of Reversible Circuits for Homogeneous Boolean Functions / A. Younes // Journal of Circuits, Systems, and Computers. - Vol. 19, No. 7. - 2010. - P. 1423-1434.

Публикации по теме диссертации

[66] Францева, А. С. Алгоритм синтеза обратимых логических схем / А.С. Фрап-цева, С.Ф. Винокуров // Международная конференция «Алгебра и ее приложения» : Тезисы докладов. — Красноярск, 2007. — С. 32-33.

[67] Францева, А. С. Факториальная система счисления в задаче синтеза обратимых логических схем / А.С. Францева, С.Ф. Винокуров // Алгебра и логика : Материалы международного российско-китайского семинара. — Иркутск, 2007. - С. 31-35.

[68] Францева, А. С. Синтез обратимых логических схем / А.С. Францева, С.Ф. Винокуров // Синтаксис и семантика логических систем : материалы российской школы-семинара, посвященной 60-летию со дня рождения Ю. Е. Шишмарева. — Владивосток, 2008. — С. 32-33.

[69] Францева, А. С. Сложность булевых функций в некоторых классах обратимых схем / А.С. Францева, С.Ф. Винокуров // Синтез и сложность управляющих систем : материалы XVIII международной школы-семинара имени академика О. Б. Лупанова. Пенза, 28 сент.-З окт. 2009 г. — Пенза, 2009. — С. 20-22.

[70] Францев а, A.C. Алгоритм вычисления сложности произвольно заданной обратимой функции / A.C. Францева, С.Ф. Винокуров // Синтаксис и семантика логических систем : материалы 3-й Российской школы-семинара, посвященной 80-летию со дня рождения А. И. Кокорина. — Иркутск, 2010. _ с. 9-12.

[71] Францева, A.C. Приближенный алгоритм вычисления сложности обратимой функции в базисе Тоффоли / A.C. Францева, С.Ф. Винокуров // Известия Иркутского государственного университета. — Серия : Математика. _ 2011. С. 12-26.

[72] Пат. 2016660636 Российская Федерация, МПК Реестр программ для ЭВМ. Программа алгоритма вычисления приближенного значения сложности обратимой функции в базисе Тоффоли / Францева A.C., Винокуров С.Ф., Рябец Л.В. ; заявитель и патентообладатель Федеральное государственное бюджетное образовательное учреждение высшего образования «Иркутский государственный университет» (ФГБОУ ВО «ИГУ») (RU). — № 2016617938/69 ; заявл. 20.07.16 ; опубл. 19.09.16, Бюл. № 10. - 1 с.

[73] Пат. 2016660638 Российская Федерация, МПК Реестр программ для ЭВМ. Программа алгоритма синтеза обратимых логических схем в базисе Тоффоли / Францева A.C., Винокуров С.Ф., Балюк A.C., Казимиров A.C. ; заявитель и патентообладатель Федеральное государственное бюджетное образовательное учреждение высшего образования «Иркутский государственный университет» (ФГБОУ ВО «ИГУ») (RU). — № 2016617950/69 ; заявл. 20.07.16 ; опубл. 19.09.16, Бюл. № 10. — 1с.

[74] Францева, A.C. Сложность представлений многовыходных функций алгебры логики / С.Ф. Винокуров, A.C. Францева // Известия Иркутского государственного университета. — Серия : Математика. — 2016. — Т. 16. — С. 30-42.

[75] Францева, A.C. Схемная сложность представлений многовыходных функций алгебры логики в обратимых вычислениях / A.C. Францева, С.Ф. Винокуров // Материалы XIX Международной конференции по мягким вычислениям и измерениям SCM'2016 : сб. докл. — Санкт-Петербург, 2016. — С. 130-132.

[76] Пат. 2017619310 Российская Федерация, МПК Реестр программ для ЭВМ. Программа построения минимального представления многовыходных булевых функций в классе обратимых схем / Францева A.C. Винокуров С.Ф., Рябец Л.В. ; заявитель и патентообладатель Федеральное государственное бюджетное образовательное учреждение высшего образования «Иркутский государственный университет» (ФГБОУ ВО «ИГУ») (RU). — № заявки 2017616741 ; заявл. 11.07.2017 ; опубл. 22.08.17, Бюл. №9.-1 с.

[77] Францева, A.C. Алгоритм построения минимального представления многовыходных функций алгебры логики в классе обратимых схем / А. С. Францева, С. Ф. Винокуров, Л. В. Рябец, С. И. Тодиков // Материалы XX Международной конференции по мягким вычислениям и измерениям SCM'2017 : сб. докл. — Санкт-Петербург, 2017. — С. 175-179.

[78] Францева, A.C. Алгоритм построения минимальной обратимой схемы, реализующей булеву функцию / A.C. Францева, С.Ф. Винокуров, С. И. Тодиков // Синтаксис и семантика логических систем : материалы 5-й Российской школы-семинара. — Улан-Удэ, 2017. — С. 27-31.

[79] Францева, A.C. Нижняя оценка сложности представлений булевых функций в классе расширенных однородных операторных форм /С.Ф. Винокуров, А. С. Францева / Дискретные модели в теории управляющих систем: X Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды / Отв. ред. В. Б. Алексеев, Д. С. Романов, Б. Р. Данилов. Москва : МАКС Пресс, 2018. - С. 83-86.

[80] Францева, A.C. Представление многовыходных булевых функций обратимыми схемами в базисе Тоффоли / A.C. Францева , С.Ф. Винокуров , A.C. Казимиров // XXI Международная конференция по мягким вычислениям и измерениям SCM'2018 : сб. докл. — Санкт-Петербург, 2018. — Т. 1. — С. 748-750.

[81] Францева, A.C. Алгоритм минимизации функций алгебры логики в классе обратимых схем Тоффоли / A.C. Францева // Известия Иркутского государственного университета. — Серия : Математика. — 2018. — Т. 25. — С. 144-158. https://doi.org/10.26516/1997-7670.2018.25.144

[82] Францев а, А.С. Сложность булевых функций в классах полиномиальных нормальных форм / С.Ф. Винокуров, А.С. Францева // Международная конференция «Мальцевские чтения», 19-22 ноября 2018г. : тезисы докладов. — Новосибирск, 2018. — С. 30.

[83] Францева, А.С. Сложность представлений булевых функций в классах расширенных двупорожденных операторных форм / А.С. Францева // Сибирские Электронные Математические Известия : электронное периодическое издание. — 2019. — Т. 16. — С. 523-541. https://doi.org/10.33048/semi.2019.16.034.

[84] Frantseva, A.S. Algorithm for constructing minimal representations of multi-ple-output Boolean functions in the reversible logic circuits / S.F. Vinokurov, L. V. Ryabets, S.I. Todikov, A.S. Frantseva / / Proceedings of the 20th International Conference on Soft Computing and Measurements (SCM), St.Petersburg, Russia. — 2017. — P. 541-543. https://doi.org/10.1109/SCM.2017.7970644.

[85] Frantseva, A.S. Complexity of representations of multiple-output Boolean functions in the reversible logic circuits / S.F. Vinokurov, A.S. Frantseva // Proceeding of the 19th International Conference on Soft Computing and Measurement (SCM), St.Petersburg, Russia. — 2016. — P. 374-376. https://doi.org/10.1109/SCM.2016.7519785.