0
$\begingroup$

$S,C,D,O$ are statements.

Then $((\neg S\rightarrow C)\wedge(C\rightarrow\neg D)\wedge(D\vee O)\wedge \neg O)\rightarrow S$ is a tautology.

This can be checked by a truth table or by the following.

(1) $\neg S\rightarrow C$

(2) $C\rightarrow\neg D$

(3) $D\vee O$

(4) $\neg O$

((1),(2),(3),(4) are premises.)

(5) $D$ ((3),(4)$\implies$(5))

(6) $\neg C$ ((2),(5)$\implies$(6))

(7) $S$ ((1),(6)$\implies$(7))

I don't understand why the above process, (1)-(7) verifies $((\neg S\rightarrow C)\wedge(C\rightarrow\neg D)\wedge(D\vee O)\wedge \neg O)\rightarrow S$ is a tautology.

$\endgroup$
1
  • 1
    $\begingroup$ Is one of the answers below enough for you ? If so, you can accept it and we can "close" the post. $\endgroup$ Feb 17, 2020 at 13:33

2 Answers 2

2
$\begingroup$

If $\varphi$ and $\psi$ are formulas, then $\varphi \to \psi$ is a tautology iff $\varphi \vdash \psi$. Here, $\varphi = (\neg S\rightarrow C)\wedge(C\rightarrow\neg D)\wedge(D\vee O)\wedge \neg O$ and $\psi = S$, so you have to show that $(\neg S\rightarrow C)\wedge(C\rightarrow\neg D)\wedge(D\vee O)\wedge \neg O \vdash S$ ie : $$\{\underbrace{\neg S\rightarrow C}_{(1)} , \underbrace{C\rightarrow\neg D}_{(2)} , \underbrace{D\vee O}_{(3)}, \underbrace{\neg O}_{(4)} \} \vdash S$$

What you wrote is a proof of the above, since :
$\{(3), (4)\} \vdash D$
$\{(2), D\} \vdash C$ hence $\{(2), (3), (4)\} \vdash C$
etc

$\endgroup$
2
  • $\begingroup$ Is ‘-iff-‘ a theorem? $\endgroup$
    – user682705
    Feb 17, 2020 at 8:06
  • 1
    $\begingroup$ @user682705 The sentence "If $\varphi$ and $\psi$ are formulas, then $\varphi \to \psi$ is a tautology iff $\varphi \vdash \psi$." is a theorem, yes. (Or rather an easy corollary of the definitions) $\endgroup$ Feb 17, 2020 at 8:12
1
$\begingroup$

The procedure checks that every truth assignment that satisfies all premises must also satisfy the conclusion.

The first (omitted) step is about premise 4) $\lnot O$ that forces the possible truth assignments $v$ to have $v(O)= \text F$.

Thus, considering 3) $D \lor O$, we must have $v(D)= \text T$, in order to satisfy it.

$v(D)= \text T$ imples $v(C)= \text F$, in order to satisfy 2), and this in turn implies $v(\lnot S)= \text F$ in order to satisy 1).

Conclusion: we have $v(S)= \text T$, i.e. evry truth assignment that satisfies all the premises will also satisfy the conclusion.


The same approach can be "reversed" working by contradiction.

Assume that the conclusion $S$ is False and see "what happens" to the premises: if we find a contradictory assignment, we can conclude that it is impossible that there is some truth assignment that satisfies the premises and not the conclusion.

$\endgroup$
2
  • $\begingroup$ Could you give me a simpler example of your answer? Thanks... $\endgroup$
    – user682705
    Feb 17, 2020 at 17:56
  • $\begingroup$ I think I got it. Thanks! $\endgroup$
    – user682705
    Feb 17, 2020 at 20:51

You must log in to answer this question.