Limbajul de prima ordine

În logica matematică, limbajul de prima ordine este un limbaj formal care servește la gestionarea mecanică a enunțurilor și raționamentelor care implică conectivități logice , relații și cuantificatori „pentru fiecare ...” (∀) și „există ...” (∃). Expresia „prima ordine” indică faptul că există un set de referință și cuantificatorii pot viza doar elementele acelui set și nu subseturile ; de exemplu, putem spune "pentru toate elementele x ale setului este P (x)", dar nu putem spune "pentru toate subseturile A este P (A)" (teoriile în care există cuantificatori care variază pe subseturi de ' setul de referință se spune în locul ordinului al doilea ).

Motivație

În limbajul logicii propoziționale este posibil să se formalizeze argumente care implică cuantificatori numai în cazurile în care mulțimea în care este „cuantificată” este finită, de exemplu prin traducerea enunțului „pentru fiecare x $P^{1}$ ${\ displaystyle P ^ {1}}$ ${\ displaystyle P ^ {1}}$ (x) „ca $P^{1}(a_{1})\land P^{1}(a_{2})\land \ldots \land P^{1}(a_{n})$ ${\ displaystyle P ^ {1} (a_ {1}) \ land P ^ {1} (a_ {2}) \ land \ ldots \ land P ^ {1} (a_ {n})}$ ${\ displaystyle P ^ {1} (a_ {1}) \ land P ^ {1} (a_ {2}) \ land \ ldots \ land P ^ {1} (a_ {n})}$ de sine $a_{1},a_{2},\ldots ,a_{n}$ ${\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n}}$ ${\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n}}$ denotați toate elementele mulțimii în care se cuantifică. Când trebuie să cuantificați pe mulțimi cu un număr nedefinit de elemente sau pe mulțimi infinite (așa cum se întâmplă dacă declarați o teoremă aritmetică precum „fiecare număr întreg admite o singură factorizare”), logica propozițională nu mai este în măsură să servească scopului.

Ideea din spatele conceptului de limbaj de ordinul întâi este de a integra limbajul logicii propoziționale cu simboluri pentru cuantificatori, variabile care pot fi „cuantificate” și simboluri care reprezintă predicate și funcții, adică posibile proprietăți sau relații între variabile.

Definiție

Un limbaj de prim ordin se caracterizează prin:

un alfabet de simboluri (fie că sunt simboluri care reprezintă variabile, constante, predicate, funcții, conectivități, cuantificatoare sau punctuație);
un set de termeni (care denotă „obiectele” setului luat în considerare);
un set de formule bine formate (sau mai pe scurt wffs sau pur și simplu „formule”) care este un set de șiruri compuse din simboluri ale alfabetului care sunt considerate corecte din punct de vedere sintactic .

Alfabet

Alfabetul unei limbi de ordinul întâi include:

simboluri pentru variabile : $x_{1},x_{2},x_{3},\ldots$ ${\ displaystyle x_ {1}, x_ {2}, x_ {3}, \ ldots}$ ${\ displaystyle x_ {1}, x_ {2}, x_ {3}, \ ldots}$ ;
simboluri pentru constante individuale : $a_{1},a_{2},\ldots$ ${\ displaystyle a_ {1}, a_ {2}, \ ldots}$ ${\ displaystyle a_ {1}, a_ {2}, \ ldots}$ ;
simboluri pentru predicate (sau relații ), fiecare dintre acestea fiind asociat cu numărul său de argumente: $P^{1},Q^{1},P^{2},Q^{2},\ldots$ ${\ displaystyle P ^ {1}, Q ^ {1}, P ^ {2}, Q ^ {2}, \ ldots}$ ${\ displaystyle P ^ {1}, Q ^ {1}, P ^ {2}, Q ^ {2}, \ ldots}$ ;
simboluri pentru funcții , fiecare dintre ele fiind asociat cu un număr corespunzător numărului de argumente: $f^{1},g^{1},f^{2},g^{2},\ldots$ ${\ displaystyle f ^ {1}, g ^ {1}, f ^ {2}, g ^ {2}, \ ldots}$ ${\ displaystyle f ^ {1}, g ^ {1}, f ^ {2}, g ^ {2}, \ ldots}$ ;
simboluri auxiliare: "(", ")" și virgula ",";
simboluri pentru conectivități logice: $\neg$ ${\ displaystyle \ neg}$ $\ neg$ ( negare ), $\rightarrow$ ${\ displaystyle \ rightarrow}$ $\ sageata dreapta$ ( implicație ), $\leftrightarrow$ ${\ displaystyle \ leftrightarrow}$ $\ leftrightarrow$ ( dacă și numai dacă ), $\land$ ${\ displaystyle \ land}$ $\ teren$ ( conjuncție ), $\lor$ ${\ displaystyle \ lor}$ $\ lor$ ( disjuncție );
simboluri pentru cuantificatori: ∀ ( cuantificator universal ), ∃ ( cuantificator existențial ).

