# rules of inference and truth table

$$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.

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

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

• Is ‘-iff-‘ a theorem?
– user682705
Feb 17, 2020 at 8:06
• @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) Feb 17, 2020 at 8:12

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.

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