Booleren aljebra

Booleren aljebra Elektronika Digital, Informatika, eta Matematika alorretan eragiketa logikoak adierazteko erabiltzen den egitura aljebraiko bat da.

Matematikan eta logika matematikoan, aljebra boolearra aljebraren adar bat da. Oinarrizko aljebrarekin bi modutan desberdintzen da. Lehenik eta behin, aldagaien balioak egiazko eta gezurrezko balioak dira, normalean 1 eta 0 bezala adierazita; oinarrizko aljebran, aldiz, aldagaien balioak zenbakiak dira. Bigarrenik, aljebra boolearrak operadore logikoak erabiltzen ditu, hala nola (y) konjuntzioa ∧ gisa adierazten dena, ∨ gisa adierazten den (o) disjuntzioa eta ¬ gisa adieraziten den (ez) ezeztapena. Oinarrizko aljebrak, berriz, batuketa, biderketa, kenketa eta zatiketa bezalako eragile aritmetikoak erabiltzen ditu. Aljebra boolearra, beraz, eragiketa logikoak deskribatzeko modu formal bat da, oinarrizko aljebrak zenbakizko eragiketak deskribatzen dituen bezala.

Aljebra boolearra George Boole-k sartu zuen The Mathematical Analysis of Logic (1847) bere lehen liburuan, eta An Investigation of the Laws of Thought (1854) liburuan azaldu zuen zehatzago. Huntingtonen arabera, Boolear aljebra terminoa Henry M. Sheffer-ek iradoki zuen lehen aldiz 1913an, nahiz eta Charles Sanders Peirce-k «Algebra boolearra konstante batekin» izenburua eman zion bere The Simpleest Mathematicsen lehen kapituluari 1880an. Aljebra boolearra oinarrizkoa izan da elektronika digitalaren garapenean, eta programazio-lengoaia moderno guztietan agertzen da. Multzoen teorian eta estatistikan ere erabiltzen da.

Historia

George Boole (1815eko azaroaren 2a - 1864ko abenduaren 8a) matematikari ingelesa izan zen egitura aljebraiko hau sistema logiko gisa definitu zuen lehenengoa. Lehen aldiz The Mathematical Analysis of Logic izeneko liburuxka batean argitaratu zuen 1847an eta ondoren liburu garrantzitsuago batean: An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities (1854).

Aljebra boolearra, aljebraren adar bat da, matematiketatik ezagutzen dugun logika proposizionalaren bidez zirkuituak sinplifikatzeko inplementatzen dena. Boolen aljebrari esker zirkuituak irudikatu eta hauen funtzionamendua irudikatu dezakegu bool aljebraren legeen bidez. George Boolek ez zuen programatzeko asmorik, urte haietan teknologia ez baitzegoen hain aurreratua. Berak giza pentsamendua aztertu nahi izan zuen, eta lehen aipatu dugun bezala, logika proposizionala lotu eta horrekin kalkuluak egin eta hark ikertutakoa An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities liburuan argitaratu zuen. George Boole gehiago kezkatzen zen edukien itxuragatik edukiagatik baino, eta, beraz, gehiago interesatzen zitzaion kalkuluak nola egiten zituen kalkulatzen zuena baino. Aurrerago garatutako guztia, D 'Morgan edo Bertrand Russell bezalako zientzialarien lege gehiagoz babestu zuten. Hain zuzen ere De Morganen legeak ezezko proposizioen funtzionamenduak nolakoak ziren azalduko zituena. Logika-mota hau filosofian ere oso presente dago, baina ez zitzaion konputazioari aplikatu 1930era arte.

1930ean, Claude Shannon zientzialari eta informatikariak kommutazio-zirkuituak aztertzen ari zela, zirkuituak ebazteko Boolen kommutazio aljebraikoa inplementatu zezakeela konturatu zen. Shannonek jada eskura zuen gailu matematiko abstraktua “A Investigation of the Laws of Thought” , eta, beraz, bere kommutazio-aljebra formulatu zuen, bi elementuren aljebra boolearra bezala, zeinak 1 eta 0 izango liratekeen. Zirkuituen ingeniaritzako hanbituan, ez dago beste aljebra boolear batzuk kontuan hartzeko beharrik, eta, beraz, "kommutazio-aljebra" eta "aljebra boolearra" askotan modu berean erabiltzen dira. Horrek bizitzan eragin handia izango zuen, batez ere ordenagailuen sorkuntzan.

Definizio formala

