O interpretare a unui limbaj de prim ordin atribuie o notare fiecărui simbol non-logic din limba respectivă. De asemenea, determină un domeniu al discursului care specifică gama de cuantificatori. Rezultatul este că fiecărui termen i se atribuie un obiect pe care îl reprezintă, fiecărui predicat i se atribuie o proprietate a obiectelor și fiecărei propoziții i se atribuie o valoare de adevăr. În acest fel, o interpretare oferă un sens semantic termenilor, predicatelor și formulelor limbajului. Studiul interpretărilor limbajelor formale se numește semantică formală. Ceea ce urmează este o descriere a semanticii standard sau tarskiene pentru logica de prim ordin. (De asemenea, este posibil să definiți semantica jocului pentru logica de prim ordin, dar, în afară de necesitarea axiomei de alegere, semantica jocului este de acord cu semantica tarskiană pentru logica de prim ordin.)
Domeniul discursului D este un set non-gol de „obiecte” de un fel. Intuitiv, o formulă de prim ordin este o afirmație despre aceste obiecte; de exemplu, ∃xP(x) afirmă existența unui obiect x astfel încât predicatul P este adevărat unde s-a referit la el. Domeniul discursului este ansamblul obiectelor considerate. De exemplu, se poate lua D ca fiind setul de numere întregi.
Interpretarea unui simbol al funcției este o funcție. De exemplu, dacă domeniul discursului este format din numere întregi, un simbol al funcției f de aritate 2 poate fi interpretat ca funcția care dă suma argumentelor sale. Cu alte cuvinte, simbolul f este asociat cu funcția I(f) care, în această interpretare, este sumare.
Interpretarea unui simbol constant este o funcție din setul de un element D0 la D, care poate fi identificat pur și simplu cu un obiect din D. De exemplu, o interpretare poate atribui valoarea I(c) = 10 simbolului constant c .
Interpretarea unui simbol predicat n-ary este un set de n-tuple de elemente ale domeniului discursului. Aceasta înseamnă că, având o interpretare, un simbol predicat și n elemente din domeniul discursului, se poate spune dacă predicatul este adevărat pentru acele elemente conform interpretării date. De exemplu, o interpretare I(P) a unui simbol de predicat binar P poate fi ansamblul de perechi de numere întregi, astfel încât primul este mai mic decât al doilea. Conform acestei interpretări, predicatul P ar fi adevărat dacă primul argument este mai mic decât al doilea.
Structuri de prim ordin
Cel mai frecvent mod de a specifica o interpretare (mai ales în matematică) este de a specifica o structură (numită și model). Structura este alcătuită dintr-un set D non-gol care formează domeniul discursului și o interpretare I a termenilor non-logici ai semnăturii. Această interpretare este ea însăși o funcție:
- Fiecărui simbol de funcție f de aritate n i se atribuie o funcție I(f) de la Dn la D. În special, fiecărui simbol constant al semnăturii i se atribuie un individual în domeniul discursului.
- Fiecărui simbol de predicat P de aritate n i se atribuie o relație I(P) peste Dn sau, echivalent, o funcție de la Dn la {true, false}. Astfel, fiecare simbol predicat este interpretat de o funcție booleană evaluată pe D.
Evaluarea valorilor de adevăr
O formulă evaluează o interpretare ca adevărată sau falsă, și o atribuire a variabilei μ care asociază un element din domeniul discursului cu fiecare variabilă. Motivul pentru care este necesară o alocare a variabilelor este de a da semnificații formulelor cu variabile libere, cum ar fi y = x. Valoarea de adevăr a acestei formule se schimbă în funcție de faptul dacă x și y denotă același individ.
În primul rând, atribuirea variabilă μ poate fi extinsă la toți termenii limbajului, cu rezultatul că fiecare termen mapează un singur element al domeniului discursului. Următoarele reguli sunt utilizate pentru a efectua această atribuire:
- Variabile. Fiecare variabilă x se evaluează la μ(x)
- Funcții. Dat fiind termenii t1,…, tn care au fost evaluați la elementele d1,…, dn din domeniul discursului și un simbol al funcției n-ary, termenul f(t1,…, tn) se evaluează la (I(f))(d1,…, dn).
În continuare, fiecărei formule i se atribuie o valoare de adevăr. Definiția inductivă folosită pentru realizarea acestei atribuții se numește schema T.
- Formule atomice (1). O formulă P(t1,…, tn) este asociată cu valoarea adevărat sau fals, în funcție de dacă ‹v1,…, vn› ∈ I(P), unde v1,…, vn sunt evaluarea termenilor t1,…, tn și I(P) este interpretarea lui P.
- Formule atomice (2). O formulă t1 = t2 este atribuită adevărat dacă t1 și t2 evaluează același obiect al domeniului discursului.
- Conectori logici. O formulă sub forma ¬ ϕ, ϕ → ψ etc. este evaluată conform tabelului de adevăr pentru conectorul în cauză, ca în logica propozițională.
- Cuantificatori existențiali. O formulă ∃xϕ(x) este adevărată în funcție de M și μ dacă există o evaluare μ′ a variabilelor care diferă doar de μ în ceea ce privește evaluarea lui x și astfel încât φ este adevărat în conformitate cu interpretarea M și alocarea variabilei μ′. Această definiție formală surprinde ideea că ∃xϕ(x) este adevărată dacă și numai dacă există o modalitate de a alege o valoare pentru x astfel încât φ(x) să fie satisfăcută.
- Cuantificatori universali. O formulă ∀xϕ(x) este adevărată în funcție de M și μ dacă φ(x) este adevărată pentru fiecare pereche compusă prin interpretarea M și o anumită atribuție variabilă μ′ care diferă de μ doar pe valoarea x. Aceasta surprinde ideea că ∀xϕ(x) este adevărată dacă fiecare alegere posibilă a unei valori pentru x face ca φ(x) să fie adevărată.
Dacă o formulă nu conține variabile libere și, de asemenea, este o propoziție, atunci alocarea variabilei inițiale nu afectează valoarea adevărului. Cu alte cuvinte, o propoziție este adevărată în conformitate cu M și μ dacă și numai dacă este adevărată în conformitate cu M și orice altă atribuire variabilă μ′.
Există o a doua abordare comună pentru definirea valorilor adevărului care nu se bazează pe funcțiile de atribuire variabile. În schimb, având în vedere o interpretare M, mai întâi se adaugă la semnătură o colecție de simboluri constante, una pentru fiecare element al domeniului discursului din M; spune că pentru fiecare d din domeniu simbolul constant cd este fixat. Interpretarea este extinsă astfel încât fiecare nou simbol constant să fie atribuit elementului său corespunzător din domeniu. Acum se definește adevărul pentru formulele cuantificate sintactic, după cum urmează:
- Cuantificatori existențiali (alternativi). O formulă ∃xϕ(x) este adevărată conform lui M dacă există un anumit d în domeniul discursului, astfel încât ϕ(cd) este valabil. Aici ϕ(cd) este rezultatul substituirii cd pentru fiecare apariție liberă a lui x în φ.
- Cuantificatori universali (alternativi). O formulă ∀xϕ(x) este adevărată conform M dacă, pentru fiecare d din domeniul discursului, ϕ(cd) este adevărat conform lui M.
Această abordare alternativă oferă exact aceleași valori de adevăr tuturor propozițiilor ca și abordarea prin atribuții variabile.
Valabilitate, satisfabilitate și consecință logică
Dacă o sentință φ evaluează „Adevărat”, după o interpretare dată M, se spune că M satisface φ; aceasta se notează M⊨φ. O propoziție este satisfăcătoare dacă există o anumită interpretare sub care este adevărată.
Satisfiabilitatea formulelor cu variabile libere este mai complicată, deoarece o interpretare pe cont propriu nu determină valoarea de adevăr a unei astfel de formule. Cea mai comună convenție este aceea că se spune că o formulă cu variabile libere este satisfăcută de o interpretare dacă formula rămâne adevărată indiferent de indivizii din domeniul discursului care sunt repartizați variabilelor sale libere. Aceasta are același efect ca afirmarea că o formulă este satisfăcută dacă și numai dacă închiderea sa universală este satisfăcută.
O formulă este validă logic (sau pur și simplu validă) dacă este adevărată în fiecare interpretare. Aceste formule joacă un rol similar cu tautologiile din logica propozițională.
O formulă φ este o consecință logică a unei formule ψ dacă fiecare interpretare care face ψ adevărată face și φ adevărată. În acest caz, se spune că φ este implicat logic de ψ.
Algebrizare
O abordare alternativă la semantica logicii de ordinul întâi se realizează prin algebră abstractă. Această abordare generalizează algebrele Lindenbaum – Tarski ale logicii propoziționale. Există trei moduri de eliminare a variabilelor cuantificate din logica de prim ordin care nu implică înlocuirea cuantificatorilor cu alți operatori de termeni de legare a variabilelor:
- Algebră cilindrică, de Alfred Tarski și colegii săi;
- Algebra poliadică, de Paul Halmos;
- Logica functorilor predicatelor, în principal datorită lui Willard Quine.
Aceste algebre sunt toate grile care extind în mod corespunzător algebra booleană cu două elemente.
Tarski și Givant (1987) au arătat că fragmentul logicii de prim ordin care nu are o propoziție atomică care se află în sfera de aplicare a mai mult de trei cuantificatori are aceeași putere expresivă ca și algebra relației. Acest fragment prezintă un mare interes pentru că este suficient pentru aritmetica Peano și cea mai axiomatică teorie a seturilor, incluzând ZFC-ul canonic. De asemenea, ei dovedesc că logica de prim ordin cu o pereche ordonată primitivă este echivalentă cu o algebră de relație cu două funcții de proiecție a perechilor ordonate.
Teorii, modele și clase elementare de prim ordin
O teorie de prim ordin pentru o anumită semnătură este un ansamblu de axiome, care sunt propoziții constând din simboluri din semnătura respectivă. Ansamblul de axiome este adesea finit sau recursiv enumerabil, caz în care teoria se numește eficientă. Unii autori impun ca teoriile să includă și toate consecințele logice ale axiomelor. Axiomele sunt considerate a fi valabile în interiorul teoriei și din ele pot fi derivate alte sentințe care sunt valabile în cadrul teoriei.
Se spune că o structură de prim ordin care satisface toate propozițiile dintr-o teorie dată este un model al teoriei. O clasă elementară este ansamblul tuturor structurilor care satisfac o anumită teorie. Aceste clase sunt un subiect principal de studiu în teoria modelelor.
Multe teorii au o interpretare intenționată, un anumit model de care se ține cont atunci când studiați teoria. De exemplu, interpretarea intenționată a aritmeticii Peano constă din numerele naturale obișnuite cu operațiile lor obișnuite. Cu toate acestea, teorema Löwenheim-Skolem arată că majoritatea teoriilor de prim ordin vor avea și alte modele non-standard.
O teorie este consistentă dacă nu este posibil să se dovedească o contradicție din axiomele teoriei. O teorie este completă dacă, pentru fiecare formulă din semnătura sa, fie acea formulă, fie negația ei este o consecință logică a axiomelor teoriei. Teorema incompletitudinii lui Gödel arată că teoriile efective de prim ordin care includ o parte suficientă a teoriei numerelor naturale nu pot fi niciodată simultan consistente și complete.
Domenii goale
Definiția de mai sus necesită ca domeniul discursului oricărei interpretări să fie non-gol. Există setări, cum ar fi logica incluzivă, unde domeniile goale sunt permise. Mai mult, dacă o clasă de structuri algebrice include o structură goală (de exemplu, există un poset gol), acea clasă poate fi doar o clasă elementară în logica de prim ordin dacă sunt permise domenii goale sau structura goală este eliminată din clasă .
Cu toate acestea, există mai multe dificultăți cu domeniile goale:
- Multe reguli comune de inferență sunt valabile numai atunci când domeniul discursului este obligat să fie non-gol. Un exemplu este regula care afirmă că ϕ ∨ ∃ x ψ implică ∃ x (ϕ ∨ ψ) când x nu este o variabilă liberă în ϕ. Această regulă, care este folosită pentru a pune formule în formă prenex normală, este corectă în domeniile non-goale, dar este incorectă dacă este permis domeniul gol.
- Definiția adevărului într-o interpretare care utilizează o funcție de atribuire variabilă nu poate funcționa cu domenii goale, deoarece nu există funcții de atribuire variabile al căror interval este gol. (În mod similar, nu se pot atribui interpretări la simboluri constante.) Această definiție a adevărului necesită că trebuie să se selecteze o funcție de atribuire a variabilelor (μ de mai sus) înainte de a putea fi definite valori de adevăr pentru chiar formule atomice. Apoi, valoarea de adevăr a unei propoziții este definită a fi valoarea ei de adevăr sub orice atribuire variabilă și se dovedește că această valoare de adevăr nu depinde de ce atribuire este aleasă. Această tehnică nu funcționează dacă nu există deloc funcții de atribuire; acesta trebuie schimbat pentru a permite domenii goale.
Astfel, atunci când domeniul gol este permis, acesta trebuie adesea tratat ca un caz special. Cu toate acestea, cei mai mulți autori exclud pur și simplu domeniul gol prin definiție.
Lasă un răspuns