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
and , there exists a variable such that either and , or and . Example: The formula
is a hitting formula, since each pair of clauses hits in a complementary literal: the first and second clauses in
, the first and third clauses in , and the second and third clauses in .