Lògica de primer ordre

La lògica de primer ordre, també anomenada lògica de predicats o càlcul de predicats, és un sistema formal dissenyat per estudiar la inferència en els llenguatges de primer ordre.^[1] Els llenguatges de primer ordre són, al seu torn, llenguatges amb quantificador que arriben només a variables d'individu, i amb funcions els arguments de les quals són només constants o variables d'individu.^[2]

La lògica de primer ordre té el poder expressiu suficient per a definir pràcticament totes les matemàtiques.

Com el desenvolupament històric i les aplicacions de la lògica de primer ordre estan molt lligats a la matemàtica, en el que segueix es farà una introducció que contempli i il·lustri aquesta relació, prenent exemples tant de la matemàtica com del llenguatge natural. Primer s'introdueixen cada un dels conceptes bàsics del sistema, i després es mostra com utilitzar-los per analitzar arguments.

Un predicat és una expressió lingüística que pot connectar amb una o diverses altres expressions per a formar una oració.^[3] Per exemple, en l'oració "Mart és un planeta ", l'expressió" és un planeta "és un predicat que es connecta amb l'expressió" Mart "per a formar una oració. I en l'oració "Júpiter és més gran que Mart", l'expressió "és més gran que" és un predicat que es connecta amb dues expressions, "Júpiter" i "Mart", per a formar una oració.

Quan un predicat es connecta amb una sola expressió, es diu que expressa una propietat (la propietat de ser un planeta), i quan es connecta amb dos o més expressions, es diu que expressa una relació (la relació de ser més gran que). La lògica de primer ordre no fa cap supòsit, però, sobre si existeixen o no les propietats o les relacions. Només s'ocupa d'estudiar la manera com parlem i raonem amb expressions lingüístiques.

A la lògica de primer ordre, els predicats són tractats com a funcions. Una funció és, metafòricament parlant, una màquina que rep un conjunt de coses, les processa i retorna com a resultat una única cosa. A les coses que entren a les funcions se les anomena arguments,^{[nota 1]} i les coses que surten, valors o imatges. Considerem per exemple la següent funció matemàtica:

f (x)=2 x

Aquesta funció pren nombres com a arguments i torna més nombres com a valors. Per exemple, si pren el nombre 1, retorna el nombre 2, i si pren el 5, torna el 10. A la lògica de primer ordre, es proposa tractar els predicats com a funcions que no només prenen nombres com a arguments, sinó expressions com "Mart", "Mercuri" i altres que es veuran més endavant. D'aquesta manera, l'oració "Mart és un planeta" pot transcriure, seguint la notació pròpia de les funcions, de la següent manera:

Planeta ( Mart )

O, més abreujadament:

P (m)

A la matemàtica hi ha més funcions que prenen diversos arguments. Per exemple:

f (x, i)=x+i

Aquesta funció, si pren els nombre 1 i 2, torna el nombre 3, i si pren el -5 i el -3, torna el -8. Seguint aquesta idea, la lògica de primer ordre tracta els predicats que expressen relacions, com a funcions que prenen dues o més arguments. Per exemple, l'oració "Caín matà Abel" pot formalitzar així:

Matà ( Caín , Abel )

O abreujant:

m (c, a)

Aquest procediment es pot estendre per tractar amb predicats que expressen relacions entre moltes entitats. Per exemple, l'oració "Anna està asseguda entre Bruno i Carlos" es pot formalitzar:

S (a, b, c)

Una constant d'individu és una expressió lingüística que fa a una entitat. Per exemple "Mart", "Júpiter", "Caín" i "Abel" són constants d'individu. També ho són les expressions "1", "2", etc., Que fan referència a nombres. Una entitat no ha d'existir perquè es pugui parlar sobre ella, de manera que la lògica de primer ordre tampoc fa supòsits sobre l'existència o no de les entitats a les que fan referència les seves constants d'individu.

A més de les constants d'individu que fan referència a entitats determinades, la lògica de primer ordre compta amb altres expressions, les variables , la referència no està determinada. La seva funció és similar a la de les expressions del llenguatge natural com "ell", "ella", "això", "això" i "allò", el referent varia amb el context. Les variables generalment es representen amb lletres minúscules a prop del final de l'alfabet llatí, principalment la x, i i z . De la mateixa manera, en la matemàtica, l'x en la funció f (x)=2 x no representa cap nombre en particular, sinó que és una cosa així com un espai buit on poden inserir diferents nombres. En conclusió, podem representar una expressió com "això és antic" amb l'expressió:

Antic (x)

O abreujadament:

a (x)