Booleren aljebra gutxienez $\perp$ eta $\top$ (edo 0 eta 1) elementuak dituen $E$ multzo bat da, zeinaren barnean bi barne-lege ($\vee$ eta $\wedge$) definitzen diren, propietate hauek betetzen dituena:

$a\lor (b\lor c)=(a\lor b)\lor c$	$a\land (b\land c)=(a\land b)\land c$	elkarkorra
$a\lor b=b\lor a$	$a\land b=b\land a$	trukakorra
$a\lor (a\land b)=a$	$a\land (a\lor b)=a$	absortzio
$a\lor (b\land c)=(a\lor b)\land (a\lor c)$	$a\land (b\lor c)=(a\land b)\lor (a\land c)$	banakorra
$a\lor {\neg }a=1$	$a\land {\neg }a=0$	osagarria

Oinarrizko propietateak eta legeak

Legeak	0 balioa	1 balioa
A + 1 = 1	A + 1 = 0 + 1 = 1	A + 1 = 1 + 1 = 1
A • 1 = A	A · 1 = 0 · 1= 0	A · 1 = 1 · 1 = 1
A + 0 = A	A + 0 = 0 + 0 = 0	A + 0 = 1 + 0 = 1
A • 0 = 0	A · 0 = 0· 0 = 0	A · 0 = 1· 0 = 0
A + A = A	A + A = 0 + 0 = 0	A + A = 1 + 1 = 1
A • A = A	A • A = 0 · 0 = 0	A • A = 1 · 1 = 1
A **= A	0=0**=1*=0	1= 1**=0*=1

Kontuan hartuz 1 zenbakia logika proposizionaleko egia eta 0, gezurra dela. Eragiketetan logika proposizionalarekin antzekotasun aurki daitezke, besteak beste, biderketa logikoa($\land$) konjuntzioa izanik edo batuketa logikoa($\vee$) disjuntzioa.

Lehenengo teoremak dio edozer baliori 1 gehituz bat izango dela, hau da egiari egia gehituz edo gezurrari egia gehituz ondorioa egia izango dela. Gainera aljebra boolearran aipatu beharra dago batuketak, batuketa logikoa izena duela.

Bigarren teoremak dio A zenbakiari (1 edo 0 ) batekin biderkatzean bere emaitza A izango dela . Hau biderketarekiko elementu neutroa izanik. Batuketa logikoaren antzera, biderketa eragiketari biderketa logikoa  deritzo.

Hurrengo teoremak adierazten du A zenbakiari 0 gehituz emaitza bere burua izango dela, hain zuzen ere batuketa logikoaren elementu neutroa 0 dela.

Bestalde edozein zenbaki, berdin du 1 (egia) edo 0 (gezurra) den 0 rekin biderkatzean emaitza beti gezurra izango da.

Ildo beretik, hurrengo teoremek azpimarratzen dute bi gorputzen arteko eragiketa, hots,  bai biderketa logikoa bai batuketa logikoa bere emaitza bereburua izango dela.

De Morganen legeak adierazten du zenbaki baten alderantzizkoaren alderantzizkoa beti hasierako zenbakia izango dela, adibidez; 0=0**=1*=0 .

Booleren aljebraren ordena:

Ordena Booleren aljebran

Jakinda ${\displaystyle ({\mathfrak {B}},\lnot {},\lor ,\land )}({\mathfrak {B}},\lnot {},\lor ,\land )$ Booleren aljebra dela, honako hau egiazta daiteke:

$a\lor b=b$

$a\land b=a$

$\lnot a\lor b=V$

$a\land \lnot b=F$

Baldintza hauetakoren bat betetzen duten a, b proposizioei dagokienez, aurretik b) proposizioa betetzen dutela baiezta daiteke. Proposizio edo predikatuen kasuan a b baino indartsuagoa edo dominantea dela esaten dela, edo b a baino ahulagoa dela, eta irudikatzen dugula:

$a\preccurlyeq b$

Adibidez, proposizioetan:

a =Lurzorua zikina dago

b = Lurzorua oso zikina dago

Ondorioztatu ahal dugu hurrengoa : (Lehenengo proposizioa)

$a\lor b=b$

Bai lurzorua zikina dago edo lurzorua oso zikina dago.

Bitik edozein gertatzen bada, lurzorua oso zikina dagoela duela edo lurzorua zikina dago, argi eta garbi lurzorua zikina dago.

$a\land b=a$

Noski lurzorua zikina badago edo lurzorua oso zikina baldin badago.

