Llògica de primer orde

Una llògica de primer orde, també cridada llògica predicativa, llògica de predicats, càlcul de predicats o llògica predicativa de calcule, és un sistema formal dissenyat per a estudiar l'inferència en els llenguages de primer orde. Els llenguages de primer orde són, a la seua volta, llenguages formals en quantificadors que alcancen solament a variables d'individu, i en predicats i funcions els arguments de les quals són solament constants o variables d'individu, lo que garantisa que tota inferència siga computacionalment decidible.

La llògica de primer orde té un poder expressiu superior al del Raonament deductivo.

Introducció

El desenroll històric i les aplicacions de la llògica de primer orde estan molt lligats a la matemàtica. En lo que seguix es farà una introducció que contemple i ilustre esta relació, prenent eixemples tant de la matemàtica com del llenguage natural. Primer s'introduïxen cada u dels conceptes bàsics del sistema, i despuix es mostra cóm utilisar-los per a analisar arguments.

Predicats

Un predicat és una expressió llingüística que es pot conectar en una o vàries atres expressions per a formar una oració. Per eixemple, en l'oració «Mart és un planeta», l'expressió «és un planeta» és un predicat que es conecta en 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 conecta en dos expressions, «Júpiter» i «Mart», per a formar una oració.

En llògica matemàtica, quan un predicat es conecta en una expressió, es diu que expressa una propietat (com la propietat de ser un planeta), i quan es conecta en dos o més expressions, es diu que expressa una relació (com la relació de ser més gran que). No obstant, la llògica de primer orde no fa cap supòsit sobre si existixen o no les propietats o les relacions. Solament s'ocupa d'estudiar el modo en que parlem i raonem en expressions llingüístiques.

En la llògica de primer orde, els predicats són tractats com funcions. Una funció és, metafòricament parlant, una màquina que rep un conjunt de coses, les processa, i torna com resultat una única cosa. A les coses que entren a les funcions li les crida arguments, i a les coses que ixen, valors o imàgens. Considere's per eixemple la següent funció matemàtica:

f(x) = 2x

Esta funció pren números com a arguments i torna més números com a valors. Per eixemple, si pren el número 1, torna el número 2, i si pren el 5, torna el 10. En la llògica de primer orde, es propon tractar als predicats com a funcions que no solament prenen números com a arguments, sino expressions com «Mart», «Mercurio» i unes atres que es voran més alvance. D'esta manera, l'oració «Mart és un planeta» pot transcribirse, seguint la notació pròpia de les funcions, de la següent manera:

Planeta(Mart)

O, més abreviadamente:

P(m)

En la matemàtica existixen ademés funcions que prenen varis arguments. Per eixemple:

f(x,i) = x + i

Esta funció, si pren els números 1 i 2, torna el número 3, i si pren el -5 i el -3, torna el -8. Seguint esta idea, la llògica de primer orde tracta als predicats que expressen relacions, com a funcions que prenen dos o més arguments. Per eixemple, l'oració «Caín va matar a Abel» es pot formalisar aixina:

Va matar(Caín,Abel)

O abreviant:

M(c,a)

Este procediment es pot estendre per a tractar en predicats que expressen relacions entre moltes entitats. Per eixemple, l'oració «Ana està assentada entre Bruno i Carlos» pot formalisar-se:

S(a,b,c)

Constants individuals

Una constant individual és una expressió llingüística que referix a una entitat. Per eixemple «Mart», «Júpiter», «Caín» i «Abel» són constants d'individu. També ho són les expressions «1», «2», etc., que referixen a números. Una entitat no té que existir per a que es puga parlar sobre ella, de modo que la llògica de primer orde tampoc fa suposts sobre l'existència o no de les entitats a les que referixen els seus constants individuals.

Variables individuals

Ademés de les constants individuals que fan referència a entitats determinades, la llògica de primer orde conta en atres expressions, les variables, la referència de les quals no està determinada. La seua funció és similar a la de les expressions del llenguage natural com «ell», «ella», «açò», «això» i «allò», el referent del qual varia en el context. Les variables generalment es representen en lletres minúscules prop del final de l'alfabet llatí, principalment la x, i i z. De la mateixa manera, en la matemàtica, la x en la funció f(x) = 2x no representa cap número en particular, sino que és alguna cosa aixina com un espai buit a on es poden insertar distints números. En conclusió, podem representar una expressió com «açò és antic» en l'expressió:

