|
Affine Logic
Affine logic is a substructural logic whose proof theory rejects the structural rule of contraction. It can also be characterized as linear logic with weakening. The name "affine logic" is associated with linear logic, to which it differs by allowing the weakening rule. Jean-Yves Girard introduced the name as part of the geometry of interaction semantics of linear logic, which characterizes linear logic in terms of linear algebra; here he alludes to affine transformations on vector spaces. Affine logic predated linear logic. V. N. Grishin used this logic in 1974, after observing that Russell's paradox cannot be derived in a set theory without contraction, even with an unbounded comprehension axiom.Cf. Frederic Fitch's demonstrably consistent set theory Likewise, the logic formed the basis of a decidable sub-theory of predicate logic, called 'Direct logic' (Ketonen & Wehrauch, 1984; Ketonen & Bellin, 1989). Affine logic can be embedded into linear logic by rewri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Substructural Logic
In logic, a substructural logic is a logic lacking one of the usual structural rules (e.g. of classical and intuitionistic logic), such as weakening, contraction, exchange or associativity. Two of the more significant substructural logics are relevance logic and linear logic. Examples In a sequent calculus, one writes each line of a proof as :\Gamma\vdash\Sigma. Here the structural rules are rules for rewriting the LHS of the sequent, denoted Γ, initially conceived of as a string (sequence) of propositions. The standard interpretation of this string is as conjunction: we expect to read :\mathcal A,\mathcal B \vdash\mathcal C as the sequent notation for :(''A'' and ''B'') implies ''C''. Here we are taking the RHS Σ to be a single proposition ''C'' (which is the intuitionistic style of sequent); but everything applies equally to the general case, since all the manipulations are taking place to the left of the turnstile symbol \vdash. Since conjunction is a c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unrestricted Comprehension
In many popular versions of axiomatic set theory, the axiom schema of specification, also known as the axiom schema of separation (''Aussonderungsaxiom''), subset axiom, axiom of class construction, or axiom schema of restricted comprehension is an axiom schema. Essentially, it says that any definable subclass of a set is a set. Some mathematicians call it the axiom schema of comprehension, although others use that term for ''unrestricted'' comprehension, discussed below. Because restricting comprehension avoided Russell's paradox, several mathematicians including Zermelo, Fraenkel, and Gödel considered it the most important axiom of set theory. Statement One instance of the schema is included for each formula \varphi in the language of set theory with free variables among ''x'', ''w''1, ..., ''w''''n'', ''A''. So ''B'' does not occur free in \varphi. In the formal language of set theory, the axiom schema is: :\forall w_1,\ldots,w_n \, \forall A \, \exists B \, \forall x ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Affine Type System
Substructural type systems are a family of type systems analogous to substructural logics where one or more of the structural rules are absent or only allowed under controlled circumstances. Such systems can constrain access to system resources such as files, locks, and memory by keeping track of changes of state and prohibiting invalid states. Different substructural type systems Several type systems have emerged by discarding some of the structural rules of exchange, weakening, and contraction: *''Ordered type systems'' (discard exchange, weakening and contraction): Every variable is used exactly once in the order it was introduced. *''Linear type systems'' (allow exchange, but neither weakening nor contraction): Every variable is used exactly once. *''Affine type systems'' (allow exchange and weakening, but not contraction): Every variable is used at most once. *''Relevant type systems'' (allow exchange and contraction, but not weakening): Every variable is used at least ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Relevant Logic
Relevance logic, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications to be relevantly related. They may be viewed as a family of substructural or modal logics. It is generally, but not universally, called ''relevant logic'' by British and, especially, Australian logicians, and ''relevance logic'' by American logicians. Relevance logic aims to capture aspects of implication that are ignored by the " material implication" operator in classical truth-functional logic, namely the notion of relevance between antecedent and conditional of a true implication. This idea is not new: C. I. Lewis was led to invent modal logic, and specifically strict implication, on the grounds that classical logic grants paradoxes of material implication such as the principle that a falsehood implies any proposition. Hence "if I'm a donkey, then two and two is four" is true when translated as a material implication, yet it seems intuitiv ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science (journal)
''Theoretical Computer Science'' (''TCS'') is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index. According to the Journal Citation Reports, its 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a type of journal ranking. Journals with higher impact factor values are considered more prestigious or important within their field. The Impact Factor of a journa ... is 0.827. References Computer science journals Elsevier academic journals Academic journals established in 1975 {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ludics
In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic. Key features of ludics include notion of compound connectives, using a technique known as ''focusing'' or ''focalisation'' (invented by the computer scientist Jean-Marc Andreoli), and its use of ''locations'' or ''loci'' over a base instead of propositions. More precisely, ludics tries to retrieve known logical connectives and proof behaviours by following the paradigm of interactive computation, similarly to what is done in game semantics to which it is closely related. By abstracting the notion of formulae and focusing on their concrete uses—that is distinct occurrences—it provides an abstract syntax for computer science, as loci can be seen as pointers on memory. The primary achievement of ludics is the discovery of a relationship between two natural, but distinct notions of type, or proposition. The first view, which might be termed the proof-theoretic or Gentzen-st ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Predicate Logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all humans are mortal", in first-order logic one can have expressions in the form "for all ''x'', if ''x'' is a human, then ''x'' is mortal", where "for all ''x"'' is a quantifier, ''x'' is a variable, and "... ''is a human''" and "... ''is mortal''" are predicates. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic. A theory about a topic, such as set theory, a theory for groups,A. Tarski, ''Undecidable Theories'' (1953), p. 77. Studies in Logic and the Foundation of Mathematics, North-Holland or a formal theory ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Decidability (logic)
In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them. Decidability of a logical system Each logical system comes with both a syntactic component, which among other things determines the notion of provability, and a semantic component, which determine ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Frederic Fitch
Frederic Brenton Fitch (September 9, 1908 – September 18, 1987) was an American logician, a Sterling Professor at Yale University. Education and career At Yale, Fitch earned his B.A in 1931 and his Ph.D. from Yale in 1934 under the supervision of F. S. C. Northrop. From 1934 to 1937 Fitch was a postdoc at the University of Virginia. In 1937 he returned to Yale, where he taught until his retirement in 1977. His doctoral students include Alan Ross Anderson, Ruth Barcan Marcus, and William W. Tait. Work Fitch was the inventor of the Fitch-style calculus for arranging formal logical proofs as diagrams. In his 1963 published paper "A Logical Analysis of Some Value Concepts" he proves "Theorem 5" (originally by Alonzo Church), which later became famous in context of the knowability paradox. Fitch worked primarily in combinatory logic, authoring an undergraduate-level textbook on the subject (1974), but he also made significant contributions to intuitionism and modal logic. He w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Set Theory
Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathematics – is mostly concerned with those that are relevant to mathematics as a whole. The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory. The non-formalized systems investigated during this early stage go under the name of ''naive set theory''. After the discovery of Paradoxes of set theory, paradoxes within naive set theory (such as Russell's paradox, Cantor's paradox and the Burali-Forti paradox), various axiomatic systems were proposed in the early twentieth century, of which Zermelo–Fraenkel set theory (with or without the axiom of choice) is still the best-known and most studied. Set the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Structural Rule
In the logical discipline of proof theory, a structural rule is an inference rule of a sequent calculus that does not refer to any logical connective but instead operates on the sequents directly. Structural rules often mimic the intended meta-theoretic properties of the logic. Logics that deny one or more of the structural rules are classified as substructural logics. Common structural rules Three common structural rules are: * , where the hypotheses or conclusion of a sequence may be extended with additional members. In symbolic form weakening rules can be written as \frac on the left of the turnstile, and \frac on the right. Known as monotonicity of entailment in classical logic. * , where two equal (or unifiable) members on the same side of a sequent may be replaced by a single member (or common instance). Symbolically: \frac and \frac. Also known as factoring in automated theorem proving systems using resolution. Known as idempotency of entailment in classical logic. * Exc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
