Logica de ordinul întâi

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 iunie 2021; verificările necesită 2 modificări .

Logica de ordinul întâi este un calcul formal care permite declarații despre variabile , funcții fixe și predicate . Extinde logica propozițională .

Pe lângă logica de ordinul întâi, există și logici de ordin superior , în care cuantificatorii pot fi aplicați nu numai variabilelor, ci și predicatelor. Termenii logica predicatelor și calculul predicatului pot însemna atât logica de ordinul întâi, cât și logica de ordinul întâi și logica de ordin superior împreună; în primul caz, se vorbește uneori de logica predicată pură sau de calcul predicat pur .

Definiții de bază

Limbajul logicii de ordinul întâi este construit pe baza unei semnături constând dintr-un set de simboluri de funcțieși un set de simboluri predicate. Fiecare funcție și simbol predicat are asociată o aritate , adică numărul de argumente posibile. Sunt permise atât simbolurile funcționale, cât și simbolurile predicate ale arității 0. Primele sunt uneori separate într-un set separat de constante . În plus, sunt utilizate următoarele caractere suplimentare: ${\mathcal {F}}$ ${\mathcal {P}}$

simboluri variabile (de obicei , , , , , , , , etc.); $X$ $y$ $z$ $x_{1}$ $y_1$ $z_{1}$ $x_{2}$ $y_2$ $z_{2}$
operatii logice:

Simbol	Sens
$\neg$	negativ (nu)
$\teren$	Conjuncție („și”)
$\lor$	Disjuncție ("sau")
$\la$	Implicație ("dacă..., atunci...")

cuantificatori :

Simbol	Sens
$\pentru toți$	Cuantificator universal
$\există$	Cuantificator de existență

caractere de serviciu: paranteze și virgulă .

Simbolurile enumerate împreună cu simbolurile din și formează alfabetul logicii de ordinul întâi . Construcțiile mai complexe sunt definite inductiv . ${\mathcal {P}}$ ${\mathcal {F}}$

Un termen este un simbol al unei variabile sau are forma , unde este un simbol funcțional al arității și sunt termeni. $f(t_{1},\ldots,t_{n})$ $f$ $n$ $t_{1},\ldots ,t_{n}$
Un atom (formula atomică) are forma , unde este simbolul de aritate predicat și sunt termeni. $p(t_{1},\ldots,t_{n})$ $p$ $n$ $t_{1},\ldots ,t_{n}$
- De exemplu, aceasta este o formulă atomică care este adevărată pentru orice număr real . Formula constă dintr-un predicat 2-ari , ale cărui argumente sunt termeni și 0. În același timp, termenul este format din constanta 1 (care poate fi considerată o funcție 0-ary), o variabilă și simboluri binar (2). -ary) funcțiile + și ×. $(x+1)\times (x+1)\geqslant 0$ $X$ $\geqslant$ $(x+1)\times (x+1)$ $(x+1)\times (x+1)$ $X$
O formulă este fie un atom, fie una dintre următoarele construcții: , , , , , , unde sunt funcții și este o variabilă. $\neg F$ $F_{1}\lor F_{2}$ $F_{1}\land F_{2}$ $F_{1}\la F_{2}$ $\forall xF$ $\există xF$ $F,F_{1},F_{2)$ $X$

O variabilă se numește legată într-o formulă dacă are forma fie , fie este reprezentabilă într-una dintre formele , , , , și este deja legată în , și . Dacă nu este legat în , se numește liber în . O formulă fără variabile libere se numește formulă închisă sau propoziție . O teorie de ordinul întâi este orice set de propoziții. $X$ $F$ $F$ $\forall xG$ $\există xG$ $\neg H$ $F_{1}\lor F_{2}$ $F_{1}\land F_{2}$ $F_{1}\la F_{2}$ $X$ $H$ $F_{1}$ $F_{2}$ $X$ $F$ $F$

Axiomatică și demonstrarea formulelor

Sistemul de axiome logice ale logicii de ordinul întâi constă din axiomele calculului propozițional completate de două noi axiome:

$\forall xA\to A[t/x]$ ,
$A[t/x]\to \exists xA$ ,

unde este formula obţinută prin înlocuirea termenului pentru fiecare variabilă liberă care apare în formula . $A[t/x]$ $t$ $X$ $A$

