Logika proposizional-en iturria ikusi

{{erreferentzia falta}}
'''Logika proposizionala''', [[proposizio]]ak eta horiek lotzen dituzten [[Lokailu logiko|lokailuak]] osagaitzat hartzen dituen [[sistema formal]] bat da. Logika proposizionalean "hizkuntza" edo proposizio konplexuak, proposizioak beraien artean lokailuen bitartez lotuz osatzen da. [[Premisa]] izeneko proposizio multzo batetik [[logika]]z erator daitekeen ondoriozko proposiziora heltzea du helburu logika proposizionalak. Logika-sistema guztiak bezalaxe, logika proposizionalak ez du aztertzen proposizio bat errealitatean egiazkoa edo faltsua den, beste proposizioetatik deduzitzeko baliatu den prozesu logikoa edo argumentua zuzena den baizik. Logika proposizionala [[XIX. mendea]]ren amaieran asmatu zuen [[Charles Sanders Peirce]] filosofoak eta [[XX. mendea]]ren hasieran [[Ludwig Wittgenstein]] filosofoak osatu zuen, ''[[Tractatus logicus-philosophicus]]'' liburuan.

Zehatzago, logika proposizionalak proposizio atomiko edo bakunak egiazkoak edo faltsuak diren hartzen du kontuan, ondoren [[egia-taula]] izenekoen bitartez proposizio konplexuen egia-balioa aztertzeko: proposizio bakunen egia-balio guztietarako proposizio konplexua egia bada, proposizio konplexua [[tautologia]] dela esaten da; proposizio bakunen egia-balio guztietarako proposizio konplexua faltsua bada, kontraesana izango da eta proposizio konplexuaren egia-balioa batzuetan egia eta beste batzuetan faltsua bada, orduan argumentua sendoa da kasu batzuetan. Aldi berean, logika proposizionalak [[inferentzia]] edo argumentuak deduzitzeko erregelak ematen ditu, proposizio bakun edo konplexuen multzo batetik [[ondorio]]ak deduzituz: [[premisa]]k (proposizio atomikoak edo konposatuak) egiazkoak direnean, ondorioa egiazkoa bada, argumentua zuzena izango da.

[[Logika modal]]etik honetan bereizten da, logika proposizionala proposizio atomikoak egia eta gezurra izateko modu ezberdinak zehazten dituen arren, erabiltzen diren inferentzia aurauen arabera, logika modala egia modalitate ezberdinetik lan egiten du, egia absolutua, eta egia erlatiboa. Logika proposizionalak proposizio konplexuei egia eta faltsua balioez gainera, tarteko balioak ere esleitzen dizkio, inferentzia arauek proposizio atomikoen modu ezberdinak garatzen dituztenean. Adibidez, "Jon altua da" eta "altuek azterketa aprobatzen dute" proposizio atomikoek egiazkoak dira, baina subjektiboak, eta horrela proposizio konplexua eratzean logika proposizionalak, tarteko balioak izango ditu, "Jon altua da eta azterketa aprobatuko du" propiszioak probabilitate bat izan dezakeelako egia izateko.

== Sarrera ==

Argumentu hau aztertuko da:

# Gaur asteazkena da '''edo''' gaur osteguna da. ''(1. premisa)''
# Gaur '''ez''' da osteguna. ''(2. premisa)''
# '''Beraz''', gaur asteazkena da. ''(ondorioa)''

Argumentu hau baliozkoa da. Honek esan nahi du, ezinezkoa dela (1) eta (2) [[Premisa]]k egia izatea eta (3) ondorioa faltsua.

Kontuan hartu behar da, irakurlea hau irakurtzen ari den eguna igandea, astelehena edo asteartea den beste edozein egun izan daitekeela, eta beraz baliteke ondorioa errealitatearekin bat ez etortzea eta alde horretatik faltsua izatea, baina hala ere, premisak betetzen badira, ondorioa egiazkoa izango da zalantzarik gabe, argumentua zuzena baita. Argumentuaren baliozkotasuna ez dator «bihar asteazkena da» edo «bihar osteguna da» esaldien zentzutik, argumentuaren egituratik baizik. Premisa hauek beste batzuengatik alda ditzakegu, eta argumentua baliozkoa izaten jarraituko du. Adibidez:

# Gaur egun eguzkitsua da '''edo''' lainotua da.
# Gaur '''ez''' da egun lainotua.
# '''Beraz''', gaur egun eguzkitsua da.

Aurreko bi argumentuen baliozkotasuna, «edo» eta «ez» adierazpenetatik dator. Bi hauetako bat beste batez aldatuko bagenu, argumentua ez baliozkoa bihurtu ahalko litzateke. Adibidez, azter dezagun ondorengo argumentu ez baliozkoa:

# Gaur '''ez''' da egun eguzkitsua '''ezta''' lainotua ere.
# Gaur '''ez''' da egun lainotua.
# '''Beraz''', gaur egun eguzkitsua da.

«Edo» eta «ez» motako adierazpenei [[lokailu logiko]] deritzegu. «Egun eguzkitsua da» eta «bihar osteguna da» motako adierazpenei buruz garrantzia duen bakarra, egia-balioa izan dezaten da. Horregatik ordezka ditzakegu letrekin. Letra hauei [[aldagai proposizional]]ak deritze, eta normalean, latindar alfabetotik hartzen ditugu, ''p''-tik hasita (proposiziotik), eta ondoren ''q, r, s,'' eta abar. Honen arabera, lehenengo bi argumentuak era honetan formaliza ditzakegu:

# ''p'' '''edo''' ''q''
# '''Ez''' ''q''
# '''Beraz''', ''p''

Eta hirugarren argumentua, nahiz eta baliozkoa ez izan, era honetan idatz dezakegu:

# '''Ez''' ''p'' '''ez''' ''q''
# '''Ez''' ''q''
# '''Beraz''', ''p''

=== Lokailu logikoak ===

Jarraian dagoen taulan agertzen dira logika proposizionalaren barruan aurki ditzakegun [[lokailu logiko]] guztiak. Hauez gain, adibideak daude hizkuntza naturalean eta hizkuntza formalean adierazteko sinboloetan.

{| class="wikitable"
!Lotura
!Hizkuntza naturalean<br />adierazpena
!Adibidea
!Artikulu honetako<br />sinboloa
!Ordezko<br />sinboloak
|- align="center"
| align="left" | [[Ezeztapen logiko|Ezeztapena]]
|ez
| align="left" | '''Ez''' du euria ari.
|<math>\neg \,</math>
|<math>\sim \,</math>
|- align="center"
| align="left" | [[Konjuntzio logiko|Konjuntzioa]]
|eta
| align="left" | Euria ari du '''eta''' lainotuta dago.
|<math>\land</math>
|<math>\And \,</math> <math>.</math>
|- align="center"
| align="left" | [[Disjuntzio logiko|Disjuntzioa]]
|edo
| align="left" | Egun euritsua da '''edo''' eguzkitsua da.
|<math>\lor</math>
|
|- align="center"
| align="left" | Inplikazioa/Baldintzazkoa
|baldin... orduan...
| align="left" | '''Baldin''' eguzkia dago, '''orduan''' egunez da.
|<math>\to \,</math>
|<math>\supset</math>
|- align="center"
| align="left" | Baldintzabikoa
|baldin eta soilik baldin
| align="left" | Lainotuta dago '''baldin eta soilik baldin''' lainoak ikusten badira.
|<math>\leftrightarrow</math>
|<math>\equiv \,</math>
|- align="center"
| align="left" | Kontrako disjuntzioa
|ez... ezta...
| align="left" | '''Ez''' da egun eguzkitsua '''ezta''' lainotua ere.
|<math>\downarrow \,</math>
|
|- align="center"
| align="left" | Disjuntzio baztertzailea
|edo... edo...
| align="left" | '''Edo''' egun eguzkitsua da, '''edo''' lainotua da.
|<math>\nleftrightarrow</math>
|<math>\oplus, \not\equiv, W</math>
|}

Logika proposizionalean, lokailu proposizionalak egia funtzio bezala tratatzen ditugu. Hau da, egia-baloreak jasotzen, eta egia-baloreak itzultzen dituzten [[Funtzio (matematika)|funtzio]] bezala. Adibidez, «ez» lokailu logikoa, T (True) balioa hartzen duenean F (False) balioa itzultzen duen, eta F balioa hartzean T itzultzen duen funtzioa da. Horrela, «ez» funtzioa aplikatzen badiogu proposizio faltsua adierazten duen letra bati, ondorioa egiazko zerbait izango da. Gezurra bada «euria ari duela», orduan egia izango da «ez duela euria ari».

Lokailu logikoen esanahia, funtzioak jaso ditzakeen balio guztien aurrean itzultzen dituen balioak jasotzen dituen taula baten bidez adieraz daiteke.

{| width="90%"
!Ezeztapena
!Konjuntzioa
!Disjuntzioa
!Inplikazioa
!Baldintzabikoa
!Disjuntzio baztertzailea
|- valign="top" align="center"
|
<math>\begin{array}{c||c}
      \phi & \neg \phi \\
      \hline
      T & F \\
      F & T \\
   \end{array}</math>
|
<math>\begin{array}{c|c||c}
      \phi & \psi & \phi \land \psi \\
      \hline
      T & T & T \\
      T & F & F \\
      F & T & F \\
      F & F & F \\
   \end{array}</math>
|
<math>\begin{array}{c|c||c}
      \phi & \psi & \phi \lor \psi \\
      \hline
      T & T & T \\
      T & F & T \\
      F & T & T \\
      F & F & F \\
   \end{array}</math>
|
<math>\begin{array}{c|c||c}
      \phi & \psi & \phi \to \psi \\
      \hline
      T & T & T \\
      T & F & F \\
      F & T & T \\
      F & F & T \\
   \end{array}</math>
|
<math>\begin{array}{c|c||c}
      \phi & \psi & \phi \leftrightarrow \psi \\
      \hline
      T & T & T \\
      T & F & F \\
      F & T & F \\
      F & F & T \\
   \end{array}</math>
|
<math>\begin{array}{c|c||c}
      \phi & \psi & \phi \nleftrightarrow \psi \\
      \hline
      T & T & F \\
      T & F & T \\
      F & T & T \\
      F & F & F \\
   \end{array}</math>
|}

=== Logikaren oinarrizko baliokidetasun legeak ===

Logika klasikoaren legeen artean hauek dira aipagarrienak:

* Ukapen bikoitza
* Idenpotentzia legeak
* Trukatze legeak
* Elkartze legeak
* Banatze legeak
* De Morganen legeak

