Let $\Gamma$ be a set of formulas and $\phi$ be a formula. Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$.

This seemed pretty obvious but I wanted to see if my proof made sense:

Proof: $(\Rightarrow)$

To derive for a contradiction, suppose that: $\Gamma \models \phi$. That means for all truth assignments $v$, for $\gamma \in \Gamma$, if $v(\gamma) = T$, then $v(\phi) = T$.

But this contradicts our assumption that $\Gamma \cup \{\neg \phi \}$ is satisfiable by the fact that $v(\phi) = T$ cannot happen so: $\Gamma \not \models \phi$ .


So by the definition of $\Gamma \not \models \phi$, we have that there is some truth assignment $v$ which satisfies $\Gamma$ but does not satisfy $\phi$. So that means $v(\phi) = F$ since $v(\phi) \not = T$ which implies that $v(\neg \phi) = T$ which means $v$ satisfies $\Gamma \cup \{\neg \phi\}$.

I feel like I'm missing something in the forward direction, but at the same time... It looks pretty trivial as well. Am I missing anything crucial?

Thank you!

  • $\begingroup$ Your proof is correct. $\endgroup$ – Mauro ALLEGRANZA Oct 18 '14 at 9:07

Your proof is entirely correct. Cheers :).


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.