Matematika Diskretua/Proposizio logika

1. Gaia: Proposizio-logika

1.1 Sarrera

Hizkuntzan adierazpen-perpausak, aginte-perpausak eta galde-perpausak erabiltzen ditugu. Ezagutza, funtsean, lehenek deskribatzen dute. Ezagutza bi bidetik jaso dezakegu: gertakariak edo ideiak egiaztatuz, adierazpen-perpausen bidez, edo dedukzioaren bidez.

Logika formalaren helburua dedukzioa (arrazoibidea, inferentzia, argudiatzea) da. Dedukzioa ezagutzen diren datu batzuetatik ezagutza berria 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. Adibidez, 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-logika eta Predikatu-logika.

Proposizio-logika: hizkuntza arruntaren adierazpen-perpausa bakunak (proposizioak) oinarrizko elementutzat hartuko ditugu, eta adierazi.

Predikatu-logika: 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-logika. 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 bakuna (proposizio atomikoa) informazioa duen hizkuntzaren gutxieneko unitatetzat har dezakegu, 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-logikan; predikatu-logikan, 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-logikan 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 dizkiona. Gorago esan bezala, lokailu bera, informazio-edukiaren ikuspuntutik, hizkuntza arruntaren zenbait elementuren bidez gauza daiteke.

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

Proposizio-logikaren 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 edo inplikazioa: →
  • 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: $\mathrm{\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 edo inplikazioa: $p\to 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 (baldintza) eta $q$ atzekaria (ondorioa) deituko ditugu.

Baldintzabikoa: $p\leftrightarrow q$

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

Adibideak

1. “$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\to (q\wedge r)$

   Adierazpen hori beste era honetan ere irakur dezakegu: “$a$ ez da bikoitia $a-3$ eta $a^2-3$ ez badira bakoitiak”.

2. “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)\to r$

   Adierazpen hori bera erabiliko dugu honetarako: “Ni mendira edo hondartzara joateko, beharrezkoa da eguraldi ona egitea”.

3. Programazioko “If p then q else r” egitura logikoak “p bada, orduan q, eta p ez bada, orduan r”. Bere adierazpena proposizio-logikan hau da:

   $(p\to q)\wedge (\mathrm{\neg }p\to r)$

Oharra. Hizkuntza arruntean, testuinguruak eta keinuek lagundu egiten dute esaldien arteko loturak ulertzen. Lengoaia formalean parentesiak erabili beharko ditugu lokailu bakoitzari dagokion proposizioa zehazteko. Horrez gain, hizkuntza arruntean ez dira gorago 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.

1.1 Definizioa. Proposizio-lengoaiaren $𝒜$ alfabetoa sinbolo hauek osatzen dute:

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

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