[[Hirugarrena baztertzearen printzipio]]a bezalako beste lege batzuk logika klasikoan onartzen dira, baina logika intuizionistan, adibidez, ez dago lege horren baliokiderik.

=== Logika proposizionalaren mugak ===

Logika proposizionalak argumentu askoren baliozkotasuna aztertzeko balio digu. Hala ere, badaude argumentu batzuk logikoki baliozkoak direnak, baina ezin direnak logika proposizionalaren bidez frogatu. Adibidez, azter dezagun honako adibide hau:

# Gizaki guztiak hilkorrak dira.
# Sokrates gizakia da.
# Ondorioz, Sokrates hilkorra da.

Argumentu honek ez duenez «ez», «eta», «edo» motako lokailurik, logika proposizionalaren arabera, honela formalizatuko genuke:

# ''p''
# ''q''
# Ondorioz, ''r''

Baina hau ez da baliozko argumentu bat. Mota honetako argumentuak frogatu ahal izateko, proposizio bakunen barne egitura aztertu behar dugu. Honetaz, lehen ordenako logika arduratzen da. Beste sistema formal batzuek ere ahalbidetzen dute hau, hala nola, bigarren ordenako logikak, logika modalak eta denborazko logikak.

== Logika proposizionalaren bi sistema formal ==

Jarraian, logika proposizionalerako bi sistema formal estandar aurkezten dira. Lehenengoa sistema axiomatiko sinple bat da, eta bigarrena berriz axiomarik gabea, dedukzio naturalekoa.

=== Sistema axiomatikoa ===

==== Alfabetoa ====

Sistema formal baten alfabetoa sistemaren lengoaiari dagozkion sinboloen multzoa da. Logika proposizionalaren sistema axiomatiko honi L izena esleituz, orduan Lren alfabetoa honetan datza:
* Aldagai proposizionalen kantitate finitu baina arbitrarioki handia. Orokorrean, alfabeto latindarretik hartzen ditu, p letrarekin hasiz, eta ondoren q,r, etab., eta beharrezkoa edo komenigarria denean azpiindizeak erabiliz. Aldagai proposizionalek [[proposizio]]ak adierazten dituzte, esaterako, "euria ari du" edo "beroaren eraginez metalak dilatatu egiten dira."

* Lokailu edo [[Eragile (matematika)|eragile]] proposizionalen multzo bat: <math>\neg, \land, \lor, \to, \leftrightarrow</math>.

* Bi puntuazio ikur: ezker eta eskuin [[parentesiak]]. Hauen funtzio bakarra zalantzazko adierazpenak argitzea da. 2+2÷2 adierazpenak, adibidez, (2 + 2) ÷ 2 edo 2 + (2 ÷ 2) esanahiak eduki ditzake.

==== Gramatika ====

Behin alfabetoa definituta, hurrengo urratsa sistemaren lengoaiari zein sinbolo konbinazio dagozkion zehaztea da, eta hau gramatika formalaren bidez lortzen da. Gramatika formalak arau batzuk ezartzen ditu, eta hauek lengoaiari dagozkion karaktere-kateak definitzen dituzte. Arau hauen bidez eraikitako karaktere-kateei ongi eratutako formulak deritze. L sistemaren arauak ondorengoak dira:
# L alfabetoko aldagai proposizionalak ongi eratutako formulak dira.
# <math>\phi \,</math> L sistemako ongi eratutako formula izanik, orduan <math>\neg \phi \,</math> ere hala izango da.
# <math>\phi \,</math> eta <math>\psi \,</math> Lko ongi eratutako sistemak badira, <math>(\phi \land \psi)</math>, <math>(\phi \lor \psi)</math>, <math>(\phi \to \psi) \,</math> eta <math>(\phi \leftrightarrow \psi)</math> ere izango dira.
# 1etik 3ra bitarteko baieztapenen eta pausu kopuru finitu baten bidez sortutako adierazpenak soilik izango dira Lren ongi eratutako formulak.

Arau hauen arabera, jarraian datozen karaktere-kateak ongi eratutako formulen adibideak dira:

:<math>p \,</math>
:<math>\neg \neg \neg q \,</math>
:<math>(p \land q)</math>
:<math>\neg (p \land q)</math>
:<math>(p \leftrightarrow \neg p)</math>
:<math>((p \to q) \land p)</math>
:<math>(\neg (p \land (q \lor r)) \lor s)</math>

 
Hauek, berriz, gaizki eratuako formulen adibideak dira:

:{| width="600px"
! align="left" |Formula
! align="left" |Akatsa
! align="left" |Zuzenketa
|-
|<math>(p) \,</math>
|Parentesiak soberan
|<math>p \,</math>
|-
|<math>\neg (p) \,</math>
|Parentesiak soberan
|<math>\neg p \,</math>
|-
|<math>(\neg p) \,</math>
|Parentesiak soberan
|<math>\neg p \,</math>
|-
|<math>p \to q \,</math>
|Parentesiak faltan
|<math>(p \to q) \,</math>
|-
|<math>(p \land q \to r)</math>
|Parentesiak faltan
|<math>((p \land q) \to r) \,</math>
|}

Bestalde, parentesien funtzio bakarra zalantzagarriak gerta daitezkeen formulak argitzea izanik, oro har beharrezkoak diren parentesiak soilik erabiltzen dira. Beraz, hurrengo adierazpenak ongi eratutako formulen adibide gisa har daitezke:

