Lehen mailako logika

**Lehen mailako logika**, **predikatuen logika, logika kuantifikatzailea** edo **predikatuen kalkulua** ere deitzen dena, lehen ordenako hizkuntzen inferentzia aztertzeko diseinatutako sistema formala da. Predikatuak, haien propietateak eta eragiketak aztertzen dituen logika. Aldagai eta kuantifikatzaileen bidez lan egiten du. Predikatuen logikak proposizioen barne-egitura hartzen du kontuan. Lehen ordenako lengoaiak, era berean, banakako aldagaiei bakarrik eragiten dien zenbatzaileak dituzten lengoaia formalak dira, eta argumentuak, konstanteak edo aldagai indibidualak dituzten predikatuak eta funtzioak baino ez dira.

Lehen ordenako logikak, logika proposizionala baino adierazkortasun-maila altuagoa du.

## Sarrera 
Historikoki lehen mailako logikaren aplikazioak matematikekin lotura handia dutenez, jarraian harreman hori kontenplatu eta ilustratuko duen sarrera egingo da, matematikatik eta lengoaia naturaletik datozen adibideak hartuz. Lehendabizi sistemaren oinarrizko kontzeptu bakoitza aurkezten da, eta gero argumentuak nola erabiltzen diren erakusten da.

### Predikatuak 
Predikatu bat esaldi bat osatzeko beste adierazpen batekin edo batzuekin erlazionatu daitekeen adierazpen linguistikoa da. Adibidez, > esaldian > esaldia > adierazpenarekin lotzen den predikatua da. Eta > esaldian > adierazpena > eta > lotzen dituen predikatua da.

Logika matematikoan, predikatu bat adierazpen batekin lotzen denean, *propietate* bat adierazten duela esaten da (*planeta bat izatearen* propietatea esate baterako), eta bi espresio edo gehiagorekin lotzen denean, *harreman* bat adierazten duela esaten da (adibidez, *zerbait baino handiagoa* *izatea*). Hala ere, lehen ordenako logikak ez du inolako hipotesirik egiten propietate edo erlazioen existentziaren inguruan. Hitz egiteko eta arrazoitzeko erabiltzen ditugun adierazpen linguistikoak aztertu besterik ez du egiten.

Lehen mailako logikan, predikatuak funtzio gisa tratatzen dira. Funtzio bat da, metaforikoki hitz eginez, datu multzo bat jasotzen duen makina, prozesatu egiten dituena eta emaitza *bakarra* itzultzen duena. Funtzioen sarrerako datuei argumentu deitzen zaie eta itzultzen diren emaitzei *balio* edo *irudi direla* esaten da. Ikus ezazu, ondorengo funtzio matematikoa:

:*f*(*x*) = 2*x*

Funtzio honek zenbakiak argumentu gisa hartzen ditu eta beste zenbaki batzuk itzultzen ditu balio gisa. Adibidez, 1 zenbakia hartzen baduzu, 2 zenbakia itzultzen du, eta 5a hartzen baduzu, 10 itzuliko du. Lehen mailako logikoan, predikatuek, zenbakiez gain, bestelako argumentu mota ere hartzen dituzten funtzioak dira, adibidez, > eta >, edo beranduago azalduko diren bestelako batzuk. Horrela, > esaldia honela transkribatu daiteke, funtzioen notazioari jarraituz:

:*Planeta*(*Marte*) edo *P*(*m*)

Matematikan hainbat argumentu hartzen dituzten funtzioak ere existitzen dira. Adibidez:

:*f*(*x*,*y*) = *x* + *y*

Funtzio honek, 1 eta 2 zenbakiak hartzen baditu, 3 zenbakia itzultzen du eta -5 eta -3 hartzen baditu, -8 itzultzen du. Ideia horri jarraituz, lehen mailako logikak erlazioak adierazten dituzten predikatuak tratatzen ditu, bi argumentu edo gehiago hartzen dituzten funtzio gisa. Adibidez, > esaldia honela formaliza daiteke:

:*Hil*(*Cain*,*Abel*) edo *H*(*c*,*a)*

