Satisfiability on hypergraphs

In [4] R.Cowen considers a generalization of the resolution rule for hypergraphs and introduces a notion of satisfiability of families of sets of vertices via 2-colorings piercing elements of such families. He shows, for finite hypergraphs with no one-element edges that if the empty set is a consequence ofA by the resolution rule, thenA is not satisfiable. Alas the converse is true for a restricted class of hypergraphs only, and need not to be true in the general case. In this paper we show that weakening slightly the notion of satisfiability, we get the equivalence of unsatisfiability and the derivability of the empty set for any hypergraph. Moreover, we show the compactness property of hypergraph satisfiability (in the weaker sense) and state its equivalence to BPI, i.e. to the statement that in every Boolean algebra there exists an ultrafilter.     

Reversed Resolution in Reducing General Satisfiability Problem

In the following we show that general property S considered by Cowen [1], Cowen and Kolany in [3] and earlier by Cowen in [2] and Kolany in [4] as hypergraph satisfiability, can be constructively reduced to (3, 2) · SAT, that is to satisfiability of (at most) triples with two-element forbidden sets. This is an analogue of the“classical” result on the reduction of SAT to 3 · SAT.     

Consequence Operations Based on Hypergraph Satisfiability

Four consequence operators based on hypergraph satisfiability are defined. Their properties are explored and interconnections are displayed. Finally their relation to the case of the Classical Propositional Calculus is shown.