:<math>p \land q</math>
:<math>\neg p \to q \,</math>
:<math>(p \land q) \lor \neg q</math>
:<math>(p \leftrightarrow q) \leftrightarrow (q \leftrightarrow p)</math>

Parentesien erabilerari dagokion beste arau batzuk ere badaude. Konjuntzio eta disjuntzioek lehentasun txikiagoa dute inplikazioa eta baldintzabikoa baino. Beraz, parentesi gabeko formula bat emanik, konjuntzioak eta disjuntzioak inplikazio eta baldintzabikoen aurretik elkartu behar dira. Adibidez:

:{| width="600px"
! align="left" |Formula
! align="left" |Irakurketa zuzena
! align="left" |Irakurketa okerra
|-
|<math>p \land q \to r \,</math>
|<math>(p \land q) \to r \,</math>
|<math>p \land (q \to r) \,</math>
|-
|<math>\neg p \leftrightarrow q \lor r \,</math>
|<math>\neg p \leftrightarrow (q \lor r) \,</math>
|<math>(\neg p \leftrightarrow q) \lor r \,</math>
|-
|<math>p \land q \leftrightarrow r \lor s \,</math>
|<math>(p \land q) \leftrightarrow (r \lor s) \,</math>
|<math>(p \land (q \leftrightarrow r)) \lor s \,</math>
|}

Arau hauek [[oinarrizko aljebra]]n daudenen berdintsuak dira, non biderketa eta zatiketa, batuketa eta kenketa baino lehen ebatzi behar diren. Esaterako, 2 + 2 x 2 ekuazioa (2 + 2) x 2 edota 2 + (2 x 2) gisa uler daiteke. Aurrenekoaren emaitza 8 da, eta bigarrenarena, berriz, 6. Baina biderketa batuketa baino lehen ebatzi behar denez emaitza zuzena 6 izango da, eta ez 8.

==== Axiomak ====

Sistema formal bateko axiomak ongi eratutako formulen multzoak dira,
hurrengo frogapenetan abiapuntutzat hartzen direnak. Axioma multzo estandar bat [[Jan Łukasiewicz]]ek aurkitutakoa da.

* <math>(\phi \to (\psi \to \phi)) \,</math>
* <math>((\phi \to (\psi \to \chi)) \to ((\phi \to \psi) \to (\phi \to \chi))) \,</math>
* <math>((\neg \phi \to \neg \psi) \to (\psi \to \phi)) \,</math>

==== Inferentzia erregelak ====

Inferentzia erregela bat formula multzoetatik formuletara doan [[funtzio]] bat da. Funtzioak argumentu bezala hartzen duen formula multzo horri premisa deritzo, eta ondorioztatzen den formulari, berriz, konklusio. Orokorrean, helburua inferentzia erregelek premisen egiazkotasuna konklusiora helaraztea da. Hau da, ezinezkoa izatea premisak egiazkoak izanik konklusioa faltsua izatea. Lren kasuan, inferentzia erregela bakarra modus ponens da:

:<math>(\phi \to \psi), \phi \vdash \psi</math>

Kontuan izan behar da <math>\phi \,</math> eta <math>\psi \,</math> ez direla formulak, aldagaiak baizik, eta hauek ongi eratutako edozein formulaz ordezka daitezke.

=== Dedukzio naturala ===

Logika proposizionaleko sistemak [[axioma|axiomen]] [[multzo]] hutsak abiapuntutzat hartuta ere sor daitezke. Horretarako, inferentzia erregela batzuk zehazten dira eta hauek, lotura logikoak naturalki aztertzeko dugun modua atzematen saiatzen dira.

;Baieztapena ukatzea: <math>\neg p \to \neg q \lor p</math>
; Ukapena sartzea: <math>(p \to q)</math> <math>(p \to \neg q)</math>-tik, <math>\neg p</math> ondorioztatzen da.
: Hau da, <math>\{ (p \to q), (p \to \neg q) \} \vdash \neg p</math>.
;Ukapena ezabatzea: <math>\neg p</math>-tik, <math>(p \to r)</math> ondorioztatzen da.
: Hau da, <math>\{ \neg p \} \vdash (p \to r)</math>.
;Ukapen bikoitza ezabatzea: <math>\neg \neg p</math>-tik, <math>p</math> ondorioztatzen da.
: Hau da, <math>\neg \neg p \vdash p</math>.
;Konjuntzioa sartzea: <math>p</math> eta <math>q</math>-tik, <math>(p \land q)</math> ondorioztatzen da.
: Hau da, <math>\{ p, q \} \vdash (p \land q)</math>.
;Konjuntzioa sinplifikatzea/ezabatzea: <math>(p \land q)</math>-tik, <math>p</math> ondorioztatzen da.
: <math>(p \land q)</math>-tik, <math>q</math> ondorioztatzen da.
: Hau da, <math>(p \land q) \vdash p</math> eta <math>(p \land q) \vdash q</math>.
;Disjuntzioa sartzea: <math>p</math>-tik, <math>(p \lor q)</math> ondorioztatzen da.
: Hau da, <math>p \vdash (p \lor q)</math> eta <math>q \vdash (p \lor q)</math>.
;Disjuntzioa ezabatzea: <math>(p \lor q)</math> eta <math>(p \to r)</math> eta <math>(q \to r)</math>-tik, <math>r</math> ondorioztatzen da.
: Hau da, <math>\{p \lor q, p \to r, q \to r\} \vdash r</math>.
;Baldintzabikoa sartzea: <math>(p \to q)</math> eta <math>(q \to p)</math>-tik, <math>(p \leftrightarrow q)</math> ondorioztatzen da.
: Hau da, <math>\{p \to q, q \to p\} \vdash (p \leftrightarrow q)</math>.
;Baldintzabikoa ezabatzea: <math>(p \leftrightarrow q)</math>-tik, <math>(p \to q)</math> ondorioztatzen da.
: <math>(p \leftrightarrow q)</math>-tik, <math>(q \to p)</math> ondorioztatzen da.
: Hau da, <math>(p \leftrightarrow q) \vdash (p \to q)</math> eta <math>(p \leftrightarrow q) \vdash (q \to p)</math>.
;Modus ponens (Inplikazioa ezabatzea): <math>p</math> eta <math>(p \to q)</math>-tik, <math>q</math> ondorioztatzen da.
: Hau da, <math>\{ p, p \to q\} \vdash q</math>.
;Inplikazio proba (Inplikazioa sartzea): [<math>p</math>-k <math>q</math>-ren proba onartzen duela onartuz]-tik, <math>(p \to q)</math> ondorioztatzen da.
: Hau da, <math>(p \vdash q) \vdash (p \to q)</math>.

