Vikipedio:Projekto matematiko/Logiko de dua ordo

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
Logiko de dua ordo
(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, logiko de dua ordo estas vastigaĵo de ĉu propona logiko aŭ logiko de la unua ordo. Logiko de dua ordo enhavas (variabloj, variablas) en predikato (pozicioj, pozicias) (iom ol nur en (termo, membro, flanko, termino) (pozicioj, pozicias), kiel en logiko de la unua ordo), kaj (kvantoroj, kvantumiloj, kvantumas) (bindanta, agrafo) ilin. (Do, Tiel):

$\forall F\ F(\mathrm{jones}) \lor \neg F(\mathrm{jones})\,$

kiu povus (ekspreso, esprimi) la principo de _bivalence_ kun respekto al _Jones_: Por ĉiu propraĵo, ĉu _Jones_ havas ĝi aŭ li ne.

Kiel alia ekzemplo, ni povas skribi en logiko de la unua ordo kondamni ŝati:

$\exists x\ P(x)$

sed ni ne povas fari la sama kun la predikato. Tio estas, jena esprimo:

$\exists P\ P(x)$

estas ne kondamni de logiko de la unua ordo. Sed ĉi tiu estas _legitimate_ kondamni de logiko de dua ordo.

Logiko de dua ordo (konsentas, permesas) de diversaj (interpretadoj, interpretadas); ofte ĝi estas penso de kiel enhavanta kvantoro super (subaroj, subaras) de domajno, aŭ funkcioj de la domajno enen sin, iom ol nur super persona (membroj, membras) de la domajno. Tial, ekzemple, se la domajno estas la aro de ĉiuj reelaj nombroj, unu povas aserti en logiko de la unua ordo la ekzisto de kontraŭegalo de ĉiu reela nombro per skribanta

$\forall x\ \exists y\ x+y=0$

sed unu (bezonas, bezonoj) logiko de dua ordo al aserti la plej malgranda-supra-bara propraĵo de la reelaj nombroj:

$\forall A\subseteq R\ [\cdots\cdots]$

kaj enigi anstataŭ la (punktoj, punktas) (propozicio, frazo, ordono) (tiu, ke, kiu) se A estas nemalplena kaj havas supera baro en R tiam A havas supremo en R.

(tabelo de matematikaj simboloj)

Enhavo

1 Kial logiko de dua ordo estas ne reduktebla al logiko de la unua ordo
2 Logiko de dua ordo kaj _metalogical_ rezultoj
3 La historio kaj disputis valoro de logiko de dua ordo
4 Povo de la ekzisteco (parto, dispecigi) sur finia (strukturoj, strukturas)
5 Aplikoj al komplekseco

[redaktu] Kial logiko de dua ordo estas ne reduktebla al logiko de la unua ordo

Optimisto povus provi al redukti logiko de dua ordo al logiko de la unua ordo en jena vojo. Elvolvi la domajno de la aro de ĉiuj reelaj nombroj al la unio de (tiu, ke, kiu) aro kun la aro de ĉiuj aroj de reelaj nombroj. Adicii nova duuma predikato al la lingvo: la membrorilato. Tiam kondamnas (tiu, ke, kiu) estis (sekundo, dua)-(mendi, ordo) iĝi unua-(mendi, ordo).

Sed (rimarki, avizo) (tiu, ke, kiu) la domajno estis asertita al inkluzivi ĉiuj aroj de reelaj nombroj. (Tiu, Ke, Kiu) bezono havas ne estas reduktita al unua-(mendi, ordo) kondamni! Sed povus tie esti iu vojo al atingi la malpligrandiĝo? La klasika Lö_wenheim_-_Skolem_ teoremo sekvigas (tiu, ke, kiu) estas ne. (Tiu, Ke, Kiu) teoremo (implicas, enhavas) (tiu, ke, kiu) estas iu kalkuleble malfinia subaro de R, kies (membroj, membras) ni estos (voko, voki) interne nombroj, kaj iu kalkuleble malfinia aro de aroj de interne nombroj, kies (membroj, membras) ni estos (voko, voki) "interne aroj", tia (tiu, ke, kiu) la domajno konsistanta de interne nombroj kaj interne aroj (verigas, kontentigas) ĉiuj de la unua-(mendi, ordo) kondamnas kontentigita per la domajno de (reala, reela)-nombroj-kaj-aroj-de-(reala, reela)-nombroj. En aparta, ĝi (verigas, kontentigas) (speco, ordigo) de plej malgranda-supra-bara aksiomo (tiu, ke, kiu) diras, en efiki:

Ĉiu nemalplena interne aro (tiu, ke, kiu) havas interne supera baro havas plej malgranda interne supera baro.

_Countability_ de la aro de ĉiuj interne nombroj (en (konjunkcio, aŭo, kajo) kun la fakto (tiu, ke, kiu) tiuj (formo, formi) (dense, kompakte) orda aro) bezone (implicas, enhavas) (tiu, ke, kiu) (tiu, ke, kiu) aro ne kontentigi la plena plej malgranda-supra-bara aksiomo. _Countability_ de la aro de ĉiuj interne aroj bezone (implicas, enhavas) tio estas ne la aro de ĉiuj (subaroj, subaras) de la aro de ĉiuj interne nombroj (ekde Teoremo de Cantor (implicas, enhavas) (tiu, ke, kiu) la aro de ĉiuj subaroj de kalkuleble malfinia aro estas nekalkulebla malfinia aro).

Ankoraŭ alia profunda diferenco inter unua-(mendi, ordo) kaj logiko de dua ordo estas la aktualaĵo de la venonta sekcio.

[redaktu] Logiko de dua ordo kaj _metalogical_ rezultoj

Ĝi estas korolario de Gö_del_'s nepleneca teoremo tiu ne povas havi (ĉiu, iu) nocio de _provability_ de (sekundo, dua)-(mendi, ordo) (formuloj, formulas) donita la norma interpretado de la lingvo (aŭ simple normo (semantiko, semantikoj, semantikas)) (tiu, ke, kiu) samtempe (verigas, kontentigas) ĉi tiuj tri dezirita (atribuas, atributoj, atributas):

(Soneco) Ĉiu demonstrebla (sekundo, dua)-(mendi, ordo) kondamni estas universe valida, kio estas, vera totale domajnoj.

(Pleneco) Ĉiu universe valida (sekundo, dua)-(mendi, ordo) formulo estas demonstrebla.

("Efikeco") Estas pruvo-kontrolanta algoritmo. (Ĉi tiu tria kondiĉo estas ofte prenita tiom (da) por koncedis (tiu, ke, kiu) ĝi estas ne eksplicite komencita.)

Ĉi tiu estas iam esprimita per (diranta, dirante) (tiu, ke, kiu) logiko de dua ordo ne konsenti plenumi pruva teorio.

En ĉi tiu respekta logiko de dua ordo diferencas de logiko de la unua ordo, kaj ĉi tiu estas almenaŭ unu de la kaŭzoj (logikistoj, logikistas) havi _shied_ for de ĝia uzi. (Sinskriba programo foje punktita al ĉi tiu kiel kaŭzo por (opinianta, pensanta) de logiko de dua ordo kiel ne logiko, pozitive parolanta.) Kiel Georgo _Boolos_ havas punktita ekster, kvankam, ĉi tiu nepleneco (enigas, eneniras) nur kun _polyadic_ logiko de dua ordo: logiko kvantiganta super n-loko (predikatoj, predikatas), por n > 1. Sed unuloka logiko de dua ordo, limigis al unu-loko (predikatoj, predikatas), estas ne nur plenumi kaj konsekvenca sed decidebla--tio estas, pruvo de ĉiu vera teoremo estas ne nur ebla sed _determinately_ alirebla per mekanika maniero. En ĉi tiu respekto, unuloka logiko de dua ordo fartas pli bona ol _polyadic_ logiko de la unua ordo: unuloka logiko de dua ordo estas plenumi, konsekvenca kaj decidebla, sed _polyadic_ logiko de la unua ordo, kvankam konsekvenca kaj plenumi, estas jam ne decidebla (Vidi problemo de haltado).

En 1950, _Leon_ _Henkin_ donis adekvateco (kio estas pleneco kaj soneco) kaj kompaktecaj pruvoj por logiko de dua ordo kun _Henkin_ (semantiko, semantikoj, semantikas). La nur diferenco inter normo kaj _Henkin_ (semantiko, semantikoj, semantikas) estas (tiu, ke, kiu) en _Henkin_ (semantiko, semantikoj, semantikas) la domajno de predikato (variabloj, variablas) estas ajna aro de aroj de (individuoj, individuas) (de la domajno) iom ol la aro de ĉiuj aroj de (individuoj, individuas) (de la domajno). Lia pruvo procedas kiel ĝi faras por la unua-(mendi, ordo) funkcionala kalkulo. Ambaŭ rezultoj estis enhavita en lia (disertacio, disertaĵo).

[redaktu] La historio kaj disputis valoro de logiko de dua ordo

Kiam predikata logiko estis prezentita al la matematika komunaĵo per _Frege_ (kaj sendepende — kaj pli influe — per _Peirce_, kiu moneris la (termo, membro, flanko, termino) Logiko de dua ordo), li farita uzi malsama (variabloj, variablas) al (distingi, diferencigi) kvantoro super (objektoj, objektas) de kvantoro super propraĵoj kaj aroj; sed li farita ne vidi sin kiel farante du malsama (specoj, specas) de logiko. Post la malkovro de Paradokso de Russell ĝi estis komprenita (tiu, ke, kiu) io estis erara kun lia sistemo. Eble (logikistoj, logikistas) fundamenti (tiu, ke, kiu) limiganta _Frege_'s logiko diversmaniere—al kio estas nun (nomita, vokis) logiko de la unua ordo—eliminis ĉi tiu problemo: aroj kaj propraĵoj ne povas esti kvantigita super en unua-(mendi, ordo)-logiko sola. La nun-norma hierarkio de (mendas, ordoj) de (logikoj, logikas) (datoj, datas, rendevuoj, rendevuas, daktilarboj, daktilarbas, daktilujoj, daktilujas, daktiloj, daktas) de ĉi tiu tempo.

Ĝi estis fundamenti (tiu, ke, kiu) aroteorio povis esti formulita kiel _axiomatized_ sistemo en la aparato de logiko de la unua ordo (je la kosti de kelkaj (specoj, specas) de pleneco, sed nenio (do, tiel) malbona kiel Paradokso de Russell), kaj ĉi tiu estis farita (vidi _Zermelo_-_Fraenkel_ aroteorio), kiel aroj estas vitala por matematiko. Aritmetiko, _mereology_, kaj (diversaj, diversaĵo) de aliaj povaj logikaj teorioj povis esti formulita aksiome sen alvoki (ĉiu, iu) pli logika aparato ol unua-(mendi, ordo) kvantoro, kaj ĉi tiu, laŭ kun Gödel-a kaj _Skolem_'s (adheraĵo, adhero) al logiko de la unua ordo, gvidis al ĝenerala deklinacii en laboro en (sekundo, dua) (aŭ (ĉiu, iu) pli alta) (mendi, ordo) logiko.

Ĉi tiu malakcepto estis aktive plibonigita per iu (logikistoj, logikistas), plej rimarkinde W. V. Sinskriba programo. Sinskriba programo plibonigita la vido (tiu, ke, kiu) en predikato-lingvo kondamnas ŝati _Fx_ la "x" estas al esti penso de kiel (variablo, varianta) aŭ noma signifanta objekto kaj de ĉi tie povas esti kvantigita super, kiel en "Por ĉiuj aĵoj, ĝi estas la (kesto, okazo) (tiu, ke, kiu) . . ." sed la "F" estas al esti penso de kiel mallongigo por nekompleta kondamni, ne la nomo de objekto (ne (eĉ, ebena, para) de abstrakta objekto ŝati propraĵo). Ekzemple, ĝi povus (meznombro, signifi) " . . . estas hundo." Sed ĝi (konstruas, faras) ne (senso, senco) al (opinii, pensi) ni povas kvantigi super io tiamaniere. (Tia pozicio estas sufiĉe konsekvenca kun _Frege_'s posedi (argumentoj, argumentas) sur la koncepto-objekta distingo). (Do, Tiel) al uzi predikato kiel (variablo, varianta) estas al havi ĝi okupi la loko de nomo kiu nur persona (variabloj, variablas) devus okupi. Ĉi tiu (racianta, rezonanta, kaŭzanta) havas estas (malakceptita, malaprobita) per _Boolos_.

En ĵusa (jaroj, jaras) logiko de dua ordo havas farita io de savo, (naĝobarelis, buita) per Georgo _Boolos_' interpretado de (sekundo, dua)-(mendi, ordo) kvantoro kiel plurala kvantoro super la sama domajno de (objektoj, objektas) kiel unua-(mendi, ordo) kvantoro. _Boolos_ plue punktoj al la _nonfirstorderizability_ de kondamnas kiel "Iu (kritikistoj, kritikoj, kritikas) admiri nur unu la alian" kaj "Iu de _Fianchetto_'s viroj iris enen la (magazeno, doko, stokejo) _unaccompanied_ per ĉiu alia." kiu povas nur esti esprimita per la plena forto de (sekundo, dua)-(mendi, ordo) kvantoro. (Ĉi tiu estas fakte ne vera kiel ĝeneraligis kvantoro kaj parte-(mendita, ordita) (aŭ (branĉanta, alanta, forkiĝanta)) kvantoro sufiĉas al (ekspreso, esprimi) certa klaso de _nonfirstorderizable_ kondamnas kiel bone kaj ĝi ne alvoki (sekundo, dua)-(mendi, ordo) kvantoro.)

[redaktu] Povo de la ekzisteco (parto, dispecigi) sur finia (strukturoj, strukturas)

La ekzisteco (parto, dispecigi) (_EMSO_) de unuloka logiko de dua ordo (_MSO_) estas logiko de dua ordo sen la universala kvantoro. Super (vortoj, vortas) $w \in \Sigma^*$ , ĉiu _MSO_ formulo povas esti konvertita enen (determinisma, determina) finia stata maŝino. Ĉi tiu denove povas esti konvertita enen _EMSO_ formulo. Tial _EMSO_ kaj _MSO_ estas ekvivalento super (vortoj, vortas). Por (arboj, arbas) kiel (enigo, enigi), ĉi tiu rezulto tenas kiel bone. Tamen, super la finia krado $Σ + +$ , ĉi tiu propraĵo ne teni (ĉiu, iu) pli, ekde la lingvoj agnoskis per (kahelanta, kahelado) sistemoj estas ne (fermita, fermis) sub komplemento. Ekde universala kvantoro estas ekvivalento al (neis, neigita) ekzistokvantoro, kiu ne povas esti esprimita, alternadoj de universala kaj ekzistokvantoroj generi pli granda kaj pli grandaj klasoj de lingvoj super $Σ + +$ .

[redaktu] Aplikoj al komplekseco

La _expressibility_ de diversaj (formoj, formas) de logiko de dua ordo estas intime (kravatita, ligita) al komputa komplekseca teorio. En aparta:

(Np, NP) estas la aro de lingvoj esprimebla per ekzisteca logiko de dua ordo.
co-NP estas la aro de lingvoj esprimebla per universala logiko de dua ordo.
PH (kemia parametro) estas la aro de lingvoj esprimebla per logiko de dua ordo.
_PSPACE_ estas la aro de lingvoj esprimebla per logiko de dua ordo kun adiciis transitiva fermaĵa operatoro.
_EXPTIME_ estas la aro de lingvoj esprimebla per logiko de dua ordo kun adiciis plej malgranda fiksa punkta operatoro.

Interrilatoj inter ĉi tiuj klasoj rekte influo la relativa _expressiveness_ de la (logikoj, logikas); ekzemple, se PH (kemia parametro)=_PSPACE_, tiam adicianta transitiva fermaĵa operatoro al logiko de dua ordo ne fari ĝi (ĉiu, iu) pli esprima.

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

Kategorioj: Artikoloj por polurado kaj movo | Modela teorio | Matematika logiko