This article is cited in 1 paper

Theoretical Foundations of Applied Discrete Mathematics

About some properties of Horn and anti-Horn functions

S. P. Gorshkov

Institute of Cryptography, Communications and Informatics, Moscow, Russia

Abstract: Some properties of weakly positive (anti-Horn) and weakly-negative (Horn) Boolean functions are investigated. Particularly, estimates are given for the complexity of constructing reduced form and for the possible lengths of expressions of considered functions, and it is shown that there are no limits for the weight of such functions.

Keywords: weakly positive (anti-Horn) Boolean function, weakly negative (Horn) Boolean function, computing complexity.

UDC: 519.7