Matematika Diskretua/Predikatu logika

2. Gaia: Predikatu-logika

2.1 Sarrera

Proposizio-logikan, argumentuen baliozkotasuna enuntziatu konposatuak sortzeko asmoz enuntziatu bakunak konbinatzeko eraren menpe dago, ez enuntziatuen barne-egituraren menpe.

Adibidez, intuizioz zuzena dirudien argumentu hau hartuko dugu:

Txakur guztiak ugaztunak dira.

Bizi txakurra da.

Beraz, Bizi ugaztuna da.

Proposizio-logikan, “Txakur guztiak ugaztunak dira” premisa proposizio bakuna da, eta $p$ atomo batez adierazten dugu. Berdin gertatzen da bigarren premisarekin eta ondorioarekin, “Bizi txakurra da” proposizio bakuna $q$ atomoaz adieraziko dugu eta “Bizi ugaztuna da” proposizio bakuna $r$ atomoaz.

Beraz, proposizio-logikan, argumentua honela adieraziko dugu:

$$\begin{array}{c}p\\ q\\ r\end{array}$$

Eta argumentu hori ez da baliozkoa; izan ere, $I=\{p,q,\mathrm{\neg }r\}$ interpretaziorako premisak egiazkoak dira eta ondorioa faltsua da.

Hori hala da, argumentuaren baliozkotasuna enuntziatuen barne-egitura logikoaren menpe dagoelako. Horrelako kasuetan, barne-egitura horiek analizatzeko tresnak garatu beharko ditugu. Predikatu-logika proposizio-logikaren hedapena da, analisi horrek behar duen tresna.

Argumentuaren bigarren premisak dio “Bizi” izeneko banakoak txakur izatearen ezaugarria duela. “Bizi” subjektua da eta “txakurra” predikatua da (subjektuak duen ezaugarri bat adierazten du).

Enuntziatuen egiturak aztertzen ditugunean, funtsean, bi adierazpen-mota hauek interesatzen zaizkigu: alde batetik, banakoei (izaki zehatzak: pertsonak, zenbakiak...) dagozkien adierazpenak eta, beste aldetik, banakoen ezaugarriak edo banakoen arteko erlazioak azaltzen dituzten adierazpenak (predikatuak).

Esate baterako, “Bizi txakurra da”, “Ilargia zuria da”, “2 5 baino txikiagoa da”, “Anek tea nahiago du kafea baino” enuntziatuetan “Bizi”, “ilargia”, “2”, “5”, “Ane”, “tea”, “kafea” banakoak dira eta “txakurra da”, “zuria da”, “baino txikiagoa da”, “nahiago du” predikatuak dira, banakoen ezaugarriak edo banakoen arteko erlazioak azaltzen dituzten adierazpenak.

Formalizazioa

Banakoak adierazteko $a,b,c,\dots$ letra xeheak erabiliko ditugu. Sinbolo horiek banakoak adierazten dituztenez, konstante deituko diegu.

Predikatuak adierazteko letra larriak erabiliko ditugu.

Adibidez,

1. Bizi txakurra da.

   $b$: “Bizi”
   $T$: “txakurra izan”	$T(b)$

2. Ilargia zuria da.

   $i$: “ilargia”
   $Z$: “zuria izan”	$Z(i)$

3. 2 5 baino txikiagoa da.

   $b$: “2”
   $z$: “5”	$T(b,z)$
   $T$: “txikiagoa izan”

4. Anek tea nahiago du kafea baino.

   $a$: “Ane”
   $t$: “tea”	$N(a,t,k)$
   $k$: “kafea”
   $N$: “nahiago izan”

Aurreko adibideetan ikus dezakegu predikatu batzuetan banakoen izen bakarra agertzen dela (banako predikatuak) eta beste batzuetan banakoen bi izen edo gehiago agertzen direla (predikatu anizkoitzak: bitarrak, hirutarrak...).

Azter dezagun, orain, predikatu-sinbolo bera duten proposizioak nola formulatzen diren:

Bizi txakurra da: $T(b)$

Lagun txakurra da: $T(l)$

7 txakurra da: $T(z)$

Proposizio horiek guztiak batera adierazteko $T(x)$ idatziko dugu. $x$ letrari aldagai esango diogu. Ez da konstantea, eta edozein konstantez ordezka dezakegu.

$T(b)$, $T(l)$, $T(z)$ proposizioak dira, hots, esan dezakegu egiazkoak edo faltsuak diren; baina $T(x)$ ez da egiazkoa, ezta faltsua ere, ez da proposizio.

$T(x)$ bazalako adierazpenei proposizio-funtzio deituko diegu. Banako aldagaiak onartzen dituzten adierazpenak dira, eta proposizio bihurtzen dira banako aldagaien ordez banako konstanteak jartzen ditugunean.

Proposizio-funtzio batetik proposizio bat lortzeko prozesuari, aldagai bat konstante batez ordezkatuz, instantziazio deituko diogu, eta ateratzen den proposizioari ordezkapen-instantzia.

Esaterako, $\mathrm{\neg }T(b)$ (Bizi ez da txakurra) eta $\mathrm{\neg }T(z)$ (7 ez da txakurra) $\mathrm{\neg }T(x)$ proposizio-funtzioaren bi instantziazioren emaitzak dira. $\mathrm{\neg }T(x)$ proposizio-funtzioaren bi ordezkapen-instantzia $\mathrm{\neg }T(b)$ eta $\mathrm{\neg }T(z)$ dira.

Badago beste prozedura bat proposizio-funtzio batetik proposizio bat lortzeko: aldagaiak kuantifikatzea.

Orain arte, banako enuntziatuen adibideak ikusi ditugu, eta horietan banako bati ezaugarri bat egokitu zaio edo bi banakoren edo gehiagoren arteko erlazio bat ezarri da. Baina enuntziatuak ez dira beti banakoak; adibidez, “Dena zuria da” eta “Zerbait zuria da” proposizio orokorrak dira, ez dute banako-izenik. Hala ere, proposizio-funtzio batetik lor ditzakegu, ez instantziazioen bidez, baizik eta orokortzearen edo kuantifikatzearen bidez.

Lehenengo adibidea, “Dena zuria da”, beste era honetan ere adieraz dezakegu: “Edozein gauza izanik, gauza hori zuria da”; eta, $x$ aldagaia erabiliz, “Edozein $x$ izanik, $x$ zuria da”.

“Edozein $x$ izanik” esaldia zenbatzaile unibertsala da, eta $\mathrm{\forall }x$ idatziz adieraziko dugu. Sinbolo hori erabiliz, “Dena zuria da” esaldia honela idatziko dugu: $$\mathrm{\forall }xZ(x)$$

Antzeko eran, “Zerbait zuria da” esaldia honela idatz dezakegu:“Badago gutxienez gauza bat zuria dena”; eta, aldagai batekin, “Badago gutxienez $x$ bat, non $x$ zuria den”.

“Badago gutxienez $x$ bat” esaldia zenbatzaile existentziala da, eta $\mathrm{\exists }x$ idatziz adieraziko dugu. Sinbolo hori erabiliz, “Zerbait zuria da” esaldia honela idatziko dugu: $$\mathrm{\exists }xZ(x)$$

Laburbilduz, “$x$ zuria da” ($Z(x)$) bezalako proposizio-funtzio bat izanik (edo enuntziatu irekia), bi bide dauzkagu proposizio bat lortzeko (edo enuntziatua ixteko):

1. Instantziazioa, aldagaia konstante batez ordezkatzea: $Z(i)$, “Ilargia zuria da”. Bide honen bidez banako enuntziatua lortuko dugu.

2. Orokortzea edo kuantifikazioa, zenbatzaile bat aurrean jartzea: $\mathrm{\forall }xZ(x)$, “Dena zuria da”; $\mathrm{\exists }xZ(x)$, “Zerbait zuria da”.

   Bide honen bidez enuntziatu orokorra lortuko dugu.

Historiari begira, logika tradizionalak lau proposizio-mota nabarmendu zituen; ikus ditzagun adibide hauekin:

• $A$ (baiezko proposizio unibertsala): “Txakur guztiak ugaztunak dira”.
• $E$ (ezezko proposizio unibertsala): “Txakur bat ere ez da ugaztun”.
• $I$ (baiezko proposizio partikularra): “Zenbait txakur ugaztunak dira”.
• $O$ (ezezko proposizio partikularra): “Zenbait txakur ez dira ugaztun”.

$T(x)$=”$x$ txakurra da” eta $U(x)$=”$x$ ugaztuna da” proposizio-funtzioak erabiltzen baditugu, $A$, baiezko unibertsala, honela irakur genezake: “Edozein gauza izanik, gauza hori txakurra bada, gauza hori ugaztuna izango da” edo “Edozein $x$ izanik, $x$ txakurra bada, $x$ ugaztuna izango da”. Eta adierazpen sinbolikoan: $$\mathrm{\forall }x(T(x)\to U(x)).$$

Era berean gainerako hiru proposizioekin:

$E$: “Edozein $x$ izanik, $x$ txakurra bada, $x$ ez da ugaztun”. Adierazpen sinbolikoan: $$\mathrm{\forall }x(T(x)\to \mathrm{\neg }U(x))$$

$I$: “Badago gutxienez $x$ bat, non $x$ txakurra den eta $x$ ugaztuna den”. Adierazpen sinbolikoan: $$\mathrm{\exists }x(T(x)\wedge U(x))$$

$O$: “Badago gutxienez $x$ bat, non $x$ txakurra den eta $x$ ez den ugaztun”. Adierazpen sinbolikoan: $$\mathrm{\exists }x(T(x)\wedge \mathrm{\neg }U(x))$$

Adibideak

1. Arranoek altu egiten dute hegan: $\mathrm{\forall }x(A(x)\to H(x))$.

   Arranoek bakarrik egiten dute hegan altu: $\mathrm{\forall }x(H(x)\to A(x))$.

2. Beroki bat ere ez da iragazgaitza ez bada bereziki tratatua izan: $$\mathrm{\forall }x(B(x)\wedge I(x)\to T(x)).$$

3. Zenbaki arrazional bakoitza zenbaki erreala da, baina zenbait zenbaki erreal ez dira arrazional: $$\mathrm{\forall }x(Q(x)\to R(x))\wedge \mathrm{\exists }x(R(x)\wedge \mathrm{\neg }Q(x)).$$

4. Edozein zenbaki arrunten hurrengoa zenbaki arrunta da: $$\mathrm{\forall }x\mathrm{\forall }y(N(x)\wedge H(y,x)\to N(y)),(H(y,x):yx\text{-ren hurrengoa da}).$$

5. Edozein zenbaki arrunten hurrengoa zeroren desberdina da: $$\mathrm{\forall }x\mathrm{\forall }y(N(x)\wedge H(y,x)\to \mathrm{\neg }B(y,a)),(B(y,x):y\text{ eta }x\text{ berdinak dira};a:0).$$

2.2 Sintaxia

2.1 Definizioa. Predikatu-logikaren $𝒜$ alfabetoa sinbolo hauek osatzen dute:

1. Aldagaiak: $𝒱=\{x,y,z,\dots \}$;
2. Konstanteak: $𝒞=\{a,b,c,\dots \}$;
3. Predikatuak: $𝒫=\{P,Q,R,\dots \}$; $P$ predikatu bakoitzak zenbaki arrunt bat darama elkarturik, predikatuak onartzen duen aldagaien edo konstanteen kopurua adierazten duena, hain zuzen; zenbaki horri predikatuaren aritate deituko diogu eta $ar(P)$ idatziko dugu.
4. Lokailu logikoak: $\{\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow \}$.
5. Zenbatzaileak : $\{\mathrm{\forall }$, $\mathrm{\exists }\}$.
6. Sinbolo inpropioak: $\{(,),,\}$ (parentesiak eta komak).

$𝒜=𝒱\cup 𝒞\cup 𝒫\cup \{\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow \}\cup \{(,),,\}.$

2.2 Definizioa. Aldagaiei eta konstanteei lehen ordenako termino deituko diegu.

2.3 Definizioa. $P$ $n$ aritateko predikatu-sinbolo bat bada eta $t_1,\dots ,t_n$ terminoak badira, $P(t_1,\dots ,t_n)$ atomo bat edo formula atomiko bat da.

2.4 Adibidea. Har ditzagun $𝒱=\{x,y,z\}$ aldagaien multzoa, $𝒞=\{a,b\}$ konstanteen multzoa eta $𝒫=\{P,Q,R,S\}$ predikatuen multzoa, aritateak $ar(P)=1$, $ar(Q)=3$, $ar(R)=2$, $ar(S)=3$ izanik.

Hona hemen atomo batzuk: $P(x)$, $P(b)$, $Q(x,a,y)$, $Q(x,y,x)$, $R(x,y)$, $S(a,b,b)$.
Honako hauek, ordea, ez dira atomo: $P(x,y)$, $Q(a)$.

2.5 Definizioa. Predikatu-logikan ongi eratutako formula (oef) arau hauei jarraituz eraikiko ditugu:

1. Atomo bat ongi eratutako formula da.
2. $A$ eta $B$ ongi eratutako formulak badira, $(\mathrm{\neg }A)$, $(A\wedge B)$, $(A\vee B)$, $(A\to B)$ eta $(A\leftrightarrow B)$ ere ongi eratutako formulak dira.
3. $A$ ongi eratutako formula bat bada eta $x$ aldagai bat bada, $(\mathrm{\forall }xA)$ eta $(\mathrm{\exists }xA)$ ongi eratutako formulak dira.
4. Aurreko hiru arauak kopuru finitu aldiz erabiliz lortzen diren formulak soilik dira ongi eratutako formulak.

2.6 Adibidea. Har ditzagun $𝒱=\{x,y,z\}$ aldagaien multzoa, $𝒞=\{a,b\}$ konstanteen multzoa eta $𝒫=\{P,Q,R\}$ predikatuen multzoa, $ar(P)=1$, $ar(Q)=3$, $ar(R)=2$ aritateak izanik.

Hona hemen ongi eratutako formula batzuk: $P(x)$, $P(b)$, $Q(x,a,y)$, $R(y,a)$, $(\mathrm{\exists }yR(y,a))$, $(\mathrm{\exists }xR(y,a))$, $(\mathrm{\forall }xP(x))$, $((\mathrm{\neg }P(x))\to Q(x,a,y))$, $(\mathrm{\forall }z(((\mathrm{\neg }P(x))\to Q(x,a,y))\wedge (\mathrm{\exists }xR(y,a))))$.

Hauek, aldiz, ez dira ongi eratutako formulak: $(\mathrm{\forall }aP(x))$, $(\mathrm{\forall }P(x,y))$, $(\mathrm{\forall }x,yP(x,y))$.

Proposizio-logikan bezala, bi eratan ken ditzakegu parentesi batzuk, nahasteko arriskurik ez dagoenean eta zenbatzaileen eta lokailuen artean hierarkia bat definituz:

• 1. maila: $\mathrm{\neg }$, $\mathrm{\forall }$, $\mathrm{\exists }$.
• 2. maila: $\wedge$, $\vee$.
• 3. maila: $\to$, $\leftrightarrow$.

2.7 Adibideak.

1. $(\mathrm{\forall }z((P(x)\wedge R(x,z))\to Q(x,a,y)))$ formula honela idatz dezakegu: $\mathrm{\forall }z(P(x)\wedge R(x,z)\to Q(x,a,y))$.
2. $\mathrm{\forall }xP(x)\to R(x,y)$ formula $((\mathrm{\forall }xP(x))\to R(x,y))$ formula da, baina ez hau: $(\mathrm{\forall }x(P(x)\to R(x,y)))$.
3. $\mathrm{\forall }x\mathrm{\forall }yR(x,y)\vee P(y)$ formula $((\mathrm{\forall }x(\mathrm{\forall }yR(x,y)))\vee P(y))$ formula da.

2.8 Definizioa. $A$ formula izanik, $A$ formularen azpiformula ongi eratutako formula bat da, $A$ formularen zatia bada eta ondoz ondo eraikia bada.

Adibidez, $A=\mathrm{\forall }xP(x)\to R(x,y)$ formula izanik, $\mathrm{\forall }xP(x)$ eta $R(x,y)$ azpiformulak dira, baina $P(x)\to R(x,y)$ ez da azpiformula.

2.9 Definizioa. Formula batean, zenbatzaile baten agerpen baten irismena agerpen horrek eragiten duen azpiformula da.

2.10 Adibideak.

1. $\mathrm{\forall }x\mathrm{\exists }yR(x,y)$ formulan, $\mathrm{\exists }y$ zenbatzailearen irismena $R(x,y)$ azpiformula da, eta $\mathrm{\forall }x$ zenbatzailearena $\mathrm{\exists }yR(x,y)$.
2. $\mathrm{\forall }y(\mathrm{\exists }xR(x,y)\vee P(x))$ formulan, $\mathrm{\exists }x$ zenbatzailearen irismena $R(x,y)$ azpiformula da, eta $\mathrm{\forall }y$ zenbatzailearena $\mathrm{\exists }xR(x,y)\vee P(x)$.
3. $\mathrm{\forall }y(R(x,y)\to \mathrm{\forall }x\mathrm{\exists }yQ(x,a,y))$ formulan, $\mathrm{\exists }y$ zenbatzailearen irismena $Q(x,a,y)$ azpiformula da, $\mathrm{\forall }x$ zenbatzailearena $\mathrm{\exists }yQ(x,a,y)$ azpiformula da, eta $\mathrm{\forall }y$ zenbatzailearena $R(x,y)\to \mathrm{\forall }x\mathrm{\exists }yQ(x,a,y)$.

2.11 Definizioa. Aldagai baten agerpen bat formula batean lotua da zenbatzaile batekin badago edo aldagaia erabiltzen duen zenbatzaile baten irismenaren barne badago. Agerpena askea da ez bada lotua.

Aldagai bat askea da formula batean gutxienez aldagaiaren agerpen bat askea bada formulan. Aldagai bat lotua da formula batean gutxienez aldagaiaren agerpen bat lotua bada formulan. Ohar gaitezen aldagai bat aldi berean askea eta lotua izan daitekeela.

2.12 Definizioa. Formula bat itxia da ez badauka aldagai askeen agerpenik.

2.13 Adibideak.

1. $\mathrm{\forall }xR(x,y)$.

   Zenbatzaileen agerpenen irismenak azpimarratuko ditugu, eta irismenei eta zenbatzaileek lotzen dituzten aldagaien agerpenei azpiindize bera jarriko diegu:

   $\mathrm{\forall }{x}_1{\underset{\_}{R(x_1,y)}}_1$. $x$ lotua da; $y$ askea da.

2. $\mathrm{\forall }x\mathrm{\exists }y(R(x,y)\to \mathrm{\forall }xP(x))$.

   Jakiteko zenbatzaileen agerpen bakoitzak aldagaien zer agerpen lotzen dituen, formularen barrutik kanpora joango gara, formula eraikitzeko bideari jarraituz.

   $\mathrm{\forall }{x}_3{\underset{\_}{\mathrm{\exists }{y}_2{\underset{\_}{(R(x_3,y_2)\to \mathrm{\forall }{x}_1{\underset{\_}{P(x_1)}}_1)}}_2}}_3$. $x$, $y$ lotuak dira eta formula itxia da.

3. $\mathrm{\exists }x\mathrm{\forall }yR(x,y)\vee \mathrm{\exists }zQ(x,a,z)$.

   $\mathrm{\exists }{x}_2{\underset{\_}{\mathrm{\forall }{y}_1{\underset{\_}{R(x_2,y_1)}}_1}}_2\vee \mathrm{\exists }{z}_3{\underset{\_}{Q(x,a,z_3)}}_3$. $x$ askea eta lotua da; $y$, $z$ lotuak dira.

4. $\mathrm{\forall }x\mathrm{\exists }yR(x,y)\to \mathrm{\forall }xP(x)$.

   $\mathrm{\forall }{x}_2{\underset{\_}{\mathrm{\exists }{y}_1{\underset{\_}{R(x_2,y_1)}}_1}}_2\to \mathrm{\forall }{x}_3{\underset{\_}{P(x_3)}}_3$. $x$, $y$ lotuak dira eta formula itxia da.

2.3 Semantika

Proposizio-logikan interpretazio bat atomoei egia-balioak esleitzea zen. Predikatu-logikan aldagaiak erabiltzen ditugunez, hori baino zerbait gehiago beharko dugu.

Lehendabizi, kontuan izan behar dugu zer objektu izan daitezkeen aldagaiaren balioak (hots, aldagaiaren definizio-eremua). Esaterako, demagun $Z(x,y)$ formulak “$x$ $y$-ren zatitzailea dela” esan nahi duela. $x$ eta $y$ aldagaiak zenbaki osoz ordezkatzen baditugu, proposizio bat lortuko dugu, egiazkoa edo faltsua izango dena. Baina aldagaiak zuhaitz-izenez ordezkatzen baditugu, ez da horrela gertatzen. Ez du zentzurik “Pagoak haritza zatitzen du” esateak. Dena dela, horrelako eztabaida baztertuko dugu suposatuz $D$ eremu ez-huts bat dagoela, non $D$ eremuaren elementuak aldagaien balioak diren.

Suposatuko dugu $D$ multzo ez-hutsa ez dugula ezagutzen; hau da, saiatuko gara predikatu-logika garatzen edozein $D$ multzo ez-huts erabiliz.

Adibidez, $D$ eremuak bi elementu baditu, elementuei 1 eta 2 deituko diegu; orduan, $D=\{1,2\}$ idatz dezakegu. $P$ 3 aritateko predikatu bat bada, $P(x,y,z)$ adierazpenean $x$, $y$, $z$ aldagaiek 1 eta 2 balioak har ditzakete: $P(1,1,1)$, $P(1,1,2)$, ..., $P(2,2,2)$.

Guztira, $2^3=8$ aukera ditugu, 1 eta 2 zenbakiekin osa ditzakegun hirukote guztiak, hain zuzen. Hirukote horien multzoa honela adieraziko dugu:

$D^3=\{(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)\}$

Antzeko eran, $D^2=\{(1,1),(1,2),(2,1),(2,2)\}$ dugu.

$D=\{1,2,3\}$ eremua badugu, $3^2=9$ bikoteen multzoa hau izango da:

$D^2=\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\},$

eta $3^3=27$ hirukoteen multzoa beste hau:

$D^3=\{(1,1,1),(1,1,2),(1,1,3),\dots ,(3,3,3)\}.$

Oro har, $D$ eremuak $m$ elementu baditu, $D^n$ multzoak $m^n$ $n$-kote izango ditu.

Orain, $P(x,y,z)$ formulatik $x$, $y$, $z$ aldagaiak $D^3$ multzoaren $(d_1,d_2,d_3)$ hirukotearen balioez ordezkatzean lortzen den proposizioa egiazkoa edo faltsua izango da (baina ez biak). Hori $D^3$ multzoaren hirukote bakoitzarekin gertatuko da; beraz, 3 aritateko $P$ predikatuari $\phi$ funtzio bat esleitu ahal izango diogu; funtzio horrek $D^3$ multzoaren hirukote bakoitzari $E$ edo $F$ balioa esleituko dio, hau da, $\phi :D^3⟶\{E,F\}$ funtzio bat izango dugu.

Adibidez, $D=\{1,2\}$ bada, demagun $P(1,1,1)$, $P(1,2,1)$, $P(1,2,2)$ proposizioei $E$ balioa esleitzen diegula, eta gainerakoei $F$ balioa. Orduan, $P$ predikatuari esleitzen diogun funtzioa hau da:

$\begin{array}{cccc}\phi :& D^3& \to & \{E,F\}\\ & 111& \mapsto & E\\ & 112& \mapsto & F\\ & 121& \mapsto & E\\ & 122& \mapsto & E\\ & 211& \mapsto & F\\ & 212& \mapsto & F\\ & 221& \mapsto & F\\ & 222& \mapsto & F\end{array}$

$D^3$ zutabean $111,112,\mathrm{...}$ idatzi dugu, $(1,1,1),(1,1,2),\mathrm{...}$ idatzi beharrean, idazkera sinplifikatzeko asmoz. Horrela egingo dugu nahasteko arriskurik ez dagoenean.

Funtzio horri 3 aritateko funtzio logiko deituko diogu, eta honela adieraziko dugu:

$\begin{array}{cc}{D}^3& \phi \\ 111& E\\ 112& F\\ 121& E\\ 122& E\\ 211& F\\ 212& F\\ 221& F\\ 222& F\end{array}$

$D=\{1,2\}$ eremuaren kasuan 3 aritateko $2^8=256$ funtzio logiko daude $P$ predikatuari esleitu ahal izateko:

$\begin{array}{cccccc}{D}^3& {\phi }_1& {\phi }_2& {\phi }_3& \dots & {\phi }_{256}\\ 111& E& E& E& \dots & F\\ 112& E& E& E& \dots & F\\ 121& E& E& E& \dots & F\\ 122& E& E& E& \dots & F\\ 211& E& E& E& \dots & F\\ 212& E& E& E& \dots & F\\ 221& E& E& F& \dots & F\\ 222& E& F& E& \dots & F\end{array}$

Antzera, $P$ $n$ aritateko predikatu bakoitzari $n$ aritateko funtzio logiko bat esleituko diogu, $\phi :D^n⟶\{E,F\}$.

$D$ eremuak $m$ elementu baditu, $D^n$ multzoak $m^n$ elementu izango ditu; eta, beraz, $n$ aritateko $2^{(m^n)}$ funtzio logiko daude.

2.14 Adibideak.

