Pure Horn CNFs, directed hypergraphs, and closure systems are objects studied in di erent subareas of theoretical computer science. Nevertheless, these three objects are in some sense isomorphic. Thus also properties derived for one of these objects can be usually translated in some way for the other two. In this talk we will concentrate on the problem of nding a shortest CNF representation of a given pure Horn function. This is a problem with many practical applications in arti cial intelligence (knowledge compression) and other areas of computer science (e.g. relational data bases). In this talk we survey complexity results known for this problem and then concentrate on the relationships between CNF representations of Horn functions and certain sets of implicates of these functions, called essential sets of implicates. The de nition of essential sets is based on the properties of resolution. Essential sets can be shown to ful ll an interesting orthogonality property: every CNF representation and every (nonempty) essential set must intersect. This property leads to non-trivial lower bounds on the CNF size, which are sometimes tight and sometimes have a gap. We will try to derive connections to the known properties of minimal implicational bases.
The talk is based on joint research with Endre Boros, Alex Kogan, Petr Kucera, and Petr Savicky.