1.2 Definizioa. Formula bat $𝒜$ multzoaren elementuekin eratutako segida finitu bat da. Adibidez, $p\vee \mathrm{\neg }q\to$, $pr(\vee s$, $(q\vee t)$...

1.3 Definizioa. Proposizio-logikan ongi eratutako formulak (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. Aurreko bi arauak kopuru finitu aldiz erabiliz lortzen diren formulak soilik dira ongi eratutako formulak.

Adibidez, hauek ongi eratutako formulak dira: $p$, $q$, $r$, $(\mathrm{\neg }r)$, $(p\vee q)$ eta $((p\vee q)\to (\mathrm{\neg }r))$. Beste hauek, ordea, ez dira: $(p\vee )$ eta $(q\to$.

Hemendik aurrera, formulez hitz egiten dugunean ongi eratutako formulei (oef) buruz arituko gara.

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

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

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

Formula bat idazterakoan parentesi batzuk ezaba ditzakegu:

1. Nahasteko arriskurik ez dagoenean. Adibidez, $((p\vee q)\to (\mathrm{\neg }r))$ formula honela idatz dezakegu: $(p\vee q)\to \mathrm{\neg }r$.

2. Lokailuen artean hierarkia bat definituz:

   • 1. maila: $\mathrm{\neg }$.

   • 2. maila: $\wedge$, $\vee$.

   • 3. maila: $\to$, $\leftrightarrow$.

   Formula batean maila desberdinetako lokailuak agertzen direnean, maila goreneko lokailuak ez du parentesien beharrik izango.

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

1.6 Adibideak.

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

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

   $\begin{array}{ccc}{\underset{\_}{\mathrm{\neg }p}}_1& {\vee }_1& {\underset{\_}{\mathrm{\neg }q}}_1\\ {\mathrm{\neg }}_2{\underset{\_}{p}}_2& & {\mathrm{\neg }}_3{\underset{\_}{q}}_3\\ p& & q\end{array}$

2. $(p\wedge q)\to (r\vee s)$ formula $p\wedge q\to r\vee s$ idatz dezakegu, $\to$ lokailua 3. mailakoa denez, $\wedge$ eta $\vee$ lokailuek lotzen dituzten $(p\wedge q)$ eta $(r\vee s)$ formulen parentesiak ken ditzakegu.

   $\begin{array}{ccc}{\underset{\_}{p\wedge q}}_1& {\to }_1& {\underset{\_}{r\vee s}}_1\\ {\underset{\_}{p}}_2{\wedge }_2{\underset{\_}{q}}_2& & {\underset{\_}{r}}_3{\vee }_3{\underset{\_}{s}}_3\\ pq& & rs\end{array}$

3. $((r\wedge s)\vee p)\to ((\mathrm{\neg }p)\wedge q)$ formula $(r\wedge s)\vee p\to \mathrm{\neg }p\wedge q$ idatz dezakegu.

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

   $\begin{array}{ccc}{\underset{\_}{(r\wedge s)\vee p}}_1& {\to }_1& {\underset{\_}{\mathrm{\neg }p\wedge q}}_1\\ {\underset{\_}{(r\wedge s)}}_2{\vee }_2{\underset{\_}{p}}_2& & {\underset{\_}{\mathrm{\neg }p}}_4{\wedge }_4{\underset{\_}{q}}_4\\ {\underset{\_}{r}}_3{\wedge }_3{\underset{\_}{s}}_{3}p& & {\mathrm{\neg }}_5{\underset{\_}{p}}_{5}q\\ rs& & p\end{array}$

4. $(p\leftrightarrow q\wedge r)\to \mathrm{\neg }s$ formulan lokailuen agerpenen irismenak hauek dira:

   $\begin{array}{ccc}{\underset{\_}{(p\leftrightarrow q\wedge r)}}_1& {\to }_1& {\underset{\_}{\mathrm{\neg }s}}_1\\ {\underset{\_}{p}}_2{\leftrightarrow }_2{\underset{\_}{q\wedge r}}_2& & {\mathrm{\neg }}_4{\underset{\_}{s}}_4\\ p{\underset{\_}{q}}_3{\wedge }_3{\underset{\_}{r}}_3& & s\\ qr& & \end{array}$

   Hortaz, parentesiak jarriz gero, formula hau izango dugu:

   $((p\leftrightarrow (q\wedge r))\to (\mathrm{\neg }s))$.

1.4 Semantika

Atomoak adierazpen-perpausak idazteko erabiliko ditugu; eta horiek, beste perpausa motak 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\\ E\\ F\end{array}& \text{ edo }& \begin{array}{c}p\\ 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\\ E& E\\ E& F\\ F& E\\ F& F\end{array}& 4=2^2\text{ aukera.}\end{array}$

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

$\begin{array}{cc}\begin{array}{ccc}p& q& r\\ 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}& 8=2^3\text{ aukera.}\end{array}$

Oro har, $n$ atomo badauzkagu, $p_1,p_2,\dots ,p_n$, beren egia-balioen konbinazioen kopurua $2^n$ izango da.

1.7 Definizioa. Izan bitez $A$ ongi eratutako formula eta $p_1,p_2,\dots ,p_n$ ($p_i\ne p_j,i\ne j$) $A$ formulan agertzen diren atomoak. $A$ formularen interpretazio bat $p_1,p_2,\dots ,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.

1.8 Adibidea. Izan bedi $A=(p\to q)\wedge (q\to 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,\dots ,p_n$ badira $A$ ongi eratutako formulan agertzen diren atomo desberdinak, $A$ formularen interpretazio bat multzo bat gisa adieraz dezakegu,

$I=\{m_1,\dots ,m_n\},$ 

non $m_i$ bakoitza honela zehaztuko dugun:

$m_i=\{\begin{array}{cc}{p}_i,& p_i\text{ atomoari }E\text{ balioa esleitzen badiogu,}\\ \mathrm{\neg }{p}_i,& p_i\text{ atomoari }F\text{ balioa esleitzen badiogu.}\end{array}$

1.9 Adibidea. Hona hemen $A=(p\to q)\wedge (q\to r)$ formularen interpretazio batzuk: $I_1=\{p,q,r\}$, $I_2=\{p,q,\mathrm{\neg }r\}$, $I_3=\{p,\mathrm{\neg }q,r\}$, $I_5=\{\mathrm{\neg }p,q,r\}$, etab. $I_3$ interpretazioan, $p$ eta $r$ atomoei $E$ balioa esleitu diegu, eta $q$ atomoari $F$ balioa.

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

Erregelak

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

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

   $A$	$\mathrm{\neg }A$
   $E$	$F$
   $F$	$E$

   $V((\mathrm{\neg }A),I)=\{\begin{array}{cc}E,& V(A,I)=F\text{ bada,}\\ F,& V(A,I)=E\text{ bada.}\end{array}$

2. $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$

   $$ $V((A\wedge B),I)=\{\begin{array}{cc}E,& V(A,I)=V(B,I)=E\text{ bada,}\\ F,& \text{ bestela.}\end{array}$

3. $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$

   $$ $V((A\vee B),I)=\{\begin{array}{cc}F,& V(A,I)=V(B,I)=F\text{ bada,}\\ E,& \text{ bestela.}\end{array}$

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

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

   $A$	$B$	$A\to B$
   $E$	$E$	$E$
   $E$	$F$	$F$
   $F$	$E$	$E$
   $F$	$F$	$E$

   $$

   $V((A\to B),I)=\{\begin{array}{cc}F,& V(A,I)=E\text{ eta }V(B,I)=F\text{ bada,}\\ E,& \text{ bestela.}\end{array}$

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

5. $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$

   $$ $V((A\leftrightarrow B),I)=\{\begin{array}{cc}E,& V(A,I)=V(B,I)\text{ bada,}\\ F,& \text{ bestela.}\end{array}$

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

Aurreko bost erregelekin ongi eratutako edozein formularen egia-balioa kalkula dezakegu interpretazio baterako.

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

$\begin{array}{ccc}{\underset{\_}{(p\to q)}}_1& {\wedge }_1& {\underset{\_}{(q\to r)}}_1\\ {\underset{\_}{p}}_2{\to }_2{\underset{\_}{q}}_2& & {\underset{\_}{q}}_3{\to }_3{\underset{\_}{r}}_3\end{array}$ 

eta osa dezagun taula:

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

Beraz, $I_3$ interpretazioak $A$ formula faltsu egiten du.

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

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

Beraz, $I_7$ interpretazioak $A$ formula egiazko egiten du. Hau da, $I_7\models A$.

Modu berean, $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.

1.12 Adibideak.

1. $A=(p\to q)\wedge (q\to r)$ formularen egia-taula:

   $\begin{array}{cccccc}p& q& r& p\to q& q\to r& A\\ 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}$
   

2. $B=p\to (q\vee r\to (r\to \mathrm{\neg }p))$ formularen egia-taula:

   $\begin{array}{cccccccc}p& q& r& \mathrm{\neg }p& q\vee r& r\to \mathrm{\neg }p& q\vee r\to (r\to \mathrm{\neg }p)& B\\ 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

1.13 Definizioa. $A$ ongi eratutako formula bat izanik, esango dugu

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

1.14 Adibideak.

1. Izan bedi $A=(p\to q)\wedge p\to q$; bere egia-taula hau da:

   $\begin{array}{ccccc}p& q& p\to q& (p\to q)\wedge p& A\\ 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.

2. Izan bedi $B=(p\to q)\wedge (p\wedge \mathrm{\neg }q)$; bere egia-taula hau da:

   $\begin{array}{cccccc}p& q& p\to q& \mathrm{\neg }q& p\wedge \mathrm{\neg }q& B\\ 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.

3. Izan bedi $C=p\vee \mathrm{\neg }q$; bere egia-taula hau da:

   $\begin{array}{cccc}p& q& \mathrm{\neg }q& p\vee \mathrm{\neg }q\\ 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: $\text{Taula}\{\begin{array}{cc}\text{Dena }E& \text{Tautologia; kontsistentea}\\ \text{Batzuk }E\text{ eta beste batzuk }F& \text{Kontsistentea; baliogabea}\\ \text{Dena }F& \text{Inkontsistentea; baliogabea}\end{array}$

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

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

Bestalde, erraz ikus dezakegu, $A$ formula bat izanik,

1. $A$ tautologia da baldin eta soilik baldin $\mathrm{\neg }A$ inkontsistentea bada.
2. $A$ inkontsistentea da baldin eta soilik baldin $\mathrm{\neg }A$ tautologia bada.
3. $A$ tautologia bada, $A$ kontsistentea da; baina elkarrekikoa ez da, orokorrean, egiazkoa.
4. $A$ inkontsistentea bada, $A$ baliogabea da, eta elkarrekikoa ez da, orokorrean, egiazkoa.

1.14 Adibidean, $C$ kontsistentea da, baina ez da tautologia. Eta $C$ baliogabea da, baina ez da kontraesana.

1.15 Definizioa. $A$ eta $B$ ongi eratutako bi formulak 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.

1.16 Adibidea. Izan bitez $A=p\to q$ eta $B=\mathrm{\neg }p\vee q$ formulak; beren egia-taulak hauek dira:

$\begin{array}{ccccc}p& q& p\to q& \mathrm{\neg }p& \mathrm{\neg }p\vee q\\ 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$ ongi eratutako formulak izanik,

1. Elkartze-legeak (ELKAR)

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

2. Trukatze-legeak (TRUK)

   $A\wedge B\equiv B\wedge A$

   $A\vee B\equiv B\vee A$

3. 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)$

4. Tautologiak (TAUT)

   $A\wedge A\equiv A$

   $A\vee A\equiv A$

5. Ukapen bikoitza (UB)

   $\mathrm{\neg }\mathrm{\neg }A\equiv A$

6. De Morganen legeak (DeM)

   $\mathrm{\neg }(A\wedge B)\equiv \mathrm{\neg }A\vee \mathrm{\neg }B$

   $\mathrm{\neg }(A\vee B)\equiv \mathrm{\neg }A\wedge \mathrm{\neg }B$

   • Transposizioa (TRANS)

   $A\to B\equiv \mathrm{\neg }B\to \mathrm{\neg }A$

7. Inplikazio materiala (INP)

   $A\to B\equiv \mathrm{\neg }A\vee B$

8. Baliokidetza materialak (BALIO)

   $A\leftrightarrow B\equiv (A\to B)\wedge (B\to A)$

   $A\leftrightarrow B\equiv (A\wedge B)\vee (\mathrm{\neg }A\wedge \mathrm{\neg }B)$

9. Esportazioa (ESP)

   $(A\wedge B)\to C\equiv A\to (B\to C)$

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

1.17 Adibideak.

1. 9b) baliokidetza frogatzeko, bi formulen egia-taulak kalkulatuko ditugu: $\begin{array}{cccccccc}A& B& A\leftrightarrow B& A\wedge B& \mathrm{\neg }A& \mathrm{\neg }B& \mathrm{\neg }A\wedge \mathrm{\neg }B& (A\wedge B)\vee (\mathrm{\neg }A\wedge \mathrm{\neg }B)\\ 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}$
2. Baliokidetza logikoetako $A$, $B$ eta $C$ formulak edozein formula direnez gero, $A=p\wedge q$ eta $B=r\vee s$ badira, $p\wedge q\to r\vee s\equiv \mathrm{\neg }(p\wedge q)\vee (r\vee s)$ baliokidetza ere beteko da (inplikazio materiala).

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\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)\\ 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& \underset{\_}{E}& E& \underset{\_}{F}\\ F& E& F& F& F& E& F\\ F& F& E& F& E& E& F\\ F& F& F& F& F& F& F\end{array}$

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

$A\equiv B\text{ 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:

1. $V(A,I)=E$. Orduan, $A\equiv B$ denez, $V(B,I)=E$ izango dugu eta, hortaz, $V((A\leftrightarrow B),I)=E$.
2. $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:

1. $V(A,I)=E$. Orduan, $\models (A\leftrightarrow B)$ denez, $V((A\leftrightarrow B),I)=E$ izango dugu eta, hortaz, $V(B,I)=E$.
2. $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$. $◻$ $◼$ $◻$

1.6 Ondorio logikoak. Baliozko argumentuak

1.19 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.

$B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa bada, honela adieraziko dugu: $A_1,\dots ,A_n\Rightarrow B\text{ edo }{A}_1,\dots ,A_n\models B.$

1.20 Adibideak.

1. $q$ formula $p\to q$ eta $p$ formulen ondorio logikoa da.

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

   Bai $p$ formula bai $p\to q$ formula $E$ diren errenkadetan (lehenengo errenkada bakarrik) $q$ formula ere $E$ da.

2. Baina, $p$ ez da $p\to q$ eta $q$ formulen ondorio logikoa. Izan ere, lehenengo eta hirugarren errenkadetan $p\to q$ eta $q$ formulak $E$ dira, baina hirugarren errenkadan $p$ formula $F$ da.

1.21 Teorema. $A_1,\dots ,A_n$ eta $B$ $n+1$ formula izanik,

$B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa da baldin eta soilik baldin $\models (A_1\wedge \dots \wedge A_n\to B)$ bada.

Froga.

Soilik baldin. Demagun $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa dela. Frogatu beharko dugu $\models (A_1\wedge \dots \wedge A_n\to B)$ dela, hau da, $V(A_1\wedge \dots \wedge A_n\to B,I)=E$ dela edozein $I$ interpretaziotarako.

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

1. $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 \dots \wedge A_n\to B,I)=E$ ere bai.
2. $i$-ren baterako, $V(A_i,I)=F$. Orduan, $V(A_1\wedge \dots \wedge A_n,I)=F$ izango da eta, hortaz, $V(A_1\wedge \dots \wedge A_n\to B,I)=E$ ere bai.

Baldin. Demagun, orain, $\models (A_1\wedge \dots \wedge A_n\to B)$ dela. $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa dela frogatu behar dugu, hau da, $V(A_1,I)=\cdots =V(A_n,I)=E$ bada, $V(B,I)=V$ ere izango dela, edozein $I$ interpretaziotarako.

Izan bedi $I$ edozein interpretazio, non $V(A_1,I)=\cdots =V(A_n,I)=E$ den. Orduan, $V(A_1\wedge \dots \wedge A_n,I)=E$ izango da. Horrez gain, $\models (A_1\wedge \dots \wedge A_n\to B)$ izateagatik, $V(A_1\wedge \dots \wedge A_n\to B,I)=E$ ere bada. Hortik $V(B,I)=E$ aterako dugu. $◻$ $◼$ $◻$

1.22 Adibideak.

1. $q$ formula $p\to q$ eta $p$ formulen ondorio logikoa da. Hortaz, $\models ((p\to q)\wedge p\to q)$. $\begin{array}{ccccc}p& q& p\to q& (p\to q)\wedge p& (p\to q)\wedge p\to q\\ E& E& E& E& E\\ E& F& F& F& E\\ F& E& E& F& E\\ F& F& E& F& E\end{array}$
2. $p$ formula ez da $p\to q$ eta $q$ formulen ondorio logikoa. Hortaz, $(p\to q)\wedge q\to p$ formula baliogabea da. $\begin{array}{ccccc}p& q& p\to q& (p\to q)\wedge q& (p\to q)\wedge q\to p\\ E& E& E& E& E\\ E& F& F& F& E\\ F& E& E& E& \underset{\_}{F}\\ F& F& E& F& E\end{array}$

1.23 Teorema. $A_1,\dots ,A_n$ eta $B$ $n+1$ formula izanik,

$B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa da baldin eta soilik baldin $A_1\wedge \dots \wedge A_n\wedge \mathrm{\neg }B$ formula inkontsistentea bada.

Teorema frogatu baino lehen, froga dezagun lema hau:

1.24 Lema. $\mathrm{\neg }(A_1\wedge \dots \wedge A_n\to B)\equiv A_1\wedge \dots \wedge A_n\wedge \mathrm{\neg }B$.

1.24 Lemaren froga.

$\mathrm{\neg }(A_1\wedge \dots \wedge A_n\to B)\equiv \mathrm{\neg }(\mathrm{\neg }(A_1\wedge \dots \wedge A_n)\vee B)$ (inplikazio materiala) $\equiv \mathrm{\neg }\mathrm{\neg }(A_1\wedge \dots \wedge A_n)\wedge \mathrm{\neg }B$ (De Morganen legeak) $\equiv (A_1\wedge \dots \wedge A_n)\wedge \mathrm{\neg }B$ (ukapen bikoitza) $\equiv A_1\wedge \dots \wedge A_n\wedge \mathrm{\neg }B$ (elkartze-legea).

Hortaz, $\mathrm{\neg }(A_1\wedge \dots \wedge A_n\to B)\equiv A_1\wedge \dots \wedge A_n\wedge \mathrm{\neg }B$. $◻$ $◼$ $◻$

1.23 Teoremaren froga.

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

1.21 Teoremaren arabera, $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa da baldin eta soilik baldin $\models (A_1\wedge \dots \wedge A_n\to B)$ bada. Beste aldetik, badakigu $\models (A_1\wedge \dots \wedge A_n\to B)$ dela baldin eta soilik baldin $\mathrm{\neg }(A_1\wedge \dots \wedge A_n\to B)$ formula inkontsistentea bada. Lema erabiliz, azkeneko formula inkontsistentea da baldin eta soilik baldin $A_1\wedge \dots \wedge A_n\wedge \mathrm{\neg }B$ formula inkontsistentea bada, baliokideak direlako. Nahi genuena lortu dugu, $B$ formula $A_1,\dots ,A_n$ formulen ondorio logikoa da baldin eta soilik baldin $A_1\wedge \dots \wedge A_n\wedge \mathrm{\neg }B$ formula inkontsistentea bada. $◻$ $◼$ $◻$

1.25 Adibideak.

1. $q$ formula $p\to q$ eta $p$ formulen ondorio logikoa da. Hortaz, $(p\to q)\wedge p\wedge \mathrm{\neg }q$ formula inkontsistentea da.

   $p$ formula ez da $p\to q$ eta $q$ formulen ondorio logikoa. Hortaz, $(p\to q)\wedge q\wedge \mathrm{\neg }p$ formula kontsistentea da. $\begin{array}{ccccccc}p& q& p\to q& \mathrm{\neg }q& (p\to q)\wedge p\wedge \mathrm{\neg }q& \mathrm{\neg }p& (p\to q)\wedge q\wedge \mathrm{\neg }p\\ E& E& E& F& F& F& F\\ E& F& F& E& F& F& F\\ F& E& E& F& F& E& \underset{\_}{E}\\ F& F& E& E& F& E& F\end{array}$

2. $p\vee q$ formula $p$ formularen ondorio logikoa da. Honela egiazta genezake: 1) definizioa erabiliz; 2) $\models (p\to p\vee q)$ egiaztatuz; 3) $p\wedge \mathrm{\neg }(p\vee q)$ formula inkontsistentea dela egiaztatuz.

   $\begin{array}{cccccc}p& q& p\vee q& p\to p\vee q& \mathrm{\neg }(p\vee q)& p\wedge \mathrm{\neg }(p\vee q)\\ 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}$

1.26 Definizioa. Argumentu bat edo argumentu-eskema bat $P_1,\dots ,P_n,C$ ongi eratutako formulen multzo bat da, non $P_1,\dots ,P_n$ premisa deitzen diren eta $C$ ondorio deitzen den. Honela adieraziko dugu:

$\begin{array}{c}{P}_1\\ ⋮\\ P_n\\ C\end{array}\text{edo}\begin{array}{c}{P}_1\\ ⋮\\ P_n\text{ / }\dot{\mathrm{..}}C\end{array}$

1.27 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.

1.28 Adibideak.

1. Baliozko argumentua (ikus 1.25 Adibidea).

   $\begin{array}{c}p\to q\\ p\end{array}\}$	premisak
   $\begin{array}{c}q\end{array}$	$\begin{array}{c}\text{ondorioa}\end{array}$

