ON A DECOMPOSITION OF BOOLEAN FUNCTIONS REPRESENTED BY QUADRATIC INEQUALITIES
( Pp. 53-59)
More about authors
Shurupov Andrei Nikolaevich
sotrudnik
FEMA (Federal Educational Methodical Association) in the system of higher education on Information security
FEMA (Federal Educational Methodical Association) in the system of higher education on Information security
Abstract:
This paper advances results on Boolean threshold function decomposition [2] to Boolean functions represented by one quadratic inequalities. Quadratic polynoms are the most compact non-linear polynoms and this property sometimes is quite important. We proved three criterions for non-trivial decomposition of quadratic Boolean threshold function. The second one can be applied without analysis of truth table and only needs some evolvement of threshold structure. Threshold functions provide a simple but fundamental model for many questions investigated in image recognition, artificial neural networks and many other areas [3].
How to Cite:
Shurupov A.N., (2014), ON A DECOMPOSITION OF BOOLEAN FUNCTIONS REPRESENTED BY QUADRATIC INEQUALITIES. Computational Nanotechnology, 2 => 53-59.
Reference list:
CHeremushkin A.V. Bespovtornaya dekompozitsiya sil no zavisimykh funktsiy // Diskretnaya matematika. 2004. T.16. Vyp.3. S.3-42.
SHurupov A. N. O funktsional noy razdelimosti bulevykh porogovykh funktsiy // Diskretnaya matematika. 1997. T.9. Vyp. 2. S. 59-73.
Ezhov A. A., SHumskiy S. A. Neyrokomp yuting i ego primeneniya v ekonomike i biznese. M., 1998. 222 s.
Ashenhurst R.L. The decomposition of switching functions // Ann. Comput. Laborat. Harv. Univ. 1959. V.29. PP.74-116.
Dertouzos M. Porogovaya logika / Perevod s angl. B. L. Ovsievicha, L. YA. Rozenblyuma, pod red. V. I. Varshavskogo. M.: Mir, 1967. 343 s. Perevod izd.: Threshold Logic: A Synthesis Approach / Michael L. Dertouzos. The M.I.T. Press, Cambridge, Massachusetts, 1965.
Logachev O. A., Sal nikov A. A., YAshchenko V. V. Bulevy funktsii v teorii kodirovaniya i kriptologii / M.: MTSNMO, 2004. 470 s.
Crama Y., Hammer P. L. Boolean Functions. Theory, Algorithms and Applications. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2011. 687 p.
Podol skiy V. V. Otsenki vesov perseptronov (polinomial nykh porogovykh bulevykh funktsiy). Avtoreferat diss. na soiskanie uch.stepeni k.f.m.n. po spets.01.01.06. M., MGU im M.V. Lomonosova, 2009.
Balakin G. V., Nikonov V. G. Metody svedeniya bulevykh uravneniy k sistemam porogovykh sootnosheniy // Obozrenie prikladnoy i promyshlennoy matematiki. T.1, Vyp.3, 1994. S.389-401.
Anashkina N. V., SHurupov A. N. Eksperimental noe sravnenie algoritmov Balasha i imitatsii otzhiga v zadache resheniya sistem lineynykh neravenstv // Prikladnaya diskretnaya matematika. Prilozhenie. №7, sentyabr 2014. Tomsk, Izdatel stvo TGU, 2014. S.151-153
SHurupov A. N. O funktsional noy razdelimosti bulevykh porogovykh funktsiy // Diskretnaya matematika. 1997. T.9. Vyp. 2. S. 59-73.
Ezhov A. A., SHumskiy S. A. Neyrokomp yuting i ego primeneniya v ekonomike i biznese. M., 1998. 222 s.
Ashenhurst R.L. The decomposition of switching functions // Ann. Comput. Laborat. Harv. Univ. 1959. V.29. PP.74-116.
Dertouzos M. Porogovaya logika / Perevod s angl. B. L. Ovsievicha, L. YA. Rozenblyuma, pod red. V. I. Varshavskogo. M.: Mir, 1967. 343 s. Perevod izd.: Threshold Logic: A Synthesis Approach / Michael L. Dertouzos. The M.I.T. Press, Cambridge, Massachusetts, 1965.
Logachev O. A., Sal nikov A. A., YAshchenko V. V. Bulevy funktsii v teorii kodirovaniya i kriptologii / M.: MTSNMO, 2004. 470 s.
Crama Y., Hammer P. L. Boolean Functions. Theory, Algorithms and Applications. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2011. 687 p.
Podol skiy V. V. Otsenki vesov perseptronov (polinomial nykh porogovykh bulevykh funktsiy). Avtoreferat diss. na soiskanie uch.stepeni k.f.m.n. po spets.01.01.06. M., MGU im M.V. Lomonosova, 2009.
Balakin G. V., Nikonov V. G. Metody svedeniya bulevykh uravneniy k sistemam porogovykh sootnosheniy // Obozrenie prikladnoy i promyshlennoy matematiki. T.1, Vyp.3, 1994. S.389-401.
Anashkina N. V., SHurupov A. N. Eksperimental noe sravnenie algoritmov Balasha i imitatsii otzhiga v zadache resheniya sistem lineynykh neravenstv // Prikladnaya diskretnaya matematika. Prilozhenie. №7, sentyabr 2014. Tomsk, Izdatel stvo TGU, 2014. S.151-153
Keywords:
Boolean functions, threshold function, decomposition, quadratic inequalities.
Related Articles
1. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 7-14 Issue №9439
ABOUT THE NEW ALGORITM OF CHARACTERIZATION OF k-VALUED THRESHOLD FUNCTIONS
threshold function
k-valued logic
characterization of threshold functions
growth factors
the coefficients of increase
Show more
1. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 6-13 Issue №6518
ABOUT BIJECTIVITY OF TRANSFORMATIONS DETERMINED BY QUASI-HADAMARD MATRIXES
bijective mapping
threshold function
quasidemocracy matrix
Show more
2. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 26-30 Issue №5869
Geometrical approach to the argumentum of bijection of one coordinate-threshold reflection
bijective mapping
threshold function
multidimensional cones
quasidemocracy matrix
Show more
Information Security Pages: 36-41 DOI: 10.33693/2313-223X-2023-10-2-36-41 Issue №23034
Construction of a Reversible Full-cycle Transformation in a Threshold Basis
substitution
threshold function
full cycle
Show more
2. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 31-36 Issue №5869
The constructive method for synthesis of balanced k-valued algebraic threshold functions
multivalued logic
threshold function
algebraic threshold function
balanced function
Show more
Information Security Pages: 56-92 DOI: 10.33693/2313-223X-2022-9-1-56-92 Issue №20643
4-Variable Boolean Functions Representations Classification in the Form of Nonlinearity Minimal Degree Separating Surfaces
Boolean functions
Khachiyan algorithm
adaptive ellipsoid algorithm
Boolean functions classification
Show more
Multiscale modeling for information control and processing Pages: 50-58 DOI: 10.33693/2313-223X-2021-8-3-50-58 Issue №19706
On the Complexity of Specifying a Symmetric Group of Permutations of Degree 2n in a Threshold Basis on a Promising Element Base
threshold function
symmetric group
implementation of permutations
threshold basis
complexity of implementation
Show more
6. INFORMATION SECURITY Pages: 39-49 Issue №9439
ABOUT POSSIBILITY OF USING FRACTAL MODELS IN DATA SECURITY SYSTEM CONSTRUCTION
fractal
protection of information
function complications
threshold function
Show more
INFORMATION SECURITY Pages: 132-139 Issue №11955
MODIFICATION OF A GEOMETRICAL ALGORITHM OF CHARACTERIZATIONk-VALUED THRESHOLD FUNCTIONS
threshold function
k-valued logic
geometric algorithm the characterization of threshold functions
the proof of convergence
Show more