Fiecare funcție și simbol predicat este notat printr-o aritate . Indică numărul de argumente sau obiecte cărora li se aplică funcția sau predicatul. Constantele pot fi considerate funcții ale ariei 0 ^[1] .

Un exemplu de alfabet este cel al limbajului aritmetic de ordinul întâi care conține două simboluri pentru funcții cu 2 argumente, $+,\times$ ${\ displaystyle +, \ times}$ $+, \ ori$ , un simbol pentru o relație cu doi subiecți, $=$ ${\ displaystyle =}$ $=$ , un simbol pentru constanta individuală, 0 și un simbol pentru funcția unui singur argument, $S.$ ${\ displaystyle S}$ $S.$ , funcția succesorală. O propoziție pe alfabetul aritmeticii de ordinul întâi este, de exemplu: $S(S(0))\times S(0)=S(S(0))$ ${\ displaystyle S (S (0)) \ times S (0) = S (S (0))}$ ${\ displaystyle S (S (0)) \ times S (0) = S (S (0))}$ .

Termeni

Setul de termeni al limbajului constă din setul minim de șiruri ale alfabetului care poate desemna obiecte specifice, formal fiind dată următoarea definiție inductivă:

o constantă individuală este un termen;
o variabilă este un termen;
de sine $t_{1},\ldots ,t_{n}$ ${\ displaystyle t_ {1}, \ ldots, t_ {n}}$ ${\ displaystyle t_ {1}, \ ldots, t_ {n}}$ Sunt $n$ ${\ displaystyle n}$ $n$ termeni și $f^{n}$ ${\ displaystyle f ^ {n}}$ $f ^ {n}$ este un simbol funcțional $n$ ${\ displaystyle n}$ $n$ -air de limbaj, atunci $f^{n}(t_{1},\ldots ,t_{n})$ ${\ displaystyle f ^ {n} (t_ {1}, \ ldots, t_ {n})}$ ${\ displaystyle f ^ {n} (t_ {1}, \ ldots, t_ {n})}$ este un termen;
nimic altceva nu este un termen.

Exemple de termeni pot fi obținuți aplicând regulile în mod iterativ, deci termeni precum

$a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ (regula 1);
$x_{1}$ ${\ displaystyle x_ {1}}$ $x_1$ (regula 2);
$f^{2}(a_{1},x_{1})$ ${\ displaystyle f ^ {2} (a_ {1}, x_ {1})}$ ${\ displaystyle f ^ {2} (a_ {1}, x_ {1})}$ de sine $f^{2}$ ${\ displaystyle f ^ {2}}$ $f ^ {2}$ este un simbol pentru funcția binară (regula 3);
$f^{1}(f^{2}(a_{1},x_{1}))$ ${\ displaystyle f ^ {1} (f ^ {2} (a_ {1}, x_ {1}))}$ ${\ displaystyle f ^ {1} (f ^ {2} (a_ {1}, x_ {1}))}$ de sine $f^{1}$ ${\ displaystyle f ^ {1}}$ ${\ displaystyle f ^ {1}}$ este un simbol pentru funcția unară (regula 3).

