0
$\begingroup$

In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot get my head around this.

Edit: Let me put it this way: I have constructed a circuit based on a Boolean formula, it is not Satisfiable, now I add one NOT-gate just before the output of the circuit. Does it make sense?

$\endgroup$
  • 3
    $\begingroup$ "For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition." How do you construct this F'? Try to make this map precise and see if you can determine if this map is bijective. If not, then that explains why the sets are of different size. $\endgroup$ – Discrete lizard Mar 27 at 12:57
  • $\begingroup$ There are infinitely many $k$-SAT formulae, so the set cardinalities are the same. However, note that it is very simple to turn a $k$-SAT formula into an unsatisfiable by just append $\wedge \bot$. It's not so simple to take a $k$-SAT formula and make it satisfiable (unless it already is). $\endgroup$ – Pål GD Mar 28 at 12:41
  • $\begingroup$ Thank you. But let me put it this way: I have constructed a circuit based on a Boolean formula, it is not Satisfiable, now I add one NOT-gate just before the output of the circuit. Does it make sense? $\endgroup$ – Mohak Shukla Mar 28 at 13:02
  • $\begingroup$ The input to $k$-SAT is a $k$-CNF. The negation of a $k$-CNF is a $k$-DNF. $\endgroup$ – Yuval Filmus Mar 28 at 13:15
4
$\begingroup$

Your trick doesn't really work. There are several issues.

First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$. But that doesn't tell you anything about the relationship between the number of unsatisfiable circuits of size $n$ vs the number of satisfiable circuits of size $n$. And, in general, there are way more circuits of size $n+1$ than circuits of size $n$, and most circuits are satisfiable, so the mapping you've found doesn't prove what you want it to prove. To prove what you're trying to prove, you'd need to find a bijection between unsatisfiable circuits of size $n$ and satisfiable circuits of size $n$ (not $n+1$); no such bijection exists.

Second, the mapping you describe isn't a bijection. Consider for example the circuit $\phi(x) = x$. This is satisfiable. Slapping a "not" in front if it, to get $\phi'(x) = \neg x$, yields another circuit that is also satisfiable. Many circuits are both satisfiable (there exists an assignment that makes $\phi$ true) and their-complement-is-satisfiable (there exists a different assignment that makes $\phi$ false). So negating an unsatisfiable circuit makes it satisfiable, but negating a satisfiable circuit doesn't necessarily make it unsatisfiable.

Finally, there's the distinction between circuits vs formulas, as David Richerby explains. If you negate the output of a CNF formula, the result isn't a CNF formula.

$\endgroup$
  • $\begingroup$ Thank you for explaining it in a clear and concise manner. $\endgroup$ – Mohak Shukla Mar 29 at 9:05
3
$\begingroup$

The sets of satisfiable and unsatisfiable formulas are the same size: both are countably infinite. However, that doesn't imply that there's any particular relationship between the number of satisfiable and unsatisfiable formulas of length $n$. For example, considering the natural numbers:

  • There are countably many odd numbers and countably many even numbers. Asymptotically, half the numbers between $0$ and $n$ are odd.

  • There are countably many multiples of seven and countably many non-multiples of seven. Asymptotically, only one seventh of the numbers between $0$ and $n$ are multiples of seven.

  • There are countably many perfect squares and countably many non-squares. Asymptotically, the fraction of perfect squares in $\{0, \dots, n\}$ is zero.

Your trick of negating a satisfying formula to get an unsatisfiable one has two problems:

  1. The negation of a tautology is unsatisfiable, but most satisfiable formulas are not tautologies. All you can say about the negation of a satisfiable formula is that it's falsifiable (has at least one truth assignment that makes it false); that's not the same thing as being unsatisfiable (every truth assignment makes it false).

  2. $k$-SAT demands that the formula is in CNF. If you just slap a "not" sign on the front of a CNF, the result isn't a CNF any more, and converting it back to CNF can make the formula exponentially longer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.