Prozedura hau entitate askoren arteko harremanak adierazten dituzten predikatuei aurre egiteko erabil daiteke. Adibidez, > esaldia honela formaliza daiteke:

:*E*(*a*,*b*,*c*)

### Banako konstanteak 
Konstante indibiduala entitate bati egiten dion adierazpen linguistikoa da. Adibidez, >, >, > eta > banako konstanteak dira. Zenbakiak deitzen diren adierazpenak, >, > eta abar ere banako konstanteak dira. Entitate batek ez du zertan existitu beharrik horri buruz hitz egin ahal izateko, beraz, lehen ordenako logikak ere ez du hipotesirik egin behar entitateak aipatzen dituen konstanteen existentziari buruz.

### Banako aldagaiak 
Entitate jakin batzuek erreferentzia egiten dituzten banakako aldagaiez gain, lehen ordenako logikak baditu beste adierazpen batzuk, *aldagaiak*, hauen erreferentziak zehazturik ez daudenak. Aldagaiak, oro har, latindar alfabetoaren amaieratik hizki xehez ordezkatzen dira, batez ere x, y, eta z. Era berean, matematiketan, f (x) = 2x funtzioko x-k ez du zenbaki partikularrik adierazten, baizik eta zenbaki desberdinak txertatu ahal izateko espazio huts bat bezala. Bukatzeko, > bezalako adierazpena irudikatu dezakegu:

:*Zaharra*(*x*) edo Z(*x)*

Bistakoa da, hala ere, x-k zer adierazten duen zehaztu arte, ezin zaiola egiazko balioa esleitu > adierazpenari, eta x-ren balioa zehaztu arte f (x) = 2x funtzioaren balioa ezin izango da kalkulatu.

Jakina, banako konstanteekin gertatzen den moduan, aldagaiek erlazioak formalizatzeko ere balio dute. Adibidez, > esaldia honela formalizatzen da:

:H(*x*,*y*)

Gainera, konstanteak banako aldagaiekin konbinatu ditzakezu. Adibidez, > esaldian:

:E(*x*,*b*,*c*)

### Zenbatzaileak 
Orain kontuan hartu honako adierazpen matematikoa:

:*x* > 3

Adierazpen hori ez da egiazkoa ezta faltsua ere, eta, dirudienez, ez da bietako bat izango x beste zenbaki batekin ordezkatzen ez dugun bitartean. Hala ere, posiblea da egiazko balio bat esleitzea adierazpenari aurretik zenbatzaile bat jartzen baldin bazaio. Zenbatzailea banako multzo baten gainean aplikatzen den eragilea da, baliabide adierazkor bat da multzoen gainean proposizioak sortzeko ahalmena ematen diguna, edo beste modu batera esanda, zenbatzaile bat banako jakin batzuentzako baldintza bat betetzen dela adierazten duen adierazpena da. Logika klasikoan, gehien aztertzen diren zenbatzaileak zenbatzaile unibertsala eta zenbatzaile existentziala dira. Lehenak esaten du baldintza bat betetzen dela hitz egiten ari den banako guztientzako, eta bigarrena, gutxienez, gizabanako *batentzat* betetzen dela. Adibidez, "x guztientzako" adierazpena zenbatzaile unibertsala da, eta "x a \quad x \quad P  \quad \lnot \quad \land \quad \lor \quad \rightarrow \quad \leftrightarrow \quad \forall 
\quad \exist \quad ( \quad )   

#### Idazkera 
# **Izen** edo konstante bat idazteko alfabetoko hasierako letrak erabiltzen dira a, b, c, d, e, a1, a2,...
# **Aldagai** bat idazteko alfabetoaren bukaerako letrak erabiltzen dira x, y, z, x1, x2,...
# **Predikatu** bat idazteko alfabetoko letra larriak erabiltzen dira P, A, B, C, S, T,...
# **Zenbatzaile unibertsala**  \boldsymbol{\forall}  ikurraz adierazten da.
# **Zenbatzaile existentziala**  \boldsymbol{\exists}  ikurraz adierazten da.

