0
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, but I still don't know the answer $\endgroup$ – ChaosPredictor Jan 28 at 18:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Watercrystal Jan 29 at 11:53

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.