== Oinarrizko argumentu eta deribatuen formulak ==

{| class="wikitable"
! Izena
! Atzekaria
! Deskribapena
|-
| [[Modus ponendo ponens|Modus ponens]]
| <math>((p \to q) \land p) \vdash q</math>
| Baldin <math>p</math> orduan <math>q</math>; <math>p</math>; ondorioz <math>q</math>
|-
| [[Modus tollendo tollens|Modus tollens]]
| <math>((p \to q) \land \neg q) \vdash \neg p</math>
| Baldin <math>p</math> orduan <math>q</math>; ez <math>q</math>; ondorioz ez <math>p</math>
|-
| [[Silogismo hipotetikoa]]
| <math>((p \to q) \land (q \to r)) \vdash (p \to r)</math>
| Baldin <math>p</math> orduan <math>q</math>; baldin <math>q</math> orduan <math>r</math>; ondorioz, baldin <math>p</math> orduan <math>r</math>
|-
| [[Silogismo disjuntiboa]]
| <math>((p \lor q) \land \neg p) \vdash q</math>
| Edozein <math>p</math> edo <math>q</math>, edo biak; ez <math>p</math>; orduan, <math>q</math>
|-
| [[Dilema eraikitzailea]]
| <math>((p \to q) \land (r \to s) \land (p \lor r)) \vdash (q \lor s)</math>
| Baldin <math>p</math> orduan <math>q</math>; eta baldin<math>r</math> orduan <math>s</math>; baina <math>p</math> edo <math>r</math>; ondorioz <math>q</math> edo<math>s</math>
|-
| [[Dilema suntsitzailea]]
| <math>((p \to q) \land (r \to s) \land(\neg q \lor \neg s)) \vdash (\neg p \lor \neg r)</math>
|Baldin <math>p</math> orduan <math>q</math>; eta baldin <math>r</math> orduan <math>s</math>; baina ez <math>q</math> edo ez <math>s</math>; ondorioz ez <math>p</math> edo ez <math>r</math>
|-
| Bi noranzkoko dilema
| <math>((p \to q) \land (r \to s) \land(p \lor \neg s)) \vdash (q \lor \neg r)</math>
| Baldin <math>p</math> orduan <math>q</math>; eta balidn <math>r</math> orduan <math>s</math>; baina <math>p</math> edo ez <math>s</math>; ondorioz <math>q</math> edo ez <math>r</math>
|-
| Sinplifikazioa
| <math>(p \land q) \vdash p</math>
| <math>p</math> eta <math>q</math> egiazkoak badira; ondorioz <math>p</math> egiazkoa da
|-
| Konjuntzioa
| <math>p, q \vdash (p \land q)</math>
| <math>p</math> eta <math>q</math> bakoitza bere aldetik egiazkoak badira; orduan elkarrekin egiazkoak dira
|-
| Batuketa
| <math>p \vdash (p \lor q)</math>
| <math>p</math> egiazkoa da; ondorioz disjuntzioa (<math>p</math> edo <math>q</math>) egiazkoa da
|-
| Osaketa
| <math>((p \to q) \land (p \to r)) \vdash (p \to (q \land r))</math>
| Baldin <math>p</math> orduan <math>q</math>; eta baldin <math>p</math> orduan <math>r</math>; ondorioz baldin <math>p</math> egiazkoa bada <math>q</math> eta <math>r</math> egiazkoak dira
|-
| [[De Morgan-en legea]] (1)
| <math>\neg (p \land q) \vdash (\neg p \lor \neg q)</math>
| (<math>p</math> eta <math>q</math>)-ren ezeztatzearen baliokidea da (ez <math>p</math> edo ez <math>q</math>)
|-
| De Morgan-en legea (2)
| <math>\neg (p \lor q) \vdash (\neg p \land \neg q)</math>
| (<math>p</math> edo <math>q</math>)-ren ezeztapenaren baliokidea da (ez <math>p</math> eta ez <math>q</math>)
|-
| Trukatze legea (1)
| <math>(p \lor q) \vdash (q \lor p)</math>
| (<math>p</math> edo <math>q</math>) , (<math>q</math> edo <math>p</math>)-ren baliokidea da
|-
| Trukatze legea (2)
| <math>(p \land q) \vdash (q \land p)</math>
| (<math>p</math> eta <math>q</math>) , (<math>q</math> eta <math>p</math>)-ren baliokidea da
|-
| Trukatze legea (3)
| <math>(p \leftrightarrow q) \vdash (q \leftrightarrow p)</math>
| (<math>p</math> , <math>q</math>-ren baliokidea da) , (<math>q</math>,  <math>p</math>-ren baliokidea da)-ren baliokidea da
|-
| Elkartze legea (1)
| <math>(p \lor (q \lor r)) \vdash ((p \lor q) \lor r)</math>
| <math>p</math> edo (<math>q</math> edo <math>r</math>),  (<math>p</math> edo <math>q</math>) edo <math>r</math>-ren baliokidea da
|-
| Elkartze legea (2)
| <math>(p \land (q \land r)) \vdash ((p \land q) \land r)</math>
| <math>p</math> eta (<math>q</math> eta <math>r</math>) , (<math>p</math> eta <math>q</math>) eta <math>r</math>-ren baliokidea da
|-
| Banaketa legea(1)
| <math>(p \land (q \lor r)) \vdash ((p \land q) \lor (p \land r))</math>
| <math>p</math> eta (<math>q</math> edo <math>r</math>) , (<math>p</math> eta <math>q</math>) edo (<math>p</math> eta <math>r</math>)-ren baliokidea da
|-
| Banaketa legea (2)
| <math>(p \lor (q \land r)) \vdash ((p \lor q) \land (p \lor r))</math>
| <math>p</math> edo (<math>q</math> eta <math>r</math>) , (<math>p</math> edo <math>q</math>) eta (<math>p</math> edo <math>r</math>)-ren baliokidea da
|-
| [[Ezeztapen bikoitza]]
| <math>p \vdash \neg \neg p</math>
| <math>p</math> , ez <math>p</math>-ren ezeztapenaren baliokidea da
|-
| [[Iraulketa]]
| <math>(p \to q) \vdash (\neg q \to \neg p)</math>
| Baldin <math>p</math> orduan <math>q</math>-ren baliokidea da, baldin ez <math>q</math> orduan ez <math>p</math>
|-
| [[Inplikazio materiala]]
| <math>(p \to q) \vdash (\neg p \lor q)</math>
| Baldin <math>p</math> orduan <math>q</math>-ren baliokidea da ez <math>p</math> edo <math>q</math>
|-
| [[Baliokidetza materiala]] (1)
| <math>(p \leftrightarrow q) \vdash ((p \to q) \land (q \to p))</math>
| (<math>p</math> baldin eta soilik baldin <math>q</math>)-ren baliokidea da (baldin <math>p</math> egiazkoa bada orduan <math>q</math> egiazkoa da) eta (<math>q</math> egiazkoa bada orduan <math>p</math> egiazkoa da)
|-
| Baliokidetza materiala (2)
| <math>(p \leftrightarrow q) \vdash ((p \land q) \lor (\neg p \land \neg q))</math>
| (<math>p</math> baliokidea <math>q</math>)-ren baliokidea da bietako bat betetzen bada: (<math>p</math> eta <math>q</math> egiazkoak dira) edo (<math>p</math> eta  <math>q</math> faltsuak dira)
|-
| Baliokidetza materiala (3)
| <math>(p \leftrightarrow q) \vdash ((p \lor \neg q) \land (\neg p \lor q))</math>
| (<math>p</math> baliokide <math>q</math>)-ren baliokidea da: bai (<math>p</math> edo ez <math>q</math> egiazkoak dira) eta (ez <math>p</math> edo <math>q</math> egiazkoak dira)
|-
| Esportazioa
| <math>((p \land q) \to r) \vdash (p \to (q \to r))</math>
| hemendik (baldin <math>p</math> eta <math>q</math> egiazkoak badira, orduan <math>r</math> egiazkoa da) hau egiazta dezakegu (<math>q</math> egiazkoa bada orduan <math>r</math> egiazkoa dela, <math>p</math> egiazkoa bada)
|-
| Inportazioa
| <math>(p \to (q \to r)) \vdash ((p \land q) \to r)</math>
| <math>p</math>-k inplikatzen du <math>q</math>-k inplikatzen du <math>r</math>-ren baliokidea da <math>p</math> eta <math>q</math>-k inplikatzen du <math>r</math>
|-
| [[Tautologia]] (1)
| <math>p \vdash (p \lor p)</math>
| <math>p</math> egiazkoa da eta honen baliokidea da <math>p</math> egiazkoa da edo <math>p</math> egiazkoa da
|-
| Tautologia (2)
| <math>p \vdash (p \land p)</math>
| <math>p</math> egiazkoa da eta honen baliokidea da <math>p</math> egiazkoa da eta  <math>p</math> egiazkoa da
|-
| [[Hirugarrena baztertzearen printzipio]]a
| <math>\vdash (p \lor \neg p)</math>
| <math>p</math> edo ez <math>p</math> egiazkoa da
|-
| [[Ez kontraesanaren printzipioa]]
| <math>\vdash \neg (p \land \neg p)</math>
| <math>p</math> eta ez <math>p</math> faltsua da
|}

