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.

  • $\begingroup$ I don't know what you mean by addition. Addition means that the statement $A \lor B$ is true if and only if either $A$ or $B$ is true or both. $\endgroup$ – Ralff Mar 31 '17 at 15:14
  • $\begingroup$ Addition here I am referring to P->PVQ is a tautology for the if then operator. $\endgroup$ – W. G. Mar 31 '17 at 15:23
  • $\begingroup$ Why did you write $P \models P \lor Q$? $\endgroup$ – Ralff Mar 31 '17 at 15:30
  • $\begingroup$ Let P=1, 1, 0, 0 and Q=1, 0, 1, 0. Then PVQ= 1, 1, 1, 0. Thus, P->Q= 1, 1, 1, 1 which is a tautology. Then, P⊨(PVQ). $\endgroup$ – W. G. Mar 31 '17 at 15:51
  • 1
    $\begingroup$ $\models$ and $\vdash$ are not the same symbol. I think you have them confused. The first means "models" and the second means "proves" $\endgroup$ – Stella Biderman Mar 31 '17 at 15:54

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.

| cite | improve this answer | |
  • $\begingroup$ I have looked for this answer for so long, and I finally get it. I had no idea that premises were assumed true. I thought the letters would be all the combinations of true and false. I finally get it. $\endgroup$ – W. G. Mar 31 '17 at 18:20
  • $\begingroup$ Great! I am glad you are able to understand. Yes. The premises are always assumed to be true. $\endgroup$ – Ralff Mar 31 '17 at 22:49

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.


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

| cite | improve this answer | |
  • $\begingroup$ I hate not being able to give the answer to you too. It is so irritating that I can not, because I was misinterpreting the use of those symbols which you figured out. I know I would not have been able to figure it out with both of these answers. I truly appreciate your help. $\endgroup$ – W. G. Mar 31 '17 at 18:25
  • $\begingroup$ @W.G. No problem, and I'm glad I could help!! :) $\endgroup$ – Bram28 Mar 31 '17 at 19:23

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.