Part 2. Special Issues in Intellectual Systems Theory

On the relationship between proper families and edge orientations of Boolean cubes

K. D. Tsaregorodtsev

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: This paper is devoted to the study of relationship between proper families of Boolean functions and unique sink orientations of cubes. A one-to-one correspondence between these two objects is established, a number of properties are carried over from unique sink orientations to proper families. These results include an upper bound for the number of proper families of given size and coNP-completeness of the problem of recognizing properness.

Keywords: proper families of Boolean functions, unique sink orientations.