#### Terminoak eta interpretazioak 
# P n (n ≥ 1)aritatea duen predikatu bat izanik eta *t*1,...,*tn* terminoak badira orduan P(*t*1,...,*tn*) termino bat da.
# Izen guztiak dira terminoak.
# Aldagai guztiak dira terminoak.
# Predikatuak terminoak dira.

#### Ongi eratutako formulak 
# A ongi eratutako formula bat baldin bada ¬A ere ongi eratutako formula bat da.
# A eta B ongi eratutako formulak baldin badira (A ∧ B), (A ∨ B), (A → B) eta (A ↔ B) ere ongi eratutako formulak dira.
# A ongi eratutako formula bat bada eta x aldagai bat bada ∀*x* A y ∃*x* A ere ongi eratutako formulak dira.

* Ondoko formulak ongi eratuta daude:

* Aldiz, ondoko formulak ez daude ongi eratuta

*

## Inferentzi erregelak 
Logika proposizionalean bezala, predikatu logikan A1, A2, . . . , An premisak eta B ondorioa dituen argudio formala baliozkoa da baldin A1 ∧ A2 ∧ . . . ∧ An → B adierazpena baliozkoa bada.

Horrela izanez gero, A1, A2, . . . , An |= B idazten da.

Beraz, argudio bat baliozkoa da baldin eta premisa denak egiazkoak direnean ondorioa ere egiazkoa bada, edozein interpretaziotarako.

Argudio bat baliozkoa dela frogatzeko, eratorpen edo frogapen formalak egiten dira. Horretarako, ondorengo lau inferentzi erregelez gain logika proposizionaleko erregelak ere erabiltzen dira.

Inferentzi erregela horien bidez, zenbatzaileak (unibertsalak eta existentzialak) ezabatu edo gehitzen dira frogapen formala egin ahala.

Gainera, kasu batzuetan banako aldagaia edo konstantea ordezkatu beharko da erregeletan esaten den bezala.

#### Unibertsala ezabatzea (UE) 
# Modua
#* \forall x A(x)\vdash A(x)
#* \forall y A(y)\vdash A(y)
# Modua
#* \forall x A(x)\vdash A(a)
#* \forall x A(x)\vdash A(b)

#### Existentziala ezabatzea (EE) 
* \exist A(x)\vdash A(a)

a,b,c konstante bat aukeratu behar da frogapenean zehar inon agertu ez dena, ezta ondorioan ere. Gainera, \exist x A(x) adierazpenean ezin da aldagai bat egon bere zenbatzailerik gabe**.**

#### Unibertsala gehitzea (UG) 
* A(x) \vdash \forall x A(x) 
* A(y)\vdash \forall y A(y) 

Unibertsalaren aldagaia x, y, z,... izan daiteke.

#### Existentziala gehitu (EG) 
* A(a) \vdash \exist x A(x) 

Existentzialaren aldagaia x, y, z,... izan daiteke

#### Argudio baten frogapena 
 

\begin{array}{l}
Frogatu: \forall x \forall y P(x) \longrightarrow \forall P(x,x) \ ?\\
Ebazpena: \\
\begin{array}{ll}
      1. \forall x \forall y P(x) &Premisa\\
      2. \forall P(a,y) &UE(1)\\
      3. P(a,a) &UE(2)\\
      4. \forall P(x,x) &UG(3)\\
\end{array}\\
\\
\underline{\forall x \forall y P(x) \longrightarrow \forall P(x,x)}
\end{array}

 

## Baliokidetasunak 
Logika proposizionalean bezala, predikatu logikan A eta B adierazpenak baliokideak dira (A ≡ B), baldin A ↔ B adierazpena baliozkoa bada. Hau da, A eta B adierazpenak baliokideak dira edozein interpretaziotarako egia-balio berdina badute**.** Jarraian oinarrizko baliokidetasun legeak daude:

# \lnot \exist A(x) =\forall x \lnot A(x)

# \lnot \forall A (x)\equiv \exist \lnot A(x)

