A DUALITY PERSPECTIVE ON SET SYSTEMS

摘要

There is a well-known duality concept in propositional logic essentially relating CNF formulas to tautologically equivalent DNF formulas. In this paper we propose and discuss another duality principle in propositional logic based on a set theoretic duality interchanging clauses and literals, thus working for arbitrary normal form formulas when they are regarded as set systems. This concept is closely related to a corresponding duality of hypergraphs which is discussed in advance, where also hypergraphs are defined as set systems. Several specifically structured subclasses of hypergraphs shall be studied in this context.