KONTUZ! Fitxategi hau zirriborroa da oraindik. LANEAN ARI GARA

1. Gaia: Proposizio-logika

1.1 Sarrera

Hizkuntzan esaldi ezagutarazleak, agintzaileak eta galdetzaileak erabiltzen ditugu. Ezagutza, funtsean, lehenek deskribatzen dute. Ezagutza bi bidetik jaso dezakegu: gertakariak edo ideiak egiaztatuz, esaldi ezagutarazleen bidez, edo dedukzioaren bidez.

Logika formalaren helburua dedukzioa (arrazoibidea, inferentzia, argudiatzea) da. Dedukzioa ezagutzen diren datu batzuetatik ezagutza berriak sortzean datza. Arrazoibide baten ezaugarri nagusia hau da, abiapuntutzat hartzen ditugun baieztapen (premisa) batzuetatik beste baieztapen (ondorio) bat ondorioztatzea. Gogoratzea edota imajinatzea, adibidez, pentsaerak dira, baina ez dira arrazoibideak.

Arrazoibide orok forma eta edukia ditu.

Arrazoibide hauek edukian bereizten dira:

(1)

Lehoi guztiak ugaztunak dira.

Ugaztun guztiek birikak dituzte.

Beraz, lehoi guztiek birikak dituzte.

(2)

Zenbaki arrunt guztiak bikoitiak dira.

Zenbaki bikoiti guztiak lehenak dira.

Beraz, zenbaki arrunt guztiak lehenak dira.

baina forma bera dute:

a guztiak b dira.

b guztiak c dira.

Beraz, a guztiak c dira.

Logika arrazoibideen forman bakarrik aritzen da. Horregatik da logika formala baliozko arrazoibideen eskemen edo formen zientzia.

Aurreko eskema baliozkoa da, premisak egiazkoak badira, ondorioa halabeharrez izango baita egiazkoa.

Ohar gaitezen arrazoibidea baliozkoa izan daitekeela premisak egiazkoak edo faltsuak diren kontuan izan gabe. Arrazoibide zuzena izan daiteke, nahiz eta premisak eta ondorioa faltsuak izan, (2) adibidean bezala.

Arrazoibide bat baliozkoa edo zuzena da, bere premisak egiazkoak izanik, ondorioa ezin denean faltsua izan. Premisak egiazkoak izan edo faltsuak izan beste kontu bat da, logikatik at geratzen den kontua (zenbaki bikoitiak lehenak izan ala ez aritmetikaren kontua da, ez logikarena).

Ikus ditzagun beste adibide batzuk:

(3)

Pilotan ari banaiz, kirolean ari naiz.

Kirolean ari naiz.

Beraz, pilotan ari naiz.

arrazoibidea eskema honi lotzen zaio:

a bada, orduan b.

b.

Beraz, a.

(4)

Aberatsa banaiz, ona naiz.

Ez naiz aberatsa.

Beraz, ez naiz ona.

Dagokion eskema hau da:

a bada, orduan b.

Ez a.

Beraz, ez b.

Arrazoibide horiek ez dira zuzenak, gerta baitaiteke premisak egiazkoak izatea eta, hala ere, ondorioa faltsua izatea.

Logikak arrazoibideen forman oinarritu behar du, edukiak kontuan izan gabe. Horregatik gainditu behar du hizkuntza naturalaren joera, non forma eta edukia nahasirik ematen baitira. Bestalde, forma isolaturik agertzen duen lengoaia bat erabili behar dugu, hots, arrazoibideen egitura bakarrik erakusten duen lengoaia.

Horregatik sortuko dugu lengoaia artifiziala, objektu lengoaia deituko duguna. Eta horri buruz hitz egiteko erabiliko dugun hizkuntzari metalengoaia deituko diogu (Euskaraz idatzitako ingelesari buruzko liburu batean, euskara metalengoaia da).

Zeinuak edo hizkuntzak, zeinu-sistema gisa, aztertzen dituen zientzia semiotika da. Semiotika sintaxiak, semantikak eta pragmatikak osatzen dute.

Sintaxiak zeinuen arteko erlazioak bakarrik aztertzen ditu. Ongi osatutako zeinuen segidak ezagutu eta eraiki egiten ditu. Esaterako, “da hau erloju Arantzarena” hitzen segida gaizki osaturik dagoela esaten dugunean, arazo sintaktiko bati heltzen diogu. Semantikak, beste aldetik, zeinuen eta zeinuek adierazten dutenaren arteko erlazioak aztertzen ditu; hau da, zeinuen eta horiekin aipatzen ditugun zera horien arteko erlazioak (izen berezien eta izendatutakoen arteko erlazioak, enuntziatuen eta enuntziatuek deskribatzen dutenaren arteko erlazioak...): “Multzo-teorian, multzo hutsa elementurik ez duen multzoa da” esaten dugunean, semantikan ari gara.

Azkenik, pragmatikan hizkuntzaren elementuen eta hizkuntz komunitateko kideen arteko erlazioek ere hartzen dute parte. Esate baterako, “abertzale” hitzak esanahi desberdina du, erabiltzailearen arabera.

Hau da, pragmatika egiten dugunean, hizkuntzaz kezkatuko gara, subjektu baten edo talde baten jokabide gisa. Semantikan, aldiz, hiztunaz ahaztuko gara, eta bere hizkerak erabiltzen dituen zeinuen eta zeinu horiek irudikatzen dituzten gauzen arteko erlazioak aztertuko ditugu. Sintaxian, azkenik, zeinuak eta zeinuen arteko erlazioak bakarrik aztertuko ditugu, kontuan izan gabe zeinu horiek aipatzen dituzten gauzak edo egoerak.

Lengoaiaren formak sinbolizatzean, bi maila bereiz ditzakegu: Proposizio-kalkulua eta Predikatu-kalkulua.

Proposizio-kalkulua: hizkuntza arruntaren esaldi ezagutarazle bakunak (proposizioak) oinarrizko elementutzat hartuko ditugu, eta adierazi.

Predikatu-kalkulua: proposizioen osagai batzuk oinarrizko elementutzat hartuko ditugu, eta adierazi: terminoak eta predikatuak.

Lengoaia adierazteko bi maila horietarako bi eratan adieraz daitezke dedukziozko egitura zuzenak:

Interpretazio-teoria edo Eredu-teoria: proposizioei eta dedukziozko egitura zuzenei egoki dakizkiekeen esanahiak (gehienetan egiazkoa eta faltsua) definitzean datza.

Frogabidearen eta dedukzio naturalaren teoria: dedukziozko egitura zuzen batzuk eta horietatik dedukziozko egitura berri batzuk lortzeko arauak axiomatikoki definitzean datza.

1.2 Proposizio-kalkulua. Esaldien formalizazioa

Logika formalaren azterketa oinarritik hasiko dugu, proposizioen edo enuntziatuen logikatik hain zuzen. Sinbolizazio-maila honetan lengoaia elementu hauek osatuko dute:

Enuntziatu bakunak, proposizio atomikoak deituak;
lokailuak.

Enuntziatu bakunak (proposizio atomikoak) informazioa duen hizkuntzaren unitate txikientzat har ditzakegu, informazio horri buruz zerbait esan dezakegularik (egiazkoa edo faltsua dela):

Esate baterako, “euria ari du”, “Ane azkarra da”.

Hizkuntzaren “euria”, “Ane” elementuek ez dute berezko informaziorik, ez badira elkartzen beste elementu batzuekin; ez dira, beraz, proposizioak. Horregatik ez dira agertuko proposizio-kalkuluan; predikatu-kalkuluan, ordea, bere lekua izango dute.

Aurreko enuntziatuak ezin dira banatu informazioa duten hizkuntzaren elementu txikiagoetan. Izan ere, “ari du” zatiak ez du informaziorik ematen ez bazaio zerbaiti lotzen.

“Euria ari du eta bustitzen ari naiz” esaldia, ordea, bi zatitan bana dezakegu “eta” hitzaren bidez (“euria ari du”, “bustitzen ari naiz”), bakoitzak berezko informazioa ematen duelarik.

“Eta” hizkuntzaren elementua da eta bi proposiziotik esaldi berri bat eraikitzeko balio du; esaldi berriaren informazioa proposizioena bera da, baina aldiberekotasuna erantsiz. “Euria ari du eta bustitzen ari naiz” proposizio konposatuaren adibidea da.

Hizkuntzan badira beste hitz batzuk esaldiak alboratzeko: “baina”, “hala ere”, “ordea”, “nahiz eta”... Horiek guztiek, informazio-edukiaren ikuspuntutik, “eta” hitzaren paper bera jokatzen dute. Hala ere, hiztunari aukera ematen diote esaldi batzuk azpimarratzeko beste esaldi batzuen aurrean. Proposizio-kalkuluan ez ditugu eite horiek kontuan izango, eta horregatik beren adierazpen matematikoa “eta” hitzarena izango da.

Aurreko adibidean “eta” lokailu bat da. Lokailu bat esaldi batzuetatik esaldi berri bat eraikitzeko aukera ematen duen hizkuntzaren elementu bat da, esaldi lotuen informazioei ñabardurak eransten dizkiola. Gorago esan bezala, lokailu bera, informazio-edukiaren ikuspuntutik, hizkuntza arruntaren zenbait elementuren bidez gauza daiteke.

Proposizio-kalkuluaren lokailuak hauek dira: ukapena, konjuntzioa, disjuntzioa, baldintzazkoa eta baldintzabikoa.

Proposizio-kalkuluaren sinbolizazio matematikoa proposizioetan eta lokailuetan oinarritzen da; honela:

p, q, r, s, . . . hizkiek proposizio atomikoak adieraziko dituzte. Adibidez, “euria ari du” esaldia p adieraziko dugu, eta “bustitzen ari naiz” esaldia q.
Lokailuak adierazteko sinbolo hauek erabiliko ditugu:
- Ukapena: ¬
- Konjuntzioa: ∧
- Disjuntzioa: ∨
- Baldintzazkoa: →
- Baldintzabikoa: ↔

Horrela, “Euria ari du eta bustitzen ari naiz”, “Aldi berean euria ari du eta bustitzen ari naiz” “Euria ari du, baina bustitzen ari naiz”, “Euria ari du, hala ere bustitzen ari naiz”, “Euria ari duen bitartean bustitzen ari naiz” esaldiak honela adieraziko ditugu:

p\wedge q

Azpimarratzekoa da $p\wedge q$ esaldiaren egitura adierazteko era bat dela, eta ez esaldia idazteko era bat. Logika egitura horien azterketaz arduratzen da, ez informazioaren edukiaz.

Jarraian lokailuak definituko ditugu:

Ukapena: $\neg p$

$p$ motako proposizio batetik “ez $p$ ”, “ $p$ faltsua da”, “ $p$ ez da egiazkoa” motako proposizioa eraikitzeko aukera ematen duen lengoaiaren elementua da.