# \forall x \forall y A(x,y)\equiv \forall y \forall x A(x,y)

# \exist x \exist y A(x,y)\equiv \exist y \exist x A(x,y)

# \forall(A(x)\land B(x))\equiv \forall xA(x) \land \forall x B(x)

# \exist(A(x)\lor B(x))\equiv \exist xA(x) \lor \exist x B(x)

Unibertsala banakorra da konjuntziorako baina EZ disjuntziorako.

Existentziala banakorra da disjuntziorako baina EZ konjuntziorako.

# \forall x(A\land B(x))\equiv A \land \forall x B(x)

# \forall x(A\lor B(x))\equiv A \lor \forall x B(x)

# \exist x(A\land B(x))\equiv A \land \exist x B(x)

# \exist x(A\lor B(x))\equiv A \lor \exist x B(x)

Aurreko lau baliokidetasunetan A azpiadierazpenean EZ da x aldagaia agertzen**.**

#### Argudio baten frogapena baliokidetasunak erabiliz 
  \begin{array}{ll}
    Frogatu: \forall x \exist y (P(x)\land Q(y)) \equiv \forall P(x) \land \exist Q(y) ?\\
    Ebazpena: \underline{\forall x \exist y (P(x)\land Q(y)) }\equiv \forall x (P(x) \land \exist y Q(y)) \equiv 
    \underline{\forall P(x) \land \exist Q(y)}\\
    \\
    Frogatu: \forall x \exist y (P(x,y) \rightarrow \lnot Q(x,y)) \equiv \lnot \exist x
    \forall y(P(x,y) \land Q(x,y)) ?\\
    Ebazpena: \underline{\lnot \exist x \forall y(P(x,y) \land Q(x,y)) }\equiv  
    \forall x \lnot \forall y(P(x,y) \land Q(x,y)) \equiv
    \forall x  \exist y \lnot(P(x,y) \land Q(x,y)) \equiv
    \forall x  \exist y (\lnot P(x,y) \lor \lnot Q(x,y)) \equiv \\
    ~~~~~~~~~~~~~~~~~~\underline{ \forall x  \exist y (P(x,y) \rightarrow \lnot Q(x,y))}
   \end{array}

 

## Adierazpen bat baliozkoa ez dela nola frogatu 
Predikatu logikan adierazpen baten baliozkotasuna aztertzeko bere egia-taulako lerroetan egiazkoa den begiratu behar da, baina egia-taulak logika proposizionalekoak baino konplexuagoak dira.

Adierazpenaren egia-taulako lerro bakoitza idazteko adierazpenaren interpretazio bat eman behar da. Jarraian interpretazio horiek nola gauzatu azaltzen dira.

# Unibertsoa zehaztuko da, multzo zenbakigarri bat izango da (finitua ala infinitua), beraz banakoak 1, 2, 3 . . . izango dira adierazpen baten interpretazioa definitzen denean.
# Adierazpenaren interpretazio bat definitzeko esleipen hauek egingo dira.
#* Aldagai proposizional bakoitzari egia-balioa: T edo F.
#* Konstante bakoitzari unibertsoko banakoa: zenbaki bat.
#* Predikatu aldagai bakoitzari funtzio logikoa: argumentutzat (aritatearen arabera) unibertsoko banakoak (1, 2, 3 . . .) hartzen dituen eta egia-balioa (T edo F) itzultzen duen funtzio bat.
# Adierazpenaren interpretazio bat (bere egia-taulako lerro bat) finkatuz, adierazpenaren egia-balioa kalkulatu daiteke, jakinik zenbatzaileekin egin behar den ondorengo kalkulua.
#* Zenbatzaile unibertsala:
#*# ∀xA(x) T da baldin A(x) T bada unibertsoko x banako guztietarako.
#*# ∀xA(x) F da baldin A(x) F bada gutxienez unibertsoko x banako baterako.
#* Zenbatzaile existentziala:
#*# ∃xA(x) T da baldin A(x) T bada gutxienez unibertsoko x banako baterako.
#*# ∃xA(x) F da baldin A(x) F bada unibertsoko x banako guztietarako.
# Interpretazio bat (egia-taulako lerro bat) finkatuz, ∀xA(x) adierazpenaren edo azpiadierazpenaren egia-balioa kalkulatzeko (berdin ∃xA(x) izanik), taula laguntzaile bat osatzen da, lerro bakoitzean x aldagaiari unibertsoko banako bat esleituz eta A(x) azpiadierazpenaren egia-balioa kalkulatuz.
# Gainera, A(x) azpieadierazpenaren barruan beste zenbatzaile bat badago, eraiki den taula laguntzailearen lerro bakoitzerako, x banakoa finkatu ondoren, taula laguntzaile bat egin beharko da bigarren zenbatzailearen egia-balioa kalkulatzeko. Beraz, interpretazio bat finkatuz, era errekurtsiboan kalkulatzen da ∀xA(x) edo ∃xA(x) adierazpenaren, edo azpiadierazpenaren, egia-balioa.