1. Izan bedi $D=\{1,2\}$ eremua, $m=2$.

   $n=1$ aritateko 4 funtzio logikoak:

   $\begin{array}{ccccc}D& {\phi }_1& {\phi }_2& {\phi }_3& {\phi }_4\\ 1& E& E& F& F\\ 2& E& F& E& F\end{array}$

   $n=2$ aritateko 16 funtzio logikoak:

   $\begin{array}{cccccc}{D}^2& {\phi }_1& {\phi }_2& {\phi }_3& \dots & {\phi }_{16}\\ 11& E& E& E& \dots & F\\ 12& E& E& E& \dots & F\\ 21& E& E& F& \dots & F\\ 22& E& F& E& \dots & F\end{array}$

2. Izan bedi $D=\{1,2,3\}$ eremua, $m=3$.

   $n=2$ aritateko 512 funtzio logikoak:

   $\begin{array}{ccccc}{D}^2& {\phi }_1& {\phi }_2& \dots & {\phi }_{512}\\ 11& E& E& \dots & F\\ 12& E& E& \dots & F\\ 13& E& E& \dots & F\\ 21& E& E& \dots & F\\ 22& E& E& \dots & F\\ 23& E& E& \dots & F\\ 31& E& E& \dots & F\\ 32& E& E& \dots & F\\ 33& E& F& \dots & F\end{array}$

2.15 Definizioa. $A$ ongi eratutako formula baten interpretazio bat emateko $D$ eremu ez-huts bat hartuko dugu eta $A$ formulan agertzen diren konstanteei, aldagai askeei eta predikatu-sinboloei balioak esleituko dizkiegu honela:

1. konstante bakoitzari $D$ eremuaren elementu bat esleituko diogu;
2. aldagai aske bakoitzari $D$ eremuaren elementu bat esleituko diogu;
3. $n$ aritateko predikatu-sinbolo bakoitzari $n$ aritateko funtzio logiko bat esleituko diogu.

Batzuetan, $D$ eremua azpimarratzeko, $D$ eremuaren gaineko interpretazioaz hitz egingo dugu.

2.16 Adibidea. $A=P(x)\wedge \mathrm{\forall }xQ(x,a)$.

Konstanteak: $a$.

Aldagai askeak: $x$.

Predikatu-sinboloak: $P$, $Q$; $ar(P)=1$, $ar(Q)=2$.

Dauden interpretazio guztien artean hona hemen bi:

1. ${\displaystyle }$ $\begin{array}{cccc}D=\{1,2\}& \begin{array}{cccc}x& a& P& Q\\ 1& 2& \alpha & \beta \end{array}& \begin{array}{cc}D& \alpha \\ 1& E\\ 2& F\end{array}& \begin{array}{cc}{D}^2& \beta \\ 11& E\\ 12& F\\ 21& F\\ 22& E\end{array}\end{array}$
2. ${\displaystyle }$ $\begin{array}{cccc}D=\{1,2\}& \begin{array}{cccc}x& a& P& Q\\ 2& 2& \alpha & \beta \end{array}& \begin{array}{cc}D& \alpha \\ 1& E\\ 2& E\end{array}& \begin{array}{cc}{D}^2& \beta \\ 11& E\\ 12& F\\ 21& F\\ 22& E\end{array}\end{array}$

2.17 Definizioa. $G$ ongi eratutako formula bat eta $G$ formularen $D$ eremuaren gaineko $I$ interpretazio bat izanik, $G$ formularen egia-balioa $I$ interpretaziorako honela kalkulatuko dugu:

1. $G=(\mathrm{\neg }A)$, $G=(A\wedge B)$, $G=(A\vee B)$, $G=(A\to B)$ edo $G=(A\leftrightarrow B)$ bada, egia-balioa proposizio-logikan bezala kalkulatuko dugu.

2. $G=(\mathrm{\forall }xA)$ edo $G=(\mathrm{\exists }xA)$ bada, $A$ formularen egia-balioa kalkulatuko dugu $x$ aldagaiak $A$ formulan duen agerpen aske bakoitza $D$ eremuaren elementu guztiez ordezkatuz; horrela, $x$ aldagaiaren funtzio logiko bat lortuko dugu:
   $\begin{array}{cc}x& A^{\ast }\\ 1& E\\ 2& F\\ ⋮& ⋮\end{array}$
   $V(\mathrm{\forall }xA,I)=E$ da funtzio logiko horrek $E$ balioa hartzen badu $D$ eremuaren elementu guztietarako, hau da, $A^{\ast }$ zutabean dena $E$ bada. Bestela, hau da, $A^{\ast }$ zutabean gutxienez $F$ bat badago, $V(\mathrm{\forall }xA,I)=F$.

   $V(\mathrm{\exists }xA,I)=E$ da funtzio logiko horrek $E$ balioa hartzen badu gutxienez $D$ eremuaren elementu baterako, hau da, $A^{\ast }$ zutabean gutxienez $E$ bat badago. Bestela, hau da, $A^{\ast }$ zutabean dena $F$ bada, $V(\mathrm{\exists }xA,I)=F$.

2.18 Adibideak.

1. $A=\mathrm{\forall }xP(x)$

   $A$ formularen $I$ interpretazio bat emateko $D$ eremu bat hartuko dugu eta $P$ predikatu-sinboloari 1 aritateko $\alpha$ funtzio logiko bat esleituko diogu. Bi elementuko eremu baten gainean 1 aritateko lau funtzio logiko daude. Konstanterik eta aldagai askerik ez dagoenez, eta 1 aritateko predikatu bakarra dagoenez, guztira lau interpretazio izango ditugu (bi elementuko eremu baten gainean). Hona hemen horietako bat:
   $\begin{array}{cccc}I:& D=\{1,2\}& \begin{array}{c}P\\ \alpha \end{array}& \begin{array}{cc}D& \alpha \\ 1& E\\ 2& F\end{array}\end{array}$
   $V(A,I)$ kalkulatzeko honela jokatuko dugu:

   1. Funtzio logikoa formulan ordezkatu: $A^{\ast }=\mathrm{\forall }x\alpha (x)$.

   2. Formula $\mathrm{\forall }x$ (zenbatzaile) motakoa denez, zenbatzailearen ($\alpha (x)$) irismenaren egia-balioa kalkulatuko dugu $x$ aldagaiak $\alpha (x)$ adierazpenean duen agerpen aske bakoitza $D$ eremuaren elementu bakoitzaz ordezkatuz:
      $\begin{array}{cc}x& \alpha (x)\\ 1& \alpha (1)=E\\ 2& \alpha (2)=F\end{array}$
      Taulan $F$ bat agertzen denez, $\mathrm{\forall }x\alpha (x)=F$ da.

   Hau da, $V(A,I)=F$ da.

2. $A=\mathrm{\exists }x\mathrm{\neg }P(x)$

   Bi elementuko eremu baten gainean lau interpretazio daude. Har dezagun $A$ formularen interpretazio hau:
   $\begin{array}{cccc}I:& D=\{1,2\}& \begin{array}{c}P\\ \alpha \end{array}& \begin{array}{cc}D& \alpha \\ 1& F\\ 2& E\end{array}\end{array}$

   1. Funtzio logikoa formulan ordezkatu: $A^{\ast }=\mathrm{\exists }x\mathrm{\neg }\alpha (x)$.

   2. Formula $\mathrm{\exists }x$ (zenbatzaile) motakoa denez, zenbatzailearen ($\mathrm{\neg }\alpha (x)$) irismenaren egia-balioa kalkulatuko dugu $x$ aldagaiak $\mathrm{\neg }\alpha (x)$ adierazpenean duen agerpen aske bakoitza $D$ eremuaren elementu bakoitzaz ordezkatuz. Bestalde, $\mathrm{\neg }\alpha (x)$ adierazpena $\mathrm{\neg }$ motakoa da, beraz, proposizio-logikan bezala kalkulatuko dugu:
      $\begin{array}{ccc}x& \alpha (x)& \mathrm{\neg }\alpha (x)\\ 1& \alpha (1)=F& E\\ 2& \alpha (2)=E& F\end{array}$
      Taulan $E$ bat agertzen denez, $\mathrm{\exists }x\mathrm{\neg }\alpha (x)=E$ da.

   Beraz, $V(A,I)=E$ da.

3. $A=P(x)\vee \mathrm{\forall }y(P(y)\to Q(a))$

   $2\cdot 2\cdot 4\cdot 4=64$ interpretazio daude bi elementuko eremu baten gainean (aldagai aske bat, konstante bat eta bi predikatu-sinbolo). Interpretazio hau hartuko dugu:
   $\begin{array}{ccccc}I:& D=\{1,2\}& \begin{array}{cccc}x& a& P& Q\\ 2& 1& \alpha & \beta \end{array}& \begin{array}{cc}D& \alpha \\ 1& E\\ 2& F\end{array}& \begin{array}{cc}D& \beta \\ 1& F\\ 2& F\end{array}\end{array}$

   1. $A^{\ast }=\alpha (2)\vee \mathrm{\forall }y(\alpha (y)\to \beta (1))=F\vee \mathrm{\forall }y(\alpha (y)\to F)$.

   2. $\mathrm{\forall }y(\alpha (y)\to F)$ kalkulatu behar dugu:
      $\begin{array}{ccc}y& \alpha (y)& \alpha (y)\to F\\ 1& \alpha (1)=E& F\\ 2& \alpha (2)=F& E\end{array}$
      $\mathrm{\forall }y$ motakoa denez, eta taulan $F$ bat agertzen denez, $\mathrm{\forall }y(\alpha (y)\to F)=F$ da.

      Eta, hortik, $A^{\ast }=F\vee F=F$ da.

   Beraz, $V(A,I)=F$ da.

4. $A=\mathrm{\forall }x\mathrm{\exists }yP(x,y)$

   $D=\{1,2,3\}$ eremuaren gainean $2^9=512$ interpretazio daude; hau hartuko dugu:
   $\begin{array}{cccc}I:& D=\{1,2,3\}& \begin{array}{c}P\\ \alpha \end{array}& \begin{array}{cc}{D}^2& \alpha \\ 11& E\\ 12& E\\ 13& F\\ 21& F\\ 22& E\\ 23& E\\ 31& F\\ 32& F\\ 33& E\end{array}\end{array}$

   1. $A^{\ast }=\mathrm{\forall }x\mathrm{\exists }y\alpha (x,y)$.

   2. $\mathrm{\forall }x\mathrm{\exists }y\alpha (x,y)$ kalkulatu behar dugu; hona hemen dagokion taula:
      $\begin{array}{cc}x& \mathrm{\exists }y\alpha (x,y)\\ 1& \mathrm{\exists }y\alpha (1,y)\\ 2& \mathrm{\exists }y\alpha (2,y)\\ 3& \mathrm{\exists }y\alpha (3,y)\end{array}$
      $\mathrm{\exists }y\alpha (1,y)$ adierazpena $\mathrm{\exists }y$ motakoa denez, dagokion taula eraiki beharko dugu; eta berdin $\mathrm{\exists }y\alpha (2,y)$ eta $\mathrm{\exists }y\alpha (3,y)$ adierazpenekin. Beraz, taula baten barnean hiru taula izango ditugu; honela:
      $\begin{array}{ccc}x& & \mathrm{\exists }y\alpha (x,y)\\ 1& \begin{array}{cc}y& \alpha (1,y)\\ 1& \alpha (1,1)=E\\ 2& \alpha (1,2)=E\\ 3& \alpha (1,3)=F\end{array}\}& \mathrm{\exists }y\alpha (1,y)=E\\ 2& \begin{array}{cc}y& \alpha (2,y)\\ 1& \alpha (2,1)=F\\ 2& \alpha (2,2)=E\\ 3& \alpha (2,3)=E\end{array}\}& \mathrm{\exists }y\alpha (2,y)=E\\ 3& \begin{array}{cc}y& \alpha (3,y)\\ 1& \alpha (3,1)=F\\ 2& \alpha (3,2)=F\\ 3& \alpha (3,3)=E\end{array}\}& \mathrm{\exists }y\alpha (3,y)=E\end{array}$
      $\mathrm{\forall }x$ motakoa denez, eta (eskuineko) taulan dena $E$ denez, $\mathrm{\forall }x\mathrm{\exists }y\alpha (x,y)=E$ da.

   Hortaz, $V(A,I)=E$ da.

2.4 Baliozkotasuna. Inkontsistentzia. Ondorio logikoak

Baliozkotasunaren, kontsistentziaren eta ondorio logikoaren definizioek bere horretan diraute, proposizio-logikan bezala.

2.19 Definizioa. $A$ formula bat tautologia edo baliozkoa da $A$ formularen interpretazio guztietarako egiazkoa bada. $A$ formula baliogabea da ez bada baliozkoa.

$A$ formula bat kontsistentea da gutxienez $A$ formularen interpretazio baterako egiazkoa bada. $A$ formula bat inkontsistentea edo kontraesana da ez bada kontsistentea.

2.20 Definizioa. $A_1,\dots ,A_n$ eta $B$ formulak izanik, $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa dela edo formuletatik logikoki deduzitzen dela esango dugu $V(A_1,I)=E$, $\cdots$, $V(A_n,I)=E$ egiten duen edozein $I$ interpretaziotarako $V(B,I)=E$ ere bada. Eta honela adieraziko dugu:

