checking '<' for two binary numbers in a cnf-formula
-
06-11-2019 - |
Pergunta
I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf:
Lets say n and m are two-digit binary numbers:
$n = n_2 + n_1$
$m = m_2 + m_1,$
where $n_i, m_i \in \{0,1\}$ for $i \in \{1,2\}$. Then the boolean formula, which will evaluate to true if $n < m$, would be:
$(\neg n_2 \land m_2) \lor (((\neg n_2 \land \neg m_2) \lor (n_2 \land m_2)) \land \neg n_1 \land m_1)$
As described, this formula should only evaluate to true if $n < m$. I know that every boolean formula can be transformed into a cnf formula, but it seems impractical, if i have higher digit binaries.
So is there a way to construct a cnf formula, which does the same?
Nenhuma solução correta