Konjuntzioa: $p\wedge q$

$p,q$ bi proposizioak lotuz “ $p$ eta $q$ ”, “ $p$ , baina $q$ ”, “ $p$ , hala ere $q$ ”, “ $p$ , nahiz eta $q$ ”... motako proposizioa eraikitzeko aukera ematen duen lengoaiaren elementua da.

Disjuntzioa: $p\vee q$

$p,q$ bi proposizioak lotuz “edo $p$ edo $q$ edo biak”, “gutxienez $p$ edo $q$ ”... motako proposizioak eraikitzeko erabiliko dugun lengoaiaren elementua da.

Hizkuntza arruntaren “edo”, “ala” hitzek bi esanahi dituzte: Inklusiboa: Larunbatean edo igandean hots egingo dizut. Esklusiboa: Zenbaki bakoitia edo bikoitia da.

Ez dakigu esaldi batzuetan zentzu inklusiboa edo esklusiboa dagoen. Baina logikaren ikuspuntutik interesgarriagoa da zentzu inklusiboa esklusiboa baino. Hortaz, $\vee$ beti izango da inklusiboa.

Baldintzazkoa: $p\rightarrow q$

Hizkuntza arruntaren kausa-ondorio erlazioa adierazteko erabiliko dugu: “ $p$ bada, $q$ ”, “ $p$ soilik baldin $q$ ”, “ $q$ $p$ bada”, “ $q$ beharrezkoa da $p$ izateko”, “ $p$ nahikoa da $q$ izateko”, “ez $p$ ez bada $q$ ”... $p$ aurrekaria eta $q$ atzekaria deituko ditugu.

Adibidez, $p$ “seme-alabak ditut” bada eta $q$ “emakumea naiz” bada, “Ez dut seme-alabarik ez banaiz emakume” esaldia $p\rightarrow q$ adieraziko dugu.

Baldintzabikoa: $p\leftrightarrow q$

“ $p$ nahikoa eta beharrezkoa da $q$ izateko”, “ $p$ baldin eta soilik baldin $q$ bada” bezalako esaldiak adierazteko erabiliko dugu.

Adibideak

“ $a$ bikoitia bada, $a-3$ bakoitia da eta $a^{2}-3$ bakoitia da”.

Proposizio atomikoak hauek dira:

- $p$ : “ $a$ bikoitia da”

- $q$ : “ $a-3$ bakoitia da”

- $r$ : “ $a^{2}-3$ bakoitia da”

Formalki, esaldia inplikazio bat da, aurrekaria lehenengo proposizioa eta atzekaria azkeneko bien konjuntzioa izanik. Proposizio-logikan honela adieraziko dugu esaldi hori:

$p\rightarrow (q\wedge r)$

Adierazpen hori beste era honetan ere irakur dezakegu: “ $a$ ez da bikoitia $a-3$ eta $a^{2}-3$ ez badira bakoitiak”.
“Mendira joango naiz edo hondartzara joango naiz soilik eguraldi ona egiten badu”.

- $p$ : “mendira joango naiz”

- $q$ : “hondartzara joango naiz”

- $r$ : “eguraldi ona egiten du”

Honela adieraziko dugu esaldia:

$(p\vee q)\rightarrow r$

Adierazpen hori bera erabiliko dugu honetarako: “Ni mendira edo hondartzara joan nadin beharrezkoa da eguraldi ona egin dezan”.
Programazioko “If p then q else r” egitura logikoak “p bada, orduan q, eta p ez bada, orduan r”. Bere adierazpena proposizio-kalkuluan hau da:

$(p\rightarrow q)\wedge (\neg p\rightarrow r)$

Oharra. Hizkuntza arruntean lokailuek eragiten dituzten esaldiak testuinguruaren edo zeinuen arabera ezagutzen ditugu. Lengoaia formalean parentesiak erabili beharko ditugu lokailu bakoitzari dagokion proposizioa zehazteko. Horrez gain, hizkuntza arruntean ez dira aipatutako bi lokailu jarraian agertzen.

Beraz, “forma” hauek idazteko arauak definitu beharko ditugu, hizkuntza arruntean esaldiak eraikitzeko erabiltzen ditugun arauetatik abiatuta.

Hau da, proposizioen “formak”, formula deituko ditugunak, idazteko sintaxia definitu beharko dugu, aurretik aipatu ditugun baldintzak kontuan izanik (lokailuak jarraian ez, proposizioen eta lokailuen arteko erlazioak definitu...).

1.3 Sintaxia

Lengoaia baten sintaxia zeinuen arteko erlazioaz arduratzen da; hau da, zeinuen segida ongi eratuak ezagutu eta eraikitzen dituen teoria da.

Definizioa. Proposizio-lengoaiaren ${\mathcal {A}}$ alfabetoa sinbolo hauek osatzen dute:

Enuntziatu bakunak adierazteko erabiliko ditugun sinboloak: ${\mathcal {P}}=\{p,q,r,s,\cdots \}$ . Sinbolo hauei atomo deituko diegu.
Lokailu logikoak (edo eragile logikoak) adierazteko erabiliko ditugun sinboloak: $\{\neg ,\wedge ,\vee ,\rightarrow ,\leftrightarrow \}$ .
Sinbolo inpropioak: parentesiak, $\{(,)\}$ .

${\mathcal {A}}={\mathcal {P}}\cup \{\neg ,\wedge ,\vee ,\rightarrow ,\leftrightarrow \}\cup \{(,)\}.$