#### Argumentu baten baliokidetasuna ez dela betetzen frogatzeko adibidea 
Frogatu \ ez \ baliozkoa \ dela: \exist x \exist y P (x,y) \rightarrow \exist x P(x,x)

 

\begin{array}{l|l}
      P(-,-)&\exist x \exist y P(x,y) \rightarrow \exist P(x,x)\\
      \hline
      \psi(-,-)&T \qquad \qquad \ \ F  \qquad F   \\
      \\
       & \psi(-,-) \ Interpretazioa?\\
\end{array}

 

 

\exist x \exist y \psi (x,y)~ T \ izateko 

 

 

\begin{array}{l|l l}
      x&\exist y \psi(x,y) \\
      \hline
      1& T\\
      &edo\\
      2& T\\
\end{array}

 

# **Lerroa:**  

\exist y \psi(1,y)~ T \ izateko 

 
#*  

\psi (1,1) ~T \quad edo \quad \psi (1,2)~ T 

 
# **Lerroa:**  

\exist y \psi(2,y)~ T ~izateko 

 
#*  

\psi(2,1) ~ T\quad edo \quad \psi(2,2)~ T 

 

 

\exist x \psi (x,x) ~ F \ izateko 

 

 

\begin{array}{l|l l}
      x&\exist y \psi(x,x) \\
      \hline
      1& F\\
      &eta\\
      2& F\\
\end{array}

 

**Emaitza posible bat:**

 

\begin{array}
\hline
      \psi&1&2\\
      \hline
      1& F&T\\
      2& T&F\\
      \hline
\end{array}

 

## Semantika 
Lengoaia formalen interpretazioari semantika formala deritzo. Lehen mailako lengoaiaren kasuan, interpretazioa egitean ikur ez-logiko bakoitzari esanahi bat ematen zaio eta zenbatzaileen esparrua zehazten duen diskurtso-domeinua ere zehazten da. Horren eraginez, termino bakoitzari, terminoa ordezkatzen duen objektu bat esleitzen zaio, eta predikatu bakoitzari egia-balio bat esleitzen zaio ordezkatutako terminoaren arabera. Horrela, interpretazioak esanahi semantikoa esleitzen die lengoaiaren termino, predikatu eta formulei.

Mota jakin bateko objektuez osatuko *D* multzo ez-hutsa izanik, lehen mailako formula objektu horien inguruko adierazpena da. Adibidez, \exists x P(x)- k objektu baten (x) existentzia adierazten du, P predikatua egiazkoa den kasuan. Diskurtsoaren domeinua multzo horren objektuez osatuta dago. Adibidez, D zenbaki osoen multzoa izan daiteke.

### Lehen Mailako Egiturak 
Interpretazioak zehazteko modurik ohikoena (batez ere matematiketan) egitura bat zehaztea izaten da. Egitura horrek, D multzoa eta l interpretazioa osatzen dute. Beraz, interpretazioa ere funtzio bat da:

• *n* aritateko ikur funtzio bakoitzari (*f-ri), l(f)* funtzio bat ezartzen zaio D^n-tik D-ra definitzen dena.

