Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The conclusion follows from all the premises. It seems to me that this means that conclusion from the conjuntion of the premises. Right? Why does logic uses comma instead?

share|improve this question
1  
This isn't really a CS specific question. The answer is simply that the $A\wedge\ldots\wedge C\Rightarrow M$ is so common, that it's often abbreviated to the form with commas. –  cody Dec 22 '13 at 17:39
    
@cody Is it your speculation? Do you see Gilles saying that the difference is distinction between lanugage and metalanguage? How abbreviation is related? Do you say that Gilles is wrong? Why is abbreviation used in textbooks? –  Val Dec 22 '13 at 18:24
3  
@cody $A, B \vdash M$ and $A \wedge B \implies M$ have very different statuses in terms of studying logic: one is a judgement, the other is a formula. The distinction doesn't matter when you're only using logic tangentially to do mathematics, but once you start studying logic for its own sake or for computer science applications (programming language semantics), it's very important. –  Gilles Dec 22 '13 at 18:37
    
Fair enough, I though it was a question about informal proofs. –  cody Dec 22 '13 at 22:50
add comment

1 Answer

up vote 6 down vote accepted

It's a distinction between language and metalanguage.

$A, B \vdash M$ says: if I have both $A$ and $B$ amongst my hypotheses, then I can deduce $M$.
$A \wedge B \vdash M$ says: if I have $A \wedge B$ amongst my hypotheses, then I can deduce $M$.
The fact that the two are equivalent comes from the definition of the operator $\wedge$.

I could define a new operator $?$ with these deduction rules (using the sequent calculus formulation): $$ \frac{A \vdash M}{A ? B \vdash M} \qquad \frac{B \vdash M}{A ? B \vdash M} \qquad \frac{\vdash A, M \quad \vdash B,M}{\vdash A?B,M} $$

This new operator has the same rules as $\wedge$ (in the sequent calculus), so I could substitute $?$ and $\wedge$ in a true judgement and still get a true judgement, and vice versa. Nonetheless, they are syntactically speaking two different propositions.

It takes a while to internalize the difference between the language and the metalanguage, especially in the beginning when you only study a logic which models our everyday reasoning. There are logics such as intuitionistic logic and linear logic which diverge further, and while these logics (especially linear logic) are more advanced, they are in some ways easier to handle because there is a clearer separation between the logic and the meta-logic.

I'll briefly discuss “and” in linear logic, to illustrate this point. To put it in a nutshell, in everyday logic, if you have a hypothesis, you can use it at multiple points in a proof. In linear logic, a hypothesis can only be used once, unless it's marked as reusable. Linear logic can thus model processes that aren't proofs as you think of them, but more physical processes, such as “if I have a cake before eating it, then I have no cake after eating it”. Linear logic has two conjunction operators. Both say: if I have a process that produces an $A$, and I have a process that produces a $B$, then I have a process that produces an $A$ “and” a $B$. They differ in how the processes are combined:

  • Multiplicative conjunction puts the two processes next to each other: given $\vdash \Gamma, A$ and $\vdash \Delta, B$ (a process that produces an $A$ and some more stuff, and a process that produces an $B$ and some more stuff), I can combine them to make $A \otimes B$ and the combined output of the two processes: $\vdash \Gamma, \Delta, A \otimes B$. For example, if I make a plate of spaghetti and an apple pie, I can eat a plate of spaghetti and an apple pie.
  • Additive conjunction runs the two processes together: given $\vdash \Gamma, A$ and $\vdash \Gamma, B$ (I can run the process and produce $\Gamma$ plus either $A$ or $B$), I can run that same process and produce both: $\vdash \Gamma, A \& B$. For example, if I can spend \$10 to get a plate of spaghetti or I can spend \$10 to get an apple pie, then \$10 gets me the choice of spaghetti or pie (but it doesn't get me $A \otimes B$, where I have both spaghetti and pie).
share|improve this answer
    
I could not understand how different interpretations of and in linear logic are related to the and we use in propositional calculus? BTW, I used the enlish word "implies" because it can mean both ⊨ and ⊢ (yet we use ∧ with →). Do you need to prove that A,B ⊢ M is equivalent to A∧B ⊢ M? –  Val Dec 22 '13 at 18:28
    
@Val Linear logic is an example of a logic where “and” means something different. Don't worry if you don't fully understand it, it's definitely advanced, I only included it to give you a taste of why there may be more than one notion of “and”. You don't need to prove that A,B ⊢ M is equivalent to A∧B ⊢ M because that comes from the definition of ∧ (though there are several different formalisms that may have different definitions). –  Gilles Dec 22 '13 at 18:35
    
Curiously, I have discovered that you should read A,B,C ⊢ X,Y,Z as if A and B and C then X **or** Y **or** Z. –  Val Dec 27 '13 at 23:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.