2. Argumentu baliogabea (ikus 1.25 Adibidea).

   $\begin{array}{cc}\begin{array}{c}p\to q\\ q\\ p\end{array}\}& \end{array}$

3. Baliozko argumentua.

   $\begin{array}{cc}\begin{array}{cc}\begin{array}{c}p\vee q\\ \mathrm{\neg }p\\ q\end{array}\}& \end{array}& \begin{array}{cccc}p& q& p\vee q& \mathrm{\neg }p\\ E& E& E& F\\ E& F& E& F\\ F& E& \underset{\_}{E}& \underset{\_}{E}\\ F& F& F& E\end{array}\end{array}$

4. Argumentu baliogabea.

   $\begin{array}{cc}\begin{array}{cc}\begin{array}{c}p\vee q\\ p\\ q\end{array}\}& \end{array}& \begin{array}{ccc}p& q& p\vee q\\ E& E& E\\ \underset{\_}{E}& F& \underset{\_}{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$ ongi eratutako edozein formula dira,

1. Modus Ponens (MP) $\begin{array}{c}A\to B\\ A\\ B\end{array}$
2. Modus Tollens (MT) $\begin{array}{c}A\to B\\ \mathrm{\neg }B\\ \mathrm{\neg }A\end{array}$
3. Silogismo Hipotetikoa (SH) $\begin{array}{c}A\to B\\ B\to C\\ A\to C\end{array}$
4. Silogismo Disjuntiboa (SD) $\begin{array}{c}A\vee B\\ \mathrm{\neg }A\\ B\end{array}$
5. Dilema Eraikitzailea (DE) $\begin{array}{c}(A\to B)\wedge (C\to D)\\ A\vee C\\ B\vee D\end{array}$
6. Dilema Suntsitzailea (DS) $\begin{array}{c}(A\to B)\wedge (C\to D)\\ \mathrm{\neg }B\vee \mathrm{\neg }D\\ \mathrm{\neg }A\vee \mathrm{\neg }C\end{array}$
7. Konjuntzioaren Sinplifikazioa (KS) $\begin{array}{c}A\wedge B\\ A\end{array}$
8. Konjuntzioaren Konbinazioa (KK) $\begin{array}{c}A\\ B\\ A\wedge B\end{array}$
9. Disjuntzioaren Batuketa (DB) $\begin{array}{c}A\\ 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& \mathrm{\neg }A\\ E& E& E& F\\ E& F& E& F\\ F& E& \underset{\_}{E}& \underset{\_}{E}\\ F& F& F& E\end{array}$

eta silogismo hipotetikoa frogatzeko beste hau:

$\begin{array}{cccccc}A& B& C& A\to B& B\to C& A\to C\\ E& E& E& \underset{\_}{E}& \underset{\_}{E}& E\\ E& E& F& E& F& F\\ E& F& E& F& E& E\\ E& F& F& F& E& F\\ F& E& E& \underset{\_}{E}& \underset{\_}{E}& E\\ F& E& F& E& F& E\\ F& F& E& \underset{\_}{E}& \underset{\_}{E}& E\\ F& F& F& \underset{\_}{E}& \underset{\_}{E}& E\end{array}$

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

$\begin{array}{c}p\wedge q\to (r\to s)\\ (r\to s)\to t\vee q\\ p\wedge q\to t\vee q\end{array}$

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

1.7 Dedukzio formala

1.7.1 Froga formala. Inferentzia-erregelak

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

Argumentuak baliozkoak direla frogatzeko, bide motzago bat argumentu elementalak erabiltzea da, baliozkoak direla badakigulako; inferentzia-erregelak deitzen dira.

Adibidez, hau inferentzia-erregela bat da:

$\begin{array}{c}A\to B\\ A\\ B\end{array}$

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

$\begin{array}{cc}1.& p\wedge \mathrm{\neg }s\to q\\ 2.& q\to r\\ 3.& p\wedge \mathrm{\neg }s\text{ / }\dot{\mathrm{..}}r\end{array}$ 

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

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

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

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

ondorioa dena. Beraz, argumentua baliozkoa da.

Inferentzia-erregelak

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

1. Modus Ponens (MP)
2. Modus Tollens (MT)
3. Silogismo Hipotetikoa (SH)
4. Silogismo Disjuntiboa (SD)
5. Dilema Eraikitzailea (DE)
6. Dilema Suntsitzailea (DS)
7. Konjuntzioaren Sinplifikazioa (KS)
8. Konjuntzioaren Konbinazioa (KK)
9. Disjuntzioaren Batuketa (DB)

1.29 Definizioa. $P_1,\dots ,P_n$ premisak eta $C$ ondorioa dituen

$\begin{array}{c}{P}_1\\ ⋮\\ P_n\\ C\end{array}$

argumentu baten baliozkotasunaren froga formal bat $S_1,\dots ,S_m$ formulen segida finitu bat da, non:

1. $S_m=C$ den eta
2. $i=1,\dots ,m$ balioetarako, $S_i$ premisa bat den edo inferentzia-erregela baten bidez segidaren aurreko formuletatik deduzitzen den.

Interpretazio baterako, premisa guztiak egiazkoak direla suposatzen badugu, horietatik inferentzia-erregelen bidez deduzituko ditugun formula guztiak egiazkoak izango dira, interpretazio horretarako. Hortaz, $S_m=C$ formula ere egiazkoa izango da, interpretazio horretarako.

1.30 Adibideak. Hona hemen argumentu batzuen froga formalen adibideak:

1. ${\displaystyle }$

   $\begin{array}{cc}\begin{array}{c}A\to B\\ C\to D\\ (\mathrm{\neg }B\vee \mathrm{\neg }D)\wedge (\mathrm{\neg }A\vee \mathrm{\neg }B)\\ \mathrm{\neg }A\vee \mathrm{\neg }C\end{array}& \begin{array}{ccc}1.& A\to B& \text{premisa}\\ 2.& C\to D& \text{premisa}\\ 3.& (\mathrm{\neg }B\vee \mathrm{\neg }D)\wedge (\mathrm{\neg }A\vee \mathrm{\neg }B)& \text{premisa /}\dot{\mathrm{..}}\mathrm{\neg }A\vee \mathrm{\neg }C\\ 4.& (A\to B)\wedge (C\to D)& \text{KK(1,2)}\\ 5.& \mathrm{\neg }B\vee \mathrm{\neg }D& \text{KS(3)}\\ 6.& \mathrm{\neg }A\vee \mathrm{\neg }C& \text{DS(4,5)}\end{array}\end{array}$

2. ${\displaystyle }$

   $\begin{array}{cc}\begin{array}{c}A\vee (B\to D)\\ \mathrm{\neg }C\to (D\to E)\\ A\to C\\ \mathrm{\neg }C\\ B\to E\end{array}& \begin{array}{ccc}1.& A\vee (B\to D)& \text{premisa}\\ 2.& \mathrm{\neg }C\to (D\to E)& \text{premisa}\\ 3.& A\to C& \text{premisa}\\ 4.& \mathrm{\neg }C& \text{premisa / }\dot{\mathrm{..}}B\to E\\ 5.& \mathrm{\neg }A& \text{MT(3,4)}\\ 6.& B\to D& \text{SD(1,5)}\\ 7.& D\to E& \text{MP(2,4)}\\ 8.& B\to E& \text{SH(6,7)}\end{array}\end{array}$

3. ${\displaystyle }$

   $\begin{array}{ccc}1.& A\wedge B\to (A\to D\wedge E)& \text{premisa}\\ 2.& (A\wedge B)\wedge C& \text{premisa / }\dot{\mathrm{..}}D\vee E\\ 3.& A\wedge B& \text{KS(2)}\\ 4.& A\to D\wedge E& \text{MP(1,3)}\\ 5.& A& \text{KS(3)}\\ 6.& D\wedge E& \text{MP(4,5)}\\ 7.& D& \text{KS(6)}\\ 8.& D\vee E& \text{DB(7)}\end{array}$

4. ${\displaystyle }$

   $\begin{array}{ccc}1.& J\to K& \text{premisa}\\ 2.& J\vee (K\vee \mathrm{\neg }L)& \text{premisa}\\ 3.& \mathrm{\neg }K& \text{premisa / }\dot{\mathrm{..}}\mathrm{\neg }L\wedge \mathrm{\neg }K\\ 4.& \mathrm{\neg }J& \text{MT(1,3)}\\ 5.& K\vee \mathrm{\neg }L& \text{SD(2,4)}\\ 6.& \mathrm{\neg }L& \text{SD(5,3)}\\ 7.& \mathrm{\neg }L\wedge \mathrm{\neg }K& \text{KK(6,3)}\end{array}$

1.7.2 Ordezkapen-erregela

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

$\begin{array}{c}A\wedge B\\ B\end{array}$ 

baliozko argumentuaren froga formalak inferentzia-erregela gehiago behar ditu.

Izan bitez $A$ oef bat, $A$ formularen $B$ azpiformula bat eta $B^{\prime }$ beste oef bat, non $B\equiv B^{\prime }$ den. $A^{\prime }$ idatziko dugu $A$ formulan $B$ azpiformularen ordez $B^{\prime }$ formula jartzean lortzen den formula adierazteko.

1.31 Adibideak.

1. Izan bedi $A=p\to q\vee \mathrm{\neg }r$ formula. $B=q\vee \mathrm{\neg }r$ $A$ formularen azpiformula bat da. Bestalde, $B=q\vee \mathrm{\neg }r\equiv \mathrm{\neg }r\vee q=B^{\prime }$ (trukatze-legea). Beraz, $A^{\prime }=p\to \mathrm{\neg }r\vee q$ izango da.
2. Izan bitez $A=p\wedge s\leftrightarrow (\mathrm{\neg }q\to t)$ formula eta $B=\mathrm{\neg }q\to t$ azpiformula. Baliokidetza logiko hau dugu: $B=\mathrm{\neg }q\to t\equiv \mathrm{\neg }\mathrm{\neg }q\vee t=B^{\prime }$ (inplikazio materiala). Orduan, $A^{\prime }=p\wedge s\leftrightarrow (\mathrm{\neg }\mathrm{\neg }q\vee t)$ izango da.

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

Ordezkapen-erregelak $A$ formulatik $A^{\prime }$ formula deduzitzeko aukera ematen digu, eta honela adieraziko dugu:

$\begin{array}{c}A\\ A^{\prime }\end{array}$

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

1.32 Adibideak. Honela adieraziko dugu froga formal batean:

1. ${\displaystyle }$

   $\begin{array}{ccc}⋮& & \\ k.& p\to q\vee \mathrm{\neg }r& \\ k+1.& p\to \mathrm{\neg }r\vee q& \text{TRUK(k)}\\ ⋮& & \end{array}$

2. ${\displaystyle }$

   $\begin{array}{ccc}⋮& & \\ k.& p\wedge s\leftrightarrow (\mathrm{\neg }q\to t)& \\ k+1.& p\wedge s\leftrightarrow (\mathrm{\neg }\mathrm{\neg }q\vee t)& \text{INP(k)}\\ ⋮& & \end{array}$

3. Baliozkotasunaren froga formala argumentu honetarako: $A\wedge B$ / $\dot{\mathrm{..}}$ $B$. $\begin{array}{ccc}1.& A\wedge B& \text{premisa / }\dot{\mathrm{..}}B\\ 2.& B\wedge A& \text{TRUK(1)}\\ 3.& B& \text{KS(2)}\end{array}$

Diferentzia handi bat dago ordezkapen-erregelaren eta aurreko bederatzi inferentzia-erregelen artean. 1.7.1 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}{ccc}⋮& & \\ k.& A\wedge B& \\ k+1.& A& \text{KS(k)}\\ ⋮& & \end{array}$

