In mathematical logic, a sequent is a very general kind of conditional assertion.
A sequent may have any number m of condition formulas Ai (called "antecedents") and any number n of asserted formulas Bj (called "succedents" or "consequents"). A sequent is understood to mean that if all of the antecedent conditions are true, then at least one of the consequent formulas is true. This style of conditional assertion is almost always associated with the conceptual framework of sequent calculus.
Sequents are best understood in the context of the following three kinds of logical judgments:
Unconditional assertion. No antecedent formulas.
Example: ⊢ B
Meaning: B is true.
Conditional assertion. Any number of antecedent formulas.
Simple conditional assertion. Single consequent formula.
Example: A1, A2, A3 ⊢ B
Meaning: IF A1 AND A2 AND A3 are true, THEN B is true.
Sequent. Any number of consequent formulas.
Example: A1, A2, A3 ⊢ B1, B2, B3, B4
Meaning: IF A1 AND A2 AND A3 are true, THEN B1 OR B2 OR B3 OR B4 is true.
Thus sequents are a generalization of simple conditional assertions, which are a generalization of unconditional assertions.
The word "OR" here is the inclusive OR. The motivation for disjunctive semantics on the right side of a sequent comes from three main benefits.
The symmetry of the classical inference rules for sequents with such semantics.
The ease and simplicity of converting such classical rules to intuitionistic rules.
The ability to prove completeness for predicate calculus when it is expressed in this way.
All three of these benefits were identified in the founding paper by .
Not all authors have adhered to Gentzen's original meaning for the word "sequent". For example, used the word "sequent" strictly for simple conditional assertions with one and only one consequent formula. The same single-consequent definition for a sequent is given by .
In a general sequent of the form
both Γ and Σ are sequences of logical formulas, not sets. Therefore both the number and order of occurrences of formulas are significant.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
The course introduces the foundations on which programs and programming languages are built. It introduces syntax, types and semantics as building blocks that together define the properties of a progr
In mathematical logic, a proof calculus or a proof system is built to prove statements. A proof system includes the components: Language: The set L of formulas admitted by the system, for example, propositional logic or first-order logic. Rules of inference: List of rules that can be employed to prove theorems from axioms and theorems. Axioms: Formulas in L assumed to be valid. All theorems are derived from axioms. Usually a given proof calculus encompasses more than a single particular formal system, since many proof calculi are under-determined and can be used for radically different logics.
In mathematical logic, a judgment (or judgement) or assertion is a statement or enunciation in a metalanguage. For example, typical judgments in first-order logic would be that a string is a well-formed formula, or that a proposition is true. Similarly, a judgment may assert the occurrence of a free variable in an expression of the object language, or the provability of a proposition. In general, a judgment may be any inductively definable assertion in the metatheory.
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. In a sequent calculus, one writes each line of a proof as Here the structural rules are rules for rewriting the LHS of the sequent, denoted Γ, initially conceived of as a string (sequence) of propositions.
Functional Dependency has been extensively studied in database theory. It provides an elegant formalism for specifying key constraints and is the basis for normalization theory used in Relational database design. Given its known axiomatization through logi ...
Recent advances in biosensing technologies have led to applications of biosensor probe arrays for rapid identification of biological agents such as drugs, gene expressions, proteins, cholesterol and fats in an input sample. However, monitoring the simultan ...
Tree structures for computing orthogonal transforms are introduced. Two cases, delay trees and decimation trees, are investigated. A simple condition, namely the orthogonality of branches with a common root, is shown to be necessary and sufficient for the ...