És evident, però, que fins que no es determini a què refereix la x, no és possible assignar un valor de veritat a l'expressió "això és antic", de la mateixa manera que fins que no es determini un nombre per a la x en la funció f (x)=2 x, no serà possible calcular cap valor per a la funció.

Per descomptat, igual que amb les constants d'individu, les variables serveixen també per a formalitzar relacions. Per exemple, l'oració "això és més gran que allò" es formalitza:

G (x, i)

I també poden combinar-constants d'individu amb variables. Per exemple en l'oració "ella està asseguda entre Bruno i Carlos":

S (x, b, c)

Considerem ara la següent expressió matemàtica:

x> 3

Aquesta expressió no és ni vertadera ni falsa, i sembla que no ho serà fins que no reemplaça a l’x per algun nombre qualsevol. No obstant això, també és possible donar un valor de veritat a l'expressió si se li anteposa un quantificador. Un quantificador és una expressió que afirma que una condició es compleix per a un cert nombre d'individus.^[4] En la lògica clàssica, els dos quantificadors més estudiats són el quantificador universal i el quantificador existencial.^[4] El primer afirma que una condició es compleix per tots els individus dels que es parla,^[4] i el segon que es compleix per almenys un dels individus.^[4] Per exemple, l'expressió "per a tot x" és un quantificador universal, que anteposat a "x <3 ", produeix:

Per a tot x, x <3

Aquesta és una expressió amb valor de veritat, en particular, una expressió falsa, ja que hi ha molts nombres (molts x) que són grans que tres. Anteposant en canvi l'expressió "per almenys un x", un quantificador existencial, s'obté:

Per a mínim un x, x <3

La qual resulta ser una expressió veritable.

Cal advertir ara, però, que el valor de veritat de les dues expressions anteriors depèn de quins nombres s'estigui parlant. Si quan s'afirma "per a tot x, x <3", s'està parlant només dels nombres negatius , llavors l'afirmació és vertadera. I si en afirmar "per almenys un x, x <3" s'està parlant només dels nombres 3, 4 i 5, llavors l'afirmació és falsa. En lògica, a allò del que s'està parlant quan es fa servir algun quantificador, se l'anomena domini de quantificació.^[5]

Aquesta maquinària pot adaptar fàcilment per formalitzar oracions amb quantificadors del llenguatge natural. Preneu-vos per cas l'afirmació "tots són amigables". Aquest predicat es pot traduir així:

Per a tot x, x és amigable.

I una oració com "algú està mentint" es pot traduir:

Per a mínim un x, x està mentint.

També és freqüent traduir aquesta última oració així:

Hi ha almenys un x, tal que x està mentint.

A continuació es formalitzen les dues oracions, introduint alhora la notació especial per als quantificadors:

Per a tot x, x és amigable.	${\displaystyle \forall x\ A(x)}$
Hi ha almenys un x, tal que x està mentint.	${\displaystyle \exists x\ M(x)}$

La lògica de primer ordre incorpora a més les connectives de la lògica proposicional. Combinant les connectives amb els predicats, constants, variables i quantificadors, és possible formalitzar oracions com les següents:

Predicat	Formalització
Sòcrates és savi i prudent.	${\displaystyle Ss\land Ps}$
Si Sòcrates és savi, aleshores també és prudent.	${\displaystyle Ss\to Ps}$
Ningú no és savi i més prudent.	${\displaystyle \neg \exists x(Sx\land Px)}$
Tots els savis són prudents.	${\displaystyle \forall x(Sx\to Px)}$

Considereu el següent argument clàssic:

1. Tots els homes són mortals.
2. Sòcrates és un home.
3. Per tant, Sòcrates és mortal.

La tasca de la lògica de primer ordre consisteix a determinar per què els arguments com aquest són vàlids. Per això, el primer pas és traduir a un llenguatge més precís, que pugui ser analitzat mitjançant mètodes formals. Segons el vist més amunt, la formalització d'aquest argument és la següent:

1. ${\displaystyle \forall x(Hx\to Mx)}$
2. ${\displaystyle Hs\,}$
3. ${\displaystyle \therefore Ms}$

El càlcul de predicats consisteix en

• Regles de formació (una definició recursiva del conjunt de les fórmules).
• Un conjunt finit de regles d'inferència.
• Un conjunt (possiblement infinit numerable) d'axiomes o esquemes axiomàtics.

Els axiomes considerats aquí són els axiomes lògics dels quals són part del càlcul de predicats. Més endavant s'agreguen axiomes no-lògics en teories de primer ordre específiques: no es consideren veritats de la lògica però sí veritats d'una teoria particular.