Definizioa. Formula bat ${\mathcal {A}}$ multzoaren elementuekin eratutako segida finitu bat da. Adibidez, $p\vee \neg q\rightarrow$ , $pr(\vee s$ , $(q\vee t)$ ...

Definizioa. Proposizio-kalkuluan formula ongi eratuak (foe) arau hauei jarraituz eraikiko ditugu:

Atomo bat formula ongi eratua da.
$A$ eta $B$ formula ongi eratuak badira, $(\neg A)$ , $(A\wedge B)$ , $(A\vee B)$ , $(A\rightarrow B)$ eta $(A\leftrightarrow B)$ ere formula ongi eratuak dira.
Aurreko bi arauak kopuru finitu aldiz erabiliz lortzen diren formulak soilik dira formula ongi eratuak.

Esate baterako, hauek formula ongi eratuak dira: $p$ , $q$ , $r$ , $(\neg r)$ , $(p\vee q)$ eta $((p\vee q)\rightarrow (\neg r))$ . Beste hauek, ordea, ez dira: $(p\vee )$ eta $(q\rightarrow$ .

Hemendik aurrera, formulez hitz egiten dugunean formula ongi eratuei (foe) gatzaizkie.

Definizioa. $G$ formula emanik, $G$ formularen azpiformula $G$ formularen zatia den ondoz ondo eraikitako formula ongi eratu bat da.

Adibidez, $G=((p\vee q)\rightarrow (\neg r))$ bada, $(p\vee q)$ eta $(\neg r)$ azpiformulak dira, baina $(q\rightarrow (\neg r))$ ez da azpiformula.

Definizioa. Formula batean, lokailu baten agerpen baten irismena agerpen horrek eragiten dituen azpiformulak dira.

Formula bat idazterakoan parentesi batzuk ezaba ditzakegu:

Nahasteko arriskurik ez dagoenean. Adibidez, $((p\vee q)\rightarrow (\neg r))$ formula honela idatz dezakegu: $(p\vee q)\rightarrow \neg r$ .
Lokailuen artean hierarkia bat definituz:
- 1. maila: $\neg$ .
- 2. maila: $\wedge$ , $\vee$ .
- 3. maila: $\rightarrow$ , $\leftrightarrow$ .
Formula batean maila desberdinetako lokailuak agertzen direnean, maila goreneko lokailuak ez du parentesien beharrik izango.

Hierarkia hau aritmetikako eragitetarako erabiltzen dugun hierarkiaren antzekoa da. Adibidez, $((\neg p)\wedge q)\rightarrow r$ formula honela idatz dezakegu: $\neg p\wedge q\rightarrow r$ . Aritmetikan, $((-p)\cdot q)+r$ honela idazten dugun bezala: $-p\cdot q+r$ .

Adibideak.

$(\neg p)\vee (\neg q)$ formula $\neg p\vee \neg q$ idatz dezakegu; izan ere, $\vee$ lokailua $\neg$ lokailua baino maila altuagokoa denez, $(\neg p)$ eta $(\neg q)$ formulen parentesiak ken ditzakegu.

Lokailu baten agerpen bakoitzaren irismena adierazteko, agerpen hori eta bere irismena etiketatuko ditugu, honela:

${\begin{array}{ccc}{\underline {\neg p}}_{1}&\vee _{1}&{\underline {\neg q}}_{1}\\\neg _{2}{\underline {p}}_{2}&&\neg _{3}{\underline {q}}_{3}\\p&&q\end{array}}$
$(p\wedge q)\rightarrow (r\vee s)$ formula $p\wedge q\rightarrow r\vee s$ idatz dezakegu, $\rightarrow$ lokailua 3. mailakoa denez, $\wedge$ eta $\vee$ lokailuek lotzen dituzten aurreko bi formulen parentesiak ken ditzakegu.
${\begin{array}{ccc}{\underline {p\wedge q}}_{1}&\rightarrow _{1}&{\underline {r\vee s}}_{1}\\{\underline {p}}_{2}\wedge _{2}{\underline {q}}_{2}&&{\underline {r}}_{3}\vee _{3}{\underline {s}}_{3}\\p\quad q&&r\quad s\end{array}}$
$((r\wedge s)\vee p)\rightarrow ((\neg p)\wedge q)$ formula $(r\wedge s)\vee p\rightarrow \neg p\wedge q$ idatz dezakegu.

Ezin dugu parentesi gehiagorik kendu, $\wedge$ eta $\vee$ maila berekoak direlako.

${\begin{array}{ccc}{\underline {(r\wedge s)\vee p}}_{1}&\rightarrow _{1}&{\underline {\neg p\wedge q}}_{1}\\{\underline {(r\wedge s)}}_{2}\vee _{2}{\underline {p}}_{2}&&{\underline {\neg p}}_{4}\wedge _{4}{\underline {q}}_{4}\\{\underline {r}}_{3}\wedge _{3}{\underline {s}}_{3}\quad p&&\neg _{5}{\underline {p}}_{5}\quad q\\r\quad \quad s\quad \quad &&p\end{array}}$
$(p\leftrightarrow q\wedge r)\rightarrow \neg s$ formulan lokailuen agerpenen irismenak hauek dira:

${\begin{array}{ccc}{\underline {(p\leftrightarrow q\wedge r)}}_{1}&\rightarrow _{1}&{\underline {\neg s}}_{1}\\{\underline {p}}_{2}\leftrightarrow _{2}{\underline {q\wedge r}}_{2}&&\neg _{4}{\underline {s}}_{4}\\p\quad \quad {\underline {q}}_{3}\wedge _{3}{\underline {r}}_{3}&&s\\\quad \quad q\quad \quad r&&\end{array}}$

Hortaz, parentesiak jarriz gero, formula hau izango dugu:

$((p\leftrightarrow (q\wedge r))\rightarrow (\neg s))$ .

1.4 Semantika

Atomoak esaldi ezagutarazleak adierazteko erabiliko ditugu; eta horiek, bestelakoak ez bezala, egiazkoak edo faltsuak dira beti. Beraz, atomoak egiazko edo faltsu balioak har ditzaketen aldagaitzat hartuko ditugu. Proposizio atomiko baten egiazkotasunari edo faltsutasunari proposizioaren egia-balio deituko diogu.

Adibidez, $p$ aldagaiak egiazko edo faltsu balioak har ditzake, eta honela azalduko dugu:

 ${\begin{array}{ccc}{\begin{array}{c}p\\\hline E\\F\end{array}}&{\mbox{ edo }}&{\begin{array}{c}p\\\hline 1\\0\end{array}}\end{array}},$

non 1 balioak egiazkoa eta 0 balioak faltsua esan nahi duten.

$p$ aldagai baten ordez, $p$ eta $q$ bi aldagai hartzen baditugu, eta dagozkien egia-balioak konbinatzen baditugu, honelako taula bat lortuko dugu:

 ${\begin{array}{cc}{\begin{array}{cc}p&q\\\hline E&E\\E&F\\F&E\\F&F\end{array}}&\quad 4=2^{2}{\mbox{ aukera.}}\end{array}}$

Hiru aldagai baditugu, $p$ , $q$ eta $r$ taula hau izango dugu:

 ${\begin{array}{cc}{\begin{array}{ccc}p&q&r\\\hline E&E&E\\E&E&F\\E&F&E\\E&F&F\\F&E&E\\F&E&F\\F&F&E\\F&F&F\end{array}}&\quad 8=2^{3}{\mbox{ aukera.}}\end{array}}$

Oro har, $n$ atomo badauzkagu, $p_{1},p_{2},\ldots ,p_{n}$ , beren egia-balioen konbinazioen kopurua $2^{n}$ izango da.

Definizioa. Izan bedi $A$ formula ongi eratua eta izan bitez $p_{1},p_{2},\ldots ,p_{n}$ ( $p_{i}\neq p_{j},i\neq j$ ) $A$ formulan agertzen diren atomoak. $A$ formularen interpretazio bat $p_{1},p_{2},\ldots ,p_{n}$ atomoei egia-balioak esleitzean datza, honela: $p_{i}$ atomoei balio bana, $E$ edo $F$ , esleitzen zaie.

Formulak $n$ atomo baditu, formulak $2^{n}$ interpretazio desberdin izango ditu.

Adibidea. Izan bedi $A=(p\rightarrow q)\wedge (q\rightarrow r)$ . $A$ formulan 3 atomo desberdin agertzen dira. Hortaz, 8 interpretazio desberdin izango ditu $A$ formulak, aurreko taularen 8 lerroak hain zuzen.

$p_{1},p_{2},\ldots ,p_{n}$ badira $A$ formula ongi eratuan agertzen diren atomo desberdinak, $A$ formularen interpretazio bat multzo bat gisa adieraz dezakegu,

 $I=\{m_{1},\ldots ,m_{n}\},$

non $m_{i}$ bakoitza honela zehaztuko dugun:

$m_{i}={\begin{cases}p_{i}&p_{i}{\mbox{ atomoari }}E{\mbox{ balioa esleitzen badiogu}}\\\neg p_{i}&p_{i}{\mbox{ atomoari }}F{\mbox{ balioa esleitzen badiogu}}\end{cases}}$

Adibidea. Hona hemen $A=(p\rightarrow q)\wedge (q\rightarrow r)$ formularen interpretazio batzuk: $I_{1}=\{p,q,r\}$ , $I_{2}=\{p,q,\neg r\}$ , $I_{3}=\{p,\neg q,r\}$ , $I_{5}=\{\neg p,q,r\}$ , etab. $I_{3}$ interpretazioan, $p$ eta $r$ atomoei $E$ balioa esleitu diegu, eta $q$ atomoari $F$ balioa.

$G$ formula ongi eratua eta bere $I$ interpretazio bat emanik, $G$ formularen $I$ interpretaziorako egia-balioa kalkula dezakegu. Egia-balio hori $V(G,I)$ idatziko dugu eta ondoko bost arau hauek, lokailu bakoitzeko bat, aplikatuz kalkulatuko dugu:

Erregelak

Izan bitez $A$ eta $B$ bi formula ongi eratu, edozein:

$V((\neg A),I)=E$ izango da $V(A,I)=F$ denean eta $V((\neg A),I)=F$ izango da $V(A,I)=E$ denean. Taula eta definizioa:

$A$	$\neg A$
$E$	$F$
$F$	$E$

\quad \quad V((\neg A),I)=\left\{{\begin{array}{cl}E&V(A,I)=F{\mbox{ bada}}\\F&V(A,I)=E{\mbox{ bada}}\\\end{array}}\right..

$V((A\wedge B),I)=E$ izango da $V(A,I)=V(B,I)=E$ denean eta $V((A\wedge B),I)=F$ izango da bestelako kasuetan. Taula eta definizioa:

$A$	$B$	$A\wedge B$
$E$	$E$	$E$
$E$	$F$	$F$
$F$	$E$	$F$
$F$	$F$	$F$

\quad \quad

V((A\wedge B),I)=\left\{{\begin{array}{cl}E&V(A,I)=V(B,I)=E{\mbox{ bada}}\\F&{\mbox{ bestela}}\\\end{array}}\right..

$V((A\vee B),I)=F$ izango da $V(A,I)=V(B,I)=F$ denean eta $V((A\vee B),I)=E$ izango da bestelako kasuetan. Taula eta definizioa:

$A$	$B$	$A\vee B$
$E$	$E$	$E$
$E$	$F$	$E$
$F$	$E$	$E$
$F$	$F$	$F$

\quad \quad

V((A\vee B),I)=\left\{{\begin{array}{cl}F&V(A,I)=V(B,I)=F{\mbox{ bada}}\\E&{\mbox{ bestela}}\\\end{array}}\right..

Ohar dezagun $\vee$ disjuntzio inklusiboa dela. Disjuntzio esklusiboak $F$ bat izango luke lehenengo lerroan.

$V((A\rightarrow B),I)=F$ izango da $V(A,I)=E$ eta $V(B,I)=F$ direnean eta $V((A\rightarrow B),I)=E$ izango da bestelako kasuetan. Taula eta definizioa:

$A$	$B$	$A\rightarrow B$
$E$	$E$	$E$
$E$	$F$	$F$
$F$	$E$	$E$
$F$	$F$	$E$

$\quad \quad$

V((A\rightarrow B),I)=\left\{{\begin{array}{cl}F&V(A,I)=E{\mbox{ eta }}V(B,I)=F{\mbox{ bada}}\\E&{\mbox{ bestela}}\\\end{array}}\right..

Ohar dezagun, $V(A,I)=F$ bada, $V((A\rightarrow B),I)=E$ dela beti, nahiz eta $A$ eta $B$ formulen artean erlaziorik ez egon; berdin $V(B,I)=E$ denean.

$V((A\leftrightarrow B),I)=E$ izango da $V(A,I)=V(B,I)$ denean eta $V((A\leftrightarrow B),I)=F$ izango da bestelako kasuetan. Taula eta definizioa:

$A$	$B$	$A\leftrightarrow B$
$E$	$E$	$E$
$E$	$F$	$F$
$F$	$E$	$F$
$F$	$F$	$E$

\quad \quad

V((A\leftrightarrow B),I)=\left\{{\begin{array}{cl}E&V(A,I)=V(B,I){\mbox{ bada}}\\F&{\mbox{ bestela}}\\\end{array}}\right..

Definizioa. $G$ formula ongi eratua eta bere $I$ interpretazio bat emanik, $V(G,I)=E$ bada, $G$ formula $I$ interpretaziorako egiazkoa dela, edo $I$ interpretazioak $G$ formula egiaztatzen duela, edo $I$ interpretazioa $G$ formularen eredu bat dela, esango dugu. Eta $I\models G$ idatziko dugu. $V(G,I)=F$ bada, ordea, $G$ formula $I$ interpretaziorako faltsua dela, edo $I$ interpretazioak $G$ formula faltsutzen duela, esango dugu.

Aurreko bost erregelekin edozein formula ongi eraturen egia-balioa kalkula dezakegu interpretazio baterako.

Adibidea. Izan bedi $A=(p\rightarrow q)\wedge (q\rightarrow r)$ eta izan bedi $I_{3}=\{p,\neg q,r\}$ interpretazioa. Ikus ditzagun, lehendabizi, lokailuen agerpenen irismenak:

 ${\begin{array}{ccc}{\underline {(p\rightarrow q)}}_{1}&\wedge _{1}&{\underline {(q\rightarrow r)}}_{1}\\{\underline {p}}_{2}\rightarrow _{2}{\underline {q}}_{2}&&{\underline {q}}_{3}\rightarrow _{3}{\underline {r}}_{3}\end{array}}$

eta osa dezagun taula:

${\begin{array}{cccccc}p&q&r&p\rightarrow q&q\rightarrow r&A\\\hline E&F&E&F&E&F\\\end{array}}$

Beraz,  $I_{3}$  interpretazioak  $A$  formula faltsu egiten du.

Saia gaitezen, orain, $I_{7}=\{\neg p,\neg q,r\}$ interpretazioarekin. Taula hau da:

${\begin{array}{cccccc}p&q&r&p\rightarrow q&q\rightarrow r&A\\\hline F&F&E&E&E&E\\\end{array}}$

Beraz,  $I_{7}$  interpretazioak  $A$  formula egiaztatzen du. Hau da,  $I_{7}\models A$ .

Bide beretik, $A$ formularen egia-balioak kalkula ditzakegu $8$ interpretazioetarako.

Adibidean ikus dezakegun bezala, formula bat ez da berez egiazkoa edo faltsua, baizik eta egiazkoa edo faltsua da interpretazio baterako.

Formula baten interpretazio guztietarako egia-balioak erakusten dituen taula bati formularen egia-taula deituko diogu.

Adibideak.

$A=(p\rightarrow q)\wedge (q\rightarrow r)$ formularen egia-taula:

 ${\begin{array}{cccccc}p&q&r&p\rightarrow q&q\rightarrow r&A\\\hline E&E&E&E&E&E\\E&E&F&E&F&F\\E&F&E&F&E&F\\E&F&F&F&E&F\\F&E&E&E&E&E\\F&E&F&E&F&F\\F&F&E&E&E&E\\F&F&F&E&E&E\\\end{array}}$

$B=p\rightarrow (q\vee r\rightarrow (r\rightarrow \neg p))$ formularen egia-taula:

${\begin{array}{cccccccc}p&q&r&\neg p&q\vee r&r\rightarrow \neg p&q\vee r\rightarrow (r\rightarrow \neg p)&B\\\hline E&E&E&F&E&F&F&F\\E&E&F&F&E&E&E&E\\E&F&E&F&E&F&F&F\\E&F&F&F&F&E&E&E\\F&E&E&E&E&E&E&E\\F&E&F&E&E&E&E&E\\F&F&E&E&E&E&E&E\\F&F&F&E&F&E&E&E\end{array}}$

1.5 Baliozkotasuna. Inkontsistentzia. Baliokidetza logikoak

Definizioa. $A$ formula ongi eratu bat emanik, esango dugu

$A$ formula kontsistentea dela gutxienez $A$ formularen interpretazio baterako egiazkoa bada.
$A$ formula tautologia edo baliozkoa dela $A$ formularen interpretazio guztietarako egiazkoa bada. Eta $\models A$ adieraziko dugu.
$A$ formula inkontsistentea edo kontraesana dela ez bada kontsistentea, hau da, $A$ formularen interpretazio guztietarako faltsua bada.
$A$ formula baliogabea dela ez bada baliozkoa, hau da, gutxienez $A$ formularen interpretazio baterako faltsua bada.

Adibideak.

[baliozkotasuna]

Izan bedi $A=(p\rightarrow q)\wedge p\rightarrow q$ ; bere egia-taula hau da:
${\begin{array}{ccccc}p&q&p\rightarrow q&(p\rightarrow q)\wedge p&A\\\hline E&E&E&E&E\\E&F&F&F&E\\F&E&E&F&E\\F&F&E&F&E\end{array}}$

Hortaz, $A$ tautologia da, $\models A$ , eta kontsistentea da.
Izan bedi $B=(p\rightarrow q)\wedge (p\wedge \neg q)$ ; bere egia-taula hau da:
${\begin{array}{cccccc}p&q&p\rightarrow q&\neg q&p\wedge \neg q&B\\\hline E&E&E&F&F&F\\E&F&F&E&E&F\\F&E&E&F&F&F\\F&F&E&E&F&F\end{array}}$
```
Beraz,  $B$  inkontsistentea eta baliogabea da.
```

Izan bedi

C=p\vee \neg q

; bere egia-taula hau da:

${\begin{array}{cccc}p&q&\neg q&p\vee \neg q\\\hline E&E&F&E\\E&F&E&E\\F&E&F&F\\F&F&E&E\end{array}}$

Beraz, $C$ kontsistentea eta baliogabea da.

Egia-taularen arabera aukera hauek guztiak izango ditugu formula baterako: ${\mbox{Taula}}\left\{{\begin{array}{ll}{\mbox{Dena }}E&{\mbox{Tautologia; kontsistentea}}\\{\mbox{Batzuk }}E{\mbox{ eta beste batzuk }}F&{\mbox{Kontsistentea; baliogabea}}\\{\mbox{Dena }}F&{\mbox{Inkontsistentea; baliogabea}}\end{array}}\right.$

Ondoko taulan, emandako lau definizioen arteko nahasketa guztiak ikusiko ditugu:

	Kontsistentea	${\begin{array}{c}{\mbox{Inkontsistentea}}\\{\mbox{(Kontraesana)}}\end{array}}$
${\begin{array}{c}{\mbox{Baliozkoa}}\\{\mbox{(Tautologia)}}\end{array}}$	Bai	Ez
Baliogabea	Bai	Bai

Beste alde batetik, erraz ikus dezakegu, $A$ formula bat emanik,

$A$ tautologia da baldin eta soilik baldin $\neg A$ inkontsistentea bada.
$A$ inkontsistentea da baldin eta soilik baldin $\neg A$ tautologia bada.
$A$ tautologia bada, $A$ kontsistentea da; baina elkarrekikoa ez da, orokorrean, egiazkoa.
$A$ inkontsistentea bada, $A$ baliogabea da, eta elkarrekikoa ez da, orokorrean, egiazkoa.

[baliozkotasuna] adibidean, $C$ kontsistentea da, baina ez da tautologia. Eta $C$ baliogabea da, baina ez da kontraesana.

Definizioa. $A$ eta $B$ bi formula ongi eratuak logikoki baliokideak dira egia-balio berberak badituzte interpretazio guztietarako ( $V(A,I)=V(B,I)$ da $I$ interpretazio guztietarako), edo berdina dena, $A$ eta $B$ formulen egia-taulak berdinak direnean.

$A$ eta $B$ formula logikoki baliokideak badira, $A\equiv B$ idatziko dugu.

Adibidea. Izan bitez $A=p\rightarrow q$ eta $B=\neg p\vee q$ formulak; beren egia-taulak hauek dira:

${\begin{array}{ccccc}p&q&p\rightarrow q&\neg p&\neg p\vee q\\\hline E&E&E&F&E\\E&F&F&F&F\\F&E&E&E&E\\F&F&E&E&E\end{array}}$

Beraz, $A$ eta $B$ baliokideak dira, hots, $A\equiv B$ .

Baliokidetza logikoak

Baliokidetza logikoen artean hauek aipatuko ditugu: $A$ , $B$ eta $C$ formula ongi eratuak emanik,

Elkartze-legeak (ELKAR)
$(A\wedge B)\wedge C\equiv A\wedge (B\wedge C)\quad \quad (A\vee B)\vee C\equiv A\vee (B\vee C)$
Trukatze-legeak (TRUK)
$A\wedge B\equiv B\wedge A$

$A\vee B\equiv B\vee A$
Banatze-legeak (BANA)
$A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$

$A\vee (B\wedge C)\equiv (A\vee B)\wedge (A\vee C)$
Tautologiak (TAUT)
$A\wedge A\equiv A$

$A\vee A\equiv A$
Ukapen bikoitza (UB)
$\neg \neg A\equiv A$
De Morganen legeak (DeM)
$\neg (A\wedge B)\equiv \neg A\vee \neg B$

$\neg (A\vee B)\equiv \neg A\wedge \neg B$
- Transposizioa (TRANS)
$A\rightarrow B\equiv \neg B\rightarrow \neg A$
Inplikazio materiala (INP)
$A\rightarrow B\equiv \neg A\vee B$
Baliokidetza materialak (BALIO)
$A\leftrightarrow B\equiv (A\rightarrow B)\wedge (B\rightarrow A)$

$A\leftrightarrow B\equiv (A\wedge B)\vee (\neg A\wedge \neg B)$
Esportazioa (ESP)
$(A\wedge B)\rightarrow C\equiv A\rightarrow (B\rightarrow C)$

Baliokidetza horiek frogatzeko, egia-taulak kalkulatuko genituzke, eta berdinak direla egiaztatuko genuke.

Adibideak.

9b) baliokidetza frogatzeko, bi formulen egia-taulak kalkulatuko ditugu: ${\begin{array}{cccccccc}A&B&A\leftrightarrow B&A\wedge B&\neg A&\neg B&\neg A\wedge \neg B&(A\wedge B)\vee (\neg A\wedge \neg B)\\\hline E&E&E&E&F&F&F&E\\E&F&F&F&F&E&F&F\\F&E&F&F&E&F&F&F\\F&F&E&F&E&E&E&E\\&&\uparrow &&&&&\uparrow \end{array}}$
$A$ , $B$ eta $C$ formulak edozein direnez gero, $p\wedge q\rightarrow r\vee s\equiv \neg (p\wedge q)\vee (r\vee s)$ baliokidetza ere beteko da.

Oharra. $\wedge$ eta $\vee$ lokailuen elkartze-legeak direla eta, $A\wedge B\wedge C$ eta $A\vee B\vee C$ parentesirik gabe idatz ditzakegu.

Hala ere, ezin izango dugu $A\wedge B\vee C$ idatzi, $(A\wedge B)\vee C\not \equiv A\wedge (B\vee C)$ delako.

${\begin{array}{ccccccc}A&B&C&A\wedge B&(A\wedge B)\vee C&B\vee C&A\wedge (B\vee C)\\\hline E&E&E&E&E&E&E\\E&E&F&E&E&E&E\\E&F&E&F&E&E&E\\E&F&F&F&F&F&F\\F&E&E&F&{\underline {E}}&E&{\underline {F}}\\F&E&F&F&F&E&F\\F&F&E&F&E&E&F\\F&F&F&F&F&F&F\end{array}}$

Teorema. Izan bitez $A$ eta $B$ bi formula ongi eratuak,

$A\equiv B{\mbox{ baldin eta soilik baldin }}\models (A\leftrightarrow B).$

Froga.

Soilik baldin: Demagun $A\equiv B$ dela. Horrek esan nahi du edozein $I$ interpretaziotarako $V(A,I)=V(B,I)$ dela. $\models (A\leftrightarrow B)$ frogatu behar dugu, hau da, edozein $I$ interpretaziotarako $V((A\leftrightarrow B),I)=E$ dela.

Izan bedi $I$ edozein interpretazio. Bi aukera daude:

$V(A,I)=E$ . Orduan, $A\equiv B$ denez, $V(B,I)=E$ izango dugu eta, hortaz, $V((A\leftrightarrow B),I)=E$ .
$V(A,I)=F$ . Orduan, $V(B,I)=F$ eta, berriro ere, $V((A\leftrightarrow B),I)=E$ .

Bi kasuetan frogatuta geratu da $V((A\leftrightarrow B),I)=E$ dela.

Baldin: Demagun $\models (A\leftrightarrow B)$ dela.

Izan bedi $I$ edozein interpretazio. Bi aukera daude:

$V(A,I)=E$ . Orduan, $\models (A\leftrightarrow B)$ denez, $V((A\leftrightarrow B),I)=E$ izango dugu eta, hortaz, $V(B,I)=E$ .
$V(A,I)=F$ . Orduan, $V((A\leftrightarrow B),I)=E$ denez, $V(B,I)=F$ izango dugu.

Beraz, edozein $I$ interpretaziotarako $V(A,I)=V(B,I)$ da eta, ondorioz, $A\equiv B$ . $\Box$

1.6 Ondorio logikoak. Baliozko argumentuak

Definizioa. $A_{1},\ldots ,A_{n}$ eta $B$ $n+1$ formula emanik, $B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa dela edo formuletatik logikoki deduzitzen dela esango dugu edozein $I$ interpretaziotarako, non $V(A_{1},I)=\cdots =V(A_{n},I)=E$ den, $V(B,I)=E$ ere bada.

$B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa bada, honela adieraziko dugu: $A_{1},\ldots ,A_{n}\Rightarrow B\;{\mbox{ edo }}\;A_{1},\ldots ,A_{n}\models B.$

Adibideak.

$q$ formula $p\rightarrow q$ eta $p$ formulen ondorio logikoa da.

${\begin{array}{ccc}p&q&p\rightarrow q\\\hline E&E&E\\E&F&F\\F&E&E\\F&F&E\end{array}}$

Bai $p$ formula bai $p\rightarrow q$ formula $E$ diren errenkadetan (lehenengo errenkada bakarrik) $q$ formula ere $E$ da.
Hala ere, $p$ ez da $p\rightarrow q$ eta $q$ formulen ondorio logikoa. Izan ere, lehenengo eta hirugarren errenkadetan $p\rightarrow q$ eta $q$ formulak $E$ dira, baina hirugarren errenkadan $p$ formula $F$ da.

Teorema. [dedukzioI] $A_{1},\ldots ,A_{n}$ eta $B$ $n+1$ formula emanik,

$B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa da baldin eta soilik baldin $\models (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ bada.

Froga.

Soilik baldin. Demagun $B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa dela. Frogatu beharko dugu $\models (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ dela, hau da, edozein $I$ interpretaziotarako $V(A_{1}\wedge \ldots \wedge A_{n}\rightarrow B,I)=E$ dela.

Izan bedi $I$ edozein interpretazio. Bi aukera daude:

$V(A_{1},I)=\cdots =V(A_{n},I)=E$ . Orduan, ondorio logikoaren definizioaren arabera, $V(B,I)=E$ izango dugu eta, hortaz, $V(A_{1}\wedge \ldots \wedge A_{n}\rightarrow B,I)=E$ ere bai.
$i$ baten baterako, $V(A_{i},I)=F$ . Orduan, $V(A_{1}\wedge \ldots \wedge A_{n},I)=F$ izango da eta, hortaz, $V(A_{1}\wedge \ldots \wedge A_{n}\rightarrow B,I)=E$ ere bai.

Baldin. Demagun, orain, $\models (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ dela. $B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa dela frogatu behar dugu, hau da, edozein $I$ interpretaziotarako, $V(A_{1},I)=\cdots =V(A_{n},I)=E$ bada, $V(B,I)=V$ ere izango dela.

Izan bedi $I$ edozein interpretazio, non $V(A_{1},I)=\cdots =V(A_{n},I)=E$ den. Orduan, $V(A_{1}\wedge \ldots \wedge A_{n},I)=E$ izango da. Horrez gain, $\models (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ izateagatik, $V(A_{1}\wedge \ldots \wedge A_{n}\rightarrow B,I)=E$ ere bada. Hortik $V(B,I)=E$ aterako dugu. $\Box$

Adibideak.

$q$ formula $p\rightarrow q$ eta $p$ formulen ondorio logikoa da. Hortaz, $\models ((p\rightarrow q)\wedge p\rightarrow q)$ . ${\begin{array}{ccccc}p&q&p\rightarrow q&(p\rightarrow q)\wedge p&(p\rightarrow q)\wedge p\rightarrow q\\\hline E&E&E&E&E\\E&F&F&F&E\\F&E&E&F&E\\F&F&E&F&E\end{array}}$
$p$ formula ez da $p\rightarrow q$ eta $q$ formulen ondorio logikoa. Hortaz, $(p\rightarrow q)\wedge q\rightarrow p$ formula baliogabea da. ${\begin{array}{ccccc}p&q&p\rightarrow q&(p\rightarrow q)\wedge q&(p\rightarrow q)\wedge q\rightarrow p\\\hline E&E&E&E&E\\E&F&F&F&E\\F&E&E&E&{\underline {F}}\\F&F&E&F&E\end{array}}$

Teorema. [dedukzioII] $A_{1},\ldots ,A_{n}$ eta $B$ $n+1$ formula emanik,

$B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa da baldin eta soilik baldin $A_{1}\wedge \ldots \wedge A_{n}\wedge \neg B$ formula inkontsistentea bada.

Teorema frogatu baino lehen, froga dezagun lema hau:

Lema. [baliolema] $\neg (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)\equiv A_{1}\wedge \ldots \wedge A_{n}\wedge \neg B$ .

[baliolema] Lemaren froga

$\neg (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)\equiv \neg (\neg (A_{1}\wedge \ldots \wedge A_{n})\vee B)$ (inplikazio materiala) $\equiv \neg \neg (A_{1}\wedge \ldots \wedge A_{n})\wedge \neg B$ (De Morganen legeak) $\equiv (A_{1}\wedge \ldots \wedge A_{n})\wedge \neg B$ (ukapen bikoitza) $\equiv A_{1}\wedge \ldots \wedge A_{n}\wedge \neg B$ (elkartze-legea).

Hortaz, $\neg (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)\equiv A_{1}\wedge \ldots \wedge A_{n}\wedge \neg B$ . $\Box$

[dedukzioII] Teoremaren froga

[dedukzioI] Teorema frogatzeko teknika bera erabil genezake, baina beste frogabide-mota bat erabiliko dugu.

[dedukzioI] Teoremaren arabera, $B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa da baldin eta soilik baldin $\models (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ bada. Beste aldetik, badakigu $\models (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ dela baldin eta soilik baldin $\neg (A_{1}\wedge \ldots \wedge A_{n}\rightarrow B)$ formula inkontsistentea bada. Lema erabiliz, azkeneko formula inkontsistentea da baldin eta soilik baldin $A_{1}\wedge \ldots \wedge A_{n}\wedge \neg B$ formula inkontsistentea bada, baliokideak direlako. Nahi genuena lortu dugu, $B$ formula $A_{1},\ldots ,A_{n}$ formulen ondorio logikoa da baldin eta soilik baldin $A_{1}\wedge \ldots \wedge A_{n}\wedge \neg B$ formula inkontsistentea bada. $\Box$

Adibideak. [ondolo]

$q$ formula $p\rightarrow q$ eta $p$ formulen ondorio logikoa da. Hortaz, $(p\rightarrow q)\wedge p\wedge \neg q$ formula inkontsistentea da.

$p$ formula ez da $p\rightarrow q$ eta $q$ formulen ondorio logikoa. Hortaz, $(p\rightarrow q)\wedge q\wedge \neg p$ formula kontsistentea da. ${\begin{array}{ccccccc}p&q&p\rightarrow q&\neg q&(p\rightarrow q)\wedge p\wedge \neg q&\neg p&(p\rightarrow q)\wedge q\wedge \neg p\\\hline E&E&E&F&F&F&F\\E&F&F&E&F&F&F\\F&E&E&F&F&E&{\underline {E}}\\F&F&E&E&F&E&F\end{array}}$
$p\vee q$ formula $p$ formularen ondorio logikoa da. Honela egiazta genezake: 1) definizioa erabiliz; 2) $\models (p\rightarrow p\vee q)$ egiaztatuz; 3) $p\wedge \neg (p\vee q)$ formula inkontsistentea dela egiaztatuz.

${\begin{array}{cccccc}p&q&p\vee q&p\rightarrow p\vee q&\neg (p\vee q)&p\wedge \neg (p\vee q)\\\hline E&E&E&E&F&F\\E&F&E&E&F&F\\F&E&E&E&F&F\\F&F&F&E&E&F\\-&-&-&&&\\&1&&2&&3\end{array}}$

Definizioa. Argumentu bat edo argumentu-eskema bat $P_{1},\ldots ,P_{n},C$ formula ongi eratuen multzo bat da, non $P_{1},\ldots ,P_{n}$ premisa deitzen diren eta $C$ ondorio deitzen den. Honela adieraziko dugu:

${\begin{array}{c}P_{1}\\\vdots \\P_{n}\\\hline C\end{array}}\quad \quad {\mbox{edo}}\quad \quad {\begin{array}{l}P_{1}\\\vdots \\P_{n}{\mbox{ / }}{\dot {..}}{\mbox{ }}C\end{array}}$

Definizioa. Argumentu bat baliozkoa da edo ongi eraikita dago ondorioa premisen ondorio logikoa bada edo premisetatik logikoki deduzitzen bada, hau da, ezinezkoa bada premisak $E$ izatea eta ondorioa $F$ izatea.

Argumentu bat baliogabea da edo gaizki eraikita dago ez bada baliozko argumentua.

Adibideak.

Baliozko argumentua

$\left.{\begin{array}{l}p\rightarrow q\\p\end{array}}\right\}$	Premisak
${\begin{array}{l}\hline q\\\end{array}}$	${\begin{array}{l}\hline {\mbox{ondorioa}}\\\end{array}}$

$\left.{\begin{array}{l}p\rightarrow q\\q\\\hline p\end{array}}\right\}$ Argumentu baliogabea
${\begin{array}{ll}{\begin{array}{ll}\left.{\begin{array}{l}p\vee q\\\neg p\\\hline q\end{array}}\right\}&{\mbox{baliozko argumentua}}\end{array}}&{\begin{array}{cccc}p&q&p\vee q&\neg p\\\hline E&E&E&F\\E&F&E&F\\F&E&{\underline {E}}&{\underline {E}}\\F&F&F&E\end{array}}\end{array}}$
${\begin{array}{ll}{\begin{array}{ll}\left.{\begin{array}{l}p\vee q\\p\\\hline q\end{array}}\right\}&{\mbox{argumentu baliogabea}}\end{array}}&{\begin{array}{ccc}p&q&p\vee q\\\hline E&E&E\\{\underline {E}}&F&{\underline {E}}\\F&E&E\\F&F&F\end{array}}\end{array}}$ Premisa egiazkoak izanik, ondorioa faltsua deneko kasua azpimarratu dugu, argumentua baliogabetzen duelako.

Baliozko argumentu-eskemak

Hona hemen ezagunak diren baliozko argumentu-eskema batzuk: $A,B,C,D$ edozein formula ongi eratu dira,

Modus Ponens (MP) ${\begin{array}{l}A\rightarrow B\\A\\\hline B\end{array}}$
Modus Tollens (MT) ${\begin{array}{l}A\rightarrow B\\\neg B\\\hline \neg A\end{array}}$
Silogismo Hipotetikoa (SH) ${\begin{array}{l}A\rightarrow B\\B\rightarrow C\\\hline A\rightarrow C\end{array}}$
Silogismo Disjuntiboa (SD) ${\begin{array}{l}A\vee B\\\neg A\\\hline B\end{array}}$
Dilema Eraikitzailea (DE) ${\begin{array}{l}(A\rightarrow B)\wedge (C\rightarrow D)\\A\vee C\\\hline B\vee D\end{array}}$
Dilema Suntsitzailea (DS) ${\begin{array}{l}(A\rightarrow B)\wedge (C\rightarrow D)\\\neg B\vee \neg D\\\hline \neg A\vee \neg C\end{array}}$
Konjuntzioaren Sinplifikazioa (KS) ${\begin{array}{l}A\wedge B\\\hline A\end{array}}$
Konjuntzioaren Konbinazioa (KK) ${\begin{array}{l}A\\B\\\hline A\wedge B\end{array}}$
Disjuntzioaren Batuketa (DB) ${\begin{array}{l}A\\\hline A\vee B\end{array}}$

Aurreko argumentuak baliozkoak direla egiazta dezakegu egia-taulen bidez. Esate baterako, silogismo disjuntiboa frogatzeko taula hau osatuko dugu:

${\begin{array}{cccc}A&B&A\vee B&\neg A\\\hline E&E&E&F\\E&F&E&F\\F&E&{\underline {E}}&{\underline {E}}\\F&F&F&E\end{array}}$

eta silogismo hipotetikoa frogatzeko beste hau:

${\begin{array}{cccccc}A&B&C&A\rightarrow B&B\rightarrow C&A\rightarrow C\\\hline E&E&E&{\underline {E}}&{\underline {E}}&E\\E&E&F&E&F&F\\E&F&E&F&E&E\\E&F&F&F&E&F\\F&E&E&{\underline {E}}&{\underline {E}}&E\\F&E&F&E&F&E\\F&F&E&{\underline {E}}&{\underline {E}}&E\\F&F&F&{\underline {E}}&{\underline {E}}&E\\\end{array}}$

Oharra. $A,B,C,D$ edozein foe direnez, argumentu hau ere baliozkoa da:

${\begin{array}{l}p\wedge q\rightarrow (r\rightarrow s)\\(r\rightarrow s)\rightarrow t\vee q\\\hline p\wedge q\rightarrow t\vee q\end{array}}$

Silogismo hipotetikoaren eskemari dagokio: $A=p\wedge q$ , $B=r\rightarrow s$ eta $C=t\vee q$ .

1.7 Dedukzio formala

1.7.1 Froga formala. Inferentzi erregelak

Argumentuek bi edo hiru atomo baino gehiago dituztenean, baliozkotasuna frogatzeko egia-taulak erabiltzea luze eta astun egiten da.

Bide motzago bat, argumentuak baliozkoak direla frogatzeko, argumentu elementalak erabiltzea da, baliozkoak direla badakigulako; inferentzi erregelak deitzen dira.

Adibidez, hau inferentzi erregela bat da:

${\begin{array}{l}A\rightarrow B\\A\\\hline B\end{array}}$

non $A$ eta $B$ edozein foe diren. Demagun argumentu hau baliozkoa dela frogatu nahi dugula:

 ${\begin{array}{ll}1.&p\wedge \neg s\rightarrow q\\2.&q\rightarrow r\\3.&p\wedge \neg s{\mbox{ / }}{\dot {..}}{\mbox{  }}r\end{array}}$

Erregela aplikatuz ( $A=p\wedge \neg s$ eta $B=q$ direnean), 1 eta 3 premisetatik hau aterako dugu:

 ${\begin{array}{ll}4.&q\end{array}}$

Erregela berriro aplikatuz ( $A=q$ eta $B=r$ direnean), 2 eta 4 formuletatik hau aterako dugu:

${\begin{array}{ll}5.&r\end{array}}$

ondorioa dena. Beraz, argumentua baliozkoa da.

Inferentzi erregelak

Hasiera batean 9 inferentzi erregela erabiliko ditugu, baliozko argumentu hauek, hain zuzen:

Modus Ponens (MP)
Modus Tollens (MT)
Silogismo Hipotetikoa (SH)
Silogismo Disjuntiboa (SD)
Dilema Eraikitzailea (DE)
Dilema Suntsitzailea (DS)
Konjuntzioaren Sinplifikazioa (KS)
Konjuntzioaren Konbinazioa (KK)
Disjuntzioaren Batuketa (DB)

Definizioa.

${\begin{array}{c}P_{1}\\\vdots \\P_{n}\\\hline C\end{array}}$

argumentu baten baliozkotasunaren froga formal bat formulen segida finitu bat da,  $S_{1},\ldots ,S_{m}$ , non:

$S_{m}=C$ .
$i=1,\ldots ,m$ balioetarako, $S_{i}$ edo premisa bat den edo segidaren aurreko formuletatik deduzitzen den inferentzi erregela baten bidez.

Interpretazio baterako, premisa guztiak egiazkoak direla suposatzen badugu, horietatik inferentzi erregelen bidez deduzituko ditugun formula guztiak egiazkoak izango dira, interpretazio horretarako. Hortaz, $S_{m}=C$ formula ere egiazkoa izango da, interpretazio horretarako.

${\begin{array}{ll}{\begin{array}{l}A\rightarrow B\\C\rightarrow D\\(\neg B\vee \neg D)\wedge (\neg A\vee \neg B)\\\hline \neg A\vee \neg C\end{array}}&{\begin{array}{lll}1.&\!\!A\rightarrow B&\!\!{\mbox{premisa}}\\2.&\!\!C\rightarrow D&\!\!{\mbox{premisa}}\\3.&\!\!(\neg B\vee \neg D)\wedge (\neg A\vee \neg B)&\!\!{\mbox{premisa /}}{\dot {..}}\,\neg A\vee \neg C\\4.&\!\!(A\rightarrow B)\wedge (C\rightarrow D)&\!\!{\mbox{KK(1,2)}}\\5.&\!\!\neg B\vee \neg D&\!\!{\mbox{KS(3)}}\\6.&\!\!\neg A\vee \neg C&\!\!{\mbox{DS(4,5)}}\end{array}}\end{array}}$
${\begin{array}{ll}{\begin{array}{l}A\vee (B\rightarrow D)\\\neg C\rightarrow (D\rightarrow E)\\A\rightarrow C\\\neg C\\\hline B\rightarrow E\end{array}}&{\begin{array}{lll}1.&A\vee (B\rightarrow D)&{\mbox{premisa}}\\2.&\neg C\rightarrow (D\rightarrow E)&{\mbox{premisa}}\\3.&A\rightarrow C&{\mbox{premisa}}\\4.&\neg C&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}B\rightarrow E\\5.&\neg A&{\mbox{MT(3,4)}}\\6.&B\rightarrow D&{\mbox{SD(1,5)}}\\7.&D\rightarrow E&{\mbox{MP(2,4)}}\\8.&B\rightarrow E&{\mbox{SH(6,7)}}\end{array}}\end{array}}$
${\begin{array}{lll}1.&A\wedge B\rightarrow (A\rightarrow D\wedge E)&{\mbox{premisa}}\\2.&(A\wedge B)\wedge C&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}D\vee E\\3.&A\wedge B&{\mbox{KS(2)}}\\4.&A\rightarrow D\wedge E&{\mbox{MP(1,3)}}\\5.&A&{\mbox{KS(3)}}\\6.&D\wedge E&{\mbox{MP(4,5)}}\\7.&D&{\mbox{KS(6)}}\\8.&D\vee E&{\mbox{DB(7)}}\end{array}}$
${\begin{array}{lll}1.&J\rightarrow K&{\mbox{premisa}}\\2.&J\vee (K\vee \neg L)&{\mbox{premisa}}\\3.&\neg K&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}\neg L\wedge \neg K\\4.&\neg J&{\mbox{MT(1,3)}}\\5.&K\vee \neg L&{\mbox{SD(2,4)}}\\6.&\neg L&{\mbox{SD(5,3)}}\\7.&\neg L\wedge \neg K&{\mbox{KK(6,3)}}\end{array}}$

1.7.2 Ordezkapen-erregela

Baliozko argumentu askoren kasuan beren baliozkotasuna ezin da bederatzi inferentzi erregela horien bidez frogatu. Adibidez,

 ${\begin{array}{l}A\wedge B\\\hline B\end{array}}$

baliozko argumentuaren froga formalak inferentzi erregela gehiago behar ditu.

Izan bitez $A$ foe bat, $A$ formularen $B$ azpiformula bat eta $B'$ beste foe bat, non $B\equiv B'$ den. $A'$ idatziko dugu $A$ formulan $B$ azpiformularen ordez $B'$ formula jartzean lortzen den formula adierazteko.

Adibideak.

Izan bedi $A=p\rightarrow q\vee \neg r$ formula. $B=q\vee \neg r$ $A$ formularen azpiformula bat da. Bestalde, $B=q\vee \neg r\equiv \neg r\vee q=B'$ . Beraz, $A'=p\rightarrow \neg r\vee q$ izango da.
Izan bitez $A=p\wedge s\leftrightarrow (\neg q\rightarrow t)$ formula bat eta $B=\neg q\rightarrow t$ . $B=\neg q\rightarrow t\equiv \neg \neg q\vee t=B'$ azpiformula bat. Orduan, $A'=p\wedge s\leftrightarrow (\neg \neg q\vee t)$ izango da.

Ohar gaitezen $A\equiv A'$ dela; izan ere, $A$ eta $A'$ formulen egia-taulak kalkulatzerakoan, diferentzia bakarra $B$ eta $B'$ azpiformulak dira; baina horiek egia-taula berdinak dituzte.

Ordezkapen-erregelak $A$ formulatik $A'$ formula deduzitzeko aukera ematen digu, eta honela adieraziko dugu:

${\begin{array}{l}A\\\hline A'\end{array}}$

Ordezkapen-erregelari esker, aurreko bederatzi inferentzi erregelei beste hamar erregela erants diezazkiekegu, baliokidetza logikoetan oinarrituz.

Adibideak.

${\begin{array}{rll}\vdots &&\\k.&p\rightarrow q\vee \neg r&\\k+1.&p\rightarrow \neg r\vee q&{\mbox{TRUK(k)}}\\\vdots &&\end{array}}$
${\begin{array}{rll}\vdots &&\\k.&p\wedge s\leftrightarrow (\neg q\rightarrow t)&\\k+1.&p\wedge s\leftrightarrow (\neg \neg q\vee t)&{\mbox{INP(k)}}\\\vdots &&\end{array}}$
Baliozkotasunaren froga formala argumentu honetarako: $A\wedge B$ / ${\dot {..}}$ $B$ . ${\begin{array}{rll}1.&A\wedge B&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}B\\2.&B\wedge A&{\mbox{TRUK(1)}}\\3.&B&{\mbox{KS(2)}}\end{array}}$

Diferentzia handi bat dago erregela honen eta aurreko bederatzi erregelen artean. [erregelak] atalean definitutako erregelak frogabide baten formula osoei aplikatu dizkiegu; ordezkapen-erregelaren barruan dauden hamar erregelak, ordea, formula osoei zein azpiformulei aplikatuko dizkiegu. Adibidez, konjuntzioaren sinplifikazioa formula osoei bakarrik aplika diezaiekegu: esaterako,

${\begin{array}{rll}\vdots &&\\k.&A\wedge B&\\k+1.&A&{\mbox{KS(k)}}\\\vdots &&\end{array}}$

argumentuan ongi aplikaturik dago, baina

${\begin{array}{rlll}\vdots &&&\\k.&A\wedge B\rightarrow C&&\\k+1.&A\rightarrow C&{\mbox{KS(k)}}&{\mbox{gaizki}}\\\vdots &&&\end{array}}$

argumentuan gaizki aplikaturik dago. Eta trukatze-legea, esate baterako, formula osoei aplika diezaiekegu,

${\begin{array}{rll}\vdots &&\\k.&A\wedge B&\\k+1.&B\wedge A&{\mbox{TRUK(k)}}\\\vdots &&\end{array}}$

bai eta azpiformulei ere,

${\begin{array}{rll}\vdots &&\\k.&A\wedge B\rightarrow C&\\k+1.&B\wedge A\rightarrow C&{\mbox{TRUK(k)}}\\\vdots &&\end{array}}$

Zerrendari beste erregela batzuk erants geniezazkioke, esate baterako, $A\wedge B$ / ${\dot {..}}$ $B$ . Baina zerrenda luzeegia eta erabiltezina izango genuke.

Beste alde batetik, inferentzi erregelen zerrendak erredundantziak ditu; esaterako Modus Tollens erregela ken genezake, beste erregelen bidez emaitza bera lor dezakegulako. Adibidez:

${\begin{array}{ll}{\begin{array}{lll}1.&A\vee B&{\mbox{premisa}}\\2.&A\rightarrow C&{\mbox{premisa}}\\3.&\neg C&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}B\\4.&\neg A&{\mbox{MT(2,3)}}\\5.&B&{\mbox{SD(1,4)}}\\&&\end{array}}&{\begin{array}{lll}&&\\&&\\&&\\4.&\neg C\rightarrow \neg A&{\mbox{TRANS(2)}}\\5.&\neg A&{\mbox{MP(4,3)}}\\6.&B&{\mbox{SD(1,5)}}\end{array}}\end{array}}$

Hala eta guztiz ere, Modus Tollens erregela sartu dugu, inferentzi erregela ezaguna eta intuiziozkoa delako. Berdin gertatzen da beste erregela batzuekin.

Adibideak.

${\begin{array}{lll}1.&A\vee B\rightarrow C\wedge D&{\mbox{premisa}}\\2.&\neg C&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}\neg B\\3.&\neg C\vee \neg D&{\mbox{DB(2)}}\\4.&\neg (C\wedge D)&{\mbox{DeM(3)}}\\5.&\neg (A\vee B)&{\mbox{MT(1,4)}}\\6.&\neg A\wedge \neg B&{\mbox{DeM(5)}}\\7.&\neg B\wedge \neg A&{\mbox{TRUK(6)}}\\8.&\neg B&{\mbox{KS(7)}}\end{array}}$
${\begin{array}{lll}1.&(E\wedge F)\wedge G&{\mbox{premisa}}\\2.&(F\leftrightarrow G)\rightarrow H\vee I&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}I\vee H\\3.&E\wedge (F\wedge G)&{\mbox{ELKAR(1)}}\\4.&(F\wedge G)\wedge E&{\mbox{TRUK(3)}}\\5.&F\wedge G&{\mbox{KS(4)}}\\6.&(F\wedge G)\vee (\neg F\wedge \neg G)&{\mbox{DB(5)}}\\7.&F\leftrightarrow G&{\mbox{BALIO(6)}}\\8.&H\vee I&{\mbox{MP(2,7)}}\\9.&I\vee H&{\mbox{TRUK(8)}}\end{array}}$
${\begin{array}{lll}1.&S\rightarrow T&{\mbox{premisa}}\\2.&S\vee T&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}T\\3.&T\vee S&{\mbox{TRUK(2)}}\\4.&\neg \neg T\vee S&{\mbox{UB(3)}}\\5.&\neg T\rightarrow S&{\mbox{INP(4)}}\\6.&\neg T\rightarrow T&{\mbox{SH(5,1)}}\\7.&\neg \neg T\vee T&{\mbox{INP(6)}}\\8.&T\vee T&{\mbox{UB(7)}}\\9.&T&{\mbox{TAUT(8)}}\end{array}}$