==== Frogapen adibidea ====
Frogatu: <math>A \to A \,</math>

Froga posible bat hau da (baliozkoa da baina beharrezkoak ez diren urrats batzuk ematen dira) eta honela egin daiteke:
<center>
{| class="wikitable" style="background:white"
! align="left" | Urrats
! Formula
! Arrazoia
|-
| 1 || <math>A</math> || Premisa.
|-
| 2 || <math>A \lor A</math> ||  (1) urratsetik disjuntzioa sartu.
|-
| 3 || <math>(A \lor A) \land A</math> ||  (1) eta (2) urratsetatik konjuntzioa sartu.
|-
| 4 || <math>A </math> || (3). urratsetik konjuntzioa ezabatu.
|-
| 5 || <math>A \vdash A</math> || (1)etik  (4)rako urratsen laburpena.
|-
| 6 || <math>\vdash A \to A</math> || (5). urratsetik baldintzazkoa sartuz. [[Quod erat demonstrandum|QED]]
|}
</center>

Interpretatu <math>A \vdash A</math> honela: "Jakinik <math>A</math>k <math>A</math> inferitzen duela". Irakurri <math>\vdash</math> <math>A \to A</math> honela "Ezer suposatu gabe, inferituz <math>A</math>k inplikatzen duela <math>A</math>", edo " Tautologia bat dela <math>A</math>k inplikatzen duela <math>A</math>", edo "Beti egia dela <math>A</math>k inplikatzen duela <math>A</math>".

