2
$\begingroup$

I am studying some Discrete Mathematics lecture notes and am trying to understand the claim that SAT is the complement of TAUTOLOGY.
(I have posted on this SE site because I think that the root of my issue is a potential misunderstanding of logic.)

I have studied the definitions of SAT, NOT-SAT, TAUTOLOGY, and NOT-TAUTOLOGY (below).


SAT: given a Boolean formula $\phi$, determine if $\phi$ is satisfiable (that is, if there is an assignment of truth values to the literals in $\phi$, such that the evaluation of $\phi$ is TRUE).
Alternatively, one could consider SAT as the set of all Boolean formulae which are satisfiable.

NOT-SAT: given a Boolean formula $\gamma$, determine if $\gamma$ is not satisfiable (that is, if, for all assignments of truth values to the literals in $\gamma$, the evaluation of $\gamma$ is FALSE).
Alternatively, one could consider NOT-SAT as the set of all Boolean formulae which are not satisfiable.

TAUTOLOGY: given a Boolean formula $\epsilon$, determine if $\epsilon$ is satisfiable for every assignment of truth values to the literals in $\epsilon$ (that is, if, for all assignments of truth values to the literals in $\epsilon$, the evaluation of $\epsilon$ is TRUE).
Alternatively, one could consider TAUTOLOGY as the set of all Boolean formulae which are tautologies.

NOT-TAUTOLOGY: given a Boolean formula $\delta$, determine if $\delta$ is not a tautology (that is, if there is an assignment of truth values to the literals of $\delta$, such that the evaluation of $\delta$ is FALSE). Alternatively, one could consider NOT-TAUTOLOGY as the set of all Boolean formulae which are not tautologies.


MY ISSUE:

I am not sure if the following logic is sound:

If the yes answers for SAT are changed to no, then SAT is transformed to NOT-TAUTOLOGY, and vice versa.
If the yes answers for TAUTOLOGY are changed to no, then TAUTOLOGY is transformed to NOT-SAT, and vice versa.
Hence SAT is equivalent to NOT-TAUTOLOGY, and TAUTOLOGY is equivalent to NOT-SAT.

I would appreciate comments/answers which help me to check if the above reasoning is correct or not.


Having read the comments, I now have a new issue. (NB: this issue is rooted in the fact that I don't think I fully understand the definition of the complement of a decision problem.)

I understand that: $A$ is a tautology $\iff \neg A$ is unsatisfiable.

Now, my lecture notes state that, given a decision problem $X$, its complement $\bar X$ is the same decision problem with the yes and no answers reversed.

(In the context of SAT, I understand a yes answer to be a Boolean formula which is satisfiable, and a no answer to be a Boolean formula which is unsatisfiable.)

According to the lecture notes' definition of 'complement' we can define SAT and NOT-SAT as follows:

SAT: given a Boolean formula $B$, if there's an assignment of truth values to the literals in $B$ such that $B$ evaluates to TRUE, then $B$ results in a yes answer.
Else (i.e., if there is no assignment of truth values to the literals in $B$ such that $B$ evaluates to TRUE) $B$ results in a no answer.

NOT-SAT: given a Boolean formula $B$, if there's an assignment of truth values to the literals in $B$ such that $B$ evaluates to TRUE, then $B$ results in a no answer.
Else (i.e., if there is no assignment of truth values to the literals in $B$ such that $B$ evaluates to TRUE) $B$ results in a yes answer.

Now, assuming that TAUTOLOGY is the complement of SAT, TAUTOLOGY should be equivalent to NOT-SAT.
However, this is the definition of TAUTOLOGY:

Given a Boolean formula $B$, if there's an assignment of truth values to the literals in $B$ such that $B$ evaluates to FALSE, then $B$ results in a no answer.
Else (i.e., if, for all assignments of truth values to the literals in $B$, $B$ evaluates to TRUE) $B$ results in a yes answer.

At first glance, this might look equivalent to NOT-SAT, but it is not - the FALSE and TRUE are reversed.
Can anyone explain why this is, please? It is, I think, the core issue which is hindering my progress in understanding why SAT is the complement of TAUTOLOGY.

$\endgroup$
  • 1
    $\begingroup$ A formula $A$ is a tautology iff its negation : $\lnot A$ is not satisfiable. $\endgroup$ – Mauro ALLEGRANZA Oct 12 '16 at 19:18
  • 2
    $\begingroup$ @MauroALLEGRANZA (and CKKOY): I recommend not using any when you mean every in this kind of context (as any can be read as meaning some, turning the universal quantifier you intended into an existential quantifier). This is possibly the source of CKKOY's difficulty. $\endgroup$ – Rob Arthan Oct 12 '16 at 20:17
  • $\begingroup$ @RobArthan That is a helpful comment which I will keep in mind. However, it was not the source of my difficulty. $\endgroup$ – Caleb Owusu-Yianoma Oct 13 '16 at 17:20
  • $\begingroup$ @MauroALLEGRANZA Why does it follow that $\neg A$ is false for every assignment? $\endgroup$ – Caleb Owusu-Yianoma Oct 13 '16 at 17:22
  • $\begingroup$ @MauroALLEGRANZA I now understand why a formula $A$ is a tautology iff its negation $\neg A$ is unsatisfiable. However, I don't see the link between this and the statement: SAT is the complement of TAUTOLOGY. 'Why don't I see this link?' you might ask. The reason is that I am really struggling to understand the definition of the complement of a decision problem. Help would be much appreciated. $\endgroup$ – Caleb Owusu-Yianoma Oct 13 '16 at 18:09
2
$\begingroup$

A formula $A$ is a tautology if it is true with every assignment.

A formula $A$ is satisfiable if there is at least an assignemnt $v$ such that $A$ is true for $v$.

If $A$ is true for the assignment $v$, then its negation, $¬A$, is false for that assignment.

A formula $A$ is a tautology iff its negation, $¬A$, is not satisfiable.

The complement of a decision problem :

is the decision problem resulting from reversing the yes and no answers.

Thus, in a nutshell, if the answer to the problem "is $A$ in TAUT ?" is NO, then $¬A$ is in SAT.

More precisely, the problem of determining if some formula $A$ is not a tautology is thus equivalent to the problem of determining if the negation of the formula, $¬A$, is satisfiable.


It seems to me that it is only a terminological issue. Compare with :

Now we define some additional complexity classes related to $\text {P}$ and $\text {NP}$.

If $L ⊆ \{ 0, 1 \}^∗$ is a language, then we denote by $\overline L$ the complement of $L$.

We make the following definition: $\text {coNP} = \{ L \mid \overline L ∈ \text {NP} \}$.

$\text {coNP}$ is not the complement of the class $\text {NP}$. The following is an example of a $\text {coNP}$ language: $\overline {\text {SAT} } = \{ \varphi \mid \varphi \text { is not satisfiable} \}$.

The decision problems (or languages) are complementary : not the corresponding classes of formulae.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The answer is helpful. Should the last line of the excerpt from Sanjeev Arora & Boaz Barak read '$\text{SAT}=\{\varphi \mid \varphi \text{ is satisfiable}\}$'? $\endgroup$ – Caleb Owusu-Yianoma Oct 14 '16 at 18:35
  • 1
    $\begingroup$ @CalebOwusu-Yianoma It's correct the way it is now; there's a line above SAT, and that line is common notation for the complement of a set. $\endgroup$ – G. Bach Sep 15 '18 at 8:33

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.