$A_1,\dots ,A_n\Rightarrow B\text{ edo }{A}_1,\dots ,A_n\models B.$

2.21 Definizioa. $P_1,\dots ,P_n/\dot{\mathrm{..}}C$ argumentu bat baliozkoa da $C$ ondorioa premisen ondorio logikoa bada. Hau da, $V(P_1,I)=E$, $\cdots$, $V(P_n,I)=E$ egiten duen edozein $I$ interpretaziotarako $V(C,I)=E$ ere bada. Argumentua baliogabea da ez bada baliozko argumentua.

Teorema hauek ere betetzen dira:

2.22 Teorema.

1. $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa da baldin eta soilik baldin $\models (A_1\wedge \cdots \wedge A_n\to B)$ bada.
2. $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa da baldin eta soilik baldin $A_1\wedge \cdots \wedge A_n\wedge \mathrm{\neg }B$ formula inkontsistentea bada.

Hala eta guztiz ere, predikatu-logikaren egoera eta proposizio-logikaren egoera zeharo desberdinak dira. Azken horretan edozein formularen egia-taula eraikitzea posiblea den bitartean, predikatu-logikan ez da hori beti posible.

Predikatu-logikan, eremua finitua denean, egia-taula eraiki dezakegu, teorikoki bada ere. Baina formula bat baliozkoa izateko, edozein eremuren gaineko edozein interpretaziotarako egiazkoa izan behar du, eremu infinituak barne. Berdin formula inkontsistenteekin, baliogabeekin...

Dena dela, formula bat baliozkoa edo kontsistentea den ala ez arrazoi dezakegu egia-taula lerroz lerro eraiki gabe.

2.23 Adibideak.

1. Ikus dezagun $A=\mathrm{\exists }x(P(x)\wedge \mathrm{\neg }P(x))$ formula inkontsistentea dela.

   Izan bitez $D$ edozein eremu ez-huts eta $I$ edozein interpretazio eremu horren gainean.
   $\begin{array}{cccc}I:& D& \begin{array}{c}P\\ \alpha \end{array}& \begin{array}{cc}D& \alpha \\ 1& ?\\ ⋮& ⋮\end{array}\end{array}$

   1. $A^{\ast }=\mathrm{\exists }x(\alpha (x)\wedge \mathrm{\neg }\alpha (x))$.

   2. $\mathrm{\exists }x(\alpha (x)\wedge \mathrm{\neg }\alpha (x))$ kalkulatu behar dugu.
      $\begin{array}{cccc}x& \alpha (x)& \mathrm{\neg }\alpha (x)& \alpha (x)\wedge \mathrm{\neg }\alpha (x)\\ 1& \alpha (1)=?& \mathrm{\neg }?& ?\wedge \mathrm{\neg }?=F\\ ⋮& ⋮& ⋮& ⋮\end{array}$
      $\mathrm{\exists }x$ motakoa denez eta taulan dena $F$ denez, $\mathrm{\exists }x(\alpha (x)\wedge \mathrm{\neg }\alpha (x))=F$ izango da.

   Beraz, $V(A,I)=F$ da, non $I$ edozein interpretazio eta $D$ edozein eremu diren. Hortaz, $A$ formula inkontsistentea da.

2. Ikus dezagun $A=P(y)\to \mathrm{\forall }xP(x)$ formula baliogabea dela.

   Horretarako nahikoa da $V(A,I)=F$ betetzen duen $I$ interpretazio bat bilatzea.

   Proba dezagun $D=\{1\}$ eremuarekin. $\begin{array}{cccc}I:& D=\{1\}& \begin{array}{cc}y& P\\ 1& \alpha \end{array}& \begin{array}{cc}D& \alpha \\ 1& ?\end{array}\end{array}$

   1. $A^{\ast }=\alpha (1)\to \mathrm{\forall }x\alpha (x)$.

   2. $A^{\ast }=F$ izateko, $\alpha (1)=E$ eta $\mathrm{\forall }x\alpha (x)=F$ bete behar dira. Orduan, 1 aritateko funtzio logiko hau daukagu:
      $\begin{array}{cc}D& \alpha \\ 1& E\end{array}$
      Orduan, taula hau izango genuke:
      $\begin{array}{cc}x& \alpha (x)\\ 1& \alpha (1)=E\end{array}$
      Taulan dena $E$ denez, $\mathrm{\forall }x\alpha (x)=E$ izango da.

   Beraz, $D=\{1\}$ eremurako ezin izan dugu aurkitu $A$ formula faltsutzen duen interpretaziorik ($A$ formula kontsistentea da).

   Proba dezagun $D=\{1,2\}$ eremuarekin.
   $\begin{array}{cccc}I:& D=\{1,2\}& \begin{array}{cc}y& P\\ d& \alpha \end{array}& \begin{array}{cc}D& \alpha \\ 1& ?\\ 2& ?\end{array}\end{array}$ ($d$ $D$ eremuaren elementu bat da)

   1. $A^{\ast }=\alpha (d)\to \mathrm{\forall }x\alpha (x)$.

   2. $A^{\ast }=F$ izateko, $\alpha (d)=E$ eta $\mathrm{\forall }x\alpha (x)=F$ bete behar dira. Biak bete daitezen:
      $\begin{array}{ccc}x& \alpha (x)& \\ 1& \alpha (1)& F\text{ bat eta }E\text{ bat}\\ 2& \alpha (2)& \end{array}$

   Har dezagun, adibidez, interpretazio hau:
   $\begin{array}{cccc}I:& D=\{1,2\}& \begin{array}{cc}y& P\\ 1& \alpha \end{array}& \begin{array}{cc}D& \alpha \\ 1& E\\ 2& F\end{array}\end{array}$
   Egiaztapena:

   1. $A^{\ast }=\alpha (d)\to \mathrm{\forall }x\alpha (x)$.

   2. Interpretazio honetarako $\alpha (1)=E$ eta $\mathrm{\forall }x\alpha (x)=F$ dauzkagu, taula honetan $F$ bat dagoelako: $\begin{array}{cc}x& \alpha (x)\\ 1& \alpha (1)=E\\ 2& \alpha (2)=F\end{array}$
      Beraz, $A^{\ast }=E\to F=F$ da.

   Ondorioz, $V(A,I)=F$ da eta $A$ formula baliogabea da.

3. Ikus dezagun $B=Q(a)$ formula $A_1=\mathrm{\forall }x(P(x)\to Q(x))$ eta $A_2=P(a)$ formulen ondorio logikoa dela.

   Horretarako frogatu beharko dugu $V(A_1,I)=V(A_2,I)=E$ bada, $V(B,I)=E$ ere izango dela, edozein $I$ interpretaziotarako.

   Izan bitez $D$ edozein eremu eta $I$ edozein interpretazio $D$ eremuaren gainean, non $V(A_1,I)=V(A_2,I)=E$ den.
   $\begin{array}{ccccc}I:& D& \begin{array}{ccc}a& P& Q\\ d& \alpha & \beta \end{array}& \begin{array}{cc}D& \alpha \\ 1& ?\\ ⋮& ⋮\end{array}& \begin{array}{cc}D& \beta \\ 1& ?\\ ⋮& ⋮\end{array}\end{array}$
   $A_1^{\ast }=\mathrm{\forall }x(\alpha (x)\to \beta (x))$.

   $A_2^{\ast }=\alpha (d)$.

   $A_2^{\ast }=E$ izateko $\alpha (d)=E$ bete behar da; beraz, $\alpha$ funtzioaren taulan, errenkada bat honelakoa izango da:
   $\underset{\text{errenkada}}{\underbrace{d\alpha (d)=E}}$

   $A_1^{\ast }=E$ denez, $\alpha (x)\to \beta (x)$ adierazpenaren taularen errenkada guztietan $E$ agertuko da. Horien artean, $d$ duen errenkada:
   $\underset{\text{errenkada}}{\underbrace{d\alpha (d)\to \beta (d)=E}}$

   $B^{\ast }=\beta (d)$.

   $\alpha (d)\to \beta (d)=E$ eta $\alpha (d)=E$ direnez, $\beta (d)=E$ bete beharko da.

   Hortaz, $V(B,I)=E$ eta $B$ formula $A_1$ eta $A_2$ formulen ondorio logikoa da.

4. Ikus dezagun argumentu hau baliogabea dela:
   $\begin{array}{c}{A}_1=\mathrm{\forall }x(P(x)\to \mathrm{\neg }Q(x))\\ A_2=\mathrm{\exists }x(R(x)\wedge Q(x))\\ B=\mathrm{\forall }x(P(x)\to R(x))\end{array}$
   Argumentu bat baliogabea dela frogatzeko nahikoa da frogatzea ondorioa ez dela premisen ondorio logikoa. Hau da, nahikoa da premisak egiazko egiten dituen eta ondorioa faltsutzen duen interpretazio bat aurkitzea.

   Proba dezagun $D=\{1\}$ eremuarekin.
   $\begin{array}{cccccc}I:& D& \begin{array}{ccc}P& Q& R\\ \alpha & \beta & \gamma \end{array}& \begin{array}{cc}D& \alpha \\ 1& ?\end{array}& \begin{array}{cc}D& \beta \\ 1& ?\end{array}& \begin{array}{cc}D& \gamma \\ 1& ?\end{array}\end{array}$

   $A_1^{\ast }=\mathrm{\forall }x(\alpha (x)\to \mathrm{\neg }\beta (x))$.

   $A_1^{\ast }=E$ izateko, $\begin{array}{cc}x& \alpha (x)\to \mathrm{\neg }\beta (x)\\ 1& \alpha (1)\to \mathrm{\neg }\beta (1)=E\end{array}$ bete behar da.

   $A_2^{\ast }=\mathrm{\exists }x(\gamma (x)\wedge \beta (x))$.

   $A_2^{\ast }=E$ izateko, $\begin{array}{cc}x& \gamma (x)\wedge \beta (x)\\ 1& \gamma (1)\wedge \beta (1)=E\end{array}$ bete behar da.

   Hortaz, azkenekotik, $\gamma (1)=E$ eta $\beta (1)=E$ dira. $\beta (1)=E$ denez, $\mathrm{\neg }\beta (1)=F$ da eta, $\alpha (1)\to \mathrm{\neg }\beta (1)=E$ bete behar denez, $\alpha (1)=F$ aterako dugu. Eta $B^{\ast }$ adierazpenerako, taula hau daukagu:
   $\begin{array}{cc}x& \alpha (x)\to \gamma (x)\\ 1& \alpha (1)\to \gamma (1)=E\end{array}$
   eta, hortaz, $B^{\ast }=E$ da.

   Ondorioz, $D=\{1\}$ eremuarekin ezin izan dugu aurkitu $A_1$ eta $A_2$ egiazko eta $B$ faltsu egiten dituen interpretaziorik.

   Proba dezagun $D=\{1,2\}$ eremuarekin.

   $\begin{array}{cccccc}I:& D& \begin{array}{ccc}P& Q& R\\ \alpha & \beta & \gamma \end{array}& \begin{array}{cc}D& \alpha \\ 1& ?\\ 2& ?\end{array}& \begin{array}{cc}D& \beta \\ 1& ?\\ 2& ?\end{array}& \begin{array}{cc}D& \gamma \\ 1& ?\\ 2& ?\end{array}\end{array}$

   $A_1^{\ast }=\mathrm{\forall }x(\alpha (x)\to \mathrm{\neg }\beta (x))$.

   $A_1^{\ast }=E$ izateko,

   $\begin{array}{cc}x& \alpha (x)\to \mathrm{\neg }\beta (x)\\ 1& \alpha (1)\to \mathrm{\neg }\beta (1)=E\\ 2& \alpha (2)\to \mathrm{\neg }\beta (2)=E\end{array}\text{ bete behar da.}\text{ (1. taula)}$

   $A_2^{\ast }=\mathrm{\exists }x(\gamma (x)\wedge \beta (x))$.

   $A_2^{\ast }=E$ izateko,

   $\begin{array}{cc}x& \gamma (x)\wedge \beta (x)\\ 1& \gamma (1)\wedge \beta (1)\\ 2& \gamma (2)\wedge \beta (2)\end{array}\text{ batek }E\text{ izan behar du.}\text{ (2. taula)}$

   $B^{\ast }=\mathrm{\forall }x(\alpha (x)\to \gamma (x))$.

   $B^{\ast }=F$ izateko,

   $\begin{array}{cc}x& \alpha (x)\to \gamma (x)\\ 1& \alpha (1)\to \gamma (1)\\ 2& \alpha (2)\to \gamma (2)\end{array}\text{ batek }F\text{ izan behar du.}\text{ (3. taula)}$

   2. taula betetzeko, nahikoa da $\gamma (1)=\beta (1)=E$ betetzea ($\mathrm{\neg }\beta (1)=F$). Orduan, 1. taula betetzeko, $\alpha (1)\to \mathrm{\neg }\beta (1)=E$ izan behar denez, $\alpha (1)=F$ aterako dugu. Eta hortik $\alpha (1)\to \gamma (1)=E$ daukagu, hau da, 3. taula taulako lehenengo errenkadan $E$ dugu.

   Hortaz, 3. taula betetzeko, $\alpha (2)\to \gamma (2)=F$ bete behar da, hau da, $\alpha (2)=E$ eta $\gamma (2)=F$. Orain, 1. taula betetzeko, $\alpha (2)=E$ denez, $\alpha (2)\to \mathrm{\neg }\beta (2)=E$ izateko, $\mathrm{\neg }\beta (2)=E$ edo $\beta (2)=F$ izango dira.

   Laburbilduz, hona hemen $A_1$ eta $A_2$ egiazko eta $B$ faltsu egiten dituen interpretazio bat:
   $\begin{array}{cccccc}I:& D& \begin{array}{ccc}P& Q& R\\ \alpha & \beta & \gamma \end{array}& \begin{array}{cc}D& \alpha \\ 1& F\\ 2& E\end{array}& \begin{array}{cc}D& \beta \\ 1& E\\ 2& F\end{array}& \begin{array}{cc}D& \gamma \\ 1& E\\ 2& F\end{array}\end{array}$

   Egiaztapena:

   $\begin{array}{cc}{A}_1^{\ast }=\mathrm{\forall }x(\alpha (x)\to \mathrm{\neg }\beta (x))& \begin{array}{ccccc}x& \alpha (x)& \beta (x)& \mathrm{\neg }\beta (x)& \alpha (x)\to \mathrm{\neg }\beta (x))\\ 1& F& E& F& E\\ 2& E& F& E& E\end{array}\end{array}$

   $\begin{array}{cc}{A}_2^{\ast }=\mathrm{\exists }x(\gamma (x)\wedge \beta (x))& \begin{array}{cccc}x& \gamma (x)& \beta (x)& \gamma (x)\wedge \beta (x)\\ 1& E& E& E\\ 2& F& F& F\end{array}\end{array}$

   $\begin{array}{cc}{B}^{\ast }=\mathrm{\forall }x(\alpha (x)\to \gamma (x))& \begin{array}{cccc}x& \alpha (x)& \gamma (x)& \alpha (x)\to \gamma (x)\\ 1& F& E& E\\ 2& E& F& F\end{array}\end{array}$

   Beraz, $V(A_1,I)=V(A_2,I)=E$ eta $V(B,I)=F$ betetzen dira. Eta argumentua baliogabea da.

