«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2009. Vol. 2

About a part noniterated functions, free from paws of the big width

Author(s)
O. V. Zubkov
Abstract

In this paper we are comparing noniterated in the whole binar basis B2 = {&, ∨, ⊕}some classespowersofBooleanfunctions.Noniterated Booleanfunctions are presented with a marked root trees, in which we can pick out the a canonical forms. To continue there is an algorithm, with the help of whitch we can pass from the canonical trees to the whole binar canonical trees. In this algorithm we can combine two definitely different methods of creating the canonical form of the noniterated in the basis B2 function. The representation of the noniterated Boolean functions as a whole binar canonical trees allowed to proof, that the part of functions in canonical form of which there is one or more k-locative function &, ∨ or ⊕ exponently aspires to zero with a growth of k-value. The result is worth testing of the noniterated Boolean function.

Keywords
noniterated Boolean function, whole binar basis, canonical forms of the noniterated function, marked root trees, whole binar canonical trees, testing of the Boolean functions concerning the noniterated alternative
UDC
УДК 519.11, 519.71
References

1. Вороненко А. А. О проверяющих тестах для бесповторных функций // Математические вопросы кибернетики. — 2002. — вып. 11. — С. 163-176.

2. Зубков О. В. О числе бесповторных булевых функций в базисе {&,;∨,;⊕,−}//, Дискретный анализ и исследование операций. — 2003. — серия 1, Т. 10, N 1. — С.41 -60.


Full text (russian)