Photo:1
Photo:2
Photo:3
Photo:4
Photo:1 Photo:2 Photo:3 Photo:4 |
| Syntax | |
| 3>
The language of classical linear logic (CLL) is defined inductively by the BNF notation
A
::=
p ∣ p⊥
∣
A ⊗ A ∣ A ⊕ A
∣
A & A ∣ A ⅋ A
∣
1 ∣ 0 ∣ ⊤ ∣ ⊥
∣
!A ∣ ?A
Here p and p⊥ range over logical atoms. For reasons to be explained below, the connectives ⊗, ⅋, 1, and ⊥ are called multiplicatives, the connectives &, ⊕, ⊤, and 0 are called additives, and the connectives ! and ? are called exponentials. We can further employ the following terminology:
⊗ is called "multiplicative conjunction" or "times" (or sometimes "tensor")
⊕ is called "additive disjunction" or "plus"
& is called "additive conjunction" or "with"
⅋ is called "multiplicative disjunction" or "par"
! is pronounced "of course" (or sometimes "bang")
? is pronounced "why not"
Every proposition A in CLL has a dual A⊥, defined as follows:
(p)⊥ = p⊥
(p⊥)⊥ = p
(A ⊗ B)⊥ = A⊥ ⅋ B⊥
(A ⅋ B)⊥ = A⊥ ⊗ B⊥
(A ⊕ B)⊥ = A⊥ & B⊥
(A & B)⊥ = A⊥ ⊕ B⊥
(1)⊥ = ⊥
(⊥)⊥ = 1
(0)⊥ = ⊤
(⊤)⊥ = 0
(!A)⊥ = ?(A⊥)
(?A)⊥ = !(A⊥)
Observe that (-)⊥ is an involution, i.e., A⊥⊥ = A for all propositions. A⊥ is also called the linear negation of A.
The columns of the table suggest another way of classifying the connectives of linear logic, termed polarity: the connectives negated in the left column (⊗, ⊕, 1, 0, !) are called positive, while their duals on the right (⅋, &, ⊥, ⊤, ?) are called negative.
Linear implication is not included in the grammar of connectives, but is definable in CLL using linear negation and multiplicative disjunction, by A ⊸ B := A⊥ ⅋ B. The connective ⊸ is sometimes pronounced "lollipop", owing to its shape.
[edit] Tags:Classical,Lollipop,Lu,Reason,Class,Proposition,Range, | |
| Sequent calculus presentation | |
| 2>
One way of defining linear logic is as a sequent calculus. We use the letters Γ and Δ to range over list of propositions A1, ..., An, also called contexts. A sequent places a context to the left and the right of the turnstile, written Γ Δ. Intuitively, the sequent asserts that the conjunction of Γ entails the disjunction of Δ (though we mean the "multiplicative" conjunction and disjunction, as explained below). Girard describes classical linear logic using only one-sided sequents (where the left-hand context is empty), and we follow here that more economical presentation.
We now give inference rules describing how to build proofs of sequents.
First, to formalize the fact that we do not care about the order of propositions inside a context, we add the structural rule of exchange:
Γ
Γ'
(Γ' a permutation of Γ)
(Alternatively we could accomplish the same thing by defining contexts to be multisets rather than lists.) Note that we do not add the structural rules of weakening and contraction, because we do care about the absence of propositions in a sequent, and the number of copies present.
Next we add initial sequents and cuts:
A, A⊥
Γ, A
A⊥, Δ
Γ, Δ
The cut rule can be seen as a way of composing proofs, and initial sequents serve as the units for composition. In a certain sense these rules are redundant: as we introduce additional rules for building proofs below, we will maintain the property that arbitrary initial sequents can be derived from atomic initial sequents, and that whenever a sequent is provable it can be given a cut-free proof. Ultimately, this canonical form property (which can be divided into the completeness of atomic initial sequents and the cut-elimination theorem, inducing a notion of analytic proof) lies behind the applications of linear logic in computer science, since it allows the logic to be used in proof search and as a resource-aware lambda-calculus.
Now, we explain the connectives by giving logical rules. Typically in sequent calculus one gives both "right-rules" and "left-rules" for each connective, essentially describing two modes of reasoning about propositions involving that connective (e.g., verification and falsification). In a one-sided presentation, one instead makes use of negation: the right-rules for a connective (say ⅋) effectively play the role of left-rules for its dual (⊗). So, we should expect a certain "harmony" between the rule(s) for a connective and the rule(s) for its dual.
[edit] Tags:Sequent Calculus,Structural Rules,Contraction,Weakening,Units,Canonical Form,Completeness Of Atomic Initial Sequents,Cut-elimination Theorem,Analytic Proof,Harmony,Logic In Computer Science,Inference,Reasoning,Fact,Completeness,Set,Theorem,Structural Rule, | |
| Multiplicatives | |
| 3>
The rules for multiplicative conjunction (⊗) and disjunction (⅋):
Γ, A
Δ, B
Γ, Δ, A ⊗ B
Γ, A, B
Γ, A ⅋ B
and for their units:
1
Γ
Γ, ⊥
Observe that the rules for multiplicative conjunction and disjunction are admissible for plain conjunction and disjunction under a classical interpretation (i.e., they are admissible rules in LK).
[edit] Tags:Admissible,Interpretation, | |
| Additives | |
| 3>
The rules for additive conjunction (&) and disjunction (⊕) :
Γ, A
Γ, B
Γ, A & B
Γ, A
Γ, A ⊕ B
Γ, B
Γ, A ⊕ B
and for their units:
Γ, ⊤
(no rule for 0)
Observe that the rules for additive conjunction and disjunction are again admissible under a classical interpretation. But now we can explain the basis for the multiplicative/additive distinction in the rules for the two different versions of conjunction: for the multiplicative connective (⊗), the context of the conclusion (Γ, Δ) is split up between the premises, whereas for the additive case connective (&) the context of the conclusion (Γ) is carried whole into both premises.
[edit] Tags:Premise, | |
| Exponentials | |
| 3>
The exponentials are used to give controlled access to weakening and contraction. Specifically, we add structural rules of weakening and contraction for ?'d propositions:
Γ
Γ, ?A
Γ, ?A, ?A
Γ, ?A
and use the following logical rules:
?Γ, A
?Γ, !A
Γ, A
Γ, ?A
One might observe that the rules for the exponentials follow a different pattern from the rules for the other connectives, and that there is no longer such a clear symmetry between the duals ! and ?. This situation is remedied in alternative presentations of CLL (e.g., the LU presentation).
[edit] Tags: | |
| Remarkable formulae | |
| 2>
In addition to the De Morgan dualities described above, some important equivalences in linear logic include:
Distributivity
Exponential isomorphism
(Here .)
The following is not in general an equivalence, only an implication:
Semi-distributivity
[edit] Tags:Dualities,De Morgan, | |
| Encoding classical/intuitionistic logic in linear logic | |
| 2>
Both intuitionistic and classical implication can be recovered from linear implication by inserting exponentials: intuitionistic implication is encoded as !A ⊸ B, and classical implication as !A ⊸ ?B.[3]. The idea is that exponentials allow us to use a formula as many times as we need, which is always possible in classical and intuitionistic logic.
Formally, there exists a translation of formulae of intuitionistic logic to formulae of linear logic in a way which guarantees that the original formula is provable in intuitionistic logic if and only if the translated formula in provable in linear logic. Using the Gödel–Gentzen negative translation, we can thus embed classical first-order logic into linear first-order logic.
[edit] Tags:Intuitionistic Logic,Gödel–gentzen Negative Translation,First-order Logic,First-order, | |
| The resource interpretation | |
| 2>
Lafont (1993) first showed how intuitionistic linear logic can be explained as a logic of resources, so providing the logical language with access to formalisms that can be used for reasoning about resources within the logic itself, rather than, as in classical logic, by means of non-logical predicates and relations. Antony Hoare (1985)'s classical example of the vending machine can be used to illustrate this idea.
Suppose we represent a candy bar by the atomic proposition candy, and a dollar by $1. To state the fact that a dollar will buy you one candy bar, we might write the implication $1 ⇒ candy. But in ordinary (classical or intuitionistic) logic, from A and A ⇒ B one can conclude A ∧ B. So, ordinary logic leads us to believe that we can buy the candy bar and keep our dollar! Of course, we can avoid this problem by using more sophisticated encodings, although typically such encodings suffer from the frame problem. However, the rejection of weakening and contraction allows linear logic to avoid this kind of spurious reasoning even with the "naive" rule. Rather than $1 ⇒ candy, we express the property of the vending machine as a linear implication $1 ⊸ candy. From $1 and this fact, we can conclude candy, but not $1 ⊗ candy. In general, we can use the linear logic proposition A ⊸ B to express the validity of transforming resource A into resource B.
Running with the example of the vending machine, let us consider the "resource interpretations" of the other multiplicative and additive connectives. (The exponentials provide the means to combine this resource interpretation with the usual notion of persistent logical truth.)
Multiplicative conjunction (A ⊗ B) denotes simultaneous occurrence of resources, to be used as the consumer directs. For example, if you buy a stick of gum and a bottle of soft drink, then you are requesting gum ⊗ drink. The constant 1 denotes the absence of any resource, and so functions as the unit of ⊗.
Additive conjunction (A & B) represents alternative occurrence of resources, the choice of which the consumer controls. If in the vending machine there is a packet of chips, a candy bar, and a can of soft drink, each costing one dollar, then for that price you can buy exactly one of these products. Thus we write $1 ⊸ (candy & chips & drink). We do not write $1 ⊸ (candy ⊗ chips ⊗ drink), which would imply that one dollar suffices for buying all three products together. However, from $1 ⊸ (candy & chips & drink), we can correctly deduce $3 ⊸ (candy ⊗ chips ⊗ drink), where $3 := $1 ⊗ $1 ⊗ $1. The unit ⊤ of additive conjunction can be seen as a wastebasket or garbage collector for irrelevant alternatives. For example, we can write $3 ⊸ (candy ⊗ ⊤) to express that three dollars will buy you a candy bar and something else (we don't care what).
Additive disjunction (A ⊕ B) represents alternative occurrence of resources, the choice of which the machine controls. For example, suppose the vending machine permits gambling: insert a dollar and the machine may dispense a candy bar, a packet of chips, or a soft drink. We can express this situation as $1 ⊸ (candy ⊕ chips ⊕ drink). The constant 0 represents a product that cannot be made, and thus serves as the unit of ⊕ (a machine that might produce A or 0 is as good as a machine that always produces A because it will never succeed in producing a 0).
Multiplicative disjunction (A ⅋ B) is more difficult to gloss in terms of the resource interpretation, although we can encode back into linear implication, either as A⊥ ⊸ B or B⊥ ⊸ A.
[edit] Tags:Antony Hoare,Frame Problem,Garbage Collector,Logical Truth,Truth,Formalism,Classical Logic,Relation,Validity,Predicate,Function, | |
| Proof nets | |
| 3>
Main article: Proof net
Introduced by Jean-Yves Girard, proof net have been created to avoid the bureaucracy, that is all the things that make two derivation different in the logical point of view, but not in a “moral” point of view.
For instance, these two proofs are “morally” identical:
A, B, C, D
A ⅋ B, C, D
A ⅋ B, C ⅋ D
A, B, C, D
A, B, C ⅋ D
A ⅋ B, C ⅋ D
The goal of proof net is to make them identical by creating a graphical representation of them.
[edit] Tags:Jean-yves Girard,Proof Net, | |
| Decidability/complexity of entailment | |
| 2>
The entailment relation in full CLL is undecidable.[4] Fragments of CLL are often considered, for which the decision problem is more subtle:
Multiplicative linear logic (MLL): only the multiplicative connectives. MLL entailment is NP-complete.
Multiplicative-additive linear logic (MALL): only multiplicatives and additives (i.e., exponential-free). MALL entailment is PSPACE-complete.
Multiplicative-exponential linear logic (MELL): only multiplicatives and exponentials. The decidability of MELL entailment is currently open.
[edit] Tags:Entailment,Undecidable,Np-complete,Pspace-complete,Decidability,Decision Problem, | |
| Variants of linear logic | |
| 2>
Many variations of linear logic arise by further tinkering with the structural rules:
Affine logic, which forbids contraction but allows global weakening.
Strict logic or relevant logic, which forbids weakening but allows global contraction.
Non-commutative logic or ordered logic, which removes the rule of exchange, in addition to barring weakening and contraction. In ordered logic, linear implication divides further into left-implication and right-implication.
Different intuitionistic variants of linear logic have been considered. When based on a single-conclusion sequent calculus presentation, like in ILL (Intuitionistic Linear Logic), the connectives ⅋, ⊥, and ? are absent, and linear implication is treated as a primitive connective. In FILL (Full Intuitionistic Linear Logic) the connectives ⅋, ⊥, and ? are present, linear implication is a primitive connective and, similarly to what happens in intuitionistic logic, all connectives (except linear negation) are independent. There are also first- and higher-order extensions of linear logic, whose formal development is somewhat standard (see first-order logic and higher-order logic).
[edit] Tags:Affine Logic,Strict Logic,Relevant Logic,Higher-order Logic, | |
| See also | |
| 2>
Logic portal
Linear types
Logic of unity (LU)
Proof nets
Geometry of interaction
Game semantics
Intuitionistic logic
Computability logic
Ludics
Chu spaces
Uniqueness type
[edit] Tags:Game Semantics,Logic Portal,Linear Types,Logic Of Unity,Proof Nets,Geometry Of Interaction,Computability Logic,Ludics,Chu Spaces,Uniqueness Type,Semantics, | |
| Notes | |
| 2>
^ Girard, Jean-Yves (1987). "Linear logic". Theoretical Computer Science 50 (1): 1–102. doi:10.1016/0304-3975(87)90045-4. http://iml.univ-mrs.fr/~girard/linear.pdf.
^ Baez, John; Stay, Mike (2008). Bob Coecke. ed. "Physics, Topology, Logic and Computation: A Rosetta Stone". New Structures of Physics. http://math.ucr.edu/home/baez/rosetta.pdf.
^ [1], chapter 2
^ For this and the below complexity results, see: Lincoln, Patrick; Mitchell, John; Scedrov, Andre; Shankar, Natarajan (1992). "Decision Problems for Propositional Linear Logic". Annals of Pure and Applied Logic 56: 239–311. doi:10.1016/0168-0072(92)90075-B.
[edit] Tags: | |
| References | |
| 2>
Girard, Jean-Yves. Linear logic, Theoretical Computer Science, Vol 50, no 1, pp. 1–102, 1987.
Girard, Jean-Yves, Lafont, Yves, and Taylor, Paul. Proofs and Types. Cambridge Press, 1989. (An electronic version is online at [2].)
Hoare, C. A. R., 1985. Communicating Sequential Processes. Prentice-Hall International. ISBN 0131532715
Lafont, Yves, 1993. Introduction to Linear Logic. Lecture notes from TEMPUS Summer School on Algebraic and Categorical Methods in Computer Science, Brno, Czech Republic.
Troelstra, A.S. Lectures on Linear Logic. CSLI (Center for the Study of Language and Information) Lecture Notes No. 29. Stanford, 1992.
A. S. Troelstra, H. Schwichtenberg (1996). Basic Proof Theory. In series Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, ISBN 0-521-77911-1.
Di Cosmo, Roberto, and Damos, Vincent. The linear logic primer. [3]
[edit] Tags:Isbn 0131532715,Troelstra, A.s.,A. S. Troelstra,Proof Theory,Theory, | |
| External links | |
| 2>
Patrick Lincoln Introduction to Linear Logic (Postscript)
Introduction to Linear Logic by Torben Brauner [4]
A taste of linear logic by Philip Wadler [5]
Linear Logic by Roberto Di Cosmo and Dale Miller. The Stanford Encyclopedia of Philosophy (Fall 2006 Edition), Edward N. Zalta (ed.).
Overview of linear logic programming by Dale Miller. In Linear Logic in Computer Science, edited by Ehrhard, Girard, Ruet, and Scott. Cambridge University Press. London Mathematical Society Lecture Notes, Volume 316, 2004.
v
d
e
Logic
Overview
Academic
areas
Argumentation theory
Axiology
Critical thinking
Computability theory
Formal semantics
History of logic
Informal logic
Logic in computer science
Mathematical logic
Mathematics
Metalogic
Metamathematics
Model theory
Philosophical logic
Philosophy
Philosophy of logic
Philosophy of mathematics
Proof theory
Set theory
Foundational
concepts
Abduction
Analytic truth
Antinomy
A priori
Deduction
Definition
Description
Entailment
Induction
Inference
Logical consequence
Logical form
Logical implication
Logical truth
Name
Necessity
Meaning
Paradox
Possible world
Presupposition
Probability
Reason
Reasoning
Reference
Semantics
Statement
Strict implication
Substitution
Syntax
Truth
Truth value
Validity
Philosophical logic
Critical thinking
and
Informal logic
Analysis
Ambiguity
Argument
Belief
Bias
Credibility
Evidence
Explanation
Explanatory power
Fact
Fallacy
Inquiry
Opinion
Parsimony
Premise
Propaganda
Prudence
Reasoning
Relevance
Rhetoric
Rigor
Vagueness
Theories of deduction
Constructivism
Dialetheism
Fictionalism
Finitism
Formalism
Intuitionism
Logical atomism
Logicism
Nominalism
Platonic realism
Pragmatism
Realism
Metalogic and metamathematics
Cantor's theorem
Church's theorem
Church's thesis
Consistency
Effective method
Foundations of mathematics
Gödel's completeness theorem
Gödel's incompleteness theorems
Soundness
Completeness
Decidability
Interpretation
Löwenheim–Skolem theorem
Metatheorem
Satisfiability
Independence
Type–token distinction
Use–mention distinction
Mathematical logic
General
Formal language
Formation rule
Formal system
Deductive system
Formal proof
Formal semantics
Well-formed formula
Set
Element
Class
Classical logic
Axiom
Natural deduction
Rule of inference
Relation
Theorem
Logical consequence
Axiomatic system
Type theory
Symbol
Syntax
Theory
Traditional logic
Proposition
Inference
Argument
Validity
Cogency
Syllogism
Square of opposition
Venn diagram
Propositional calculus
and Boolean logic
Boolean functions
Propositional calculus
Propositional formula
Logical connectives
Truth tables
Predicate
First-order
Quantifiers
Predicate
Second-order
Monadic predicate calculus
Set theory
Set
Empty set
Enumeration
Extensionality
Finite set
Function
Subset
Power set
Countable set
Recursive set
Domain
Range
Ordered pair
Uncountable set
Model theory
Model
Interpretation
Non-standard model
Finite model theory
Truth value
Validity
Proof theory
Formal proof
Deductive system
Formal system
Theorem
Logical consequence
Rule of inference
Syntax
Computability theory
Recursion
Recursive set
Recursively enumerable set
Decision problem
Church–Turing thesis
Computable function
Primitive recursive function
Non-classical logic
Modal logic
Alethic
Axiologic
Deontic
Doxastic
Epistemic
Temporal
Intuitionism
Intuitionistic logic
Constructive analysis
Heyting arithmetic
Intuitionistic type theory
Constructive set theory
Fuzzy logic
Degree of truth
Fuzzy rule
Fuzzy set
Fuzzy finite element
Fuzzy set operations
Substructural logic
Structural rule
Relevance logic
Linear logic
Paraconsistent logic
Dialetheism
Description logic
Ontology
Ontology language
Logicians
Anderson
Aristotle
Averroes
Avicenna
Bain
Barwise
Bernays
Boole
Boolos
Cantor
Carnap
Church
Chrysippus
Curry
De Morgan
Frege
Geach
Gentzen
Gödel
Hilbert
Kleene
Kripke
Leibniz
Löwenheim
Peano
Peirce
Putnam
Quine
Russell
Schröder
Scotus
Skolem
Smullyan
Tarski
Turing
Whitehead
William of Ockham
Wittgenstein
Zermelo
Lists
Topics
Outline of logic
Index of logic articles
Mathematical logic
Boolean algebra
Set theory
Other
Logicians
Rules of inference
Paradoxes
Fallacies
Logic symbols
Tags:Substructural Logic,Constructive,Argumentation Theory,Axiology,Critical Thinking,Computability Theory,Formal Semantics,History Of Logic,Informal Logic,Mathematical Logic,Mathematics,Metalogic,Metamathematics,Model Theory,Philosophical Logic,Philosophy,Philosophy Of Logic,Philosophy Of Mathematics,Set Theory,Abduction,Analytic Truth,Antinomy,A Priori,Deduction,Definition,Description,Induction,Logical Consequence,Logical Form,Logical Implication,Name,Necessity,Meaning,Paradox,Possible World,Presupposition,Probability,Reference,Statement,Strict Implication,Substitution,Syntax,Truth Value,Analysis,Ambiguity,Argument,Belief,Bias,Credibility,Evidence,Explanation,Explanatory Power,Fallacy,Inquiry,Opinion,Parsimony,Propaganda,Prudence,Relevance,Rhetoric,Rigor,Vagueness,Theories Of Deduction,Constructivism,Dialetheism,Fictionalism,Finitism,Intuitionism,Logical Atomism,Logicism,Nominalism, | |
zote monety view link view link view link view link view link |