Logical consequence equivalence proof

Question

Let $S$ be a set of propositional terms and let $t$ be a propositional term.

I am trying to prove the statement; $ S \vDash t$ iff $S\cup{\{\neg t}\}$ is unsatisfiable.

Now, in my head this makes sense, as if for whenever $S$ is true, then $t$ is true, so if $S$ is true then ${\{\neg t}\}$ is false and if $S$ i false then there is a propositional term in $S$ which is false, hence it cannot be satisfied.

But my lecturer gave the following argument;

$S\cup{\{\neg t}\}$ is unsatisfiable iff $-(1)$

$\forall$ valuations $v$, we have $v(s) = F$ for some $s \in S$ or $v(\neg t) = F$ iff $-(2)$

$\forall$ valuations $v$, if $v(s) = T \forall s \in S$, then $v(\neg t) = F$ $-(3)$

which is clearly equivalent to $S \vDash t$.

How does he get from$(2)$ to $(3)$?

Answer 1

We may re-phrase a little the argument of your teacher in order to simplify it a litte bit.

We have that:

$S ∪ \{ ¬t \}$ is unsatisfiable iff there is no valuation $v$ such that $v(¬t)=$TRUE and $v(s)$=TRUE for every $s ∈ S$.

Thus, we have equivalently [exchange the "there is no with "not for all" and then the negation sign applies to "and": use De Morgan to get an "or"] :

(1) for every valuation $v$, we have not $v(¬t)=$T [i.e. not $v(t)=$F i.e. $v(t)=$T] or not $v(s)=$T for every $s∈S$.

Now we can simply re-read it as:

(1') for every valuation $v$, not (for every $s∈S$ : $v(s)=$T ) or $v(t)=$T.

But we know that $(\lnot p \lor q)$ is equivalent to $(p \to q)$, and thus we have that:

(3) for every valuation $v$, if (for every $s∈S$ : $v(s)=$T ), then $v(t)=$T.

And this is:

$S \vDash t$.

Answer 2

I'd view the step from (2) to (3) as two steps. First, use the principle that $p\lor q$ is equivalent to $(\neg p)\to q$ to convert (2) into the equivalent statement (2.5) For all valuations $v$ if it is not the case that we have some $s\in S$ with $v(s)=F$ then $v(t)=F$. Second, use the principle that $\neg\exists x\,\phi(x)$ is equivalent to $\forall x\,\neg\phi(x)$ to convert (2.5) into (3).

Strictly speaking, one could even separate a third step, converting $\neg(v(s)=F)$ to $v(s)=T$.

Answer 3

$S\cup \{\neg t\}$ shall be unsatisfiable if no valuation can satisfy both $S$ and $\{\neg t\}$.   Then any valuation which does satisfy $S$, will be a valuation that does not satisfy $\{\neg t\}$ - that is, it is a valuation which values $t$ as true.   Therefore $S$ models $t$ if $S\cup\{\neg t\}$ is unsatisfiable.

$$\begin{array}{l}\begin{array}{|l}\text{There exists no valuation, $\nu$, where $\nu(\neg t)=\top$ and $\forall s\in S: \nu(s)=\top$}\\\hline \text{For any valuation, $\nu$, it will be $\nu(\neg t)=\bot$ or $\exists s\in S: \nu(s)=\bot$}\\ \text{For any valuation, $\nu$, where $\forall s\in S:\nu (s)=\top$, then it cannot be that $\nu(\neg t)=\top$}\end{array}\\\therefore\quad S\cup\{\neg t\}\text{ is unsatisfiable}\quad\implies\quad S\models t\end{array}$$

Conversely if $S$ models $t$, no valuation which satisfies $S$ will satisfy $\{\neg t\}$.   So $S\cup\{\neg t\}$ is unsatisfiable if $S$ models $t$.

$$\begin{array}{l}\begin{array}{|l}\text{For any valuation, $\nu$, where $\forall s\in S:\nu (s)=\top$, then $\nu(t)=\top$}\\\hline \text{There exists no valuation, $\nu$, where $\forall s\in S: \nu(s)=\top$ and $\nu(\neg t)=\top$}\end{array}\\\therefore\quad S\models t\quad\implies\quad S\cup\{\neg t\}\text{ is unsatisfiable}\end{array}$$

Conclusion: $S\cup\{\neg t\}$ is unsatisfiable iff $S$ models $t$.