Числова теоретико-множинна інтерпретація полінома Жеґалкіна

Числова теоретико-множинна інтерпретація полінома Жеґалкіна

Рассмотрена численная теоретико-множественная интерпретация полинома Жегалкина и описан простой теоретико-множественный метод преобразования (совершенной) дизъюнктивной нормальной формы логической функции от n переменных в полином Жегалкина, и наоборот. Преимущества предложенного метода показаны на...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2013
Автор: Рицар, Б.Є.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2013
Назва видання:Управляющие системы и машины
Теми:
Новые методы в информатике
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/83125
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Числова теоретико-множинна інтерпретація полінома Жеґалкіна / Б.Є. Рицар // Управляющие системы и машины. — 2013. — № 1. — С. 11-26. — Бібліогр.: 11 назв. — укр, рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-83125
record_format dspace
spelling irk-123456789-831252015-06-16T03:43:14Z Числова теоретико-множинна інтерпретація полінома Жеґалкіна Рицар, Б.Є. Новые методы в информатике Рассмотрена численная теоретико-множественная интерпретация полинома Жегалкина и описан простой теоретико-множественный метод преобразования (совершенной) дизъюнктивной нормальной формы логической функции от n переменных в полином Жегалкина, и наоборот. Преимущества предложенного метода показаны на примерах. A numeric set-theoretical interpretation of polynomial Zhegalkin is considered and a simple set-theoretical transformation method of (perfect) – disjunctive normal form of the logic function of n variables in polynomial Zhegalkin and vice versa is described. The advantages of suggested of the suggested method are illustrated by examples. Розглянуто числову теоретико-множинну інтерпретацію полінома Жеґалкіна та описано простий теоретико-множинний метод перетворення (досконалої) диз’юнктивної нормальної форми логікової функції від n змінних у поліном Жеґалкіна, і навпаки. Переваги запропонованого методу показано на прикладах. 2013 Article Числова теоретико-множинна інтерпретація полінома Жеґалкіна / Б.Є. Рицар // Управляющие системы и машины. — 2013. — № 1. — С. 11-26. — Бібліогр.: 11 назв. — укр, рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/83125 519.718 uk Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
topic Новые методы в информатике
Новые методы в информатике
spellingShingle Новые методы в информатике
Новые методы в информатике
Рицар, Б.Є.
Числова теоретико-множинна інтерпретація полінома Жеґалкіна
Управляющие системы и машины
description Рассмотрена численная теоретико-множественная интерпретация полинома Жегалкина и описан простой теоретико-множественный метод преобразования (совершенной) дизъюнктивной нормальной формы логической функции от n переменных в полином Жегалкина, и наоборот. Преимущества предложенного метода показаны на примерах.
format Article
author Рицар, Б.Є.
author_facet Рицар, Б.Є.
author_sort Рицар, Б.Є.
title Числова теоретико-множинна інтерпретація полінома Жеґалкіна
title_short Числова теоретико-множинна інтерпретація полінома Жеґалкіна
title_full Числова теоретико-множинна інтерпретація полінома Жеґалкіна
title_fullStr Числова теоретико-множинна інтерпретація полінома Жеґалкіна
title_full_unstemmed Числова теоретико-множинна інтерпретація полінома Жеґалкіна
title_sort числова теоретико-множинна інтерпретація полінома жеґалкіна
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate 2013
topic_facet Новые методы в информатике
url http://dspace.nbuv.gov.ua/handle/123456789/83125
citation_txt Числова теоретико-множинна інтерпретація полінома Жеґалкіна / Б.Є. Рицар // Управляющие системы и машины. — 2013. — № 1. — С. 11-26. — Бібліогр.: 11 назв. — укр, рос.
series Управляющие системы и машины
work_keys_str_mv AT ricarbê čislovateoretikomnožinnaínterpretacíâpolínomažegalkína
first_indexed 2025-07-06T09:51:10Z
last_indexed 2025-07-06T09:51:10Z
_version_ 1836890687665078272
fulltext УСиМ, 2013, № 1 11 УДК 519.718 Б.Є. Рицар Числова теоретико-множинна інтерпретація полінома Жеґалкіна Рассмотрена численная теоретико-множественная интерпретация полинома Жегалкина и описан простой теоретико-множественный метод преобразования (совершенной) дизъюнктивной нормальной формы логической функции от n переменных в полином Жегал- кина, и наоборот. Преимущества предложенного метода показаны на примерах. A numeric set-theoretical interpretation of polynomial Zhegalkin is considered and a simple set-theoretical transformation method of (perfect) – disjunctive normal form of the logic function of n variables in polynomial Zhegalkin and vice versa is described. The advantages of suggested of the suggested method are illustrated by examples. Розглянуто числову теоретико-множинну інтерпретацію полінома Жеґалкіна та описано простий теоретико-множинний метод перетворення (досконалої) диз’юнктивної нормальної форми логікової функції від n змінних у поліном Жеґалкіна, і навпаки. Переваги запропонованого методу показано на прикладах. Вступ. У практиці логікового синтезу цифро- вих пристроїв (ЦП), окрім зображення логіко- вих функцій у диз’юнктивній нормальній фор- мі (ДНФ, Sum-Of-Product form – SOP), часто вживають поліномну нормальну форму (ПНФ, Exclusive-OR Sum-Of-Product form – ESOP), утворену двомісними операціями кон’юнкції (AND) і суми за mod2 (EXCLUSIVE OR) та кон- стантою 1. Останні складають поліномний ба- зис {&, , 1}, що визначає структуру дворів- невих схем логікових елементів AND-EXOR: на першому рівні – AND, на другому – EXOR. Ар- гументів на користь ЦП, побудованих з AND- EXOR, порівняно з традиційними AND-OR, чи- мало [1–5]: мають кращу тестувальну здатність, тобто їх легше тестувати та діагностувати, а для деяких спеціальних класів функцій, особливо си- метричних, необхідних для синтезу різних ариф- метичних пристроїв, детекторів помилок, кодо- перетворювачів та іншого, уможливлюють реа- лізацію ЦП з порівняно меншою кількістю ло- гікових елементів. Вираз функції f (x1, x2, , xn) у поліномній формі можна одержати безпосередньо з її до- сконалої ДНФ простою заміною символа опе- рації диз’юнкції () на символ операції суми за mod2 () на тій підставі, що мінтерми взаємно ортогональні. Утворена внаслідок такої заміни канонічна форма – це досконала ПНФ, яка то- тожно дорівнює досконалій ДНФ f. З доскона- лої ПНФ функції f за розкладом Ріда–Маллера (Reed–Muller expansion – RM-розклад) можна утворити ПНФ з кон'юнктермів довільних ран- гів r  {0, 1, , n), які матимуть змінні зі зна- ком або без знаку інверсії. Зокрема, якщо в кон'- юнктермах досконалої ПНФ потрібно усунути знак інверсії з і-ї змінної, то замість x i підстав- ляється вираз x i  xi 1, а якщо потрібно внес- ти знак інверсії в і-ту змінну, то замість xi під- ставляється вираз xi  x i 1. У кожному разі до кон'юнктермів r , утворених після розкрит- тя дужок, застосовують правило спрощення: r r  0 і r r r  r. Вираз ПНФ f, у якому всі змінні є без знаку інверсії, називають поліномом Жеґалкіна (Posi- tive Polarity Reed–Muller expression – PPRM-по- ліном). Нехай, наприклад, досконала ДНФ функції f  x 1x 2x 3  x 1x2x3  x1x2x 3. Щоб одержати полі- ном Жеґалкіна функції f, потрібно спочатку записати її досконалу ПНФ, а потім виконати RM-розклад за виразом x i  xi 1: f  x 1x 2x 3  x 1x2x3  x1x2x 3  x 1x 2x 3  x 1x2x3  x1x2x 3   (1 x1)(1 x2 )(1 x3 ) (1 x1)x2x3  x1x2(1 x3 )  . 1 32121321 32321323121123 xxxxxxxx xxxxxxxxxxxxxx   Після усунення пар однакових кон'юнктер- мів одержимо поліном Жеґалкіна f 1 x3  x2  x1  x1x3  x1x2x3 . Постановка задачі У практиці логікового синтезу ЦП часто ви- никає потреба виконувати взаємні перетворен- ня типу «(досконала) ДНФ  поліном Жеґал- кіна». Аналітичні методи перетворень, унаслі- 12 УСиМ, 2013, № 1 док їх специфіки, не мають прямого практич- ного застосування в комп’ютерних програмах автоматизованого проектування ЦП. З цією ме- тою застосовують методи, переважно таблич- ний на основі карт Карно [1, 6] та векторно-мат- ричний [4, 5, 7] – досить громіздкі й складні. Зокрема, щоб зреалізувати на комп’ютері вза- ємні перетворення між (досконалою) ДНФ і поліномом Жеґалкіна, у першому випадку по- трібно попередньо виконати спеціальні пере- творення, у другому – одержати Кронекерів до- буток над матрицями розмірності 2 n. Як показано в [8, 9], для комп’ютерної реа- лізації різних операцій і процедур над число- вими (двійковими і/або трійковими) кон’юнк- термами довільних рангів r  {0, 1, , n) логі- кових функцій, які можуть виникати в процесі логікового синтезу ЦП, досить простим і зруч- ним є теоретико-множинний підхід. У цій стат- ті покажемо, що, крім диз’юнктивної форми зо- браження функцій, такий підхід можна успіш- но застосовувати й до поліномних форм, зок- рема, до полінома Жеґалкіна. Основна частина Теоретико-множинне зображення логікової функції f (x1, x2, , xn) у поліномній формі (тоб- то ПНФ f), основою якої є логіковий базис {&, , 1}, називатимемо поліномною теорети- ко-множинною формою (ПТМФ) функції f. У загальному випадку ПТМФ f – це множина Y  {1 r1 ,2 r2 ,...,k rk } , (1) де 1 r1 ,2 r2 ,...,k rk – взаємно ортогональні числові кон’юнктерми рангів ri  {0, 1, 2, , n); верхній індекс  символізує поліномне зображення функції f, а знаки коми між кон’юнктермами множини Y  відображають операцію суми за mod 2 у теоретико-множинному форматі. ПТМФ Y  (1) називатимемо досконалою ПТМФ Y  , якщо її елементами є числові кон’- юнктерми n-рангу, тобто числові (двійкові чи десяткові) мінтерми m1, m2, , mk функції f: Y  {m1, m2 ,..., mk } . Отже, досконала ПТМФ Y  функції f – це те- оретико-множинний відповідник її досконалої ПНФ. Водночас досконала ПТМФ Y  тотожно дорівнює досконалій ТМФ Y 1 = {m1, m2, , mk} 1, яка є теоретико-множинним відповідником до- сконалої ДНФ f [8]. Отже, щоб від досконалої ТМФ Y 1 перейти до досконалої ПТМФ Y  до- сить верхній індекс «1» замінити на символ , а в разі зворотного переходу –  на одиницю. Натомість, щоб з досконалої ДНФ f одержати досконалу ПТМФ Y  , потрібно вирази мінтер- мів замінити на їх числові відповідники – двій- кові n-позиційні числа, символи диз'юнкції  за- мінити на коми та скласти з цих чисел множи- ну Y  ; в разі зворотного переходу виконати за- міни у зворотному порядку. Отже, якщо доско- нала ДНФ функції f  x 1x 2x 3  x 1x2x3  x1x2x 3, то її досконала ТМФ Y 1 = {(000), (011), (110)}1 = = {0, 3, 6}1 і досконала ПТМФ {(000), (011),Y  (110)} {0,3,6}  . Вироджену функцію f (x1, x2, , xn) = 1 ці фор- ми відображає кон'юнктерм нульового рангу, а саме: у двійковому форматі 1 1{( )}Y    = 1 і Y  {(  )}  1, а в десятковому – Y 1 {(0,1,...,2n 1)}1  E2 n і .)}12,...,1,0{( 2 nnY E  Відповідно f (x1, x2, , xn) = 0 відображає доско- нала ТМФ Y 1  і досконала ПТМФ Y  . Теоретико-множинним методом взаємне перетворення ПНФ f  ПТМФ Y  виконуєть- ся за правилом, аналогічним правилу взаємно- го перетворення ДНФ f  ТМФ Y 1 [8]: xi  (1)i , x i  (0)i , відсутня xi  ()i , знак   (,) . (2) Наприклад, ПНФ ,),,( 33121321 xxxxxxxxf  а її ПТМФ Y  {(10),(11),( 1)} . У разі необхідності одержати з ПНФ f доско- налу ПНФ f, а звідти – досконалу ДНФ f, по- трібно у кон’юнктерми ПНФ f, що мають ранг r < n, внести вираз (xi  x i ) , де xi – відсутня змін- на. Тоді досконала ПНФ f одержується після роз- криття дужок та усунення пар однакових мін- термів. На прикладі розглянутої вище функції така процедура виконується у такий спосіб:   322113221 332133121 ))(()( )( xxxxxxxxx xxxxxxxxxf УСиМ, 2013, № 1 13   321321321321 321321321321 xxxxxxxxxxxx xxxxxxxxxxxx .321321321321 321321321321 xxxxxxxxxxxx xxxxxxxxxxxx   . Числовим теоретико-множинним методом перехід «ПТМФ Y   досконала ПТМФ Y   досконала ТМФ Y 1» зреалізувати простіше, що ілюструється прикладом, де задля наочності застосовано десяткові числа: .}5,4,3,1{}5,4,3,1{)}7,5,3,1( ),7,5(),5,4{()}1(),11(),10{( 1   Y У статті розглянуто числову теоретико-мно- жинну інтерпретацію полінома Жеґалкіна та ме- тод взаємного перетворення з одного формату зображення функції f в інший. У загальному випадку поліном Жеґалкіна функції f (x1, x2, , xn) – це логіковий вираз, який зображає суму за mod2 скінченної кілько- сті кон’юнктермів рангів ri = 0, 1, 2, , n, змінні яких не мають знаку інверсії: ......... ...),...,,( 31132112 2211011   xxcxxcxc xcxccxxxf nn nn 1,2,..., 1 2 2 1 1,2,..., 1 2 0 ... ... ... , n k k n n I I I c x x x c x x x c          (3) де cI  {0, 1} – коефіцієнти кон’юнктермів I, I  {0, 1, , 2 n – 1}; причому 0 = 1. Покажемо, що між значеннями коефіцієн- тів cI (3) і значеннями коефіцієнтів fI  {0, 1}, I  0,1,...,2n 1, мінтермів mI (на I-му наборі) досконалої ДНФ або ПНФ функції f (оскільки II I II I mfmf nn       12 0 12 0 ) існує певна відповідність. На прикладі довільної функції від двох змін- них поліном Жеґалкіна можна одержати так:   213212211210 3322110021 ),( xxfxxfxxfxxf mfmfmfmfxxf   2132122112 10213212211210 )1()1()1( )1( xxfxxfxxfx xfxxfxxfxxfxxf 0 0 1 2 0 2 1( ) ( )f f f x f f x      0 1 2 3 1 2( )f f f f x x     Zh  Zh c0  c1x2  c2x1  c3x1x2 , (4) де оператор  Zh символізує процедуру перехо- ду з досконалої ДНФ/ПНФ до полінома Жеґа- лкіна, коефіцієнти ci якого зв’язані з коефі- цієнтами fi i = 0, 1, 2, 3, співвідношеннями: c0  f0, c1  f0  f1, c2  f0  f2 , c3  f0  f1  f2  f3. (5) Співвідношення (5) між значеннями коефі- цієнтів fi досконалих ДНФ чи ПНФ та значен- нями коефіцієнтів ci, i = 0, 1, 2, 3, полінома Же- ґалкіна функції f (x1, x2) ілюструє табл. 1. Т а б л и ц я 1 Тепер розглянемо зворотний перехід від по- лінома Жеґалкіна до досконалої ПНФ (ДНФ) для функції від двох змінних: f ( x1, x2 )  c0  c1x2  c2x1  c3x1x2 =   213210 1202100 )( )()( xxffff xffxfff , )( )()1( 33221100 2132112 212121120 mfmfmfmf xxfxxxf xxxfxxxxf    де m0 1 x2  x1  x1x2  x 1x 2 m1  x2  x1x2  x 1x2 m2  x1  x1x2  x1x 2 m3  x1x2 . Отже, f ( x1, x2 )  f0x 1x 2  f1x 1x2  f2x1x 2  f3x1x2 . З одержаної досконалої ПНФ повернутися до полінома Жеґалкіна можна так:   33221100 123122121120 mfmfmfmf xxfxxfxxfxxf   33210 22011000 )( )()( mcccc mccmccmc N f0 f1 f2 f 3 c0 c1 c2 c3 8 9 10 11 12 13 14 15 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 N f0 f1 f2 f3 c0 c1 c2 c3 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 14 УСиМ, 2013, № 1   33322311 32100 )()( )( mcmmcmmc mmmmc  c0 p0  c1 p1  c2 p2  c3 p3, де 121212121 32100   xxxxxxxx mmmmp p1  m1 m3  x 1x2  x1x2  x2 p2  m2 m3  x1x 2  x1x2  x1 p3  m3  x1x2. Отже, f (x1, x2 )  c0  c1x2  c2x1  c3x1x2 , що відповідає (4). Для функції f (x1, x2, x3 ) поліном Жеґалкіна матиме такий вигляд: , ),,( 321721631514 32322310321 xxxcxxcxxcxc xxcxcxccxxxf   (6) де c0  f0, c1  f0  f1, c2  f0  f2 , c3  f0  f1  f2  f3, c4  f0  f4 , c5  f0  f1  f4  f5 , c6  f0  f2  f4  f6 , c7  f0  f1  f2  f3  f4  f5  f6  f7 . Зворотний перехід від полінома Жеґалкіна до досконалої ПНФ (ДНФ) через заміну ci  fi у цьому випадку також засвідчуватиме повну від- повідність і взаємозамінність коефіцієнтів fi і ci . Щоб довести справедливість твердження про взаємозамінність коефіцієнтів fi і ci для довіль- ної функції f (x1, x2, , xn), упорядкуємо між ни- ми співвідношення у вигляді матричних рів- нянь для n = 1, 2. Зокрема, якщо для f (x) маємо f0  c0, f1  c0  c1, то в матричному зображенні цю систему мож- на записати у вигляді рівняння або в більш компактній формі: f0 f1       1 0 1 1       c0 c1       або F 1  A1C 1. (7) Справді, взаємозамінність коефіцієнтів fi  ci матиме місце, оскільки у поліномному форматі добуток матриці 1A самої на себе, який позна- чимо як 2 1 1 1A A A , дорівнює одиничній матри- ці E2 другого порядку: . 10 01 11011111 10011011 11 01 11 01 2 2 1 EA                            Тоді, перемноживши ліву і праву частини рівності (7) на A1, одержимо C 1  A1F 1. Для n = 2, беручи за основу вираз (5), одер- жимо (пунктирними лініями виділено блоки для n = 1): f0 f1 f2 f3              1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1             c0 c1 c2 c3              A1 0 A1 A1      C2 або F 2  A2C 2 , (8) де        00 00 0 – нульова матриця другого порядку. За аналогічною процедурою одержимо ,42 2 2 2 2 11 2 1 2 1 111 2 1 11 1 11 12 2 E E E AAAA AAAA AA A AA A A                             0 0 0 000 00 де E4  1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1             – одинична матриця по- рядку 22. Отже, на підставі цього та (8) для n = 2 справедливо записати рівність C 2  A2F 2 . Для доведення справедливості твердження про взаємозамінність коефіцієнтів fi і ci для довільного n застосуємо метод математичної індукції. Для n = 1, 2, як бачимо, це твердження справджується. Нехай для n1 справедлива рівність 1 2 1 2nnA E   . Тоді 1 1 1     n n n FAC , де           22 2 1 nn n n AA A A 0 . УСиМ, 2013, № 1 15 Оскільки для n                                    12 1 0 11 1 12 1 0 ...... nn c c c AA A f f f nn n 0 або F n  AnC n, (9) 1 12 1 1 1 1 а n n n n n n n A A A A A A A                    0 0 1 1 2 1 1 1 1 2 2 2 2 2 1 1 1 1 2 , n n n n n n n n n n n EA A A A E EA A A A                            00 0 0 00 тобто An 2  E 2n , то на підставі цього та (9) спра- ведливо записати рівність C n  AnF n. (10) Взаємозамінність коефіцієнтів fi і ci (10) дає підставу твердити про взаємозамінність мінте- рмів досконалих форм (ПНФ, ДНФ, ТМФ) та кон’юнктермів полінома Жеґалкіна, яку можна використати для числової теоретико-множинної інтерпретації полінома Жеґалкіна. Поліном Жеґалкіна функції ),...,,( 21 nxxxf у теоретико-множинній формі зображення нази- ватимемо теоретико-множинною формою по- лінома Жеґалкіна – ТМФЖ Y  . Зазначимо, що на відміну від трійкових кон’юнктермів ПТМФ Y  кон’юнктерми ТМФЖ Y  матимуть значення позицій {1,}. При цьому, ТМФЖ Y  виро- дженної функції f (x1,x2,...,xn) 1 не відрізняєть- ся від досконалої ПТМФ Y  : у двійковому фо- рматі маємо   )}12,...,1,0{( nY 2 nE , у десятко- вому форматі – {( )}Y    1 . Це легко по- казати, якщо кон’юнктерми полінома Жеґалкі- на замінити на їх числові відповідники за пра- вилом (2) та усунути в утвореній множині пари однакових чисел. Отже, якщо в (4) 0 1f f  2 3 1f f   , то f ( x1, x2 )  1. Тоді у двійковому форматі матимемо x1x2  x2  x1 1 x1x2  x2  x1x2  x1  x1x2 Zh {(11), ( 1), (1 ), ( ), (11), ( 1), (11), (1 ), (11)} {( )} , Zh             відповідно у десятковому форматі – ,)}3,2,1,0{()}3(),3,2(),3(),3,1( ),3(),3,2,1,0(),3,2(),3,1(),3{(    Zh де  Zh – оператор переходу до ТМФЖ Y  фун- кції f. Якщо f0  f1  f2  f3  0, то f ( x1, x2 )  0 , а оскільки c0  c1  c2  c3  0, то ТМФЖ Y   . Числову теоретико-множинну інтерпретацію полінома Жеґалкіна (для невироджених випад- ків) розглянемо на прикладі функції f ( x1, x2 ) . Відповідність між коефіцієнтами fi і ci про- ілюструємо на картах Карно (рис. 1), де а і б – карти для fi і їх мінтермів mi ДНФ/ПНФ, а в і г – карти для ci і їх кон’юнктермів полінома Жеґалкіна. f 0 f1 f 2 f 3 x 1 x 2 x 1 x2 x1 x 2 x1 x2  c0 c1 c2 c3 1 x2 x1 x1 x2   Zh а б в г Рис. 1 Карти а і б та в і г взаємно зв'язані відповід- ністю клітинок. Їх об'єднаємо попарно та утво- римо числові карти (рис. 2), що відображають відповідність f i  Zh ci : ліворуч – для двійкових індексів (00), (01), (10), (11) коефіцієнтів f i , праворуч – для десяткових індексів (0), (1), (2), (3) коефіцієнтів ci . 00 01 10 11 0 1 2 3  Zh Рис. 2 Відповідність ТМФ (ПТМФ)  Zh ТМФЖ ви- значатимемо так. На числових картах (див. рис. 2) чорним кружечком () виділемо клітинки, но- мери яких відповідають значенням індексів ко- ефіцієнтів f i = 1 і с i = 1. З табл. 1 для заданих f i  {0, 1} визначимо значення с i, записуючи від- повідний вираз мінтерма ДНФ і полінома Же- ґалкіна. Зчитувані з карти коефіцієнтів с i числа (з контурів – множини чисел) – це шукані чис- лові кон’юнктерми ТМФЖ Y  функції f (x1, x2). Нехай f0 1, f1  f2  f3  0 ; це мінтерм m0  x 1x 2 {(00)}1. 16 УСиМ, 2013, № 1 Тоді c0  c1  c2  c3 1, що відповідає полі- ному  Zh 1 x2  x1  x1x2. Відповідно ТМФЖ {(0,1,2,3)} {( )}Y     . f1 1, f0  f2  f3  0 ; m1  x 1x2 {(01)}1; c1  c3 1, c0  c2  0, тобто  Zh x2  x1x2; Y  {(1,3)} {(1)} . f2 1, f0  f1  f3  0 ; m2  x1x 2 {(10)}1; c2  c3 1, c0  c1  0, тобто  Zh x1  x1x2; Y  {(2,3)} {(1)} . f3 1, f0  f1  f2  0 ; m3  x1x2 {(11)}1; c3 1, c0  c1  c2  0, тобто  Zh x1x2 ; Y  {(3)} {(11)} . У табл. 2 відображено для f (x1, x2 ) відповід- ність між диз'юнктивним і поліномним подан- нями як в аналітичному, так і в теоретико-мно- жинному форматах. У стовпці маска розміщено маски літералів ( l {x , x} – для аналітичного формату, l {0,1} – для числового формату), які формують кон’юнктерми і їх ранги r для певних ДНФ/ПНФ і ТМФ/ПТМФ, а саме: маска {ll} формує кон’юнктерми другого рангу; {l} і {l} – першого рангу; {} – нульового рангу. У стовпцях Аналітичний формат містяться вирази кон'юнктермів ДНФ/ПНФ і полінома Жеґалкіна, а у стовпцях Теоретико-множин- ний формат – їх двійкові (або трійкові) та деся- ткові відповідники для ТМФ/ПТМФ і ТМФЖ. Т а б л и ц я 2 Аналітичний формат Теоретико-множинний формат Мас- ка ДНФ/ПНФ Поліном Ж. ТМФ/ПТМФ ТМФЖ {ll} x 1x 2 x 1x2 x1x 2 x1x2 1x2x1 x1x2 x2x1x2 x1x1x2 x1x2 (00) (01) (10) (11) (0) (1) (2) (3) (– –) (–1) (1–) (11) (0,1,2,3) (1,3) (2,3) (3) {l –} x 1 x1 1x1 x1 (0–) (1–) (0,1) (2,3) (– –), (–1) (1–), (11) (0,2) (2) {– l} x 2 x2 1x2 x2 (–0) (–1) (0,2) (1,3) (– –), (1–) (–1), (11) (0,1) (1) {– –} 1 1 (– –) (0,1,2,3) (– –), (–1), (1–), (11) (0) Табл. 3 ілюструє аналогічну відповідність для f (x1, x2, x3), де маски літералів формують кон’юнктерми різних рангів r так: {lll} – r  3; {ll}, {l  l}, {ll} – r  2; {l  }, {l}, {  l} – r 1; {  } – r  0. Взаємно однозначна відповідність між роз- глянутими формами, яка відображена у табл. 2 і 3, зберігатиметься для довільної функції від n змінних. У табл. 2 і 3 подвійною лінією відокремлено множини елементів досконалих форм обох фо- рматів для масок {ll} і {lll}. Так зазначено, що елементи табл. 2 і 3 у стовпцях ДНФ/ПНФ і ТМФ/ПТМФ для решти масок утворено опе- рацією склеювання (у загальному випадку для ДНФ – це вираз 1 1 1r r r i ix x       , де  r1xi  1 r і  r1x i  2 r – сусідні кон’юнктерми r-рангу). По- ліноми Жеґалкіна для таких масок утворюва- тимуться операцією суми за mod 2 та процеду- рою усунення пар однакових кон’юнктермів. Наприклад, у табл. 2 для маски {l} {0}, якій відповідає вираз x 1x 2 x 1x2 x 1, одержимо по- ліном Жеґалкіна 2 1 1 2 2 1 2(1 ) ( )x x x x x x x      = 1  x1. Числовим теоретико-множинним методом перетворення типу «досконала ДНФ  полі- ном Жеґалкіна» виконується за схемою: досконала ДНФ f  досконала ТМФ Y 1  Zh  Zh ТМФЖ Y   поліном Жеґалкіна.  Zh  Zh  Zh  Zh УСиМ, 2013, № 1 17 Схема зворотного перетворення «поліном Жеґалкіна  досконала ТМФ (ДНФ)» має та- кий вигляд: поліном Жеґалкіна  ТМФЖ Y   досконала ТМФ Y 1  досконала ДНФ f. У розглянутих схемах взаємні перетворення «досконала ТМФ Y 1  ТМФЖ Y » виконують- ся заміною значень i-х позицій їх кон'юнктермів за правилом, яке ґрунтується на правилі (2): (0)i  ()i; (1)i  (1)i. (11) Над утвореною ТМФЖ Y  далі викону- ється процедура спрощення, яка реалізується усуненням пар однакових чисел. Після цього, щоб одержати поліном Жеґалкіна, потрібно i-ті позиції двійкових кон’юнктермів спро- щеної ТМФЖ Y  замінити на літерали полі- нома за правилом, яке буде справедливе та- кож для зворотного перетворення «поліном Жеґалкіна  ТМФЖ Y »: (0)i  відсутня xi ; (1)i  xi . (12) Зазначимо, перехід ТМФЖ Y   досконала ТМФ Y 1 однозначний – двійкові кон’юнктерми спрощеної ТМФЖ Y  переписуються без змін, оскільки, як зазначено раніше, ці форми тотожні. Отже, за описаною раніше схемою перехід від досконалої ДНФ f до ТМФЖ Y  для роз- глянутого прикладу (п’ятий зверху рядок табл. 2) виконуватиметься так: x 1x 2 x 1x2 {(00),(01)}1 Zh {(),(1)} або  Zh {(0,1,2,3),(1,3)} {(0,2)} . Зокрема, для виродженої функції f ( x1, x2 )  1 (останній рядок табл. 2) поліном Жеґалкіна до- рівнює одиниці: Т а б л и ц я 3 Аналітичний формат Теоретико-множинний формат Маска ДНФ/ ПНФ Поліном Жеґалкіна ТМФ/ПТМФ ТМФЖ {lll} x 1x 2x 3 x 1x 2x3 x 1x2x 3 x 1x2x3 x1x 2x 3 x1x 2x3 x1x2x 3 x1x2x3 1 x3  x2 x 2x3  x1  x1x3  x1x2  x1x2x3 x3 x 2x3  x1x3  x1x2x3 x2 x 2x3  x1x2  x1x2x3 x 2x3  x1x2x3 x1  x1x3  x1x2  x1x2x3 x1x3  x1x2x3 x1x2  x1x2x3 x1x2x3 (000) (001) (010) (011) (100) (101) (110) (111) (0) (1) (2) (3) (4) (5) (6) (7) (– – –) (– –1) (–1–) (–11) (1– –) (1–1) (11–) (111) (0,1,2,3,4,5,6,7) (1,3,5,7) (2,3,6,7) (3,7) (4,5,6,7) (5,7) (6,7) (7) {ll–} x 1x 2 x 1x2 x1x 2 x1x2 1 x2  x1  x1x2 x2  x1x2 x1  x1x2 x1x2 (00–) (01–) (10–) (11–) (0,1) (2,3) (4,5) (6,7) (– – –), (– –1) (–1–), (–11) (1– –), (1–1) (11–), (111) (0,2,4,6) (2,6) (4,6) (6) {l–l} x 1x 3 x 1x3 x1x 3 x1x3 1 x3  x1  x1x3 x3  x1x3 x1  x1x3 x1x3 (0–0) (0–1) (1–0) (1–1) (0,2) (1,3) (4,6) (5,7) (– – –), (– 1–) (– –1), (–11) (1– –), (11–) (1–1), (111) (0,1,4,5) (1,5) (4,5) (5) {–ll} x 2x 3 x 2x3 x2x 3 x2x3 1 x3  x2  x2x3 x3  x2x3 x2  x2x3 x2x3 (–00) (–01) (–10) (–11) (0,4) (1,5) (2,6) (3,7) (– – –), (1– –) (– –1), (1–1) (–1–), (11–) (–11), (111) (0,1,2,3) (1,3) (2,3) (3) {l– –} x 1 x1 1 x1 x1 (0– –) (1– –) (0,1,2,3) (4,5,6,7) (– – –), (– –1), (–1–), (–11) (1– –), (1–1), (11–), (111) (0,4) (4) {–l–} x 2 x2 1 x2 x2 (–0–) (–1–) (0,1,4,5) (2,3,6,7) (– – –), (– –1), (1– –), (1–1) (–1–), (–11), (11–), (111) (0,2) (2) {– –l} x 3 x3 1 x3 x3 (– –0) (– –1) (0,2,4,6) (1,3,5,7) (– – –), (–1–), (1– –), (11–) (– –1), (–11), (1–1), (111) (0,1) (1) {– – –} 1 1 (– – –) (0,1,2,3,4,5,6,7) (– – –), (– –1), (–1–), (–11), (1– –), (1–1), (11–), (111) (0) 18 УСиМ, 2013, № 1 .1)()( )1( 21211212 211221212121   xxxxxxxx xxxxxxxxxxxx У теоретико-множинному форматі – це чис- ловий кон’юнктерм нульового рангу, тобто ТМФ 1 1{( )}Y   , якому відповідає ТМФЖ Y  : 1 1{00,01,10,11} {( ), ( 1), (1 ), (11)} Zh Y       {(0,1,2,3),(1,3),(2,3),(3)} {(0)}. Перетворення «ДНФ/ТМФ  поліном Же- ґалкіна» виконується за аналогічною схемою за умови, якщо кон’юнктерми ДНФ/ТМФ вза- ємно ортогональні. Останні можна одержати або процедурою ортогоналізації [5, 8] або пе- ретворенням заданої ДНФ/ТМФ у досконалу форму. Ортогоналізацію кон’юнктермів, яка на- лежить до складних багатоваріантних проце- дур, є сенс застосовувати тоді, коли кількість неортогональних елементів невелика. Натомість другий шлях значно простіший, якщо в доскона- лу форму перетворювати ТМФ Y 1 [8, 9]. Цей ви- падок відображено схемою: ДНФ f  ТМФ Y 1 досконала ТМФ Y 1  Zh  Zh ТМФЖ Y   поліном Жеґалкіна. Перетворення «поліном Жеґалкіна  ДНФ f» виконується за зворотною схемою, яка на етапі переходу від досконалої ДНФ Y 1 до ТМФ Y 1 доповнюється процедурою мінімізації. Запропонований числовий теоретико-мно- жинний метод перетворення кон’юнктермів (до- сконалої) ДНФ чи ТМФ у поліном Жеґалкіна, і навпаки, покажемо на прикладах. Приклад 1. Числовим теоретико-множинним методом перетворити досконалу ДНФ функції f  x 1x 2x 3 x 1x 2x3 x1x 2x 3 x1x 2x3 x1x2x3 у полі- ном Жеґалкіна, і навпаки. Розв’язання. Перетворивши досконалу ДНФ f у досконалу ТМФ Y 1 та застосувавши правило (11), одержимо ТМФЖ Y  заданої функції: .)}111(),11(),1(),1(),{( )}111(),101(),100(),001(),000{( 11   Zh Zh Y Відтак, розписавши утворені кон’юнктерми ТМФЖ Y  на множини десяткових чисел і спростивши одержану множину усуненням пар однакових чисел, запишемо за правилом (12) поліном Жеґалкіна:    }7,2,0{)}7(),7,5(),7,6,5,4( ),7,5,3,1(),7,6,5,4,3,2,1,0{( = {(000),(010),(111)} 1 x2  x1x2x3 . Зворотне перетворення «поліном Жеґалкіна  досконала ДНФ» виконується так:     )}7(),7,6,3,2(),7,6,5,4,3,2,1,0{()}111(),1( ),{()}111(),010(),000{(1 3212 xxxx . )}111(),101(),100(),001(),000{(}7,5,4,1,0{ 321321321321321 1 xxxxxxxxxxxxxxx    Приклад 2. Числовим теоретико-множинним методом перетворити поліном Жеґалкіна фун- кції f (a,b,c,d )  a bc ad в еквівалентну ДНФ, і навпаки [4], с. 17. Розв’язання.     )}11(),11(),1{( )}1001(),0110(),1000{(adbca    }15,12,10,8,7,6{)}15,13,11,9( ),15,14,7,6(),15,14,13,12,11,10,9,8{( {(0110),(0111),(1000),(1010),(1100),(1111)}1. Одержану досконалу ТМФ Y 1 змінімізуємо, наприклад, методом розчеплення кон’юнктер- мів [10]: 1 1 011 011 100 101 110 111 01 0 01 1 10 0 10 0 11 0 11 1 0 10 0 11 1 00 1 10 1 00 1 11 110 111 000 010 100 111 {(011 ),(10 0),(1 00),( 111)} . S C C lll ll l Y l ll lll                                                 Звідси, еквівалентна ДНФ заданої функції f  a bc ab d  ac d  bcd . Зворотне перетворення «ДНФ f  поліном Жеґалкіна» виконується так:   1)}111(),001( ),010(),011{(bcddcadbabca   )}1111(),11(),11(),1(),111(),11{( )}1111(),1001(),1010(),1000(),0111(),0110{( 1 Zh Zh УСиМ, 2013, № 1 19 ),15,14,13,12,11,10,9,8(),15,7(),15,14,7,6{(   }9,8,6{)}15(),15,14,13,12(),15,14,11,10( ),11{()}1001(),1000(),0110{(   .)}11(),1( adbca   Приклад 3. Числовим теоретико-множин- ним методом перетворити ДНФ f (x1, x2, x3 ) =  x1 x2  x3 у поліном Жеґалкіна, і навпаки [11], с. 33. Розв’язання.   11 1 321 }7,6,5,4,3,2,1{)}7,5,3,1(),7,6,3,2(),7,6,5,4{( )}1(),1(),1{(xxx   )}111(),11(),11(),1(),11(),1(),1{( )}111(),110(),101(),100(),011(),010(),001{( 1 Zh Zh  x3  x2  x2x3  x1  x1x3  x1x2  x1x2x3 . З одержаного полінома Жеґалкіна задана ДНФ f утворюється так:   )}111(),11(),11(),1(),11(),1(),1{( 321213113223 xxxxxxxxxxxx    }7,6,5,4,3,2,1{)}7(),7,6(),7,5( ),7,6,5,4(),7,3(),7,6,3,2(),7,5,3,1{( 1{(001),(010),(011),(100),(101),(100),(111)} 00 01 01 10 10 11 11 0 1 0 0 0 1 1 0 1 1 1 0 1 1 01 10 11 00 01 10 11 S S c ll l l ll                                          C ll  l  l       {(01),(10),(11);(0 1),(1 0),(11)}1. З одержаної множини покриття на наступ- ному кроці розчеплення маємо: (01 ), (10 ), (11 ) 0 1 1 (1 ), ( 1 ), 1 0 1 S C l l                                 (0 1), (1 0), (1 1) 0 1 1 (1 ), ( 1). 1 0 1 S C l l                                Звідси мінімальна ТМФ ),1(),1{(1 Y 1)}1(  . Отже, f  x1 x2  x3. Висновки. З розглянутого матеріалу можна зробити висновок про те, що запропонована чи- слова теоретико-множинна інтерпретація полі- нома Жеґалкіна та оснований на цьому метод взаємного перетворення диз’юнктивного і полі- номного форматів зображення логікових функ- ції від n змінних, зручно використовувати для безпосередньої реалізації на комп'ютері без будь-яких проміжних процедур або перетворень. Метод можна також застосовувати до системи логікових функцій від п змінних. 1. Sasao T. Switching Theory for Logic Synthesis. – Klu- wer Acad. Publ., 1999. – 361 p. 2. Sasao T. Representation of logic functions using EXOR operations // IFIP WG.10.5 Workshop on Applications of the Reed-Muller Expansions in Circuit Design, Aug. 1995, Makuhari, Chiba, Japan. – P. 11–22. 3. Sasao T. Easily testable realizations for generalized Reed- Muller expressions // IEEE Trans. On Comp., June 1997. – 46, N 6. – P. 709–716. 4. Закревский А.Д., Топоров Н.Р. Полиномиальная реа- лизация частичных булевых функций и систем. – М.: УРСС, 2003. – 200 с. 5. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. – М.: Физматлит, 2007. – 592 с. 6. Almaini A.E.A., McKenzie L. Tabular techniques for generating Kronecker expentions // IEE Proc. Comp. Digit. Tech., July 1996. – 143, N 4. – P. 205–212. 7. Astola J.T., Stankovic R.S. Fundamentals of Switching Theory and Logic Design. – Springer, 2006. – P. 47–87. 8. Рицар Б.Є. Теоретико-множинні оптимізаційні ме- тоди логікового синтезу комбінаційних мереж. Дис.  д. техн. наук. – Львів, 2004. – 348 с. 9. Rytsar B., Romanowski P., Shvay A. Set-theoretical Constructions of Boolean Functions and theirs Appli- cations in Logic Synthesis // Fundamenta Informati- cae. – 2010. – 99, № 3. – P. 339–354. 10. Рицар Б.Є. Мінімізація бульових функцій методом розчеплення кон’юнктермів // УСиМ. – 1998. – № 3. – C. 14–22. 11. Steinbach B., Posthoff C. Logic Functions and Equations: Examples and Exercises. – Springer Science + Busi- ness Media B.V. – 2009. – 33 p. Поступила 05.10.2012 Тел. для справок: +38 0322 759-513 (Львoв) E-mail: bohdanrytsar@gmail.com © Б.Е. Рыцар, 2013  20 УСиМ, 2013, № 1 Б.Е. Рыцар Числовая теоретико-множественная интерпретация полинома Жегалкина Введение. В практике логического синтеза цифровых уст- ройств (ЦУ), кроме представления логических функций в дизъюнктивной нормальной форме – ДНФ (Sum-Of- Product form – SOP), часто применяют полиномиальную нормальную форму – ПНФ (Exclusive-OR Sum-Of-Product form – ESOP), образованную двухместными операциями конъюнкции (AND) и суммы по mod2 (EXCLUSIVE OR) и константой 1. Последние составляют полиномиальный базис {&, , 1}, определяющий структуру двухуровне- вых схем логических элементов AND-EXOR: на первом уровне – AND, на втором – EXOR. Аргументов в пользу ЦУ, построенных из AND-EXOR, в сравнении с традици- онными AND-OR, достаточно [1–5]: имеют лучшую тес- тируемую способность, т.е. их легче тестировать и диаг- ностировать, а для некоторых специальных классов функ- ций, особенно симметричных, необходимых для синтеза различных арифметических устройств, детекторов оши- бок, кодопреобразователей и других, допускают реали- зацию ЦУ со сравнительно меньшим числом логических элементов. Выражение функции f (x1, x2, , xn) в полиномиальной форме можно непосредственнно получить из ее совер- шенной ДНФ f простой заменой символа операции дизъ- юнкции () на символ операции суммы по mod 2 () на том основании, что минтермы функции f взаимно орто- гональны. Образованная вследствие такой замены кано- ническая форма – это совершенная ПНФ f, тождествен- но равная совершенной ДНФ f. Из совершенной ПНФ f по разложению Рида–Маллера (Reed–Muller expansion) – RM-разложению, можно образовать ПНФ из конъюнк- термов произвольных рангов r  {0, 1, , n}, которые будут иметь переменные со знаком или без знака инвер- сии. В частности, если в конъюнктермах совершенной ПНФ необходимо удалить знак инверсии из i-й перемен- ной, то вместо ix подставляется выражение 1,i ix x  а если необходимо внести знак инверсии в i-ю перемен- ную, то вместо ix подставляется выражение 1 ii xx . В каждом случае к конъюнктермам r, образованным по- сле раскрытия скобок, применяется правило упрощения: 0 rr и rrrr  . Выражение ПНФ f, в котором все переменные не име- ют знака инверсии, называют полиномом Жегалкина (Po- sitive Polarity Reed–Muller expression – PPRM-полином). Пусть, например, совершенная ДНФ функции 321321321 xxxxxxxxxf  . Чтобы получить полином Же- галкина этой функции, необходимо при помощи выра- жения 1 ii xx выполнить RM-разложение:  321321321321321321 xxxxxxxxxxxxxxxxxxf 1 2 3 1 2 3 1 2 3(1 )(1 )(1 ) (1 ) (1 )x x x x x x x x x         3 2 1 1 2 1 3 2 31 x x x x x x x x x        1 2 3 2 3 1 2 3 1 2 1 2 3.x x x x x x x x x x x x x     После удаления пар одинаковых конъюнктермов по- лучим полином Жегалкина 321311231 xxxxxxxxf  . Постановка задачи В практике логического синтеза ЦУ часто возникает необходимость взаимных преобразований типа «(совер- шенная) ДНФ  ПНФ». Аналитические методы преоб- разования, в силу их специфики, не имеют прямого прак- тического применения в компъютерных программах ав- томатизированного проектирования ЦУ. С этой целью ис- пользуют методы, преимущественно табличный на основе карт Карно [1, 6] и векторно-матричный [4, 5, 7], доволь- но громоздкие и сложные. В частности, для реализации на компьютере взаимных преобразований между (совершен- ной) ДНФ и полиномом Жегалкина, в первом случае требу- ется выполнение предварительного специального преобра- зования, во втором – получение кронекерского произведе- ния матриц размерности 2n. Как показано в [8, 9], для компьютерной реализации разных операций и процедур над числовыми (двоичны- ми и/или троичными) конъюнктермами произвольных рангов r  {0, 1, , n} логических функций, которые могут возникать в процессе логического синтеза ЦУ, довольно прост и удобен теоретико-множественный подход. В дан- ной статье покажем, что, кроме дизъюнктивной формы представления функций, такой подход можно успешно применять и к полиномиальным формам, в частности, к полиному Жегалкина. Основная часть Теоретико-множественное представление логической функции f (x1, x2, , xn) в полиномиальной форме (ПНФ f), основа которой – логический базис {&, , 1}, будем на- зывать полиномиальной теоретико-множественной фор- мой (ПТМФ) функции f. В общем случае ПТМФ f – это множество   },...,,{ 21 21 kr k rrY , (1) где kr k rr  ,...,, 21 21 – взаимно ортогональные числовые конъюнктермы рангов ri  {0, 1, 2, , n}; верхний индекс  символизирует полиномиальное представление функ- ции f, а запятые между конъюнктермами (1) представ- ляют операцию суммы по mod 2 в теоретико-множествен- ном формате. ПТМФ Y (1) будем называть совершенной ПТМФ Y , если ее элементы – числовые конъюнктермы n-ранга, т.е. числовые (двоичные либо десятичные) минтермы m1, m2, , mk функции f:   },...,,{ 21 kmmmY . Следовательно, совершенная ПТМФ Y функции f – это теоретико-множественный представитель ее совер- шенной ПНФ. В то же время совершенная ПТМФ Y  то- УСиМ, 2013, № 1 21 ждественно равна совершенной ТМФY1 = {m1,m2,,mk} 1, ко- торая есть теоретико-множественным представителем совершенной ДНФ f [8]. Таким образом, чтобы от совер- шенной ТМФ !Y перейти к совершенной ПТМФ Y  доста- точно верхний индекс 1 заменить на символ , а в случае обратного перехода –  на единицу. При этом, чтобы из совершенной ДНФ f получить совершенную ПТМФ Y , необходимо выражения минтермов заменить на их чи- словое представление – двоичные n-разрядные числа, сим- волы дизъюнкции  заменить на запятые и сложить из этих чисел множество Y , а в случае обратного перехода выполнить замены в обратном порядке. Следовательно, ес- ли совершенная ДНФ функции  321 xxxf 1 2 3x x x  1 2 3x x x , то ее совершенная ТМФ ),000{(1 Y (011), 1 1(110)} {0,3,6} и совершенная ПТМФ Y {(000), (011), (110)} {0,3,6}  . Вырожденную функцию f (x1, x2, , xn) = 1 эти фор- мы представляет конъюнктерм нулевого ранга, а именно: в двоичном формате 1 11 )}{(Y и {( )}Y    = 1, а в десятичном – nnY 2 11 )}12,...,1,0{( E и Y 2{(0,1, ..., 2 1)}n n  E . Соответственно, f (x1, x2, , xn) = 0 представляет совершенная ТМФ Y 1 =  и совершенная ПТМФ Y  = . Теоретико-множественным методом взаимное пре- образование ПНФ f  ПТМФ Y  выполняется по пра- вилу, аналогичному правилу взаимного преобразования ДНФ f  ТМФ Y 1 [8]: iix )1( , iix )0( , отсутствующая iix )( , знак   (,). (2) Например, ПНФ 33121321 ),,( xxxxxxxxf  , а ее ПТМФ   )}1(),11(),10{(Y . В случае необходимости получить из ПНФ f совер- шенную ПНФ f, а оттуда – совершенную ДНФ f, необ- ходимо в конъюнктермы ПНФ f, имеющие ранг r n , внести выражение )( ii xx  , где ix – отсутствующая пе- ременная. Тогда совершенная ПНФ f получается после раскрытия скобок и удаления пар одинаковых минтер- мов. На примере рассмотренной функции такая проце- дура выполняется следующим образом:   322113221 332133121 ))(()( )( xxxxxxxxx xxxxxxxxxf  321321321321 xxxxxxxxxxxx  321321321321 xxxxxxxxxxxx .321321321321 321321321321 xxxxxxxxxxxx xxxxxxxxxxxx   Числовым теоретико-множественным методом пере- ход «ПТМФ Y  совершенная ПТМФ Y  совершен- ная ТМФ 1Y » реализовать проще, что видим на примере (для наглядности применим десятичные числа):   }5,4,3,1{)}7,5,3,1(),7,5(),5,4{()}1(),11(),10{(Y . В статье рассмотрена числовая теоретико-множествен- ная интерпретация полинома Жегалкина и метод взаимно- го преобразования из одного формата представления функ- ции f в другой. В общем случае полином Жегалкина функции f (xn, xn–1, , x1), – это логическое выражение, представленное суммой по mod 2 конечного числа конъюнктермов рангов r  {0, 1, 2, , n}, переменные которых не имеют знака ин- версии: ......... ...),...,,( 31132112 2211011   xxcxxcxc xcxccxxxf nn nn II I nnkk cxxxcxxxc n     12 0 21,...,2,121,...,2,1 ...... , (3) где сI  {0, 1} – коэффициенты конъюнктермов I, I = = 0, 1, , 2 n – 1; 0 = 1. Покажем, что между значениями коэффициентов сI (3) и значениями коэффициентов f I  {0, 1}, I = 0, 1, , 2 n–1, минтермов mI (на I-м наборе) совершенной ДНФ или ПНФ функции f (поскольку II I II I mfmf nn       12 0 12 0 ) суще- ствует определенное соответствие. На примере произ- вольной функции от двух переменных полином Жегал- кина можно получить следующим образом:   213212211210 3322110021 ),( xxfxxfxxfxxf mfmfmfmfxxf   2132122112 10213212211210 )1()1()1)(1 ( xxfxxfxxfx xfxxfxxfxxfxxf 2132101202100 )()()( xxffffxffxfff  21312210 xxcxcxcc Zh  , (4) где оператор Zh  символизирует процедуру перехода из совершенной ДНФ/ПНФ к полиному Жегалкина, коэф- фициенты c i которого связаны с коэффициентами f i, i = 0, 1, 2, 3 соотношениями 0 0c f , 101 ffc  , 202 ffc  , 32103 ffffc  . (5) Соотношения (5) между значениями коэффициентов f i совершенной ДНФ или ПНФ и значениями коэффици- ентов c i, i = 0, 1, 2, 3 полинома Жегалкина функции f (x1, x2) иллюстрирует табл. 1. Теперь рассмотрим обратный переход от полинома Жегалкина к совершенной ПНФ (ДНФ) для функции от двух переменных: 1 2 0 1 2 2 1 3 1 2( , )f x x c c x c x c x x     0 0 1 2 0 2 1 0 1 2 3 1 2( ) ( ) ( )f f f x f f x f f f f x x          0 2 1 1 2 1 2 1 2 2 1(1 ) ( ) (f x x x x f x x x f x        22 УСиМ, 2013, № 1 1 2 3 1 2 0 0 1 1 2 2 3 3) ,x x f x x f m f m f m f m      где 0 2 1 1 2 1 21m x x x x x x     212121 xxxxxm  212112 xxxxxm  213 xxm  . Т а б л и ц а 1 Следовательно, 21321221121021 ),( xxfxxfxxfxxfxxf  . От полученной совершенной ПНФ возвратиться к полиному Жегалкина можно следующим путем:  33221100123122121120 mfmfmfmfxxfxxfxxfxxf  3321022011000 )()()( mccccmccmccmc  )()()( 32231132100 mmcmmcmmmmc 3322110033 pcpcpcpcmc  , где 12121212132100  xxxxxxxxmmmmp 22121311 xxxxxmmp  12121322 xxxxxmmp  2133 xxmp  . Следовательно, 2131221021 ),( xxcxcxccxxf  , что соответствует (3). В случае функции f (x1, x2, x3) полином Жегалкина бу- дет иметь такой вид: , ),,( 321721631514 32322310321 xxxcxxcxxcxc xxcxcxccxxxf   (6) где 00 fc  , 101 ffc  , 202 ffc  , 32103 ffffc  , 404 ffc  , 54105 ffffc  , 64206 ffffc  , 765432107 ffffffffc  . Обратный переход от полинома Жегалкина к совер- шенной ПНФ (ДНФ) через замену ci  f i в этом случае также будет свидетельствовать о полном соответствии и взаимозаменяемости коэффициентов f i и ci. Чтобы доказать справедливость утверджения о взаи- мозаменяемости коэффициентов f i и ci для произволь- ной функции f (x1, x2, , xn), соотношения между этими коэффициентами упорядочим в виде матричных урав- нений для n = 1, 2. В частности, если для f (x) имеем f0  c0, f1  c0  c1, то в матричном представлении эту систему можно запи- сать в виде уравнения или в более компактной форме следующим образом:                   1 0 1 0 11 01 c c f f или 1 1 1 CAF  . (7) Действительно, взаимозаменяемость коэффициентов ii cf  здесь будет иметь место, поскольку в полино- миальном формате произведение матрицы А1 самой на себя, которое обозначим как 11 2 1 AAA  , равно единичной матрице 2E второго порядка: 2 1 2 1 0 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 A E                                     . Тогда, перемножив левую и правую части равенства (7) на 1A , получим 1 1 1 FAC  . Для n = 2, взяв за основу (5), получим (пунктирными линиями выделены блоки для n = 1): 0 0 1 1 1 2 2 2 1 1 3 3 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 f c f c A C f c A A f c                                       0 или 2 2 2 CAF  , (8) где        00 00 0 – нулевая матрица второго порядка. По аналогичной процедуре получим 2 2 1 12 1 1 1 1 2 2 42 2 2 2 1 1 1 1 1 1 1 1 2 A A A A A A E A E A A A A A A A A E                                 0 0 0 0 0 0 0 0 , где              1000 0100 0010 0001 4E – единичная матрица порядка 22. Следо- вательно, на основании этого и (8) для n = 2 справедливо равенство C2 = A2F 2. Для доказательства справедливости утверждения о взаимозаменяемости коэффициентов fi и ci для произ- вольного n применим метод математической индукции. Для n = 1, 2, как видим, это утверджение справед- ливо. Пусть для 1n справедливо равенство 12 2 1  nEAn . Тогда 1 1 1     n n n FAC , где           22 2 1 nn n n AA A A 0 . Поскольку для n 0 0 1 11 1 1 2 1 2 1 ... ... n n n n n f c f cA A A f c                                   0 или n n n CAF  , (9) N f0 f1 f2 f 3 c0 c1 c2 c3 8 9 10 11 12 13 14 15 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 N f0 f1 f2 f3 c0 c1 c2 c3 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 УСиМ, 2013, № 1 23 а 1 1 1 12 1 1 1 1 2 1 1 1 1 2 2 2 2 2 1 1 1 1 2 , n n n n n n n n n n n n n n n n n n A A A A A A A EA A A A E EA A A A                                               0 0 00 0 0 00 то на основании этого и (9) запишем искомое равенство n n n FAC  . (10) Взаимозаменяемость коэффициентов f i и ci (10) дает основание утверждать взаимозаменяемость минтермов совершенных форм (ПНФ, ДНФ, ТМФ) и конъюнктер- мов полинома Жегалкина, которое можно использовать для числовой теоретико-множественной интерпретации полинома Жегалкина. Полином Жегалкина в теоретико-множественной фор- ме представления будем называть теоретико-множе- ственной формой полинома Жегалкина – ТМФЖ Y . За- метим, что в отличие от троичных конъюнктермов ПТМФ Y конъюнктермы ТМФЖ Y будут иметь значения раз- рядов },1{  . При этом ТМФЖ Y вырожденной функ- ции f (x1, x2, , xn) = 1 не отличается от совершенной ПТМФ Y : в двоичном формате {[0,1,...,2 1]}nY    2 n E , в десятичном – 1  ]}{[Y . Это легко показать, если конъюнктермы полинома Жегалкина за- менить на их числовые представители по правилу (2) и удалить в образовавшемся множестве пары одинаковых чисел. Следовательно, если в (4) 0 1 2f f f   3 1f  , то 1),( 21 xxf , тогда в двоичном формате получим Zh xxxxxxxxxxxx  211212211221 1   )}{()}11(),1(),11(),1(),11(),(),1(),1(),11{( Zh , соответственно в десятичном формате –   )}3,2,1,0{()}3(),3,2(),3(),3,1(),3(),3,2,1,0(),3,2(),3,1(),3{( Zh , где Zh  – оператор перехода к ТМФЖ Y функции f. Если 03210  ffff , то 0),( 21 xxf , а посколь- ку 03210  cccc , то ТМФЖ Y . Числовую теоретико-множественную интерпретацию полинома Жегалкина (для невырожденных случаев) рас- смотрим на примере функции f (x1, x2). Соответствие между коэффициентами f i и ci проиллюстрируем на картах Карно (рис. 1), где а и б – карты для f i и их минтермов im ДНФ или ПНФ, а в и г – карты для c i и их конъюнк- термов полинома Жегалкина. f 0 f1 f 2 f 3 x 1 x 2 x 1 x2 x1 x 2 x1 x2  c0 c1 c2 c3 1 x2 x1 x1 x2   Zh а б в г Рис. 1 Карты а и б, а также в и г взаимно связаны соответ- ствием клеток. Объеденим их попарно и образуем число- вые карты (рис. 2), отображающие соответствие fi Zh  ci : слева – для двоичных индексов (00), (01), (10), (11) ко- эффициентов f i, справа – для десятичных индексов [0], [1], [2], [3] коэффициентов c i. 00 01 10 11 0 1 2 3  Zh Рис. 2 Соответствие ТМФ (ПТМФ) Zh  ТМФЖ определим следующим способом. На числовых картах (см. рис. 2) черным кружком () выделим клетки, номера которых соответствуют значениям индексов коэффициентов fi = 1 и ci = 1. Из табл. 1 для каждого заданного }1,0{if оп- ределим значения ci, записывая соответствующее выра- жение минтерма ДНФ и полинома Жегалкина. Считы- ваемые числа с карты коэффициентов ic (из контуров карты – множество чисел) – это искомые числовые конъ- юнктермы ТМФЖ Y функции f (x1, x2). Пусть 10 f , 0321  fff ; это минтерм 0m 1 21 )}00{( xx . Тогда 13210  cccc , что соответствует полино- му 21121 xxxx Zh  . Соответственно ТМФЖ {[0,1,2,3]} {[ ]}Y       . 11 f , 0320  fff ; 1 211 )}01{( xxm ; 131  cc , 020  cc , т.е. 212 xxx Zh  ;   ]}1{[]}3,1{[Y . 12 f , 0310  fff ; 1 212 )}10{( xxm ; 132  cc , 010  cc , т.е. 211 xxx Zh  ;   ]}1{[]}3,2{[Y . 13 f , 0210  fff ; 1 213 )}11{( xxm ; 13 c , 0210  ccc , т.е. 21xx Zh  ;   ]}11{[]}3{[Y . В табл. 2 отображено для f (x1, x2) соответствие между дизъюнктивним и полиномиальным представлениями как в аналитическом, так и в теоретико-множественном  Zh  Zh  Zh  Zh 24 УСиМ, 2013, № 1 форматах. В колонке маска размещены маски литералов ( },{ xxl – для аналитического формата, }1,0{l – для числового формата), формирующие конъюнктермы и их ранги r для определенных ДНФ/ПНФ и ТМФ/ПТМФ, а именно: маска }{ll формирует конъюнктермы второго ранга; {l–}и {–l} – первого ранга; {– –}– нулевого ранга. Т а б л и ц а 2 Аналитический формат Теоретико-множественный формат Мас ка ДНФ/ПНФ Полином Ж. ТМФ/ПТМФ ТМФЖ {ll} x 1x 2 x 1x2 x1x 2 x1x2 1x2x1 x1x2 x2x1x2 x1x1x2 x1x2 (00) (01) (10) (11) (0) (1) (2) (3) (– –) (–1) (1–) (11) (0,1,2,3) (1,3) (2,3) (3) {l –} x 1 x1 1x1 x1 (0–) (1–) (0,1) (2,3) (– –), (–1) (1–), (11) (0,2) (2) {– l} x 2 x2 1x2 x2 (–0) (–1) (0,2) (1,3) (– –), (1–) (–1), (11) (0,1) (1) {– –} 1 1 (– –) (0,1,2,3) (– –), (–1), (1–), (11) (0) В колонках Аналитический формат помещены вы- ражения конъюнктермов ДНФ/ПНФ и полинома Жегал- кина, а в колонках Теоретико-множественный формат – их двоичные (троичные) и десятичные представления, т.е. ТМФ и ПТМФ, а также ТМФЖ. Табл. 3 иллюстрирует аналогичное соответствие для f (x1, x2, x3), где маски литералов формируют конъюнктер- мы различных рангов r так: }{lll – 3r ; }{ ll , }{ ll  , }{ ll – 2r ; }{ l , }{ l , }{ l – 1r ; }{  – 0r . Взаимно однозначное соответствие между рассмот- ренными формами, отображаемые в табл. 2 и 3, будет со- храняться для произвольной функции от n переменных. В табл. 2 и 3 двойной линией отделены множества элементов совершенных форм обоих форматов для ма- сок {ll} и {lll}. Это значит, что элементы табл. 2 и 3 в колонках ДНФ/ПНФ и ТМФ/ПТМФ для остальных ма- сок образованы операцией склеивания (в общем слу- чае для ДНФ – это выражение 1r ix 11   r i r x , где r i r x 1 1   и r i r x 2 1   – соседние конъюнктермы r- ранга). Например, в табл. 2 для маски }0{}{ l , кото- рой соответствует выражение 1 2x x 121 xxx  , получим полином Жегалкина  )1( 2112 xxxx 2 1 2 1( ) 1x x x x   . Числовым теоретико-множественным методом пре- образование типа «совершенная ДНФ (ТМФ)  поли- ном Жегалкина» выполняется по схеме: совершенная ДНФ f  совершенная ТМФ 1Y Zh  Zh  ТМФЖ Y  полином Жегалкина. Схема обратного преобразования «полином Жегал- кина  совершенная ТМФ (ДНФ)» имеет вид: полином Жегалкина  ТМФЖ Y  совершенная ТМФ 1Y  совершенная ДНФ f. В рассмотренных схемах взаимные преобразования «совершенная ТМФ 1Y  ТМФЖ Y » выполняются за- меной значений i-х разрядов конъюнктермов по прави- лу, основанному на правиле (2): ii )()0(  ; ii )1()1(  . (11) Над образовавшейся ТМФЖ Y далее выполняется процедура упрощения, которая реализуется удалением пар одинаковых чисел. Затем, чтобы получить полином Жегалкина, необходимо i-е разряды двоичных конъюнк- термов упрощенной ТМФЖ Y заменить на литералы полинома по правилу, справедливому и для обратного преобразования «полином Жегалкина  ТМФЖ Y »: i)0( отсутствующая ix ; ii x)1( . (12) Заметим, переход ТМФЖ Y  совершенной ТМФ 1Y однозначный – двоичные конъюнктермы ТМФЖ Y за- писываются без изменений, поскольку, как упомянуто ранее, эти формы тождественны. Следовательно, по описанной схеме переход от со- вершенной ДНФ f к ТМФЖ Y для рассмотренного примера (пятая сверху строка табл. 2) будет выполнять- ся так:  )}1(),{()}01(),00{( 1 2121 Zh xxxx или   )}2,0{()}3,1(),3,2,1,0{( Zh . В частности, для вырожденной функции f (x1, x2) = 1 (последняя строка табл. 2) полином Жегалкина равен еди- нице: .1)()() 1( 2121121221 1221212121   xxxxxxxxxx xxxxxxxxxx В теоретико-множественном формате – это числовой конъюнктерм нулевого ранга, т.е. ТМФ 1 1{( )}Y    , которому соответствует ТМФЖ Y : 1 1{00,01,10,11} {( ), ( 1), (1 ), (11)} Zh Y          )}0{()}3(),3,2(),3,1(),3,2,1,0{( . Преобразование «ДНФ/ТМФ  полином Жегалкина» выполняется по аналогичной схеме при условии, если конъюнктермы ДНФ/ТМФ взаимно ортогональны. По- следние можно получить либо процедурой ортогонали- заци [5, 8] либо путем преобразования заданной ДНФ/ТМФ в совершенную форму. Ортогонализацию конъюнктер- мов, приналежащую к сложным многовариантным про- цедурам, целесообразно применять тогда, когда число неортогональных элементов небольшое. Другой путь значительно проще, если в совершенную форму преобра- зовывать ТМФ 1Y [8, 9]. Этот случай представим схемой: УСиМ, 2013, № 1 25 ДНФ f  ТМФ 1Y  совершенная ТМФ 1Y Zh  Zh  ТМФЖ Y  полином Жегалкина. Преобразование «полином Жегалкина  ДНФ f» вы- полняется по обратной схеме, которая на этапе перехода от совершенной ДНФ 1Y к ТМФ 1Y дополняется про- цедурой минимизации. Предложенный числовой теоретико-множественный метод преобразования конъюнктермов (совершенной) ДНФ или ТМФ в полином Жегалкина, и наоборот, по- кажем на примерах. Пример 1. Числовым теоретико-множественным методом преобразовать совершенную ДНФ функции 321321321321321 xxxxxxxxxxxxxxxf  в полином Же- галкина, и наоборот. Решение. Преобразовав совершенную ДНФ f в со- вершенную ТМФ Y 1 и применив правило (11), получим ТМФЖ Y  заданной функции: .)}111(),11(),1(),1(),{( )}111(),101(),100(),001(),000{( 11   Zh Zh Y Затем, расписав образовавшиеся конъюнктермы ТМФЖ Y  на множества десятичных чисел и упростив полученное множество путем удаления пар одинаковых чисел, запишем по правилу (12) полином Жегалкина   }7,2,0{)}7(),7,5(),7,6,5,4(),7,5,3,1(),7,6,5,4,3,2,1,0{( 32121)}111(),010(),000{( xxxx  , Обратное преобразование «полином Жегалкина  со- вершенная ДНФ» выполняется так:     )}7(),7,6,3,2(),7,6,5,4,3,2,1,0{()}111(),1( ),{()}111(),010(),000{(1 3212 xxxx 1{0,1,4,5,7} {(000), (001),(100),(101),(111)}   1 2 3 1 2 3 1 2 3 1 2 3 1 2 3.x x x x x x x x x x x x x x x     Пример 2. Числовым теоретико-множественным ме- тодом преобразовать полином Жегалкина функции adbcadcbaf ),,,( в эквивалентную ДНФ, и об- ратно [4], с. 17. Решение {(1000), (0110), (1001)} {(1 ), ( 11 ), (1 1)} a bc ad                Т а б л и ц а 3 Аналитический формат Теоретико-множественный формат Маска ДНФ/ ПНФ Полином Жегалкина ТМФ/ПТМФ ТМФЖ {lll} x 1x 2x 3 x 1x 2x3 x 1x2x 3 x 1x2x3 x1x 2x 3 x1x 2x3 x1x2x 3 x1x2x3 1 x3  x2 x 2x3  x1  x1x3  x1x2  x1x2x3 x3 x 2x3  x1x3  x1x2x3 x2 x 2x3  x1x2  x1x2x3 x 2x3  x1x2x3 x1  x1x3  x1x2  x1x2x3 x1x3  x1x2x3 x1x2  x1x2x3 x1x2x3 (000) (001) (010) (011) (100) (101) (110) (111) (0) (1) (2) (3) (4) (5) (6) (7) (– – –) (– –1) (–1–) (–11) (1– –) (1–1) (11–) (111) (0,1,2,3,4,5,6,7) (1,3,5,7) (2,3,6,7) (3,7) (4,5,6,7) (5,7) (6,7) (7) {ll–} x 1x 2 x 1x2 x1x 2 x1x2 1 x2  x1  x1x2 x2  x1x2 x1  x1x2 x1x2 (00–) (01–) (10–) (11–) (0,1) (2,3) (4,5) (6,7) (– – –), (– –1) (–1–), (–11) (1– –), (1–1) (11–), (111) (0,2,4,6) (2,6) (4,6) (6) {l–l} x 1x 3 x 1x3 x1x 3 x1x3 1 x3  x1  x1x3 x3  x1x3 x1  x1x3 x1x3 (0–0) (0–1) (1–0) (1–1) (0,2) (1,3) (4,6) (5,7) (– – –), (– 1–) (– –1), (–11) (1– –), (11–) (1–1), (111) (0,1,4,5) (1,5) (4,5) (5) {–ll} x 2x 3 x 2x3 x2x 3 x2x3 1 x3  x2  x2x3 x3  x2x3 x2  x2x3 x2x3 (–00) (–01) (–10) (–11) (0,4) (1,5) (2,6) (3,7) (– – –), (1– –) (– –1), (1–1) (–1–), (11–) (–11), (111) (0,1,2,3) (1,3) (2,3) (3) {l– –} x 1 x1 1 x1 x1 (0– –) (1– –) (0,1,2,3) (4,5,6,7) (– – –), (– –1), (–1–), (–11) (1– –), (1–1), (11–), (111) (0,4) (4) {–l–} x 2 x2 1 x2 x2 (–0–) (–1–) (0,1,4,5) (2,3,6,7) (– – –), (– –1), (1– –), (1–1) (–1–), (–11), (11–), (111) (0,2) (2) {– –l} x 3 x3 1 x3 x3 (– –0) (– –1) (0,2,4,6) (1,3,5,7) (– – –), (–1–), (1– –), (11–) (– –1), (–11), (1–1), (111) (0,1) (1) {– – –} 1 1 (– – –) (0,1,2,3,4,5,6,7) (– – –), (– –1), (–1–), (–11), (1– –), (1–1), (11–), (111) (0) 26 УСиМ, 2013, № 1    }15,12,10,8,7,6{)}15,13,11,9( ),15,14,7,6(),15,14,13,12,11,10,9,8{( 1)}1111(),1001(),1010(),1000(),0111(),0110{( . Полученную совершенную ТМФ 1Y сминимизируем, например, методом расцепления конъюнктермов [10]: 1 1 011 011 100 101 110 111 01 0 01 1 10 0 10 0 11 0 11 1 0 10 0 11 1 00 1 10 1 00 1 11 110 111 000 010 100 111 {(011 ),(10 0),(1 00),( 111)} . S C C lll ll l Y l ll lll                                                 Отсюда, эквивалентная ДНФ заданной функции bcddcadbabcaf  . Обратное преобразование «ДНФ f  полином Же- галкина» выполняется так:  1)}111(),001(),010(),011{(bcddcadbabca   )}1111(),11(),11(),1(),111(),11{( )}1111(),1001(),1010(),1000(),0111(),0110{( 1 Zh Zh {(6,7,14,15), (7,15), (8,9,10,11,12,13,14,15), (10,11,14,15), (12,13,14,15), (15)} {6,8,9}     .)}11(),1( ),11{()}1001(),1000(),0110{( adbca     Пример 3. Числовым теоретико-множественным методом преобразовать ДНФ функции ),,( 321 xxxf 321 xxx  в полином Жегалкина, и наоборот [12], с. 33. Решение 1 1 2 3 {(1 ), ( 1 ), ( 1)}x x x        1 1{(4,5,6,7), (2,3,6,7), (1,3,5,7)} {1,2,3,4,5,6,7}     )}111(),11(),11(),1(),11(),1(),1{( )}111(),110(),101(),100(),011(),010(),001{( 1 Zh Zh 321213113223 xxxxxxxxxxxx  . Из полученного полинома Жегалкина заданная ДНФ f образуется следующим путем:   )}111(),11(),11(),1(),11(),1(),1{( 321213113223 xxxxxxxxxxxx     }7,6,5,4,3,2,1{ )}7(),7,6(),7,5(),7,6,5,4(),7,3(),7,6,3,2(),7,5,3,1{( 1{(001),(010),(011),(100),(101),(100),(111)} 00 01 01 10 10 11 11 0 1 0 0 0 1 1 0 1 1 1 0 1 1 01 10 11 00 01 10 11 S S c ll l l ll                                         1)}11(),01(),10();11(),10(),01{(           ll llC . Из полученного множества покрытия на следующем шаге расщепления получим: 0 1 1 (01 ),(10 ),(11 ) (1 ),( 1 ) 1 0 1 S Cl l                            , 0 1 1 (0 1),(1 0),(1 1) (1 ),( 1) 1 0 1 S Cl l                       . Отсюда минимальная ТМФ 11 )}1(),1(),1{( Y . Следовательно, 321 xxxf  . Заключение. Из рассмотренного материала не слож- но сделать вывод о том, что предложенную числовую теоретико-множественную интерпретацию полинома Же- галкина и основанный на этом метод взаимного преоб- разования дизъюнктивного и полиномиального форма- тов представления логических функций, удобно исполь- зовать для непосредственной реализации на компьютере без каких-либо промежуточных процедур или преобра- зований. Описанный метод можно также применять к системе логических функций от п переменных.  Внимание ! Оформление подписки для желающих опубликовать статьи в нашем журнале обязательно. В розничную продажу журнал не поступает. Подписной индекс 71008 << /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

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