Thursday, November 30, 2006

Compare two n-bit numbers using CNF

Here is an interesting problem:

Given two n-bit numbers A and B, represented as two single-bit-arrays An-1...A0 and Bn-1...B0,
Write a program that generates a CNF (Conjunctive Normal Form) expression that checks if A is less than B.

Hint - The CNF expression for checking if a single-bit number A0 is less than another single-bit number B0 is = !A0.B0 = !(A0 + !BO) in CNF

I'll post the answer to this soon.

No comments: