|
This article is cited in 1 scientific paper (total 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.
Received: 17.06.2014
Citation:
Yu. V. Maximov, “Shortest and minimal disjunctive normal forms of complete functions”, Zh. Vychisl. Mat. Mat. Fiz., 55:7 (2015), 1266–1280; Comput. Math. Math. Phys., 55:7 (2015), 1242–1255
Linking options:
https://www.mathnet.ru/eng/zvmmf10242 https://www.mathnet.ru/eng/zvmmf/v55/i7/p1266
|
Statistics & downloads: |
Abstract page: | 282 | Full-text PDF : | 91 | References: | 46 | First page: | 4 |
|