argumentuan ongi aplikaturik dago, baina

$\begin{array}{cccc}⋮& & & \\ k.& A\wedge B\to C& & \\ k+1.& A\to C& \text{KS(k)}& \text{gaizki}\\ ⋮& & & \end{array}$

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

$\begin{array}{ccc}⋮& & \\ k.& A\wedge B& \\ k+1.& B\wedge A& \text{TRUK(k)}\\ ⋮& & \end{array}$

bai eta azpiformulei ere,

$\begin{array}{ccc}⋮& & \\ k.& A\wedge B\to C& \\ k+1.& B\wedge A\to C& \text{TRUK(k)}\\ ⋮& & \end{array}$

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

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

$\begin{array}{cc}\begin{array}{ccc}1.& A\vee B& \text{premisa}\\ 2.& A\to C& \text{premisa}\\ 3.& \mathrm{\neg }C& \text{premisa / }\dot{\mathrm{..}}B\\ 4.& \mathrm{\neg }A& \text{MT(2,3)}\\ 5.& B& \text{SD(1,4)}\\ & & \end{array}& \begin{array}{ccc}& & \\ & & \\ & & \\ 4.& \mathrm{\neg }C\to \mathrm{\neg }A& \text{TRANS(2)}\\ 5.& \mathrm{\neg }A& \text{MP(4,3)}\\ 6.& B& \text{SD(1,5)}\end{array}\end{array}$

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