Logica de ordinul întâi folosește două reguli de inferență:

Modus ponens (această regulă este folosită și în logica propozițională): ${\frac {A,A\la B}{B}}$
Regula de generalizare : ${\frac {A}{\forall xA}}$

Interpretare

În cazul clasic, interpretarea formulelor logice de ordinul întâi este dată pe modelul de ordinul întâi , care este determinat de următoarele date:

Set de transport , $\mathcal{D}$
Afișarea funcției semantice $\sigma$
- fiecare simbol al funcției -ary de la la funcția -ary , $n$ $f$ ${\mathcal {F}}$ $n$ $\sigma (f)\colon \,{\mathcal {D}}\times \ldots \times {\mathcal {D}}\rightarrow {\mathcal {D}}$
- fiecare simbol predicat -ary de la relația -ary . $n$ $p$ ${\mathcal {P}}$ $n$ $\sigma (p)\subseteq {\mathcal {D}}\times \ldots \times {\mathcal {D}}$

De obicei se acceptă identificarea setului purtător și a modelului în sine, implicând o funcție semantică implicită, dacă aceasta nu duce la ambiguitate. $\mathcal{D}$

Să presupunem că este o funcție care mapează fiecare variabilă cu un element din , pe care îl vom numi substituție . Interpretarea termenului on cu privire la substituție este dată inductiv : $s$ $\mathcal{D}$ $[\![t]\!]_{s}$ $t$ $\mathcal{D}$ $s$

$[\![x]\!]_{s}=s(x)$ , dacă este o variabilă, $X$
$[\![f(x_1,\ldots,x_n)]\!]_s = \sigma(f)([\!\![\,x_1]\!]_s,\ldots,[\![x_n]\ !]_s)$

În același spirit, se definește relația de adevăr al formulelor pe relativ : $\modele_{s}$ $\mathcal{D}$ $s$