2.5 Baliokidetza logikoak

2.24 Definizioa. $A$ eta $B$ ongi eratutako bi formulak logikoki baliokideak dira ($A\equiv B$) egia-balio berberak badituzte interpretazio guztietarako, $V(A,I)=V(B,I)$.

Ondorioak.

1. Proposizio-logikaren baliokidetza logikoek bere horretan diraute predikatu-logikan.
2. $A\equiv B$ da baldin eta soilik baldin $\models (A\leftrightarrow B)$ bada.

Horietaz gain, predikatu-logikan baliokidetza gehiago dauzkagu.

Idazkera.

• $A[x]$, $B[x]$: $x$ aldagaia aske duten formulak dira. Adibideak:

  $A[x]=P(x)$, $A[x]=\mathrm{\forall }y(P(x)\wedge Q(y)\to \mathrm{\exists }xR(x,x))$, $A[x]=P(x)\to \mathrm{\forall }yP(y)$, etab.

• $J$: $x$ aldagaia aske ez duen formula da. Adibideak:

  $J=\mathrm{\forall }yP(y)$, $J=\mathrm{\forall }xP(x)\to Q(y)$, etab.

• $A^{\ast }[x]$, $J^{\ast }$: $I$ interpretazio bat $A[x]$, $J$ formuletan ordezkatzean lortzen diren adierazpenak dira.

Zenbatzaileen baliokidetzak.

1. $\mathrm{\neg }\mathrm{\forall }xA[x]\equiv \mathrm{\exists }x\mathrm{\neg }A[x]$.

2. $\mathrm{\forall }x\mathrm{\neg }A[x]\equiv \mathrm{\neg }\mathrm{\exists }xA[x]$.

3. $\mathrm{\forall }xA[x]\wedge \mathrm{\forall }xB[x]\equiv \mathrm{\forall }x(A[x]\wedge B[x])$, $\mathrm{\forall }$ zenbatzailea banakorra da $\wedge$ lokailuarekiko.

4. $\mathrm{\exists }xA[x]\vee \mathrm{\exists }xB[x]\equiv \mathrm{\exists }x(A[x]\vee B[x])$, $\mathrm{\exists }$ zenbatzailea banakorra da $\vee$ lokailuarekiko.

5. 1. $\mathrm{\forall }xA[x]\vee J\equiv \mathrm{\forall }x(A[x]\vee J)$.

   2. $\mathrm{\exists }xA[x]\vee J\equiv \mathrm{\exists }x(A[x]\vee J)$.

6. 1. $\mathrm{\forall }xA[x]\wedge J\equiv \mathrm{\forall }x(A[x]\wedge J)$.

   2. $\mathrm{\exists }xA[x]\wedge J\equiv \mathrm{\exists }x(A[x]\wedge J)$.

Ez dira baliokideak.

EB1

$\mathrm{\forall }xA[x]\vee \mathrm{\forall }xB[x]\equiv ̸\mathrm{\forall }x(A[x]\vee B[x])$, $\mathrm{\forall }$ zenbatzailea ez da banakorra $\vee$ lokailuarekiko.

EB2

$\mathrm{\exists }xA[x]\wedge \mathrm{\exists }xB[x]\equiv ̸\mathrm{\exists }x(A[x]\wedge B[x])$, $\mathrm{\exists }$ zenbatzailea ez da banakorra $\wedge$ lokailuarekiko.

Froga.

1. $G=\mathrm{\neg }\mathrm{\forall }xA[x]\equiv \mathrm{\exists }x\mathrm{\neg }A[x]=H$ dela frogatzeko ikusi behar dugu edozein $I$ interpretaziotarako $V(G,I)=V(H,I)$ betetzen dela.

   Izan bitez $D$ edozein eremu eta $I$ edozein interpretazio $D$ eremuaren gainean.

   $I$ interpretazioa $G$ eta $H$ formuletan ordezkatuz, $G^{\ast }=\mathrm{\neg }\mathrm{\forall }x{A}^{\ast }[x]$ eta $H^{\ast }=\mathrm{\exists }x\mathrm{\neg }{A}^{\ast }[x]$ adierazpenak lortuko ditugu, hurrenez hurren.

   Bi aukerak ditugu: a) $V(G,I)=E$. b) $V(G,I)=F$.

   a) $V(G,I)=E$ bada, $G^{\ast }=\mathrm{\neg }\mathrm{\forall }x{A}^{\ast }[x]=E$ izango da; orduan, $\mathrm{\forall }x{A}^{\ast }[x]=F$ izango da. Beraz, $A^{\ast }[x]$ adierazpenaren taulan honelako errenkada bat egongo da: $\underset{\_}{\overline{d{A}^{\ast }[d]=F}}$.

   $\mathrm{\neg }{A}^{\ast }[x]$ adierazpenaren errenkada hori honelakoa izango da: $\underset{\_}{\overline{d\mathrm{\neg }{A}^{\ast }[d]=E}}$. Beraz, $H^{\ast }=\mathrm{\exists }x\mathrm{\neg }{A}^{\ast }[x]=E$ beteko da.

   Hortaz, $V(H,I)=E=V(G,I)$ dugu.

   b) $V(G,I)=F$ bada, $G^{\ast }=\mathrm{\neg }\mathrm{\forall }x{A}^{\ast }[x]=F$ izango da; orduan, $\mathrm{\forall }x{A}^{\ast }[x]=E$ izango da. Beraz, $A^{\ast }[x]$ adierazpenaren taulan dena da $E$.

   $A^{\ast }[x]$ adierazpenaren taulan dena $E$ bada, $\mathrm{\neg }{A}^{\ast }[x]$ adierazpenaren taulan dena $F$ izango da. Beraz, $H^{\ast }=\mathrm{\exists }x\mathrm{\neg }{A}^{\ast }[x]=F$ da.

   Hortaz, $V(H,I)=F=V(G,I)$ da.

   Bi kasuetan, $V(G,I)=V(H,I)$ dugu, hau da, $G\equiv H$.

2. $G=\mathrm{\forall }x\mathrm{\neg }A[x]\equiv \mathrm{\neg }\mathrm{\exists }xA[x]=H$ dela frogatzeko baliokidetasun logikoaren definizioa erabil dezakegu, aurrekoan bezala, eta frogatu edozein $I$ interpretaziotarako $V(G,I)=V(H,I)$ betetzen dela.

   Baina, jadanik frogatu ditugun baliokidetzak ere erabil ditzakegu, aurrekoa eta proposizio-logikarenak.

   $G=\mathrm{\forall }x\mathrm{\neg }A[x]\stackrel{UB}{\equiv }\mathrm{\neg }(\mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }A[x])\stackrel{1.}{\equiv }\mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }\mathrm{\neg }A[x]\stackrel{UB}{\equiv }\mathrm{\neg }\mathrm{\exists }xA[x]=H$.

3. $G=\mathrm{\forall }xA[x]\wedge \mathrm{\forall }xB[x]\equiv \mathrm{\forall }x(A[x]\wedge B[x])=H$ dela frogatzeko baliokidetasun logikoaren definizioa erabiliko dugu.

   Izan bitez $D$ edozein eremu eta $I$ edozein interpretazio $D$ eremuaren gainean.

   $I$ interpretazioa $G$ eta $H$ formuletan ordezkatzean, $G^{\ast }=\mathrm{\forall }x{A}^{\ast }[x]\wedge \mathrm{\forall }x{B}^{\ast }[x]$ eta $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\wedge B^{\ast }[x])$ adierazpenak lortuko ditugu, hurrenez hurren.

   Bi aukerak ditugu: a) $G^{\ast }=E$. b) $G^{\ast }=F$.

   a) $G^{\ast }=E$ bada, $\mathrm{\forall }x{A}^{\ast }[x]=E$ eta $\mathrm{\forall }x{B}^{\ast }[x]=E$ izango dira. Beraz, $A^{\ast }[x]$ eta $B^{\ast }[x]$ adierazpenen tauletan errenkada guztiak dira $E$.

   Hortik, $A^{\ast }[x]\wedge B^{\ast }[x]$ adierazpenaren taularen errenkada guztietan $E$ agertuko da. Ondorioz, $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\wedge B^{\ast }[x])=E$ dugu.

   Hortaz, $V(H,I)=E=V(G,I)$ da.

   b) $G^{\ast }=F$ bada, beste bi aukera dauzkagu:
   b.1) $\mathrm{\forall }x{A}^{\ast }[x]=E$. b.2) $\mathrm{\forall }x{A}^{\ast }[x]=F$.

   b.1) $\mathrm{\forall }x{A}^{\ast }[x]=E$ bada, $G^{\ast }=F$ denez, $\mathrm{\forall }x{B}^{\ast }[x]=F$ izango da. Beraz, $B^{\ast }[x]$ adierazpenaren taulan honelako errenkada bat egongo da: $\underset{\_}{\overline{d{B}^{\ast }[d]=F}}$ .

   Errenkada hori bera baina orain $A^{\ast }[x]\wedge B^{\ast }[x]$ adierazpenaren taulan hau izango da: $\underset{\_}{\overline{d{A}^{\ast }[d]\wedge B^{\ast }[d]=F}}$. Beraz, $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\wedge B^{\ast }[x])=F$ beteko da.

   Ondorioz, $V(H,I)=F=V(G,I)$ dugu.

   b.2) $\mathrm{\forall }x{A}^{\ast }[x]=F$ bada, $A^{\ast }[x]$ adierazpenaren taularen errenkadaren batean hau izango dugu: $\underset{\_}{\overline{d{A}^{\ast }[d]=F}}$. $A^{\ast }[x]\wedge B^{\ast }[x]$ adierazpenaren taularen errenkada berean beste hau izango dugu: $\underset{\_}{\overline{d{A}^{\ast }[d]\wedge B^{\ast }[d]=F}}$.

   Hortaz, $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\wedge B^{\ast }[x])=F$ da.

   Ondorioz, $V(H,I)=F=V(G,I)$ betetzen da

   Hortaz, edozein $I$ interpretaziotarako $V(H,I)=V(G,I)$ daukagu, hau da, $G\equiv H$.

