Vikipedio:Projekto matematiko/Natura konkludo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Natura konkludo
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En matematika logiko, natura konkludo estas (maniero, proksimiĝi, proksimiĝo) al pruva teorio (tiu, ke, kiu) provas al provizi formala modelo de racio kiel ĝi "(naive, krude, nature)" okazas.

Enhavo

1 Motivado
2 Juĝoj kaj (propozicioj, propozicias)
3 Enkonduko kaj elimino
4 Hipotezaj derivaĵoj
5 Konsekvenco, pleneco, kaj normalaj formoj
6 Unua kaj pli alta (mendi, ordo) (vastigaĵoj, vastigaĵas)
7 Pruvoj kaj tipo-teorio
8 Klasika kaj modalaj logikoj
9 Komparo kun alia fundamenta (manieroj, proksimiĝoj)
- 9.1 Sekva kalkulo
10 Referencoj
11 Ekstera (ligoj, ligas)

[redaktu] Motivado

Natura konkludo kreskita el ĉirkaŭteksto de _dissatisfaction_ kun _sentential_ (aksiomigoj, aksiomigas) komuna al la sistemoj de Hilberto, _Frege_, kaj Russell-a. Tia (aksiomigoj, aksiomigas) estita plej fame uzita per Russell-a kaj _Whitehead_ en ilia matematika traktato Principoj Mathematica. Spronita sur per serio de seminarioj en Pollando en 1926 per _Łukasiewicz_ (tiu, ke, kiu) advokatis pli natura kuracado de logiko, _Jaśkowski_ farita la plaj frua provas je difinanta pli natura konkludo, unua en 1929 uzanta _diagrammatic_ (notacio, skribmaniero), kaj poste ĝisdatiganta lia edziĝpropono en vico de (paperoj, paperas) en 1934 kaj 1935. Liaj edziĝproponoj farita ne pruvi al esti populara, tamen. Natura konkludo en ĝia moderna (formo, formi) estita sendepende proponita per la Germana matematikisto _Gentzen_ en 1935, en (disertacio, disertaĵo) liveris al la fakultato de matematika (sciencoj, sciencas) de la universitato de Göttingen. La (termo, membro, flanko, termino) natura konkludo (aŭ iom, ĝia Germana ekvivalento) estis monerita en (tiu, ke, kiu) papero:

_Ich_ _wollte_ _zunächst_ _einmal_ _einen_ _Formalismus_ _aufstellen_, _der_ _dem_ _wirklichen_ _Schließen_ _möglichst_ _nahe_ _kommt_. (Do, Tiel) _ergab_ _sich_ _ein_ „_Kalkül_ _des_ _natürlichen_ _Schließens_“. (Unua Mi dezirita al konstrui formalismo (tiu, ke, kiu) venas kiel fermi kiel ebla al reala (racianta, rezonanta, kaŭzanta). Tial aperita "kalkulo de natura konkludo".)

— _Gentzen_, _Untersuchungen_ _über_ _das_ _logische_ _Schließen_ (_Mathematische_ _Zeitschrift_ 39, _pp_.176-210, 1935)

_Gentzen_ estita motivigita per deziri al fondi la konsekvenco de nombroteorio, kaj li fundamenti senpera uzi por lia natura konkluda kalkulo. Li estis tamen _dissatisfied_ kun la komplekseco de liaj pruvoj, kaj en 1938 donis nova konsekvenca pruva uzanta lia sekva kalkulo. En serio de seminarioj en 1961 kaj 1962 _Prawitz_ donis multampleksa enkonduko de naturaj konkludaj kalkuloj, kaj transportis multa de _Gentzen_'s laboro kun sekvaj kalkuloj enen la natura konkluda kadro. Lia 1965 monografio Natura konkludo: pruvo-teoria studi estita al iĝi la definitiva laboro sur natura konkludo, kaj inkluzivis aplikoj por modala kaj logiko de dua ordo.

La sistemo (surscenigis, enscenigita, prezentita) en ĉi tiu artikolo estas minora variado de _Gentzen_'s aŭ _Prawitz_'s formulaĵo, sed kun pli proksima (adheraĵo, adhero) al _Martin_-_Löf_'s priskribo de logikaj juĝoj kaj (ligiloj, ligas) (_Martin_-_Löf_, 1996).

[redaktu] Juĝoj kaj (propozicioj, propozicias)

juĝo estas ia tio estas _knowable_, tio estas, objekto de scio. Ĝi estas evidenta se unu fakte (konas, scias) ĝi. Tial "ĝi estas pluvanta" estas juĝo, kiu estas evidenta por la unu kiu (konas, scias) (tiu, ke, kiu) ĝi estas reale pluvanta; en ĉi tiu (kesto, okazo) unu (majo, povas) _readily_ trovi indikaĵo por la juĝo per (aspektanta, rigardanta) ekster la fenestro aŭ (stepanta, ŝtupanta, paŝanta) el la domo. En matematika logiko tamen, indikaĵo estas ofte ne kiel rekte videbla, sed iom (deduktis, konkludita) de pli bazaj evidentaj juĝoj. La procezo de konkludo estas kio konsistigas pruvo; en alia (vortoj, vortas), juĝo estas evidenta se unu havas pruvo por ĝi.

La plej gravaj juĝoj en logiko estas de la (formo, formi) "A estas vera". La (letero, litero) A staras por (ĉiu, iu) esprimo (figuranta, prezentanta) propozicio; la veraj juĝoj tial postuli pli primitiva juĝo: "A estas propozicio". Multaj aliaj juĝoj havi estas studita; ekzemple, "A estas malvera" (vidi klasika logiko), "A estas vera je tempo t" (vidi portempa logiko), "A estas bezone vera" aŭ "A estas eble vera" (vidi modala logiko), "la programo M havas tipo τ" (vidi programlingvoj kaj tipa teorio), "A estas _achievable_ de la havebla (rimedo, rimedoj, rimedas)" (vidi lineara logiko), kaj multaj aliaj. Al starti kun, ni estos koncerni nin mem kun la plej simpla du juĝoj "A estas propozicio" kaj "A estas vera", mallongigis kiel "A apogilo" kaj "A vera" respektive.

La juĝo "A apogilo" difinas la strukturo de validaj pruvoj de A, kiu laŭvice difinas la strukturo de (propozicioj, propozicias). Por ĉi tiu kaŭzo, la konkludaj reguloj por ĉi tiu juĝo estas iam sciata kiel formaciaj reguloj. Al ilustri, se ni havi du (propozicioj, propozicias) A kaj B (tio estas, la juĝoj "A apogilo" kaj "B apogilo" estas evidenta), tiam ni (formo, formi) la kombinaĵa propozicio A kaj B, skribita signmaniere kiel " $A \wedge B$ ". Ni povas skribi ĉi tiu en la (formo, formi) de konkluda regulo:

$\frac{A\hbox{ prop} \qquad B\hbox{ prop}}{A \wedge B\hbox{ prop}}\ \wedge_F$

Ĉi tiu konkluda regulo estas _schematic_: A kaj B povas esti generita kun (ĉiu, iu) esprimo. La ĝenerala (formo, formi) de konkluda regulo estas:

$\frac{J_1 \qquad J_2 \qquad \cdots \qquad J_n}{J}\ \hbox{name}$

kie ĉiu $J i$ estas juĝo kaj la konkluda regulo estas nomita "nomo". La juĝoj pli supre la linio estas sciata kiel premisoj, kaj tiuj pli sube la linio estas (konkludoj, konkludas). Alia komuna logika (propozicioj, propozicias) estas (kajaŭo, disjunkcio) ( $A \vee B$ ), nego ( $\neg A$ ), implikacio ( $A \supset B$ ), kaj la logika konstanta vero ( $\top$ ) kaj _falsehood_ ( $\bot$ ). Iliaj formaciaj reguloj estas pli sube.

$\frac{A\hbox{ prop} \qquad B\hbox{ prop}}{A \vee B\hbox{ prop}}\ \vee_F \qquad \frac{A\hbox{ prop} \qquad B\hbox{ prop}}{A \supset B\hbox{ prop}}\ \supset_F$

$\frac{\hbox{ }}{\top\hbox{ prop}}\ \top_F \qquad \frac{\hbox{ }}{\bot\hbox{ prop}}\ \bot_F \qquad \frac{A\hbox{ prop}}{\neg A\hbox{ prop}}\ \neg_F$

[redaktu] Enkonduko kaj elimino

Nun ni (diskuti, diskuto) la "A vera" juĝo. Konkludaj reguloj (tiu, ke, kiu) prezenti logika ligilo en la konkludo estas sciata kiel enkondukaj reguloj. Al prezenti (konjunkcioj, konjunkcias, aŭoj, aŭas, kajoj, kajas), kio estas, al konkludi "A kaj B vera" por (propozicioj, propozicias) A kaj B, unu postulas indikaĵo por "A vera" kaj "B vera". Kiel konkluda regulo:

$\frac{A\hbox{ true} \qquad B\hbox{ true}}{A \wedge B\hbox{ true}}\ \wedge_I$

Ĝi devas esti komprenita (tiu, ke, kiu) en tiaj reguloj la (objektoj, objektas) estas (propozicioj, propozicias). Tio estas, la pli supre regulo estas (reale, reele) mallongigo por:

$\frac{A\hbox{ prop} \qquad B\hbox{ prop} \qquad A\hbox{ true} \qquad B\hbox{ true}}{A \wedge B\hbox{ true}}\ \wedge_I$

Ĉi tiu povas ankaŭ esti skribita:

$\frac{A \wedge B\hbox{ prop} \qquad A\hbox{ true} \qquad B\hbox{ true}}{A \wedge B\hbox{ true}}\ \wedge_I$

En ĉi tiu (formo, formi), la unua premiso povas esti kontentigita per la $\wedge_F$ formacia regulo, donanta la unua du premisoj de la antaŭa (formo, formi). En ĉi tiu artikolo ni estos apostrofi la "apogilo" juĝoj kie ili estas komprenita. En la _nullary_ (kesto, okazo), unu povas derivi vero de ne premisoj.

$\frac{\ }{\top\hbox{ true}}\ \top_I$

Se la vero de propozicio povas esti (fondita, fondis) en pli ol unidirekta, la (korespondanta, respektiva) ligilo havas multaj enkondukaj reguloj.

$\frac{A\hbox{ true}}{A \vee B\hbox{ true}}\ \vee_{I1} \qquad \frac{B\hbox{ true}}{A \vee B\hbox{ true}}\ \vee_{I2}$

(Tononomo, Noto, Noti) (tiu, ke, kiu) en la _nullary_ (kesto, okazo), kio estas, por _falsehood_, estas ne enkondukaj reguloj. Tial unu povas neniam konkludi _falsehood_ de pli simplaj juĝoj.

Duala al enkondukaj reguloj estas eliminaj reguloj al priskribi kiel al _de_-konstrui informo pri kombinaĵa propozicio enen informo pri ĝia (komponantoj, komponantas). Tial, de "A ∧ B vera", ni povas konkludi "A vera" kaj "B vera":

$\frac{A \wedge B\hbox{ true}}{A\hbox{ true}}\ \wedge_{E1} \qquad \frac{A \wedge B\hbox{ true}}{B\hbox{ true}}\ \wedge_{E2}$

Kiel ekzemplo de la uzi de konkludaj reguloj, konsideri komuteco de (konjunkcio, aŭo, kajo). Se A ∧ B estas vera, tiam B ∧ A estas vera; Ĉi tiu derivaĵo povas esti desegnita per (verkanta, komponanta) konkludaj reguloj en tia (modo, maniero) (tiu, ke, kiu) premisoj de suba konkludo (alumeto, svati, maĉo, konkurso, kongrui) la konkludo de la venonta pli alta konkludo.

$\cfrac{\cfrac{A \wedge B\hbox{ true}}{B\hbox{ true}}\ \wedge_{E2} \qquad \cfrac{A \wedge B\hbox{ true}}{A\hbox{ true}}\ \wedge_{E1}} {B \wedge A\hbox{ true}}\ \wedge_I$

La konkludo (ciferoj, ciferas, geometriaj figuroj, figuroj, figuras) ni havi vidita (do, tiel) malproksime estas ne sufiĉa al (ŝtato, stato, stati) la reguloj de implikacia enkonduko aŭ disjunkcia elimino; por ĉi tiuj, ni (bezoni, bezono, necesa) pli ĝenerala nocio de hipoteza derivaĵo.

[redaktu] Hipotezaj derivaĵoj

_Pervasive_ operacio en matematika logiko estas (racianta, rezonanta, kaŭzanta) de (premisoj, supozoj, supozas). Ekzemple, konsideri jena derivaĵo:

$\frac{A \wedge \left ( B \wedge C \right ) \ true}{\frac{B \wedge C \ true}{B \ true} \wedge E_1} \wedge E_2$

Ĉi tiu derivaĵo ne fondi la vero de B kiel tia; iom, ĝi _establishes_ jena fakto:

Se A ∧ (B ∧ C) estas vera tiam B estas vera.

En logiko, unu diras "alprenanta A ∧ (B ∧ C) estas vera, ni montri (tiu, ke, kiu) B estas vera"; en alia (vortoj, vortas), la juĝo "B vera" dependas sur la alprenis juĝo "A ∧ (B ∧ C) vera". Ĉi tiu estas hipoteza derivaĵo, kiu ni skribi kiel sekvas:

$\begin{matrix} A \wedge \left ( B \wedge C \right ) \ true \\ \vdots \\ B \ true \end{matrix}$

La interpretado estas: "B vera estas _derivable_ de A ∧ (B ∧ C) vera". Kompreneble, en ĉi tiu specifa ekzemplo ni reale scii la derivaĵo de "B vera" de "A ∧ (B ∧ C) vera", sed en ĝenerala ni (majo, povas) ne a-_priori_ scii la derivaĵo. La ĝenerala (formo, formi) de hipoteza derivaĵo estas:

$\begin{matrix} D_1 \quad D_2 \cdots D_n \\ \vdots \\ J \end{matrix}$

