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

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top