4. $G=\mathrm{\exists }xA[x]\vee \mathrm{\exists }xB[x]\equiv \mathrm{\exists }x(A[x]\vee B[x])=H$ betetzen dela frogatzeko jadanik frogatu ditugun baliokidetzak erabiliko ditugu.

   $G=\mathrm{\exists }xA[x]\vee \mathrm{\exists }xB[x]\stackrel{UB}{\equiv }\mathrm{\neg }(\mathrm{\neg }(\mathrm{\exists }xA[x]\vee \mathrm{\exists }xB[x]))\stackrel{DeM}{\equiv }\mathrm{\neg }(\mathrm{\neg }\mathrm{\exists }xA[x]\wedge \mathrm{\neg }\mathrm{\exists }xB[x])\stackrel{2.}{\equiv }\mathrm{\neg }(\mathrm{\forall }x\mathrm{\neg }A[x]\wedge \mathrm{\forall }x\mathrm{\neg }B[x])\stackrel{3.}{\equiv }\mathrm{\neg }\mathrm{\forall }x(\mathrm{\neg }A[x]\wedge \mathrm{\neg }B[x])\stackrel{1.}{\equiv }\mathrm{\exists }x\mathrm{\neg }(\mathrm{\neg }A[x]\wedge \mathrm{\neg }B[x])\stackrel{DeM}{\equiv }$

   $\mathrm{\exists }x(\mathrm{\neg }\mathrm{\neg }A[x]\vee \mathrm{\neg }\mathrm{\neg }B[x])\stackrel{UB}{\equiv }\mathrm{\exists }x(A[x]\vee B[x])=H$

5. 1. $G=\mathrm{\forall }xA[x]\vee J\equiv \mathrm{\forall }x(A[x]\vee J)=H$ betetzen dela frogatzeko baliokidetasun logikoaren definizioa erabiliko dugu.

   Izan bitez $D$ edozein eremu eta $I$ edozein interpretazio $D$ eremuaren gainean.

   $I$ interpretazioa $G$ eta $H$ bi formuletan ordezkatuz gero, $G^{\ast }=\mathrm{\forall }x{A}^{\ast }[x]\vee J^{\ast }$ eta $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\vee J^{\ast })$ adierazpenak lortuko ditugu, hurrenez hurren.

   Aukerak: a) $G^{\ast }=\mathrm{\forall }x{A}^{\ast }[x]\vee J^{\ast }=E$. b) $G^{\ast }=\mathrm{\forall }x{A}^{\ast }[x]\vee J^{\ast }=F$.

   a) $G^{\ast }=E$ bada, beste bi aukera ditugu: a.1) $J^{\ast }=E$. a.2) $J^{\ast }=F$.

   a.1) $J^{\ast }=E$ bada, $A^{\ast }[x]\vee J^{\ast }$ adierazpenaren taularen errenkada guztietan $E$ agertuko da. Beraz, $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\vee J^{\ast })=E$ izango da.

   Hortaz, $V(H,I)=E=V(G,I)$ beteko da.

   a.2) $J^{\ast }=F$ bada, $G^{\ast }=E$ denez, $\mathrm{\forall }x{A}^{\ast }[x]=E$ bete beharko da. Hau da, $A^{\ast }[x]$ adierazpenaren taularen errenkada guztietan $E$ agertuko da. Hortik, $A^{\ast }[x]\vee J^{\ast }$ adierazpenaren taularen errenkada guztietan $E$ agertuko da. Eta, horren ondorioz, $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\vee J^{\ast })=E$ izango da.

   Kasu honetan ere $V(H,I)=E=V(G,I)$ beteko da.

   b) $G^{\ast }=\mathrm{\forall }x{A}^{\ast }[x]\vee J^{\ast }=F$ bada, $\mathrm{\forall }x{A}^{\ast }[x]=F$ eta $J^{\ast }=F$ bete beharko dira. Lehenengotik aterako dugu $A^{\ast }[x]$ adierazpenaren taularen errenkadaren batean $F$ agertuko dela: $\underset{\_}{\overline{d{A}^{\ast }[d]=F}}$. $A^{\ast }[x]\vee J^{\ast }$ adierazpenaren taularen errenkada berean ere $F$ agertuko da: $\underset{\_}{\overline{d{A}^{\ast }[d]\vee J^{\ast }=F}}$. Ondorioz, $H^{\ast }=\mathrm{\forall }x(A^{\ast }[x]\vee J^{\ast })=F$ izango da.

   Kasu honetan $V(H,I)=F=V(G,I)$ dugu.

   Hortaz, edozein $I$ interpretaziotarako $V(H,I)=V(G,I)$ daukagu, hau da, $G\equiv H$.

   2. $G=\mathrm{\exists }xA[x]\vee J\equiv \mathrm{\exists }x(A[x]\vee J)=H$ betetzen dela frogatzeko baliokidetasun logikoaren definizioa erabiliko dugu berriro.

   Izan bitez $D$ edozein eremu eta $I$ edozein interpretazio $D$ eremuaren gainean.

   $I$ interpretazioa $G$ eta $H$ bi formuletan ordezkatuz gero, $G^{\ast }=\mathrm{\exists }x{A}^{\ast }[x]\vee J^{\ast }$ eta $H^{\ast }=\mathrm{\exists }x(A^{\ast }[x]\vee J^{\ast })$ adierazpenak lortuko ditugu, hurrenez hurren.

   Aukerak: a) $G^{\ast }=E$. b) $G^{\ast }=F$.

   a) $G^{\ast }=E$ bada, beste bi aukera ditugu: a.1) $J^{\ast }=E$ . a.2) $J^{\ast }=F$.

   a.1) $J^{\ast }=E$ bada, $A^{\ast }[x]\vee J^{\ast }$ adierazpenaren taulan dena $E$ izango da. Beraz, $H^{\ast }=\mathrm{\exists }x(A^{\ast }[x]\vee J^{\ast })=E$ izango da.

   Kasu honetan $V(H,I)=E=V(G,I)$ betetzen da.

   a.2) $J^{\ast }=F$ bada, $G^{\ast }=E$ denez, $\mathrm{\exists }x{A}^{\ast }[x]=E$ bete behar da. Beraz, $A^{\ast }[x]$ adierazpenaren taulan honelako errenkadaren bat egongo da: $\underset{\_}{\overline{d{A}^{\ast }[d]=E}}$ . Errenkada hori bera $A^{\ast }[x]\vee J^{\ast }$ adierazpenaren taulan hau izango da: $\underset{\_}{\overline{d{A}^{\ast }[d]\wedge J^{\ast }=E}}$. Beraz, $H^{\ast }=\mathrm{\exists }x(A^{\ast }[x]\vee J^{\ast })=E$ dugu.

   Kasu honetan ere $V(H,I)=E=V(G,I)$ betetzen da.

   b) $G^{\ast }=F$ bada, $\mathrm{\exists }x{A}^{\ast }[x]=F$ eta $J^{\ast }=F$ izango dira. Lehenengotik aterako dugu $A^{\ast }[x]$ adierazpenaren taulan dena $F$ dela. Beraz, $A^{\ast }[x]\vee J^{\ast }$ adierazpenaren taulan ere dena $F$ da. Hortaz, $H^{\ast }=\mathrm{\exists }x(A^{\ast }[x]\vee J^{\ast })=F$ izango da.

   Kasu honetan ere $V(H,I)=F=V(G,I)$ betetzen da.

   Ondorioz, edozein $I$ interpretaziotarako $V(H,I)=V(G,I)$ daukagunez, $G\equiv H$ betetzen da.

6. 6.1. eta 6.2. frogatzeko aurreko baliokidetza batzuk erabiliko ditugu.

   1. $\mathrm{\forall }xA[x]\wedge J\stackrel{UB}{\equiv }\mathrm{\neg }\mathrm{\neg }(\mathrm{\forall }xA[x]\wedge J)\stackrel{DeM}{\equiv }\mathrm{\neg }(\mathrm{\neg }\mathrm{\forall }xA[x]\vee \mathrm{\neg }J)\stackrel{1.}{\equiv }\mathrm{\neg }(\mathrm{\exists }x\mathrm{\neg }A[x]\vee \mathrm{\neg }J)\stackrel{\mathrm{5.2.}}{\equiv }\mathrm{\neg }\mathrm{\exists }x(\mathrm{\neg }A[x]\vee \mathrm{\neg }J)\stackrel{DeM}{\equiv }\mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }(A[x]\wedge J)\stackrel{2.}{\equiv }\mathrm{\forall }x\mathrm{\neg }(\mathrm{\neg }(A[x]\wedge J))\stackrel{UB}{\equiv }\mathrm{\forall }x(A[x]\wedge J).$

   2. $\mathrm{\exists }xA[x]\wedge J\stackrel{UB}{\equiv }\mathrm{\neg }\mathrm{\neg }(\mathrm{\exists }xA[x]\wedge J)\stackrel{DeM}{\equiv }\mathrm{\neg }(\mathrm{\neg }\mathrm{\exists }xA[x]\vee \mathrm{\neg }J)\stackrel{2.}{\equiv }\mathrm{\neg }(\mathrm{\forall }x\mathrm{\neg }A[x]\vee \mathrm{\neg }J)\stackrel{\mathrm{5.1.}}{\equiv }\mathrm{\neg }(\mathrm{\forall }x(\mathrm{\neg }A[x]\vee \mathrm{\neg }J))\stackrel{DeM}{\equiv }\mathrm{\neg }(\mathrm{\forall }x\mathrm{\neg }(A[x]\wedge J))\stackrel{1.}{\equiv }\mathrm{\exists }x\mathrm{\neg }\mathrm{\neg }(A[x]\wedge J)\stackrel{UB}{\equiv }\mathrm{\exists }x(A[x]\wedge J).$

Egiazta dezagun, orain, EB1 eta EB2 ez direla baliokidetzak.

• EB1

  $\mathrm{\forall }xA[x]\vee \mathrm{\forall }xB[x]\equiv ̸\mathrm{\forall }x(A[x]\vee B[x])$ dela frogatzeko ikus dezagun $A[x]=P(x)$ eta $B[x]=Q(x)$ direnean, $G=\mathrm{\forall }xP(x)\vee \mathrm{\forall }xQ(x)\equiv ̸\mathrm{\forall }x(P(x)\vee Q(x))=H$ dela.

  Horretarako nahikoa izango da $V(H,I)\ne V(G,I)$ betetzen duen $I$ interpretazio bat aurkitzea.

  Har dezagun interpretazio hau:
  $$\begin{array}{ccccc}I:& D=\{1,2\}& \begin{array}{cc}P& Q\\ \alpha & \beta \end{array}& \begin{array}{cc}D& \alpha \\ 1& E\\ 2& F\end{array}& \begin{array}{cc}D& \beta \\ 1& F\\ 2& E\end{array}\end{array}$$
  $G^{\ast }=\mathrm{\forall }x\alpha (x)\vee \mathrm{\forall }x\beta (x)$.

  $\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}x& \alpha (x)\\ 1& \alpha (1)=E\\ 2& \alpha (2)=F\end{array}\}& \mathrm{\forall }x\alpha (x)=F\end{array}& \begin{array}{cc}\begin{array}{cc}x& \beta (x)\\ 1& \beta (1)=F\\ 2& \beta (2)=E\end{array}\}& \mathrm{\forall }x\beta (x)=F\end{array}\end{array}$

  Beraz, $G^{\ast }=F\vee F=F$ betetzen da.

  $H^{\ast }=\mathrm{\forall }x(\alpha (x)\vee \beta (x))$.

  $\begin{array}{cc}\begin{array}{cccc}x& \alpha (x)& \beta (x)& \alpha (x)\vee \beta (x)\\ 1& \alpha (1)=E& \beta (1)=F& \alpha (1)\vee \beta (1)=E\\ 2& \alpha (2)=F& \beta (2)=E& \alpha (2)\vee \beta (2)=E\end{array}& H^{\ast }=\mathrm{\forall }x(\alpha (x)\vee \beta (x))=E\end{array}$

  Orduan, $V(H,I)\ne V(G,I)$. Eta, beraz, $G\equiv ̸H$ daukagu.

• EB2:

  $G=\mathrm{\exists }xA[x]\wedge \mathrm{\exists }xB[x]\equiv ̸\mathrm{\exists }x(A[x]\wedge B[x])=H$ dela frogatzeko, ikus dezakegu, aurrekoan bezala, $I$ interpretazio baterako $V(H,I)\ne V(G,I)$ dela. Baina jadanik frogaturik dauden baliokidetzak eta baliokidetza ez den aurrekoa ere erabil ditzakegu.

  $G=\mathrm{\exists }xA[x]\wedge \mathrm{\exists }xB[x]\stackrel{UB}{\equiv }\mathrm{\neg }\mathrm{\neg }(\mathrm{\exists }xA[x]\wedge \mathrm{\exists }xB[x])\stackrel{DeM}{\equiv }\mathrm{\neg }(\mathrm{\neg }\mathrm{\exists }xA[x]\vee \mathrm{\neg }\mathrm{\exists }xB[x])\stackrel{2.}{\equiv }\mathrm{\neg }(\mathrm{\forall }x\mathrm{\neg }A[x]\vee \mathrm{\forall }x\mathrm{\neg }B[x])\stackrel{EB1}{\equiv ̸}\mathrm{\neg }\mathrm{\forall }x(\mathrm{\neg }A[x]\vee \mathrm{\neg }B[x])\stackrel{1.}{\equiv }\mathrm{\exists }x\mathrm{\neg }(\mathrm{\neg }A[x]\vee \mathrm{\neg }B[x])\stackrel{DeM}{\equiv }$

  $\mathrm{\exists }x(\mathrm{\neg }\mathrm{\neg }A[x]\wedge \mathrm{\neg }\mathrm{\neg }B[x])\stackrel{UB}{\equiv }\mathrm{\exists }x(A[x]\wedge B[x])=H$. $◻$ $◼$ $◻$