Ĉiu hipoteza derivaĵo havas kolekto de antaŭaĵo derivaĵoj (la D_mi) skribita sur la supra linio, kaj _succedent_ juĝo (J) skribita sur la funda linio. Ĉiu de la premisoj (majo, povas) sin esti hipoteza derivaĵo. (Por simpleco, ni (trakti, kuraci) juĝo kiel premisoSen- derivaĵo.)

La nocio de hipoteza juĝo estas _internalised_ kiel la ligilo de implikacio. La enkonduko kaj eliminaj reguloj estas kiel sekvas.

$\frac{ \begin{matrix} \frac{}{A \ true} u \\ \vdots \\ B \ true \end{matrix} }{A \supset B \ true} \supset I^u \qquad \frac{A \supset B \ true \quad A \ true}{B \ true} \supset E$

En la enkonduka regulo, la antaŭaĵo nomis u estas eksigita en la konkludo. Ĉi tiu estas mekanismo por dislimanta la (regiono, vidotereno) de la hipotezo: ĝia (plando, plandumo) kaŭzo por ekzisto estas al fondi "B vera"; ĝi ne povas esti uzita por (ĉiu, iu) alia celo, kaj en aparta, ĝi ne povas esti uzita pli sube la enkonduko. Kiel ekzemplo, konsideri la derivaĵo de "A ⊃ (B ⊃ (A ∧ B)) vera":

$\frac{\frac{{}}{A \ true} u \quad \frac{{}}{B \ true} w}{ \frac{A \wedge B \ true}{ \frac{B \supset \left ( A \wedge B \right ) \ true}{ A \supset \left ( B \supset \left ( A \wedge B \right ) \right ) \ true } \supset I^u } \supset I^w } \wedge I$

Ĉi tiu plena derivaĵo havas ne _unsatisfied_ premisoj; tamen, sub-derivaĵoj estas hipoteza. Ekzemple, la derivaĵo de "B ⊃ (A ∧ B) vera" estas hipoteza kun antaŭaĵo "A vera" (nomis u).

Kun hipotezaj derivaĵoj, ni povas nun skribi la elimina regulo por (kajaŭo, disjunkcio):

$\frac{ A \vee B \hbox{ true} \quad \begin{matrix} \frac{}{A \ true} u \\ \vdots \\ C \ true \end{matrix} \quad \begin{matrix} \frac{}{B \ true} w \\ \vdots \\ C \ true \end{matrix} }{C \ true} \vee E^{u,w}$

En (vortoj, vortas), se A ∨ B estas vera, kaj ni povas derivi C vera ambaŭ de A vera kaj de B vera, tiam C estas ja vera. (Tononomo, Noto, Noti) (tiu, ke, kiu) ĉi tiu regulo ne _commit_ al ĉu A vera aŭ B vera. En la nulo-_ary_ (kesto, okazo), kio estas por _falsehood_, ni ricevi jena elimina regulo:

$\frac{\perp true}{C \ true} \perp E$

Ĉi tiu estas legi kiel: se _falsehood_ estas vera, tiam (ĉiu, iu) propozicio C estas vera.

Nego estas simila al implikacio.

$\frac{ \begin{matrix} \frac{}{A \ true} u \\ \vdots \\ p \ true \end{matrix} }{\lnot A \ true} \lnot I^{u,p} \qquad \frac{\lnot A \ true \quad A \ true}{C \ true} \lnot E$

La enkonduka regulo eksigas ambaŭ la nomo de la hipotezo u, kaj la _succedent_ p, kio estas, la propozicio p devas ne okazi en la konkludo ¬ A. Ekde ĉi tiuj reguloj estas _schematic_, la interpretado de la enkonduka regulo estas: se de "A vera" ni povas derivi por ĉiu propozicio p (tiu, ke, kiu) "p vera", tiam A devas esti malvera, kio estas, "¬ A vera". Por la elimino, se ambaŭ A kaj ¬ A estas montrita al esti vera, tiam estas kontraŭdiro, en kiu (kesto, okazo) ĉiu propozicio C estas vera. Ĉar la reguloj por implikacio kaj nego estas (do, tiel) simila, ĝi devus esti honeste facila al vidi (tiu, ke, kiu) ¬ A kaj A ⊃ ⊥ estas ekvivalento, kio estas, ĉiu estas _derivable_ de la alia.

[redaktu] Konsekvenco, pleneco, kaj normalaj formoj

Teorio estas dirita al esti konsekvenca se _falsehood_ estas ne demonstrebla (de ne (premisoj, supozoj, supozas)) kaj estas plenumi se ĉiu teoremo estas demonstrebla uzanta la konkludaj reguloj de la logiko. Ĉi tiuj estas (propozicioj, frazoj, ordonoj) pri la tuta logiko, kaj estas kutime (kravatita, ligita) al iu nocio de modelo. Tamen, estas loka (komprenaĵoj, nocioj, nocias) de konsekvenco kaj pleneco (tiu, ke, kiu) estas pure sintaksaj kontroloj sur la konkludaj reguloj, kaj postuli ne apelacias al (modeloj, modelas). La unua de ĉi tiuj estas loka konsekvenco, ankaŭ sciata kiel loka _reducibility_, kiu diras (tiu, ke, kiu) (ĉiu, iu) derivaĵa enhavanta enkonduko de ligilo sekvis (tuj, senpere) per ĝia elimino povas esti (turnita, turnis) enen ekvivalenta derivaĵo sen ĉi tiu _detour_. Ĝi estas kontroli sur la forteco de eliminaj reguloj: ili devas ne esti (do, tiel) forta (tiu, ke, kiu) ili inkluzivi scio ne jam enhavis en ĝiaj premisoj. Kiel ekzemplo, konsideri (konjunkcioj, konjunkcias, aŭoj, aŭas, kajoj, kajas).