1.33 Adibideak. Hona hemen argumentu batzuen froga formalak inferentzia-erregelak eta ordezkapen-erregela erabiliz.

1. ${\displaystyle }$

   $\begin{array}{ccc}1.& A\vee B\to C\wedge D& \text{premisa}\\ 2.& \mathrm{\neg }C& \text{premisa / }\dot{\mathrm{..}}\mathrm{\neg }B\\ 3.& \mathrm{\neg }C\vee \mathrm{\neg }D& \text{DB(2)}\\ 4.& \mathrm{\neg }(C\wedge D)& \text{DeM(3)}\\ 5.& \mathrm{\neg }(A\vee B)& \text{MT(1,4)}\\ 6.& \mathrm{\neg }A\wedge \mathrm{\neg }B& \text{DeM(5)}\\ 7.& \mathrm{\neg }B\wedge \mathrm{\neg }A& \text{TRUK(6)}\\ 8.& \mathrm{\neg }B& \text{KS(7)}\end{array}$

2. ${\displaystyle }$

   $\begin{array}{ccc}1.& (E\wedge F)\wedge G& \text{premisa}\\ 2.& (F\leftrightarrow G)\to H\vee I& \text{premisa / }\dot{\mathrm{..}}I\vee H\\ 3.& E\wedge (F\wedge G)& \text{ELKAR(1)}\\ 4.& (F\wedge G)\wedge E& \text{TRUK(3)}\\ 5.& F\wedge G& \text{KS(4)}\\ 6.& (F\wedge G)\vee (\mathrm{\neg }F\wedge \mathrm{\neg }G)& \text{DB(5)}\\ 7.& F\leftrightarrow G& \text{BALIO(6)}\\ 8.& H\vee I& \text{MP(2,7)}\\ 9.& I\vee H& \text{TRUK(8)}\end{array}$

