Boolean Gadgets for Binary Multiplication

in conjunctive normal form

X=(A+B+C)mod 2 = Parity3

(A+B+C+!X) (!A+!B+!C+X) (A+B+!C+X) (A+!B+C+X) (!A+B+C+X) (A+!B+!C+!X) (!A+B+!C+!X) (!A+!B+C+!X)

X=carry(A+B+C)

(A+B+!X) (B+C+!X) (A+C+!X) (!A+!B+X) (!A+!C+X) (!B+!C+X)

F=X*Y

(F+!X+!Y) (!F+X) (!F+Y)

F=(A+B) mod 2 = xor = Parity2

(A+B+!F) (!A+!B+!F) (A+!B+F) (!A+B+F)

C=Carry(A+B)

(A+!C) (B+!C) (!A+!B+C)

X=Y

(X+!Y) (!X+Y)

Distribution

(A+BC) = (A+B) (A+C)