Idea behind derivation in logic

Question

Lets say you have the following premises. $$\{ (C \lor E) \rightarrow \neg M, R \rightarrow M, C \}$$ which is equivalent to $$\{ ((C \lor E) \rightarrow \neg M) \land (R \rightarrow M) \land C \}$$

Addition means that $\{P\} \vdash P \lor Q$.

Why does $$\{ ((C \lor E) \rightarrow \neg M) \land (R \rightarrow M) \land C \} \vdash C \lor E$$

without truth tables with using addition?

I could see how you form the following implication

$$\{ (C \lor E) \rightarrow \neg M, R \rightarrow M, \mathbf{ C \vdash C \lor E} \}$$

I do not get the idea behind the derivation. I know the question is broad but I feel like I have always been missing something.

I am relatively new to logic.

Answer 1

Perhaps, this will help you understand the problem more clearly. If you are given the following premises,

$$(C \lor E) \rightarrow \neg M\\ R \rightarrow M\\ C$$

You can instantly verify that $C \lor E$ is true because we are given $C$ is true as our third premises. Therefore, since $C$ is true, $C \lor E$ is also true.

Perhaps, you are wondering what we can deduce from the remaining premises.

Well, since we know $C$ is true because it is the third premises, we know $C \lor E$ is also true, so $\neg M$ must be true because of the first premises.

Since $\neg M$ is true, then $M$ is false, so $R$ must also be false for the second premises to be true.

We cannot determine anything useful about $E$. The premises holds if either $E$ is true or false since $C$ is true.

Edit: The statements above can be easily written out as expressions, but I feel that it is easier to understand in words rather than symbols.

Answer 2

EDIT (Before the OP changed the $\vDash$ into $\vdash$ the comments directly below were aplicable. But now, scroll down to Answer below)

As several commentators already pointed out: you seem to be confusing $\vDash$ and $\vdash$

It is certainly true that $P$ logically implies $P \lor Q$ (you can verify this with a truth-table). We write this fact as $P \vDash P \lor Q$. That is: $\vDash$ stands for 'logically implies'.

Derivations are something different though. In a derivation we have specified certain rules that tell us what kind of statements can be written down during a derivation on the basis of other statements. And the key to these rules is that they are syntactic or formal. They say "If you have something that looks like bla-bla, then you can write down that looks like such-and-such".

So, to give a crazy example, I could define an inference rule that says: "whenever you have a statement of the form $\phi \lor \psi$. then you can write down ('infer') $\phi$ by itself. And suppose I call this rule Modus Bogus. Then Modus Bogus can be specified as (or: the fact that I have Modus Bogus available to me for a derivation means that) $\phi \lor \psi \vdash \phi$. That is, the $\vdash$ stands for 'allows me to derive'

Now, of course this Modus Bogus inference rule is of course bogus, because it allows me to derive $P$ from $P \lor Q$, which does not at all follow. That is: $P \lor Q \not \vDash P$ ... even though with Modus Bogus I have $P \lor Q \vdash P$! Do you see the difference?

Now, when you are talking about Addition, it is most likely an inference rule (because many proof systems have Addition as an inference rule and call it as such). So what you have to work with for a derivation is $P \vdash P \lor Q$. And yes, it is also true that $P \vDash P \lor Q$, but by 'Addition' we typically mean $P \vdash P \lor Q$.

Likewise, when you ask

Why does $$\{ ((C \lor E) \rightarrow \neg M) \land (R \rightarrow M) \land C \} \models C \lor E$$

you probably should have asked:

Why does $$\{ ((C \lor E) \rightarrow \neg M) , (R \rightarrow M) , C \} \vdash C \lor E$$

because you are asking for a derivation, rather than a truth-table demonstration of logical consequence.

Answer

If you start a derivation with

$$((C \lor E) \rightarrow \neg M) , (R \rightarrow M) , C $$

as your 3 premises, then you can immediately apply the Addition inference rule on $C$ to derive

$$C \lor E$$

and that will complete your derivation. And therefore:

$$\{ ((C \lor E) \rightarrow \neg M) , (R \rightarrow M) , C \} \vdash C \lor E$$