Sintaxa în logica predicatelor (logica de ordinul întâi)

Există două părți-cheie ale logicii de ordinul întâi. Sintaxa determină ce colecții de simboluri sunt expresii legale, în timp ce semantica determină semnificațiile din spatele acestor expresii.

Alfabetul

Spre deosebire de limbile naturale, cum ar fi limba engleză, limba logicii de ordinul întâi este complet formală, astfel încât să poată fi determinată mecanic dacă o expresie dată este legală. Există două tipuri cheie de expresii legale: termeni, care reprezintă intuitiv obiecte, și formule, care exprimă intuitiv predicate care pot fi adevărate sau false. Termenii și formulele logicii de ordinul întâi sunt șiruri de simboluri, unde toate simbolurile formează împreună alfabetul limbii. Ca și în cazul tuturor limbilor formale, natura simbolurilor în sine este în afara scopului logicii formale; ele sunt adesea considerate pur și simplu litere și simboluri de punctuație.

Este comună împărțirea simbolurilor alfabetului în simboluri logice, care au întotdeauna același înțeles, și simboluri non-logice, a căror semnificație variază prin interpretare. De exemplu, simbolul logic ∧ reprezintă întotdeauna „și”; nu este niciodată interpretată ca „sau”. Pe de altă parte, un simbol predicat non-logic precum Phil(x) ar putea fi interpretat ca însemnând „x este un filozof”, „x este un om pe nume Philip” sau orice alt predicat unar, în funcție de interpretarea la îndemână .

Simboluri logice

Există mai multe simboluri logice în alfabet, care variază în funcție de autor, dar de obicei includ:

• Simbolurile cuantificatoare ∀ și ∃
• Conexiunile logice: ∧ pentru conjuncție, ∨ pentru disjuncție, → pentru implicare, ↔ pentru bicondițional, ¬ pentru negare. Ocazional sunt incluse și alte simboluri logice logice. Unii autori utilizează Cpq, în loc de →, și Epq, în loc de ↔, în special în contextul în care → este utilizat în alte scopuri. În plus, simbolul ⊃ poate înlocui →; bara triplă ≡ poate înlocui ↔; tilda (~) pe Np, sau Fpq poate înlocui ¬; ||, sau Apq poate înlocui ∨; și &, Kpq sau punctul de mijloc, ·, poate înlocui ∧, mai ales dacă aceste simboluri nu sunt disponibile din motive tehnice. (Notă: simbolurile menționate anterior Cpq, Epq, Np, Apq și Kpq sunt folosite în special în notația poloneză.)
• Parantezele i alte simboluri de punctuație. Alegerea acestor simboluri variază în funcție de context.
• Un set infinit de variabile, deseori marcat cu litere mici de la sfârșitul alfabetului x, y, z, …. Subscripturile sunt adesea folosite pentru a distinge variabilele: x₀, x₁, x₂, ….
• Un simbol al egalității (uneori, simbolul identității) =.

Nu sunt necesare toate aceste simboluri – este suficient doar unul dintre cuantificatori, negare și conjuncție, variabile, paranteze și egalitate. Există numeroase variații minore care pot defini simboluri logice suplimentare:

• Uneori sunt incluse constantele de adevăr T, Vpq sau ┬, pentru „adevărat” și F, Opq, sau ┴ pentru „fals”. Fără astfel de operatori logici de valență 0, aceste două constante pot fi exprimate doar cu ajutorul unor cuantificatori.
• Uneori sunt incluse conexiuni logice suplimentare, cum ar fi disjuncția, Dpq (NAND) și sau exclusiv, Jpq.

Simboluri non-logice

Simbolurile non-logice reprezintă predicatele (relațiile), funcțiile și constantele din domeniul discursului. A fost o practică standard pentru a utiliza un set fix, infinit de simboluri non-logice pentru toate scopurile. O practică mai recentă este să folosim diferite simboluri non-logice în funcție de aplicația pe care o avem în vedere. Prin urmare, a devenit necesară numirea setului de simboluri non-logice utilizate într-o anumită aplicație. Această alegere se face printr-o semnătură.

Abordarea tradițională este de a avea un set infinit de simboluri non-logice (o semnătură) pentru toate aplicațiile. În consecință, în abordarea tradițională există doar un limbaj al logicii de ordinul întâi. Această abordare este încă comună, mai ales în cărțile orientate filosofic.

• Pentru fiecare întreg n ≥ 0 există o colecție de simboluri n–ary, sau simboluri predicate n–place. Deoarece reprezintă relațiile dintre n elemente, ele sunt numite și simboluri de relație. Pentru fiecare aritate n avem o cantitate infinită de ele:Pⁿ₀, Pⁿ₁, Pⁿ₂, Pⁿ₃, …
• Pentru fiecare număr întreg n ≥ 0 există infinit de multe simboluri funcție n-ary:f ⁿ₀, f ⁿ₁, f ⁿ₂, f ⁿ₃, …

