RUS  ENG
Full version
JOURNALS // Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki // Archive

Zh. Vychisl. Mat. Mat. Fiz., 2015 Volume 55, Number 7, Pages 1266–1280 (Mi zvmmf10242)

This article is cited in 1 paper

Shortest and minimal disjunctive normal forms of complete functions

Yu. V. Maximovab

a Institute for Information Transmission Problems, Russian Academy of Sciences, Bolshoi Karetnyi per. 19/1, Moscow, 127051, Russia
b Moscow Institute of Physics and Technology, Institutskii per. 9, Dolgoprudnyi, Moscow oblast, 141700, Russia

Abstract: It was previously established that almost every Boolean function of $n$ variables with $k$ zeros, where $k$ is at most $\log_2n-\log_2\log_2n+1$, can be associated with a Boolean function of $2^{k-1}-1$ variables with $k$ zeros (complete function) such that the complexity of implementing the original function in the class of disjunctive normal forms is determined only by the complexity of implementing the complete function. An asymptotically tight bound is obtained for the minimum possible number of literals contained in the disjunctive normal forms of the complete function.

Key words: Boolean function, disjunctive normal form, complexity of implementing Boolean functions by disjunctive normal forms.

UDC: 519.7

Received: 17.06.2014

DOI: 10.7868/S0044466915070108


 English version:
Computational Mathematics and Mathematical Physics, 2015, 55:7, 1242–1255

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025