Lankide:Xgarrote001/Proba orria

Sintaxia

Predikatu logikan erabiltzen den alfabetoa honako ikurrez osatuta dago:

$a\quad x\quad P\quad \lnot \quad \land \quad \lor \quad \rightarrow \quad \leftrightarrow \quad \forall \quad \exists \quad (\quad )$

Idazkera

1. Izen edo konstante bat idazteko alfabetoko hasierako letrak erabiltzen dira a, b, c, d, e, a₁, a₂,...
2. Aldagai bat idazteko alfabetoaren bukaerako letrak erabiltzen dira x,y,z, x₁,x_2,...
3. Predikatu bat idazteko alfabetoko letra larriak erabiltzen dira P, A, B, C, S, T,...
4. Kuantifikatzaile unibertsala ${\boldsymbol {\forall }}$ ikurraz adierazten da.
5. Kuantifikatzaile existentziala ${\boldsymbol {\exists }}$ ikurraz adierazten da.

Terminoak eta interpretazioak

1. P predikatu bat izanik aritatea n n ≥ 1 duena eta t₁,...,t_n terminoak badira orduan P(t₁,...,t_n) termino bat da.
2. Izen guztiak dira terminoak.
3. Aldagai guztiak dira terminoak.
4. Predikatuak terminoak dira.

Katea	Interpretazio posiblea
a	Mikel
x	Futbolari bat
H(a)	Mikel futbolaria da.

Ongi osatutako formulak

1. A ongi osatutako formula bat baldin bada ¬A baita ere da.
2. A eta B ongi osatutako formulak baldin badira (A ∧ B), (A ∨ B), (A → B) eta (A ↔ B) baita ere.
3. A ongi osatutako formula bada eta x aldagai bat bada ∀x A y ∃x A ere ongi osatutako formulak dira.

• Ondoko formulak ongi osatuta daude:

Katea	Interpretazio posiblea
P(a)	Mikel artzaia da
M(a,e)	Mikelek Leire maite du
P(v) → ¬E(v)	Venus planeta bat baldin bada ez da izar bat
∀x G(x)	Denak gezurtiak dira.
∀x ∃y M(x,y)	Denak norbait maite dute.
∃x ∀y M(x,y)	Norbaitek denak maite ditu

• Aldiz, ondoko formulak ez daude ongi osatuta

Katea	Errorea
P ()	Predikatuak ez dauka argumenturik
P (a, , )	Predikatuak bakarrik argumentu bat du.
∀a P (a)	Kuantifikatzaile unibertsalaren ondoan konstante bat dago.

Inferentzia erregelak

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

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

Beraz, argumentu bat baliozkoa da baldin premisa denak egiazkoak direnean ondorioa ere egiazkoa bada edozein interpretaziorako.

Argumentu bat baliozkoa dela frogatzeko, deribazio edo frogapen formalak egiten dira. Horretarako, ondorengo lau inferentzia-erregelak, eta logika proposizionalekoak, erabiltzen dira.

Inferentzia-erregela hauen bidez, zenbatzaileak (unibertsalak eta existentzialak) ezabatu edo sartzen dira frogapen formalean zehar.

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

Unibertsala ezabatzea

1. Modua
   • $\forall xA(x)\vdash A(x)$
   • $\forall yA(y)\vdash A(y)$
2. Modua
   • $\forall xA(x)\vdash A(a)$
   • $\forall xA(x)\vdash A(b)$

Existentziala ezabatzea

• $\exists A(x)\vdash A(a)$

a,b,c konstante bat aukeratu behar da frograpenean zehar inon agertu ez dena, ondorioan ere ez. Gainera, $\exists xA(x)$ adierazpenean ezin da aldagai bat egon bere zenbatzailerik gabe.

Unibertsala sartzea

• $A(x)\vdash \forall xA(x)$
• $A(y)\vdash \forall yA(y)$

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

Existentziala sartu

• $A(a)\vdash \exists xA(x)$

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

Argumentu baten frogapena

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

Baliokidetasunak

Logika proposizionalean bezala, predikatu logikan A eta B adierazpenak baliokideak dira, A ≡ B idatziz, baldin A ↔ B adierazpena baliozkoa bada. Hau da, A eta B adierazpenak baliokideak dira edozein interpretaziorako egia balio berdina badute. Jarraian oinarrizko baliokidetasun legeak daude.

