Generation of Images of Several Literals

Аннотация

In this article we describe the construction of discrete functions such that some of their values specify (generate) arbitrary pairs of literals under two mutually exclusive assumptions: the function is equal to one of the variables or to its negation. We prove the existence of such functions with at least seven arguments and show that for sufficiently large n this function can be defined on O(n log₂n) tuples. We also consider the problem of simultaneous generation of k literals. We show that with k < n − log₂n+log₂(log₃ 4−1), functions generating arbitrary k literals exist, and if (n−log₂n−k) → ∞ as n → ∞ , then almost all functions generate arbitrary k literals.