2.6 Dedukzio formala

Predikatu-logikan ere argumentuak baliozkoak diren ala ez ikusteko froga formalak egin ditzakegu.

Hona hemen erabiliko ditugun erregelak:

1. Proposizio-logikaren 9 inferentzia-erregelak (MP, MT, SH, SD, DE, DS, KS, KK, DB).
2. Ordezkapen-erregela, proposizio-logikaren 10 baliokidetza logikoak erabiliz, (ELKAR, TRUK, BANA, TAUT, UB, DeM, TRANS, INP, BALIO, ESP) eta aurreko atalean frogatutako zenbatzaileen 6 baliokidetzak.
3. Baldintzazko frogaren erregela (BFE) eta absurdora eramateko erregela (AEE).
4. Atal honetako erregela berriak: Zenbatzaileen erregelak. Erregela hauek froga baten errenkada osoei bakarrik aplika diezazkiekegu.

Idazkera. Erregela horiek erabiltzean idazkera hau erabiliko dugu:

$A(x)$ edozein formula da; $A(r)$ da $x$ aldagaiak $A(x)$ formulan dituen agerpen aske guztiak $r$ balioaz ordezkatzean lortzen den formula.

2.25 Adibideak.

1. $A(x)=\mathrm{\forall }z(Q(x)\vee \mathrm{\forall }xP(x,y,z))$ bada, $A(y)=\mathrm{\forall }z(Q(y)\vee \mathrm{\forall }xP(x,y,z))$ daukagu.
2. $A(y)=\mathrm{\exists }x(P(x,y)\vee \mathrm{\forall }z\mathrm{\exists }yP(y,z))$ bada, $A(z)=\mathrm{\exists }x(P(x,z)\vee \mathrm{\forall }z\mathrm{\exists }yP(y,z))$ daukagu.
3. $A(x)=\mathrm{\forall }xP(x,y)\vee P(z,y)$ bada, $A(z)=\mathrm{\forall }xP(x,y)\vee P(z,y)$ ($=A(x)$) daukagu.
4. $A(x)=\mathrm{\forall }yP(y)$ bada, $A(y)=A(z)=A(x)$ daukagu.

2.26 Definizioa. Esango dugu $r$ aldagaia $A(x)$ formulan $x$ aldagairako askea dela, ordezkapenaren ondoren, $r$ aldagaiak $A(r)$ formulan dituen agerpen guztiak askeak badira ($r$ posizio gehiagotan ager daiteke aske).

2.27 Adibideak.

1. $A(x)=\mathrm{\forall }z(Q(x)\vee \mathrm{\forall }xP(x,y,z))$.

   $A(y)=\mathrm{\forall }z(Q(y)\vee \mathrm{\forall }xP(x,y,z))$. $y$ askea da $x$ aldagairako $A(x)$ formulan.

   $A(z)=\underset{\_}{\mathrm{\forall }z}(Q(\underset{\_}{z})\vee \mathrm{\forall }xP(x,y,z))$. $z$ ez da askea $x$ aldagairako $A(x)$ formulan.

2. $A(y)=\mathrm{\exists }x(P(x,y)\vee \mathrm{\forall }z\mathrm{\exists }yP(y,z))$.

   $A(z)=\mathrm{\exists }x(P(x,z)\vee \mathrm{\forall }z\mathrm{\exists }yP(y,z))$. $z$ askea da $y$ aldagairako $A(y)$ formulan.

   $A(x)=\underset{\_}{\mathrm{\exists }x}(P(x,\underset{\_}{x})\vee \mathrm{\forall }z\mathrm{\exists }yP(y,z))$. $x$ ez da askea $y$ aldagairako $A(y)$ formulan.

3. $A(x)=\mathrm{\forall }xP(x,y)\vee P(z,y)$.

   $A(z)=A(y)=\cdots =A(x)$. Edozein aldagai da askea $x$ aldagairako $A(x)$ formulan.

Oharrak.

1. $A(x)$ formulak ez badu $x$ aske, edozein $r$ aldagaitarako $A(r)=A(x)$ izango da, eta $r$ askea izango da $x$ aldagairako $A(x)$ formulan.
2. Edozein $A(x)$ formulatarako, $x$ askea da $x$ aldagairako $A(x)$ formulan.

Zenbatzaileen erregelak.

• $\underset{\_}{\mathrm{\forall }\text{ Zenbatzailea ezabatu. }}$

$$\begin{array}{c}\mathrm{\forall }xA(x)\\ A(r)\end{array}$$ Murriztapenak: $r$ askea da $x$ aldagairako $A(x)$ formulan edo $r$ konstante bat da.

2.28 Adibideak.

1. ${\displaystyle }$

   $$\begin{array}{c}\mathrm{\forall }x(P(x,x)\wedge Q(y))\\ P(z,z)\wedge Q(y)\end{array}$$ $A(x)=P(x,x)\wedge Q(y)$; $A(z)=P(z,z)\wedge Q(y)$, $z$ askea da $x$-rako $A(x)$ formulan.

2. ${\displaystyle }$

   $$\begin{array}{c}\mathrm{\forall }x(P(x,x)\wedge Q(y))\\ P(x,x)\wedge Q(y)\end{array}\begin{array}{c}\mathrm{\forall }x(P(x,x)\wedge Q(y))\\ P(y,y)\wedge Q(y)\end{array}$$ $x$ eta $y$ askeak dira $x$ aldagairako $P(x,x)\wedge Q(y)$ formulan.

3. ${\displaystyle }$

   $$\begin{array}{c}\mathrm{\forall }y(P(y,y)\wedge Q(x)\wedge \mathrm{\forall }xR(x))\\ P(x,x)\wedge Q(x)\wedge \mathrm{\forall }xR(x))\end{array}$$ $x$ askea da $y$ aldagairako $P(y,y)\wedge Q(x)\wedge \mathrm{\forall }xR(x)$ formulan.

4. ${\displaystyle }$

   $$\begin{array}{c}\mathrm{\forall }x(P(x,x)\wedge Q(y)\wedge \mathrm{\exists }xR(x))\\ P(y,y)\wedge Q(y)\wedge \mathrm{\exists }xR(x))\end{array}$$ $y$ askea da $x$ aldagairako $P(x,x)\wedge Q(y)\wedge \mathrm{\exists }xR(x)$ formulan.

5. ${\displaystyle }$

   Txakur guztiak ugaztunak dira.	$\mathrm{\forall }x(T(x)\to U(x))$
   Bizi txakurra da.	$T(b)$
   Beraz, Bizi ugaztuna da.	$U(b)$

   $\begin{array}{ccc}1.& \mathrm{\forall }x(T(x)\to U(x))& \text{premisa}\\ 2.& T(b)& \text{premisa / }\dot{\mathrm{..}}U(b)\\ 3.& T(b)\to U(b)& \mathrm{\forall }x\text{-ezab(1) (}b\text{ konstantea da)}\\ 4.& U(b)& \text{MP(3,2)}\end{array}$

6. ${\displaystyle }$

   $\begin{array}{ccc}1.& \mathrm{\neg }P(x)& \text{premisa}\\ 2.& \mathrm{\forall }y(P(y)\vee Q(y))& \text{premisa / }\dot{\mathrm{..}}Q(x)\\ 3.& P(x)\vee Q(x)& \mathrm{\forall }y\text{-ezab(2) (}x\text{ askea da }y\text{-rako }P(y)\vee Q(y)\text{ formulan)}\\ 4.& Q(x)& \text{SD(3,1)}\end{array}$

7. Hona hemen dedukzio oker bat: $$\begin{array}{ccc}1.& \mathrm{\forall }x\mathrm{\exists }yP(x,y)& \text{premisa / }\dot{\mathrm{..}}\mathrm{\exists }yP(y,y)\\ 2.& \mathrm{\exists }yP(y,y)& \mathrm{\forall }x\text{-ezab(1)}\end{array}$$
   Erregela gaizki aplikatu dugu, $y$ ez delako askea $x$ aldagairako $\mathrm{\exists }yP(x,y)$ formulan.

   Horrez gain, argumentua baliogabea dela froga dezakegu. Har dezagun interpretazio hau:

   $$\begin{array}{cccc}I:& D=\{1,2\}& \begin{array}{c}P\\ \alpha \end{array}& \begin{array}{cc}{D}^2& \alpha \\ 11& F\\ 12& E\\ 21& E\\ 22& F\end{array}\end{array}</br>$$ $V(\mathrm{\forall }x\mathrm{\exists }yP(x,y),I)=E$ da, eta $V(\mathrm{\exists }yP(y,y),I)=F$.

8. Hona hemen erregelaren aplikazio okerraren beste adibide bat:
   $$\begin{array}{c}\mathrm{\forall }xP(x,x)\\ P(x,y)\end{array}$$
   Ez dira ordezkatu $x$ aldagaiak $P(x,x)$ formulan dituen agerpen aske guztiak $y$ aldagaiarekin.

   Horrez gain, argumentua baliogabea dela froga liteke.

• $\underset{\_}{\mathrm{\exists }\text{ Zenbatzailea sartu.}}$

$$\begin{array}{c}A(r)\\ \mathrm{\exists }xA(x)\end{array}$$ Murriztapenak: $r$ askea da $x$ aldagairako $A(x)$ formulan edo $r$ konstantea da.

2.29 Adibideak.

1. ${\displaystyle }$

   $$\begin{array}{c}P(x)\\ \mathrm{\exists }xP(x)\end{array}\begin{array}{c}P(y)\\ \mathrm{\exists }xP(x)\end{array}$$ $x$ eta $y$ askeak dira $x$ aldagairako $P(x)$ formulan.

2. ${\displaystyle }$

   $$\begin{array}{c}P(x,y)\wedge \mathrm{\forall }zR(z)\\ \mathrm{\exists }z(P(x,z)\wedge \mathrm{\forall }zR(z))\end{array}$$ $y$ askea da $z$ aldagairako $P(x,z)\wedge \mathrm{\forall }zR(z)$ formulan.

3. ${\displaystyle }$

   $$\begin{array}{c}P(x)\to Q(x)\\ \mathrm{\exists }y(P(x)\to Q(y))\end{array}$$ $x$ askea da $y$ aldagairako $P(x)\to Q(y)$ formulan.

4. ${\displaystyle }$

   $$\begin{array}{cccc}& 1.& \mathrm{\forall }x(P(x)\to Q(x))& \text{premisa / }\dot{\mathrm{..}}P(y)\to \mathrm{\exists }x(P(x)\wedge Q(x))\\ \to & 2.& P(y)& \text{BFEren hipotesia / }\dot{\mathrm{..}}\mathrm{\exists }x(P(x)\wedge Q(x))\\ |& 3.& P(y)\to Q(y)& \mathrm{\forall }x\text{-ezab(1) (}y\text{ askea }x\text{-rako, }P(x)\to Q(x)\text{)}\\ |& 4.& Q(y)& \text{MP(3,2)}\\ |& 5.& P(y)\wedge Q(y)& \text{KK(2,4)}\\ |& 6.& \mathrm{\exists }x(P(x)\wedge Q(x))& \mathrm{\exists }x\text{-sar(5) (}y\text{ askea }x\text{-rako, }P(x)\wedge Q(x)\text{)}\\ --& --& --------& \\ & 7.& P(y)\to \mathrm{\exists }x(P(x)\wedge Q(x))& \text{BFE(2-6)}\end{array}$$

5. Erregelaren aplikazio oker bat:
   $$\begin{array}{c}P(x)\leftrightarrow \mathrm{\neg }P(y)\\ \mathrm{\exists }x(P(x)\leftrightarrow \mathrm{\neg }P(x))\end{array}</br>$$ Erregela gaizki aplikatu dugu ez ditugulako ordezkatu $y$ aldagaiarekin $x$ aldagaiak $P(x)\leftrightarrow \mathrm{\neg }P(x)$ formulan dituen agerpen aske guztiak.

   Eta argumentua baliogabea dela froga liteke.

6. Erregelaren beste aplikazio oker bat:
   $$\begin{array}{c}\mathrm{\forall }xP(x,x)\\ \mathrm{\exists }y\mathrm{\forall }xP(y,x)\end{array}$$ Erregela gaizki aplikatu dugu $x$ ez delako askea $y$ aldagairako $\mathrm{\forall }xP(y,x)$ formulan.

   Eta argumentua baliogabea dela froga liteke.

• $\underset{\_}{\mathrm{\forall }\text{ Zenbatzailea sartu.}}$

$\begin{array}{c}{P}_1\\ ⋮\\ P_n\\ A\end{array}$ argumentua baliozkoa bada, $\begin{array}{c}{P}_1\\ ⋮\\ P_n\\ \mathrm{\forall }xA\end{array}$ argumentua ere baliozkoa izango da.

Murriztapenak: $P_1,\dots ,P_n$ premisek ez dute $x$ aske.

