On Full Checking Tests under Local Glueings of Variables in Boolean Functions

I. A. Kuzhetsov ; D. S. Romanov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 90-97

Résumé

A local $k$-fold glueing of variables in Boolean function $f(\widetilde x^n)$ is a function obtained as a result of substitution instead of some $k$ successive variables an arbitrary Boolean function depending on these variables ($2\le k\le n$). Full checking tests under local $k$-fold glueings of variables in Boolean functions $f(\widetilde x^n)$ are studied in this paper. It is established that if $n\to\infty$, $(n-k)\to\infty$, $k\to\infty$, then an asymptotics of Shannon function of the test length is $2^{k-1}(n-k+2)$. Furthermore, let $n\to\infty$, $(n-k)\to\infty$, $\gamma(n,k)\to\infty$, $\gamma(n,k)=o(\log_2(n-k))$, therefore, a set of $n$-tuples exists which is full checking test under local $k$-fold glueings of variables in almost all Boolean functions $f(\widetilde x^n)$ and whose power is not greater than $\lceil\log_{4/3}(n-k+1)+\gamma(n,k)\rceil$. At last, under conditions $n\to\infty$, $2\le k\le n$, $(n-k)\to\infty$, a length of minimal full checking test under local $k$-fold glueings of variables is not greater than 3 for almost all Boolean functions $f(\widetilde x^n)$.

Détail

Keywords: Boolean function, test for inputs of circuits, local glueing of variables.