|
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] |
Logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure of arguments alone, independent of their topic and content. Informal logic is associated with informal fallacies, critical thinking, and argumentation theory. Informal logic examines arguments expressed in natural language whereas formal logic uses formal language. When used as a countable noun, the term "a logic" refers to a specific logical formal system that articulates a proof system. Logic plays a central role in many fields, such as philosophy, mathematics, computer science, and linguistics. Logic studies arguments, which consist of a set of premises that leads to a conclusion. An example is the argument from the premises "it's Sunday" and "if it's Sunday then I don't have to work" leading to the conclusion "I don't have to wor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Intuitionistic
In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fundamental principles claimed to exist in an objective reality. That is, logic and mathematics are not considered analytic activities wherein deep properties of objective reality are revealed and applied, but are instead considered the application of internally consistent methods used to realize more complex mental constructs, regardless of their possible independent existence in an objective reality. Truth and proof The fundamental distinguishing characteristic of intuitionism is its interpretation of what it means for a mathematical statement to be true. In Brouwer's original intuitionism, the truth of a mathematical statement is a subjective claim: a mathematical statement corresponds to a mental construction, and a mathematician ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Residuated Lattice
In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice (order), lattice ''x'' ≤ ''y'' and a monoid ''x''•''y'' which admits operations ''x''\''z'' and ''z''/''y'', loosely analogous to division or implication, when ''x''•''y'' is viewed as multiplication or conjunction, respectively. Called respectively right and left residuals, these operations coincide when the monoid is commutative. The general concept was introduced by Morgan Ward and Robert P. Dilworth in 1939. Examples, some of which existed prior to the general concept, include Boolean algebra (structure), Boolean algebras, Heyting algebras, residuated Boolean algebras, relation algebras, and MV-algebras. Residuated lattice#Residuated semilattice, Residuated semilattices omit the meet operation ∧, for example Kleene algebras and action algebras. Definition In mathematics, a residuated lattice is an algebraic structure such that : (i) (''L'', ≤) is a lattice (ord ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Substructural 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 l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Logic
Linear logic is a substructural logic proposed by French logician Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also been studied for its own sake, more broadly, ideas from linear logic have been influential in fields such as programming languages, game semantics, and quantum physics (because linear logic can be seen as the logic of quantum information theory), as well as linguistics, particularly because of its emphasis on resource-boundedness, duality, and interaction. Linear logic lends itself to many different presentations, explanations, and intuitions. Proof-theoretically, it derives from an analysis of classical sequent calculus in which uses of (the structural rules) contraction and weakening are carefully controlled. Operationally, this means that logical deduction is no longer merely about an ever-expanding collection of pe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monotonicity Of Entailment
Monotonicity of entailment is a property of many logical systems such that if a sentence follows deductively from a given set of sentences then it also follows deductively from any superset of those sentences. A corollary is that if a given argument is deductively valid, it cannot become invalid by the addition of extra premises. Logical systems with this property are called monotonic logics in order to differentiate them from non-monotonic logics. Classical logic and intuitionistic logic are examples of monotonic logics. Weakening rule Monotonicity may be stated formally as a rule called weakening, or sometimes thinning. A system is monotonic if and only if the rule is admissible. The weakening rule may be expressed as a natural deduction sequent: :\frac This can be read as saying that if, on the basis of a set of assumptions \Gamma, one can prove C, then by adding an assumption A, one can still prove C. Example The following argument is valid: "All men are mortal. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Idempotent
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors and closure operators) and functional programming (in which it is connected to the property of referential transparency). The term was introduced by American mathematician Benjamin Peirce in 1870 in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from + '' potence'' (same + power). Definition An element x of a set S equipped with a binary operator \cdot is said to be ''idempotent'' under \cdot if : . The ''binary operation'' \cdot is said to be ''idempotent'' if : . Examples * In the monoid (\mathbb, \times) of the natural numbers with multiplication, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Associative
In mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs. Within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed. That is (after rewriting the expression with parentheses and in infix notation if necessary), rearranging the parentheses in such an expression will not change its value. Consider the following equations: \begin (2 + 3) + 4 &= 2 + (3 + 4) = 9 \,\\ 2 \times (3 \times 4) &= (2 \times 3) \times 4 = 24 . \end Even though the parentheses were rearranged on each line, the values of the expressions were not altered. Since this holds true when performing addition and multiplication on any real numbers, i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a property of arithmetic, e.g. or , the property can also be used in more advanced settings. The name is needed because there are operations, such as division (mathematics), division and subtraction, that do not have it (for example, ); such operations are ''not'' commutative, and so are referred to as noncommutative operations. The idea that simple operations, such as the multiplication (mathematics), multiplication and addition of numbers, are commutative was for many centuries implicitly assumed. Thus, this property was not named until the 19th century, when new algebraic structures started to be studied. Definition A binary operation * on a Set (mathematics), set ''S'' is ''commutative'' if x * y = y * x for all x,y \in S. An operat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turnstile (symbol)
In mathematical logic and computer science the symbol ⊢ (\vdash) has taken the name turnstile because of its resemblance to a typical turnstile. It is also referred to as tee and is often read as "yields", "proves", "satisfies" or "entails". Interpretations The turnstile represents a binary relation. It has several different interpretations in different contexts: * In epistemology, Per Martin-Löf (1996) analyzes the \vdash symbol thus: "... e combination of Frege's , judgement stroke and , content stroke �� came to be called the assertion sign." Frege's notation for a judgement of some content ::\vdash A :can then be read ::''I know is true''. :In the same vein, a conditional assertion ::P \vdash Q :can be read as: ::''From , I know that '' * In metalogic, the study of formal languages; the turnstile represents syntactic consequence (or "derivability"). This is to say, that it shows that one string can be derived from another in a single step, according to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logical Conjunction
In logic, mathematics and linguistics, ''and'' (\wedge) is the Truth function, truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as \wedge or \& or K (prefix) or \times or \cdot in which \wedge is the most modern and widely used. The ''and'' of a set of operands is true if and only if ''all'' of its operands are true, i.e., A \land B is true if and only if A is true and B is true. An operand of a conjunction is a conjunct. Beyond logic, the term "conjunction" also refers to similar concepts in other fields: * In natural language, the denotation of expressions such as English language, English "Conjunction (grammar), and"; * In programming languages, the Short-circuit evaluation, short-circuit and Control flow, control structure; * In set theory, Intersection (set theory), intersection. * In Lattice (order), lattice theory, logical conjunction (Infimum and supremum, greatest lower bound). Notati ... [...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] |
