1. kapitulua
ALJEBRA BOOLEARRA
Aljebra boolearra da zirkuitu logikoen portaera azaltzen duen oinarrizko
teoria matematikoa. Zirkuitu digitaletan prozesatzen diren seinaleek bi balio
besterik ez dute hartzen --egiazkoa eta faltsua, edo 1 eta 0-- eta seinale
horien balio-aldaketek aljebra boolearraren axiomei eta teoremei jarraitzen
diete. Horregatik, zirkuitu digitalak nola diseinatu eta erabili ikusi baino
lehen, beharrezkoa da aljebra hori ezagutzea. Hori da, beraz, kapitulu honen
helburua: aljebra boolearraren oinarrizko kontzeptuak azaltzea.
2 1. kapitulua: ALJEBRA BOOLEARRA
1.1. ALJEBRA BOOLEARRA
Giza arrazoibidearen lehen formalizazio matematikoa George Boole
matematikari ingelesak egin zuen, 1854. urtean. Horretarako, zenbakizko
aljebrarekin antz handia zuen beste aljebra bat definitu zuen, non "egiazkoa"
(true, 1) eta "faltsua" (false, 0) balio logikoak erabili baitzituen. Aljebra
horri, aljebra boolearra deitu ohi zaio.
Handik ia ehun urtetara, 1938an, Claude E. Shannon ingeniaritzako
ikasleak egindako lanen bitartez, ondorioztatu zen aljebra boolearra erabil
zitekeela zirkuitu digitalak analizatzeko eta diseinatzeko. Aljebra boolearrak
era abstraktuan tratatzen du zirkuituen portaera, eta, horregatik, zirkuitu
digitalak analizatzeko oinarrizko teoria da gaur egun ere, nahiz eta, urtetan
zehar, zirkuituak eraikitzeko teknologiek asko eboluzionatu duten.
1.1.1. Aljebra boolearraren axiomak
Aljebra bat definitzeko, hiru elementu hauek behar dira: (a) osagai multzo
bat; (b) eragiketa batzuk osagai horiekin; eta (c) axioma batzuk. Axiomek
(edo postulatuek) aljebraren oinarrizko erregelak edo ezaugarriak definitzen
dituzte.
Boolearra izateko, axioma konkretu batzuk bete behar ditu aljebra batek.
Huntington matematikariak publikatu zituen, 1904. urtean, aljebra
boolearraren axiomak.
Huntington-en axiomak laburbilduko ditugu hurrengo paragrafoetan.
Axioma horietan, osagai multzoa B da, eta bi eragiketa erabiltzen dira, bi
eragigaikoak: or --batuketa logikoa-- eta and --biderketa logikoa--.
Batuketa eta biderketa adierazteko, `+' eta `·' ikurrak erabili ohi dira: a + b
eta a · b. Testuinguruaren arabera, ikur horiei "eragile" deritze.
Axiomak bikoitzak dira, bi eragiketetarako adierazten baitira.
A1 axioma. B multzoko bi osagaien (edozeinen) batura zein
biderkadura logikoa B multzokoa da. Hau da, B multzoa "itxia" da bi
eragiketetarako.
BbaBba + ,
BbaBba ,
1.1. ALJEBRA BOOLEARRA 3
A2 axioma. Bi eragiketek elementu neutro bana dute B multzoan. B-ko
edozein elementu hartuta (a), a-ren eta elementu neutroaren arteko
eragiketaren emaitza a bera da.
Batuketaren elementu neutroa adierazteko, 0 ikurra erabiliko dugu, eta
biderketarena adierazteko, 1 ikurra.
aaBaB =+ 0/0
aaBaB = 1/1
A3 axioma. Bi eragiketek trukatze-legea betetzen dute; hau da,
eragigaien ordenak ez du eraginik emaitzan.
abbaBba +=+ ,
abbaBba = ,
A4 axioma. Bi eragiketek banatze-legea betetzen dute batak
bestearekiko.
)()()(,, cabacbaBcba ++=+
)()()(,, cabacbaBcba +=+
A5 axioma. B multzoko a elementuak (edozeinek) bere osagarria
dauka, a (ez-a), baldintza hauek betetzen dituena:
1/ =+ aaBaBa (emaitza biderketaren elementu neutroa da)
0/ = aaBaBa (emaitza batuketaren elementu neutroa da)
A6 axioma. B multzoak baditu, gutxienez, bi osagai desberdin.
baBba /,
Aipatu dugun bezala, boolearra deritzo axioma edo postulatu horiek
betetzen dituen aljebrari. B multzoan bi osagai baino ez dagoenean --1 eta
0--, kommutazio-aljebra ere deitzen zaio. Axiomak kontsistenteak eta
independenteak dira: ez dute kontraesanik sortzen eta ezin da bat ere
ondorioztatu besteetatik abiatuz.
Adi! Aljebra boolearrak hainbat desberdintasun du ohiko aljebrarekin konparatuta;
esaterako:
- B multzoa finitua da, eta zenbakien multzoa ez.
- Batuketa logikoak (+) banatze-legea betetzen du biderketa logikoarekiko (·);
zenbakizko aljebran, aldiz, ez.
4 1. kapitulua: ALJEBRA BOOLEARRA
- Zenbakizko aljebran ez da a elementua (elementu osagarria) definitzen.
- Aljebra boolearrean ez dira alderantzizko elementuak definitzen bi eragiketetan
(a batuketan eta 1/a biderketan), eta ez dira ez kenketa ez zatiketa eragiketak
definitzen.
1.1.2. Aljebra boolearraren teorema erabilgarri
batzuk
Aljebraren axiometatik hainbat lege edo teorema ondoriozta daitezke. Gure
helburua ez da aljebra boolearra xehetasunez aztertzea, eta horregatik ez
ditugu teorema horiek egiaztatuko, baina merezi du ohikoenak zerrendatzea,
hainbat unetan erabiliko ditugulako. Axiomekin ikusi dugun moduan,
teorema bakoitza bi eragiketetarako betetzen da.
T1 teorema edo idenpotentzia-legea
aaaBa =+
aaaBa =
T2 teorema
11 =+ aBa
00 = aBa
T3 teorema edo xurgapen-teorema
abaaBba =+ )(,
abaaBba =+ )(,
T4 teorema edo inboluzio-legea
aaBa =
hau da, elementu baten osagarriaren osagarria elementu bera da.
T5 teorema edo elkartze-legea
)()(,, cbacbaBcba ++=++
)()(,, cbacbaBcba =
T6 teorema edo DeMorgan-en legeak
babaBba =+ ,
babaBba += ,
1.1. ALJEBRA BOOLEARRA 5
T7 teorema
babaaBba +=+ ,
babaaBba =+ )(,
Bai axiomak bai teoremak bikoteka betetzen dira. Izan ere, dualitate-
printzipioa betetzen du aljebra boolearrak. Propietate horren arabera,
axiometatik ondorioztatzen den edozein berdintza aljebraikok bere "duala"
dauka, bi aldaketa hauek eginez lortzen dena:
- Bi eragiketak trukatu: biderketak batuketa bihurtu, eta alderantziz.
- Bi konstanteak trukatu: 0 konstanteak 1 bihurtu, eta alderantziz.
Esaterako, a + 1 = 1 a · 0 = 0 (T2 teorema). Irakurleak erraz egiazta
dezake propietate hori aurreko axioma eta teorema guztietan.
1.1.3. Oinarrizko eragiketa logikoak
1.1.3.1. Batuketa (or) eta biderketa (and)
Esan dugunez, bi eragiketa definitzen dira kommutazio-aljebran B = {0, 1}
osagai multzoarekin: batuketa logikoa --a or b edo a + b-- eta biderketa
logikoa --a and b edo a · b (askotan, punturik gabe ere: a b)--. Kontuan
hartuta osagai multzoa mugatua dela --bi osagai bakarrik--, eragiketa bat
definitzeko, nahikoa da eragigaien balioen konbinazio guztien emaitzak
ematea. Halako informazioa biltzen duen taulari egia-taula deritzo.
Honela definitzen dira bi eragiketak, egia-taulak erabiliz:
a b a or b a b a and b
0 0 0 0 0 0
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1
1.1. taula. Batuketa (or) eta biderketa (and) eragiketa logikoen definizioak edo
egia-taulak.
Beraz, batura 1 izango da eragigairen bat 1 denean; biderkadura, berriz,
biak 1 direnean. Bi eragiketak horrela definituta, erraz egiazta daiteke
aljebraren axiomak betetzen direla (ikus 1.1. taula):
6 1. kapitulua: ALJEBRA BOOLEARRA
A1 B itxia da bi eragiketetarako: emaitza 0 edo 1 da beti.
A2 Bi eragiketek elementu neutroa dute:
batuketaren elementu neutroa 0a da: 0 + 0 = 0 eta 1 + 0 = 1
biderketaren elementu neutroa 1a da: 0 · 1 = 0 eta 1 · 1 = 1
A3 Bi eragiketek trukatze-legea betetzen dute:
0 + 1 = 1 + 0 = 1
0 · 1 = 1 · 0 = 0
A4 Bi eragiketek banatze-legea betetzen dute bata bestearekiko:
)()()(,, cabacbaBcba +=+
)()()(,, cabacbaBcba ++=+
Hori frogatzeko, nahikoa da berdintza bakoitzaren bi aldeetako
espresioen balio guztiak kalkulatzea eta konparatzea.
Froga dezagun lehenengo berdintza. 3 aldagai erabiltzen direnez, 23
= 8
kasu posible analizatu behar dira. Emaitza guztiak 1.2. taulan ageri dira.
Lehen hiru zutabeetan, hiru aldagaien konbinazio guztiak daude, eta,
ondoan, aurreko espresioaren bi aldeetako funtzioen emaitzak.
a b c b + c a · (b + c) a · b a · c a · b + a · c
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
1.2. taula. Banatze-legearen froga.
1.2. taulan ageri denez (grisez markatutako bi zutabeak), bi espresioen
balioak beti dira berdinak; hortaz, banatze-legea betetzen da.
Adierazpen duala frogatzea ariketa gisa uzten dugu.
A5 0 elementuaren osagarria 1a da: 0 + 1 = 1 eta 0 · 1 = 0; beraz, 10 =
1 elementuaren osagarria 0a da: 1 + 0 = 1 eta 1 · 0 = 0; beraz, 01 =
A6 Bi elementu daude B multzoan, 1a eta 0a.
1.2. FUNTZIO LOGIKOAK 7
1.1.3.2. Ezeztapena (not)
Bi eragigai erabiltzen dituzte or eta and eragiketek. not eragiketak, aldiz,
eragigai bakarra du. Osagarria ere deitzen zaio eragiketa honi.
Hau da not eragiketaren egia-taula, A5 axiomatik (eta or eta and eragiketen
definizioetatik) ondorioztatzen den moduan (ikus aurreko atala):
a not a
0 1
1 0
1.3. taula. not eragiketaren egia-taula.
Eragile gisa, not a edo a erabiltzen da. Irakurtzean, berriz, hauetako eraren
bat, denak baliokideak: a ezeztatua, a-ren osagarria, edo ez-a.
1.2. FUNTZIO LOGIKOAK
Funtzio logikoa aplikazio bat da, non jatorrizko multzoa {0, 1}n
biderketa
cartesiarra den, eta helburuko multzoa {0, 1}; hots: {0, 1}n
{0, 1}.
Jatorrizko multzoan 2n
osagai daude, eta esaten da funtzioa n aldagaikoa
dela; helburuko multzoan, aldiz, bi osagai besterik ez dago. Hori dela eta, n
aldagaiko
n
2
2 funtzio desberdin defini daitezke (aldagai bakarreko 4 funtzio;
2 aldagaiko 16 funtzio; eta abar).
Esaterako, hauek dira aldagai bakarreko 4 funtzioak:
a f1 f2 f 3 f 4
0 0 0 1 1
1 0 1 0 1
1.4. taula. Aldagai bakarreko 4 funtzio logikoak; haien artean, not funtzioa (f3) eta
identitatea (f2).
Modu berean, hauek dira 2 aldagaiko 16 funtzio logikoak:
a b f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1.5. taula. Bi aldagaiko 16 funtzio logikoak.
8 1. kapitulua: ALJEBRA BOOLEARRA
Funtzio horien artean, jadanik definitutako biderketa (and) eta batuketa
(or) logikoak daude (f2 eta f8). Gainerakoen artean, zirkuitu digitaletan
askotan erabiltzen diren beste funtzio batzuk daude:
xor funtzioa (f7), eta haren ezeztapena, equ funtzioa (f10).
a b a xor b a equ b
0 0 0 1
0 1 1 0
1 0 1 0
1 1 0 1
1.6. taula. xor eta equ funtzio logikoen egia-taula.
Beraz, xor (exclusive or) funtzioak 1 balioa hartzen du bi aldagaiak
desberdinak direnean, eta equ funtzioak, aldiz, biak berdinak direnean.
xor funtzioa adierazteko, ikurra erabiltzen da, eta equ funtziorako,
ikurra. Egia-taulan ageri den moduan, honako hau betetzen da:
baba = eta baba =
nand (f15) eta nor (f9) funtzioak, and eta or funtzioen ezeztapena,
hurrenez hurren (ikus 1.5. taula).
Edozein funtzio logiko adieraz daiteke not, and eta or funtzio logikoen
bidez. Ezaugarri hori dela eta, esaten da hiru funtzio horiek sistema oso bat
osatzen dutela. Adibidez, xor eta equ funtzioak honela adieraz daitezke and,
or eta not eragiketen bidez1
:
bababa += eta bababa +=
Berdintzak egiaztatzeko, adierazpen berrien egia-taulak egin behar dira eta
1.6. taulako definizioekin erkatu. 1.7. taulan ageri da lehenengo berdintzaren
froga. Bestea irakurlearentzat uzten da.
a b ba ba baba + a b
0 0 0 0 0 0
0 1 1 0 1 1
1 0 0 1 1 1
1 1 0 0 0 0
1.7. taula. xor funtzioaren definizioa and, or eta not bitartez.
1
Espresio aljebraikoetan, lehentasun hauek dituzte eragileek: not, and eta or.
1.2. FUNTZIO LOGIKOAK 9
1.2.1. Funtzio logikoen adierazpena
Bi era nagusi daude funtzio logikoak adierazteko, eta jadanik biak erabili
ditugu aurreko adibideetan: egia-taulak eta adierazpen aljebraikoak.
Lehendabiziko kasuan, egia-taulan, funtzioaren balioa adierazten da
aldagaien konbinazio guztietarako (ez ahaztu: B multzoa finitua da, bi
osagaikoa soilik, eta, beraz, konbinazio guztiak ere finituak dira eta taula
batean bil daitezke). Dena den, aldagai askoko funtzioak horrela adieraztea
astuna da, aldagaien balioen konbinazio guztiak asko izango baitira.
Bigarren aukera funtzioaren adierazpen aljebraikoa da, hau da, aldagaien
eta eragileen bidezko adierazpena (aurreko atalean, xor eta equ funtzioekin
egin dugun moduan).
Funtzio logiko baten adierazpen aljebraikotik abiatuta, erraza da haren
egia-taula lortzea (nahikoa da adierazpenean adierazten diren eragiketak
egitea aldagaien balio guztietarako), baina alderantzizkoa, hots, egia-taulatik
abiatuta adierazpen aljebraikoa lortzea, ez da hain sinplea.
Ikus dezagun adibide bat. 1.8. taulan, f funtzioaren egia-taula ageri da.
Nola adierazi funtzio hori adierazpen aljebraiko baten bitartez?
c b a f
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
1.8. taula. Funtzio logiko baten egia-taula.
Galdera horri erantzuteko, lehendabizi bi definizio emango ditugu.
Minterm-a (mi): funtzio logiko baten aldagai guztien biderketa logikoa
da, non aldagaiak ezeztatuta edo ezeztatu gabe ageri baitira. Egia-
taulako lerro bakoitzari funtzioaren minterm bat dagokio.
Minterm-a idaztean, aldagaia ezeztatuko da haren balioa 0 bada, eta ez
da ezeztatuko 1 bada. Esaterako, c = 1, b = 0, eta a = 1 direnean,
minterm-a abc da.
10 1. kapitulua: ALJEBRA BOOLEARRA
Hala, 3 aldagaiko funtzio batek (1.8. taulakoak, esaterako) 8 minterm
ditu. Taularen ordena berari jarraituz, hauek dira minterm-ak:
abcm0 = abcm1 = abcm2 = abcm3 =
abcm4 = abcm5 = abcm6 = abcm7 =
Minterm-ak izendatzeko, aldagaien balioek bitarrez adierazten duten
zenbakia erabiltzen da: 0 0 0 m0, 0 0 1 m1, eta abar.
Maxterm-a (Mi): funtzio logiko baten aldagai guztien batuketa logikoa
da, non aldagaiak ezeztatuta edo ezeztatu gabe ageri baitira. Egia-
taulako lerro bakoitzari funtzioaren maxterm bat dagokio.
Maxterm-a idaztean, aldagaia ezeztatuko da haren balioa 1 bada, eta ez
da ezeztatuko 0 bada. Esaterako, c = 1, b = 0, eta a = 1 direnean,
maxterm-a abc ++ da.
Esaterako, 3 aldagaiko funtzio batek 8 maxterm ditu. 1.8. taularen
ordena berari jarraituz, hauek dira maxterm-ak:
abcM ++=0 abcM ++=1 abcM ++=2 abcM ++=3
abcM ++=4 abcM ++=5 abcM ++=6 abcM ++=7
Erraz egiazta daiteke, DeMorgan-en legeak erabiliz, honako erlazio hau
betetzen dela minterm-en eta maxterm-en artean .ii Mm =
Minterm-ak eta maxterm-ak erabiliz, bi aukera ditugu funtzio logiko baten
adierazpen aljebraikoa lortzeko, egia-taulatik abiatuta:
a. 1 balioa hartzen duten minterm guztien batuketa gisa. Adibidez,
honela adieraz daiteke aurreko f funtzioa (ikus 1.8. taula):
abcabcabcabcabcf ++++=
Honako adierazpen hauek ere erabiliko ditugu funtzioak adierazteko:
f = (m1, m2, m5, m6, m7) = (1, 2, 5, 6, 7)
b. 0 balioa hartzen duten maxterm guztien biderketa gisa. Adibidez,
honela adieraz daiteke aurreko f funtzioa:
)()()( abcabcabcf ++++++=
Aurrekoan bezala, honako adierazpen hauek ere erabiliko ditugu
funtzioak adieratzeko:
f = (M0, M3, M4) = (0, 3, 4)
1.2. FUNTZIO LOGIKOAK 11
Funtzio logikoak adierazteko aurreko bi aukerei era kanonikoak deitzen
zaie. Zirkuitu digitaletako funtzioak adierazteko, minterm-en bidezko era
kanonikoa erabili ohi da.
Bi adierazpen kanonikoak baliokideak dira. Hori egiaztatzeko, lehen ikusi
dugun moduan, egia-taulak idatz eta konpara daitezke. Baina hori ez da
aukera bakarra. Aljebra boolearraren axiomak eta teoremak aplika daitezke
adierazpen batetik bestera iristeko.
Baliokidetasuna frogatzeko, f funtzioaren minterm-en bidezko
adierazpenetik abiatuko gara, eta, horretarako, jatorrizko f funtzioaren 0koak
hartu behar ditugu kontuan (ikus 1.8. taula):
abcabcabcabcabcf ++++= beraz,
abcabcabcf ++= (f funtzioaren osagarria)
Berdintzaren bi alderdiak ezeztatzen ditugu:
abcabcabcf ++=
Orain, T4 teorema (inboluzio-legea) aplikatzen diogu ezkerreko alderdiari
eta DeMorgan-en legea (T6) eskuinekoari:
abcabcabcf =
Berriro DeMorgan-en legea aplikatuz funtzioaren gai bakoitzari:
)()()( abcabcabcf ++++++=
Azkenik, berriro T4 teorema (inboluzio-legea) aplikatuz:
)()()( abcabcabcf ++++++=
Horixe da f funtzioaren bigarren adierazpen kanonikoa: 0 balioa hartzen
duten maxterm-en biderketa. Beraz, frogatu dugu bi adierazpen kanonikoak
baliokideak direla.
1.2.2. Funtzioen adierazpenaren minimizazioa
Funtzio logiko baten adierazpen aljebraikotik abiatuta, ez da zaila funtzio
logiko hori gauzatzen duen zirkuitu digital bat sortzea. Hori nola egiten den,
hurrengo kapituluan ikusiko dugu.
12 1. kapitulua: ALJEBRA BOOLEARRA
Hala ere, ikusi dugun bezala, funtzio logiko batek ez du adierazpen
bakarra: bi adierazpen kanonikoak ikusi ditugu, eta gehiago ere badaude.
Beraz, zein da egokiena zirkuitu fisikoa eraikitzeko?
Erantzuna kontuan hartu nahi diren diseinu-parametroen araberakoa izango
da: zirkuiturik "txikiena", hots, hardware minimoa erabiltzen duena,
kontsumo baxuenekoa, azkarrena, merkeena... Une honetan, zirkuitu
"txikienak" sortzea interesatzen zaigu. Ez dago zuzeneko erlaziorik
adierazpen aljebraikoaren eta zirkuitu digital baten osagai kopuruaren artean,
baina, oro har, komeni da adierazpen aljebraiko minimoak erabiltzea
zirkuituak eraikitzeko2
.
Funtzio logiko baten adierazpen minimoa lortzeko, aljebraren axiomak eta
teoremak erabili behar dira, batik bat funtzioaren adierazpena sinplifikatzen
dutenak. Ikus dezagun adibide bat.
Izan bedi 3 aldagaiko funtzio logikoa, honela definituta, lehenengo era
kanonikoan, minterm-en batuketa gisa: f = (0, 1, 2, 3, 6).
Beraz, =++++= abcabcabcabcabcf (banatze-legea)
=++++= abcaabcaabc )()( (A5/A2 axiomak)
=++= abcbcbc (banatze-legea)
=++= abcbbc )( (A5/A2 axiomak)
=+= abcc (T7 teorema)
abc += adierazpen minimoa
Funtzioa ezin da gehiago sinplifikatu, eta, beraz, hori da haren adierazpen
minimoa. Garbi dago: "erosoagoa" da adierazpen minimo hori hasierakoa
baino.
Aldagai gutxiko funtzioak horrela minimizatzea ez da zaila, baina aldagai
kopurua handia bada, konplexua izan daiteke adierazpen minimoa lortzea.
Izan ere, hainbat programa daude funtzio logikoak minimizatzeko
konputagailuaren bidez.
2
Gaur egun, funtzio logikoen minimizazioa ez da behinola izan zen bezain garrantzitsua:
gero eta transistore gehiago integratzen dira zirkuituetan eta diseinu-tresnak egokitu dira
ezaugarri hori aprobetxatzeko. Hala ere, egokia eta erosoa da ahalik eta funtzio sinpleenak
erabiltzea.
1.2. FUNTZIO LOGIKOAK 13
1.2.2.1. Karnaugh-en mapak
Prozedura aljebraikoaz gain, badago metodo grafiko nahiko sinplea funtzio
logikoak minimizatzeko, aldagai kopurua baxua denean: Karnaugh-en
mapak.
Funtzio logiko baten Karnaugh-en mapa (edo, laburrago, K-mapa)
funtzioaren egia-taula baino ez da, baina bi dimentsiotan eta ordena
berezian adierazita (gero azalduko dugu ordena horren zioa). Itxura
desberdineko K-mapak daude, funtzioaren aldagai kopuruaren arabera. 1.1.
irudian, 2, 3 eta 4 aldagaiko K-mapak ageri dira (5 aldagaiko mapa 4
aldagaiko bi mapa gisa adierazi ohi da; 6koa, 4 aldagaiko lau mapa moduan;
eta abar; hala ere, aldagai kopurua altua denean, K-mapak ez dira oso
erabilgarriak).
a
b 0 1
0 m0 m1
1 m2 m3
ba b
c 00 01 11 10
0 m0 m1 m3 m2
1 m4 m5 m7 m6 c
a
ba b
dc 00 01 11 10
00 m0 m1 m3 m2
01 m4 m5 m7 m6
11 m12 m13 m15 m14
c
d
10 m8 m9 m11 m10
a
1.1. irudia. Bi, hiru eta lau aldagaiko Karnaugh-en mapak (geziek minterm baten
"albokoak" adierazten dituzte, bit bakar batean bereizten direnak).
1.1. irudian ageri den moduan, mapetako gelaxka bakoitza funtzioaren
minterm bat da (minterm-ak esleitzeko, dcba ordena erabili ohi da, a izanik
beti "pisu" txikieneko aldagaia). Mapako gelaxka bakoitzean, minterm
horretarako funtzioak hartzen duen balioa idatzi behar da. Ikus ditzagun
adibide batzuk.
1. adibidea
ababf += = (0, 1)
a
b 0 1
0 1 1
1 0 0
14 1. kapitulua: ALJEBRA BOOLEARRA
2. adibidea
abcabcabcabcabcf ++++=
f = (0, 1, 2, 5, 7)
ba b
c 00 01 11 10
0 1 1 0 1
1 0 1 1 0 c
a
3. adibidea
abcdabcdabcd
abcdabcdabcdf
+++
+++=
f = (0, 2, 6, 10, 13, 14)
ba b
dc 00 01 11 10
00 1 0 0 1
01 0 0 0 1
11 0 1 0 1
c
d
10 0 0 0 1
a
Azter dezagun 1.1. irudiko 4 aldagaiko mapa. Ezkerraldean, d eta c
aldagaien balioak ageri dira, eta goiko aldean, berriz, b eta a aldagaienak,
ordena honetan: 00, 01, 11, 10. Ordena hori dela eta --ondoz ondoko
kodeak bit bakar batean bereizten dira--, propietate berezi bat dute
Karnaugh-en mapetako gelaxkek: gelaxka bati dagokion minterm-a eta
alboko gelaxketako minterm-ak aldagai bakar batean bereizten dira (gauza
bera gertatzen da gainerako mapetan).
Adibidez, 4 aldagaiko mapan, gelaxka bakoitzak 4 gelaxka ditu alboetan:
goian, behean, ezkerrean eta eskuinean (oro har, n aldagaiko mapetan, n
albo-gelaxka daude). 1.1. irudian ageri den moduan, hau gertatzen da:
- gelaxka jakin bat (m5) abcd
- albo-gelaxkak abcd (m13, azpian, d aldagaia aldatuta)
abcd (m1, gainean, c aldagaia aldatuta)
abcd (m7, eskuinean, b aldagaia aldatuta)
abcd (m4, ezkerrean, a aldagaia aldatuta)
Gainera, mapak "zirkularrak" dira, hots, ertz batean kokatutako gelaxkaren
albokoa kontrako aldean dagoen gelaxka da, 1.1. irudiko 3 aldagaiko mapan
ageri den moduan (m4 gelaxka m6 gelaxkaren albokoa da).
K-mapen propietate hori erabiltzen da funtzioen adierazpen aljebraikoak
minimizatzeko. Izan ere, baldin baditugu 1 balioko minterm-ak alboko bi
gelaxkatan, honako sinplifikazio-erregela hau aplika dakieke, babab =+ ,
1.2. FUNTZIO LOGIKOAK 15
aldagai bakar batean bereiziko baitira. Hala, funtzioaren adierazpen
sinpleagoa lortuko dugu: aldagai komunak baino ez dituen gai bakar batean
bilduko ditugu jatorrizko bi gaiak.
Teknika hori --funtzioaren bi gai bakar batean biltzea-- modu
errekurtsiboan aplika daiteke tamaina bereko elkarketekin; hots, 4ko
elkarketak egin daitezke 2ko elkarketekin; 8koak, 4koekin, eta abar (betiere,
2ren berreturak). 1.2. irudian, minterm-en elkarketa batzuk ageri dira.
ba b
dc 00 01 11 10
00 1 1 1 1
01 0 0 0 1
11 0 1 1 1
c
d
10 1 1 0 1
a
ba b
dc 00 01 11 10
00 1 1 1 1
01 0 1 1 1
11 0 0 1 1
c
d
10 1 0 1 1
a
1.2. irudia. Gelaxka-elkarketa posible batzuk. Kontuan hartu mapa "zirkularra" dela.
Hau da, beraz, funtzio baten adierazpen minimoa lortzeko prozedura:
0. Kontuan hartu 1 balioa duten mapako (funtzioko) minterm-ak edo
gelaxkak.
1. Ahal den neurrian, elkartu gelaxka horiek 2naka, 4naka, 8naka, baldin
eta alboko posizioetan badaude. Aukeran, elkarketarik handiena erabili
behar da.
2. Oro har, aukera bat baino gehiago izango da 1ekoak elkartzeko. Hala
bada, hasi beti elkarketa-aukera bakarra (edo gutxien) duten gelaxkekin.
3. Dagoeneko beste elkarketa batean sartu diren 1ekoak berriro elkar
daitezke, horrekin lortzen bada beste 1eko batzuk multzo handiagoetan
elkartzea. Hain zuzen ere, a + a = a da.
4. Elkartze-prozesua bukatzen da 1eko guztiak kontuan hartu eta elkarketa
handienetan bildu direnean. Elkarketa kopuruak ahalik eta txikiena izan
behar du.
5. Elkarketei dagozkien gai sinplifikatuen batuketa da funtzioaren
adierazpen minimoa. Gai horiek lortzeko, kontuan hartu behar dira
bakarrik elkarketa horietako minterm-etan balio bera duten aldagaiak,
eta ez aldatzen direnak; adibidez: cacbacba =+ .
16 1. kapitulua: ALJEBRA BOOLEARRA
Ikus dezagun nola minimizatu aurreko adibideetako funtzioak.
1. adibidea: ababf +=
a
b 0 1
0 1 1
1 0 0
Bi 1eko daude funtzioan. Bata bestearen alboan daudenez, elkartu egin
daitezke. Bi gelaxka horietan komuna honako hau da: b = 0. Beraz, hau da
funtzioaren adierazpen minimoa: bf =
2. adibidea: abcabcabcabcabcf ++++=
ba b
c 00 01 11 10
0 1 1 0 1
1 0 1 1 0 c
a
1ekoak elkartzeko, cba = 010 minterm-arekin has gaitezke, eta elkartu 000
minterm-arekin (hori da duen aukera bakarra); gai berria ac da. Gauza bera
egin daiteke 101 eta 111 minterm-ekin, eta emaitza ac da. Azkenik, 001 eta
000 minterm-ak elkar daitezke eta bc gaia sortu. Ikusten den moduan, 000
minterm-a bi elkarketetan sartu da, horrekin funtzio sinpleagoa lortuko baita.
Hala, hau da funtzioaren adierazpen minimoa: bcacacf ++=
Hainbat kasutan, adierazpen minimo bat baino gehiago lor daiteke. Esaterako,
honela ere minimiza daiteke aurreko K-mapa:
ba b
c 00 01 11 10
0 1 1 0 1
1 0 1 1 0 c
a
Kasu honetan, 001 minterm-a 101 minterm-arekin elkartu dugu; gai berria
ab da, eta funtzioa abacacf ++= . Bi adierazpenak baliokideak dira.
1.2. FUNTZIO LOGIKOAK 17
3. adibidea: abcdabcdabcdabcdabcdabcdf +++++=
ba b
dc 00 01 11 10
00 1 0 0 1
01 0 0 0 1
11 0 1 0 1
c
d
10 0 0 0 1
a
0000 minterm-a elkartzeko, aukera bakarra dago: 0010 minterm-arekin;
funtziorako gai berria acd da. Bestalde, eskuineko zutabeko lau minterm-ak
ere elkar daitezke, eta honako gai hau sortu: ab . Azkenik, 1101 minterm-a
ezin da beste inorekin elkartu, eta hari dagokion gaia abcd izango da. Beraz:
abcdacdabf ++= .
Laburrean. K-mapak tresna grafiko sinple bat dira funtzioen adierazpen
aljebraiko minimoak lortzeko, minterm-ak elkartuz gai sinpleagoak
erdiesteko. Mapen bidez, aljebra boolearraren axiomak eta teoremak besterik
ez da aplikatzen (batik bat babab =+ eta a + a = a). Dena den, zaila da K-
mapak erabiltzea aldagai kopurua altuagoa denean; kasu horietarako, bide
aljebraikoa baino ez da geratzen (oro har, konputagailuaren laguntzaren
bidez).
1.2.3. Zehaztu gabeko gaiak (don't care)
n aldagaiko funtzio logiko batean, 2n
konbinazio desberdin daude: sarrera-
aldagaien konbinazio bakoitzeko bat. Sistema logikoen portaera adierazten
duten funtzio logikoak interesatzen zaizkigu, eta, horietako askotan, ohikoa
da sarrera-aldagaien konbinazio guztiak behar ez izatea. Bi arrazoirengatik
gerta daiteke hori: (a) konbinazio horiek ez direlako inoiz gertatuko; edo (b)
gertatzen badira ere, berdin zaigulako funtzioak hartuko duen balioa,
eraginik izango ez duelako (ikus 1.8. ariketa).
Kasu horietan, esaten da funtzioa ez dagoela zeharo espezifikatuta, ez baita
emaitza adierazten --ez 0, ez 1-- hainbat sarrera-konbinaziotarako. Zehaztu
gabeko balio horiek egia-tauletan eta K-mapetan adierazteko, "x" edo ""
ikurra erabiliko dugu (baita d letra ere --don't care-- funtzioa minterm-en
batukari gisa ematen denean). Minterm horiei zehaztu gabeko gaiak deritze.
18 1. kapitulua: ALJEBRA BOOLEARRA
Adibidez,
a b f
0 0
0 1 1
1 0 1
1 1 0
f = (1, 2) + d(0)
Funtzio horrek zehaztu gabeko gai bat du: bi aldagaiak 0 direnean, "berdin
zaigu" zein den funtzioaren balioa; beraz, 1 edo 0 izan daiteke.
Sinplifikatu behar badugu zehaztu gabeko gaiak dituen funtzio bat, 0 gisa
edo 1 gisa hartuko dugu gai horien balioa, funtzioaren adierazpena
minimizatzearren. Hau da, 1 baliokotzat hartuko ditugu baldin eta minterm-
en elkarketa handiagoak egin badaitezke haien bitartez; bestela, 0 baliokotzat
hartuko ditugu. Ikus dezagun adibide bat.
f = (1, 7, 9, 11) + d(3, 5, 12) funtzioaren adierazpen aljebraiko minimoa
lortu behar da. Funtzioaren lau minterm 1ekoak dira, eta badaude zehaztu
gabeko hiru gai. Lehendabizi, K-mapa irudikatuko dugu.
ba b
dc 00 01 11 10
00 0 1 0
01 0 1 0
11 0 0 0
c
d
10 0 1 1 0
a
1 balioa duten minterm-ak elkartzeko, zehaztu gabeko gaiak ere erabil
daitezke, horrela sortutako elkarketak handiagoak badira. Adibidean, 0001
eta 0111 minterm-ak elkartu ahal izango ditugu, 0011 eta 0101 zehaztu
gabeko gaiak 1ekotzat hartuz. Era berean, 0011 zehaztu gabeko gaiaren
bidez, elkarketa handiago batean (4koan) sar daitezke 1001 eta 1011
minterm-ak (0001 minterm-arekin batera).
1.2. FUNTZIO LOGIKOAK 19
ba b
dc 00 01 11 10
00 0 1 0
01 0 1 0
11 0 0 0
c
d
10 0 1 1 0
a
Beraz, bi elkarketa horiek direla eta, hau izango da f funtzioaren adierazpen
minimoa:
acadf +=
Hori lortzeko, zehaztu gabeko bi gai hartu ditugu elkarketetarako
(1ekotzat, beraz), eta hirugarrena (1100), aldiz, ez (0kotzat hartu da).
20 1. kapitulua: ALJEBRA BOOLEARRA
1.3. ARIKETA EBATZIAK
Aljebra boolearraren oinarrizko kontzeptu teorikoak azaldu ditugu aurreko
paragrafoetan. Atal honetan, berriz, ariketa batzuk ebatziko ditugu,
kontzeptu teoriko horiek nola erabiltzen diren argi eta garbi erakusteko
asmoz. Ariketa guztiak sinpleak dira, eta zehatz-mehatz azalduko ditugu;
beraz, gaia ezagutzen badu, irakurleak hurrengo kapituluetara jo dezake.
1.1. Ariketa
Aljebra boolearraren axiomak eta teoremak erabiliz, sinplifika ezazu funtzio
logiko honen adierazpen aljebraikoa:
acabcbaabdcbaf ++++=
Adierazpen aljebraikoak sinplifikatzeko, modu bat baino gehiago dago.
Esaterako, adibide honetan ab faktore komuna atera daiteke 1. eta 3. gaietan,
eta b 2. eta 4. gaietan. Hala,
acaabcdcbaf ++++= )()(
Lehenengo parentesiko adierazpenari T7 teorema aplika dakioke, eta
bigarrenari A5 axioma (ikus 1.1.1. eta 1.1.2. atalak). Beraz,
acbcdbaacbcdbaf +++=+++= )(1)(
non b · 1 = b dela aplikatu baitugu (A2 axioma).
Orain, f funtzioaren lehenengo eta bigarren batugaiei aplika dakieke berriro
T7 teorema, eta, hala, lehenengo batugaiko b aldagaia kendu; hau da,
acbcdaf +++= )(
Azkenik, banatze-legea (A4 axioma) aplikatzen badugu lehenengo gaian,
bi gai berdinak lortuko ditugu adierazpidean -- acca = --, eta beraz, bat
ken daiteke (T1 teorema):
bcdabcadaacbcadaf ++=++=+++= )(
Hori da f funtzioaren adierazpen minimoa, ezin baita gehiago sinplifikatu.
1.3. ARIKETA EBATZIAK 21
1.2. Ariketa
Adieraz ezazu ))(( dacbadf ++= funtzioaren osagarria, eta minimiza
ezazu haren adierazpena.
Funtzio baten osagarria lortzeko, not eragilea aplikatu behar da. Beraz,
))(( dacbadf ++=
Gero, adierazpena sinplifikatzeko, DeMorgan-en legeak aplika daitezke
(T6 teorema), gainerako legeekin batera. Hasteko, biderketa baten
ezeztapena dago; ondorioz, biderketa batuketa bihurtuko dugu eta bi
biderkagaiak ezeztatu:
))(())(( dacbaddacbadf +++=++=
Eragiketa bera aplika dakioke orain bigarren gaiari: batuketa biderketa
bihurtuz eta bi eragigaiak ezeztatuz. Hau da,
))(())(( dacbaddacbadf ++=++=
non, azkenean, aa = dela erabili baitugu (T4 teorema).
Prozedura bera aplika daiteke behin eta berriz:
=+++= ))(( dacbadf
=++=++= )))((()))((( dacbaddacbad
))(())(( dacbaddacbad +++=+++=
Azkenik, adierazpen hori sinplifikatuko dugu:
dcaacabaddacabadf +++=+++= )(
Banatze-legea aplikatu ondoren, hirugarren gaia ken daiteke 0=aa
delako (A5 axioma). Era berean, 4. gaia sinplifika daiteke 1.arekin, T7
teorema erabiliz.
Beraz, hauxe da f funtzioaren adierazpen minimoa:
)( cbadcabadf ++=++=
22 1. kapitulua: ALJEBRA BOOLEARRA
1.3. Ariketa
Sor ezazu funtzio honen egia-taula: )()( cabcbaf ++=
Funtzio baten egia-taula osatzeko, funtzioak hartzen dituen balioak
kalkulatu behar ditugu, aldagaien balioen konbinazio guztietarako. Modu
askotan egin badaiteke ere, egokia da taulako ezkerreko aldean funtzioaren
aldagaiak idaztea, eta eskuineko aldean, berriz, funtzioak hartzen dituen
balioak. Funtzioa konplexua den neurrian, komeni da funtzioaren gaien eta
"azpigaien" balioak ere taulan idaztea, lagungarriak direlako funtzioaren
balioa kalkulatzeko.
Beraz, adibide honetarako egingo dugun egia-taulan, c, b eta a aldagaien
balioak idatziko ditugu ezkerraldean; ondoan, ,ba ,cba + ca eta cab +
gaiak; eta azkenik, f funtzioa. 3 aldagaiko funtzioa denez, 8 kasu desberdin
(23
) izango ditugu aldagaien balio gisa, taulan ageri direnak.
c b a ba cba + ca cab + f
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Prest gaude egia-taula betetzeko, zutabez zutabe edo lerroz lerro,
oinarrizko eragiketen edo funtzioen egia-taulak kontuan hartuz (not, or,
and...). Esaterako, ba zutabean, 1eko bat ageriko da bakarrik a = 1 eta b = 0
direnean. Gainerako kasuetan, emaitza 0 da.
c b a ba cba + ca cab + f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
1.3. ARIKETA EBATZIAK 23
Prozedura bera errepikatu behar da gainerako zutabeak betetzeko. Hona
hemen tarteko emaitzak:
c b a ba cba + ca cab + f
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 0 0 0 0 1
0 1 1 0 0 0 1
1 0 0 0 1 1 1
1 0 1 1 1 0 0
1 1 0 0 1 1 1
1 1 1 0 1 0 1
Azkenik, funtzioaren balioak kalkulatuko ditugu, taulako tarteko bi
emaitzak (grisez bereizita) biderkatuz. Hona, beraz, f funtzioaren egia-taula:
c b a ba cba + ca cab + f
0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0
0 1 0 0 0 0 1 0
0 1 1 0 0 0 1 0
1 0 0 0 1 1 1 1
1 0 1 1 1 0 0 0
1 1 0 0 1 1 1 1
1 1 1 0 1 0 1 1
Aldagai askoko funtzioen egia-taulak oso luzeak dira; hainbat kasutan, hala
ere, taulen idazketa sinplifika daiteke lerroak bilduz. Esaterako, aurreko
taula era honetan ere idatz daiteke:
c b a f
0 0
1 0 0 1
1 0 1 0
1 1 1
Honela irakurri behar da taulako lehen lerroa: c = 0 denean, f = 0 da,
edozein direlarik b eta a. Beraz, aurreko taulako lehenengo 4 lerroak bildu
ditugu lerro bakar batean. Modu berean, azkeneko lerroan adierazten da f = 1
izango dela c = b = 1 direnean, a-ren balioa kontuan hartu gabe (aurreko
taulako azkeneko bi lerroak).
24 1. kapitulua: ALJEBRA BOOLEARRA
1.4. Ariketa
Hiru aldagaiko f eta g funtzioen egia-tauletan oinarrituta, idatz itzazu bi
funtzioen adierazpen kanonikoak, minterm-en eta maxterm-en bitartez.
c b a f g
0 0 0 0 1 0
1 0 0 1 1 0
2 0 1 0 1 1
3 0 1 1 0 0
4 1 0 0 1 1
5 1 0 1 1 0
6 1 1 0 0 0
7 1 1 1 1 1
Funtzioaren 1. era kanonikoa adierazteko, 1ekoei dagozkien minterm-ak
batu behar dira. 2. era kanonikoa sortzeko, berriz, funtzioaren 0koei
dagozkien maxterm-ak biderkatu behar dira.
Beraz, minterm-en bidez adierazi nahi badugu f funtzioa, 0, 1, 2, 4, 5 eta 7
minterm-ak kontuan hartuko ditugu:
f = (0, 1, 2, 4, 5, 7) = m0 + m1 + m2 + m4 + m5 + m7 =
= abcabcabcabcabcabc +++++
Eta maxterm-en bidez adierazteko, bakarrik 3 eta 6 maxterm-ak, funtzioak
0 balio duelako bi kasu horietan:
f = (3, 6) = M3 · M6 = )()( abcabc ++++
Prozedura berari jarraitu behar zaio bigarren funtzioaren adierazpen
kanonikoak lortzeko. Beraz,
- minterm-en bidezko adierazpena:
g = (2, 4, 7) = m2 + m4 + m7 = abcabcabc ++
- eta maxterm-en bidezko adierazpena:
g = (0, 1, 3, 5, 6) = M0 · M1 · M3 · M5 · M6 =
= )()()()()( abcabcabcabcabc ++++++++++
Funtzio bakoitzerako lortutako bi adierazpenak, minterm-en eta maxterm-
en bidezkoak, baliokideak dira.
1.3. ARIKETA EBATZIAK 25
1.5. Ariketa
Lor ezazu f(c,b,a) = (1, 2, 4, 6, 7) funtzioaren adierazpen aljebraiko
minimoa Karnaugh-en mapak erabiliz.
Hiru aldagaiko funtzioa denez, dagokion K-mapak 23
= 8 gelaxka izango
ditu, minterm bakoitzeko bat. K-mapa betetzeko, funtzioak hartzen duen
balioa jarriko dugu minterm bakoitzari dagokion gelaxkan. Beraz, bost 1eko
(cba = 001, 010, 100, 110, 111 gelaxketan) eta hiru 0ko (cba = 000, 011, 101
gelaxketan) idatzi behar dira K-mapan. Maiz, K-mapa argiagoa izan dadin,
0koak ez dira idazten.
ba b
c 00 01 11 10
0 0 1 0 1
1 1 0 1 1 c
a
ba b
c 00 01 11 10
0 1 1
1 1 1 1 c
a
K-mapa horretan, 001 minterm-a ezin da sinplifikatu beste minterm batekin
elkartuz; beraz, funtzioaren adierazpen minimoan agertuko da. Gainerakoak,
aldiz, sinplifika daitezke: 010 minterm-a 110 minterm-arekin elkar daiteke,
eta gauza bera egin daiteke 100 eta 110 minterm-ekin, eta 111 eta 110
minterm-ekin. Mapan ageri denez, hiru aldiz erabili dugu 110 minterm-a
elkarketak egiteko. Gogoratu: aljebra boolearrean a + a = a da.
ba b
c 00 01 11 10
0
1 1
1 1 1 1 c
a
Funtzioaren adierazpen minimoa idazteko, lortu ditugun lau elkarketei
dagozkien gaien batuketa egin behar da. Elkarketa bati dagokion gaia
osatzeko, batu diren bi minterm-etan mantentzen diren aldagaiak biderkatu
behar dira, eta aldatzen direnak baztertu. Esaterako, 010 minterm-a ( abc )
eta 110 minterm-a ( abc ) elkartzean --batzean--, ab gaia, sinpleagoa,
lortzen da. Elkarketa guztiekin gauza bera eginez gero, hau izango da
funtzioaren adierazpen minimoa:
26 1. kapitulua: ALJEBRA BOOLEARRA
bcacababcf +++=
Teorian azaldu den moduan, and, or eta not eragileekin edozein funtzio
logiko adieraz daiteke. Horrek ez du galarazten, hala ere, beste eragile
logikoen erabilera funtzio bat adierazteko. Esaterako, sistema digitalak
eraikitzeko asko erabiltzen den beste eragile bat xor funtzioa da (eta haren
ezeztapena, equ funtzioa).
Hala, bi aldagaiko xor ( baba + ) funtzioari dagokion K-mapak bi 1eko
dauzka, 01 eta 10 minterm-etan, diagonalean. Era berean, hiru aldagaiko xor
funtzioak lau 1eko dauzka: 001, 010, 100 eta 111 minterm-etan. Erraz froga
daiteke hori egia-taula baten bidez.
Ariketako K-mapan, esaterako, aurreko lau 1ekoak ageri dira; beraz,
minterm horiek bil daitezke xor funtzioa sortzeko:
ba b
c 00 01 11 10
0 1 1
1 1 1 1 c
a
Azkenik, elkartu gabe geratu den 110 minterm-a minimizatzeko, hiru
aukera daude: goikoarekin (010), eskuinekoarekin (100) eta ezkerrekoarekin
(111). Aukeraren arabera, funtzioaren hiru adierazpen "minimo" baliokide
lortuko ditugu. Esaterako,
ba b
c 00 01 11 10
0 1 1
1 1 1 1 c
a
Hau da: abcbaf += )( edo bccbaf += )(
Laburbilduz: ariketaren lehen partean lortu dugun adierazpena minimoa da,
oinarrizko eragiketa kopurua (and, or eta not) kontuan hartuta. Hala ere,
beste eragile batzuk erabiliz gero (adibidez, xor funtzioa), adierazpen
"minimo" desberdinak lortuko ditugu.
1.3. ARIKETA EBATZIAK 27
1.6. Ariketa
Minimiza ezazu f = (2, 4, 8, 13, 14) + d(0, 5, 10, 12, 15) funtzio logikoa
Karnaugh-en mapa baten bidez.
Funtzioak bost 1eko ditu eta, horrez gain, badaude zehaztu gabeko bost
minterm, hau da, 0kotzat edo 1ekotzat har daitezkeen gaiak (d = don't care).
Bestalde, ez da zehazten funtzioaren aldagai kopurua. Beraz, Karnaugh-en
mapa marraztu ahal izateko, kalkulatu behar da kopuru hori. Ikusten denez,
minterm handiena 15a da; ondorioz, gutxienez 4 aldagaiko funtzioa izango
da (24
= 16 15). Hortaz,
f(d, c, b, a) = (2, 4, 8, 13, 14) + d(0, 5, 10, 12, 15)
4 aldagaiko mapa erabili behar dugu, beraz, eta hor idatzi, batetik,
funtzioaren 1ekoak, eta, bestetik, zehaztu gabeko gaiak ("" edo "x" ikurra
erabiliz):
ba b
dc 00 01 11 10
00 1
01 1
11 1 1
c
d
10 1
a
Has gaitezke funtzioa minimizatzen, minterm-ak elkartuz. Beti bezala,
elkartzeko aukera bakarra (edo, oro har, gutxien) duten minterm-ekin hasiko
gara. Hala, bada, 0010 minterm-a gainerako hiru erpinetako minterm-ekin
elkar daiteke; horretarako, 0000 eta 1010 zehaztu gabeko gaiak 1ekotzat
hartu behar dira.
Era berean, hirugarren errenkadako minterm-ak elkar daitezke, 1100 eta
1111 minterm-ak 1ekotzat hartuz.
Azkenik, elkartu gabe gelditu den minterm bakarra (0100) lehenengo
zutabekoekin elkar daiteke.
28 1. kapitulua: ALJEBRA BOOLEARRA
ba b
dc 00 01 11 10
00 1 acf =1
01 1 abf =3
11 1 1
c
cdf =2
d
10 1
a
Guztira, hiru elkarketa sortu ditugu, lau minterm-ekoak. 4 minterm-eko
elkarketetan, bi aldagai desagertzen dira, eta, ondorioz, funtzioak bi
aldagaiko hiru gai izango ditu:
abcdacfffabcdf ++=++= 321),,,(
Hori ez da, baina, 1eko guztiak elkartzeko era bakarra. Izan ere, f3
elkarketaren ordez, beste hau egin zitekeen, 0101 eta 1100 minterm-ak
1ekotzat hartuz:
ba b
dc 00 01 11 10
00 1
01 1 bcf =4
11 1 1
c
d
10 1
a
Ondorioz, honela ere idatz daiteke funtzioa:
bcdcacfffabcdf ++=++= 421),,,(
1.3. ARIKETA EBATZIAK 29
1.7. Ariketa
abdbcdabcdacdf +++=1 funtzioa sinplifikatzeko asmoz, hainbat
zehaztu gabeko gai erabili dira. Emaitza addcbaf ++=2 izan da. Zein
zehaztu gabeko gai erabili dira sinplifikazioa egiteko?
Bi adierazpideen arteko desberdintasunak ikusteko, haien egia-taulak edo
K-mapak egin eta konpara ditzakegu. Desberdintasunek zehaztu gabeko
gaiak izan behar dute.
Has gaitezen adierazpen minimoarekin: adcdabf ++=2 . K-mapa
betetzeko, funtzioaren 1ekoak lortu behar ditugu; batuketa bat denez, gai
bakoitzari dagozkion 1ekoak.
Lehenengo gaia ab da, bi aldagaikoa; 4 aldagaiko funtzioa denez, gai
horrek lau minterm biltzen ditu (ageri ez diren bi aldagaien konbinazio
bakoitzekobat): abcdabcdabcdabcdab +++= . Gauza bera gertatzen
da funtzioaren beste bi gaiekin: cd eta ad .
Badago beste era bat gai batek
ordezkatzen dituen minterm-ak
ezagutzeko: K-mapan bertan, gaiaren
aldagaiei dagozkien errenkaden eta
zutabeen arteko ebakidurako
minterm-ak dira, hain zuzen ere.
Esaterako, hauek dira ad gaiari
dagozkion lau minterm-ak:
ba b
dc 00 01 11 10
00 1 1 1 1
01 1 1 1 1
11 1 1
c
d
10 1 1
a
<
Prozesu hori errepikatzen badugu gai guztiekin, f2 funtzioaren K-mapa hau
lortuko dugu:
ba b
dc 00 01 11 10
00 1 1 adf =23
01 1 1
11 1 1 1 1
c
dcf =22
d
10 1 baf =21
a
a
d
30 1. kapitulua: ALJEBRA BOOLEARRA
Beraz, f2 funtzioak bederatzi 1eko ditu.
Jatorrizko funtzioarekin, abdbcdabcdacdf +++=1 , gauza bera egin
behar da. Kasu honetan, gaiak 3 edo 4 aldagaikoak dira. 3 aldagaiko gaiei
bina minterm dagozkie; esaterako, abcdabcdbcd += . 4 aldagaiko gaia,
berriz, minterm bakarra da.
Hau da, beraz, f1 funtzioaren K-mapa:
ba b
dc 00 01 11 10
00 1 1 acdf =11
01 1 abcdf =12
11 1 1
c
bcdf =13
d
10 1 abdf =14
a
Lortutako bi mapak konparatzen baditugu, garbi ageri dira funtzioa
minimizatzeko erabili diren zehaztu gabeko gaiak: bigarren mapan hutsak
egonik, lehenengoan 1ekoak dituzten gelaxkak. Hau da, 1ekotzat hartu dira
0101, 1100 eta 1101 minterm-ak.
ba b
dc 00 01 11 10
00 1 1
01 1 1
11 1 1 1 1
c
d
10 1
a
ba b
dc 00 01 11 10
00 1 1
01 1
11 1 1
c
d
10 1
a
Ondorioz, honela zegoen definituta f1 funtzioa:
abdbcdabcdacdf +++=1 + d(5, 12, 13)
1.3. ARIKETA EBATZIAK 31
1.8. Ariketa
Sistema digital askotan, ikusgailu bereziak erabiltzen dira
0tik 9ra arteko zenbakiak erakusteko. Ikusgailu horiek "7
segmentuzko digituak" deitzen dira, argitzen diren zazpi
segmentu (diodo) dituztelako, irudian ageri den moduan.
Adibidez, a = 1 denean, a diodoa pizten da; 0 denean,
berriz, itzali egiten da.
0tik 9rako zenbakiak bitarrez adierazteko, 4 bit behar dira; esate baterako,
X = x3 x2 x1 x0. Zenbakia grafikoki adierazteko, aldiz, 7 biteko kode bat
behar da: a, b, c, d, e, f eta g segmentuetakoa, hain zuzen ere.
Hau egin behar da ariketa honetan: idatzi a, b... eta g funtzio logikoen
adierazpen minimoak, x3, x2, x1, x0 aldagaien arabera (funtzio horiek
gauzatzen dituen zirkuituari "BCD 7 segmentu" deskodegailua deritzo).
a, b, c, d, e, f eta g zazpi funtzio logikoen adierazpenak kalkulatu aurretik,
zenbaki bakoitza nola irudikatzen den aztertu behar dugu. Izan ere, era bat
baino gehiago dago digituak adierazteko, eta horietako bat estandarra da.
Ariketa honetan, hala ere, askatasun handiz jokatuko dugu digituak
irudikatzean. Esaterako, honela adieraz daitezke 10 digituak:
Irudikatze horretan, aukera bikoitza utzi dugu 6, 7 eta 9 digituak
adierazteko:
Beraz, 6 zenbakiaren kasuan, berdin zaigu a segmentuak zein balio hartzen
duen: 0 edo 1. a = 0 bada, aurreko irudiko ezkerreko 6a ikusiko da; a = 1
bada, eskuinekoa. Gauza bera gertatzen da 7 digituaren f segmentuarekin, eta
9 digituaren d segmentuarekin. Aukera bikoitz horiek erabiliko ditugu gero,
funtzioak minimizatzeko orduan.
funtzio
logikoak
x3
x2
x1
x0
a
b
c
d
e
f
g
a
b
c
d
e
f
g
a
b
c
d
e
f g
32 1. kapitulua: ALJEBRA BOOLEARRA
7 segmentuen egia-taulak sortu behar ditugu, hau da, zer segmentu aktibatu
behar diren digitu bakoitzerako. Taulako ezkerraldean, beraz, zenbakien
kode bitarrak jarriko ditugu eta eskuinaldean ikusgailuan aktibatu behar
diren segmentuak. Adibidez, 0 zenbakia irudikatzeko, a, b, c, d, e eta f
segmentuak aktibatu behar dira, eta g segmentua desaktibatu.
Azken ohar bat. 4 bitekin 16 zenbaki desberdin adieraz daitezke, 0tik
15era. Hala ere, 10 digitu hamartar baino ez dago; beraz, sarrerako hainbat
konbinazio (10etik 15era) ez dira inoiz agertuko: zehaztu gabeko gaiak dira.
Hauek dira 7 segmentuen egia-taulak:
x3 x2 x1 x0 a b c d e f g
0 0 0 0 1 1 1 1 1 1 0
0 0 0 1 0 1 1 0 0 0 0
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1
0 1 1 0 0 1 1 1 1 1
0 1 1 1 1 1 1 0 0 0
1 0 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 0 1 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Egia-taula definituta, funtzio bakoitzaren adierazpen minimoa lortuko
dugu; esaterako, K-mapak erabiliz.
Hau da a funtzioaren K-mapa. a funtzioaren 1ekoak eta zehaztu gabeko
gaiak () idatzi ditugu mapan, eta ahal diren elkarketa handienak egin
ditugu, funtzioa minimizatzeko.
x1x0 x1
x3x2 00 01 11 10
00 1 1 1
01 1 1
11
x2
x3
10 1 1
x0
Beraz, 302102 xxxxxxa +++= da.
1.3. ARIKETA EBATZIAK 33
Gainerako funtzioak (b, c, d, e, f eta g) modu berean ateratzen dira.
Gogoratu: zehaztu gabeko gaiak 1ekotzat zein 0kotzat har daitezke,
komenigarriena dena funtzioaren adierazpen aljebraikoa minimizatzeko.
x1x0 x1
x3x2 00 01 11 10
00 1 1 1 1
01 1 1
11
x2
x3
10 1 1
x0
x1x0 x1
x3x2 00 01 11 10
00 1 1 1
01 1 1 1 1
11
x2
x3
10 1 1
x0
20101 xxxxxb ++= 201 xxxc ++=
x1x0 x1
x3x2 00 01 11 10
00 1 1 1
01 1 1
11
x2
x3
10 1
x0
x1x0 x1
x3x2 00 01 11 10
00 1 1
01 1
11
x2
x3
10 1
x0
011201202 xxxxxxxxxd +++= 0102 xxxxe +=
x1x0 x1
x3x2 00 01 11 10
00 1
01 1 1 1
11
x2
x3
10 1 1
x0
x1x0 x1
x3x2
00 01 11 10
00 1 1
01 1 1 1
11
x2
x3
10 1 1
x0
3201 xxxxf ++= 0131212 xxxxxxxg +++=
34 1. kapitulua: ALJEBRA BOOLEARRA
7 funtzioen adierazpen minimoak lortu ditugu. Hala ere, funtzio multzo
baten adierazpen minimoa ez dator bat, askotan, funtzio bakoitzaren
adierazpen minimoen multzoarekin. Aukeran, funtzio batean erabiltzen diren
gaiak besteetan ere erabiltzea interesgarria da, nahiz eta agian gai horiek ez
izan minimoak beste funtzioetan. Hala egiten denean, funtzio guztiak
osatzeko (eta gero eraikitzeko) behar den gai kopurua txikiagoa izango da.
1.4. ARIKETAK 35
1.4. ARIKETAK
1.1. Aljebra boolearraren axiomak eta teoremak erabiliz, sinplifika itzazu honako
adierazpen hauek:
(1) cbacbcacbabaf ++++=
(2) )()( cbabag ++=
(3) h = a (b + c (b + a))
1.2. Froga itzazu berdintza hauek, batetik, egia-taulak erabiliz, eta, bestetik, aljebra
boolearraren axiomak eta teoremak erabiliz:
(1) cabcabacba +=++
(2) accbcbacab +=+ )()(
(3) )()()()()( cabacbcaba ++=+++
1.3. Adieraz itzazu honako funtzio hauen osagarriak, eta minimizatu adierazpenak:
(1) dcbcbaf +++= )(
(2) )( edccaag +++=
(3) )( dbcbah ++=
1.4. Lor itzazu honako funtzio hauen adierazpen minimoak Karnaugh-en mapak
erabiliz.
(1) f(c, b, a) = )( bacabbaabc ++++
(2) f(d, c, b, a) = dbacbacbada +++
(3) f(d, c, b, a) = (0, 13, 14, 15) + d(1, 2, 3, 9, 10, 11)
(4) f(d, c, b, a) = (1, 3, 5, 8, 9, 11, 15) + d(2, 13)
1.5. Minimiza itzazu K-mapen bidez adierazitako bi funtzio hauek.
ba b
dc 00 01 11 10
00 0 1 0 0
01 1 1 1
11 1 0 0 0
c
d
10 1 0 0 0
a
ba b
dc 00 01 11 10
00 1 0 1 1
01 0 1 0 0
11 0 0 0 0
c
d
10 1 0 1 1
a
36 1. kapitulua: ALJEBRA BOOLEARRA
1.6. Bi funtzio logikoen egia-taulak kontuan hartuz, idatzi funtzio bakoitzaren era
kanonikoa; gero, minimizatu adierazpenak K-mapak erabiliz.
d c b a f c b a g
0 0 0 1 0 0 0 1
0 0 1 0 0 0 0 1 0
0 0 1 1 1 0 1 0 1
0 1 0 1 1 0
1 0 0 0 1 1 0 0 1
1 0 0 1 1 1 0 1 1
1 1 0 1 1 1 0 0
1 0 1 1 0 1 1 1 1
1 1 0 0
1 1 0 1 0
1 1 1 1 1
1.7. Irudiko zirkuituaren sarrerek --x3, x2, x1, x0-- 4 biteko zenbaki arrunt bat
adierazten dute, bitar hutsez. Z irteerak, berriz, sarrerako zenbakia 2ren
berretura den ala ez adierazi beharko du. Idatz ezazu funtzioaren egia-taula eta
lor ezazu adierazpen minimoa Karnaugh-en mapak erabiliz.
Errepikatu aurrekoa, baina murriztapen hau kontuan hartuta: sarrerako
zenbakia digitu hamartar bat da: 0tik 9ra.
1.8. 4 biteko kodeak --X (x3, x2, x1, x0)-- prozesatzen dira sistema digital batean,
eta, emaitza gisa, bit bateko hiru funtzio sortzen dira: BAT, ZERO eta
BERDIN izenekoak. BAT funtzioa aktibatzen da sarrera-kodearen 1ekoen
kopurua 0koena baino handiagoa denean; ZERO aktibatzen da 0koen kopurua
1ekoena baino handiagoa denean; eta BERDIN bi kopuruak berdinak
direnean.
Idatz itzazu hiru funtzio horien egia-taulak, eta eman haien adierazpen
aljebraiko minimoak.
1.9. Sistema digital batek detektatu behar du sarrerako zenbakiak (4 bitekoak)
lehenak diren ala ez. Idatzi funtzio horri dagokion egia-taula eta eman
funtzioaren adierazpen minimoa.
2ren
berretura
x3
x2
x1
x0
ZSistema digitalen diseinu-hastapenak: Oinarrizko kontzeptuak eta adibideak