1.7.3 Baldintzazko frogaren erregela

$P\rightarrow C$ motako baldintzazko formula bat deduzitu nahi dugunean erabil dezakegun inferentzi erregela da. Adibidez, $A\rightarrow B$ / ${\dot {..}}$ $A\rightarrow A\wedge B$ .

Teorema. (Baldintzazko frogaren erregela)

${\begin{array}{ll}(1)&{\begin{array}{l}P_{1}\\\vdots \\P_{n}\\\hline P\rightarrow C\end{array}}\end{array}}$

argumentua baliozkoa da baldin eta soilik baldin

${\begin{array}{ll}(2)&{\begin{array}{l}P_{1}\\\vdots \\P_{n}\\P\\\hline C\end{array}}\end{array}}$

argumentua baliozkoa bada.

Froga.

(1) argumentua baliozkoa da baldin eta soilik baldin $P\rightarrow C$ formula $P_{1},\ldots ,P_{n}$ formulen ondorio logiko bat bada, baliozko argumentuaren definizioaren arabera.

[dedukzioI] Teorema aplikatuz, $P\rightarrow C$ formula $P_{1},\ldots ,P_{n}$ formulen ondorio logiko bat da baldin eta soilik baldin $\models (P_{1}\wedge \cdots \wedge P_{n}\rightarrow (P\rightarrow C))$ bada.