== Lengoaia formala BNF notazioan ==

Logika proposizionalaren lengoaia formala gramatika formala erabiliz adieraz dezakegu BNF idazkerarekin deskribatuz.

:<math>
\begin{array}{rcl}
\rm\langle Baldintzabikoa \rangle & ::= & \rm\langle Baldintzatua \rangle \leftrightarrow \langle Baldintzabikoa \rangle \mid \langle Baldintzatua \rangle
\\
\rm\langle Baldintzatua \rangle & ::= & \rm\langle Konjuntzioa \rangle \rightarrow \langle Baldintzatua \rangle \mid \langle Konjuntzioa \rangle
\\
\rm\langle Konjuntzioa \rangle & ::= & \rm\langle Disjuntzioa \rangle \vee \langle Konjuntzioa \rangle \mid\langle Disjuntzioa \rangle
\\
\rm\langle Disjuntzioa \rangle & ::= & \rm\langle Literala \rangle \wedge \langle Disjuntzioa \rangle \mid \langle Literala \rangle
\\
\rm\langle Literala \rangle & ::= & \rm\langle Atomoa \rangle \mid \neg \langle Atomoa \rangle
\\
\rm\langle Atomoa \rangle & ::= & \rm\top \mid \bot \mid \langle Letra \rangle \mid \langle Agrupazioa \rangle
\\
\rm\langle Agrupazioa \rangle & ::= & \rm( \langle Baldintzabikoa \rangle ) \mid [ \langle Baldintzabikoa \rangle ] \mid \{ \langle Baldintzabikoa \rangle \}
\end{array}
</math>

Aurreko gramatikako operazioak lehentasun hauek dituzte:
# Ezeztapena (<math>\neg \,</math>)
# Konjuntzioa (<math>\land \,</math>)
# Disjuntzioa (<math>\lor \,</math>)
# Baldintza materiala (<math>\to \,</math>)
# Baldintzabikoa (<math>\leftrightarrow</math>)
#
== Semantika ==

Logika proposizionaleko sistemaren interpretazio bat aldagai bakoitzaren egia-balioa ezartzean datza, operazio logikoak jarriz bakoitza bere lekuan. Aldagai proposizional bakoitzari bi balore esleitzen zaizkio: T(egiazkoa) edo F(faltsua). Honek esan nahi du ''n'' aldagai baldin badaude, 2<sup>''n''</sup> interpretazio daudela.

Hemendik abiatuz nozio semantikoak definitzeko aukera dugu. L lengoaiaren edozein A eta B formulak badira, <math>\Gamma</math> L formulen multzoa izango litzateke eta M Lren interpretazio bat, orduan:
* A egiazkoa da Mren interpretaziorako baldin eta soilik baldin Mk T egia-balioa ezartzen badio Ari.
* A faltsua da Mren interpretaziorako baldin eta soilik baldin Mk F egia-balioa ezartzen badio Ari.
* A tautologia bat da baldin eta soilik baldin M interpretazio guztirako, Mk T egia-balioa ezartzen badio Ari.
* A kontraesan bat da baldin eta soilik baldin M interpretazio guztirako, Mk F egia-balioa ezartzen badio Ari.
* A satisfaktiblea da baldin eta soilik baldin Mren interpretazio batean Ak T egia-balioa baldin badu.
* <math>\Gamma</math> kontsistentea da baldin eta soilik baldin existitzen bada interpretazio bat non <math>\Gamma</math>ko formula guztiak egiazkoak diren.
* A <math>\Gamma</math> formulen multzoaren ondorio semantikoa da baldin eta soilik baldin ez bada existitzen interpretazio bat <math>\Gamma</math>ko formula guztiak egiazkoak eta A faltsua izanik. A ondorio semantikoa izatean honela idazten da: <math>\Gamma \models_L A</math>.
* A egia logikoa da baldin eta soilik baldin A konjuntzio huts baten ondorio semantikoa bada eta honela idazten da: <math>\models_L A</math>.

=== Egia-taulak ===