• *n* graduko ikur predikatu bakoitzari (*P-ri),* *l(P)* erlazio bat ezartzen zaio D^n-ren inguruan, edo, beste modu batean esanda, funtzio bat D^n-tik **{**{true, false}**}** -ra.

### Baliozkotasuna eta ondorio logikoak 
Formula bat logikoki baliozkoa da (edo, besterik gabe, baliozkoa) interpretazio guztietan egia bada. Formula horiek proposamenen logikan tautologien antzeko funtzioa betetzen dute.

Φ formula ψ formularen ondorio logikoa da ψ egia bihurtzen duen interpretazio bakoitzak Φ egia bihurtzen badu.

### Lehen mailako teoriak, ereduak eta oinarrizko klaseak 
Signatura jakin baten lehen mailako teoria bat, axioma multzo bat da, signatura horretako sinboloz osatutako esaldiak direnak. Axioma multzoa sarritan finitua edo errekurtsiboa izan ohi da, kasu horietan **teoria eraginkorra** dela esaten da. Zenbait autorek teoriak ere behar izaten dituzte axiomen ondorio logiko guztiak gehitzeko. Axiomak teoriaren barruan daudela uste da eta hortik teoriaren barruko beste esaldi batzuk erator daitezke.

Teoria jakin batean esaldi guztiak asetzen dituen lehen mailako egiturari, **eredu** deritzo. **Oinarrizko klasea** teoria jakin bat asetzen duten egitura guztien multzoa da. Klase horiek ereduen teorien azterketan gai nagusi bat izaten dira.

Hainbat teoriak interpretazio asmo bat izaten dute, teoria aztertzeko garaian kontuan hartzen den eredu bat.

Teoria bat koherentea dela esaten da, teoriaren axiometatik kontraesan bat frogatzea ezinezkoa bada. Teoria bat osoa dela esaten da, baldin eta bere signaturako formula bakoitzerako teoriaren axiomen ondorio logikoa bada: formula bera edo bere ezeztapena. Gödelen osogabetasuneko teoremaren arabera, zenbaki arrunten teoriaren zati bat biltzen duten lehen mailako teoria eraginkorrak ezin dira sekula aldi berean koherenteak eta osoak izan.

### Domeinu hutsak 
Aurreko definizioak eskatzen du edozein interpretazioren diskurtsoaren domeinua hutsa ez izatea. Baina badira kasuak, adibidez, logika inklusiboa, non domeinu hutsak baimenduta dauden. Gainera, egitura aljebraikoen klase batek egitura huts bat barne hartzen badu, klase hori oinarrizko lehen mailako logikan oinarrizko elementua bakarrik izan daiteke, domeinu hutsak onartzen badira edo egitura hutsezko egitura klasetik kentzen bada.

Domeinu hutsekin hainbat zailtasun daude, ordea:

• Inferentzia ohiko arau asko zuzenak dira diskurtsoaren domeinua ez-hutsa izatea eskatzen denean.

• Aldagaien esleipen-funtzio bat erabiltzen duen interpretazioetan egiaren definizioak ezin du domeinu hutsekin funtzionatu, ez baitago aldagaien esleipen-funtzio bat non tartea hutsa den (era berean, ezin zaizkie interpretazioak esleitu ikur konstanteei). Egiaren definizio honek eskatzen du aldagaien esleipen-funtzio bat hautatu behar dela formula atomikoak definitu baino lehen. Orduan, esaldi baten egia-balioa bere egiazko balioa izango da edozein aldagai esleipenen arabera, eta egia-balio hori ez dago aukeratutako esleipenearen menpe. Teknika horrek ez du funtzionatzen inolako esleipen-funtziorik ez badago; izan ere, aldatu behar da multzo ez-hutsetarako moldatzeko

Beraz, domeinu huts bat baimentzen denean, normalean kasu berezi bezala tratatu behar izaten da. Autore gehienek, hala ere, domeinu hutsa definizioan bertan baztertzen dute.

## Erreferentziak 
## Kanpo estekak