Re: cnf/dnf approximation

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 10/12/04 

Date: Tue, 12 Oct 2004 14:00:27 -0600

On 12 Oct 2004, Daniel A. Jimenez wrote:

> What is the obvious conversion? I know how to convert a k-CNF into a 3-CNF
> that is satisfiable iff the original k-CNF is satisfiable by introducing new
> variables, but the new formula isn't equivalent because it has a different
> truth table.

"equivalent" in the sense that expression E1 gets mapped to E2, E1 is
satisfiable if and only if E2 is satisfiable, and that the evaluation
function satisying E2 gives the truth function under the appropriate
restriction gives a satisfying function for E1. This probably isn't the
usual notion of 'equivalence,' so I retract that word.

J