Formule bine formate

Setul de formule bine formate (sau pe scurt fbf ) este format din secvențele de simboluri ale alfabetului cu care am dori să reprezentăm propoziții corecte din punct de vedere sintactic. În mod formal, un wff este definit astfel:

Pentru un limbaj dat de prima ordine, setul de formule bine formate este setul minim astfel încât:

orice formulă atomică $A^{n}(t_{1},\ldots ,t_{n})$ ${\ displaystyle A ^ {n} (t_ {1}, \ ldots, t_ {n})}$ ${\ displaystyle A ^ {n} (t_ {1}, \ ldots, t_ {n})}$ este un wff , unde $A^{n}$ ${\ displaystyle A ^ {n}}$ $A ^ n$ este un simbol pentru predicat $n$ ${\ displaystyle n}$ $n$ -ario și $t_{1},\ldots ,t_{n}$ ${\ displaystyle t_ {1}, \ ldots, t_ {n}}$ ${\ displaystyle t_ {1}, \ ldots, t_ {n}}$ sunt termeni
de sine $LA$ {\ displaystyle {\ mathcal {A}}} ${\ mathcal A}$ Și $B.$ {\ displaystyle {\ mathcal {B}}} ${\ mathcal B}$ sunt fbf și $X$ {\ displaystyle x} $X$ este o variabilă, atunci sunt și wffs
- $\bot$ ${\ displaystyle \ bot}$ $\ bot$
- $\neg {\mathcal {A}}$ ${\ displaystyle \ neg {\ mathcal {A}}}$ $\ neg {\ mathcal A}$
- ${\mathcal {A}}\rightarrow {\mathcal {B}}$ ${\ displaystyle {\ mathcal {A}} \ rightarrow {\ mathcal {B}}}$ ${\ mathcal A} \ rightarrow {\ mathcal B}$
- ${\mathcal {A}}\leftrightarrow {\mathcal {B}}$ ${\ displaystyle {\ mathcal {A}} \ leftrightarrow {\ mathcal {B}}}$ ${\ mathcal A} \ leftrightarrow {\ mathcal B}$
- ${\mathcal {A}}\land {\mathcal {B}}$ ${\ displaystyle {\ mathcal {A}} \ land {\ mathcal {B}}}$ ${\ mathcal A} \ land {\ mathcal B}$
- ${\mathcal {A}}\lor {\mathcal {B}}$ ${\ displaystyle {\ mathcal {A}} \ lor {\ mathcal {B}}}$ ${\ mathcal A} \ lor {\ mathcal B}$
- $(\forall x){\mathcal {A}}$ ${\ displaystyle (\ forall x) {\ mathcal {A}}}$ ${\ displaystyle (\ forall x) {\ mathcal {A}}}$
- $(\exists x){\mathcal {A}}$ ${\ displaystyle (\ există x) {\ mathcal {A}}}$ ${\ displaystyle (\ există x) {\ mathcal {A}}}$
toate și numai wff - urile sunt definite de regulile anterioare.

Exemple de formule bine formate în limbajul aritmeticii de prim ordin sunt:

x+y=0,

{\ displaystyle x + y = 0,}

{\ displaystyle x + y = 0,}

\forall z(x+y=0),

{\ displaystyle \ forall z (x + y = 0),}

{\ displaystyle \ forall z (x + y = 0),}

(x=x)\to \forall x(S(x)=S(y)).

{\ displaystyle (x = x) \ to \ forall x (S (x) = S (y)).}

{\ displaystyle (x = x) \ to \ forall x (S (x) = S (y)).}

Pe de altă parte, nu este un wff

(x=x)\to \forall x(S(x)),

