Hitting Formula

logic

Definition

Hitting Formula

A hitting formula is a CNF formula in which every two distinct clauses contain a complementary pair of literals. Formally, for all distinct clauses $C_i$ and $C_j$, there exists a variable $x$ such that either $x\in C_i$ and $\neg x\in C_j$, or $\neg x\in C_i$ and $x\in C_j$.

Example: The formula

$$(a\vee b)\wedge (\neg a\vee c)\wedge (\neg b\vee \neg c)$$

is a hitting formula, since each pair of clauses hits in a complementary literal: the first and second clauses in $a$, the first and third clauses in $b$, and the second and third clauses in $c$.