Erabilbidea: Argumentu baten froga formal batean, premisek eta indarrean dauden hipotesiek ez badute $x$ aske, eta frogaren formuletako bat $A$ bada, $\mathrm{\forall }$ zenbatzailea sartzeko erregelatik $\mathrm{\forall }xA$ deduzi dezakegu. $$\begin{array}{ccc}1.& P_1& \text{premisa}\\ ⋮& ⋮& ⋮\\ n.& P_n& \text{premisa / }\dot{\mathrm{..}}C\\ ⋮& ⋮& \\ m.& A& \\ m+1.& \mathrm{\forall }xA& \mathrm{\forall }x\text{-sar(m)}\end{array}$$
($P_1,\dots ,P_n$ premisek eta indarrean dauden hipotesiek ez dute $x$ aske)

2.30 Adibideak.

1. ${\displaystyle }$

   $\begin{array}{ccc}1.& \mathrm{\forall }yP(y,y)\wedge \mathrm{\forall }zR(z)& \text{premisa / }\dot{\mathrm{..}}\mathrm{\forall }y(P(y,y)\wedge R(y))\\ 2.& \mathrm{\forall }yP(y,y)& \text{KS(1)}\\ 3.& P(y,y)& \mathrm{\forall }y\text{-ezab(2) (}y\text{ askea da }y\text{ aldagairako }P(y,y)\text{ formulan)}\\ 4.& \mathrm{\forall }zR(z)\wedge \mathrm{\forall }yP(y,y)& \text{TRUK(1)}\\ 5.& \mathrm{\forall }zR(z)& \text{KS(4)}\\ 6.& R(y)& \mathrm{\forall }z\text{-ezab(5) (}y\text{ askea da }z\text{ aldagairako }R(z)\text{ formulan)}\\ 7.& P(y,y)\wedge R(y)& \text{KK(3,6)}\\ 8.& \mathrm{\forall }y(P(y,y)\wedge R(y))& \mathrm{\forall }y\text{-sar(7) (1. premisak ez du }y\text{ aske)}\end{array}$

2. ${\displaystyle }$

   $\begin{array}{cccc}& 1.& \mathrm{\forall }x(P(x)\to Q(x))& \text{premisa}\\ & 2.& \mathrm{\forall }x(R(x)\to \mathrm{\neg }Q(x))& \text{premisa / }\dot{\mathrm{..}}\mathrm{\forall }x(R(x)\to \mathrm{\neg }P(x))\\ \to & 3.& R(x)& \text{BFEren hipotesia / }\dot{\mathrm{..}}\mathrm{\neg }P(x)\\ |& 4.& R(x)\to \mathrm{\neg }Q(x)& \mathrm{\forall }x\text{-ezab(2) (}x\text{ askea }x\text{-rako, }R(x)\to \mathrm{\neg }Q(x)\text{)}\\ |& 5.& \mathrm{\neg }Q(x)& \text{MP(4,3)}\\ |& 6.& P(x)\to Q(x)& \mathrm{\forall }x\text{-ezab(1) (}x\text{ askea }x\text{-rako }P(x)\to Q(x)\text{ formulan)}\\ |& 7.& \mathrm{\neg }P(x)& \text{MT(6,5)}\\ --& --& ------& \\ & 8.& R(x)\to \mathrm{\neg }P(x)& \text{BFE(3-7)}\\ & 9.& \mathrm{\forall }x(R(x)\to \mathrm{\neg }P(x))& \mathrm{\forall }x\text{-sar(8)}\\ & & & \text{(1. eta 2. premisek ez dute }x\text{ aske; 3. hipotesia ez dago indarrean)}\end{array}$

3. Aplikazio okerraren adibidea:

   $\begin{array}{cccc}& 1.& \mathrm{\forall }x(P(x)\to Q(x))& \text{premisa / }\dot{\mathrm{..}}P(x)\to \mathrm{\forall }xQ(x)\\ \to & 2.& P(x)& \text{BFEren hipotesia / }\dot{\mathrm{..}}\mathrm{\forall }xQ(x)\\ |& 3.& P(x)\to Q(x)& \mathrm{\forall }x\text{-ezab(1) (}x\text{ askea }x\text{-rako }P(x)\to Q(x)\text{ formulan)}\\ |& 4.& Q(x)& \text{MP(3,2)}\\ |& 5.& \mathrm{\forall }xQ(x)& \mathrm{\forall }x\text{-sar(4)}\\ & & & \text{GAIZKI: 2. hipotesiak }x\text{ aske du}\\ --& --& ------& \\ & 6.& P(x)\to \mathrm{\forall }xQ(x)& \text{BFE(2-5)}\end{array}$

• $\underset{\_}{\mathrm{\exists }\text{ Zenbatzailea ezabatu.}}$

(1) $\begin{array}{c}{P}_1\\ ⋮\\ P_n\\ A\\ C\end{array}$ argumentua baliozkoa bada, (2) $\begin{array}{c}{P}_1\\ ⋮\\ P_n\\ \mathrm{\exists }xA\\ C\end{array}$ argumentua ere baliozkoa da.

Murriztapenak: $P_1,\dots ,P_n$ premisek eta $C$ ondorioak ez dute $x$ aske.

Erabilbidea: (2) argumentuaren froga formalean, premisek eta indarrean dauden hipotesiek ez badute $x$ aske, eta frogaren formuletako bat $\mathrm{\exists }xA$ bada, $A$ suposatuko dugu erregela aplikatzeko ((1) argumentua). Hipotesi horrekin $C$ formula deduzituz gero, (1) argumentua frogatua dugu. Orduan, $C$ formulak ere ez badu $x$ aske, erregela aplikatuz, (2) argumentua ere baliozkoa dela esan ahal izango dugu. $$\begin{array}{cccc}& 1.& P_1& \text{premisa}\\ & ⋮& ⋮& ⋮\\ & n.& P_n& \text{premisa}\\ & ⋮& ⋮& \\ & p.& \mathrm{\exists }xA& \\ & ⋮& ⋮& \\ \to & q.& A& \mathrm{\exists }x\text{-ezabatzeko hipotesia(p)}\\ |& ⋮& ⋮& \\ |& m.& C& \\ --& --& --& \\ & m+1.& C& \mathrm{\exists }x\text{-ezab(p,q-m)}\end{array}$$
($P_1,\dots ,P_n$ premisek, hipotesiek eta $C$ ondorioak ez dute $x$ aske)

2.31 Adibideak.

1. .

   $\begin{array}{cccc}& 1.& \mathrm{\forall }x(P(x)\to Q(x))& \text{premisa}\\ & 2.& \mathrm{\exists }yP(y)& \text{premisa / }\dot{\mathrm{..}}\mathrm{\exists }zQ(z)\\ \to & 3.& P(y)& \mathrm{\exists }y\text{-ezabatzeko hipotesia(2)}\\ |& 4.& P(y)\to Q(y)& \mathrm{\forall }x\text{-ezab(1) (}y\text{ askea }x\text{-rako }P(x)\to Q(x)\text{ formulan)}\\ |& 5.& Q(y)& \text{MP(4,3)}\\ |& 6.& \mathrm{\exists }zQ(z)& \mathrm{\exists }z\text{-sar(5) (}y\text{ askea da }z\text{ aldagairako }Q(z)\text{ formulan)}\\ --& --& -------& \\ & 7.& \mathrm{\exists }zQ(z)& \mathrm{\exists }y\text{-ezab(2,3-6) (1. eta 2. premisek eta 6. ondorioak ez dute }y\text{ aske)}\end{array}$

2. .

   $\begin{array}{cccc}& 1.& \mathrm{\exists }x(P(x)\wedge Q(x))& \text{premisa / }\dot{\mathrm{..}}\mathrm{\exists }xP(x)\wedge \mathrm{\exists }xQ(x)\\ \to & 2.& P(x)\wedge Q(x)& \mathrm{\exists }x\text{-ezabatzeko hipotesia(1)}\\ |& 3.& P(x)& \text{KS(2)}\\ |& 4.& \mathrm{\exists }xP(x)& \mathrm{\exists }x\text{-sar(3) (}x\text{ askea da }x\text{ aldagairako }P(x)\text{ formulan)}\\ |& 5.& Q(x)\wedge P(x)& \text{TRUK(2)}\\ |& 6.& Q(x)& \text{KS(5)}\\ |& 7.& \mathrm{\exists }xQ(x)& \mathrm{\exists }x\text{-sar(6) (}x\text{ askea da }x\text{ aldagairako }Q(x)\text{ formulan)}\\ |& 8.& \mathrm{\exists }xP(x)\wedge \mathrm{\exists }xQ(x)& \text{KK(4,7)}\\ --& --& --& \\ & 9.& \mathrm{\exists }xP(x)\wedge \mathrm{\exists }xQ(x)& \mathrm{\exists }x\text{-ezab(1,2-8) (1. premisak eta 8. ondorioak ez dute }x\text{ aske)}\end{array}$

3. Erregelaren aplikazio okerraren adibidea:

   $\begin{array}{cccc}& 1.& \mathrm{\forall }x\mathrm{\exists }yP(x,y)& \text{premisa / }\dot{\mathrm{..}}\mathrm{\forall }y\mathrm{\exists }xP(x,y)\\ & 2.& \mathrm{\exists }yP(x,y)& \mathrm{\forall }x\text{-ezab(1) (}x\text{askea da}x\text{aldagairako }\mathrm{\exists }yP(x,y)\text{ formulan)}\\ \to & 3.& P(x,y)& \mathrm{\exists }y\text{-ezabatzeko hipotesia(2)}\\ |& 4.& \mathrm{\exists }xP(x,y)& \mathrm{\exists }x\text{-sar(3) (}x\text{askea da}x\text{aldagairako }P(x,y)\text{ formulan)}\\ --& --& --& \\ & 5.& \mathrm{\exists }xP(x,y)& \mathrm{\exists }y\text{-ezab(2,3-4) (GAIZKI: 4 ondorioak}y\text{aske du)}\\ & 6.& \mathrm{\forall }y\mathrm{\exists }xP(x,y)& \mathrm{\forall }y\text{-sar(5) (1. premisak eta 2. formulak ez dute}y\text{aske)}\end{array}$

4. Argumentu beraren beste froga oker bat:

   $\begin{array}{cccc}& 1.& \mathrm{\forall }x\mathrm{\exists }yP(x,y)& \text{premisa / }\dot{\mathrm{..}}\mathrm{\forall }y\mathrm{\exists }xP(x,y)\\ & 2.& \mathrm{\exists }yP(x,y)& \mathrm{\forall }x\text{-ezab(1) (}x\text{askea da}x\text{aldagairako }\mathrm{\exists }yP(x,y)\text{ formulan)}\\ \to & 3.& P(x,y)& \mathrm{\exists }y\text{-ezabatzeko hipotesia(2)}\\ |& 4.& \mathrm{\exists }xP(x,y)& \mathrm{\exists }x\text{-sar(3) (}x\text{askea da}x\text{aldagairako }P(x,y)\text{ formulan)}\\ |& 5.& \mathrm{\forall }y\mathrm{\exists }xP(x,y)& \mathrm{\forall }y\text{-sar(4) (GAIZKI: 3 hipotesiak}y\text{aske du)}\\ --& --& --& \\ & 6.& \mathrm{\forall }y\mathrm{\exists }xP(x,y)& \mathrm{\exists }y\text{-ezab(2,3-5) (1. premisak eta 5. formulak ez dute}y\text{aske)}\end{array}$

5. Erregelaren beste aplikazio oker bat:

   $\begin{array}{ccccc}& & 1.& \mathrm{\exists }x(P(x)\wedge R(x))& \text{premisa}\\ & & 2.& \mathrm{\exists }x(Q(x)\wedge R(x))& \text{premisa / }\dot{\mathrm{..}}\mathrm{\exists }x(P(x)\wedge Q(x))\\ \to & & 3.& Q(x)\wedge R(x)& \mathrm{\exists }x\text{-ezabatzeko hipotesia(2)}\\ |& & 4.& Q(x)& \text{KS(3)}\\ |& \to & 5.& P(x)\wedge R(x)& \mathrm{\exists }x\text{-ezabatzeko hipotesia(1)}\\ |& |& 6.& P(x)& \text{KS(5)}\\ |& |& 7.& P(x)\wedge Q(x)& \text{KK(6,4)}\\ |& |& 8.& \mathrm{\exists }x(P(x)\wedge Q(x))& \mathrm{\exists }x\text{-sar(7) (}x\text{askea }x\text{-rako }P(x)\wedge Q(x)\text{ formulan)}\\ & --& --& --& \\ |& & 9.& \mathrm{\exists }x(P(x)\wedge Q(x))& \mathrm{\exists }x\text{-ezab(1,5-8) (GAIZKI: 3 hipotesiak}x\text{aske du)}\\ --& --& --& --& \\ & & 10.& \mathrm{\exists }x(P(x)\wedge Q(x))& \mathrm{\exists }x\text{-ezab(2,3-9) (1. eta 2. premisek eta 9. formulak ez dute}x\text{aske)}\end{array}$