În logica matematică contemporană, semnătura variază în funcție de aplicație. Semnăturile tipice din matematică sunt {1, ×} sau doar {×} pentru grupuri sau {0, 1, +, ×, <} pentru câmpurile ordonate. Nu există restricții asupra numărului de simboluri non-logice. Semnătura poate fi goală, finită sau infinită, chiar nesemnificativă. Semnăturile nesemnificative apar, de exemplu, în dovezile moderne ale teoremei Löwenheim-Skolem.

În această abordare, fiecare simbol non-logic este unul dintre următoarele tipuri.

1. Un simbol predicat (sau simbol relație) cu o anumită valență (sau aritate, număr de argumente) mai mare sau egal cu 0. Acestea sunt deseori marcate cu majuscule P, Q, R, ….
   • Relațiile valenței 0 pot fi identificate cu variabile propoziționale. De exemplu, P, care poate suporta orice declarație.
   • De exemplu, P(x) este o variabilă predicată a valenței 1. O interpretare posibilă este „x este un om”.
   • Q (x,y) este o variabilă predicată a valenței. 2. Interpretările posibile includ „x este mai mare decât y” și „x este tatăl y”.
2. Un simbol funcție, cu o valență mai mare sau egală cu 0. Acestea sunt adesea indicate cu litere mici, f, g, h, ….
   • Exemple: f(x) poate fi interpretat ca și pentru „tatăl lui x„. În aritmetică, poate fi valabil pentru „-x„. În teoria seturilor, aceasta poate reprezenta „setul de putere al lui x„. În aritmetică, g(x,y) poate reprezenta „x+y„. În teoria seturilor, ea poate reprezenta „unirea lui x și y”.
   • Simbolurile funcție ale valenței 0 sunt numite simboluri constante și adesea sunt marcate cu litere mici de la începutul alfabetului a, b, c, …. Simbolul a poate fi valabil pentru Socrates. În aritmetică, poate fi 0. Pentru teoria seturilor, o astfel de constantă poate reprezenta setul gol.

Abordarea tradițională poate fi recuperată în abordarea modernă prin specificarea pur și simplu a semnăturii „personalizate” care constă în secvențele tradiționale de simboluri non-logice.

Regulile formării

Regulile de formare definesc termenii și formulele logicii de ordinul întâi. Atunci când termenii și formulele sunt reprezentate ca șiruri de simboluri, aceste reguli pot fi folosite pentru a scrie o gramatică formală pentru termeni și formule. Aceste reguli sunt în general fără context (fiecare producție are un singur simbol în partea stângă), cu excepția faptului că setul de simboluri poate fi permis să fie infinit și pot exista multe simboluri de pornire, de exemplu variabilele în cazul termenilor.

Termeni

Setul de termeni este definit inductiv prin următoarele reguli:

1. Variabile. Orice variabilă este un termen.
2. Funcții. Orice expresie f(t₁,…,t_n) de n argumente (unde fiecare argument t_i este un termen și f este un simbol funcțional de valență n) este un termen. În special, simbolurile care denotă constantele individuale sunt simboluri nulare ale funcțiilor și sunt astfel termeni.

Doar expresiile care pot fi obținute prin numeroase aplicații finite ale regulilor 1 și 2 sunt termeni. De exemplu, nicio expresie care implică un simbol predicat nu este un termen.

Formule

Setul de formule (denumite și formule bine formate sau WFF) este definit inductiv prin următoarele reguli:

1. Simboluri predicate. Dacă P este un simbol predicat n-ary și t₁, …, t_n sunt termeni atunci P(t₁,…,t_n) este o formulă.
2. Egalitate. Dacă simbolul egalității este considerat parte a logicii și t1 și t2 sunt termeni, atunci t₁ = t₂ este o formulă.
3. Negare. Dacă φ este o formulă, atunci ¬ φ este o formulă.
4. Conectări binare. Dacă φ și ψ sunt formule, atunci (φ → ψ) este o formulă. Reguli similare se aplică și altor conexiuni logice binare.
5. Cuantificatori. Dacă φ este o formulă și x este o variabilă, atunci ∀xφ (pentru toate x, φ) și ∃xφ (există x astfel încât φ) sunt formule.

Numai expresiile care pot fi obținute prin numeroase aplicații finite ale regulilor 1-5 sunt formule. Formulele obținute din primele două reguli sunt considerate a fi formule atomice.

De exemplu,

∀x∀y(P(f(x)) → ¬ (P(x) → Q(f(y),x,z)))

este o formulă, dacă f este un simbol al funcției unare, P este un simbol predicat unar și Q este un simbol predicat ternar. Pe de altă parte, ∀xx → nu este o formulă, deși este un șir de simboluri din alfabet.

