RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1996 Volume 8, Issue 2, Pages 117–132 (Mi dm523)

Checking tests for superpositions of Boolean functions from elementary homogeneous functions

N. A. Solov'ev


Abstract: We consider the Shannon function for superpositions of Boolean functions of elementary homogeneous functions (constant, negation, conjunction, disjunction and addition modulo 2) which characterizes the length of the minimal checking test. We point out a class of the initial Boolean functions such that the Shannon function is attained on superpositions of those functions. A general approach to solving similar problems is suggested which is based on the analysis of the distinguishability tables.

UDC: 519.714

Received: 25.05.1992

DOI: 10.4213/dm523


 English version:
Discrete Mathematics and Applications, 1996, 6:3, 241–255

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024