Eta hori horrela da baldin eta soilik baldin $\models (P_{1}\wedge \cdots \wedge P_{n}\wedge P\rightarrow C)$ bada, $P_{1}\wedge \cdots \wedge P_{n}\rightarrow (P\rightarrow C)\equiv P_{1}\wedge \cdots \wedge P_{n}\wedge P\rightarrow C$ (ESP) delako.

Eta azken hori beteko da baldin eta soilik baldin $C$ formula $P_{1},\ldots ,P_{n},P$ formulen ondorio logiko bat bada, [dedukzioI] Teorema erabiliz. Hau da, baldin eta soilik baldin (2) argumentua baliozkoa bada, baliozko argumentuaren definizioaren arabera. $\Box$

Erregela erabiltzeko bidea

$P_{1},\ldots ,P_{n}$ premisak dituen (1) argumentu bat emanik, $P\rightarrow C$ formula deduzitu nahi badugu, premisei $P$ hipotesia erantsiko diegu, eta $C$ deduzituko dugu. $P$ hipotesia eranstean beste argumentu bat, (2), izango dugu, premisak $P_{1},\ldots ,P_{n},P$ dituena. Behin $C$ deduzitu eta gero, $P$ hipotesia baztertuko dugu eta, baldintzazko frogaren erregela aplikatuz, $P\rightarrow C$ deduzituko dugu; hau da, $P\rightarrow C$ formula $P_{1},\ldots ,P_{n}$ formuletatik deduzituko dugu. Hori dena honela adieraziko dugu:

${\begin{array}{lrcl}&1.&P_{1}&{\mbox{Premisa.}}\\&\vdots &\vdots &\\&n.&P_{n}&{\mbox{Premisa.}}\\&\vdots &\vdots &\\\rightarrow &m.&P&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}C\\\vline &\vdots &\vdots &\\\vline &k.&C&\\--&--&--&\\&k+1.&P\rightarrow C&{\mbox{BFE(m-k)}}\end{array}}$

Idazkera horrekin adierazi nahi dugu $m+1$ etik $k$ ra bitartean formulak $P_{1},\ldots ,P_{n},P$ premisak erabiliz deduzitu ditugula ((2) argumentua). $k+1$ formula, aldiz, $P_{1},\ldots ,P_{n}$ premisetatik deduzitu dugu ((1) argumentua), $P$ hipotesia baztertu dugu.

${\begin{array}{lrll}&1.&A\rightarrow B&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}A\rightarrow A\wedge B\\\rightarrow &2.&A&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}A\wedge B\\\vline &3.&B&{\mbox{MP(1,2)}}\\\vline &4.&A\wedge B&{\mbox{KK(2,3)}}\\--&--&--&\\&5.&A\rightarrow A\wedge B&{\mbox{BFE(2-4)}}\end{array}}$
${\begin{array}{lrll}&1.&T\rightarrow E&{\mbox{premisa}}\\&2.&A\rightarrow L&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}T\vee A\rightarrow L\vee E\\\rightarrow &3.&T\vee A&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}L\vee E\\\vline &4.&(T\rightarrow E)\wedge (A\rightarrow L)&{\mbox{KK(1,2)}}\\\vline &5.&E\vee L&{\mbox{DE(4,3)}}\\\vline &6.&L\vee E&{\mbox{TRUK(5)}}\\--&--&--&\\&7.&T\vee A\rightarrow L\vee E&{\mbox{BFE(3-6)}}\end{array}}$
${\begin{array}{llrll}&&1.&Q\rightarrow R&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}(P\rightarrow Q)\rightarrow (P\rightarrow R)\\\rightarrow &&2.&P\rightarrow Q&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}P\rightarrow R\\\vline &\rightarrow &3.&P&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}R\\\vline &\vline &4.&Q&{\mbox{MP(2,3)}}\\\vline &\vline &5.&R&{\mbox{MP(1,4)}}\\\vline &--&--&--&\\\vline &&6.&P\rightarrow R&{\mbox{BFE(3-5)}}\\--&--&--&--&\\&&7.&(P\rightarrow Q)\rightarrow (P\rightarrow R)&{\mbox{BFE(2-6)}}\end{array}}$
${\begin{array}{llrll}&&1.&(A\rightarrow C)\rightarrow D&{\mbox{premisa}}\\&&2.&B\rightarrow E&{\mbox{premisa}}\\&&3.&A\wedge B\rightarrow C&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}B\rightarrow E\wedge D\\\rightarrow &&4.&B&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}E\wedge D\\\vline &&5.&E&{\mbox{MP(2,4)}}\\\vline &\rightarrow &6.&A&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}C\\\vline &\vline &7.&A\wedge B&{\mbox{KK(6,4)}}\\\vline &\vline &8.&C&{\mbox{MP(3,7)}}\\\vline &--&--&--&\\\vline &&9.&A\rightarrow C&{\mbox{BFE(6-8)}}\\\vline &&10.&D&{\mbox{MP(1,9)}}\\\vline &&11.&E\wedge D&{\mbox{KK(5,10)}}\\--&--&--&--&\\&&12.&B\rightarrow E\wedge D&{\mbox{BFE(4-11)}}\end{array}}$

