New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification

A generalized simplify rules of conjuncterms in polynomial set-theoretical format is considered. These rules are based on the proposed theorems for different initial transform condition of pair conjuncterms where hamming distance between them can be arbitrary. These rules may be useful to minimize i...

Full description

Saved in:
Bibliographic Details
Published in:Управляющие системы и машины
Date:2015
Main Author: Rytsar, B.Ye.
Format: Article
Language:English
Published: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2015
Subjects:
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/87194
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification / B.Ye. 04-Rytsar // Управляющие системы и машины. — 2015. — № 2. — С. 39–57. — Бібліогр.: 33 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859990996823048192
author Rytsar, B.Ye.
author_facet Rytsar, B.Ye.
citation_txt New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification / B.Ye. 04-Rytsar // Управляющие системы и машины. — 2015. — № 2. — С. 39–57. — Бібліогр.: 33 назв. — англ.
collection DSpace DC
container_title Управляющие системы и машины
description A generalized simplify rules of conjuncterms in polynomial set-theoretical format is considered. These rules are based on the proposed theorems for different initial transform condition of pair conjuncterms where hamming distance between them can be arbitrary. These rules may be useful to minimize in polynomial set-theoretical format of arbitrary logic functions of n variables. Advantages of the proposed rules are illustrated by the examples. Рассмотрены обобщенные правила упрощения конъюнктермов в полиномиальном теоретико-множественном формате, основанные на предложенных теоремах для разных начальных условий преобразования пары конъюнктермов, хеммингово расстояние между которыми может быть произвольным. Упомянутые правила могут быть полезными для минимизации в полиномиальном теоретико-множественном формате произвольных логических функций от n переменных. Преимущества предложенных правил проиллюстрированы примерами. Розглянуто узагальнені правила спрощення кон’юнктермів у поліноміальному теоретико-множинному форматі, які ґрунтуються на запропонованих теоремах для різних початкових умов перетворення пари кон’юнктермів, геммінгова відстань між якими може бути довільна. Зазначені правила можуть бути корисні для мінімізації у поліноміальному теоретико-множинному форматі довільних логічних функцій від n змінних. Переваги запропонованих правил проілюстровано прикладами.
first_indexed 2025-12-07T16:31:25Z
format Article
fulltext УСиМ, 2015, № 2 39 Новые методы в информатике UDC 519.718 B.Ye. Rytsar New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification Рассмотрены обобщенные правила упрощения конъюнктермов в полиномиальном теоретико-множественном формате, осно- ванные на предложенных теоремах для разных начальных условий преобразования пары конъюнктермов, хеммингово рас- стояние между которыми может быть произвольным. Упомянутые правила могут быть полезными для минимизации в по- линомиальном теоретико-множественном формате произвольных логических функций от n переменных. Преимущества пред- ложенных правил проиллюстрированы примерами. A generalized simplify rules of conjuncterms in polynomial set-theoretical format is considered. These rules are based on the proposed theorems for different initial transform condition of pair conjuncterms where hamming distance between them can be arbitrary. These rules may be useful to minimize in polynomial set-theoretical format of arbitrary logic functions of n variables. Advantages of the pro- posed rules are illustrated by the examples. Розглянуто узагальнені правила спрощення кон’юнктермів у поліноміальному теоретико-множинному форматі, які ґрунтуються на запропонованих теоремах для різних початкових умов перетворення пари кон’юнктермів, геммінгова відстань між якими може бути довільна. Зазначені правила можуть бути корисні для мінімізації у поліноміальному теоретико-множинному форматі довільних логі- чних функцій від n змінних. Переваги запропонованих правил проілюстровано прикладами. Introduction. The problem of minimization of logical functions in polynomial format caused the practical interest because of many advantages of realization of digital devices and systems in comparison with rea- lization in disjunctive format. The investigations [1–8] have shown that it is economically profitable to build such digital devices as arithmetic, communication, coding error detectors as well as devices of programmed logic and others on logical elements AND-EXOR which realize polynomial basis , that is AND, EX- CLUSIVE OR (EXOR) logical operations and constant 1. It is easier to test and diagnose [9–11] digital de- vices on AND-EXOR if compared to the devices built on AND-OR. However, inspite of the mentioned ad- vantages it is more difficult to minimize a function in polynomial format than in disjunctive format. The precise solutions of a minimization problem in polynomial format generally is based on analytical transformations of positive pDavio-expansion and/or negative nDavio-expansion [2] or on visual K-map method [1–3]. Correspondly, such methods are suitable only for functions from not great number of variables [5, 7, 10–13] and only for special classes of functions with up to 10 variables [14]. Heuristic methods have comparatively wider practical application [1, 8, 16–23]. Among them two should be singled out. One of them, a minimization method based on a coefficient of generalized canonical Reed–Muller forms which makes use of matrix transformations. The second method being more efficient involves iterative carring out of operations with conjuncterms of different ranks and polynomial forms of the given function. To the last belongs the algorithm [17], which after transformation of the given function in Zhegalkin polynomial (that is Positive Polarity Reed–Muller expression) minimizes it on the basis of three operations with conjuncterms. Better results have been shown by algorithm based on the procedure of so-called linked product terms [18, 19]. Later, on the basis of this procedure, the algorithms have been worked out which were completed with more perfect operations (that is primary xlink, secondary xlink, unlink, exorlink), which can be used for minimization of a system of complete and incomplete functions [20, 21]. However, the mentioned above algorithms have one drawback in common. They involve the procedure of linking in pairs only conjuncterms of the same rank },...,2,1{ nr , which differ by binary positions. Cor- respondingly, this limits the use of such algorithms to functions given in SOP (Sum-Of-Product) or 40 УСиМ, 2015, № 2 ESOP (EXOR Sum-Of-Product), which can have triple values in the different part. In these cases to con- juncterms that differ in ranks certain procedures of transformation (for example into canonical form) are applied which lead to an increase of steps and time of procedures. Besides the above mentioned opera- tions of conjuncterms linking and other rules of simplification [24–26] do not have generalized character as to Hamming distance between any two conjuncterms of different ranks of a given function that does not guarantee final minimized result. Because of this, as one can judge from the literature, the search is still under way of such operations and procedures with conjuncterms which would guarantee precise or at least close to precise result of solving the problem of minimization of arbitrarily given function in poly- nomial format. In this paper we consider a new method of minimization of logical functions with n variables in polyno- mial set-theoretical format, in the basis of which there is a procedure of splitting of conjuncterms of complete and incomplete function and also their system [27–29], and generalized set-theoretical rules of conjuncterms simplification. The suggested rules contrary to the known [21–25], guarantee generally better (as to costs of realization and number of procedure steps) results of minimization of different forms of given functions what is proved by the given in the paper numerous examples that are borrowed from publications by other authors for comparison. The suggested method of minimization on the basis of conjuncterms splitting in polynomial set-theoretical format has been described in three papers by the author: the first one is focuses on generalized set-theoretical rules of conjuncterms simplification (this paper), the second one – on minimization of com- plete and incomplete functions and the third one – on minimization of functions system. 1.1. Formulation of problem The complexity of minimization problem of logical functions in the polynomial format consists of the fact that contrary to minimization in disjunctive format based on an operation of adjacency of neighbouring conjuncterms, here, except for the last one, other operations can be applied which can also simplify conjuncterms of a given function [1, 2]. The simplification of conjuncterms of the rank },...,2,1{ nr of any logical function f ( x1, x2,..., xn) in po- lynomial set-theoretical form (PSTF) is based on analytical axioms of a logical operation of sum for mod 2: , , , , , , }1,0{a . Such sets of PSTF [30] correspond to the below given expressions: , , , , , , where }1,0{ ,  – an empty set that reflects the function-constant f (x)  0, and symbol dash () reflects absorbed variable x, that is complete set E2 1 {0,1}, that reflects the function-constant f (x)  1. On this ground, for example, the function 212121221 )1(),( xxxxxxxxxf  will have PSTF , and the function will have PSTF   )}01(),01{(Y . The suggested generalized set-theoretical rules of simplification of a conjuncterm set of any logical function f ( x1, x2,..., xn), given in PSTF Y , are based on iterative process of simplification of two con- juncterms )( 211 1 n r  and )( 212 2 n r  , },1,0{ i , },...,2,1{, 21 nrr  , which differ in (Hamming) difference nd ,...,2,1 – number of different in value },1,0{,...,,,  of onename posi- tions. Here the different part ,...,,,  of these conjuncterms can have a different total number of liter- als kl . For example, two pairs of conjuncterms         1001 0111 and         1001 111 have d  3, but the first has 6lk , and the second – 5lk . In connection with this different initial conditions of transformation are possible. We will consider the following conditions: УСиМ, 2015, № 2 41  when kl  2d , here two conjuncterms are of the same rank r 1 and r 2 but differ in d onename bi- nary positions }1,0{,...,,,  ;  when kl  2d 1, here one conjuncterm of (r 1)-rank 1 1 r , and the second of r-rank r 2 , differ in d onename positions },1,0{,...,,,  , where dash (–) belongs to 1 1 r ;  when kl  2(d 1), here two conjuncterms are of the same r-rank r 1 and r 2 differ in d onename posi- tions },1,0{,...,,,  each of them has one dash (–). As a result of transformation of two conjuncterms in polynomial set-theoretical format some set of con- juncterms of certain ranks will appear that is transformed PSTF . Depending on distance d, as it is fur- ther shown, different number of transformed PSTF , will appear which will be designated as kY. The very fact of creation of different transformed PSTF will have decisive meaning for minimization in polynomial format of a given function f. Efficiency of simplification of two different conjuncterms for the mentioned above initial conditions will be estimated on the basis of comparison of interrelation k * / kl *, obtained on the ground of data of transformed PSTF , with initial interrelation k / kl, where k  2. 1.2. Theoretical part If d  0, then conjuncterms r 1 and r 2 are the same, that is rrr  21 . Then according to the ex- pression , transformed PSTF , that corresponds to removal of r 1 and r 2 from the given function f. In this case kY 1 аnd k * / kl *  0 / 0. In the case 1d conjuncterms are different rr 21  . Correspondingly every transformed PSTF will have different interrelation k * / kl * and their set will have different power kY. Let us consider the first initial condition (see p. 1.1) when two conjuncterms of r-rank r 1 and r 2 differ in values of d onename binary position }1,0{,...,,,  . Theorem 1. Two conjuncterms of r-rank r 1 and r 2 , },...,2,1{ nr , of the function f ( x1, x2,..., xn), that differ in values d of onename binary positions }1,0{,...,,,  , in polynomial set-theoretical format form a set of different PSTF of power kY  d!, each of them consists of k *  d conjuncterms of (r 1)-rank and has in different part the total number of literals kl *  d(d 1). Proof. To determine k * / kl * and kY let us consider transformation of conjuncterms r 1 and r 2 for d 1,2,3,4. Here it should be mentioned that initial interrelation k / kl  2 / 2d .  Let d 1. Then )( 11 ni r  , )( 12 ni r  , }1,0{i , respectively for analytical ex- pression we can write: , (1) where the transformed PSTF that is a triple conjuncterm of (r 1)-rank. For (1) interrelation k * / kl * 1/ 0, and as initial interrelation k / kl  2 / 2, then it is indicative of the fact that as a result of transformation (1) simplification took place due to replacement of two conjunc- terms of r-rank by one conjuncterm of (r 1)-rank; kY 1. With the aim of simpler writing the conjuncterms of the given and transformed PSTF will be con- sidered only for their different positions which will be written down in a column. In (1) such position is i, so, simplified writing down (1) with taking into account }1,0{i will look like: 42 УСиМ, 2015, № 2 , (2) where – operator of the given conjuncterms r 1 and r 2 in polynomial format of the function f. In particu- lar examples of transformation the same in meaning onename positions of conjuncterms will be rewritten without any change. For example, , that in decimal format corresponds to and in analytical form is .  Let d  2. Then )( 11 nji r  , )( 12 nji r  , }1,0{,  ji , and respectively to analytical expressions (if i  i) and (if ii  ), in simplified way ( i , i , }1,0{,  ) we will get . (3) For (3) we have k * / kl *  2 / 2, that are indicative of simplification of the given conjuncterms due to re- duction of their rank from r до (r 1), as initial interrelation k / kl  2 / 4; kY  2. The set of conjuncterms PSTF for d  2 can be easily formed visually with the help of a pattern of a given function f, vertices of which are interpreted by minterms and edges – conjuncterms of (n 1)-rank [31]. As the degree of each vertex of the pattern is equal to n, then possible ways of passing from initial vertex to final one will have points of branching the number of which will be directly proportional to dis- tance d. Here, a change of an edge in the point of branching will determine a change of way of passing and respectively a position of dash (–) in a formed conjuncterm of (n 1)-rank. So, placement of dash (–) in certain position of a conjuncterm of (n 1)-rank has combinative character and it is a permutation with- out any repetition. It will be that what determine number of kY of transformed PSTF . For d  2 one can be sure about this.  Let d  3. Then )( 11 nkji r  and )( 12 nkji r  , }1,0{,,  kji . In the Fig. 1 six patterns of the function f (,, ), }1,0{,,  , are shown where marked edges il- lustrate all possible ways of passing from initial vertex 0 (it is minterm (000)) to final vertex 7 (it is minterm (111)). As every such way consists of three edges, every transformed PSTF will have three conjuncterms of 2-rank. From Fig. 1 we get the set , to which corresponds the set of the transformed PSTF :                                                                                  11 01 00 , 11 10 00 , 11 01 00 , 11 10 00 , 11 01 00 , 11 10 00 111 000 . УСиМ, 2015, № 2 43 a b c d e f Fig. 1 To form the conjuncterms of (n 1)-rank of the set of transformed PSTF for any pair of minterms of the function f, that have d  3, is possible with the help of matrix of disposition of dashes (–) of the scale 63 :           012012 100221 221100 , where in every column the numbers 0, 1, 2 – values of degrees of scales of binary positions in a cortege of conjuncterms of the transformed PSTF , where a dash (–) must be. For example, let the generating element of the pair         be the minterm(). Then, if the first element of the matrix is () and this number 0 (for dash in 20), we will have two variants of dis- position of dashes: the first one will be represented by the column         2 1 0 , and so PSTF              , the second –         1 2 0 , and so PSTF              . We will show creation of a set of transformed PSTF on the examples of two conjuncterms that have d  3 and common part in position 21 and 24:                                                                                    110 011 011 , 111 111 011 , 101 100 010 , 110 001 010 , 111 111 101 , 101 110 101 1110 0101 , that is                                                                27,26,25,24 30,28,26,24 30,28,22,20 , 31,29,27,25 31,30,29,28 30,28,22,20 , 27,25,19,17 19,18,17,16 22,20,18,16 , 27,26,25,24 26,24,18,16 22,20,18,16 , 31,29,27,25 31,29,23,21 23,22,21,20 , 27,25,19,17 23,21,19,17 23,22,21,20 27,25 22,20 . So, for d  3 in general case one can write:                                                                                              ,,,,, . (4) 4 0 6 2 1 5 3 7 (00) (0  1) (11) 4 0 6 2 1 5 3 7 4 0 6 2 1 5 3 7 4 0 6 2 1 5 3 7 4 0 6 2 1 5 3 7 4 0 6 2 1 5 3 7 44 УСиМ, 2015, № 2 For (4) k * / kl *  3/ 6 is indicative of an increase of power of each transformed PSTF and un- changeability of number of their literals as initial interrelation k / kl  2 / 6; kY  6. The following analytical expressions correspond to the transformed PSTF (4):                 abcacb acbacb bcbaca abcbca accbba bccaba abccba , where the first equation, for example, can be got this way:  abccbabaabccbaabccba )1( .)1()1( bccabaabcbcacabaabcbcacabaabccbaba   Let d  4 . Then for )( 11 nlkji r  and )( 12 nlkji r  , where }1,0{,,,  lkji , matrix of disposition of dashes will have the scale 244 , namely:             012012301301230230123123 100221033110322003211332 221100110033003322332211 333333222222111111000000 , where 0, 1, 2, 3 – values of degrees of scales of binary positions in the cortege of conjunc- terms of each transformed PSTF , what is reflected by columns of matrix. On the ground of the matrix of disposition of dashes for the case d  4 we will get a set from 24 transformed PSTF , each of them consists of 4 conjuncterms of 3-rank:                                                                                                                ,,,,,, ,,,,,,                                                                                                 (5) ,,,,,,                                                                                                                                                                                                       ,,,,, . УСиМ, 2015, № 2 45 For example, let        1. Then for function f (,, ,) the set (5) will look like:                                                                                                              , 111 011 001 000 , 111 110 001 000 , 111 101 010 000 , 111 101 010 000 , 111 011 100 000 , 111 110 100 000 1111 0000 (5) , 111 011 001 000 , 111 110 001 000 , 111 101 010 000 , 111 101 010 000 , 111 011 100 000 , 111 110 100 000                                                                                                 (5) , 111 011 001 000 , 111 110 001 000 , 111 101 010 000 , 111 101 010 000 , 111 011 100 000 , 111 110 100 000                                                                                                 (5)                                                                                                       111 011 001 000 , 111 110 001 000 , 111 101 010 000 , 111 101 010 000 , 111 011 100 000 , 111 110 100 000 . (5) Fig. 2 8 12 10 14 6 1 5 3 7 In Fig. 2 we see a pattern of the function f (,,,), on which we have one of examples (5) of forma- tion of a set of edges starting with vertex 0 up to vertex 15, that corresponds to formation of a set of con- juncterms of 3-rank PSTF in case of transformation of a pair of minterms (0000) and (1111), distance between them d  4, i.e.                    15,11 11,9 9,1 1,0 15 0 , that is                        111 110 001 000 1111 0000 . So, for (5) k * / kl *  4 /12 is indicative of an increase of power of transformed PSTF and the num- ber of literals, as the initial interrelation k / kl  2 / 8; kY  24. In the case of necessity for any pair of conjuncterms of r-rank of a function f , that have distance d  4, one can in analogical way form a set of d! transformed PSTF ; d 1,2,..., n. So, on the ground of the considered above one can state that two conjuncterms of r-rank 1 r and 2 r function f, that differ d 1,2,..., n in different by values onename binary positions }1,0{,...,,,  , 46 УСиМ, 2015, № 2 form in polynomial format a set with з kY  d! of transformed PSTF , each of them consists of different conjuncterms of (r 1)-rank with interrelation k * / kl *  d / d(d 1), that proves truth of theorem 1.  Efficiency of application of theorem 1 for simplification of a set of conjuncterms and obtaining minimal PSTF of a given function f is illustrated by examples given further. Here the cost of realization of minimized function f will be estimated by comparison of numeric interrelation k * / kl * and k / kl. Example 1. To apply theorem 1 to the function f (x1, x2, x3 , x4 ) , given by perfect STF Y1 {0,6,14,15}1, which in polynomial format has been minimized by xlinking method [21, p. 28], as the result of what we have got solution PSTF , where k / kl = 3/10. Solution . For minterms (0111),(0000) we will apply theorem 1 for d  3 rule (4):                                                                                    011 001 000 , 101 010 000 , 110 001 000 , 011 100 000 , 101 010 000 , 110 100 000 0111 0000 . Having changed (0111) and (0000) by marked (underlined) PSTF , we will get two solutions: . Underlined conjuncterms are simplified by merging operation [30]: , that corresponds to the expression . So the given function f has two solutions of mini- mization that reflect minimal PSTF: 1.   )}100(),000(),111{(Y ; 2.   )}000(),001(),111{(Y . Answer. The cost of realization of minimized function f is equal to k * / kl *= 3/9 and is better than in [21]. Let us consider the case when one conjuncterm of (r 1)-rank 1 r1 differs from another conjuncterm of r-rank 2 r in one dash (–), and other onename positions }1,0{,...,,,  . Theorem 2. Two conjuncterms of the function f ( x1, x2,..., xn), one of which of (r 1)-rank 1 r1 dif- fers from another r-rank 2 r in the number of d different in values onename positions },1,0{,...,,,  , among which the dash (–) belongs to the conjuncterm 1 r1, },...,2,1{ nr , in polynomial set-theoretical format create kY  (d 1)! of sets PSTF , each of them has power k *  d and the total number of lit- erals in different part kl *  d(d 1)  (d  2), here:  if d 1, then )~(~          ; (6)  if d  2, then                  ~~ ,                  ~~ ; (7)  if d  3, then , ,                                        , ,                                                                                               ~ , ~ ~ , (8), (9), (10) УСиМ, 2015, № 2 47  if d  4, then                                                                                                                        ~ , ~ , ~ , ~ , ~ , ~ ~ , (11)                                                                                                                      ~ , ~ , ~ , ~ , ~ , ~ ~ , (12)                                                                                                                        ~ , ~ , ~ , ~ , ~ , ~ ~ , (13)                                                                                                                        ~ , ~ , ~ , ~ , ~ , ~ ~ , (14) where  ~,~,~,~ – binary positions of any value 0 or 1. Proof. In this case the given PSTF has interrelation k / kl  2 /(2d 1).  Let d 1. Then )( 1 1 1 ni r   , )~( 12 ni r  , }1,0{~  i , and respectively for the expression aa ~~1  , },{~ aaa  , we can write down such PSTF :   )}~{()}~(),{( 111 nininiY . As interrelation k * / kl * 1/1, then compared with k / kl  2 /1 we have simplification of the given PSTF due to removal of one conjuncterm; kY 1. For example, corresponds to and .  Let d  2 . Then for )( 1 1 1 nji r   and )~( 12 nji r  and )( 1 1 1 nji r   and )~( 12 nji r  , }1,0{,  ji , and respectively to the expres- sions babaabaa ~1)~1(~  and bababbab ~1)1~(~  , },{~ aaa  , },{~ bbb  , we will get   )}~(),{()}~(),{( 1111 njinjinjinjiY and   )}~(),{()}~(),{( 1111 njinjinjinjiY . Comparing the obtained interrelation k * / kl *  2 / 2 with k / kl  2 / 3, we see that formed PSTF is simpler than the given PSTF for one literal. For example, having applied the rule (7) of theorem 2 to f (,), }1,0{,  , we will get: 48 УСиМ, 2015, № 2                             11 01 0 10 0 ,                             10 00 1 11 0 ,                             01 11 0 00 1 ,                             00 10 1 01 1 . It should be mentioned that a number of transformed PSTF is determined by a number of binary positions in different part 1 r1 and 2 r, which conforms to theorem 1. Therefore for d  2 we have kY 1.  Let d  3 . Then for )( 1 1 1 nkji r   and )~( 12 nkji r  , )( 1 1 1 nkji r   and )~( 12 nkji r  and )( 1 1 1 nkji r   and )~( 12 nkji r  , and respectively to the expressions       ba ba cabcabbacabba ~)~1(~ ,       ca cacbacbaca ~~ and      cb cbbcabcacb ~~ , },{~ aaa  , },{~ bbb  , },{~ ccc  , we have:   )}~(),{( 11 nkjinkjiY             )~(),(),( )~(),(),( 111 111 nkjinkjinkji nkjinkjinkji ,   )}~(),{( 11 nkjinkjiY             )~(),(),( )~(),(),( 111 111 nkjinkjinkji nkjinkjinkji ,   )}~(),{( 11 nkjinkjiY             )~(),(),( )~(),(),( 111 111 nkjinkjinkji nkjinkjinkji . The obtained interrelation k * / kl *  3/ 5 is indicative of an increase in one conjuncterm for k / kl  2 / 5. Whereas kY  2 and as a result of the fact that the given conjuncterms (8) have two binary positions in common which are transformed for d  2 according to the rule (3) of theorem 1. This is illustrated (look at dotted lines) .  Let d  4. Then on the ground of the considered above, taking into account the rule (4) of theorem 1 for d  3 (three binary positions are common), it is not hard to state that for )( 1 1 1 nlkji r   і )~( 12 nlkji r  , )( 1 1 1 nlkji r   і )~( 12 nlkji r  , )( 1 1 1 nlkji r   і )~( 12 nlkji r  , )( 1 1 1 nkji r   і )~( 12 nkkji r  , УСиМ, 2015, № 2 49 the interrelation k * / kl *  4 /10, which compared with k / kl  2 / 7 is indicative of an increase of num- ber of conjuncterms as well as their literals; kY  6. For example, , that corresponds to                                                                                            14 15,14,13,12 13,12,9,8 9,8,1,0 , 14 15,14,11,10 11,10,9,8 9,8,1,0 , 14 15,14,13,12 13,12,5,4 5,4,1,0 , 14 15,14,7,6 7,6,5,4 5,4,1,0 , 14 15,14,11,10 11,10,3,2 3,2,1,0 , 14 15,14,7,6 7,6,3,2 3,2,1,0 15 1,0 . So, if a conjuncterm of (r 1)-rank 1 r1 differs from a conjuncterm of r-rank 2 r in the number d of different by value onename positions },1,0{,...,,,  , here dash (–) belongs to 1 r1, },...,2,1{ nr , then (d 1)! of sets PSTF will be formed, each of which has the interrelation k * / kl *  d /(d(d 1)  (d  2)), that proves the truth of theorem 2.  For example, let the function f (x1, x2, x3 , x4 ) has PSTF   )}0110(),000(),010(),11{(Y , where distance between any pair of conjuncterms d  3, а 12/4/  lkk . If the function that has canoni- cal STF Y1 {0,1,6,8,11,14,15}1 , is minimized in disjunctive format, then we get STF Y1 {(000),(000),(110),(111)}1, which also has 12/4/  lkk . But such interrelation can be im- proved if theorem 2 is applied to the underlined pair PSTF namely rule (8), that is , and having got                          0111 10 00 ),010(),11(Y , one should apply to the under- lined pairs of this set the rule (2) and the rule (7) . Then we get minimal PSTF , which if compared with the previous result has better interrelation 9/4/  lkk . Application of rules of theorems 1 and 2 is further illustrated by the examples. Example 2. To apply the rules of theorems 1 and 2 to the function given by f (x1, x2, x3 , x4 , x5 ) , PSTF (distances d between all pairs of conjuncterms are shown on the right of ) , where 22/6/  lkk . 2 3 4 3 3 4 3 2 4 3 5 3 4 5 4 50 УСиМ, 2015, № 2 Solution. We apply theorem 1 for d  4 to the minterms (00000) and (11110) having chosen from (5) the six transformed PSTF :                        1110 0011 0001 0000 11110 00000 . Then after corresponding change we apply the rule (6) of theorem 2 to the pairs of elements of the formed set that have d 1 , namely: )0000(0001 000          , )0100(0000 000          , )0110(1110 110          . As a result of this we get PSTF                       0011 0110 111 0100 0000 Y , where k * / kl * = 5/19 is better than the initial 22/6/  lkk . Example 3. To apply the rules of theorems 1 and 2 to the function f (x1, x2, x3, x4 ), given by PSTF   )}011(),00(),11(),1011(),000{(Y , that has 14/5/  lkk . Solution. All pairs of conjuncterms in given PSTF Y have 3d , except (1011), (11), for d  2 , transformation of which does not simplify the given set. Let us apply, for example, to the pair (000), (1011), that has d  4, theorem 2, having chosen from the rule (13) the fifth set:                        1111 11 01 00 1011 000 . Now                                )011(),00(),11(, 1111 11 01 00 Y and after the rule (3)                  1 0 11 00 we have                                 )011(),00(),1(, 1111 11 01 0 Y  )}011(),00(),1111(),10(),00{( . Further, according to the rules (10)                     111 0 1 011 00 and (7) )01(0 00          and )1110(111 1111         we will get a minimal PSTF   )}1110(),1(),10(),01{(Y . Answer. Cost of realization of the minimized function k * / kl * = 4/9 is better than 14/5/  lkk . Let us consider now the situation when two conjuncterms of r-rank 1 r and 2 r differ in d onename bi- nary positions },1,0{,...,,,  , here each of them has one dash (–). Theorem 3. Two conjuncterms of r-rank 1 r and 2 r , },...,2,1{ nr , of the function f (x1, x2,..., xn) dif- fer in d onename binary positions },1,0{,...,,,  , where each conjuncterm has one (–), in polyno- mial set-theoretical format starting with d  2 , create kY  (d 2)! of sets PSTF Y , each of which has power k *  d and the total number of literals in the different part kl *  d(d1)2(d 2), here: УСиМ, 2015, № 2 51  if d  2 , than                    ~ ~ ~ ~ , (15)  where 3d , than                       ~ ~ ~ ~ ,                       ~ ~ ~ ~ ,                       ~ ~~ ~ , (16), (17), (18)  if d  4, than                                                            ~ ~, ~ ~~ ~ ,                                                              ~ ~, ~ ~~ ~ , (19), (20)                                                            ~ ~, ~ ~~ ~ ,                                                            ~ ~, ~ ~~ ~ , (21), (22)                                                            ~ ~, ~ ~~ ~ ,                                                            ~ ~, ~ ~~ ~ , (23),(24) where  ~,~,~,~ – binary positions of any value 0 or 1. Proof. Given PSTF Y has the initial interrelation k / kl  2 / 2(d1).  Let d  2 . Then )~( 11 nji r  and )~( 12 nji r  , }1,0{~,~  ji . For ),( baf respectively to (15) we have bababa ~~)1~()1~(~~  , that corresponds to PSTF   )}~(),~{()}~(),~{( 1111 njinjinjinjiY . Here the interrelation 2/2// **   ll kkkk that is indicative of unchangeability of parameters of the transformed PSTF Y , in which only inversion of different positions took place; kY 1.  Let d  3 . Then )~( 11 nkji r  and )~( 12 nkji r  , )~( 11 nkji r  and )~( 12 nkji r  and )~( 11 nkji r  and )~( 12 nkji r  , }1,0{~,~,~  kji . For f (a,b,c) respectively to (16–18) we have: 1~~)1~()1~(~~  cbbacbbacbba , 1~~~~  cabacaba and 1~~~~  cbcacbca , },{~ aaa  , },{~ bbb  , },{~ ccc  . So, corresponding PSTF Y will look like:   )}~(),~{( 11 nkjinkjiY  )}~(),~(),{( 111 nkjinkjinkji ,   )}~(),~{( 11 nkjinkjiY 52 УСиМ, 2015, № 2  )}~(),~(),{( 111 nkjinkjinkji ,   )}~(),~{( 11 nkjinkjiY  )}~(),~(),{( 111 nkjinkjinkji . Compared with k / kl  2 / 4 here the interrelation k * / kl *  3 / 4 means that the transformed PSTF Y has one more conjuncterm, here its rank is (r 3); kY 1. For example, for some values of variables }1,0{,,  of the function f (,, ) we will get such PSTF Y : (16)                     10 1011 00 ,                     01 0111 00 ; (17)                     01 0111 00 ,                     10 1011 00 ; (18)                     01 0111 00 ,                     10 1011 00 .  Let d  4. Then )~( 11 nlkji r  and )~( 12 nlkji r  , )~( 11 nlkji r  and )~( 12 nlkji r  , )~( 11 nlkji r  and )~( 12 nlkji r  , )~( 11 nlkji r  and )~( 12 nlkji r  , )~( 11 nlkji r  and )~( 12 nlkji r  , )~( 11 nlkji r  and )~( 12 nlkji r  . The transformations (19–24) are formed on the ground of respective expressions for f (a,b,c, d):      cb cbdbccbabccbdbccbadbccbadbccba ~~~~)1~()1~(~~ ,       ca cadaccbadaccba ~~~~ ,       ba ba dabcbadabcba ~~~~ ,       db dbdcbdbadcbdba ~~~~ ,       da da dcadbadcadba ~~~~ ,       dc dc cdbdcacdbdca ~~~~ and, },{~ aaa  , },{~ bbb  , },{~ ccc  , },{~ ddd  . Not giving general expressions of the formed PSTF Y , that are evident from the considered above, we will illustrate the transformations (19–24) for some values }1,0{,,,  of the function f (,, ,): (19–21)                                                      110 100 0 1 , 110 100 1 0 111 000 ;                                                      101 010 0 1 , 101 010 1 0 111 000 ;                                                      011 001 0 1 , 011 001 1 0 111 000 ; УСиМ, 2015, № 2 53 (22–24)                                                      101 010 0 1 , 101 010 1 0 111 000 ;                                                      011 001 0 1 , 011 001 1 0 111 000 ;                                                      011 001 0 1 , 011 001 1 0 111 000 . Dotted lines in (19) show general tendency of the formed PSTF Y , which consists in formation of two subsets: one respectively to theorem 1 (for d  4 according to the rule (3)), and another one that repeats given conjuncterms with certain inverse positions. This is illustrated by the example of formation of PSTF Y for d  5 :                               1110 1000 11 10 00 1111 0000 , that corresponds to                        30,14 17,16 31,30,23,22,15,14,7,6 23,22,19,18,7,6,3,2 19,18,17,16,3,2,1,0 31,15 1,0 . Here, for d  4 the interrelation k * / kl *  4 / 8 is greater than the initial one k / kl  2 / 6; kY  2. So, if two conjuncterms of r-rank 1 r і 2 r , },...,2,1{ nr , of the function f (x1, x2,..., xn) differ in d dif- ferent by values onename positions },1,0{,...,,,  , among which each of these conjuncterms has one dash (–), then in polynomial set-theoretical format, starting with 2d , they form kY  (d 2)! of the sets PSTF Y , each of them has ))2(2)1(/(/ **  ddddkk l , and this is proved by theorem 3.  Application of the rules of theorems 1, 2 and 3 will be illustrated by the examples. Let PSTF of the function f (x1, x2, x3, x4 )   )}1(),01(),000(),111{(Y , the cost of reali- zation of which 9/4/  lkk . If the given PSTF Y is simplified only according to the rules for 3d , for example, to the pair (111) і (01), that has d  2 , the rule (7) of theorem 2, is applied, namely                  110 1 01 111 , we will get PSTF                  110 1),1(),000(Y with  ** / lkk 4/8. However, if to the pair (111) and (0 00), that has d  4, the second set of the rule (20) of theorem 3 is applied                          010 101 1 0 000 111 , then after respective transformation we will get                                   )}010(),101(),00{()1(),01(, 010 101 1 0 )}1(),01(),000(),111{(Y . Here, having applied to the pair (00) and (101), that has d  3, the rule (7) of theorem 2, namely                  100 0 101 00 , we will get the final minimal PSTF of the given function f   )}010(),100(),0{(Y , 54 УСиМ, 2015, № 2 The cost of realization of which  ** / lkk 3/7 is better than the previous one. Example 4. To apply the theorems 1, 2 and 3 to the function f (x1, x2, x3, x4 ), that is given by perfect STF Y1  {0,3, 5, 6, 7,8, 9,10,12,15}1, which is minimized in polynomial format by K-maps method to the expression 432143214342321 xxxxxxxxxxxxxxxf  [32, с. 97]. Solution. This function has PSTF   )}0000(),1111(),11(),11(),11(),1{(Y . To the pair (1111) і (0000), that has d  4, we will apply, for example the fourth PSTF from the rule (5):                                111 101 010 000 ),11(),11(),11(),1(Y . Applying to the underlined pairs that have 1d , the rule (6) of theorem 2, namely )111(101 11          , )011(111 11          , and the rule (7), in the formed set namely                  010 1 11 011 , we will get PSTF   )}010(),111(),000(),010(),1(),1{(Y . Doing further transformations according to the rules (16) and (17) of theorems 3, namely                       011 100 0 000 010 and                     110 000 0 010 100 , we will get the fi- nal minimal PSTF   )}111(),110(),000(),011(),0(),0(),1(),1{(Y  )}111(),110(),000(),011(),1(),1( . Now the cost of realization of the minimized function 42132143143221 xxxxxxxxxxxxxxf  is equal to  ** / lkk 6/14 that is a better result if compared to [32], where 15/6/  lkk . 1.3. Estimate of efficiency of application of the suggested rules Let us estimate efficiency of application of theorems 1, 2 і 3 for simplification of the sets of conjunc- terms of the function f in polynomial set-theoretical format. On the ground of the considered above one can draw such a conclusion:  the number of the conjuncterms composing the transformed k * , PSTF Y of the function f, is di- rectly proportional to distance d between the pair of the given conjuncterms which in the different part have the total number of the literals )}1(2),12(,2{  dddkl , that is k *  d;  the power kY of the set of the transformed PSTF Y in the combinative way depends on distance d, here if kl  2d , then kY  d!; if kl  2d1, then kY  (d1)!; starting with 2d , if kl  2(d1) , then kY  (d 2)!;  the quantitative estimation of efficiency of application of theorem 1 (Т1), theorem 2 (Т2) and theo- rem 3 (Т3) is shown in the table of dependence of the interrelation of Yll kkk // * on distance d: d Т1 Т2 Т3 1 2 3 4 5 6 ... 2/0/1 4/2/2 6/6/6 8/12/24 10/20/120 12/30/720 ... 1/1/1 3/2/1 5/5/2 7/10/6 9/17/24 11/26/120 ... – 2/2/1 4/4/1 6/8/2 8/14/6 10/22/24 ... УСиМ, 2015, № 2 55 From the data of the table it is seen that starting with d  3, simplification of two conjuncterms of the function f does not take place. This is eventually stated by the authors [7,14,15,21,24], who on this ground draw a conclusion that it is not expedient to do further minimization in polynomial format of the function f, if between any pair of its conjuncterms distance 3d . However, it is evident from the con- sidered above that this statement is false. The given examples in this and next papers on this theme are indicative of the fact that application of the suggested theorems to the function f, which is not given by two but greater number of conjuncterms of different ranks between any pairs of which distance d is dif- ferent it is quite possible to do further simplification. The explanation is set that the set of the trans- formed PSTF Y , by which the chosen pair with distance 3d is replaced, can have elements which together with other elements of the given function f will form pairs with distance d  3. Here, in spite of an increase of power of the newformed set, one can get a minimal PSTF Y after application of respec- tive rules of the suggested theorems to the pairs with little d. Besides with an increase of d the probabil- ity of simplifications is greater as it is seen from the table here the power of kY formed PSTF Y in- creases, so there is a better choice of useful for simplification elements. The procedure of search of such elements has a combinative character – after each replacement of a chosen pair of conjuncterms of the given PSTF Y for certain set of the transformed PSTF Y we get a new set in which it is necessary to determine distance d between new pairs and having chosen from them the elements with minimal d, to apply the rules of respective theorem and build again a new set and so on and so forth (algorithm de- scription of suggested minimization method in the next paper 2). It should also be noted that application of the suggested rules of simplification of a set of conjuncterms of the given PSTF Y to the pairs with distance 3d makes it possible to get the searched result with fewer number of steps of simplification procedure. Let us illustrate this by the examples. Example 5. To apply the suggested theorems to the function f (x1, x2, x3, x4 ) , given by PSTF   )}1010(),11(),110(),000{(Y , on the example of which [20, example 8, p. 388] the authors show efficiency of exorlink method. Solution. Let the difference d  3 between any pair of conjuncterms of the given PSTF Y . The minimal PSTF   )}1111(),10(),00{(Y is got within five procedure steps with the help of exor- link method. We will show that the same result can be got within 4 steps                                                                                 1111 10 00 1111 00 1 00 110 1011 00 11 110 11 1 110 1011 11 01 1010 000 Y , where in bold font the elements are highlited which are formed according to certain rule of one from the sug- gested theorems. For example, for the first step the chosen pair        1010 000 is transformed according to the rule (8) of theorem 2 so:                   1011 01 00 1010 000 . After respective change in the second step we apply the rule (2) of theorem 1 to the pair )1(11 01          , in the third step the rule (7) of theorem 2 to the pair                1111 11 110 1011 and in the fourth step the rule (2) of theorem 1 to )10(11 1          . 56 УСиМ, 2015, № 2 Example 6. To apply the suggested theorems to the function dcaabdcbacadcbaf ),,,( , on the example of which the authors [15, p. 6] show on the K-maps efficiency of their suggested procedure (look-ahead strategiesof the improved exorlink method. Solution. The given function f has PSTF   )}011(),11(),0100(),00{(Y . If we apply in the first step the rule (9) of theorem 2 to the elements        011 0100 , that have d  3 , namely                                     0000 01 00 , 0000 00 01 011 0100 , then we get two variants: 1)                                                                 0000 01 11 0000 11 0000 00 11 11 00 00 001 00 011 0100Y and 2)                                                 0000 01 11 0000 01 11 11 00 00 00 011 0100Y , out of which the second solution, as we see it, is simpler and shorter. So, the given function has the minimal PSTF   )}0000(),01(),11{(Y , to which corresponds dcabdcbadcbaf ),,,( . In [15] the same result is got in a more complicated way and within a greater number of steps. Conclusions The generalized set-theoretical rules of simplification in the polynomial format of a set of conjunc- terms of different ranks of a logic function with n variables have been suggested. These rules are based on three theorems for certain initial conditions of transformation of a pair of conjuncterms with any Hamming distance between them. Efficiency of the suggested rules is proved by given in the paper exam- ples which have been borrowed from the papers by well-known authors with the aim of comparison and which give the ground to confirm their expediency in application for minimization of any logic function from n variables in polynomial format. 1. Besslish P.W. Efficient computer method for EXOR logic design // IEEE Proc. Pt. E. – 1983. – 130. – P. 203–206. 2. Sasao T. Switching Theory for Logic Synthesis. – Kluwer Acad. Publ. – 1999. – 361 p. 3. Papakonstantinou G. A Parallel algorithm for minimizing ESOP expressions // J. Circuits Syst. Comp. – 2014. – 23, issue 01. – 17 p. 4. Saul J. Logic synthesis for arithmetic circuits using the Reed–Muller representation / Proc. of Europ. Conf. on Design Automation // IEEE Comp. Society Press, March 1992. 5. Perkowski M., Chrzanowska–Jeske M. An exact algorithm to minimize mixed–radix exclusive sums of products for incompletely specified boolean functions // Proc. Int. Symp. Circuits Syst. – New Orleans, LA, May 1990. – P. 1652–1655. 6. Tsai C., Marek-Sadowska M. Multilevel Logic Synthesis for Arithmetic Functions // Proc. DAC’96. – June 1996. – P. 242– 247. 7. Takashi Hirayama, Yasuaki Nishitani. Exact minimization of AND-EXOR expressions of practical benchmark func- tions // J. of Circuits, Systems and Computers. – 2009. – 18, N 3. – P. 465–486. 8. Debnath D., Sasao T. Output phase optimization for AND-OR-EXOR PLAs with decoders and its application to design of adders // IEICE Trans. Inf. & Syst. – July 2005. – E88-D, N 7. – P. 1492–1500. 9. Fujiwara H. Logic testing and design for testability // Comp. Syst. Series. – Cambridge, MA: Mass. Inst. Tech., 1986. 10. Sasao T. Easily testable realizations for generalized Reed–Muller expressions // IEEE Trans. On Computers. – 1997. – 46, N 6. – P. 709–716. 11. Faraj Khalid. Design Error Detection and Correction System based on Reed–Muller Matrix for Memory Protection // J. of Comp. Appl. (0975-8887). – Nov. 2011. – 34, N 8. – P. 42–55. 12. Exact ESOP expressions for incompletely specified functions / M. Sampson, M. Kalathas, D. Voudouris et al. // VLSI J. – 2012. – 45, issue 2. – P. 197–204. УСиМ, 2015, № 2 57 13. Stergiou S., Papakonstantinou G. Exact minimization of ESOP expressions with less than eight product terms // J. of Circuits, Systems and Comp. – 2004. – 13, N 1. – P. 1–15. 14. Debnath D., Sasao T. A New Relation of Logic Functions and Its Application in the Desing of AND-OR-EXOR Net- works // IEICE Trans. Fundamentals. – May 2007. – E90-A, N 5. – P. 932 – 939. 15. Mishchenko A., Perkowski M. Fast Heuristic Minimization of Exclusive-Sums-of-Products // Proc. Reed–Muller Inter. Workshop’01. – 2001. – P. 242–250. 16. Wu X., Chen X., Hurst S. L. Mapping of Reed–Muller coefficients and the minimization of exclusive-OR switching function // IEEE Proc. Pt. E. – Jan. 1982. – 129. – P. 5–20. 17. Fleisher H., Tavel M., Yager J. A computer algorithm for minimizing Reed–Muller cannonical forms // IEEE Trans. Comput. – Feb. 1987. – C-36. – P. 247–250. 18. Even S., Kohavi I., Paz A. On minimal modulo-2-sum of products for switching functions // Ibid. – Oct. 1967. – EC-16. – P. 671–674. 19. Helliwell M., Perkowski M. A fast algorithm to minimize mixed polarity generalized Reed–Muller forms. In Proceed- ings of the 25th ACM/IEEE Design Automation Conference // IEEE Comp. Society Press. – 1988. – P. 427–432. 20. Song N., Perkowski M. Minimization of Exclusive Sum-of-Products Expressions for Multiple-Valued Input, Incom- pletely Specified Functions // IEEE Trans. Comput.-Aided Design of Integrated Circuits and Systems. – April, 1996. – 15, N 4. – P. 385–395. 21. Saul J. Logic synthesis based on the Reed–Muller representation, 1991 – http://citeseer.uark.edu:8080/citeerx/viewdoc/ summary;jsessionid=A765F8A29F4FB9D2143A1DB7CDC91593?doi=10.1.1.45.8570 22. Zakrenskij A. Minimum Polynomial Implementation of Systems of Incompletely Specified Functions // Proc. of IFIP WG 10.5 Workshop on Applications of Reed–Muller Expansion in Circuits Design 1995, Japan. – P. 250–256. 23. Brand D., Sasao T. Minimization of AND-EXOR Using Rewrite Rules // IEEE Trans. on Comp. – May 1993. – 42, N 5. 24. Knysh D., Dubrova E. Rule-Based Optimization of AND-XOR Expressions // Facta Universitatis (Nis), Ser.: Elec. En- erg. – Dec. 2011. – 24, N 3. – P. 437–449. 25. Wang L. Automated Synthesis and Optimization of Multilevel Logic Circuits, 2000 – http://researchrepository.napier. ac.uk/4342/1/Wang.pdf 26. Stergiou S., Daskalakis K., Papakonstantinou G. A Fast and Efficient Heuristic ESOP Minimization Algorithm // GLSVLSI’04. – Boston, Mass., USA, April 26–28 2004. 27. Рицар Б.Є. Мінімізація бульових функцій методом розчеплення кон’юнктермів // УСИМ. – 1998. – № 5. – С. 14–22. 28. Рицар Б.Є. Теоретико-множинні оптимізаційні методи логікового синтезу комбінаційних мереж: Дис. д. т.н. – Львів, 2004. – 348 с. 29. Рицар Б.Є. Мінімізація системи логікових функцій методом паралельного розчеплення кон’юнктермів // Вісн. НУ ЛП «Радіоелектроніка та телекомунікації». – 2013. – № 766. – С. 18–27. 30. Рицар Б.Є. Числова теоретико-множинна інтерпретація полінома Жеґалкіна // УСИМ. – 2013. – № 1. – С. 11–26. 31. Рицар Б.Є. Візерунки бульових функцій: метод мінімізації // УСИМ. – 2007. – № 3. – С. 34–51. 32. Tran A. Graphical method for the conversion of minterms to Reed–Muller coefficients and the minimization of exclu- sive-OR switching functions // IEEE Proc. – March 1987. – 134, Pt.E, N 2. – P. 93–99. 33. Tinder R.F. Engineering digital design. – Academic Press, 2000. – 884 p. Поступила 30.12.2014 E-mail: bohdanrytsar@gmail.com © Б.Е. Рыцар, 2015  << /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
id nasplib_isofts_kiev_ua-123456789-87194
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 0130-5395
language English
last_indexed 2025-12-07T16:31:25Z
publishDate 2015
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
record_format dspace
spelling Rytsar, B.Ye.
2015-10-14T11:14:22Z
2015-10-14T11:14:22Z
2015
New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification / B.Ye. 04-Rytsar // Управляющие системы и машины. — 2015. — № 2. — С. 39–57. — Бібліогр.: 33 назв. — англ.
0130-5395
https://nasplib.isofts.kiev.ua/handle/123456789/87194
519.718
A generalized simplify rules of conjuncterms in polynomial set-theoretical format is considered. These rules are based on the proposed theorems for different initial transform condition of pair conjuncterms where hamming distance between them can be arbitrary. These rules may be useful to minimize in polynomial set-theoretical format of arbitrary logic functions of n variables. Advantages of the proposed rules are illustrated by the examples.
Рассмотрены обобщенные правила упрощения конъюнктермов в полиномиальном теоретико-множественном формате, основанные на предложенных теоремах для разных начальных условий преобразования пары конъюнктермов, хеммингово расстояние между которыми может быть произвольным. Упомянутые правила могут быть полезными для минимизации в полиномиальном теоретико-множественном формате произвольных логических функций от n переменных. Преимущества предложенных правил проиллюстрированы примерами.
Розглянуто узагальнені правила спрощення кон’юнктермів у поліноміальному теоретико-множинному форматі, які ґрунтуються на запропонованих теоремах для різних початкових умов перетворення пари кон’юнктермів, геммінгова відстань між якими може бути довільна. Зазначені правила можуть бути корисні для мінімізації у поліноміальному теоретико-множинному форматі довільних логічних функцій від n змінних. Переваги запропонованих правил проілюстровано прикладами.
en
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
Управляющие системы и машины
Новые методы в информатике
New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
Новый метод минимизации логических функций в полиномиальном теоретико-множественном формате. 1. Обобщенные теоретико-множественные правила упрощения конъюнктермов
Новий метод мінімізації логікових функцій у поліноміальному теоретико-множинному форматі. 1. Узагальнені теоретико-множинні правила спрощення кон’юнктермів
Article
published earlier
spellingShingle New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
Rytsar, B.Ye.
Новые методы в информатике
title New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
title_alt Новый метод минимизации логических функций в полиномиальном теоретико-множественном формате. 1. Обобщенные теоретико-множественные правила упрощения конъюнктермов
Новий метод мінімізації логікових функцій у поліноміальному теоретико-множинному форматі. 1. Узагальнені теоретико-множинні правила спрощення кон’юнктермів
title_full New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
title_fullStr New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
title_full_unstemmed New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
title_short New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification
title_sort new minimization method of logical functions in polynomial set-theoretical format. 1. generalized rules of conjuncterms simplification
topic Новые методы в информатике
topic_facet Новые методы в информатике
url https://nasplib.isofts.kiev.ua/handle/123456789/87194
work_keys_str_mv AT rytsarbye newminimizationmethodoflogicalfunctionsinpolynomialsettheoreticalformat1generalizedrulesofconjunctermssimplification
AT rytsarbye novyimetodminimizaciilogičeskihfunkciivpolinomialʹnomteoretikomnožestvennomformate1obobŝennyeteoretikomnožestvennyepravilauproŝeniâkonʺûnktermov
AT rytsarbye noviimetodmínímízacíílogíkovihfunkcíiupolínomíalʹnomuteoretikomnožinnomuformatí1uzagalʹneníteoretikomnožinnípravilasproŝennâkonûnktermív