[Math] Why is SAT the complement of TAUTOLOGY

logicpropositional-calculussatisfiability

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.

Best Answer

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.

Related Question