Quan el conjunt d'axiomes és infinit, es requereix un algorisme que pugui decidir per una fórmula ben formada si és un axioma o no. Encara més, hauria d'existir un algorisme que pugui decidir si l'aplicació d'una regla d'inferència és correcta o no.

És important notar que el càlcul de predicats pot ser formalitzat de diverses formes diferents. No hi ha res canònic sobre els axiomes i regles d'inferència aquí donades, però qualsevol formalització produeix els mateixos teoremes de la lògica (i deduir els mateixos teoremes de qualsevol conjunt d'axiomes no-lògics).

L'alfabet d'un sistema Q de lògica de predicats de primer ordre sense identitat consta dels següents símbols:

• Un conjunt finit però arbitràriament gran de constants d'individu: ${\displaystyle \{a,b,c,d,...\}\,}$
• Un conjunt finit però arbitràriament gran de variables: ${\displaystyle \{x,y,z,x_{1},x_{2},y_{9},...\}\,}$
• Un conjunt finit però arbitràriament gran de funcions: ${\displaystyle \{f,g,o,l,b,...\}\,}$
• Un conjunt finit però arbitràriament gran de lletres de predicat: ${\displaystyle \{P,A,S,N,...\}\,}$
• El conjunt de connectives lògiques heretades de la lògica proposicional: ${\displaystyle \{\neg ,\land ,\lor ,\to ,\Leftrightarrow \}}$
• El conjunt de quantificador és: ${\displaystyle \{\forall ,\exists \}}$
• Els parèntesis esquerre i dret: ${\displaystyle \{(,)\}\,}$

Algunes observacions respecte a l'anterior:

• La igualtat de vegades es considera part de la lògica de primer ordre. En aquest cas, el símbol d'igualtat s'inclou en el vocabulari i es comporta sintàcticament com un predicat binari. Aquest cas es diu de vegades lògica de primer ordre amb igualtat.
• Les constants en realitat són funcions d'aritat 0, de manera que és possible ometre les constants i permetre a les funcions tenir qualsevol aritat. No obstant això, tradicionalment es fa servir el terme "funció" només per a funcions d'aritat més gran o igual a 1.
• En la definició anterior les relacions ha de tenir aritat més gran o igual que 1. És possible permetre relacions d'aritat 0; aquestes podrien ser considerades com a variables proposicionals.
• Hi ha diferents convencions sobre on posar els parèntesis, per exemple, una podria ser? x o (? x). De vegades es fan servir dos punts (:) o punt (.) En lloc de barres inclinades per desambiguar fórmules. Una notació interessant però poc usual és la notació polonesa, on s'ometen tots els parèntesis, i s'escriu?,?, Davant dels arguments en comptes d'entre ells. La notació polonesa és compacta però poc comú per ser difícil per a ser llegida pels humans.
• Una observació tècnica és que si hi ha un símbol de funció d'aritat 2 representant el parell ordenat (o símbol de predicat d'aritat 2 representant la relació) no es necessiten funcions i predicats d'aritat més gran que 2.