${\mathcal {D}}\modele _{s}p(t_{1},\ldots ,t_{n})$ , dacă și numai dacă , $\sigma(p)([\!\![\,t_1]\!]_s,\ldots,[\![t_n]\!]_s)$
${\mathcal {D}}\modele _{s}\neg \phi$ , dacă și numai dacă - este fals, ${\mathcal {D}}\modele _{s}\phi$
${\mathcal {D}}\models _{s}\phi \land \psi$ , dacă și numai dacă și sunt adevărate, ${\mathcal {D}}\modele _{s}\phi$ ${\mathcal {D}}\modele _{s}\psi$
${\mathcal {D}}\models _{s}\phi \lor \psi$ , dacă și numai dacă sau este adevărat, ${\mathcal {D}}\modele _{s}\phi$ ${\mathcal {D}}\modele _{s}\psi$
${\mathcal {D}}\modele _{s}\phi \to \psi$ , dacă și numai dacă , ${\mathcal {D}}\modele _{s}\phi$ ${\mathcal {D}}\modele _{s}\psi$
${\mathcal {D}}\modele _{s}\există x\,\phi$ , dacă și numai dacă, pentru o substituție , care diferă doar de valoarea variabilei , ${\mathcal {D}}\modele _{{s'}}\phi$ $s'$ $s$ $X$
${\mathcal {D}}\modele _{s}\forall x\,\phi$ , dacă și numai dacă pentru toate substituțiile , care diferă doar de valoarea variabilei . ${\mathcal {D}}\modele _{{s'}}\phi$ $s'$ $s$ $X$

Formula este adevărată pe (care se notează ca ) dacă pentru toate permutările . O formulă se numește validă (care se notează ca ) dacă pentru toate modelele . O formulă se numește satisfăcătoare dacă pentru cel puțin un . $\phi$ $\mathcal{D}$ ${\mathcal {D}}\modele \phi$ ${\mathcal {D}}\modele _{s}\phi$ $s$ $\phi$ $\modele \phi$ ${\mathcal {D}}\modele \phi$ $\mathcal{D}$ $\phi$ ${\mathcal {D}}\modele \phi$ $\mathcal{D}$

Proprietăți și rezultate principale

Logica de ordinul întâi are o serie de proprietăți utile care o fac foarte atractivă ca instrument de bază pentru formalizarea matematicii . Principalele sunt:

completitudine (asta înseamnă că pentru orice formulă închisă, fie ea însăși, fie negația ei este derivabilă);
consistență (nici o formulă nu poate fi derivată simultan cu negația ei).

Mai mult, dacă consistența este mai mult sau mai puțin evidentă, atunci completitudinea este un rezultat non-trivial obținut de Gödel în 1930 ( teorema completității lui Gödel ). În esență, teorema lui Gödel stabilește o echivalență fundamentală între conceptele de demonstrabilitate și validitate .

Logica de ordinul întâi are proprietatea de compactitate , demonstrată de Maltsev : dacă un set de formule nu este fezabil, atunci unele dintre submulțimile sale finite nu sunt, de asemenea, fezabile.

Conform teoremei Löwenheim-Skolem, dacă un set de formule are un model, atunci are și un model de cardinalitate cel mult numărabilă . Legat de această teoremă este paradoxul lui Skolem , care, totuși, este doar un paradox imaginar .

Logica de ordinul întâi cu egalitate

Multe teorii de ordinul întâi implică simbolul egalității. Este adesea menționată ca simboluri ale logicii și completată de axiomele corespunzătoare care o definesc. O astfel de logică se numește logică de ordinul întâi cu egalitate , iar teoriile corespunzătoare sunt numite teorii de ordinul întâi cu egalitate . Semnul egal este introdus ca simbol de predicat binar . Axiomele suplimentare introduse pentru acesta sunt următoarele: $=$

$\forall x(x=x)$
$\forall x\forall y(x=y)\to (F(x)\to F(y))$

Utilizare

Logica de ordinul întâi ca model de raționament formal

Fiind un analog oficial al logicii obișnuite , logica de ordinul întâi face posibilă raționarea strictă a adevărului și falsității enunțurilor și a relației lor, în special despre consecința logică a unei afirmații din alta sau, de exemplu, despre echivalența lor. . Luați în considerare un exemplu clasic de formalizare a declarațiilor de limbaj natural în logica de ordinul întâi .

Să luăm raționamentul „Orice om este muritor. Socrate este un om. Prin urmare, Socrate este muritor .” Să notăm „x este bărbat” prin MAN (x) și „x este muritor” prin MERTEN (x). Atunci afirmația „fiecare persoană este muritoare” poate fi reprezentată prin formula: x( OM (x) → MOARTE (x)) afirmația „Socrate este un om” prin formula OM ( Socrate ), iar „Socrate este muritor” prin formula MOARTE ( Socrate ). Declarația în ansamblu poate fi acum scrisă ca $\pentru toți$

( x( OM (x) → MOARTE (x)) OM ( Socrate )) → MOARTE ( Socrate )

\pentru toți

\land

Vezi și

Literatură

Gilbert D., Akkerman V. Fundamentele logicii teoretice. M., 1947
Kleene S.K. Introducere în metamatematică. M., 1957
V. I. Markin. Logica predicatelor // New Philosophical Encyclopedia : în 4 volume / prev. științific-ed. sfatul lui V. S. Stepin . — Ed. a II-a, corectată. si suplimentare - M . : Gândirea , 2010. - 2816 p.
Mendelson E. Introducere în logica matematică. M., 1976
Novikov PS Elemente de logică matematică. M., 1959
Biserica A. Introducere în logica matematică, vol. I. M. 1960

Dicționare și enciclopedii	Rusă mare Britannica (online) Universalis

Logici

Filosofie • Semantică • Sintaxă • Istorie

Grupuri logice

logica clasica	logica aristotelică Logica propozițională Logica de ordinul întâi Logica de ordinul doi logica de ordin superior
logica matematica	teoria multimilor Teoria modelului Teoria computabilității Teoria dovezilor și matematică constructivă Logica liniară sistem formal concluzie firească Calcul de secvență Algebra logicii Logica relevanta Logica deontică logica intuiționistă calculul Lambek
Logica non-clasica	intuitionism logica fuzzy Logica substructurala logica Logica descrierii Logica cu mai multe valori Sinteza logica Logica obligatorie Logica temporală Logica modală ( logica hibridă ) logica epistemică
Logica filozofică	Gândire critică logica informala motiv dedus

Componente

Lista simbolurilor booleene