Antic(x)

O abreviadamente:

A(x)

És evident, no obstant, que fins que no es determine a qué referix la x, no és possible assignar un valor de veres a l'expressió «açò és antic», de la mateixa manera que fins que no es determine un número per a la x en la funció f(x) = 2x, no serà possible calcular cap valor per a la funció.

Per supost, de la mateixa manera que en les constants individuals, les variables servixen també per a formalisar relacions. Per eixemple, l'oració «açò és més gran que allò» es formalisa:

G(x,i)

I també es poden combinar constants individuals en variables. Per eixemple en l'oració «ella està assentada entre Bruno i Carlos»:

S(x,b,c)

Quantificadors

Considere's ara la següent expressió matemàtica:

x > 3

Esta expressió no és ni verdadera ni falsa, i sembla que no ho serà fins que no reemplacem a la x per algun número qualsevol. No obstant, també és possible donar un valor de veres a l'expressió si se li antepon un quantificador. Un quantificador és un operador sobre un conjunt d'individus, es tracta d'un recurs expressiu que permet construir proposicions sobre conjunts o dit d'una atra forma, un quantificador és una expressió que afirma que una condició es complix per a un cert número d'individus. En la llògica clàssica, els dos quantificadors més estudiats són el quantificador universal i el quantificador existencial. El primer afirma que una condició es complix per a tots els individus dels que s'està parlant, i el segon que es complix per a a lo manco un dels individus. Per eixemple, l'expressió "per a tot x" és un quantificador universal, que antepost a "x < 3", produïx:

Per a tot x, x < 3

Esta és una expressió en valor de veres, en particular, una expressió falsa, puix existixen molts números (molts x) que són majors que tres. Anteponent en canvi l'expressió "per a a lo manco un x", un quantificador existencial, s'obté:

Per a a lo manco un x, x < 3

La qual resulta ser una expressió verdadera.

Advertixca's ara, no obstant, que el valor de veres de les dos expressions anteriors depén de quins números s'estiga parlant. Si quan s'afirma "per a tot x, x < 3", s'està parlant solament dels números negatius, per eixemple, llavors l'afirmació és verdadera. I si en afirmar "per a a lo manco un x, x < 3" s'està parlant solament dels números 3, 4 i 5, llavors l'afirmació és falsa. En llògica, a allò de lo que s'està parlant quan s'usa algun quantificador, li'l crida el domini de discurs.

Esta maquinària es pot adaptar fàcilment per a formalisar oracions en quantificadors del llenguage natural. Prenga's per cas l'afirmació "tots són amigables". Esta oració es pot traduir aixina:

Per a tot x, x és amigable.

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

Per a a lo manco un x, x està mentint.

També és freqüent traduir esta última oració aixina:

Existix a lo manco un x, tal que x està mentint.

A continuació es formalisen abdós oracions, introduint al mateix temps la notació especial per als quantificadors:

Per a tot x, x és amigable.	∀x A(x)
Existix a lo manco un x, tal que x està mentint.	∃x M(x)

Conectivas

Artícul principal → Llògica proposicional.

La llògica de primer orde incorpora ademés les conectivas de la llògica proposicional. Combinant les conectivas en els predicats, constants, variables i quantificadors, és possible formalisar oracions com les següents:

Oració	Formalisació
Sócrates és sapient i prudent.	Ss ∧ Ps
Si Sócrates és sapient, llavors també és prudent.	Ss → Ps
Ningú és sapient i ademés prudent.	¬∃x (Sx ∧ Px)
Tots els sabio són prudents.	∀x (Sx → Px)

Arguments

Considere's el següent argument clàssic:

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

La tasca de la llògica de primer orde consistix en determinar per qué els arguments com a est resulten vàlits. Per a això, el primer pas és traduir-los a un llenguage més precís, que puga ser analisat per mig de métodos formals. Segons lo vist més dalt, la formalisació d'este argument és la següent:

1. ∀x (Hx → Mx)
2. Hs
3. ∴ Ms

Sistema formal

A continuació es definix un llenguage formal, Q, i despuix es definixen axiomas i regles d'inferència sobre eixe llenguage que donen com resultat el sistema llògic SQ.

Sintaxis

L'alfabet del llenguage formal Q consta dels següents símbols:

a   x   f   P   *   '   ¬   ∧   ∨   →   ↔   ∀   ∃   (   )

A partir d'estos símbols, es definixen les següents nocions:

Un nom (o constant individual) és una a seguida d'una o més comillas. Per eixemple, a', a'' i a'''''' són noms. Per a facilitar la llectura, se solen ometre les comillas i utilisar distintes lletres prop del començ del alfabet llatí, en o sense subíndexs, per a distinguir noms distints: a, b, c, d, i, a₁, a₃, c₉, etc.

Una variable (o variable individual) és una x seguida d'una o més comillas. Per eixemple, x', x'' i x'''''' són variables. Per a facilitar la llectura, se solen ometre les comillas i utilisar distintes lletres prop del final de l'alfabet llatí, en o sense subíndexs, per a distinguir variables distintes: x, i, z, x₁, x₃, z₉, etc.

Un functor és una f seguida d'un o més asteriscs, i despuix d'una o més comillas. Per eixemple, f *', f **'''' i f ****'' són functores. El número d'asteriscs indica l'aridad del functor. Per a facilitar la llectura, se solen ometre els asteriscs i les comillas i utilisar distintes lletres de l'alfabet llatí prop de la f, en o sense subíndexs, per a distinguir functores distints: f, g, h, f₁, f₃, h₉, etc.

Un predicat és una P seguida d'un o més asteriscs, i despuix d'una o més comillas. Per eixemple, P *', P **'''' i P ****'' són predicats. El número d'asteriscs indica l'aridad del predicat. Per a facilitar la llectura, se solen ometre els asteriscs i les comillas i utilisar distintes lletres en mayúscula a lo llarc de l'alfabet llatí per a distinguir predicats distints: P, A, B, C, S, T, etc.

La noció de terme es definix recursivamente per mig de les següents clàusules:

1. Tots els noms són térmens.
2. Totes les variables són térmens.
3. Si f és un functor de aridad n ≥ 1 i t₁,...,t_n són térmens, llavors f(t₁,...,t_n) és un terme.
4. Res més és un terme.

Segons esta definició, les següents cadenes de caràcters són térmens:

Cadena	Simplificació	Possible interpretació
a'	a	Aristóteles
x'''''	i
f *'''(a''')	h(c)	El germà de Caín
f *''(f *''(f *''(a')))	f(f(f(b)))	El pare del pare del pare de Beatriz

I en canvi, les següents cadenes de caràcters no són térmens:

Cadena	Error
a	Falten comillas.
x*'''	Sobra l'asterisc.
f '	Falten asteriscs i arguments.
f **	Falten comillas i arguments.
f *'(f *')	Falta l'argument del functor més anidado.
f *'(a',a'')	El functor és de aridad 1 pero té dos arguments.

La noció de fòrmula ben formada de Q es definix per mig de les següents clàusules:

1. Si P és un predicat de aridad n ≥ 1 i t₁,...,t_n són térmens, llavors P(t₁,...,t_n) és una fòrmula ben formada.
2. Si A és una fòrmula ben formada, llavors ¬A també ho és.
3. Si A i B són fòrmules ben formades, llavors (A ∧ B), (A ∨ B), (A → B) i (A ↔ B) també ho són.
4. Si A és una fòrmula ben formada i x és una variable, llavors ∀x A i ∃x A són fòrmules ben formades.
5. Res més és una fòrmula ben formada.

Segons esta definició, les següents cadenes de caràcters són fòrmules ben formades:

Cadena	Simplificació	Possible interpretació
P *'(a')	Pa	Abel és pastor.
P **''''(a'',a''')	Aae	Abelardo ama a Eloísa.
¬P *'(f *'(a'))	¬P(h(a))	El germà d'Abel no és pastor.
(P *'''(a'') → ¬P *'''''(a''))	Pv → ¬Ev	Si Venus és un planeta, llavors no és una estrela.
∀x'' P *'''(x'')	∀x Mx	Tots són bolers.
∀x'' ∃x'''' P **'(x'',x'''')	∀x ∃i Axy	Tots amen a algú.
∃x'' ∀x'''' P **'(x'',x'''')	∃x ∀i Axy	Algú ama a tots.

I en canvi, les següents cadenes de caràcters no són fòrmules ben formades:

Cadena	Error
P *'	El predicat és de aridad 1 pero no té arguments.
P ***'(a')	El predicat és de aridad 3 pero té un sol argument.
P *'(a') → P *'(a''')	Falten els paréntesis externs.
(P *'(a'))	Sobren els paréntesis externs.
∀a' P *'(a')	El quantificador està seguit d'un nom en lloc d'una variable.

Per a certs predicats molt utilisats, la notació estàndar pot tindre la forma a R b en lloc de R(a,b). Per eixemple, s'escriu 2 > 1 en lloc de >(2,1), i 4 = 4 en lloc de =(4,4). Análogamente, si f és un functor de aridad 2, a voltes s'escriu a f b en lloc de f(a,b). Per eixemple, s'escriu 1 + 2 en lloc de +(1,2).

Observacions

• El símbol d'identitat a voltes s'inclou entre els símbols primitius de l'alfabet i es comporta sintácticamente com un predicat binari. A una llògica de primer orde que inclou el símbol d'identitat li la crida, justament, llògica de primer orde en identitat.
• Els noms poden ser definits com functores de aridad 0, de modo que és possible ometre la a d'entre els símbols primitius.
• En la definició anterior es requerix que els predicats tinguen aridad major o igual que 1. És possible permetre predicats de aridad 0, considerant-los com a variables proposicionals de la llògica proposicional.

• És possible reduir el número de símbols primitius fins a quedar-se en sol nou: x   f   P   *   '   ↓   ∀   (   )
• Hi ha diferents convencions sobre on posar els paréntesis. Per eixemple, alguns escriuen (∀x) en lloc de ∀x. A voltes s'usen dos punts (:) o un punt (.) en lloc de paréntesis per a desambiguar fòrmules. Una notació interessant pero poc usual és la notació polaca, a on s'ometen tots els paréntesis i s'escriu ∧, ∨, davant dels arguments en lloc d'entre ells. La notació polaca és compacta pero poc comuna per ser difícil per a ser llegida pels humans.
• Una observació tècnica és que si existix un símbol de funció de aridad 2 representant el parell ordenat (o símbol de predicat de aridad 2 representant la relació) no es necessiten funcions i predicats de aridad major que 2.
• Usualment es considera que el conjunt de constants, funcions i relacions formen un llenguage, mentres que les variables, els operadors llògics i quantificadors li'ls considera pertanyents a la llògica. Per eixemple, el llenguage de la teoria de grups consistix d'una constant (l'element identitat), una funció de aridad 1 (l'inversa), una funció de aridad 2 (el producte), i una relació de aridad 2 (l'igualtat), omesa pels autors que inclouen l'igualtat en la llògica subjacent.

Substitució de variables lliures

Les nocions de variable lliure i variable lligada s'introduïxen per a evitar un possible error en el procés de substitució. Supongam per un moment la fòrmula $\mathrm{\forall }x(x\le y)$. Intuitivamente, esta fòrmula diu que para tot x, x és menor o igual que i (és dir, que i és màxim). En esta fòrmula, i és una variable lliure, o siga que no està baix l'alcanç de cap quantificador. Si substituimos i per qualsevol atre terme t, llavors la fòrmula passarà a dir que t és màxim. Pero supongam ara que substituimos a i per x mateixa (a fi de contes, x és un terme). En eixe cas, i passa a estar lligada per un quantificador universal, perque la nova fòrmula és: $\mathrm{\forall }x(x\le x)$. Pero esta fòrmula ya no diu d'un terme que és màxim, sino alguna cosa molt distint. Per a evitar este tipo de desplaçament de significat, convenim que al substituir una variable lliure per un terme qualsevol, cal evitar que les variables lliures en el nou terme queden lligades per algun quantificador. És dir, que permaneixquen lliures.

Dit d'una manera més general, si t és un terme i $\varphi (x)$ és una fòrmula que possiblement conté a x com una variable lliure, llavors $\varphi (t)$ és el resultat de substituir totes les aparicions lliures de x per t, suponent que cap variable lliure en t es torne lligada en este procés. Si alguna variable lliure de t es tornara lligada, llavors per a substituir t per x es necessita canviar els noms de les variables lligades de $\varphi (x)$ per uns atres que no coincidixquen en les variables lliures de t.

Identitat

Hi ha vàries maneres diferents d'introduir la noció d'identitat en la llògica de primer orde, pero totes són essencialment les mateixes conseqüències. Esta secció resumix les principals:

• La manera més comuna d'introduir a l'identitat és incloent al símbol entre els primitius, i agregant axioma que definixquen el comportament del mateix. Estos són:

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

$\mathrm{\forall }x\mathrm{\forall }y((x=y)\to \mathrm{\forall }f((f(\mathrm{...}x\mathrm{...})=f(\mathrm{...}y\mathrm{...})))$

$\mathrm{\forall }x\mathrm{\forall }y((x=y)\to \mathrm{\forall }P((P(\mathrm{...}x\mathrm{...})\leftrightarrow P(\mathrm{...}y\mathrm{...})))$

• Una atra manera és incloure al símbol d'identitat com una de les relacions de la teoria i agregar els axioma d'identitat a la teoria. En la pràctica esta convenció és casi indistinguible de l'anterior, llevat en el cas inusual de les teories sense noció d'identitat. Els axioma són els mateixos. L'única diferència és que uns es diuen axioma llògics i els atres axioma de la teoria.

• En les teories sense funcions i en un número finit de relacions, és possible definir l'identitat en térmens de les relacions. Açò es fa definint que dos térmens a i b són iguals si i solament si cap relació presenta canvis reemplaçant a per b en qualsevol argument. Per eixemple, en teoria de conjunts en una relació de pertinença (∈), definiríem a = b com un abreujament per a ∀x [(a ∈ x) ↔ (b ∈ x)] ∧ [(x ∈ a) ↔ (x ∈ b)]. Esta definició d'identitat automàticament satisfà els axioma d'identitat.
• En algunes teories és possible donar definicions ad hoc per a l'identitat. Per eixemple, en una teoria d'órdens parcials en una relació de menor o igual (&li;) podríem definir a = b com un abreujament per a (a &li; b) ∧ (b &li; a).

Regles d'inferència

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

$\begin{array}{c}A\\ \mathrm{\forall }xA\end{array}$

O en la notació del càlcul de secuentes:

$A⊢\mathrm{\forall }xA$

És dir: a partir d'és possible concloure que ∀x A.

Note's que la regla de generalisació universal és anàloga a la regla de Necesitación de la llògica modal.

Axioma

Els axioma considerats ací són els axioma llògics els quals són part del càlcul de predicats. En formalisar teories de primer orde particulars (com l'aritmètica de Peano) s'agreguen axioma no-llògics específics, és dir axioma que no es consideren veritats de la llògica pero sí veritats d'una teoria particular.

Quan el conjunt de axioma és infinit, es requerix d'un algoritme que puga decidir per a una fòrmula ben formada si és un axioma o no. Més encara, deuria existir un algoritme que puga 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 axiomatizado de vàries formes diferents. No existix res canònic sobre els axioma i regles d'inferència ací donades, pero qualsevol formalisació produïx les mateixes teoremes de la llògica (i permet deduir les mateixes teoremes de qualsevol conjunt de axioma no-llògics).

Els següents tres axioma són heretats de la llògica proposicional i s'incorporen a la llògica de primer orde. Sean A, B i C fòrmules ben formades de Q. Després, els següents són axioma llògics:

Ax1: A → (B → A)

Ax2: (A → (B → C)) → ((A → B) → (A → C))

Ax3: (¬A → ¬B) → (B → A)

Els dos axioma següents són característics de la llògica de primer orde. Sean A i B fòrmules ben formades de Q en com a màxim una variable lliure, x. Siga t un terme tancat i A(x/t) el resultat de reemplaçar tota aparició de x en A per t. Després, els següents són axioma llògics:

Ax4: ∀x A → A(x/t)

Ax5: ∀x (A → B) → (∀x A → ∀x B)

Intuitivamente, el quart axioma diu que lo que val per a tots val per a qualsevol. Per eixemple, un cas particular de l'axioma podria ser: «Si tots són mortals, llavors Abel és mortal»; o també: «Si tots són mortals, llavors el pare de Mateo és mortal» El quint axioma és anàlec a l'axioma K de la llògica modal, i un cas particular del mateix podria ser: «Si tots els humans són mortals, llavors, si tots són humans, tots són mortals.»

Semàntica

Una interpretació és un parell <D,I>, a on D és un conjunt no buit cridat el domini de discurs i I és una funció cridada la funció d'interpretació definida com seguix:

1. Si a és un nom, llavors I li assigna un element del domini.
2. Si f és un functor de aridad n, llavors I li assigna una funció de n arguments que pren elements del domini i torna elements del domini.
3. Si P és un predicat de aridad n, llavors I li assigna un conjunt de n-tuplas construïdes a partir del domini.

Després és possible definir la noció de veritat per a una interpretació (per a les oracions de Q):

1. P(t₁,...,t_n) és verdadera per a l'interpretació M si i solament si la n-tupla formada per les interpretacions de t₁,...,t_n és un element de l'interpretació de P.
2. ¬A és verdadera per a l'interpretació M si i solament si A és falsa baix eixa interpretació.
3. (A ∧ B) és verdadera per a l'interpretació M si i solament si A és verdadera i B és verdadera baix eixa interpretació.
4. (A ∨ B) és verdadera per a l'interpretació M si i solament si A és verdadera o B és verdadera baix eixa interpretació.
5. (A → B) és verdadera per a l'interpretació M si i solament si A és falsa o B és verdadera baix eixa interpretació.
6. (A ↔ B) és verdadera per a l'interpretació M si i solament si A i B són abdós verdaderes o abdós falses baix eixa interpretació.

Per a donar les definicions de veres per a fòrmules en la forma ∀x A o ∃x A, primer són necessàries algunes definicions preliminars: Siga A(x/a) el resultat de reemplaçar tota aparició de x en A per un nom a (que no haja segut utilisat en la fòrmula). Ademés, si M i M' són interpretacions i a un nom, llavors M' és una a-variant de M si i solament si M' és idèntica a M o diferix solament en l'element del domini que li assigna al nom a.

7. ∀x A és verdadera per a M si i solament si A(x/a) és verdadera per a tota a-variant de M.
8. ∃x A és verdadera per a M si i solament si A(x/a) és verdadera per a a lo manco una a-variant de M.

Una fòrmula és falsa baix una interpretació si i solament si no és verdadera baix eixa interpretació.

A partir d'açò es poden definir vàries atres nocions semàntiques:

• Una fòrmula és una veritat llògica si i solament si és verdadera per a tota interpretació.
• Una fòrmula és una contradicció si i solament si és falsa per a tota interpretació.
• Una fòrmula és consistent si i solament si existix a lo manco una interpretació que la faça verdadera.
• Una fòrmula A és una conseqüència semàntica d'un conjunt de fòrmules $\Gamma$ si i solament si no hi ha cap interpretació que faça verdaderes a totes les fòrmules en $\Gamma$ i falsa a A. Quan A és una conseqüència semàntica de $\Gamma$ en un llenguage Q, s'escriu: $\Gamma {\models }_{Q}A$
• Una fòrmula A és llògicament vàlida si i solament si és una conseqüència semàntica del conjunt buit. Quan A és una fòrmula llògicament vàlida d'un llenguage Q, s'escriu: ${\models }_{Q}A$

Vore també

• Llògica d'orde zero
• Llògica de segon orde

• Llògica d'orde superior
• Quantificador
• Argument
• Càlcul llògic
• Predicat (llògica matemàtica)