1.7.4 Zeharkako frogaren erregela edo absurdora eramateko erregela

Zeharkako frogaren metodoa, edo absurdora eramateko metodoa, frogatu nahi dugunaren aurkakoa suposatu eta kontraesan bat (formula inkontsistente bat) deduzitzean datza.

Formula inkontsistente bat $\Box$ adieraziko dugu (adibidez, $A\wedge \neg A$ ).

[aee] Teorema (Zeharkako frogaren erregela edo absurdora eramateko erregela)

${\begin{array}{ll}(1)&{\begin{array}{l}P_{1}\\\vdots \\P_{n}\\\hline C\end{array}}\end{array}}$ argumentua baliozkoa da baldin eta soilik baldin ${\begin{array}{ll}(2)&{\begin{array}{l}P_{1}\\\vdots \\P_{n}\\\neg C\\\hline \Box \end{array}}\end{array}}$ argumentua baliozkoa bada.

Erregela frogatzeko lema hau erabiliko dugu:

Lema. [boxezkon] Izan bedi $\Box$ foe inkontsistente bat eta izan bedi $A$ edozein foe. Orduan,

$A$ inkontsistentea da baldin eta soilik baldin $\models (A\rightarrow \Box )$ bada.

[boxezkon] Lemaren froga

Solik baldin. Demagun $A$ formula inkontsistentea dela; $\models (A\rightarrow \Box )$ frogatu behar dugu, hau da, edozein $I$ interpretaziotarako, $V((A\rightarrow \Box ),I)=V$ betetzen dela.