1. $\lnot \exists A(x)=\forall x\lnot A(x)$
2. $\lnot \forall A(x)\equiv \exists \lnot A(x)$
3. $\forall x\forall yA(x,y)\equiv \forall y\forall xA(x,y)$
4. $\exists x\exists yA(x,y)\equiv \exists y\exists xA(x,y)$
5. $\forall (A(x)\land B(x))\equiv \forall xA(x)\land \forall xB(x)$
6. $\exists (A(x)\lor B(x))\equiv \exists xA(x)\lor \exists xB(x)$

Unibertsala banakorra da konjuntziorako baina EZ disjuntziorako.

Existentziala banakorra da disjuntziorako baina EZ konjuntziorako.

1. $\forall (A\land B(x))\equiv A\land \forall xB(x)$
2. $\forall (A\lor B(x))\equiv A\lor \forall xB(x)$
3. $\exists (A\land B(x))\equiv A\land \exists xB(x)$
4. $\exists (A\lor B(x))\equiv A\lor \exists xB(x)$

Azken lau baliokidetasun hauetan A azpiadierazpenean EZ da x aldagaia agertzen.

Argumentu baten frogapena baliokidetasunak erabiliz

${\begin{array}{ll}Frogatu:\forall x\exists y(P(x)\land Q(y))\equiv \forall P(x)\land \exists Q(y)?\\Ebazpena:{\underline {\forall x\exists y(P(x)\land Q(y))}}\equiv \forall x(P(x)\land \exists yQ(y)\equiv {\underline {\forall P(x)\land \exists Q(y)}}\\\\Frogatu:\forall x\exists y(P(x,y)\rightarrow \lnot Q(x,y))\equiv \lnot \exists x\forall y(P(x,y)\land Q(x,y))?\\Ebazpena:{\underline {\lnot \exists 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\exists y\lnot (P(x,y)\land Q(x,y))\equiv \forall x\exists y(\lnot P(x,y)\lor \lnot Q(x,y))\equiv {\underline {\forall x\exists y(P(x,y)\rightarrow \lnot Q(x,y))}}\end{array}}$

Adierazpen bat ez baliozkoa den frogatu

Predikatu logikan adierazpen baten baliozkotasuna aztertzeko bere egia taulako lerroetan egiazkoa den begiratu behar da, baina orain egia taulak konplexuagoak dira, logika proposizionalekoak baino.

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

1. Unibertsoa zehaztuko da, multzo zenbakigarri bat izango da (finitua ala infinitua), beraz banakoak 1, 2, 3 . . . izango dira adierazpen baten interpretazioa definitzen denean.
2. 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.
3. Adierazpenaren interpretazio bat (bere egia taulako lerro bat) finkatuz, adierazpenaren egia balioa kalkulatu daiteke, jakinik zenbatzaileekin egin behar den ondorengo kalkulua.
   • Zenbatzaile unibertsala:
     1. ∀xA(x) T da baldin A(x) T bada unibertsoko x banako guztietarako.
     2. ∀xA(x) F da baldin A(x) F bada gutxienez unibertsoko x banako baterako.
   • Zenbatzaile existentziala:
     1. ∃xA(x) T da baldin A(x) T bada gutxienez unibertsoko x banako baterako.
     2. ∃xA(x) F da baldin A(x) F bada unibertsoko x banako guztietarako.
4. 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.
5. 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 ez baliokidetasuna adibidea

$Frogatu\ ez\ baliozkoa\ dela:\exists x\exists yP(x,y)\rightarrow \exists P(x,x)$

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

$\exists x\exists y\psi (x,y)T\ izateko$

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

1. Lerroa: $\exists y\psi (1,y)T\ izateko$
   • $\psi (1,1)T\quad edo\quad \psi (1,2)T$
2. Lerroa: $\exists y\psi (2,y)Tizatekoa$
   • $\psi (2,1)\quad edo\quad \psi (2,2)T$

$\exists x\psi (x,x)F\ izateko$

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

Emaitza posible bat:

${\begin{array}{|l|ll|}\hline \psi &1&2\\\hline 1&F&T\\2&T&F\\\hline \end{array}}$