Formula
Exact CNF counting as a sum of indicator products
For each full assignment x, multiply the satisfaction indicators of all clauses. Call the product W(x). It is 1 exactly when every clause is satisfied, and 0 otherwise. Adding W(x) over all assignments therefore gives #F. For F = (p OR q) AND NOT p, W(x,y) = 1-(1-x)(1-y). In assignment order (0,0), (0,1), (1,0), (1,1), its values are 0, 1, 0, 0; their sum is 1. The sum includes every declared variable, even unused ones. This identity alone is not a faster algorithm: directly evaluating all assignments still examines 2^n cases.
0
1
Updated 2026-11-07
Tags
Math