Lurzorua oso zikina dagoela eta lurzorua zikina dagoela esaten badugu, eta bi baldintzak betetzen badira, lurzorua oso zikina dago.

$\lnot a\lor b=V$

Bestalde, lurzorua oso zikina ez dagoela edo lurzorua oso zikina dagoela egia da.

Lurzorua oso zikina ez badago, lurzorua pixkabat zikina egon daiteke edo lurzorua zikina ez dagoela adierazten du; lurzorua oso zikina ez dagoela edo lurzorua zikina dago, aukera guztiak hartzen ditu barnean.

$a\land \lnot b=F$

Lurzorua oso zikina badago baina lurzorua zikina ez badago ez da egia izango

Lurzorua oso zikina badagoela eta aldi berean lurzorua zikina badagoela esaten badugu, baieztapena argi eta garbi faltsua da.

Baieztapen murriztaileena indartsuena da eta ahulena gutxien murrizten duena, kasu honetan:

$Lurzorua\,oso\,zikin\preccurlyeq Lurzorua\,zikin$

Proposizioak lurzorua oso zikina dago edo lurzorua zikina dago gogorragoa edo dominanteagoa da.

Aljebra Boolearraren garapena

Aljebra boolearra, 1-etan eta 0-etan oinarritzen den logika da, eta hauen arteko eragiketak adierazteko, egiazkotasun taulak erabiltzen dira. Hauek ere, beste modu batzuetan adieraz daitezke, normalean, diagramen (ate logiko) bidez. Hala ere, taula hauek oso luzeak izatera iritsi daitezkeenez, 4 aldagai edo gutxiago daudenean Karnaugh-en mapak erabiltzen dira eragiketa horiek ahalik eta gehien sinplifikatzeko. Horrela, diagramak askoz laburragoak egin daitezke.

Diagramak (Ate Logikoak)

Artikulu printzipala: Ate logiko

Aljebra boolearra diagramen bidez adierazi daiteke, ate logikoak erabiliz. Hainbat motatako ate logikoak daude eta hauen interakzioen bidez eragiketa desberdinak adieraz daitezke. Ate hauek aldagai bat edo gehiago jaso eta bakarra itzultzen dute, 1 edo 0. Hainbat ate logiko desberdin daude eta bakoitzak aljebra boolearreko eragiketa bat egiten du.

OR ate logikoa:

OR ate logikoa batuketa logikoa adierazteko erabiltzen da, eta “+” ikurraren bidez adierazten da. Ate honek jasotzen duen balioetako bat gutxienez 1 bada, 1 itzuliko du, bestela 0.

AND ate logikoa:

AND ate logikoa biderketa logikoa adierazteko erabiltzen da, eta “·” ikurraren bidez adierazten da. Ate honek jasotzen duen balioetako bat gutxienez 0 bada, 0 itzuliko du, bestela 1.

NOT ate logikoa:

NOT ate logikoak alderantzizkoa bueltatzen du beti, hau da, 1 jasotzen badu 0 eta 0 jasotzen badu 1. Horregatik, ate honek elementu bakarra jaso dezake aldi berean. Normalean, aldagaia errepresentatzen duen letraren gainean marra bat ipiniz adierazten da.

Hiru ate logiko hauen konbinazioetatik beste batzuk lortzen ditugu. OR eta NOT interakzioak elkartuz, NOR ate logikoa sortzen da, eta AND eta NOT interakzioak elkartuz NAND ate logikoa.

NOR ate logikoa:

NOR ate logikoak esan bezala OR eta NOT elkartzen ditu, hau da, OR ate logikoak hainbat aldagai jasotzen ditu eta bakarra itzultzen du. Jarraian, aldagai hori NOT ate logikoak jasotzen du eta bere alderantzizkoa itzultzen du.

NAND ate logikoa:

NAND ate logikoak esan bezala AND eta NOT ateen konbinaziotik lortzen da. NOR-en kasuan bezala, AND ate batek hainbat aldagai jaso eta bakarra itzultzen du. Ondoren, NOT ate batek jasotzen du aldagai hori eta bere alderantzizkoa itzultzen du.

Normalean, NAND eta NOR dira ate logiko erabilienak, hauen konbinazioekin gainontzekoak lor daitezkeelako.

Azkenik, OR interakzioan oinarrituta beste ate logiko bat erabiltzen da, XOR edo OR esklusiboa.

XOR (OR esklusiboa):

OR esklusiboak batuketa logikoa, biderketa logikoa eta alderantzizkoa konbinatzen ditu.

NOR esklusiboa:

NOR esklusiboak, OR esklusiboa eta NOT konbinatzen ditu, hau da, OR esklusibo ate batek hainbat aldagai jasotzen ditu eta bakarra itzultzen du. Gero itzuli duen aldagai hori NOT batek jasotzen du eta horren alderantzizkoa itzultzen du.

Karnaugh-en mapak

Artikulu printzipala: Kharnaughen mapak

Gure sistemak 4 aldagai edo gutxiago dituenean, diagramak sinplifikatzeko Kharnaugh-en mapak erabiltzen dira. Mapa hauek oso modu sinplean funtzionatzen dute eta oso lagungarriak dira. Mapak erabiltzeko nagusiki 4 pausu jarraitu behar dira:

• Egiazkotasun taula egin:

Lehenik eta behin jasotako sistemaren egiazkotasun taula osatu beharko dugu.

• Egiazkotasun taula Kharnaugh-en mapara pasa:

Taula hauek desberdinak izango dira aldagai kopuruaren arabera. Taula hauek egiterakoan, oso garrantzitsua da zutabeen eta lerroen goiburuen esleipena, oso garrantzitsua da 1-eko guztiak elkarren segidan egotea. Behin taula eginda, egiazko taulan hauen balioak begiratuz osatzen da karnaugh en taula. Berez, emaitza 1 dutenak bakarrik hartu behar dira kontuan, hauek baitira sinplifikatzerakoan kontuan hartuko ditugunak.

• 1-ekoen multzoak egin:

Behin taula eginda dagoenean, batekoak 2ⁿ - ko multzoetan bilduko ditugu, baina horretarako ere arau batzuk jarraitu behar dira:

1. Elkarrekin hartutako bi gelaxkak ondoz ondo egon behar dira, ez diagonalean.
2. Karratuetan edo ilaraka elkartu daitezke baina ez L itxurako formetan.
3. Taula baten hertzak ondoz ondo daudela kontsideratzen da, donut bat izango balitz bezala.

• Lortutako taldeak aztertuz sinplifikatu:

Azkenik, talde berdinean bildu ditugun aldagaiak aztertu behar ditugu. Talde berean bildu dugun lauki bakoitzaren koordenatuak idatziko ditugu jarraian eta taldeko denetan errepikatzen direnak bakarrik gordeko ditugu. Bakarra badago lauak hartu beharko ditugu kontuan eta ezingo dugu sinplifikatu.

Erabilpenak

Bi egoeratako unitate minimoetan gordeko balira, eta unitate hauekin operatuko balitz. Arrazoi nagusia da fisikoki oso erraza delako bi egoeratako unitate minimo bat lortzea, adibidez: “itzalia eta piztua”,”piztua eta itzalia”, “1 eta 0”... edo elektronikan gehien erabiltzen dena, “tentsioa dago edo ez”. Aparatu elektronikoen hardwarearen diseinu eta funtzionamendua horretan oinarritzen da.

Elektronikako sistemarik oinarrizkoenak diodoak eta trantsitoreak dira. Hauek konbinatuz ate logikoak sor daitezke. Diodo bat itxia dagoela esaten da korronotea pasatzen denean, eta honi 1 balioa ematen zaio. Irekia dagoenean berriz, ez dago tentsiori, eta 0 balioa ematen zaio. Ate logikoak baldintza batzuk betzen direnean isten eta irekitzen diren elementuak dira, eta horrela korrontea modu konplexuagoan manipulatzea lortzen da. Oinarrizko ate logikoak AND, OR eta NOT ateak dira, eta hauek konbinatuz lortzen diren XOR, NOR eta NAND.

Aurkikuntza honekin elektronikako hainbat oinarrizko elementu sortu dira, hala nola: kodifikadoreak, dekodifikadoreak, memoriak edo mikroprozesatzaileak. Hauek funtzionarazteko zirkuitu logikoak erabiltzen dira. Sistema logiko baten zirkuitua lortzeko egiazkotasun taula batekin hasten da, eta hor sistema elektronikoak egiten duena txertatzen da, eta hortik haren funtzio logikoa eskuratzen da. Karnaughen mapak erabiliz (3 aldagai arte) edo beste metodo batzuen bitartez (adibidez Quine-McCluskey-ren metodoa 4 aldagai baino gehiagorekin lan egiteko) funtzio hori sinplifikatu egiten da. Azkenik zirkuitu logikoaren grafoa lortzen da.

Kanpo estekak

• Datuak: Q173183
• Multimedia: Boolean algebra / Q173183