A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II
The article describes a new method for the recognition of different types of total and partial symmetry in boolean functions based on the numeric set-theoretical differentiation. The proposed algorithm is based on the theorem on the recognition of different types of partial symmetry. This algorithm,...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2019
|
| Назва видання: | Control systems & computers |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/181044 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II / B.Ye. Rytsar // Control systems & computers. — 2019. — № 5. — С. 5-11. — Бібліогр.: 22 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-181044 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1810442021-10-31T01:27:04Z A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II Rytsar, B.Ye. Fundamental Problems in Computer Science The article describes a new method for the recognition of different types of total and partial symmetry in boolean functions based on the numeric set-theoretical differentiation. The proposed algorithm is based on the theorem on the recognition of different types of partial symmetry. This algorithm, compared to the known, has a relatively less computational complexity of realization due to a comparatively smaller number of operations and procedures necessary for the accomplishment of the given task. This is evidenced by the presented examples for the recognition of the proposed method of the different types of symmetry in complete and incomplete of Boolean functions, including given in the SOP format, borrowed for comparison reasons from publications of wellknown authors. Мета статті — розробити простий для реалізації метод розпізнавання різних типів повних і частинних симетрій як у повних, так і частково заданих булових функціях. Методи. У статті запропоновано новий метод розпізнавання різних типів повних і частинних симетрій, таких як полісиметрія, проста симетрія та антисиметрія, як у повністю, так і частинно заданих функціях на основі числового теоретико-множинного логікового диференціювання. Алгоритм методу ґрунтується на теоремі про розпізнавання різних типів частинних симетрій, який, порівняно з відомими, має відносно меншу обчислювальну складність за рахунок порівняно меншої кількості операцій і процедур, потрібних для виконання поставленої задачі. Цель статьи — разработать простой в реализации метод распознавания разных типов полных и частичных симметрий, как в полных, так и частично заданных булевых функциях. Методы. В статье предложен новый метод распознавания разных типов полных и частичных симметрий, таких как полисимметрия, простая симметрия и антисимметрия, как в полностью, так и частично заданных функциях на основе численного теоретико-множественного логического дифференцирования. Алгоритм метода основан на теореме распознавания разных типов частичных симметрий, который, в сравнении с известными, имеет относительно меньшую вычислительную сложность благодаря сравнительно меньшему количеству операций и процедур, необходимых для выполнения поставленной задачи. 2019 Article A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II / B.Ye. Rytsar // Control systems & computers. — 2019. — № 5. — С. 5-11. — Бібліогр.: 22 назв. — англ. 2706-8145 DOI: https://doi.org/10.15407/usim.2019.05.005 http://dspace.nbuv.gov.ua/handle/123456789/181044 519.713 en Control systems & computers Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Fundamental Problems in Computer Science Fundamental Problems in Computer Science |
| spellingShingle |
Fundamental Problems in Computer Science Fundamental Problems in Computer Science Rytsar, B.Ye. A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II Control systems & computers |
| description |
The article describes a new method for the recognition of different types of total and partial symmetry in boolean functions based on the numeric set-theoretical differentiation. The proposed algorithm is based on the theorem on the recognition of different types of partial symmetry. This algorithm, compared to the known, has a relatively less computational complexity of realization due to a comparatively smaller number of operations and procedures necessary for the accomplishment of the given task. This is evidenced by the presented examples for the recognition of the proposed method of the different types of symmetry in complete and incomplete of Boolean functions, including given in the SOP format, borrowed for comparison reasons from publications of wellknown authors. |
| format |
Article |
| author |
Rytsar, B.Ye. |
| author_facet |
Rytsar, B.Ye. |
| author_sort |
Rytsar, B.Ye. |
| title |
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II |
| title_short |
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II |
| title_full |
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II |
| title_fullStr |
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II |
| title_full_unstemmed |
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II |
| title_sort |
new method for symmetry recognition in boolean functions based on the set-theoretical logic differentiation. ii |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2019 |
| topic_facet |
Fundamental Problems in Computer Science |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/181044 |
| citation_txt |
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II / B.Ye. Rytsar // Control systems & computers. — 2019. — № 5. — С. 5-11. — Бібліогр.: 22 назв. — англ. |
| series |
Control systems & computers |
| work_keys_str_mv |
AT rytsarbye anewmethodforsymmetryrecognitioninbooleanfunctionsbasedonthesettheoreticallogicdifferentiationii AT rytsarbye newmethodforsymmetryrecognitioninbooleanfunctionsbasedonthesettheoreticallogicdifferentiationii |
| first_indexed |
2025-07-15T21:34:29Z |
| last_indexed |
2025-07-15T21:34:29Z |
| _version_ |
1837750309162582016 |
| fulltext |
iSSN 2706-8145, control systems and computers, 2019, № 5 5
doi https://doi.org/10.15407/usim.2019.05.005
Udc 519.713
B.ye. rytsar, doctor eng., professor,
institute of telecommunications, radioelectronics and electronic engineering,
l’viv polytechnic National University, bandera str., 12, l’viv, 79013, Ukraine,
e-mail: bohdanrytsar@gmail.com
A new method For symmetry reCoGnItIon
In BooleAn FunCtIons BAsed on the set-theoretICAl
loGIC dIFFerentIAtIon. II1
The article describes a new method for the recognition of different types of total and partial symmetry in boolean functions based
on the numeric set-theoretical differentiation. The proposed algorithm is based on the theorem on the recognition of different
types of partial symmetry. This algorithm, compared to the known, has a relatively less computational complexity of realization
due to a comparatively smaller number of operations and procedures necessary for the accomplishment of the given task. This is
evidenced by the presented examples for the recognition of the proposed method of the different types of symmetry in complete and
incomplete of Boolean functions, including given in the SOP format, borrowed for comparison reasons from publications of well-
known authors.
Keywords: recognition of total and partial symmetry, Boolean function, numeric set-theoretical differentiation.
Fundamental
problems in Computer
science
Description of algorithm
The algorithm of the numeric set-theoreti-
cal method for recognition of the partial sym-
metries types in complete of Boolean function
f = (x
1
, . . ., x
i
, . . ., x
j
, . . . x
n
) given by the perfect STF
Y1 ={m
1
, m
2
, . . ., m
z
}1, 2 < z <2n , can be realized by
means of the following steps:
Step 1: The mask of the literals
⋅⋅⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅⋅
nji
nji
llll
llll
1
1 ,
l∈{0, 1}, impose on the set of given binary min-
terms m
1
, m
2
, . . ., m
z
and determine the vectorial ST-
derivative of the 2-nd order (1) for all
!2)!2(
!2
−
=
n
nCn
possible pairs of variables of the function f; if z is an
odd number, then proceed to Step 3, and if z is an
even number, then
Step 2: Check the condition (2) of the theorem
(Section 3) for all 2
nC pairs of variables and if it is
executed, then the given function has a totally poly-
symmetry of variables and then perform the transi-
tion to Step 6; if condition (2) is satisfied only for
one or some pairs of variables, then this function
has a partial polysymmetry with respect to these
variables and then perform the transition to Step 5,
and if condition (2) is not fulfilled, then
Step 3: Check condition (3) for all 2
nC pairs of
variables, and if it is executed, then the given func-
tion has a totally simple symmetry of variables and
then perform the transition to Step 6; if condition
(3) is satisfied only for some pairs of variables, then
this function has a partial simple symmetry with
respect to these variables and then perform the
transition to Step 5, and if condition (3) is not sa-
tisfied, then
Step 4: Check condition (4) for all 2
nC pairs of va-
riables and if it is executed, then the given function
has the totally antisymmetry of the variables, and if
condition (4) is satisfied only for some pairs of vari-
ables, then this function has a partial antisymmet-
6 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
B.Ye. Rytsar
ry with respect to these variables; if the condition
(4) is not fulfilled, then proceed to the Step 6;
Step 5: Check condition (3) or (4) for the re-
maining pairs of variables and if it is executed, then
the function has a partial simple symmetry or par-
tial antisymmetry with respect to these variables,
and if condition (3) or (4) is not satisfied, then
Step 6: Write the final result .
Note that if a function is given in SOP format
(or STF) and has non-orthogonal pseudoternary
conjuncterms, then such a function needs to be or-
thogonalized, for example by numeric set-theore-
tical method [16] .
recognition of partial symmetries
types in incomplete functions
The proposed method can also be used to identify
partial symmetries in incomplete (incompletey
specified) functions on the basis of the theorem
(Part I) with respect to the peculiarities of incom-
plete functions .
In the set-theoretical format (STF) the incom-
plete function f:{0,1}n→{0, 1, ∼}, where the sign of
the tilde ~ symbolizes the uncertainty of the func-
tion f, is represented by two sets that constitute the
perfect STF [18]
or
=
=
−−++
~
221
~
1
21
1
},...,,{
},...,,{
hzzz
z
nmmmY
mmmY
, (5)
or
=
=
−−++
0
221
0
1
21
1
},...,,{
},...,,{
hzzz
z
nmmmY
mmmY
, zh n −< 2 , (6)
where Y1, Y0 and Y ∼ are subsets of the minterms of
the set nE2 , on which the function f has values 1, 0
and “don’t care” (~) . In our case we will apply the
perfect STF (5) .
Accordingly, the vectorial ST-derivative of the
2-nd order with respect to variables (x
i
, x
j
) of the
function f will consist of two sets of pairs of min-
terms formed by masks of literals
⋅⋅⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅⋅
nji
nji
llll
llll
1
1
,
PSTF’s Y ⊕ and ⊕
~
Y , that is ⊕⊕
~
YY M , where M is the
sign of separation of these sets . As in the case of
a complete function (Part I), the procedure for
simplifying the set Y ⊕ will be realized by elimi-
nating pairs of identical elements . In addition,
the procedure for predetermined of an incom-
plete function will simultaneously be realized —
if any pair of minterms of the set Y ⊕ has a copy
in the set ⊕
~
Y , then it is eliminated from Y ⊕ .Then,
for received of minterms of the vectotial ST-
derivative ),(2
ji xxY ∂∂ ⊕ of a predetermined in-
complete function f, the same as in the case of a
complete function, the verification of the condi-
tions (2), (3), and (4) of the theorem (Section 3)
is performed . Let’s consider it in the examples .
Example 7[9] . Identify the types of parti-al
symmetries for the incomplete function f(x
1
, x
2
,
x
3
, x
4
, x
5
) given by the perfect STF
=
=
~~
11
}31,26,25,18,16,11,5,2,1{
}22,21,15,10,9,6,0{
Y
Y
(in [9] the K-map
method is used) .
Solution . We firs tdefine the vectorial ST-de-
rivative ),( 21
2 xxY ∂∂ ⊕ , impose the appropriate
mask of the literals on the minterms of the perfect
PSTF ⊕⊕
~
YY M :
( ) ( ) ( )00000 00110 01001, , ,11000 11110 10001
=
⊕
�( ) )01010 01111 10101 10110, , ,10010 10111 01101 01110( ( () )
( ) (00001 00010 00101, , ,11001 11010 11101
�
01011
10011
10000
01000, ,
==>
==>
00000 00110 01001, , ,11000 11110 10001
01111 10101 10110, ,10111 01101 01110
.
⊕̂
( ( (
( ) ( ) ( )
( )
) ) ) )
( ) ( )
10010 11001 11010 11111, , ,01010 00001 00010 00111( )( )( )( )
Since none of the conditions (2), (3) and
(4) of the theorem (Part I) is not satisfied here
the predetermined incomplete function f does
not have a partial symmetry with respect to the
iSSN 2706-8145, control systems and computers, 2019, № 5 7
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II
pair of variables {x
1
, x
2
} . Similarly, there are no
partial symmetries with respect to the pairs of
variables {x
1
, x
3
}, {x
1
, x
4
} and {x
1
, x
5
} . Instead,
for the rest of all possible 2
5 10C = pairs of vari-
ables we get:
for th• e pair of variables {x
2
, x
3
} we have
3
( )00000 00110 01001, , ,01100 01010 00101
=
⊕
�
( ) ( )
01010 01111 10101 10110, , ,00110 00011 11001 11010( ) ( ) ( ) ( )
00001 00010 00101, , ,01101 01110 01001
�
01011
00111
10000
11100, ,
==>
==>
00000 00110
11000 11110
⊕̂
,
( ) ( )
( ) ( )
01 , 10
,
00 , 11
− − − − − − = ∅∩
− − − − − − ≠ ∅
( ) ( ) ( ) ( ) ( )
( ) ( )
10010 11001 11010 11111
11110 10101 10110 10011
, , ,( ) ( ) ( ) ( )
,
in accordance with condition (3), the predeter-
mined incomplete function f has the partial simple
symmetry 2 3 2 3~ / ~x x x x ;
for the pair of variables {• x
2
, x
4
} we have
4
00000 00110 01001, , ,01010 01100 00011
=
⊕
�
( ) ( ) ( )
01010 01111 10101 10110, , ,00000 00101 11111 11100( ) ( ) ( ) ( )
00001 00010 00101
, , ,01011 01000 01111
�
01011
00001
10000
11010, ,
==>
==>
00000 01001
01100 00011
⊕̂
, 10110
11100
,
⊕
( ) ( )
( ) ( )
0 1 , 1 0
,
0 0 , 1 1
− − − − − − ≠ ∅∩
− − − − − − = ∅
∩
( ) ( ) ( ) ( ) ( )
( ) ( ) ( )
10010 11001 11010 11111
11000 10011 10000 10101
, , ,( ) ( ) ( ) ( )
in accordance with condition (4) the predeter-
mined incomplete function f has the antisymmetry
type 2 4 2 4~ / ~x x x x .
By performing the proposed method similar
procedures for the remaining pairs of variables of
the given incomplete function f, we obtain the fol-
lowing partial symmetries:
for the pair of variables {• x
2
, x
5
}
we have the
antisymmetry 2 5 2 5~ / ~x x x x ,
for the pair of variables {• x
3
, x
4
} we have the
antisymmetry 3 4 3 4~ / ~x x x x ,
for the pair of variables {• x
2
, x
5
} we have the
antisymmetry 3 5 3 5~ / ~x x x x ,
for the pair of variables {• x
4
, x
5
} we have the
simple symmetry 4 5 4 5~ / ~x x x x .
Thus, the given incomplete function f is
characterized by a mixed symmetry of type
1 2 3 4 5~ ( ~ ~ ~ )x x x x x/ or 1 2 3 4 5~ ( ~ ~ ~ )X X X X X/ .
We note that partial symmetries were detected in
[9] only for two pairs of variables {x
2
, x
4
} and {x
3
, x
4
} ,
that is mixed symmetry type 1 5 2 3 4~ ~ ( ~ ~ )x x x x x/ /
or 1 5 2 3 4~ ~ ( ~ ~ )X X X X X/ / .
Example 8 [14] . Identify the types of partial
symmetries for the incomplete function f(x
1
, x
2
,
x
3
, x
4
) given by theperfect STF
1 1
~ ~
{(0001), (0100), (0101), (0110), (0111)}
{(0000), (0010), (0011), (1001), (1010)}
Y
Y
=
=
.
Solution . For the pair of variables {x
1
, x
2
} we have:
21
{ }0001 0100 0101 0110 0111, , , ,0111 0010 0011 0000 0001
⊕
�
ˆ
0000 0010 0011 1001 1010, , , ,1100 1110 1111 0101 0110
⊕
⇒�{ }
( )=
0001 0100 0111 (01 ), (10 ), , (00 ), (11 )1101 1000 1011
− − − − ≠ ∅⇒ ∩ − − − − ≠ ∅{ }
( ) ( ) ( ) ( )
{
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) .
As well as for a pair {x
1
, x
2
}, the predetermined
incomplete function f does not have partial sym-
metries with respect to the pairs of variables {x
1
, x
3
}
and {x
1
, x
4
} . Let’s consider for the rest of all possible
2
4 6C = pairs of variables .
For the pair of variables {x
2
, x
3
} we have:
32
8 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
B.Ye. Rytsar
ˆ
0100 0101 0110
, ,
0010 0011 0000
0000 0010 0011 1001 1010
, , , ,
0110 0100 0101 1111 1100
⊕
⊕
= ∅
�
� .
=
After simplifying the set Y ⊕ here you can find dif-
ferent types of partial symmetries, which depend
on the selected variant for the predetermination of
the given function f . Consider these variants:
1 .
ˆ
0100 0101 0110
, ,
0010 0011 0000
0000 0010 0011 1001 1010
, , , ,
0110 0100 0101 1111 1100
⊕
⊕
�
� =∅;
2 .
ˆ
0100 0101 0110
, ,
0010 0011 0000
0000 0010 0011 1001 1010
, , , ,
0110 0100 0101 1111 1100
⊕
⊕
�
� ⇒
∩⇒
( 01 ), ( 10 )
;
( 00 ), ( 11 )
− − − − = ∅
− − − − ≠ ∅
0110
0000
3 .
ˆ
0100 0101 0110
, ,
0010 0011 0000
0000 0010 0011 1001 1010
, , , ,
0110 0100 0101 1111 1100
⊕
⊕
�
� ⇒
∩⇒
( 01 ), ( 10 )
( 00 ), ( 11 )
− − − − = ∅
− − − − ≠ ∅
.0110 0101
,
0000 0011
Consequently, for each of the variants for the
predetermination we will have the following partial
symmetries with respect to the pair {x
2
, x
3
}:
1 . polysymmetry 2 3~x x� � ;
2 . simple symmetry 2 3 2 3~ / ~x x x x ;
3 . antisymmetry 2 3 2 3~ / ~x x x x .
• For the pair of variables {x
2
, x
4
} we have:
42
ˆ0000 0010 0011 1001 1010
, , , ,
0110 0100 0101 1111 1100
⊕
�
0001 0100 0101 0110 0111
, , , ,
0100 0001 0000 0011 0010
⊕
�
.
=
In this case, just like in the previous one, we also
have three variants for the predetermination:
1 .
ˆ
0101 0110 0111
, ,
0000 0011 0010
0000 0010 0011 1001 1010
, , , ,
0101 0111 0110 1100 1111
⊕
⊕
�
� =∅;
2 .
ˆ
0101 0110 0111
, ,
0000 0011 0010
0000 0010 0011 1001 1010
, , , ,
0101 0111 0110 1100 1111
⊕
⊕
�
� ⇒
0110 ( 0 1), ( 1 0) ;( 0 0), ( 1 1)0011
− − − − ≠ ∅⇒ ∩ − − − − = ∅
3 .
ˆ
0101 0110 0111
, ,
0000 0011 0010
0000 0010 0011 1001 1010
, , , ,
0101 0111 0110 1100 1111
⊕
⊕
�
� ⇒
∩⇒
( 01 ), ( 10 )
.
( 00 ), ( 11 )
− − − − = ∅
− − − − ≠ ∅
0110
0000
0111
0010
,
Consequently, for a pair of variables {x
2
, x
4
}, we
have the following partial symmetries:
1 . polysymmetry 2 4~x x� � ;
2 . antisymmetry 2 4 2 4~ / ~x x x x ;
3 . simple symmetry 2 4 2 4~ / ~x x x x .
• For the pair of variables {x
3
, x
4
} we have:
43
0001 0100 0101 0110 0111
, , , ,
0010 0111 0110 0101 0100
⊕
�=
iSSN 2706-8145, control systems and computers, 2019, № 5 9
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II
ˆ0000 0010 0011 1001 1010
, , , ,
0011 0001 0000 1010 1001
⊕
� ⇒ ∅
∩⇒
0101
0110
{( 01), ( 10)} ,− − − − = ∅
0110
0101
,
and hence, in accordance with the condition (9),
the predetermined incomplete function f has a par-
tial symmetry .
Thus, the given function f has the following
variants of mixed partial symmetries:
• 3 4 3 4~ / ~x x x x ;
• 1 2 3 4~ ( ~ ~ )x x x x/ � � � ;
• 1 2 3 4 1 2 3 4~ ( ~ ~ ) / ~ ( ~ ~ )x x x x x x x x/ / ,
that corresponds to [14] .
ConClusIon
Part 2 of the article describes the algorithm of the
proposed method for the recognition of various
types of symmetry (polysymmetry, simple symmetry
and antisymmetry) in the boolean functions of n
variables, based on the numerical set-theoretical
logical differentiation . In particular, features of
recognition of partial symmetries in incomplete
functions are shown on the basis of the theorem
(Part 1) . The advantage of the proposed method,
in comparison with other [2, 3, 8–11], consists in
the fact that during the simplification procedure
(of the set Y ⊕) the predetermination procedure
for the incomplete function is simultaneously
implemented . In addition, the proposed method is
easier to implement in practice, which in this work
is illustrated by examples of functions borrowed
from publications by well-known authors .
REFERENCES
Maurer, P .M ., 2015 . “Symmetric Boolean Functions” . Int . J . of Math ., Game Theory and Algebra, . 24 (2–3), 1 .
pp . 159–202 .
Scholl, Ch ., 2001 . “Functional Demposition with Application to FPGA Synthesis” . Kluwer Academic Publishers, 2 .
Boston/Dordrecht/London, pp . 50–63 .
Schneeweiss, W .G ., 1989 . Boolean Functions with Engineering Applications and Computer Programs . Springer-3 .
Verlag Berlin Heidelberg, 264 p .
Bhattacharjee, P .K ., 2010 . “Digital Combinational Circuits Design with the Help of Symmetric Functions 4 .
Considering Heat Dissipation by Each QCA Gate” . Int . J . of Computer and Electrical Engineering, 2 (4), pp . 666–672 .
Stanica, P ., Maitra, S ., 2008 . “Rotation symmetric Boolean functions — Count and cryptographic properties” . 5 .
Discrete Applied Mathematics, 156 (10), pp . 1567–1580 .
Butler, J .T ., Sasao, T ., 2010 . “Boolean Functions for Cryptography” . In book Sasao T ., Butler J .T .: Progress in 6 .
Applications of Boolean Functions, pp . 33–53 .
Zhang, J . S ., Mishchenko, A ., Brayton, R ., Chszanowska, M ., 2006 . “Symmetry Detection for Large Boolean 7 .
Functions using Circuit Representation, Simulation, and Satisfiability” . DAC 2006, July 24–28, https://people .eecs . berke-
ley .edu/~alanmi/publications/2006/dac06_sym .pdf .
Butler, J .T ., Dueck, G .W ., Holowinski, G ., Shmerko, V .P ., Janushkewich, V .N ., 1999 . “On Recognition of 8 .
Symmetries for Switching Functions in Reed-Muller Forms” . Proc . PRIP’99, Belarus, 1, pp . 215–234 .
Paulin, O .N ., Lyakhovetskiy, A .M ., 1999 . “Metod doopredeleniya nepolnost’yu zadannoy funktsii do 9 .
simmetricheskoy” . Elektron . Modelirovaniye, 21 (6), pp . 21–30 . (In Russian) .
Zakrevskiy, A .D ., Pottosin, Yu .V ., Cheremisinova, L .D ., 2007 . Logicheskiye osnovy proyektirovaniya diskretnykh 10 .
ustroystv . M .: Fizmatlit, 592 p . (In Russian) .
Rytsar, B ., 2018 . “Set-Theoretical Decomposition on the Basis of Symmetric Functions” . Proc . TCSET’2018, 11 .
20-24 Feb ., pp . 868–872 .
Steinbach, B ., Posthoff, C ., 2009 . Logic Functions and Equations . Examples and Exercises . Springer Science + 12 .
Business Media B .V ., 230 p .
Steinbach, B ., Posthoff, C ., 2017 . “Boolean Differential Calculus . Morgan & Claypool Publishers series”, 195 p ., 13 .
www .morganclaypool .com .
Wang, K .-H ., Chen, J .-H ., 2004 . “Symmetry Detection for Incompletely Specified Functions” . DAC 2004, June 7–11, 14 .
San Diego, California, USA, pp . 434–437 . https://www .sciencedirect .com/science/journal/0166218X/156/10 .
Rytsar, B .15 . , 2016 . “A Simple Numeric Set-Theoretical Method of the Logic Differential Calculus” . Control Systems
and Computers, 6, pp . 12–23 .
10 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
B.Ye. Rytsar
Rytsar, B ., Romanowski, P ., Shvay, A ., 2010 .16 . “Set-theoretical Constructions of Boolean Functions and theirs
Applica tions in Logic Synthesis” . Fundamenta Informaticae, 99 (3), pp . 339–354 .
Rytsar, B .17 . , 2003 . “Identification of symmetry of Boolean function decomposition cloning method” . Proc . 6th Int .
Conf . on Telecom ., TELSIKS 2003, Yugoslavia, Nis . 003, pp . 596–603 .
Rytsar, B . 2015 . “A n18 . ew minimization method of logical functions in polynomial set-theoretical format . 1 . Generalized
rules of conjuncterms simplification” . Control Systems and Computers, 2, pp . 39–57 .
Rytsar, B .Ye ., 2013 . “19 . A Numeric Set-Theoretical Interpretation of Reed-Muller Expressions with Fixed and Mixed
Polarity”, Control Systems and Computers, 3, pp . 30–44 .
Yang, S ., 1991 . Logic synthesis and optimization benchmarks user guide — version 3 .0 . Microelectronics Center 20 .
of North Carolina, Research Triangle Park, NC, January .
Kravets, V .N ., Sakallah, K .A . Generalized Symmetries in Boolean Functions, [online] . Available at: <www .eecs .21 .
umich > [Accessed 15 Dec . 2018] .
Kaeslin, H ., 2008 . “Digital Integrated Circuit Design From VLSI Architectures to CMOS Fabrication” . Cambridge 22 .
University Press, pp . 741 .
Received 22 .07 .2019
Б.Є. Рицар, доктор технічних наук, професор,
кафедра радіоелектронних пристроїв та систем,
Національний університет «Львівська політехніка»,
вул . С . Бандери, 12, Львів, 79013, Україна,
E-mail: bohdanrytsar@gmail .com
НОВИЙ МЕТОД РОЗПІЗНАВАННЯ СИМЕТРІЇ У БУЛОВИХ ФУНКЦІЯХ
НА ОСНОВІ ТЕОРЕТИКО-МНОЖИННОГО ЛОГІКОВОГО ДИФЕРЕНЦІЮВАННЯ . ІІ
Вступ . Симетричні булові функції завдяки своїм специфічним властивостям мають широке застосування у
проектуванні цифрових пристроїв, телекомунікаціях, криптографії тощо . Оскільки булові функції можуть мати
різні типи симетрії з властивими їм особливостями, важливо вміти їх розпізнавати якомога простішими засобами .
Проте проблема ускладнюється тим, що, з одного боку, функції можуть бути як одного типу, так і змішаного, а також
як повністю симетричними, так і частково симетричними, а з другого боку, сама функція може бути не повністю
визначена, тобто задана частково, або задана ДНФ . Сучасні методи розпізнавання типів симетрії ґрунтуються
переважно на аналітичному підході (розкладі Шеннона), візуальному методі, аналітичному обчисленні логікових
похідних і т .ін ., надто складні щодо реалізації та мало ефективні для функцій великих розмірів і особливо, коли
вони задані частково .
Мета статті — розробити простий для реалізації метод розпізнавання різних типів повних і частинних симетрій
як у повних, так і частково заданих булових функціях .
Методи . У статті запропоновано новий метод розпізнавання різних типів повних і частинних симетрій, таких
як полісиметрія, проста симетрія та антисиметрія, як у повністю, так і частинно заданих функціях на основі
числового теоретико-множинного логікового диференціювання . Алгоритм методу ґрунтується на теоремі про
розпізнавання різних типів частинних симетрій, який, порівняно з відомими, має відносно меншу обчис-
лювальну складність за рахунок порівняно меншої кількості операцій і процедур, потрібних для виконання
поставленої задачі .
Результат . Справедливість доведеної теореми засвідчують приклади розпізнавання різних типів повних і ча-
стинних симетрій як у повністю заданих функціях (Частина 1), так і частково заданих функціях (Частина 2), у тому
числі заданих у ДНФ, які з метою порівняння ефективності запропонованого алгоритму запозичено з публікацій
відомих авторів .
Висновок . Запропонований новий метод розпізнавання різних типів повних і частинних симетрій (полісиметрії,
прості симетрії та антисиметрії) як у повністю, так і частково заданих булових функціях на основі числового
теоретико-множинного логікового диференціювання відрізняється від відомих відносно простішою практичною
реалізацією .
Ключові слова: розпізнавання повних і часткових симетрій, булова функція, числове теоретико-множинне логікове
диференціювання.
iSSN 2706-8145, control systems and computers, 2019, № 5 11
A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II
Б.Е. Рыцар, доктор технических наук, профессор,
кафедра радиоэлектронных устройств и систем,
Национальный университет «Львівська політехніка»,
ул . С . Бандеры, 12, Львов, 79013, Украина,
E-mail: bohdanrytsar@gmail .com
НОВЫЙ МЕТОД РАСПОЗНАВАНИЯ СИММЕТРИИ В БУЛЕВЫХ ФУНКЦИЯХ
НА ОСНОВЕ ТЕОРЕТИКО-МНОЖЕСТВЕННОГО ЛОГИЧЕСКОГО ДИФФЕРЕНЦИРОВАНИЯ . ІІ
Введение . Симметричные булевые функции благодаря своим специфическим свойствам широко используются
в проектировании цифровых устройств, телекоммуникациях, криптографии и т .п . Поскольку булевые функции
могут иметь разные типы симметрии с присущими им особенностями, важно уметь их распознавать как можно
простейшими способами . Но проблема усложняется тем, что, с одной стороны, функции могут быть как одного
типа, так и смешанного, а также как полностью симметричными, так и частично симметричными, а с другой сто-
роны, сама функция может быть не полностью определена, т .е . задана частично, или задана ДНФ . Современные
методы распознавания типов симметрии основаны преимущественно на аналитическом подходе (разложении
Шеннона), визуальном методе, аналитическом вычислении логических производных и др ., слишком сложны в
реализации и мало эффективны для функций больших размеров и особенно, когда они заданы частично .
Цель статьи — разработать простой в реализации метод распознавания разных типов полных и частичных сим-
метрий, как в полных, так и частично заданных булевых функциях .
Методы . В статье предложен новый метод распознавания разных типов полных и частичных симметрий, таких
как полисимметрия, простая симметрия и антисимметрия, как в полностью, так и частично заданных функциях
на основе численного теоретико-множественного логического дифференцирования . Алгоритм метода основан
на теореме распознавания разных типов частичных симметрий, который, в сравнении с известными, имеет отно-
сительно меньшую вычислительную сложность благодаря сравнительно меньшему количеству операций и про-
цедур, необходимых для выполнения поставленной задачи .
Результат . Справедливость доказанной теоремы показывают примеры распознавания разных типов полных и
частичных симметрий как в полностью заданных функциях (Часть 1), так и частично заданных функциях (Часть
2), в том числе заданных в ДНФ, которые с целью сравнения эффективности предложенного алгоритма взято из
публикаций известных авторов .
Выводы . Предложенный новый метод распознавания разных типов полных и частичных симметрий (полисим-
метрии, простые симметрии и антисимметрии) как в полностью, так и частично заданных булевых функциях на
основе числового теоретико-множественного логического дифференцирования отличается от известных относи-
тельно простейшей практической реализацией .
Ключевые слова: распознавание полных и частичных симметрий, булевая функция, числовое теоретико-множественное
логическое дифференцирование.
|