3. ${\displaystyle }$

   $\begin{array}{ccc}1.& S\to T& \text{premisa}\\ 2.& S\vee T& \text{premisa / }\dot{\mathrm{..}}T\\ 3.& T\vee S& \text{TRUK(2)}\\ 4.& \mathrm{\neg }\mathrm{\neg }T\vee S& \text{UB(3)}\\ 5.& \mathrm{\neg }T\to S& \text{INP(4)}\\ 6.& \mathrm{\neg }T\to T& \text{SH(5,1)}\\ 7.& \mathrm{\neg }\mathrm{\neg }T\vee T& \text{INP(6)}\\ 8.& T\vee T& \text{UB(7)}\\ 9.& T& \text{TAUT(8)}\end{array}$

1.7.3 Baldintzazko frogaren erregela

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

1.34 Teorema. Baldintzazko frogaren erregela

$P_1,\dots ,P_n$ premisak eta $P\to C$ ondorioa dituen

$\begin{array}{cc}(1)& \begin{array}{c}{P}_1\\ ⋮\\ P_n\\ P\to C\end{array}\end{array}$

argumentua baliozkoa da baldin eta soilik baldin

$\begin{array}{cc}(2)& \begin{array}{c}{P}_1\\ ⋮\\ P_n\\ P\\ C\end{array}\end{array}$

argumentua baliozkoa bada.

Froga.

(1) argumentua baliozkoa da baldin eta soilik baldin $P\to C$ formula $P_1,\dots ,P_n$ formulen ondorio logiko bat bada, baliozko argumentuaren definizioaren arabera.

1.21 Teorema aplikatuz, $P\to C$ formula $P_1,\dots ,P_n$ formulen ondorio logiko bat da baldin eta soilik baldin $\models (P_1\wedge \cdots \wedge P_n\to (P\to C))$ bada.

Eta hori horrela da baldin eta soilik baldin $\models (P_1\wedge \cdots \wedge P_n\wedge P\to C)$ bada, $P_1\wedge \cdots \wedge P_n\to (P\to C)\equiv P_1\wedge \cdots \wedge P_n\wedge P\to C$ esportazioa delako.

Eta azken hori beteko da baldin eta soilik baldin $C$ formula $P_1,\dots ,P_n,P$ formulen ondorio logiko bat bada, 1.21 Teorema erabiliz. Hau da, baldin eta soilik baldin (2) argumentua baliozkoa bada, baliozko argumentuaren definizioaren arabera. $◻$ $◼$ $◻$

Erregela erabiltzeko bidea

