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

Описаны результаты экспериментального исследования алгоритма декомпозиции частичных булевых функций и систем, основанного на сведении задачи декомпозиции к задаче «выполнимость конъюнктивной нормальной формы». Для проверки выполнимости задачи использованы известные SAT-программы picosat и zChaff....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автори:	Авлочинская, Т.В., Бибило, П.Н.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2012
Назва видання:	Управляющие системы и машины
Теми:	Новые методы в информатике
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/83064
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений / Т.В. Авлочинская, П.Н. Бибило // Управляющие системы и машины. — 2012. — № 3. — С. 15-23. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-83064
record_format	dspace
spelling	irk-123456789-830642015-06-14T03:02:04Z Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений Авлочинская, Т.В. Бибило, П.Н. Новые методы в информатике Описаны результаты экспериментального исследования алгоритма декомпозиции частичных булевых функций и систем, основанного на сведении задачи декомпозиции к задаче «выполнимость конъюнктивной нормальной формы». Для проверки выполнимости задачи использованы известные SAT-программы picosat и zChaff. The results of experimental research of the decomposition algorithm for partial Boolean functions and systems are described. The algorithm is based on the reduction of the decomposition problem to the SAT problem. To check the satisfiability for the given CNF the SAT-programmes (picosat and zChaff) are used. Описано результати експериментального дослідження алгоритму декомпозиції часткових булевих функцій і систем, заснованого на зведенні задачі декомпозиції до задачі «виконуваності кон’юнктивної нормальної форми». Для перевірки виконуваності задачи використано відомі SAT-програми picosat та zChaff. 2012 Article Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений / Т.В. Авлочинская, П.Н. Бибило // Управляющие системы и машины. — 2012. — № 3. — С. 15-23. — Бібліогр.: 12 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/83064 517.98 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Новые методы в информатике Новые методы в информатике
spellingShingle	Новые методы в информатике Новые методы в информатике Авлочинская, Т.В. Бибило, П.Н. Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений Управляющие системы и машины
description	Описаны результаты экспериментального исследования алгоритма декомпозиции частичных булевых функций и систем, основанного на сведении задачи декомпозиции к задаче «выполнимость конъюнктивной нормальной формы». Для проверки выполнимости задачи использованы известные SAT-программы picosat и zChaff.
format	Article
author	Авлочинская, Т.В. Бибило, П.Н.
author_facet	Авлочинская, Т.В. Бибило, П.Н.
author_sort	Авлочинская, Т.В.
title	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений
title_short	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений
title_full	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений
title_fullStr	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений
title_full_unstemmed	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений
title_sort	экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2012
topic_facet	Новые методы в информатике
url	http://dspace.nbuv.gov.ua/handle/123456789/83064
citation_txt	Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений / Т.В. Авлочинская, П.Н. Бибило // Управляющие системы и машины. — 2012. — № 3. — С. 15-23. — Бібліогр.: 12 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT avločinskaâtv éksperimentalʹnoeissledovanierazdelimostičastičnyhbulevyhfunkcijnaosnoverešeniâlogičeskihuravnenij AT bibilopn éksperimentalʹnoeissledovanierazdelimostičastičnyhbulevyhfunkcijnaosnoverešeniâlogičeskihuravnenij
first_indexed	2025-07-06T09:47:44Z
last_indexed	2025-07-06T09:47:44Z
_version_	1836890473542713344
fulltext	УСиМ, 2012, № 3 15 УДК 517.98 Т.В. Авлочинская, П.Н. Бибило Экспериментальное исследование разделимости частичных булевых функций на основе решения логических уравнений Описаны результаты экспериментального исследования алгоритма декомпозиции частичных булевых функций и систем, основанно- го на сведении задачи декомпозиции к задаче «выполнимость конъюнктивной нормальной формы». Для проверки выполнимости за- дачи использованы известные SAT-программы picosat и zChaff. The results of experimental research of the decomposition algorithm for partial Boolean functions and systems are described. The algo- rithm is based on the reduction of the decomposition problem to the SAT problem. To check the satisfiability for the given CNF the SAT-programmes (picosat and zChaff) are used. Описано результати експериментального дослідження алгоритму декомпозиції часткових булевих функцій і систем, заснованого на зведенні задачі декомпозиції до задачі «виконуваності кон’юнктивної нормальної форми». Для перевірки виконуваності задачи ви- користано відомі SAT-програми picosat та zChaff. Введение Задача разделения (декомпозиции) булевой функции на подфункции давно изуча- ется в литературе с целью создания эффектив- ных методов синтеза комбинационных логиче- ских схем в различных технологических бази- сах. В настоящее время декомпозиция находит практическое применение при синтезе структур FPGA (Field-Programmable Gate Arrays) [1], по- лучивших широкое распространение при реали- зации цифровых схем. В литературе проведена классификация видов разложений булевых функ- ций, сформулированы критерии существования разложений функций и систем функций, пред- ложены методы, алгоритмы и программы де- композиции. Проблемам декомпозиции посвя- щен обзор [2] и монографии [3–5]. При реше- нии задач декомпозиции используются различ- ные формальные модели – булевы и троичные матрицы [6], специальные таблицы [5], аппарат понятий производной, дифференциала и разно- сти булевой функции [7], спектральные пред- ставления [8] и др. Предлагается также [5, 9] использовать логические уравнения и преобра- зовывать уравнения к виду конъюнктивной нор- мальной формы (КНФ), т.е. сводить решение за- дачи декомпозиции к задаче выполнимости КНФ (Boolean satisfiability problem – SAT-problem) [10]. Для решения КНФ-уравнений имеются мощные SAT-программы (SAT-solvers) [11], хо- рошо зарекомендовавшие себя при верифика- ции логических схем [12]. В статье описаны результаты эксперимен- тального исследования свойства разделимости (декомпозабельности) не полностью определен- ных булевых функций и систем в зависимости от степени определенности функций, числа функций в системе и других параметров. Для проверки существования функциональных раз- ложений используется аппарат логических урав- нений, для решения уравнений – известные SAT-программы picosat и zChaff [11]. Основные понятия и определения Булевыми называются двоичные (0, 1) функ- ции f (x) = f (x1, x2, , xn) двоичных (булевых) пе- ременных x1, x2, , xn. Пусть Vx – булево про- странство, построенное над переменными буле- ва вектора x = (x1, x2, , xn). Элементами этого пространства являются n-компонентные набо- ры (векторы) x нулей и единиц. Булева функ- ция, значения 0, 1 которой определены на всех 2n элементах x  Vx, называется полностью оп- ределенной. Если же на некоторых элементах бу- лева пространства Vx значения функции не оп- ределены, то такая функция называется не пол- ностью определенной или частичной. Частичная булева функция принимает единичное значение на элементах x подмножества 1 fM булева про- странства Vx и нулевое значение на элементах подмножества 0 fM . На всех остальных элемен- тах пространства Vx, образующих подмножество fM  пространства Vx, значение частичной функ- ции не определено. Очевидно, что 0 fM  1 fM   fM  = ,xV а 0 fM + 1 fM + fM  = 2 n , где через 16 УСиМ, 2012, № 3 M  обозначена мощность множества M. Под степенью неопределенности d булевой функ- ции будем понимать отношение мощности мно- жества fM  к мощности всего булева простран- ства Vx, т.е. 2 f n M d   . Степень определенности s частичной булевой функции выражается сум- мой s = 0 1s s величин 0 0 2 f n M s  , 1 1 2 f n M s  . Пример частичной булевой функции, зави- сящей от переменных x1, x2, x3, x4, x5, приведен в табл. 1. Для данной функции s0 =s1 = 5/32, s = 10/32, d = 22/32. Упорядоченную систему частичных булевых функций будем называть далее частичной векторной булевой функцией или просто векторной функцией. Пусть задана частичная функция f (x1, , xn) = = f (x) и разбиение множества X = {x1, , xn} ее аргументов на два непересекающиеся подмно- жества Y = {y1, , yr}, Z = {z1, , zn–r}. Разделением (декомпозицией) частичной бу- левой функции f (x) по двухблочному разбие- нию Y, Z множества аргументов X называется процесс представления f (x) в виде суперпози- ции (функционального разложения) f ( )x = ( , )f y z = ( ( ), )g h y z , (1) где g(h(y), z) – частичная булева функция, h(y) = = h1(y), , hp(y)) – частичная векторная функция. Сведение задачи декомпозиции к реше- нию логического уравнения Проиллюстрируем известное [5] сведение за- дачи многократной декомпозиции к решению логического уравнения на примере декомпо- зиции частичной функции f (x1, x2, x3, x4, x5) (табл. 1) по разбиению Y = {x1, x2, x3}, Z = {x4, x5} множества переменных X = {x1, x2, x3, x4, x5}. Этап 1. Найдем коэффициенты разложе- ния Шеннона частичной булевой функции f (x1, x2, x3, x4, x5) по подмножеству Y = {x1, x2, x3} и зададим их в табл. 2. Построим граф G (рис. 1) отношения несов- местимости на множестве векторов iy yV , ис- пользуя полученные коэффициенты. Например, в этом графе G имеется ребро между вершина- ми 000, 001, так как коэффициенты f 000 f 001 не мо- гут быть доопределены до одной функции – име- ется набор z = (00), на котором f 000(00) = 0, а f 001(00) = 1. Вершины 000, 010 не соединены реб- ром (являются несмежными), так как соответ- ствующие им коэффициенты f 000, f 010 могут быть доопределены до одной и той же функции, в ка- честве такой функции может быть функция f 000. Т а б л и ц а 1 x F Область значений 00000 00011 01000 01101 01110 0 0 0 0 0 0 fM 00001 00100 00110 00111 01001 1 1 1 1 1 1 fM 00010 00101 01010 01011 01100 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 - - - - - - - - - - - - - - - - - - - - - -  fM Т а б л и ц а 2 z = ),( 54 xx 000f 001f 010f 011f 100f 101f 110f 111f 00 0 1 0 - - - - - 01 1 - 1 0 - - - - 10 - 1 - 0 - - - - 11 0 1 - - - - - - Рис. 1. Граф G отношения несовместимости УСиМ, 2012, № 3 17 Минимальное число pmin промежуточных функций ( )ih y в многократном разложении (1) частичной функции f(x) определяется из соот- ношения  min 2log ( )p G , (2) где (G) – хроматическое число графа G, через  a  обозначено ближайшее сверху целое чис- ло, большее либо равное a. Если граф G не со- держит ребер (является пустым), то подмноже- ство Y является несущественным (pmin = 0) под- множеством аргументов функции f ( )x . При построении разложения (1) возникает во- прос о нетривиальности полученного решения. Утверждение 1. Условия p < r, n – r > log 2 p выделяют класс нетривиальных многократных разложений (1). При условии p  r в получившемся разло- жении нет уменьшения числа компонент век- тора y в сравнении с числом p компонент век- тора h(y). Так как число k всех возможных ко- эффициентов разложения Шеннона по под- множеству Y ограничено неравенством k  2 2n–r , а для существования разложения (1) необхо- димо не более 2 p различных дизъюнктивных членов [2], то 2 p  2 2n–r , откуда n – r > log 2 p . Далее под свойством разделимости функ- ции по заданному разбиению Y, Z множества ее аргументов будем понимать свойство функции иметь нетривиальное разложение вида (1). В рассматриваемом примере граф G являет- ся 3-хроматическим ((G)= 3), а минимальное число промежуточных функций равно двум:  2log χ( )G = 2 и 1 2( , )h h h . Этап 2. Составление логического уравне- ния для заданного числа p = 2 промежуточных функций. Закодируем неизолированные вер- шины булевыми переменными wi так, как дано в табл. 3. Т а б л и ц а 3 Решение 1 Решение 2 Вершина графа G Код вершины h1h2 h1h2 000 w1 w2 1- 01 001 w3 w4 00 11 010 w5 w6 10 0- 011 w7 w8 01 10 Запишем логическое уравнение, выражаю- щее условия существования решения – усло- вия существования частичной векторной функ- ции h = (h1, h2), принимающей ортогональные значения для каждой пары смежных вершин графа G [5]. Например, для пары 000, 001 смеж- ных вершин графа G значения функции будут ортогональными тогда и только тогда, когда логическое уравнение (w1  w2)  (w3  w4) = 1 будет иметь решение. Для того чтобы найти функцию h = (h1, h2), удовлетворяющую по- добным условиям по всем ребрам графа G, требуется решить логическое уравнение ((w1  w3)  (w2  w4))  ((w1  w7)   (w2  w8))  (w3  w5)  (w4  w6))   ((w3  w7)  (w4  w8))  ((w5  w7)   (w6  w8)) = 1, (3) составленное по всем ребрам графа G. Каждый конъюнктивный член уравнения может быть записан в виде КНФ, после чего уравнение (3) приобретает вид КНФ 1 2 3 4( )w w w w   & 2 41 3( )w w w w   & & 1 32 4( )w w w w   & 1 2 3 4( )w w w w   & & 1 2 7 8( )w w w w   & 2 81 7( )w w w w   & & 1 72 8( )w w w w   & 1 2 7 8( )w w w w   & & 3 4 5 6( )w w w w   & 4 63 5( )w w w w   & & 3 54 6( )w w w w   & 3 4 5 6( )w w w w   & & 3 4 7 8( )w w w w   & 4 83 7( )w w w w   & & 3 74 8( )w w w w   & 3 4 7 8( )w w w w   & & 5 6 7 8( )w w w w   & 6 85 7( )w w w w   & & 5 76 8( )w w w w   & 5 6 7 8( )w w w w   = 1.(4) Данное уравнение имеет решения, два из них приведены в табл. 3. На данном примере продемонстрировано, каким образом проверка существования разложения (1) с заданным чис- лом p промежуточных функций может быть сведена к составлению КНФ-уравнения вида (4) и нахождению его решений, т.е. к решению задачи о выполнимости КНФ. После того, как векторная функция ( )h y 1( ( ),..., ( ))ph y h y най- 18 УСиМ, 2012, № 3 дена, построение частичной функции ( ( ), )g h y z не вызывает затруднений и описано в [5]. В результате строится частичная булева функция ( ( ), )g h y z , реализующая частичную булеву функ- цию f ( )x . Если говорить более строго, равен- ство ( , )f y z = ( ( ), )g h y z – отношение реализа- ции частичных булевых функций. Пусть L – число дуг, инцидентных той вер- шине графа G, которая имеет максимальную степень. Если при составлении логического уравнения начальное значение числа p опреде- ляется по формуле  2logp L (5) и логическое уравнение составляется только один раз, то такая оценка разделимости (нахо- ждение минимального значения числа p) явля- ется приближенной. Далее будем называть ос- нованный на данной оценке алгоритм быст- рым алгоритмом оценки разделимости. Точный алгоритм оценки разделимости, т.е. нахождения минимального значения числа p, на- чинает свою работу, используя формулу (5), и если логическое уравнение имеет решение для такого значения p, то число p уменьшается на единицу. Для меньшего значения p составляется и решается новое логическое уравнение и т.д. Если для p уравнение имеет решение, а для p – 1 решений уравнения не существует, то p = pmin. Программная реализация. Выбор SAT-про- грамм Для написания программного комплекса «Де- композиция булевых функций» использовались следующие технологии разработки программ- ного обеспечения:  Java Development Kit 1.6 (JRE 1.6).  Библиотека для JUnit-тестов: junit-4.5.jar.  Язык сценариев для Batch файлов. При разработке использовалась интегриро- ванная среда разработки java-приложений NetBeans IDE 6.8. Выбор технологии осущест- влялся по принципу выгодного соотношения производительности языка программирования и скорости разработки. Язык программирова- ния Java дает хорошую возможность постро- ить удобную ООП-модель классов, на основе которой и были реализованы алгоритмы де- композиции. Для решения задачи выполнимости КНФ выбраны SAT-программы picosat и zСhaff [11]. Данные программы написаны на языке С++, находятся в свободном доступе и используют текстовый формат .cnf для представления вход- ных данных. В результате своей работы SAT- программы выдают либо ответ о том, что КНФ невыполнима (не имеет решения), либо ответ о том, что КНФ выполнима – в этом случае вы- дается хотя бы одно решение. Выбранные SAT- программы имеют очень высокие показатели производительности: программа picosat заняла второе место на соревнованиях SAT-программ в 2007 году, zСhaff – первое место на соревно- ваниях SAT-программ в 2004 году, способна обрабатывать КНФ, состоящие из 10 миллио- нов дизъюнктов [9]. Организация экспериментов Цель экспериментов – изучение свойства разделимости псевдослучайных частичных бу- левых функций и систем таких функций в зави- симости от степени определенности (неопреде- ленности) функций, мощности перекодируемо- го подмножества Y аргументов, числа m функ- ций в системе и других параметров. Для генерации псевдослучайной частичной булевой функции требуется указать число n ар- гументов функции и числа 0v = 0 fM , 1v = 1 fM . Получение псевдослучайной (далее – случай- ной) частичной функции осуществляется гене- рацией 0v + 1v различных псевдослучайных чи- сел (n–разрядных двоичных наборов), первые 0v из которых интерпретируется как область 0 fM нулевых значений функции, следующие 1v наборов – как область 1 fM единичных значе- ний функции. Выбор подмножества Y переко- дируемых аргументов заданной мощности r осуществлялся случайным образом. Проверка существования разложения (1) сводилась к по- строению логического уравнения в текстовом формате .cnf, являющемся исходным для про- грамм picosat, zChaff решения задачи «выпол- нимость КНФ». УСиМ, 2012, № 3 19 Например, уравнение (4) – исходные данные для программы picosat – записывается в виде p cnf 8 20 -1 -2 -3 -4 0 1 -2 3 -4 0 -1 2 -3 4 0 1 2 3 4 0 -1 -2 -7 -8 0 1 -2 7 -8 0 -1 2 -7 8 0 1 2 7 8 0 -3 -4 -5 -6 0 3 -4 5 -6 0 -3 4 -5 6 0 3 4 5 6 0 -3 -4 -7 -8 0 3 -4 7 -8 0 -3 4 -7 8 0 3 4 7 8 0 -5 -6 -7 -8 0 5 -6 7 -8 0 -5 2 -7 8 0 5 2 7 8 0 0 В такой записи каждая строка (кроме пер- вой и последней) задает один дизъюнкт, знак минус свидетельствует об инверсном литерале, например, строка -1 -2 -3 -4 0 соответствует первому дизъюнкту 1 2 3 4( )w w w w   в формуле (4). Символ 0 в последней строке указывает на окончание записи КНФ, в первой строке: число 8 – это число переменных КНФ, 20 – это число дизъюнктов в КНФ (4). Экспериментальные исследования Эксперимент 1. Как влияет степень неоп- ределенности на разделимость функции? В данном эксперименте генерировалось 100 псевдослучайных булевых функций для каждого значения параметра n (числа аргументов) и d (степени неопределенности), причем полагалось s1 = s 0. Для каждой из функций случайным обра- зом выбиралось r перекодируемых аргументов (множество Y), затем составлялись логические уравнения и находились минимальные числа pmin промежуточных функций в разложениях (1), осуществлялась проверка нетривиальности по- лученных разложений. Полученные по 100 функ- циям значения pmin усреднялись, подсчитыва- лась доля R (процент) функций, для которых получались нетривиальные разложения. Резуль- таты эксперимента 1 для быстрого алгоритма оценки разделимости представлены в табл. 4. Т а б л и ц а 4 n r d Среднее значение p Нетривиальные разложения, % 0,5 63 0 0,84 6 0 0,86 6 0 0,88 6 0 0,9 5,46 54 0,91 5,11 89 0,915 5,07 93 0,92 5,005 99 0,925 5 100 0,93 5 100 0,935 4,86 100 0,94 4,63 100 12 6 0,96 3,81 100 0,88 7 0 0,89 7 0 0,9 7 0 0,91 7 0 0,92 7 0 0,925 6,71 29 0,93 6,24 76 0,935 6,03 97 14 7 0,94 6 100 0,93 7 0 0,935 7 0 0,94 7 0 0,945 6,71 29 0,947 6,36 64 0,95 6,04 96 0,955 6,01 99 15 7 0,96 6 100 0,93 8 0 0,94 8 0 0,95 7,05 95 0,955 7,02 98 16 8 0,96 7 100 Анализируя результаты эксперимента 1, мож- но заметить, что разделимость функции нахо- дится в непосредственной зависимости от сте- пени неопределенности функции. Чем больше степень неопределенности d, тем больше веро- ятность, что для этой функции удастся постро- ить нетривиальное разложение и уменьшить чи- сло аргументов функций g, hi, входящих в раз- ложение (1) в сравнении с числом n аргументов декомпозируемой функции. С ростом числа пе- ременных возрастает вероятность разделения случайной частичной булевой функции при раз- биении множества аргументов «пополам»: так, 20 УСиМ, 2012, № 3 для функций от 14 переменных можно навер- няка получить нетривиальные разложения для частичных функций с 94% неопределенных зна- чений, для функций от 16 переменных – уже для функций с 96% неопределенных значений. Зависимость доли R функций, имеющих нетри- виальные разложения, от степени неопределен- ности d функций показана на рис. 2–4. На рис. 2 видно, что случайная функция, зависящая от 12 аргументов, степень неопределенности d кото- рой не превышает 0,88, будет неразделима или разделима, если степень неопределенности бу- дет больше 0,92, для случая перекодирования шести аргументов. Аналогичные скачкообраз- ные переходы от свойства «неразделимость» к свойству «разделимость» при увеличении сте- пени неопределенности для n = 14, r =7 и для n =15, r = 7 показаны на рис. 3 и 4 соответст- венно. Для значений параметров n = 12, r = 6 на рис. 5 показано уменьшение числа p проме- жуточных функций в разложении (1) при уве- личении степени неопределенности d. Анало- гичный график представлен на рис. 6 для n = 16, r = 8. 0 0,2 0,4 0,6 0,8 1 R d R d Рис. 2. Увеличение доли R разделимых функций при увеличе- нии степени неопределенности d; фиксированные параметры n = 12, r = 6 0 0,2 0,4 0,6 0,8 1 0,88 0,89 0,9 0,91 0,92 0,925 0,93 0,935 0,94 R d R d Рис. 3. Увеличение доли R разделимых функций при увеличе- нии степени неопределенности d; фиксированные параметры n = 14, r = 7 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 0,93 0,935 0,94 0,945 0,947 0,95 0,955 0,96 d RR d Рис. 4. Увеличение доли R разделимых функций при увеличе- нии степени неопределенности d; фиксированные параметры n = 15, r = 7 Для точного алгоритма оценки раздели- мости результаты эксперимента 1 представле- ны в табл. 5, 6. Аналогичные «скачки» перехо- да к свойству разделимости наблюдаются и в данном случае, когда ищется минимальное число промежуточных функций. p d Рис. 5. Зависимость числа p промежуточных функций h от d – степени неопределенности функции; фиксированные параметры n = 12, r = 6 p d Рис. 6. Зависимость числа p промежуточных функций h от d – степени неопределенности функции; фиксированные параметры n = 16, r = 8 Поясним результаты эксперимента 1, приве- денные в табл. 5, 6. Рассмотрим строку в табл. 5, выделенную жирным шрифтом: в данном случае декомпозируется 100 частичных функций от ше- сти переменных (n = 6) по случайно выбранным подмножествам Y, состоящим из трех перемен- ных, степень неопределенности всех таких функ- ций равна 0,6 (функции заданы на 16 наборах). УСиМ, 2012, № 3 21 Т а б л и ц а 5 n r d Число функций p = 0 p = 1 p = 2 p = 3 0 100 100\100 0,1 100 100\100 0,2 100 0\100 0\100 100\100 0,3 100 0\100 1\100 100\100 0,4 100 0\100 11\100 100\100 0,5 100 0\100 53\100 100\100 0,6 100 0\100 93\100 85\85 0,7 200 0\200 194\194 75\75 0,75 200 0\2 0\191 162\162 20\20 0,8 200 0\12 0\174 92\92 3\3 0,85 200 0\34 0\111 33\33 6 3 0,9 200 0\43 0\41 4\4 0,1 100 0\100 0\100 100\100 0,2 100 0\100 0\100 100\100 0,3 100 0\100 0\100 100\100 0,4 100 0\100 0\100 100\100 0,5 100 0\100 0\100 100\100 0,6 100 0\100 0\100 100\100 0,7 100 0\100 1\100 100\100 0,8 100 0\100 94\100 100\100 0,9 100 0\98 92\92 23\23 0,92 100 0\95 53\53 1\1 0,94 100 0\66 15\15 0,96 100 0\25 3\3 8 4 0,98 100 0\3 0,1 100 0\100 0\100 100\100 0,2 100 0\100 0\100 100\100 0,3 100 0\100 0\100 100\100 0,4 100 0\100 0\100 100\100 0,5 100 0\100 0\100 100\100 0,6 100 0\100 0\100 100\100 0,7 100 0\100 0\100 100\100 0,8 100 0\100 0\100 100\100 10 5 0,9 100 0\100 99\100 100\100 В столбце p = 1 приводится значение 0\100 – это означает, что нет ни одной функции (из ис- пытанных 100), для которой существует разде- ление (1) с одной (p = 1) промежуточной функ- цией. В столбце p = 2 приводится значение 93\100 – это означает, что 93 функции (из ис- пытанных 100 функций) имеют представление (1) с двумя (p = 2) промежуточными функциями. В столбце p = 3 приводится значение 85\85 – это означает, что все 85 функций (из испытан- ных 85 функций) имеют разделение (1) с тремя (p = 3) промежуточными функциями. В общем случае запись α \β для столбца p =  в табл. 5 и 6 означает, что испытано  функций и  из них имеют  промежуточных функций в представлении (1). Т а б л и ц а 6 n r d Число функций p = 1 p = 2 p = 3 0,1 100 0\100 0\100 100\100 0,2 100 0\100 0\100 100\100 0,3 100 0\100 0\100 100\100 0,4 100 0\100 0\100 100\100 0,5 100 0\100 0\100 100\100 0,6 100 0\100 0\100 100\100 0,7 100 0\100 0\100 100\100 0,8 100 0\100 0\100 100\100 0,9 100 0\100 0\100 100\100 0,91 100 0\100 0\100 100\100 12 6 0,96 100 0\100 99\100 100\100 0,1 100 0\100 0\100 100\100 0,2 100 0\100 0\100 100\100 0,3 100 0\100 0\100 100\100 0,4 100 0\100 0\100 100\100 0,5 100 0\100 0\100 100\100 0,6 100 0\100 0\100 100\100 0,7 100 0\100 0\100 100\100 0,8 100 0\100 0\100 100\100 0,9 100 0\100 0\100 100\100 0,94 25 0\25 0\25 25\25 0,95 25 0\25 0\25 25\25 14 7 0,97 25 0\25 18\25 25\25 0,1 25 0\25 0\25 25\25 0,2 25 0\25 0\25 25\25 0,3 25 0\25 0\25 25\25 0,4 25 0\25 0\25 25\25 0,5 25 0\25 0\25 25\25 0,6 25 0\25 0\25 25\25 0,7 25 0\25 0\25 25\25 0,8 25 0\25 0\25 25\25 16 8 0,9 25 0\25 0\25 25\25 Эксперимент 2. Как влияет мощность мно- жества Y на разделимость функции ? Для каждого значения параметров n = 14, d = 0,97, 1s = 0s генерировалось 15 псевдослу- чайных булевых функций, для каждой из них случайным образом выбиралось множество Y фиксированной мощности r (r = 7, 6, 5, 4, 3, 2) и предпринималась попытка построения раз- ложения (1) с помощью быстрого алгоритма. Подсчитывалось число функций, для которых существовало нетривиальное разложение. Ре- зультаты эксперимента 2, представленные в табл. 7, показывают, что для получения нетри- виальных разложений целесообразно прово- дить разбиение множества X на равномощные подмножества Y, Z. Результаты нахождения минимального зна- чения p (с помощью точного алгоритма) при 22 УСиМ, 2012, № 3 изменении мощности подмножества Y представ- лены в табл. 8. Поясним первую строку табл. 8: 12 (из 15) функций разделимы и имеют две про- межуточные функции 1( )h y , 2 ( )h y в представ- лении (1); три (из 15) функции имеют в пред- ставлении три промежуточные функции ( )ih y . Т а б л и ц а 7 Мощность множе- ства Y (r) Число функций, имеющих нетривиальное разложение (1) 7 15 6 15 5 14 4 4 3 0 2 1 Т а б л и ц а 8 Число функций, имеющих разложение (1) Мощность r мно- жества Y pmin = 2 pmin = 3 7 12 3 6 11 4 5 11 4 4 11 4 3 9 6 2 15 0 Эксперимент 3. Как влияет увеличение доли единичных значений на разделимость функции ? В данном эксперименте множества 1 fM , 0 fM имели различную мощность, однако сумма v0 + v1 мощностей множеств 1 fM , 0 fM оставалась не- изменной, т.е. s1, s0 имели различные значения, однако суммарное значение s = s1 + s 0 остава- лось неизменным. Усреднение осуществлялось по четырем функциям с одинаковыми пара- метрами n = 12, r = 6, s = 0.9. Параметр s1 уве- личивался от 0,5 до 0,98, в результате наблю- далось уменьшение (использовался быстрый алгоритм) числа p от p =5 до p = 4. Аналогич- но установлено, что увеличение доли нулевых значений функции при постоянном значении S также ведет к уменьшению числа p промежу- точных функций. Использование точного алгоритма провер- ки разделимости на 10 функциях (n = 12, r = 6) позволило получить следующие выводы: при увеличении параметра s1 от 0,5 до 0,89 значе- ние pmin было равным трем, в диапазоне значе- ний s1 от 0,9 до 0,99 значение pmin равнялось двум. Эксперимент 3 показал, что неравномер- ность значений s1, s0 ведет к большей вероят- ности разделения функции. Эксперимент 4. Как влияет число функций системы на разделимость? Для частичных векторных функций исследо- вано свойство разделимости в зависимости от увеличения числа m компонент декомпозируемой векторной функции ( )f x = 1( ( ),..., ( ).mf x f x Для векторной булевой функции ( )f x рассматрива- лась задача получения нетривиальных разло- жений ( )f x = ( , )f y z = ( ( ), )g h y z , (5) где 1( ) ( ( ),..., ( ))ph y h y h y . В эксперименте 4 были зафиксированы сле- дующие параметры: n = 12, r = 6, d = 0,985, s1 = s 0. Результат эксперимента представлен на рис. 7. Эксперимент показал, что при увеличе- нии числа m функций системы для разделимо- сти требуется большая степень неопределен- ности. На рис. 8 показана зависимость времени получения логического КНФ-уравнения при увеличении числа функций в системе. Очевид- но, увеличение числа функций системы ведет к увеличению времени получения логического уравнения, а именно это время занимает основ- ную долю времени декомпозиции, так как SAT- программы решают получаемые КНФ-уравне- ния очень быстро. Например, для n = 12, r = 6, d = 0,9 время построения графа G составляет 1,680 с, а время решения логического уравне- ния – 0,070 с, т.е. в 24 раза меньше. Для SAT- программ, решающих получаемые логические уравнения, большее значение имеет число пере- менных в логическом уравнении в сравнении с числом дизъюнктов в уравнениях. Это под- тверждается тем, что при уменьшении степени неопределенности время решения уравнения растет незначительно, хотя число дизъюнктов в этих случаях значительно увеличивается. Были проведены эксперименты с примера- ми систем функций, возникающими в практике промышленного проектирования. Системы функ- ций были заданы на 1000 наборах и характери- УСиМ, 2012, № 3 23 зовались следующим набором параметров: n = 17, r = 9, m = 60. Для таких примеров век- торных функций получение логического урав- нения и его решение происходит за практиче- ски приемлемое время. R m Рис. 7. Увеличение доли R нетривиально разделимых систем функций при увеличении числа m функций системы; фиксированные параметры n = 12, r = 6, d = 0,985 t m Рис. 8. Зависимость времени декомпозиции от числа m функ- ций в системе Заключение. Для случайных булевых функ- ций характерен скачкообразный (в узких гра- ницах) переход от неразделимости к разделимо- сти при увеличении степени неопределенности. Для получения нетривиальных разложений де- композицию лучше проводить по разбиению множества аргументов X декомпозируемой ча- стичной функции на равномощные блоки Y, Z. Эксперименты показали, что при увеличении числа аргументов декомпозируемых функций и увеличении степени неопределенности, число p промежуточных функций уменьшается. Основ- ное время для проверки разделимости функции занимает составление логического уравнения, известные SAT-программы решают полученные КНФ-уравнения чрезвычайно быстро. Резуль- таты экспериментов дополняют и уточняют из- вестные [2] экспери ментальные результаты по проверке декомпозиционных свойств псевдо- случайных булевых функций и систем, а также показывают практическую возможность приме- нения эффективных программ решения задачи о выполнимости КНФ не только для верифика- ции, но и для синтеза логических схем, осуществ- ляемого методами функционального разделения. 1. Sasao T. FPGA design by generalized functional de- composition // Representations of discrete functions. – Kluwer Academic Publishers, 1996. – P. 233–258. 2. Бибило П.Н. Декомпозиция булевых функций: об- зор // Проектирование устройств логического управ- ления. – М.: Наука, 1984. – С. 106–126. 3. Бибило П.Н., Енин С.В. Синтез комбинационных схем методами функциональной декомпозиции. – Минск: Наука и техника, 1987. – 189 с. 4. Поттосин Ю.В., Шестаков Е.А. Табличные методы декомпозиции систем полностью определенных бу- левых функций. – Минск: Беларус. навука, 2006. – 327 с. 5. Бибило П.Н. Декомпозиция булевых функций на основе решения логических уравнений. – Минск: Там же, 2009. – 211 с. 6. Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, 1981. – 416 c. 7. Брейтон Р.К., Хэчтел Г.Д., Санджованни-Винчен- телли А.Л. Синтез многоуровневых комбинацион- ных логических схем // ТИИЭР. – 1990. – Т. 78. – № 2. – С. 38 – 83. 8. Каммозев Н.Ф., Сычев А.Н. Спектральный метод декомпозиции булевых функций // Автоматика и вычислительная техника. – 1979. – № 2. – С. 54–58. 9. Lee R.-R., Jiang J.-H.R., Hung W.-L. Bi-decomposing large Boolean functions via interpolation and satisfi- ability solving // Design Automation: proceedings of the 45th annual conf., Anaheim, California, 8–13 Jun. 2008. – NY: ACM, 2008. – P. 636–641. 10. Kunz W., Marques-Silva J., Malik S. SAT and ATPG: Algorithms for Boolean Decision Problems // Logic synthesis and verification. – Kluwer Academic Publi- shers, 2002. – P. 309 – 341. 11. http://satcompetition.org 12. Goldberg E., Novikov Y. BerkMin: a Fast and Robust Sat-Solver // Proc. of Design, Automation and Test in Europe (DATE02), 4–8 March, 2002. – P. 142–149. Поступила 19.09.2011 Тел. для справок: +375 (17) 284-2084 (Минск) E-mail: bibilo@newman.bas-net.by © Т.В. Авлочинская, П.Н. Бибило, 2012  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

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

Репозитарії

Схожі ресурси