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
For read the full article, please, register or log in
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
Keywords:
Boolean functions, threshold function, decomposition, quadratic inequalities.