$P_1,\dots ,P_n$ premisak dituen (1) argumentu bat izanik, $P\to 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,\dots ,P_n,P$ dituena. Behin $C$ deduzitu eta gero, $P$ hipotesia baztertuko dugu eta, baldintzazko frogaren erregela aplikatuz, $P\to C$ deduzituko dugu; hau da, $P\to C$ formula $P_1,\dots ,P_n$ formuletatik deduzituko dugu. Hori dena honela adieraziko dugu:

$\begin{array}{cccc}& 1.& P_1& \text{Premisa.}\\ & ⋮& ⋮& \\ & n.& P_n& \text{Premisa.}\\ & ⋮& ⋮& \\ \to & m.& P& \text{BFEren hipotesia / }\dot{\mathrm{..}}C\\ |& ⋮& ⋮& \\ |& k.& C& \\ --& --& --& \\ & k+1.& P\to C& \text{BFE(m-k)}\end{array}$

Idazkera horrekin adierazi nahi dugu $m+1$etik $k$ra bitartean formulak $P_1,\dots ,P_n,P$ premisak erabiliz deduzitu ditugula ((2) argumentua). $k+1$ formula, aldiz, $P_1,\dots ,P_n$ premisetatik deduzitu dugu ((1) argumentua), $P$ hipotesia baztertu dugu.

1.35 Adibideak. Hona hemen argumentu batzuen froga formalak inferentzia-erregelak, ordezkapen-erregela eta baldintzazko frogaren erregela erabiliz.

1. ${\displaystyle }$

   $\begin{array}{cccc}& 1.& A\to B& \text{premisa / }\dot{\mathrm{..}}A\to A\wedge B\\ \to & 2.& A& \text{BFEren hipotesia / }\dot{\mathrm{..}}A\wedge B\\ |& 3.& B& \text{MP(1,2)}\\ |& 4.& A\wedge B& \text{KK(2,3)}\\ --& --& --& \\ & 5.& A\to A\wedge B& \text{BFE(2-4)}\end{array}$

2. ${\displaystyle }$

   $\begin{array}{cccc}& 1.& T\to E& \text{premisa}\\ & 2.& A\to L& \text{premisa / }\dot{\mathrm{..}}T\vee A\to L\vee E\\ \to & 3.& T\vee A& \text{BFEren hipotesia / }\dot{\mathrm{..}}L\vee E\\ |& 4.& (T\to E)\wedge (A\to L)& \text{KK(1,2)}\\ |& 5.& E\vee L& \text{DE(4,3)}\\ |& 6.& L\vee E& \text{TRUK(5)}\\ --& --& --& \\ & 7.& T\vee A\to L\vee E& \text{BFE(3-6)}\end{array}$

3. ${\displaystyle }$

   $\begin{array}{ccccc}& & 1.& Q\to R& \text{premisa / }\dot{\mathrm{..}}(P\to Q)\to (P\to R)\\ \to & & 2.& P\to Q& \text{BFEren hipotesia / }\dot{\mathrm{..}}P\to R\\ |& \to & 3.& P& \text{BFEren hipotesia / }\dot{\mathrm{..}}R\\ |& |& 4.& Q& \text{MP(2,3)}\\ |& |& 5.& R& \text{MP(1,4)}\\ |& --& --& --& \\ |& & 6.& P\to R& \text{BFE(3-5)}\\ --& --& --& --& \\ & & 7.& (P\to Q)\to (P\to R)& \text{BFE(2-6)}\end{array}$

4. ${\displaystyle }$

   $\begin{array}{ccccc}& & 1.& (A\to C)\to D& \text{premisa}\\ & & 2.& B\to E& \text{premisa}\\ & & 3.& A\wedge B\to C& \text{premisa / }\dot{\mathrm{..}}B\to E\wedge D\\ \to & & 4.& B& \text{BFEren hipotesia / }\dot{\mathrm{..}}E\wedge D\\ |& & 5.& E& \text{MP(2,4)}\\ |& \to & 6.& A& \text{BFEren hipotesia / }\dot{\mathrm{..}}C\\ |& |& 7.& A\wedge B& \text{KK(6,4)}\\ |& |& 8.& C& \text{MP(3,7)}\\ |& --& --& --& \\ |& & 9.& A\to C& \text{BFE(6-8)}\\ |& & 10.& D& \text{MP(1,9)}\\ |& & 11.& E\wedge D& \text{KK(5,10)}\\ --& --& --& --& \\ & & 12.& B\to E\wedge D& \text{BFE(4-11)}\end{array}$

1.7.4 Absurdora eramateko erregela

Absurdora eramateko metodoa frogatu nahi dugunaren aurkako hipotesia egin eta kontraesan bat (formula inkontsistente bat) deduzitzean datza.

Idazkera. Formula inkontsistente bat $◻$ adieraziko dugu (adibidez, $A\wedge \mathrm{\neg }A$).

1.36 Teorema Absurdora eramateko erregela

$\begin{array}{cc}(1)& \begin{array}{c}{P}_1\\ ⋮\\ P_n\\ C\end{array}\end{array}$ argumentua baliozkoa da baldin eta soilik baldin $\begin{array}{cc}(2)& \begin{array}{c}{P}_1\\ ⋮\\ P_n\\ \mathrm{\neg }C\\ ◻\end{array}\end{array}$ argumentua baliozkoa bada.

Erregela frogatzeko lema hau erabiliko dugu:

1.37 Lema. Izan bedi $◻$ oef inkontsistente bat eta izan bedi $A$ edozein oef. Orduan,

$A$ inkontsistentea da baldin eta soilik baldin $\models (A\to ◻)$ bada.

1.37 Lemaren froga.

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

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

Baldin. Demagun $\models (A\to ◻)$ 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\to ◻)$ denez, $V((A\to ◻),I)=E$ izango da eta, $◻$ inkontsistentea denez, $V(◻,I)=F$ da. Hortaz, $V(A,I)=F$. $◻$ $◼$ $◻$

1.36 Teoremaren froga.

(1) argumentua baliozkoa da baldin eta soilik baldin $C$ formula $P_1,\dots ,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 \mathrm{\neg }C$ formula inkontsistentea bada (1.23 Teorema) eta, lemaren arabera, baldin eta soilik baldin $\models (P_1\wedge \cdots \wedge P_n\wedge \mathrm{\neg }C\to ◻)$ bada. Hori dena beteko da baldin eta soilik baldin $◻$ formula $P_1,\dots ,P_n,\mathrm{\neg }C$ formulen ondorio logikoa bada (1.21 Teorema). Hau da, baldin eta soilik baldin (2) argumentua baliozkoa bada, baliozko argumentuaren definizioaren arabera. $◻$ $◼$ $◻$

Erregela erabiltzeko bidea

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

$\begin{array}{cccc}& 1.& P_1& \text{Premisa}\\ & ⋮& ⋮& \\ & n.& P_n& \text{Premisa}\\ & ⋮& ⋮& \\ \to & m.& \mathrm{\neg }C& \text{AEEren hipotesia / }\dot{\mathrm{..}}◻\\ |& ⋮& ⋮& \\ |& k.& ◻& \\ --& --& --& \\ & k+1.& C& \text{AEE(m-k)}\end{array}$

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