Normalment es considera que el conjunt de constants, funcions i relacions formen un llenguatge, mentre que les variables, els operadors lògics i quantificadors se'ls considera pertanyents a la lògica. Per exemple, el llenguatge de la teoria de grups consisteix d'una constant (l'element identitat), una funció d'aritat 1 (al revés), una funció d'aritat 2 (el producte), i una relació d'aritat 2 (la igualtat), omesa pels autors que inclouen la igualtat en la lògica subjacent.

La gramàtica defineix les fórmules ben formades de Q de la següent manera:

Primer es defineix la noció de terme:

1. Qualsevol constant és un terme.
2. Qualsevol variable és un terme.
3. Qualsevol expressió ${\displaystyle f(t_{1},...,t_{n})\,}$, on ${\displaystyle f\,}$ és un símbol de funció d'aritat ${\displaystyle n\geq 1}$, i ${\displaystyle (t_{1},...,t_{n})\,}$ és una seqüència d’N termes, és un terme.
4. Cap altra cosa és un terme.

Després es defineix recursivament el conjunt de les fórmules ben formades de Q a través de les següents regles:

1. Si ${\displaystyle P\,}$ és una lletra de predicat d'aritat ${\displaystyle n\geq 1}$, i ${\displaystyle (t_{1},...,t_{n})\,}$ és una seqüència d’N termes, llavors ${\displaystyle P(t_{1},...,t_{n})\,}$ és una fórmula ben formada de Q. A aquestes fórmules se les anomena fórmules atòmiques de Q. Es diu variables lliures a totes les variables que apareguin entre els termes. Algunes fórmules atòmiques ben formades són:

${\displaystyle P(a),G(x),R(a,b),S(x,y,a),T(a,f(c)),D(s,g(x,i),e)\,}$
Per simplificar la lectura i l'escriptura, però, quan no hi ha cap símbol de funció involucrat, generalment s'ometen els parèntesis i s'escriu:
${\displaystyle Pa,GX,Rab,Sxya\,}$

1. Si ${\displaystyle \phi \,}$ és una fórmula ben formada de Q, llavors ${\displaystyle \neg \phi \,}$ també ho és. Les seves variables lliures són les variables lliures de ${\displaystyle \phi \,}$.
2. Si ${\displaystyle \phi \,}$ i ${\displaystyle \psi \,}$ són fórmules ben formades de Q, llavors ${\displaystyle (\phi \land \psi )}$, ${\displaystyle (\phi \lor \psi )}$, ${\displaystyle (\phi \to \psi )}$ i ${\displaystyle (\phi \Leftrightarrow \psi )}$ també ho són. Les seves variables lliures són les variables lliures de ${\displaystyle \phi \,}$ o ${\displaystyle \psi \,}$.
3. Si ${\displaystyle \phi \,}$ és una fórmula ben formada de Q, llavors ${\displaystyle \forall x(\phi )\,}$ i ${\displaystyle \exists x(\phi )\,}$ també ho són, es pot usar qualsevol altra variable en lloc de x. Les seves variables lliures són les variables lliures de ${\displaystyle \phi \,}$ diferents de x. A qualsevol instància de x (o una altra variable reemplaçant x en aquesta construcció) se l'anomena lligada (no lliure) a ${\displaystyle \forall x(\phi )\,}$ i ${\displaystyle \exists x(\phi )\,}$.
4. Només les expressions que poden ser generades mitjançant les clàusules 1 a 4 en un nombre finit de passos són fórmules ben formades de Q.

Segons aquesta gramàtica, alguns exemples de fórmules ben formades (no atòmiques) són:

${\displaystyle \forall x(Px),\forall x(Da),\exists i(Ryyy),\forall x(\exists i(Gyaxbc)),\exists x(Bx\land Nxo),\forall x(Pxs\to \exists i(Kxyo\land \forall z(Rxyz)))}$

I alguns exemples de fórmules mal formades són:

${\displaystyle x,a,P,xat,\forall ,\exists x,\exists \forall x(Bx),\exists xy(Statin)}$

Quan no hi ha risc de confusió, és normal ometre certs parèntesi per simplificar la lectura i l'escriptura. Per exemple:

${\displaystyle \forall x\ Px}$ en comptes de ${\displaystyle \forall x(Px)}$

${\displaystyle \forall x\forall y\exists z(Px\to Ryz)}$ en comptes de ${\displaystyle \forall x(\forall i(\exists z(Px\to Ryz)))}$

Per certes relacions molt utilitzades d'aritat 2, generalment s'escriu a R b en comptes de N (a, b). Per exemple, 2> 1 en lloc de> (2,1), i 4=4 en lloc de=(4,4). Anàlogament, si f és un símbol de funció d'aritat 2, de vegades s'escriu AFB en comptes de f (a, b). Per exemple, 1+2 en comptes de+(1, 2).

Les nocions de variable lliure i variable lligada s'introdueixen per evitar un possible error en el procés de substitució. Suposem per un moment la fórmula ${\displaystyle \forall x(x\leq i)}$. Intuïtivament, aquesta fórmula diu que per a tot x, x és menor o igual que i (és a dir, que i és màxim). En aquesta fórmula, i és una variable lliure, o sigui que no està sota l'abast de cap quantificador. Si es substituïx i per qualsevol altre terme t, llavors la fórmula passarà a dir que t és màxim. Però suposem ara que substituïm a i per x mateix (al cap i a la fi, x és un terme). En aquest cas, i passa a estar lligada per un quantificador universal, perquè la nova fórmula és: ${\displaystyle \forall x(x\leq x)}$. Però aquesta fórmula ja no diu d'un terme que és màxim, sinó una cosa molt diferent. Per evitar aquest tipus de desplaçament de significat, convenim que en substituir una variable lliure per un terme qualsevol, cal evitar que les variables lliures en el nou terme quedin lligades per algun quantificador. És a dir, que romanguin lliures.

Dit d'una manera més general, si t és un terme i ${\displaystyle \phi (x)\,}$ és una fórmula que possiblement conté x com una variable lliure, llavors ${\displaystyle \phi (t)\,}$ és el resultat de substituir totes les aparicions lliures de x per t, suposant que cap variable lliure en t es torni lligada en aquest procés . Si alguna variable lliure de t es tornés lligada, llavors per substituir t per x cal canviar els noms de les variables lligades d'${\displaystyle \phi (x)\,}$ per altres que no coincideixin amb les variables lliures de t.

Hi ha diverses maneres diferents d'introduir la noció d'identitat en la lògica de primer ordre, però totes amb essencialment les mateixes conseqüències. Aquesta secció resumeix les principals:

• La manera més comuna d'introduir la identitat és incloent al símbol entre els primitius, i afegint axiomes que defineixin el comportament d'aquest. Aquests són:

${\displaystyle \forall x(x=x)}$

${\displaystyle \forall x\forall y{\bigg (}(x=y)\to \forall f{\Big (}(f(...x...)=f(...i...){\Big )}{\bigg )}}$

${\displaystyle \forall x\forall y{\bigg (}(x=y)\to \forall P{\Big (}(P(...x...)\Leftrightarrow P(...i...){\Big )}{\bigg )}}$

• Una altra manera és incloure al símbol d'identitat com una de les relacions de la teoria i afegir els axiomes d'identitat a la teoria. A la pràctica aquesta convenció és gairebé indistingible de l'anterior, excepte en el cas inusual de les teories sense noció d'identitat. Els axiomes són els mateixos. L'única diferència és que uns s'anomenen axiomes lògics i els altres axiomes de la teoria.
• En les teories sense funcions i amb un nombre finit de relacions, és possible definir la identitat en termes de les relacions. Això es fa definint que dos termes aib són iguals si i només si cap relació presenta canvis reemplaçant a per b en qualsevol argument. Per exemple, en teoria de conjunts amb una relació de pertinença (${\displaystyle \in \,}$), definiríem ${\displaystyle a=b\,}$ com una abreviació per ${\displaystyle \forall x((a\in x)\Leftrightarrow (b\in x))\land ((x\in a)\Leftrightarrow (x\in b))}$ Aquesta definició d'identitat automàticament satisfà els axiomes d'identitat.
• En algunes teories és possible donar definicions ad hoc per a la identitat. Per exemple, en una teoria d'ordres parcials amb una relació de menor o igual (${\displaystyle \leq \,}$) podríem definir ${\displaystyle a=b\,}$ com una abreviació per ${\displaystyle (a\leq b)\land (b\leq a)}$

La lògica de primer ordre té dues regles d'inferència. La primera és el modus ponens, heretada de la lògica proposicional. La segona és la regla de Generalització universal , que és característica de la lògica de primer ordre. La mateixa diu:

${\displaystyle {\frac {\vdash \phi }{\vdash \forall x(\phi )}}}$

És a dir, si ${\displaystyle \phi \,}$ és un teorema, llavors ${\displaystyle \forall x(\phi )}$ també ho és.

Noteu que la regla de generalització universal és anàloga a la regla de Necesitación de la lògica modal.

Els següents quatre axiomes lògics caracteritzen un càlcul de predicats:

• ${\displaystyle (\forall x\ \phi (x))\to \phi (a)}$
• ${\displaystyle \phi (a)\to (\exists x\ \phi (x))}$
• ${\displaystyle (\forall x\ \psi \to \phi (x))\to (\psi \to \forall x\ \phi (x))}$
• ${\displaystyle (\forall x\ \phi (x)\to \psi )\to (\exists x\ \phi (x)\to \psi )}$

Per tal de poder caracteritzar problemes en les classes de complexitat computacional més conegudes, se sol afegir poder d'expressió a la lògica de primer ordre utilitzant quantificadors generalitzats o Lindström.

Existeixen diversos sistemes lògics que generalitzen la lògica de primer ordre ${\displaystyle {\mathcal {L}}_{I}}$ i als quals són aplicables els teoremes de Lindström són aplicables que classifiquen lògiques que inclouen:

• La lògica de segon ordre completa (LSOC)${\displaystyle {\mathcal {L}}_{II}}$
• La lògica de segon ordre feble ${\displaystyle {\mathcal {L}}_{II}^{w}}$
• La lògica de primer ordre infinitària ${\displaystyle {\mathcal {L}}_{\omega _{1}\omega }}$
• La lògica de primer amb quantificador no-numerable${\displaystyle {\mathcal {L}}_{Q}}$

Totes aquestes lògiques condueixen a sistemes lògics regulars i poden ser ordenades segons la seva fortalesa lògica:

${\displaystyle {\mathcal {L}}_{I}\leq {\mathcal {L}}_{II}^{w}\leq {\mathcal {L}}_{\omega _{1}\omega },\quad {\mathcal {L}}_{II}^{w}\leq {\mathcal {L}}_{II}}$

• Lògica
• Càlcul lògic