# Complementary for $SAT$

I have tried to find a definition of complementary language to $$SAT$$, I mean $$\overline{SAT}$$. But I still confused, in case of $$L\in \overline{SAT}$$ is it mean:
if $$\varphi\in L$$ then all interpretations are satisfy and if $$\varphi\notin L$$ then exists interpretation that unsatisfy
OR vice versa
if $$\varphi\notin L$$ then all interpretations are satisfy and if $$\varphi\in L$$ then exists interpretation that unsatisfy

please if you downvote write explanation of why

## 1 Answer

Usually, when we talk about the complement of a set we have some reference set to compare to. In the setting of languages over some alphabet $$\Sigma$$, this means that the complement of some language $$L$$ would be $$\overline L = \Sigma^\ast \setminus L$$, i.e. the set of all strings over $$\Sigma$$ which are not in $$L$$.

In the particular case of $$\mathrm{Sat} = \{\langle \psi \rangle \in \Sigma^\ast \mid \langle \psi \rangle \text{ encodes a satisfiable propositional formula } \psi \}$$ we find that $$\overline{\mathrm{Sat}} = \{w \in \Sigma^\ast \mid w \text{ does not encode a satisfiable propositional formula } \psi \}$$ and hence, $$\overline{\mathrm{Sat}}$$ consists of all strings which represent unsatisfiable propositional formulas (i.e. ones that have no satisfying interpretations) and all strings which don't represent formulas at all.

• Thank you, but I still don't know the answer – ChaosPredictor Jan 28 at 18:46
• Well, in that case I'm not sure how to help you any further. I suggest you review the basic terminology and come back to my answer when you have done so. If you have any specific questions, I can answer those, too. – Watercrystal Jan 29 at 11:53