Vikipedio:Projekto matematiko/Lineara logiko

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
Lineara logiko
(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, lineara logiko estas tipo de substruktura logiko (tiu, ke, kiu) malkonsentas la strukturaj reguloj de malfortiganta kaj kuntiro. La interpretado estas de hipotezoj kiel (rimedo, rimedoj, rimedas): ĉiu hipotezo devas esti konsumita akurate iam en pruvo. Ĉi tiu diferencas de kutima (logikoj, logikas) kiel klasika aŭ instituteca logiko kie la reganta juĝo estas de vero, kiu (majo, povas) esti libere uzita kiel multaj (tempoj, tempas) kiel necesa. Al doni ekzemplo, de (propozicioj, propozicias) A kaj A ⇒ B unu (majo, povas) konkludi A ∧ B kiel sekvas:

Elimplikaciigo (aŭ implikacia elimino) sur la (premisoj, supozoj, supozas) A kaj A ⇒ B al konkludi B.
(Konjunkcio, Aŭo, Kajo) de la (premiso, supozo) A kaj (1) al konkludi A ∧ B.

Ĉi tiu estas ofte signmaniere (prezentita, prezentis) kiel sekva: A, A ⇒ B ├ B. Ambaŭ linioj en la pli supre pruvo "konsumi" la fakto (tiu, ke, kiu) A estas vera; ĉi tiu "_freeness_" de vero estas kutime kio estas dezirita en formala matematiko.

Tamen, vero estas ofte ankaŭ abstrakta aŭ _unwieldy_ kiam aplikis al (propozicioj, frazoj, ordonoj) pri la mondo. Ekzemple, supozi Mi havi kvarto de (lakto, melki) de kiu Mi povas fari (funto, pisti, pundo) de (butero, buterigi, buterumi). Se Mi decidi al fari (butero, buterigi, buterumi) el ĉiuj de mia (lakto, melki), Mi ne povas tiam konkludi (tiu, ke, kiu) Mi havi ambaŭ (lakto, melki) kaj (butero, buterigi, buterumi)! Ankoraŭ, la logikaj skemoj konturis pli supre lasas mi konkludi (tiu, ke, kiu) <tajpeska tiparo TTF>(lakto, melki)</tajpeska tiparo TTF>, <tajpeska tiparo TTF>(lakto, melki)</tajpeska tiparo TTF> ⇒ <tajpeska tiparo TTF>(butero, buterigi, buterumi)</tajpeska tiparo TTF> ├ <tajpeska tiparo TTF>(lakto, melki)</tajpeska tiparo TTF> ∧ <tajpeska tiparo TTF>(butero, buterigi, buterumi)</tajpeska tiparo TTF> (ĉi tie, <tajpeska tiparo TTF>(lakto, melki)</tajpeska tiparo TTF> staras por la propozicio "Mi havi kvarto de (lakto, melki)", kaj tiel plu). La malsukceso de ordinara logiko al precize modelo ĉi tiu agado estas pro al la naturo de (lakto, melki), (butero, buterigi, buterumi), kaj (rimedo, rimedoj, rimedas) en ĝenerala: la kvanto de (rimedo, rimedoj, rimedas) estas ne libera fakto al esti uzita aŭ disponis laŭvole, ŝati vero, sed iom devas esti (zorgeme, zorge) (kontis, kalkulita) en ĉiu "(ŝtato, stato, stati) ŝanĝi". La preciza (propozicio, frazo, ordono) pri mia (butero, buterigi, buterumi) farante agado estas:

De kvarto de (lakto, melki) kaj procezo al konverti kvarto de (lakto, melki) enen (funto, pisti, pundo) de (butero, buterigi, buterumi), Mi ricevi (funto, pisti, pundo) de (butero, buterigi, buterumi).

En lineara logiko ĉi tiu estas skribita: <tajpeska tiparo TTF>(lakto, melki)</tajpeska tiparo TTF>, <tajpeska tiparo TTF>(lakto, melki)</tajpeska tiparo TTF> ⊸ <tajpeska tiparo TTF>(butero, buterigi, buterumi)</tajpeska tiparo TTF> ⊩ <tajpeska tiparo TTF>(butero, buterigi, buterumi)</tajpeska tiparo TTF>, uzanta malsama (ligiloj, ligas) (⊸ anstataŭ ⇒) kaj malsama nocio de logika _entailment_.

Lineara logiko estis proponita per la Franca matematikisto _Jean_-_Yves_ _Girard_ en 1987.

[redaktu] Lineara (ligiloj, ligas)

La logikaj ligiloj estas rao-ekzamenita en ĉi tiu (risurco, rimedo)-interpretado; ĉiu ligilo (klivas, fendas, forkiĝas) enen multiplika kaj alsuma (versioj, versias), kiu esti konforma laŭ samtempa kaj alternativo ekzisto, respektive. Al motivigi la (ligiloj, ligas), estu ni uzi la ekzemplo de vendaŭtomato.

Multiplika (konjunkcio, aŭo, kajo), ankaŭ (nomita, vokis) tensoro (skribita ⊗), signifas samtempa aper(aĵ)o de (rimedo, rimedoj, rimedas). Ekzemple, se Mi enigi 50 cendoj enen la vendaŭtomato, tiam la vendaŭtomato samtempe havas <tajpeska tiparo TTF>cendo</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>cendo</tajpeska tiparo TTF> ⊗ ⋯ ⊗ <tajpeska tiparo TTF>cendo</tajpeska tiparo TTF> (50 de ilin). Se Mi aĉeti du (bastonoj, bastonas) de (dentkarno, dentokarno), ilin Mi ricevi <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF>. Se la maŝino havis kvar (bastonoj, bastonas) de (dentkarno, dentokarno) (<tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF>) antaŭ, ĝi havas du nun: <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>(dentkarno, dentokarno)</tajpeska tiparo TTF>. La konstanto 1 estas uzita al signifi la foresto de (risurco, rimedo); ĝiaj funkcioj kiel unuo de tensoro: A ⊗ 1 ≡ 1 ⊗ A ≡ A.

Alsuma (konjunkcio, aŭo, kajo), ankaŭ sciata kiel interne elekto (skribita &) prezentas alternativo aper(aĵ)o de (rimedo, rimedoj, rimedas). Se en la vendaŭtomato estas paketo de (terpomflokoj, terpomflokas, blatoj, blatas), (mezuro, drinkejo, bari) de bombono, kaj botelo de mola (trinkaĵo, drinkaĵo, drinki, trinki, alkoholaĵo), ĉiuj valori 50 cendoj ĉiu, tiam post eniganta 50 cendoj Mi povas preni akurate unu de ĉi tiuj (produktoj, produktas, produktaĵoj, produktaĵas, produtoj, produtas). Post la aĉeti, Mi havi <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF> & <tajpeska tiparo TTF>(terpomflokoj, terpomflokas, blatoj, blatas)</tajpeska tiparo TTF> & <tajpeska tiparo TTF>(trinkaĵo, drinkaĵo, drinki, trinki, alkoholaĵo)</tajpeska tiparo TTF>, kio estas, akurate unu de la _conjuncts_. Mi ne povas uzi ⊗ por la rezulto ĉar Mi ne povas preni ĉiuj de ĉi tiuj (produktoj, produktas, produktaĵoj, produktaĵas, produtoj, produtas) samtempe kun nur 50 cendoj. Alsuma (konjunkcio, aŭo, kajo) havas unuo supro (skribita ⊤, kun A & ⊤ ≡ ⊤ & A ≡ A); ĝi prezentas la _nullary_ alternativo. Ĝi estas ofte uzita kiam la akurata (kalkulanta, kalkulo) de (rimedo, rimedoj, rimedas) estas peza aŭ neebla. Ekzemple, se Mi don't reale (zorgi, zorgo) kio Mi preni de la maŝino, aŭ ja se Mi preni io ajn, tiam la rezulto kiel malproksime kiel Mi am koncernis estas ⊤. Ĉi tiu unuo povas esti uzita kaj ankaŭ ⊗ al difini minimuma komponaĵo de (rimedo, rimedoj, rimedas): se Mi bezona bombono (mezuro, drinkejo, bari) almenaŭ, sed eble alio ankaŭ, tiam mia deziris rezulto estas <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF> ⊗ ⊤.

Alsuma (kajaŭo, disjunkcio), ankaŭ sciata kiel ekstera elekto (skribita ⊕) prezentas elekto super kiu havas ne regi. Ekzemple, se la vendaŭtomato permesas mi al veti (kio estas, "enigi 50 cendoj kaj konkeri bombono (mezuro, drinkejo, bari), mola (trinkaĵo, drinkaĵo, drinki, trinki, alkoholaĵo), aŭ ĉiu elspeza pagita ferio al Havajo") tiam la rezulto de la aĉeti estas <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF> ⊕ <tajpeska tiparo TTF>(trinkaĵo, drinkaĵo, drinki, trinki, alkoholaĵo)</tajpeska tiparo TTF> ⊕ <tajpeska tiparo TTF>ferio</tajpeska tiparo TTF>. Mi scii (tiu, ke, kiu) Mi estos preni unu de la elektoj, sed Mi havi ne regi super la rezulto. (Tononomo, Noto, Noti) la diferenco de interne elekto: se Mi havita <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF> & <tajpeska tiparo TTF>(trinkaĵo, drinkaĵo, drinki, trinki, alkoholaĵo)</tajpeska tiparo TTF> & <tajpeska tiparo TTF>ferio</tajpeska tiparo TTF>, tiam Mi povita elekti la <tajpeska tiparo TTF>ferio</tajpeska tiparo TTF> se Mi _wasn_'t (palpanta, sentanta) aparte malsata aŭ soifa. La unuo de ⊕ estas skribita 0, kaj prezentas manko de rezulto aŭ katastrofa malsukceso — diri la vendaŭtomato (marmeladoj, marmeladas), aŭ la mondo estas detruita per (trairanta, pasanta) kometo.

Multiplika (kajaŭo, disjunkcio), ankaŭ (nomita, vokis) _par_ (skribita ⅋) prezentas samtempaj goloj (tiu, ke, kiu) devas esti atingita. Ĝi estas io (pli peza, pli peza) al motivigi uzanta la vendaŭtomata metaforo. Se estas aparta aromo de bombono (tiu, ke, kiu) Mi ŝati treege, sed Mi havi _forgotten_ ĝia nomo, tiam Mi povas aĉeti multaj (mezuroj, mezuras, drinkejoj, drinkejas, baras) kaj provi al (serĉi, serĉo) por mia favorata. Ĉiu aĉeti konsumas iu de mia mono, sed mia nur regi super la rezulto de ĉi tiu eksperimento estas per aliiganta mia (mendi, ordo) de (areo, elektado) de la diversa bombono (mezuroj, mezuras, drinkejoj, drinkejas, baras). En ĉi tiu (kesto, okazo) la rezulto estas <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF>₁ ⅋ ⋯ ⅋ <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF>_n. La unuo de ⅋ estas fundo (skribita ⊥), kaj staras por la malplena golo: imagi (malkonsentanta, elĵetaĵanta, forĵet(ind)aĵanta, rifuzanta) al enigi (ĉiu, iu) mono, aŭ tiranta la "monero redoni" baskulo sen farante (areo, elektado).

Lineara implikacio. La (konjunkcioj, konjunkcias, aŭoj, aŭas, kajoj, kajas) kaj (kajaŭoj, kajaŭas, disjunkcioj, disjunkcias) pli supre difini la (ŝtato, stato, stati) de la mondo, sed la priskribo estas statika. Por (ŝtato, stato, stati) ŝanĝi, lineara logiko difinas la ligilo de lineara implikacio (skribita ⊸), iam ankaŭ sciata kiel _multimap_ aŭ _lolli_ pro ĝia _lollipop_Eca formo. La propozicio A ⊸ B (meznombroj, meznombras, signifas): konsumi (risurco, rimedo) A al (efektivigi, atingi) (risurco, rimedo) B. Ekzemple, se Mi aĉeti bombono (mezuro, drinkejo, bari) kun du (kvartaloj, kvartalas), tiam Mi povas priskribi la ŝanĝi kiel <tajpeska tiparo TTF>kvartalo</tajpeska tiparo TTF> ⊗ <tajpeska tiparo TTF>kvartalo</tajpeska tiparo TTF> ⊸ <tajpeska tiparo TTF>bombono</tajpeska tiparo TTF>. (Tononomo, Noto, Noti) (tiu, ke, kiu) la implikacia sin estas (risurco, rimedo) (tiu, ke, kiu) devas obei la principo de sola ftizo.

Eksponenta funkcio (ligiloj, ligas). La kolekto de (ligiloj, ligas) (do, tiel) malproksime estas bonega por priskribanta (ŝtato, stato, stati) kaj (trairoj, trairas), sed ili estas ankaŭ malforta se unu (bezonas, bezonoj) la kutima nocio de vero. Ĉi tiu estas evidente tre dezirinda ĉar diskuto pri la reala mondo devus ne _preclude_ normo matematika (racianta, rezonanta, kaŭzanta). Lineara logiko uzas ideo de modala logiko al _embed_ la kutima logiko per paro de eksponenta funkcio (operatoroj, operatoras).

Rao-uzi aŭ kopianta estas permesita por (propozicioj, propozicias) uzanta la "kompreneble" eksponenta funkcia operatoro (skribita !). Logike, du (aper(aĵ)oj, aper(aĵ)as) de !A kiel hipotezoj (majo, povas) esti kontraktita enen sola aper(aĵ)o.
La kolekto de goloj estas permesita al esti etendita kun (propozicioj, propozicias) uzanta la "kial ne" operatoro (skribita ?). Logike, (ĉiu, iu) fakto povas esti malfortigita per inkluzivanta aldona konkludo ?A.

Sub la (risurco, rimedo) interpretado, ! kodas ajna (produktado, produkto) kaj ? kodas ajna ftizo.

[redaktu] Aromoj de lineara logiko

Lineara logiko havas multaj limigoj kaj (rikordaj kazoj, variantoj, variantas). La primara akso de variado estas laŭ la klasika/instituteca dividi. Klasika lineara logiko (_CLL_) estas la originala lineara logiko kiel proponis per _Girard_. En _CLL_ ĉiu ligilo havas duala. Jeno estas duflanka (surscenigo, prezento) de _CLL_ kiel sekva kalkulo:

Image:Sequent_calculus_for_classical_linear_logic.png

Lineara implikacio estas difinebla en (termoj, kondiĉoj, terminoj, termas, terminas) de lineara nego kaj multiplika (kajaŭo, disjunkcio) en _CLL_: A ⊸ B ≡ ? A ⅋ B. Ĉi tiu estas familiara de alia klasika (logikoj, logikas): ekzemple, la kutima implikacio ⇒ estas simile difinebla: A ⇒ B ≡ ? A ∨ B. Tia (difinoj, difinas) kompreneble postuli nocio de nego, sed en klasika logiko unu povas uzi _duals_: la duala de A, skribita A^⊥ estas difinita kiel sekvas.

(A ⊗ B)^⊥	=	A^⊥ ⅋ B^⊥
(A & B)^⊥	=	A^⊥ ⊕ B^⊥
(A ⊕ B)^⊥	=	A^⊥ & B^⊥
(A ⅋ B)^⊥	=	A^⊥ ⊗ B^⊥

La logika (unuoj, unuas) havi simila _duals_; ekzemple: ⊤^⊥ = 0.

Instituteca lineara logiko (_ILL_) permesas nur sola konkludo. Malverŝajne _CLL_, (ligiloj, ligas) en _ILL_ ne havi perfekta _duals_. Ja, la (ligiloj, ligas) _par_ kaj demandosigno, kaj la propona konstanto fundo (⊥), estas malasidua en _ILL_ ĉar ilia enkonduko postulas multaj (konkludoj, konkludas). Kiel rezulto, lineara implikacio estas baza ligilo en _ILL_.

Alia (rikordaj kazoj, variantoj, variantas) de lineara logiko diverse permesi aŭ _disallow_ certa (ligiloj, ligas), donanta pligrandiĝo al (logikoj, logikas) kun varianta komplekseco. Jeno estas la plej komuna (rikordaj kazoj, variantoj, variantas).

Multiplika lineara logiko aŭ _MLL_. Ĉi tiu (rikorda kazo, varianto) permesas nur la multiplika (ligiloj, ligas) tensoro kaj _par_ (kaj ilia (unuoj, unuas)). Ĝi estas decidebla, sed la decida problemo estas NP-pleneco.
Multiplika alsuma lineara logiko aŭ _MALL_, kiu adicias la alsuma (ligiloj, ligas) al _MLL_. Ĉi tiu (rikorda kazo, varianto) estas ankaŭ decidebla kun _PSPACE_-plenumi decida problemo.
Multiplika eksponenta funkcia lineara logiko aŭ _MELL_, kiu estas _MLL_ plus la eksponenta funkcio (operatoroj, operatoras). La decida problemo por _MELL_ estas nun (malfermi, malfermita).
Multiplika alsuma eksponenta funkcia lineara logiko aŭ _MAELL_, kiu havas ĉiu pli supre (ligiloj, ligas). Ĉi tiu (rikorda kazo, varianto) estas nedecidebla.

Estas ankaŭ unua- kaj pli alta-(mendi, ordo) (vastigaĵoj, vastigaĵas) de lineara logiko, sed ilia evoluo estas normo (Vidi logiko de la unua ordo kaj logiko de pli alta ordo.)

La plej proksima sub-struktura (kuzoj, kuzas) de lineara logiko estas:

Afina logiko, kiu etendas lineara logiko kun la struktura regulo de malfortiganta. La (ligiloj, ligas) unu kaj supro estas nediferencigebla en afina logiko.
Severa logiko aŭ taŭga logiko, kiu etendas lineara logiko kun la struktura regulo de kuntiro.
Ne-komuta logiko aŭ (mendita, ordita) logiko kiu forprenas la struktura regulo de interŝanĝi de lineara logiko. Multiplika (konjunkcio, aŭo, kajo) (akvodislimoj, akvodislimas, divizoras, dividas) plui enen paro de kunfandiĝis ((maldekstre, restis) kunfandiĝi kaj (ĝusta, dekstra, rajto) kunfandiĝi).