A propositional formula is said to be *affine* (or in *XOR-CNF*)
[Sch78,KS98,Zan02] if it is written as a finite conjunction of
linear equations over the two-element field, e.g.,
. As can be seen,
equations play the same role in affine formulas as clauses do in CNFs;
roughly, affine formulas represent conjunctions of parity or equivalence
constraints. This class proves interesting for knowledge representation,
since on one hand it is tractable for most of the common reasoning tasks,
and on the other hand the affine approximations of a knowledge base can be
made very small and are efficiently learnable [Zan02]. We show
that projecting an
affine formula onto a subset of its variables is quite easy too, enabling our
algorithm to run in polynomial time. The proof of the following lemma is
easily obtained with gaussian elimination [CUR84]: triangulate
with the variables in put rightmost, and then keep only those
equations formed upon ; full details are given in the technical report
version [Zan03].

Note that variables, literals and clauses are special cases of
disjunctions of linear equations.