Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Sequent calculus
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
===Sequent calculus systems=== Finally, sequent calculus generalizes the form of a natural deduction judgment to : <math>A_1, \ldots, A_n \vdash B_1, \ldots, B_k,</math> a syntactic object called a sequent. The formulas on left-hand side of the [[Turnstile (symbol)|turnstile]] are called the ''antecedent'', and the formulas on right-hand side are called the ''succedent'' or ''consequent''; together they are called ''cedents'' or ''sequents''.{{sfn|Shankar|Owre|Rushby|Stringer-Calvert|2020}} Again, <math>A_i</math> and <math>B_i</math> are formulas, and <math>n</math> and <math>k</math> are nonnegative integers, that is, the left-hand-side or the right-hand-side (or neither or both) may be empty. As in natural deduction, theorems are those <math>B</math> where <math>\vdash B</math> is the conclusion of a valid proof. The standard semantics of a sequent is an assertion that whenever ''every'' <math> A_i</math> is true, ''at least one'' <math>B_i</math> will also be true.<ref>For explanations of the disjunctive semantics for the right side of sequents, see {{harvnb|Curry|1977|pp=189–190}}, {{harvnb|Kleene|2002|pp=290, 297}}, {{harvnb|Kleene|2009|p=441}}, {{harvnb|Hilbert|Bernays|1970|p=385}}, {{harvnb|Smullyan|1995|pp=104–105}} and {{harvnb|Gentzen|1934|p=180}}.</ref> Thus the empty sequent, having both cedents empty, is false.{{sfn|Buss|1998|p=10}} One way to express this is that a comma to the left of the turnstile should be thought of as an "and", and a comma to the right of the turnstile should be thought of as an (inclusive) "or". The sequents :<math>A_1, \ldots, A_n \vdash B_1, \ldots, B_k</math> and :<math>\vdash (A_1 \land\cdots\land A_n)\rightarrow(B_1 \lor\cdots\lor B_k)</math> are equivalent in the strong sense that a proof of either sequent may be extended to a proof of the other sequent. At first sight, this extension of the judgment form may appear to be a strange complication—it is not motivated by an obvious shortcoming of natural deduction, and it is initially confusing that the comma seems to mean entirely different things on the two sides of the turnstile. However, in a [[Classical logic|classical context]] the semantics of the sequent can also (by propositional tautology) be expressed either as :: <math>\vdash \neg A_1 \lor \neg A_2 \lor \cdots \lor \neg A_n \lor B_1 \lor B_2 \lor\cdots\lor B_k</math> (at least one of the As is false, or one of the Bs is true) :or as :: <math>\vdash \neg(A_1 \land A_2 \land \cdots \land A_n \land \neg B_1 \land \neg B_2 \land\cdots\land \neg B_k)</math> (it cannot be the case that all of the As are true and all of the Bs are false). In these formulations, the only difference between formulas on either side of the turnstile is that one side is negated. Thus, swapping left for right in a sequent corresponds to negating all of the constituent formulas. This means that a symmetry such as [[De Morgan's laws]], which manifests itself as logical negation on the semantic level, translates directly into a left–right symmetry of sequents—and indeed, the inference rules in sequent calculus for dealing with conjunction (∧) are mirror images of those dealing with disjunction (∨). Many logicians feel {{Citation needed|date=November 2018}} that this symmetric presentation offers a deeper insight in the structure of the logic than other styles of proof system, where the classical duality of negation is not as apparent in the rules.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)