{\ displaystyle (x = x) \ to \ forall x (S (x)),}

{\ displaystyle (x = x) \ to \ forall x (S (x)),}

întrucât în limbajul aritmeticii de ordinul întâi $S.$ ${\ displaystyle S}$ $S.$ nu este un simbol prin predicat ci un simbol prin funcție.

Sub-formule, variabile libere și formule închise

O subformulă este un șir din interiorul unui wff care este, de asemenea, un wff .

De exemplu în wff

\forall x(P^{1}(x)\land Q^{1}(y))

{\ displaystyle \ forall x (P ^ {1} (x) \ land Q ^ {1} (y))}

{\ displaystyle \ forall x (P ^ {1} (x) \ land Q ^ {1} (y))}

subformulele sunt

\forall x(P^{1}(x)\land Q^{1}(y))

{\ displaystyle \ forall x (P ^ {1} (x) \ land Q ^ {1} (y))}

{\ displaystyle \ forall x (P ^ {1} (x) \ land Q ^ {1} (y))}

P^{1}(x)\land Q^{1}(y)

{\ displaystyle P ^ {1} (x) \ land Q ^ {1} (y)}

{\ displaystyle P ^ {1} (x) \ land Q ^ {1} (y)}

P^{1}(x)

{\ displaystyle P ^ {1} (x)}

{\ displaystyle P ^ {1} (x)}

Q^{1}(y)

{\ displaystyle Q ^ {1} (y)}

{\ displaystyle Q ^ {1} (y)}

Într-un wff , cuantificatorii apar în mod necesar în fața sub-formulelor și sunt asociați cu o variabilă (cea care apare imediat după simbolul ∀ sau ∃).

O variabilă dintr-o formulă se spune că este liberă dacă nu apare în nici o sub-formulă precedată de un cuantificator asociat cu acea variabilă. Altfel se spune că este legat . În exemplul anterior $X$ ${\ displaystyle x}$ $X$ este legat în timp ce $y$ ${\ displaystyle y}$ $y$ este gratis.

O formulă închisă este un wff care nu conține variabile libere, o formulă deschisă care le conține.

Semantică

Până în prezent, regulile pentru o formare „corectă” a enunțurilor unui limbaj de ordinul întâi ( wffs ) au fost date fără a lua în considerare ce au însemnat acestea. Pentru a atribui semnificație formulelor lingvistice, este necesar să indicați:

un set de referință $U$ ${\ displaystyle U}$ $U$ ( universul discursului ) căruia îi aparțin „obiectele” despre care vorbim (notate prin constantele individuale) și în care variază cuantificatoarele ;
pentru fiecare $n$ ${\ displaystyle n}$ $n$ un set de funcții din $U^{n}$ ${\ displaystyle U ^ {n}}$ $U ^ {n}$ în $U$ ${\ displaystyle U}$ $U$ pentru a fi asociat cu fiecare simbol al funcției $n$ ${\ displaystyle n}$ $n$ -air de limbaj;
pentru fiecare $n$ ${\ displaystyle n}$ $n$ un set de relații $n$ ${\ displaystyle n}$ $n$ -air pe $U$ ${\ displaystyle U}$ $U$ să fie asociat cu fiecare simbol al relației $n$ ${\ displaystyle n}$ $n$ -aria limbajului;

colecția acestor seturi împreună cu asocierea fiecărui element la propriul său „simbol” identifică ceea ce se numește model pentru limbă.

Un model permite asocierea univocă a unui element al universului discurs fiecărui termen închis (adică fără variabile libere ) și o valoare de adevăr fiecărui wff.

Notă

^ Asperti și Ciabattoni , p. 100.

Bibliografie

Andrea Asperti și Agata Ciabattoni, 4. Logica predicatelor , în Logică către informatică , McGraw-Hill, 1997.

Elemente conexe

linkuri externe

( EN ) Limba de primul ordin , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Asperti și Ciabattoni , p. 100.

[1]