Rolul parantezelor în definiție este acela de a se asigura că orice formulă poate fi obținută într-un singur mod, urmând definiția inductivă (cu alte cuvinte, există un arbore sintactic unic pentru fiecare formulă). Această proprietate este cunoscută ca citirea unică a formulelor. Există multe convenții unde parantezele sunt folosite în formule. De exemplu, unii autori utilizează coloane sau opriri complete în locul parantezelor sau modifică locurile în care sunt inserate paranteze. Definirea particulară a fiecărui autor trebuie să fie însoțită de o dovadă a citirii unice.

Această definiție a unei formule nu susține definirea unei funcții if-then-else ite(c,a,b), unde „c” este o condiție exprimată ca o formulă care ar întoarce „a” dacă c este adevărată și ” b „dacă este falsă. Acest lucru se datorează faptului că atât predicatele, cât și funcțiile pot accepta numai termenii ca parametri, dar primul parametru este o formulă. Unele limbi construite pe prima logică, cum ar fi SMT-LIB 2.0, adaugă acest lucru.

Convenții notaționale

Pentru conveniență, s-au dezvoltat convenții privind prioritatea operatorilor logici, pentru a evita necesitatea de a scrie paranteze în unele cazuri. Aceste reguli sunt similare cu ordinea operațiilor în aritmetică. O convenție comună este:

• ¬ este evaluat mai întâi
• ∧ și ∨ sunt evaluate în continuare
• Cuantificatorii sunt evaluați în continuare
• → este evaluat ultima dată.

În plus, punctuația suplimentară, care nu este impusă de definiție, poate fi inserată pentru a face formulele mai ușor de citit. Astfel formula

¬ ∀ x P (x) → ∃ x ¬ P (x)

poate fi scrisă ca

(¬ [∀ x P (x)]) → ∃ x [¬ P (x)].

În unele domenii, este comună utilizarea notării infix pentru relații binare și funcții, în loc de notația prefix definită mai sus. De exemplu, în aritmetică, se scrie de obicei „2 + 2 = 4” în loc de „= (+ (2,2), 4)”. Este comun să se considere formulele în notația infix ca abrevieri pentru formulele corespunzătoare în notația prefix.

Definițiile de mai sus utilizează notația infix pentru conectorii binari, cum ar fi → . O convenție mai puțin comună este notația poloneză, în care se scrie →, ∧ și așa mai departe în fața argumentelor lor, nu între ele. Această convenție permite eliminarea tuturor simbolurilor de punctuație. Notația poloneză este compactă și elegantă, dar rar utilizată în practică, deoarece este greu pentru oameni să o citească. În notația poloneză, formula

∀x ∀ y (P (f (x)) → ¬ (P (x) → Q (f (y), x, z)))

devine

∀x∀y → Pfx¬ → PxQfyxz

Variabile libere și legate

Într-o formulă, o variabilă poate apărea liberă sau legată (sau ambele). Intuitiv, o ocurență variabilă este liberă într-o formulă dacă nu este cuantificată: în ∀yP(x,y), ocurența unică a variabilei x este liberă în timp ce cea al lui y este legată. Ocurențele variabile libere și legate într-o formulă sunt definite inductiv după cum urmează.

1. Formule atomice. Dacă φ este o formulă atomică atunci x apare liber în φ dacă și numai dacă x apare în φ. Mai mult, nu există variabile obligatorii în nicio formulă atomică.
2. Negare. x apare liber în ¬ φ dacă și numai dacă x apare liber în φ. x apare legat în ¬ φ dacă și numai dacă x apare legat în φ.
3. Conectări binare. x apare liber în (φ → ψ) dacă și numai dacă x apare liber în fie φ sau ψ. x apare legat în (φ → ψ) dacă și numai dacă x apare legat fie în φ fie în ψ. Aceeași regulă se aplică oricăror altor conectări binare în loc de →.
4. Cuantificatori. x apare liber în ∀yφ dacă și numai dacă x apare liber în φ și x este un simbol diferit față de y. De asemenea, x apare legat în ∀yφ dacă și numai dacă x este y sau x apare legat în φ. Aceeași regulă este valabilă pentru ∃.

De exemplu, în ∀x ∀y (P(x) → Q(x,f(x),z)), x apare doar legat, z apare doar liber și w nu este în niciun fel pentru că nu apare în formulă.

Variabilele libere și legate ale unei formule nu trebuie să fie disjuncte: în formula P (x) → ∀xQ(x), prima ocurență a lui x ca argument al lui P, este liberă, în timp ce a doua, ca argument al lui Q, este legată.

O formulă în logica de ordinul întâi, fără ocurențe variabile libere, se numește sentință de ordinul întâi. Acestea sunt formulele care vor avea valori de adevăr bine definite sub o interpretare. De exemplu, dacă o formulă precum Phil(x) este adevărată trebuie să depindă de ceea ce reprezintă x. Dar propoziția ∃xPhil(x) va fi fie adevărată, fie falsă într-o interpretare dată.