Izan bedi $I$ edozein interpretazio. $A$ formula inkontsistentea denez, $V(A,I)=F$ da eta, hortaz, $V((A\rightarrow \Box ),I)=V$ izango da.

Baldin. Demagun $\models (A\rightarrow \Box )$ dela. $A$ formula inkontsistentea dela frogatu behar dugu, hau da, edozein $I$ interpretaziotarako, $V(A,I)=F$ dela.

Izan bedi $I$ edozein interpretazio. $\models (A\rightarrow \Box )$ denez, $V((A\rightarrow \Box ),I)=V$ izango da eta, $\Box$ inkontsistentea denez, $V(\Box ,I)=F$ da. Hortaz, $V(A,I)=F$ . $\Box$

[aee] Teoremaren froga

(1) argumentua baliozkoa da baldin eta soilik baldin $C$ formula $P_{1},\ldots ,P_{n}$ formulen ondorio logikoa bada, baliozko argumentuaren definizioaren arabera. Hori horrela da baldin eta soilik baldin $P_{1}\wedge \cdots \wedge P_{n}\wedge \neg C$ formula inkontsistentea bada ([dedukzioII] Teorema) eta, lemaren arabera, baldin eta soilik baldin $\models (P_{1}\wedge \cdots \wedge P_{n}\wedge \neg C\rightarrow \Box )$ bada. Hori dena beteko da baldin eta soilik baldin $\Box$ formula $P_{1},\ldots ,P_{n},\neg C$ formulen ondorio logikoa bada ([dedukzioI] Teorema). Hau da, baldin eta soilik baldin (2) argumentua baliozkoa bada, baliozko argumentuaren definizioaren arabera. $\Box$

Erregela erabiltzeko bidea

$P_{1},\ldots ,P_{n}$ premisak dituen (1) argumentu bat emanik, $C$ formula deduzitu nahi badugu, $\neg C$ hipotesia erantsiko dugu eta kontraesan bat deduzituko dugu ( $A\wedge \neg A$ motako edozein formula). $\neg C$ hipotesia eranstean, $P_{1},\ldots ,P_{n},\neg C$ premisak dituen beste argumentu bat, (2), lortuko dugu. Behin kontraesana deduzitu eta gero, $\neg C$ hipotesia baztertuko dugu eta, absurdora eramateko erregela erabiliz, $C$ formula deduzituko dugu ( $C$ formula $P_{1},\ldots ,P_{n}$ formuletatik deduzituko dugu).

${\begin{array}{lrcl}&1.&P_{1}&{\mbox{Premisa}}\\&\vdots &\vdots &\\&n.&P_{n}&{\mbox{Premisa}}\\&\vdots &\vdots &\\\rightarrow &m.&\neg C&{\mbox{AEEren hipotesia / }}{\dot {..}}{\mbox{ }}\Box \\\vline &\vdots &\vdots &\\\vline &k.&\Box &\\--&--&--&\\&k+1.&C&{\mbox{AEE(m-k)}}\\\end{array}}$

$m+1$ etik $k$ ra formulak $P_{1},\ldots ,P_{n},\neg C$ premisak erabiliz deduzitu ditugu ((2) argumentua); $k+1$ formula, aldiz, $P_{1},\ldots ,P_{n}$ formuletatik deduzitu dugu ((1) argumentua).

Ikus ditzagun argumentu beraren bi froga formal, bata AEE erabiliz eta bestea erabili gabe. ${\begin{array}{lrll}&1.&p&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}q\vee (q\rightarrow r)\\\rightarrow &2.&\neg (q\vee (q\rightarrow r))&{\mbox{AEEren hipotesia / }}{\dot {..}}{\mbox{ }}\Box \\\vline &3.&\neg q\wedge \neg (q\rightarrow r)&{\mbox{DeM(2)}}\\\vline &4.&\neg q\wedge \neg (\neg q\vee r)&{\mbox{INP(3)}}\\\vline &5.&\neg q\wedge (\neg \neg q\wedge \neg r)&{\mbox{DeM(4)}}\\\vline &6.&(\neg q\wedge \neg \neg q)\wedge \neg r&{\mbox{ELKAR(5)}}\\\vline &7.&\neg q\wedge \neg \neg q&{\mbox{KS(6)}}\\--&--&--&\\&8.&q\vee (q\rightarrow r)&{\mbox{AEE(2-7)}}\end{array}}$ Absurdora eramateko erregela erabili gabe: ${\begin{array}{lrll}&1.&p&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}q\vee (q\rightarrow r)\\\rightarrow &2.&\neg (q\vee (q\rightarrow r))&{\mbox{BFEren hipotesia / }}{\dot {..}}{\mbox{ }}q\vee (q\rightarrow r)\\\vline &3.&\neg q\wedge \neg (q\rightarrow r)&{\mbox{DeM(2)}}\\\vline &4.&\neg q\wedge \neg (\neg q\vee r)&{\mbox{INP(3)}}\\\vline &5.&\neg q\wedge (\neg \neg q\wedge \neg r)&{\mbox{DeM(4)}}\\\vline &6.&(\neg \neg q\wedge \neg r)\wedge \neg q&{\mbox{TRUK(5)}}\\\vline &7.&\neg \neg q\wedge \neg r&{\mbox{KS(6)}}\\\vline &8.&\neg \neg q&{\mbox{KS(7)}}\\\vline &9.&q&{\mbox{UB(8)}}\\\vline &10.&q\vee (q\rightarrow r)&{\mbox{DB(9)}}\\--&--&--&\\&11.&\neg (q\vee (q\rightarrow r))\rightarrow q\vee (q\rightarrow r)&{\mbox{BFE(2-10)}}\\&12.&\neg \neg (q\vee (q\rightarrow r))\vee (q\vee (q\rightarrow r))&{\mbox{INP(11)}}\\&13.&(q\vee (q\rightarrow r))\vee (q\vee (q\rightarrow r))&{\mbox{UB(12)}}\\&14.&q\vee (q\rightarrow r)&{\mbox{TAUT(13)}}\end{array}}$
${\begin{array}{lrll}&1.&p&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}q\vee (r\rightarrow \neg q)\\\rightarrow &2.&\neg (q\vee (r\rightarrow \neg q))&{\mbox{AEEren hipotesia / }}{\dot {..}}{\mbox{ }}\Box \\\vline &3.&\neg q\wedge \neg (r\rightarrow \neg q)&{\mbox{DeM(2)}}\\\vline &4.&\neg q\wedge \neg (\neg r\vee \neg q)&{\mbox{INP(3)}}\\\vline &5.&\neg q\wedge (\neg \neg r\wedge \neg \neg q)&{\mbox{DeM(4)}}\\\vline &6.&\neg q\wedge (\neg \neg q\wedge \neg \neg r)&{\mbox{TRUK(5)}}\\\vline &7.&(\neg q\wedge \neg \neg q)\wedge \neg \neg r&{\mbox{ELKAR(6)}}\\\vline &8.&\neg q\wedge \neg \neg q&{\mbox{KS(7)}}\\--&--&--&\\&9.&q\vee (r\rightarrow \neg q)&{\mbox{AEE(2-8)}}\\\end{array}}$
Ikus ditzagun, berriro ere, argumentu beraren bi froga formal, bata AEE erabiliz eta bestea erabili gabe. ${\begin{array}{lr}{\begin{array}{lrll}&1.&\neg q\wedge s&{\mbox{premisa}}\\&2.&s\rightarrow \neg r&{\mbox{premisa}}\\&3.&\neg r\rightarrow \neg p\vee q&{\mbox{premisa / }}{\dot {..}}{\mbox{ }}\neg p\\\rightarrow &4.&\neg \neg p&{\mbox{AEEren hipotesia / }}{\dot {..}}{\mbox{ }}\Box \\\vline &5.&\neg q&{\mbox{KS(1)}}\\\vline &6.&\neg \neg p\wedge \neg q&{\mbox{KK(4,5)}}\\\vline &7.&\neg (\neg p\vee q)&{\mbox{DeM(6)}}\\\vline &8.&\neg \neg r&{\mbox{MT(3,7)}}\\\vline &9.&\neg s&{\mbox{MT(2,8)}}\\\vline &10.&s\wedge \neg q&{\mbox{TRUK(1)}}\\\vline &11.&s&{\mbox{KS(10)}}\\\vline &12.&s\wedge \neg s&{\mbox{KK(11,9)}}\\--&--&--&\\&13.&\neg p&{\mbox{AEE(4-12)}}\\\end{array}}&{\begin{array}{rll}&&\\&&\\&&\\4.&s\wedge \neg q&{\mbox{TRUK(1)}}\\5.&s&{\mbox{KS(4)}}\\6.&\neg r&{\mbox{MP(2,5)}}\\7.&\neg p\vee q&{\mbox{MP(3,6)}}\\8.&q\vee \neg p&{\mbox{TRUK(7)}}\\9.&\neg q&{\mbox{KS(1)}}\\10.&\neg p&{\mbox{SD(8,9)}}\\&&\\&&\\&&\end{array}}\end{array}}$

MD-liburua/Proposizio-logika

Edukiak

1. Gaia: Proposizio-logika

1.1 Sarrera

1.2 Proposizio-kalkulua. Esaldien formalizazioa

1.3 Sintaxia

1.4 Semantika

1.5 Baliozkotasuna. Inkontsistentzia. Baliokidetza logikoak

1.6 Ondorio logikoak. Baliozko argumentuak

1.7 Dedukzio formala

1.7.1 Froga formala. Inferentzi erregelak

1.7.2 Ordezkapen-erregela

1.7.3 Baldintzazko frogaren erregela

1.7.4 Zeharkako frogaren erregela edo absurdora eramateko erregela