<(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Duale, loka pleneco diras (tiu, ke, kiu) la eliminaj reguloj estas forta sufiĉa al malkomponi ligilo enen la (formoj, formas) taŭgi por ĝia enkonduka regulo. Denove por (konjunkcioj, konjunkcias, aŭoj, aŭas, kajoj, kajas): <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Ĉi tiuj (komprenaĵoj, nocioj, nocias) korespondi akurate al β-malpligrandiĝo kaj η-elvolvaĵo en la lambda kalkulo, uzanta la Kareo-_Howard_ izomorfio. Per loka pleneco, ni vidi (tiu, ke, kiu) ĉiu derivaĵo povas esti konvertita al ekvivalenta derivaĵo kie la ĉefa ligilo estas prezentita. Fakte, se la tuta derivaĵo obeas ĉi tiu (ordenanta, mendanta, ordanta, dimensianta, komandanta, ordigo) de (eliminoj, eliminas) sekvita per (enkondukoj, enkondukas), tiam ĝi estas dirita al esti normala. En normala derivaĵo ĉiuj (eliminoj, eliminas) okazi pli supre (enkondukoj, enkondukas). En plej (logikoj, logikas), ĉiu derivaĵo havas ekvivalenta normala derivaĵo, (nomita, vokis) normala formo. La ekzisto de normalaj formoj estas ĝenerale peza al pruvi uzanta natura konkludo sola, kvankam tia (kontoj, kalkuloj, kontas, kalkulas) fari ekzisti en la literaturo, plej rimarkinde per _Dag_ _Prawitz_ en 1961; vidi lia libro Natura konkludo: pruvo-teoria studi, A&W Stokholmo 1965, ne ISBN. Ĝi estas multa pli simpla al montri ĉi tiu malrekte per tranĉi-libera sekva kalkulo (surscenigo, prezento).

[redaktu] Unua kaj pli alta (mendi, ordo) (vastigaĵoj, vastigaĵas)

Enkonduko de unua-(mendi, ordo) sistemo

La logiko de la pli frua sekcio estas ekzemplo de sola-(specis, ordigita) logiko, kio estas, logiko kun sola speco de objekto: (propozicioj, propozicias). Multaj (vastigaĵoj, vastigaĵas) de ĉi tiu simpla kadro havi estas proponita; en ĉi tiu sekcio ni estos etendi ĝi kun (sekundo, dua) (speco, ordigo) de (individuoj, individuas) aŭ (termoj, kondiĉoj, terminoj, termas, terminas). Pli detale, ni estos adicii nova speco de juĝo, "t estas (termo, membro, flanko, termino)" (aŭ "t (termo, membro, flanko, termino)") kie t estas _schematic_. Ni estos (fiksi, neŝanĝebligi) numerebla aro V de (variabloj, variablas), alia numerebla aro F de funkcio (simboloj, simbolas), kaj konstrui (termoj, kondiĉoj, terminoj, termas, terminas) kiel sekvas:

<(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Por (propozicioj, propozicias), ni konsideri tria numerebla aro Pde (predikatoj, predikatas), kaj difini atoma (predikatoj, predikatas) super (termoj, kondiĉoj, terminoj, termas, terminas)kun jena formacia regulo: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Aldone, ni adicii paro de kvantigis(propozicioj, propozicias): universala (∀) kaj ekzisteco (∃): <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Ĉi tiuj kvantigis (propozicioj, propozicias) havi jena enkonduko kaj eliminaj reguloj. <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> En ĉi tiuj reguloj, la (notacio, skribmaniero) [t/x] Astaras por la anstataŭo de tpor ĉiu (videbla) aper(aĵ)o de xen A, evitanta (enkapti, kapto); vidi la artikolo sur lambda kalkulo por pli detalo pri ĉi tiu norma operacio. Kiel antaŭ la supraj indicoj sur la nomo stari por la (komponantoj, komponantas) (tiu, ke, kiu) estas eksigita: la (termo, membro, flanko, termino) ane povas okazi en la konkludo de ∀Mi (tia (termoj, kondiĉoj, terminoj, termas, terminas) estas sciata kiel _eigenvariables_aŭ (parametroj, parametras)), kaj la hipotezoj nomis ukaj ven ∃E estas _localised_ al la (sekundo, dua) premiso en hipoteza derivaĵo. Kvankam la propona logiko de pli fruaj sekcioj estis decidebla, adicianta la (kvantoroj, kvantumiloj, kvantumas) (konstruas, faras) la logiko nedecidebla. (Do, Tiel) malproksime la kvantigis (vastigaĵoj, vastigaĵas) estas unua-(mendi, ordo): ili (distingi, diferencigi) (propozicioj, propozicias) de la (specoj, specas) de (objektoj, objektas) kvantigita super. pli alta (mendi, ordo) logiko prenas malsama (maniero, proksimiĝi, proksimiĝo) kaj havas nur sola (speco, ordigo) de (propozicioj, propozicias). La (kvantoroj, kvantumiloj, kvantumas) havi kiel la domajno de kvantoro la tre sama (speco, ordigo) de (propozicioj, propozicias), kiel reflektis en la formaciaj reguloj: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Diskuto de la enkonduko kaj elimino (formoj, formas) por pli alta (mendi, ordo) logiko estas preter la (regiono, vidotereno) de ĉi tiu artikolo. Ĝi estas ebla al furori inter unua (mendi, ordo) kaj pli alta (mendi, ordo) (logikoj, logikas). Ekzemple, (sekundo, dua) (mendi, ordo) logiko havas du (specoj, specas) de (propozicioj, propozicias), unu speco kvantiganta super (termoj, kondiĉoj, terminoj, termas, terminas), kaj la (sekundo, dua) speco kvantiganta super (propozicioj, propozicias) de la unua speco.

[redaktu] Pruvoj kaj tipo-teorio

La (surscenigo, prezento) de natura konkludo (do, tiel) malproksime havas (koncentrita, koncentriĝita) sur la naturo de (propozicioj, propozicias) sen donanta formala difino de pruvo. Al _formalise_ la nocio de pruvo, ni aliigi la (surscenigo, prezento) de hipotezaj derivaĵoj malmulte. Ni marko la (antaŭaĵoj, antaŭaĵas) kun pruvo (variabloj, variablas) (de iu numerebla aro V de (variabloj, variablas)), kaj dekori la _succedent_ kun la reala pruvo. La (antaŭaĵoj, antaŭaĵas) aŭ hipotezoj estas apartigita de la _succedent_ per _turnstile_ (⊢). Ĉi tiu ŝanĝo iam iras sub la nomo de _localised_ hipotezoj. Jena figuro resumas la ŝanĝi.

<(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> La kolekto de hipotezoj estos esti skribita kiel Γ kiam ilia akurata komponaĵo estas ne taŭga. Al fari pruvoj eksplicita, ni movi de la pruvoSen- juĝo "A vera" al juĝo: "π estas pruvo de (A vera)", kiu estas skribita signmaniere kiel "π : A vera". Sekva la normo (maniero, proksimiĝi, proksimiĝo), pruvoj estas precizigita kun ilia posedi formaciaj reguloj por la juĝo "π pruvo". La plej simpla ebla pruvo estas la uzi de (etikedita, markita, markita) hipotezo; en ĉi tiu (kesto, okazo) la indikaĵo estas la marka sin. <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Por koncizeco, ni estos lasi for la _judgemental_ marko veraen la cetera ĉi tiu artikolo, kio estas, skribi "Γ ⊢ π : A". Estu ni rao-ekzameni iu de la (ligiloj, ligas) kun eksplicitaj pruvoj. Por (konjunkcio, aŭo, kajo), ni rigardi la enkonduka regulo ∧Mi al (malkovri, esplori) la (formo, formi) de pruvoj de (konjunkcio, aŭo, kajo): ili devas esti paro de pruvoj de la du _conjuncts_. Tial: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> La eliminaj reguloj ∧E₁kaj ∧E₂(apartigi, elekti) ĉu la (maldekstre, restis) aŭ la (ĝusta, dekstra, rajto) _conjunct_; tial la pruvoj estas paro de projekcioj — unua (_fst_) kaj (sekundo, dua) (_snd_). <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Por implikacio, la enkonduko (formo, formi) _localises_ aŭ bindasla hipotezo, skribita uzanta λ; ĉi tiu korespondas al la eksigis marko. En la regulo, "Γ, u:A" staras por la kolekto de hipotezoj Γ, kaj ankaŭ la aldona hipotezo u. <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Kun pruvoj havebla eksplicite, unu povas manipuli kaj rezoni pri pruvoj. La ŝlosila operacio sur pruvoj estas la anstataŭo de unu pruvo por (premiso, supozo) uzita en alia pruvo. Ĉi tiu estas kutime sciata kiel anstataŭa teoremo, kaj povas esti (pruvita, pruvis) per indukto sur la profundaĵo (aŭ strukturo) de la (sekundo, dua) juĝo.

Anstataŭa teoremo: Se Γ ⊢ π₁ : A kaj Γ, u:A ⊢ π₂ : B, tiam Γ ⊢ [π₁/u] π₂ : B.

(Do, Tiel) malproksime la juĝo "Γ ⊢ π : A" havas havita pure logika interpretado. En tipa teorio, la logika vido estas interŝanĝita por pli komputa vido de (objektoj, objektas). (Propozicioj, Propozicias) en la logika interpretado estas nun vidita kiel (klavas, tipoj), kaj pruvoj kiel programoj en la lambda kalkulo. Tial la interpretado de "π : A" estas "la programoπ havas tipo A". La logikaj ligiloj estas ankaŭ donita malsama leganta: (konjunkcio, aŭo, kajo) estas vidita kiel (produkto, produto) (×), implikacio kiel la funkcia sago (→), kaj tiel plu La diferencoj estas nur (kosmetiko, ŝminko), tamen. Tipa teorio havas natura konkludo (surscenigo, prezento) en (termoj, kondiĉoj, terminoj, termas, terminas) de formacio, enkonduko kaj eliminaj reguloj; fakte, la legilo povas facile rekonstrui kio estas sciata kiel simpla tipa teoriode la antaŭaj sekcioj. La diferenco inter logiko kaj tipa teorio estas unuavice (ŝovi, ŝovo) de fokuso de la (klavas, tipoj) ((propozicioj, propozicias)) al la programoj (pruvoj). Tipa teorio estas ĉefe (interezita, interesita) en la _convertibility_ aŭ _reducibility_ de programoj. Por ĉiu tipo, estas kanonaj programoj de (tiu, ke, kiu) tipo kiu estas nereduktebla; ĉi tiuj estas sciata kiel kanonaj formojaŭ (valoroj, valoras). Se ĉiu programo povas reduktiĝi al kanona formo, tiam la tipa teorio estas dirita al esti _normalising_(aŭ (lame, malforte) _normalising_). Se la kanona formo estas unika, tiam la teorio estas dirita al esti forte _normalising_. _Normalisability_ estas malofta esprimilo de plej ne-bagatelaj tipaj teorioj, kiu estas granda (foriro, forveturo) de la logika mondo. (Memori (tiu, ke, kiu) ĉiu logika derivaĵo havas ekvivalenta normala derivaĵo.) Al skizi la kaŭzo: en tipaj teorioj (tiu, ke, kiu) konsenti rekursiaj difinoj, ĝi estas ebla al skribi programoj (tiu, ke, kiu) neniam redukti al valoro; tia (buklanta, ciklanta) programoj povas ĝenerale esti donita (ĉiu, iu) tipo. En aparta, la (buklanta, ciklanta) programo havas tipo ⊥, kvankam estas ne logika pruvo de "⊥ vera". Por ĉi tiu kaŭzo, la (propozicioj, propozicias) kiel (klavas, tipoj); pruvoj kiel programojscienca paradigmo nur (laboroj, laboras) en unu direkto, se ajn: (interpretado, interpretanta) tipa teorio kiel logiko ĝenerale donas nekonsekvenca logiko. Ŝati logiko, tipa teorio havas multaj (vastigaĵoj, vastigaĵas) kaj (rikordaj kazoj, variantoj, variantas), inkluzivanta unua (mendi, ordo) kaj pli alta (mendi, ordo) (versioj, versias). (Interezanta, Interesanta) branĉo de tipa teorio, sciata kiel dependa tipa teorio, permesas (kvantoroj, kvantumiloj, kvantumas) al limigo super programa sin. Ĉi tiuj kvantigis (klavas, tipoj) estas skribita kiel Π kaj Σ anstataŭ ∀ kaj ∃, kaj havi jenaj formaciaj reguloj: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Ĉi tiuj (klavas, tipoj) estas (ĝeneraligoj, ĝeneraligas) de la sago kaj (produkto, produto) (klavas, tipoj), respektive, kiel atestantis per ilia enkonduko kaj eliminaj reguloj. <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Dependa tipa teorio en plena universaleco estas tre pova: ĝi estas pova (ekspreso, esprimi) preskaŭ (ĉiu, iu) konjektebla propraĵo de programoj rekte en la (klavas, tipoj) de la programo. Ĉi tiu universaleco venas je (krutaĵo, kruta) prezo — kontrolanta (tiu, ke, kiu) donita programo estas de donita tipo estas nedecidebla. Por ĉi tiu kaŭzo, dependaj tipaj teorioj en praktiko ne permesi kvantoro super ajnaj programoj, sed iom limigi al programoj de donita decidebla indeksa domajno, ekzemple (entjeroj, entjeras), (surfadenigas, kordoj, kordas, ĉenoj, ĉenas, linioj, linias), aŭ linearaj programoj. Ekde dependaj tipaj teorioj permesi (klavas, tipoj) al dependi sur programoj, natura demando al (demandi, peti) estas ĉu ĝi estas ebla por programoj al dependi sur (klavas, tipoj), aŭ (ĉiu, iu) alia kombinaĵo. Estas multaj (specoj, specas) de (respondoj, respondas) al tia (demandoj, demandas). Populara (maniero, proksimiĝi, proksimiĝo) en tipa teorio estas al permesi programoj al esti kvantigita super (klavas, tipoj), ankaŭ sciata kiel parametra homonimigo (de operacisimboloj); de ĉi tiu estas du ĉefa (specoj, specas): se (klavas, tipoj) kaj programoj estas konservita apartigi, tiam unu ricevas io pli bone-kondutita sistemo (nomita, vokis) _predicative_ homonimigo (de operacisimboloj); se la distingo inter programo kaj tipo estas malklariĝita, unu ricevas la tipo-teoria analoga de logiko de pli alta ordo, ankaŭ sciata kiel _impredicative_ homonimigo (de operacisimboloj). Diversaj (kombinaĵoj, kombinaĵas) de dependo kaj homonimigo (de operacisimboloj) havi estas (konsiderita, konsideris) en la literaturo, la plej fama estante la lambda kubo de _Henk_ _Barendregt_. La komunaĵo de logiko kaj tipa teorio estas vasta kaj aktiva esplori areo. Nova (logikoj, logikas) estas kutime _formalised_ en ĝenerala tipa teoria opcio, sciata kiel logika kadro. Populara moderna logika (kadroj, kadras) kiel la kalkulo de konstruoj kaj _LF_ estas bazita sur pli alta-(mendi, ordo) dependa tipa teorio, kun diversa komerco-_offs_ en (termoj, kondiĉoj, terminoj, termas, terminas) de decideblo kaj esprima povo. Ĉi tiuj logika (kadroj, kadras) estas sin ĉiam precizigis kiel naturaj konkludaj sistemoj, kiu estas testamento al la _versatility_ de la natura konkludo (maniero, proksimiĝi, proksimiĝo).

[redaktu] Klasika kaj modalaj logikoj

Por simpleco, la (logikoj, logikas) (surscenigita, enscenigita, prezentita) (do, tiel) malproksime havi estas instituteca. Klasika logiko etendas instituteca logiko kun aldona aksiomo aŭ principo de ekskludis mezo:

Por (ĉiu, iu) propozicio p, la propozicio p ∨ ¬ p estas vera.

Ĉi tiu (propozicio, frazo, ordono) estas ne evidente ĉu enkonduko aŭ elimino; ja, ĝi engaĝas du klara (ligiloj, ligas). _Gentzen_'s originala kuracado de ekskludis mezo preskribis unu de jeno tri (ekvivalento) (formulaĵoj, formulaĵas), kiu estis jam (prezenti, aktuala) en analoga (formoj, formas) en la sistemoj de Hilberto kaj _Heyting_:

<(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> (_XM_₃estas nure _XM_₂esprimita en (termoj, kondiĉoj, terminoj, termas, terminas) de ¬E.) Ĉi tiu kuracado de ekskludis mezo, aldone al estante malaprobinda de _purist_'s starpunkto, prezentas aldonaj komplikaĵoj en la difino de normalaj formoj. Kompare pli kontentiga kuracado de klasika natura konkludo en (termoj, kondiĉoj, terminoj, termas, terminas) de enkonduko kaj eliminaj reguloj sola estis unua proponis per _Parigot_ en 1992 en la (formo, formi) de klasika lambda kalkulo (nomita, vokis) _λμ_. La ŝlosilo _insight_ de lia (maniero, proksimiĝi, proksimiĝo) estis al anstataŭigi vero-_centric_ juĝo A verakun pli klasika nocio: en _localised_ (formo, formi), anstataŭ Γ ⊢ A, li uzita Γ ⊢ Δ, kun Δ kolekto de (propozicioj, propozicias) simila al Γ. Γ estis (traktita, kuracita) kiel (konjunkcio, aŭo, kajo), kaj Δ kiel (kajaŭo, disjunkcio). Ĉi tiu strukturo estas esence (levita, liftita) rekte de klasikaj sekvaj kalkuloj, sed la _innovation_ en _λμ_ estis al doni komputa signifo al klasikaj naturaj konkludaj pruvoj en (termoj, kondiĉoj, terminoj, termas, terminas) de _callcc_ aŭ (ĵeti, ĵeto)/kapti mekanismo vidita en _LISP_ kaj ĝiaj posteuloj. (Vidi ankaŭ: unua klaso regi.) Alia grava vastigaĵo estis por modala kaj alia (logikoj, logikas) (tiu, ke, kiu) (bezoni, bezono, necesa) pli ol (justa, ĵus) la baza juĝo de vero. Ĉi tiuj estis unua priskribis en natura konkluda stilo per _Prawitz_ en 1965, kaj havi ekde akumulita granda korpo de rilatanta laboro. Al doni simpla ekzemplo, la modala logiko de neceseco postulas unu nova juĝo, "A valida", tio estas kategoria kun respekto al vero:

Se "A vera" sub ne (premisoj, supozoj, supozas) de la (formo, formi) "B vera", tiam "A valida".

Ĉi tiu kategoria juĝo estas _internalised_ kiel unuloka ligilo ◻A(legi "bezone A") kun jena enkonduko kaj eliminaj reguloj: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> (Tononomo, Noto, Noti) (tiu, ke, kiu) la premiso "A valida" havas ne difinantaj reguloj; anstataŭe, la kategoria difino de vereco estas uzita en ĝia loko. Ĉi tiu reĝimo iĝas pli klara en la _localised_ (formo, formi) kiam la hipotezoj estas eksplicita. Ni skribi "Ω;Γ ⊢ A vera" kie Γ enhavas la veraj hipotezoj kiel antaŭ, kaj Ω enhavas validaj hipotezoj. Dekstre estas (justa, ĵus) sola juĝo "A vera"; vereco estas ne (bezonata, bezonis) ĉi tie ekde "Ω ⊢ A valida" estas per difino la sama kiel "Ω;⋅ ⊢ A vera". La enkonduko kaj elimino (formoj, formas) estas tiam: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> La modalaj hipotezoj havi ilia posedi versio de la hipoteza regulo kaj anstataŭa teoremo. <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)>

Modala anstataŭa teoremo: Se Ω;⋅ ⊢ π₁ : A vera kaj Ω, u: (A valida) ; Γ ⊢ π₂ : C vera, tiam Ω;Γ ⊢ [π₁/u] π₂ : C vera.

Ĉi tiu kadro de apartigantaj juĝoj enen klara (kolektoj, kolektas) de hipotezoj, ankaŭ sciata kiel _multi_-zonitaaŭ _polyadic_ĉirkaŭtekstoj, estas tre pova kaj _extensible_; ĝi havas estas aplikita por multaj malsamaj modalaj logikoj [5], kaj ankaŭ por lineara [6] kaj aliaj substrukturaj logikoj, al doni kelkaj (ekzemploj, ekzemplas).

[redaktu] Komparo kun alia fundamenta (manieroj, proksimiĝoj)

[redaktu] Sekva kalkulo

Ĉefa artikolo: sekva kalkulo

La sekva kalkulo estas la ĉefa alternativo al natura konkludo kiel (fundamento, subkonstruaĵo) de matematika logiko. En natura konkludo la (flui, fluo) de informo estas dudirekta: eliminaj reguloj (flui, fluo) informo suben per _deconstruction_, kaj enkondukaj reguloj (flui, fluo) informo supren per asembleo. Tial, natura konkluda pruvo ne havi pure fundo-supren aŭ supro-suben leganta, farante ĝi _unsuitable_ por aŭtomacio en pruvo (serĉi, serĉo), aŭ (eĉ, ebena, para) por pruvo kontrolanta (aŭ tipo-kontrolanta en tipa teorio). Al adreso ĉi tiu fakto, _Gentzen_ en 1935 proponis lia sekva kalkulo, kvankam li (komence, fonte) intencis ĝi kiel teknika aparato por klariganta la konsekvenco de predikata logiko. Kleene-a, en lia _seminal_ 1952 libro Enkonduko al Metamatematiko (ISBN 0720421039), donis la unua formulaĵo de la sekva kalkulo en la moderna stilo.

En la sekvaj kalkulaj ĉiuj konkludaj reguloj havi pure fundo-supren leganta. Konkludaj reguloj povas turni sin al eroj sur ambaŭ flankoj de la _turnstile_. (Al (diferenciali, derivi) de natura konkludo, ĉi tiu artikolo uzas duopa sago ⇒ anstataŭ la (ĝusta, dekstra, rajto) kudri ⊢ por _sequents_.) La enkondukaj reguloj de natura konkludo estas vidita kiel (ĝusta, dekstra, rajto) reguloj en la sekva kalkulo, kaj estas strukture tre simila. La eliminaj reguloj aliflanke turni enen (maldekstre, restis) reguloj en la sekva kalkulo. Al doni ekzemplo, konsideri (kajaŭo, disjunkcio); la (ĝusta, dekstra, rajto) reguloj estas familiara:

<(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Maldekstre: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> Memori la ∨E regulo de natura konkludo en _localised_ (formo, formi): <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> La propozicio A ∨ B, kiu estas la _succedent_ de premiso en ∨E, (kurbiĝoj, kurbiĝas, turnas, tornas, kurbigas) enen hipotezo de la konkludo en la (maldekstre, restis) regulo ∨L. Tial, (maldekstre, restis) reguloj povas vidiĝi kiel (speco, ordigo) de inversigis elimina regulo. Ĉi tiu observado povas esti ilustrita kiel sekvas: <(baremo, tabelo, tablo) align="center"> <(th, -a)>natura konkludo</(th, -a)><(th, -a)>sekva kalkulo</(th, -a)></(baremo, tabelo, tablo)> En la sekva kalkulo, la (maldekstre, restis) kaj (ĝusta, dekstra, rajto) reguloj estas (aperita, plenumita) en (kluzo, seruro, ŝlosi)-(ŝtupo, paŝi) ĝis unu atingopovoj la komenca sekva, kiu korespondas al la (konferenco, veriganta) punkto de elimino kaj enkondukaj reguloj en natura konkludo. Ĉi tiuj komencaj reguloj estas malprofunde simila al la hipoteza regulo de natura konkludo, sed en la sekvaj kalkulaj ili priskribi transponoaŭ manpremode (maldekstre, restis) kaj (ĝusta, dekstra, rajto) propozicio: <(baremo, tabelo, tablo) style="margin-left: 2em;"></(baremo, tabelo, tablo)> La rilato inter la sekva kalkulo kaj natura konkludo estas paro de soneco kaj pleneco (teoremoj, teoremas), kiu estas ambaŭ demonstrebla per indukta argumento.

Soneco de ⇒ _wrt_. ⊢: Se Γ ⇒ A, tiam Γ ⊢ A.
Pleneco de ⇒ _wrt_. ⊢: Se Γ ⊢ A, tiam Γ ⇒ A.

Ĝi estas klara per ĉi tiuj (teoremoj, teoremas) (tiu, ke, kiu) la sekva kalkulo ne ŝanĝi la nocio de vero, ĉar la sama kolekto de (propozicioj, propozicias) resti vera. Tial, unu povas uzi la sama pruvo (objektoj, objektas) kiel antaŭ en sekvaj kalkulaj derivaĵoj. Kiel ekzemplo, konsideri la (konjunkcioj, konjunkcias, aŭoj, aŭas, kajoj, kajas). La (ĝusta, dekstra, rajto) regulo estas virtuale identa al la enkonduka regulo <(baremo, tabelo, tablo) style="margin-left: 2em;"> <(th, -a)>sekva kalkulo</(th, -a)><(th, -a)>natura konkludo</(th, -a)></(baremo, tabelo, tablo)> La (maldekstre, restis) regulo, tamen, plenumas iu aldona (anstataŭoj, anstataŭas) (tiu, ke, kiu) estas ne (aperita, plenumita) en la (korespondanta, respektiva) eliminaj reguloj. <(baremo, tabelo, tablo) style="margin-left: 2em;"> <(th, -a)>sekva kalkulo</(th, -a)><(th, -a)>natura konkludo</(th, -a)></(baremo, tabelo, tablo)> La (specoj, specas) de pruvoj generita en la sekva kalkulo estas pro tio iom malsama de tiuj de natura konkludo. La sekva kalkulo produktas pruvoj en kio estas sciata kiel la β-normala η-longa(formo, formi), kiu korespondas al kanona prezento de la normala formo de la natura konkluda pruvo. Se unu provas al priskribi ĉi tiu pruva uzanta natura konkluda sin, unu ricevas kio estas (nomita, vokis) la _intercalation_ kalkulo(unua priskribis per Johano _Byrnes_ [3]), kiu povas kutimi formale difini la nocio de normala formopor natura konkludo. La anstataŭa teoremo de natura konkludo prenas la (formo, formi) de struktura regulo aŭ struktura teoremo sciata kiel tranĉien la sekva kalkulo.

Tranĉi (anstataŭo): Se Γ ⇒ π₁ : A kaj Γ, u:A ⇒ π₂ : C, tiam Γ ⇒ [π₁/u] π₂ : C.

En plej bone kondutis (logikoj, logikas), tranĉi estas senbezona kiel konkluda regulo, kvankam ĝi restas demonstrebla kiel _meta_-teoremo; la _superfluousness_ de la tranĉi regulo estas kutime (surscenigita, enscenigita, prezentita) kiel komputa procezo, sciata kiel tranĉi elimino. Ĉi tiu havas (interezanta, interesanta) apliko por natura konkludo; kutime ĝi estas ege teda al pruvi certaj propraĵoj rekte en natura konkludo pro nebarita nombro de (okazoj, skatoloj, kestoj, kestas, okazas). Ekzemple, konsideri montranta (tiu, ke, kiu) donita propozicio estas nedemonstrebla en natura konkludo. Simpla indukta argumento mankas pro reguloj ŝati ∨E aŭ ¬E kiu povas prezenti ajna (propozicioj, propozicias). Tamen, ni scii (tiu, ke, kiu) la sekva kalkulo estas plenumi kun respekto al natura konkludo, (do, tiel) ĝi estas sufiĉa al montri ĉi tiu _unprovability_ en la sekva kalkulo. Nun, se tranĉi estas ne havebla kiel konkluda regulo, tiam ĉiuj sekvaj reguloj ĉu prezenti ligilo dekstre aŭ la (maldekstre, restis), (do, tiel) la profundaĵo de sekva derivaĵo estas plene barita per la (ligiloj, ligas) en la fina konkludo. Tial, montranta _unprovability_ estas multa pli simpla, ĉar estas nur finia nombro de (okazoj, skatoloj, kestoj, kestas, okazas) al konsideri, kaj ĉiu (kesto, okazo) estas (verkita, komponita) tute de sub-(propozicioj, propozicias) de la konkludo. Simpla aper(aĵ)o de ĉi tiu estas la malloka konsekvencoteoremo: "⋅ ⊢ ⊥ vera" estas ne demonstrebla. En la sekva kalkula versio, ĉi tiu estas evidente vera ĉar estas ne regulo (tiu, ke, kiu) povas havi "⋅ ⇒ ⊥" kiel konkludo! Pruvo (teoriistoj, teoriistas) ofte preferi al laboro sur tranĉi-libera sekva kalkulo (formulaĵoj, formulaĵas) pro tiaj propraĵoj.

[redaktu] Referencoj

Prelego (tononomoj, notoj, notas) al mallonga kurso je _Università_ _degli_ _Studi_ _di_ Sieno, Aprilo 1983.

[redaktu] Ekstera (ligoj, ligas)

Enkonduko al natura konkludo
Domeno Sur Acido. Natura konkludo bildigis kiel ludo de domeno (ludo).

------ u ------w Vera B vera ------------------ ∧Mi ∧ B vera ---------- ∧E₁ Vera	⇒	------ u Vera
---------- u ∧ B vera	⇒	---------- u ---------- u ∧ B vera A ∧ B vera ---------- ∧E₁ ---------- ∧E₂ Vera B vera ----------------------- ∧Mi ∧ B vera
v ∈ V ------ _var_-F v (termo, membro, flanko, termino)		f ∈ F t₁ (termo, membro, flanko, termino) t₂ (termo, membro, flanko, termino) ... t_n (termo, membro, flanko, termino) ------------------------------------------ _app_-F f (t₁, t₂, ..., t_n) (termo, membro, flanko, termino)
φ ∈ P t₁ (termo, membro, flanko, termino) t₂ (termo, membro, flanko, termino) ... t_n (termo, membro, flanko, termino) ------------------------------------------ antaŭanto-F φ (t₁, t₂, ..., t_n) apogilo
------ u x (termo, membro, flanko, termino) ⋮ Apogilo ---------- ∀F^{^u} ∀x. Apogilo		------ u x (termo, membro, flanko, termino) ⋮ Apogilo ---------- ∃F^{^u} ∃x. Apogilo
------ u (termo, membro, flanko, termino) ⋮ [a/x] A vera ------------ ∀Mi^{^{u, a}} ∀x. Vera		∀x. Vera t (termo, membro, flanko, termino) -------------------- ∀E [t/x] A vera
[t/x] A vera ------------ ∃Mi ∃x. Vera		------ u ------------ v (termo, membro, flanko, termino) [a/x] A vera ⋮ ∃x. Vera C vera -------------------------- ∃E^{^{a, u,v}} C vera
------ u p apogilo ⋮ Apogilo ---------- ∀F^{^u} ∀p. Apogilo		------ u p apogilo ⋮ Apogilo ---------- ∃F^{^u} ∃p. Apogilo
---- u₁ ---- u₂ ... ---- u_n J₁ J₂ J_n ⋮ J	⇒	u₁:J₁, u₂:J₂, ..., u_n:J_n ⊢ J
u ∈ V ------- pruvo-F u pruvo		--------------------- _hyp_ u:A vera ⊢ u : A vera
π₁ pruvo π₂ pruvo -------------------- paro-F (π₁, π₂) pruvo		Γ ⊢ π₁ : A Γ ⊢ π₂ : B ------------------------ ∧Mi Γ ⊢ (π₁, π₂) : A ∧ B
π pruvo ----------- _fst_-F _fst_ π pruvo		Γ ⊢ π : A ∧ B ------------- ∧E₁ Γ ⊢ _fst_ π : A
π pruvo ----------- _snd_-F _snd_ π pruvo		Γ ⊢ π : A ∧ B ------------- ∧E₂ Γ ⊢ _snd_ π : B
π pruvo ------------ λ-F _λu_. π pruvo		Γ, u:A ⊢ π : B ----------------- ⊃Mi Γ ⊢ _λu_. π : A ⊃ B
π₁ pruvo π₂ pruvo ------------------- _app_-F π₁ π₂ pruvo		Γ ⊢ π₁ : A ⊃ B Γ ⊢ π₂ : A ---------------------------- ⊃E Γ ⊢ π₁ π₂ : B
Γ ⊢ A tipo Γ, x:A ⊢ B tipo ----------------------------- Π-F Γ ⊢ _Πx_:A. B tipo		Γ ⊢ A tipo Γ, x:A ⊢ B tipo ---------------------------- Σ-F Γ ⊢ _Σx_:A. B tipo
Γ, x:A ⊢ π : B -------------------- _ΠI_ Γ ⊢ _λx_. π : _Πx_:A. B		Γ ⊢ π₁ : _Πx_:A. B Γ ⊢ π₂ : A ----------------------------- _ΠE_ Γ ⊢ π₁ π₂ : [π₂/x] B
Γ ⊢ π₁ : A Γ, x:A ⊢ π₂ : B ----------------------------- _ΣI_ Γ ⊢ (π₁, π₂) : _Σx_:A. B		Γ ⊢ π : _Σx_:A. B ---------------- _ΣE_₁ Γ ⊢ _fst_ π : A	Γ ⊢ π : _Σx_:A. B ------------------------ _ΣE_₂ Γ ⊢ _snd_ π : [_fst_ π/x] B
-------------- _XM_₁ ∨ ¬ A vera		¬ ¬ A vera ---------- _XM_₂ Vera	-------- u ¬ A vera ⋮ p vera ------ _XM_₃^{u, p} Vera
Valida -------- ◻Mi ◻ A vera		◻ A vera -------- ◻E Vera
Ω;⋅ ⊢ π : A vera -------------------- ◻Mi Ω;⋅ ⊢ skatolo π : ◻ A vera		Ω;Γ ⊢ π : ◻ A vera ---------------------- ◻E Ω;Γ ⊢ _unbox_ π : A vera
------------------------------- valida-_hyp_ Ω, u: (A valida) ; Γ ⊢ u : A vera
Γ ⇒ A --------- ∨R₁ Γ ⇒ A ∨ B		Γ ⇒ B --------- ∨R₂ Γ ⇒ A ∨ B
Γ, u:A ⇒ C Γ, v:B ⇒ C --------------------------- ∨L Γ, w: (A ∨ B) ⇒ C
Γ ⊢ A ∨ B Γ, u:A ⊢ C Γ, v:B ⊢ C --------------------------------------- ∨E Γ ⊢ C

------ _hyp_ \| \| _elim_. reguloj \| ↓ ---------------------- ↑↓ verigi ↑ \| \| _intro_. reguloj \| konkludo	⇒	--------------------------- _init_ ↑ ↑ \| \| \| (maldekstre, restita) reguloj \| (ĝusta, dekstra, rajto) reguloj \| \| konkludo
---------- _init_ Γ, u:A ⇒ A

Γ ⇒ π₁ : A Γ ⇒ π₂ : B --------------------------- ∧R Γ ⇒ (π₁, π₂) : A ∧ B		Γ ⊢ π₁ : A Γ ⊢ π₂ : B ------------------------- ∧Mi Γ ⊢ (π₁, π₂) : A ∧ B

Γ, v: (A ∧ B), u:A ⇒ π : C -------------------------------- ∧L₁ Γ, v: (A ∧ B) ⇒ [_fst_ v/u] π : C		Γ ⊢ π : A ∧ B ------------- ∧E₁ Γ ⊢ _fst_ π : A
Γ, v: (A ∧ B), u:B ⇒ π : C -------------------------------- ∧L₂ Γ, v: (A ∧ B) ⇒ [_snd_ v/u] π : C		Γ ⊢ π : A ∧ B ------------- ∧E₂ Γ ⊢ _snd_ π : B

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Natura_konkludo_8edd.html"

Kategorioj: Artikoloj por polurado kaj movo | Logiko | Pruva teorio