Egia-taula, formula baten interpretazio posible guztiak aztertzen dituen taula bat da, formulan agertzen diren aldagai proposizional guztiak erabiliz. Adibidez, hau da formula honen egia-taula <math>\neg (p \lor q) \to (p \to r)</math>:

:<math>
\begin{array}{c|c|c||c|c|c|c}
p & q & r & (p \lor q) & \neg (p \lor q) & (p \to r) & \neg (p \lor q) \to (p \to r) \\
\hline
T & T & T & T & F & T & T \\
T & T & F & T & F & F & T \\
T & F & T & T & F & T & T \\
T & F & F & T & F & F & T \\
F & T & T & T & F & T & T \\
F & T & F & T & F & T & T \\
F & F & T & F & T & T & T \\
F & F & F & F & T & T & T \\
\end{array}
</math>

Ikusten den bezala, formula honek 2<sup>''n''</sup> interpretazio posible ditu non ''n'' aldagai proposizional kopurua den, kasu honetan hiru aldagai daude, hau da, p, q eta r eta tautologia da, hau da, interpretazio guztietarako egia da formula.

== Forma normalak ==

Askotan, beharrezkoa da formula bat eraldatzea, batez ere, formula bat bere forma normalera eraldatzea. Hau lortzeko, formula bere baliokide batean eraldatzen da, eta prozesu hau errepikatzen da, oinarrizko lokailuak (<math>\land, \lor, \neg</math>) bakarrik dituen adierazpena lortu arte. Hau lortzeko erabiltzen dira baliokidetasun logikoak:
:<math>(p \to q) \leftrightarrow (\neg p \lor q)</math>
:<math>(p \leftrightarrow q) \leftrightarrow [(\neg p \lor q) \land (\neg q \lor p)]</math>

Adibidez, ikus dezagun honako formula:
:<math>(p \to q) \land (\neg q \leftrightarrow p)</math>

Formula hau era honetan gara dezakegu:
:<math>(\neg p \lor q) \land (q \lor p) \land (\neg p \lor \neg q)</math>

Formula bat ''forma normal disjuntiboan'' (FND) dagoela esaten da baldin eta soilik baldin honako itxura badu:
:<math>A_1 \lor A_2 \lor ... \lor A_n</math>

non A bakoitza formulen konjuntzioa den. Adibidez, honako formula forma normal disjuntiboan dago:
:<math>p \land (q \lor s) \land (\neg q \lor p)</math>

Formula bat ''forma normal konjuntiboan'' (FNK) dagoela esaten da baldin eta soilik baldin honako itxura badu:
:<math>A_1 \land A_2 \land ... \land A_n</math>

non A bakoitza formulen disjuntzioa den. Adibidez, honako formula forma normal konjuntiboan dago:
:<math>p \land (q \lor s) \land (\neg q \lor p)</math>

De Morgan-en legeen arabera, posible da forma normal disjuntibotik forma normal konjuntibora pasatzea, eta alderantziz:
:<math>\neg (A \lor B) \leftrightarrow (\neg A \land \neg B)</math>
:<math>\neg (A \land B) \leftrightarrow (\neg A \lor \neg B)</math>

FNK eta FND elkar dualak dira. Frogapena, De Morgan-en legeen bidez, eta konjuntzioaren eta disjuntzioaren [[banakortasun]] legeen bidez egiten da. Honako adierazpena bete behar da:
:<math>\neg [(A_1 \land B_1) \lor (A_2 \land B_2) \lor ... \lor (A_n \land B_n)] \leftrightarrow [(\neg A_1 \lor \neg B_1) \land (\neg A_2 \lor \neg B_2) \land ... \land (\neg A_n \lor \neg B_n)]</math>

Eta alderantziz:
:<math>\neg [(A_1 \lor B_1) \land (A_2 \lor B_2) \land ... \land (A_n \lor B_n)] \leftrightarrow [(\neg A_1 \land \neg B_1) \lor (\neg A_2 \land \neg B_2) \lor ... \lor (\neg A_n \land \neg B_n)]</math>

== Logika proposizionala eta konputazioa ==

Konputagailuek informazio bitarrarekin lan egiten dutenez, [[Booleren aljebra]] oso egokia da konputagailuen funtzionamendua aztertzeko eta diseinatzeko. Booleren aljebra hasiera batean logikaren ikerketarako sortu zen eta 1938. urtetik aurrera izan zen konputagailu digitaletan dituen aplikazioak areagotzen hasi zirela. Gaur egun, tresna hau oso beharrezkoa da konputagailuen garapenerako, zirkuitu logikoen analisia eta sintesia azkar egitea baimentzen baitigu.

== Ikus, gainera ==
* [[Booleren aljebra]]
* [[Grafo teoria]]
* [[Silogismo]]

== Bibliografia ==
{{Erreferentzia |abizena1=Grassman |izena1=W. K. |abizena2=Tremblay |izena2=J-P. |izenburua=Logic and Discrete Mathematics: A Computer Science Perspective / Matemática Discreta y Lógica}}

{{Erreferentzia |abizena=Grimaldi |izena=R. P. |izenburua=Discrete and Combinatorial Mathematics: An Applied Introduction / Matemáticas discretas y combinatorias}}

{{Erreferentzia |abizena1=Ross |izena1=K. A. |abizena2=Wright |izena2=C. R. B. |izenburua=Discrete Mathematics}}

[[Kategoria:Proposizio logika]]