Representation theorems for hypergraph satisfiability

Abstract

Given a set of propositions, one can consider its inconsistency hypergraph. Then the satisfiability of sets of clauses with respect to that hypergraph (see [1], [6]) turns out to be the usual satisfiability. The problem is which hypergraphs can be obtained from sets of formulas as inconsistency hypergraphs. In the present paper it is shown that this can be done for all hypergraphs with countably many vertices and pairwise incomparable edges. Then, a general method of transforming the combinatorial problems into the satisfiability problem is shown.