1.38 Adibideak.

1. Ikus ditzagun argumentu beraren bi froga formal, bata AEE erabiliz eta bestea erabili gabe.

   $\begin{array}{cccc}& 1.& p& \text{premisa / }\dot{\mathrm{..}}q\vee (q\to r)\\ \to & 2.& \mathrm{\neg }(q\vee (q\to r))& \text{AEEren hipotesia / }\dot{\mathrm{..}}◻\\ |& 3.& \mathrm{\neg }q\wedge \mathrm{\neg }(q\to r)& \text{DeM(2)}\\ |& 4.& \mathrm{\neg }q\wedge \mathrm{\neg }(\mathrm{\neg }q\vee r)& \text{INP(3)}\\ |& 5.& \mathrm{\neg }q\wedge (\mathrm{\neg }\mathrm{\neg }q\wedge \mathrm{\neg }r)& \text{DeM(4)}\\ |& 6.& (\mathrm{\neg }q\wedge \mathrm{\neg }\mathrm{\neg }q)\wedge \mathrm{\neg }r& \text{ELKAR(5)}\\ |& 7.& \mathrm{\neg }q\wedge \mathrm{\neg }\mathrm{\neg }q& \text{KS(6)}\\ --& --& --& \\ & 8.& q\vee (q\to r)& \text{AEE(2-7)}\end{array}$

   Absurdora eramateko erregela erabili gabe:

   $\begin{array}{cccc}& 1.& p& \text{premisa / }\dot{\mathrm{..}}q\vee (q\to r)\\ \to & 2.& \mathrm{\neg }(q\vee (q\to r))& \text{BFEren hipotesia / }\dot{\mathrm{..}}q\vee (q\to r)\\ |& 3.& \mathrm{\neg }q\wedge \mathrm{\neg }(q\to r)& \text{DeM(2)}\\ |& 4.& \mathrm{\neg }q\wedge \mathrm{\neg }(\mathrm{\neg }q\vee r)& \text{INP(3)}\\ |& 5.& \mathrm{\neg }q\wedge (\mathrm{\neg }\mathrm{\neg }q\wedge \mathrm{\neg }r)& \text{DeM(4)}\\ |& 6.& (\mathrm{\neg }\mathrm{\neg }q\wedge \mathrm{\neg }r)\wedge \mathrm{\neg }q& \text{TRUK(5)}\\ |& 7.& \mathrm{\neg }\mathrm{\neg }q\wedge \mathrm{\neg }r& \text{KS(6)}\\ |& 8.& \mathrm{\neg }\mathrm{\neg }q& \text{KS(7)}\\ |& 9.& q& \text{UB(8)}\\ |& 10.& q\vee (q\to r)& \text{DB(9)}\\ --& --& --& \\ & 11.& \mathrm{\neg }(q\vee (q\to r))\to q\vee (q\to r)& \text{BFE(2-10)}\\ & 12.& \mathrm{\neg }\mathrm{\neg }(q\vee (q\to r))\vee (q\vee (q\to r))& \text{INP(11)}\\ & 13.& (q\vee (q\to r))\vee (q\vee (q\to r))& \text{UB(12)}\\ & 14.& q\vee (q\to r)& \text{TAUT(13)}\end{array}$

2. ${\displaystyle }$

   $\begin{array}{cccc}& 1.& p& \text{premisa / }\dot{\mathrm{..}}q\vee (r\to \mathrm{\neg }q)\\ \to & 2.& \mathrm{\neg }(q\vee (r\to \mathrm{\neg }q))& \text{AEEren hipotesia / }\dot{\mathrm{..}}◻\\ |& 3.& \mathrm{\neg }q\wedge \mathrm{\neg }(r\to \mathrm{\neg }q)& \text{DeM(2)}\\ |& 4.& \mathrm{\neg }q\wedge \mathrm{\neg }(\mathrm{\neg }r\vee \mathrm{\neg }q)& \text{INP(3)}\\ |& 5.& \mathrm{\neg }q\wedge (\mathrm{\neg }\mathrm{\neg }r\wedge \mathrm{\neg }\mathrm{\neg }q)& \text{DeM(4)}\\ |& 6.& \mathrm{\neg }q\wedge (\mathrm{\neg }\mathrm{\neg }q\wedge \mathrm{\neg }\mathrm{\neg }r)& \text{TRUK(5)}\\ |& 7.& (\mathrm{\neg }q\wedge \mathrm{\neg }\mathrm{\neg }q)\wedge \mathrm{\neg }\mathrm{\neg }r& \text{ELKAR(6)}\\ |& 8.& \mathrm{\neg }q\wedge \mathrm{\neg }\mathrm{\neg }q& \text{KS(7)}\\ --& --& --& \\ & 9.& q\vee (r\to \mathrm{\neg }q)& \text{AEE(2-8)}\end{array}$

3. Ikus ditzagun, berriro ere, argumentu beraren bi froga formal, bata AEE erabiliz eta bestea erabili gabe. $\begin{array}{cc}\begin{array}{cccc}& 1.& \mathrm{\neg }q\wedge s& \text{premisa}\\ & 2.& s\to \mathrm{\neg }r& \text{premisa}\\ & 3.& \mathrm{\neg }r\to \mathrm{\neg }p\vee q& \text{premisa / }\dot{\mathrm{..}}\mathrm{\neg }p\\ \to & 4.& \mathrm{\neg }\mathrm{\neg }p& \text{AEEren hipotesia / }\dot{\mathrm{..}}◻\\ |& 5.& \mathrm{\neg }q& \text{KS(1)}\\ |& 6.& \mathrm{\neg }\mathrm{\neg }p\wedge \mathrm{\neg }q& \text{KK(4,5)}\\ |& 7.& \mathrm{\neg }(\mathrm{\neg }p\vee q)& \text{DeM(6)}\\ |& 8.& \mathrm{\neg }\mathrm{\neg }r& \text{MT(3,7)}\\ |& 9.& \mathrm{\neg }s& \text{MT(2,8)}\\ |& 10.& s\wedge \mathrm{\neg }q& \text{TRUK(1)}\\ |& 11.& s& \text{KS(10)}\\ |& 12.& s\wedge \mathrm{\neg }s& \text{KK(11,9)}\\ --& --& --& \\ & 13.& \mathrm{\neg }p& \text{AEE(4-12)}\end{array}& \begin{array}{ccc}& & \\ & & \\ & & \\ 4.& s\wedge \mathrm{\neg }q& \text{TRUK(1)}\\ 5.& s& \text{KS(4)}\\ 6.& \mathrm{\neg }r& \text{MP(2,5)}\\ 7.& \mathrm{\neg }p\vee q& \text{MP(3,6)}\\ 8.& q\vee \mathrm{\neg }p& \text{TRUK(7)}\\ 9.& \mathrm{\neg }q& \text{KS(1)}\\ 10.& \mathrm{\neg }p& \text{SD(8,9)}\\ & & \\ & & \\ & & \end{array}\end{array}$