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...
Saved in:
| Published in: | Управляющие системы и машины |
|---|---|
| Date: | 2015 |
| Main Author: | |
| 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
6lk , and the second – 5lk . 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 1d 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
r1 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
r1 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
r1, },...,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
r1 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
r1 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
r1, },...,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),(111)}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 3d , except (1011), (11), for d 2 ,
transformation of which does not simplify the given set. Let us apply, for example, to the pair
(000), (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(d1)2(d 2), here:
УСиМ, 2015, № 2 51
if d 2 , than
~
~
~
~
, (15)
where 3d , 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(d1).
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 2d , 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 3d ,
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 1d , 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 2d1, then kY (d1)!; starting with 2d , if kl 2(d1) , 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 3d . 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 3d 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 3d 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 |