Funtzio boolear

Matematika arloan funtzio boolearra funtzio bat da non bere domeinua 0 edo 1 balio bitarrek ("faltsua" edo "egiazkoa" hurrenez hurren) osatzen duten.

Formalki, ƒ : Bⁿ → B motako funtzioak dira, non B = {0,1} eta n zenbaki oso ez negatiboa den, funtzioaren aridadea alegia.

Adierazpideak

Funtzio logiko bat modu desberdinetan adieraz daiteke, besteak beste honako hauek azpimarra ditzakegu:

Aljebraikoa
Egi-taula bidezkoa
Zenbakizkoa
Grafikoa

Adierazpide bat edo bestea aukeratzea, ikusiko dugun bezala, kasu bakoitzaren behar zehatzen arabera egingo da.

Aljebraikoa

Eragiketa aljebraikoak egiten direnean erabiltzen da. Jarraian, adibide baten bidez, hiru aldagaiko funtzio beraren adierazpide aljebraiko ezberdinak agertzen dira.

a) F = [(A + BC’)’ + ABC]’ + AB’C

b) F = A’BC’ + AB’C’ + AB’C + ABC’

c) F = (A + B + C)(A + B + C’)(A + B’ + C’)(A’ + B’ + C’)

d) F = BC’ + AB’

e) F = (A + B)(B’ + C’)

f) F = [(BC’)’(CB)´ (AB’)’]’

g) F = [(A + B)’ + (B’ + C’)’]’

a) adierazpenak planteatutako problema logiko batean izan dezake jatorria edo zehaztapen batzuk lengoaia aljebraikora itzulitakoan sor daiteke. b) eta c) adierazpenei kanonikoak esaten zaie: b) adierazpenari biderketen batuketa (sum-of-products, SOP, ingelesez), eta c) adierazpenari batuketen biderketa (product-of-sums, POS, ingelesez); haien ezaugarri nagusia da batuketa edo biderketa bakoitzean aldagai guztiak (A, B eta C) ageri direla. d) eta e) funtzio sinplifikatuak dira, hau da, funtzioen adierazpen minimoa. Azken bi adierazpenek berezitasun bat dute, f) adierazpenak soilik NAND funtzioak erabiltzen ditu, eta g) adierazpenak NOR funtzioak.

Egia-taula bidez

{\begin{array}{|c|c|c|c|}\hline A&B&C&F(A,B,C)\\\hline 0&0&0&0\\0&0&1&0\\0&1&0&1\\0&1&1&0\\1&0&0&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\\\hline \end{array}}

Egia-taula batek funtzio logikoaren balio posible guztiak definitzen ditu funtzioaren aldagaien balio-konbinazio guztietarako. n aldagaiko funtzio baten konbinazio posibleen kopurua 2ⁿ izango da. Ikusi dugun bezala funtzio logiko bat adierazpen aljebraiko ezberdinekin adieraz daiteke, baina egia-taula bakarra du. Ondoko taulak aurreko ataleko funtzio logikoari dagokio.

Modu errazena egia-taularen eta adierazpen aljebraikoaren arteko baliokidetasuna ikusteko, azken hau era kanonikoan adieraztea da. Horrela, biderketen batuketaz adierazitako era kanoniko honek (forma kanoniko disjuntiboa)

F = A’BC’ + AB’C’ + AB’C + ABC’

adierazten digu funtzioaren balioa 1 izango dela bere batugairen batek 1 balioa hartzen duenean. Adibide honetan lau konbinaziotan gertatuko da hau (A’BC’ batugaian 010 daukagunean, AB’C’-n 100 dagoenean, AB’C batugaian 101 eta ABC’-n 110) eta gainerako konbinaziotan 0 izango da. Funtzioa batuketen biderketa era kanonikoan (edo forma kanoniko konjuntiboa) adierazita badago antzera gertatzen da, baina honelakotan kontuan izan behar dena da funtzioa 0 izango dela adierazpeneko biderketaren bat 0 denean.

Funtzio sinplifikatua abiapuntu hartuta egia-taula lortzea ere erraza da, baina ez alderantziz.

Zenbakizkoa

Zenbakizko adierazpidea espresio kanonikoak adierazteko modu sinplifikatua da. Ezeztatu gabe dagoen aldagaia 1 balioaz ordezkatzen badugu eta ezeztatuta dagoena 0 balioaz, terminoa batuketa nahiz biderketa izan, konbinazioaren balio bitarraren baliokidea den zenbaki hamartar baten bidez adieraz daiteke. Adibidez, honako termino kanoniko hauek era honetara adieraziko dira (kontuan izan A pisu handienekoa dela eta D pisu txikienekoa):

AB’CD = 1011₂ = 11₁₀

A’ + B + C’ + D’ = 0100₂ = 4₁₀

Funtzio kanoniko bat biderketen batuketa modura adierazteko Σ_n (sigma) ikurra erabiliko dugu eta batuketen biderketa modura adierazteko Π_n (pi), non n aldagai kopurua izango den. Honela, aurreko ataleko egia-taulari dagokion zenbakizko adierazpena honela geratuko da:

F = Σ₃(2, 4, 5, 6) = Π₃(0, 1, 3, 7)

Matematikoki frogatzen da, funtzio baten edozein i gairentzat honako ekuazio hau betetzen dela:

F = [Σ_n(i)]' = Π_n(2ⁿ-1-i )

Adibide gisa berdintasun hau erabil daiteke aurreko adibideko biderketen batuketatik abiatuta, batuketen biderketa lortzeko:

F = Σ₃(2, 4, 5, 6) = [Σ₃(2, 4, 5, 6)]' ' = [Σ₃(0, 1, 3, 7)]' = Π₃(0, 1, 3, 7)

Grafikoa

Adierazpide grafikoa zirkuitutan eta eskema elektronikotan erabiltzen dena da. Honako irudi honetan bi funtzio aljebraiko adierazten dira grafikoki, bat nonrmalizatu gabeko ikurrekin, goialdean, eta bestea normalizatuekin, behealdean. (ikusi ate logikoen sinboloak)

Sinplifikazio metodoak

Funtzio logiko bat sinplifikatzea bere adierazpen minimoa lortzea da. Funtzio logiko bat eraiki behar denean, aurretik sinplifikatu egiten da zirkuituaren konplexutasuna murrizteko.

Jarraian, funtzio logiko bat sinplifikatzeko modu usuenak agertzen dira.

Aljebraikoa

Sinplifikatzeko metodo hau erabiliko bada, booleren aljebraren propietate eta teorema guztiak ezagutzeaz gain, esperientziaz lortzen den trebezi logiko-matematikoa ere izan behar da.

Adibide gisa honako funtzio hau sinplifikatuko da:

F = A’C’ + ABC + BC’ + A’B’C + A’BC

Batugaiak aztertzen baditugu, ikus dezakegu batetik 2. eta 5. batugaietan eta bestetik 4. eta 5. batugaietan gai komunak daudela eta ondorioz sinplifikagarriak direla:

F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)

Kontuan izan 5. batugaia birritan hartu dela, horrela eginda emaitza aldatzen ez baita. Orain A + A´ = 1 eta A . 1 = A propietateak aplikatuz honela geratzen da:

F = A’C’ + BC’ + BC + A’C

Prozesua berriz errepikatzean,

F = A’(C’ + C) + B(C’ + C) = A’ + B

Funtzioak ez dira beti aurreko hori bezain errazak sinplifikatzen. Gehienetan metodo aljebraikoa ez da erosoa adituak ez direnentzat; behin ekuazioa sinplifikatuta, zalantza handiak egon daitezke lortu dena sinplifikazio maximoa den ala ez.

Karnaugh-en mapa

Metodo hau 2ⁿ gelaxkaz osatutako diagramak egitean datza, n aldagai kopurua izanik. Gelaxka bakoitzak konbinazio posibletako bat adierazten du, eta aldameneko gelaxka batera pasatzerakoan, bai horizontalean bai bertikalean, aldagai bakarra aldatzen da, berau forma ezeztatura edo forma zuzenera pasatzeko.

Metodo hau gehienez lau aldagaiko funtzioak sinplifikatzeko erabiltzen da. Aldagai kopuru handiagoko funtzioak sinplifikatzeko beste metodo batzuk erabiltzen dira, zenbakizkoa adibidez. Jarraian diagramak edo Karnaugh-en mapak ikus ditzakegu, bi, hiru eta lau aldagaikoak.

Bi, hiru eta lau aldagaiko Karnaugh-en mapak

Ohikoa da gelaxka bakoitza zenbaki batez zenbatzea funtzio kanonikoa errazago adierazteko. Zenbaki hori gelaxkak adierazten duen termino kanonikoari dagokion zenbaki hamartarra da.

Funtzio logiko bat Karnaugh-en metodoa erabiliz sinplifikatzeko honako urrats hauei jarraituko zaie:

1. Diagrama edo mapa marrazten da sinplifikatu nahi den funtzioaren aldagai kopurua kontuan hartuta.

2. Batekoak jartzen dira funtzioaren parte diren termino kanonikoen gelaxkatan.

3. Aldameneko gelaxkatan dauden batekoak multzotan biltzen dira honako arau hauek errespetatuz:

a) Bi gelaxka aldamenekoak dira haien arteko diferentzia aldagai bakar batean baldin badago.

b) Multzo bakoitzean ahalik eta bateko kopuru handiena sartu behar da, betiere kopuru hori biren berretura bada (1, 2, 4, ...)

c) Multzoak gainjar daitezke, hau da, gelaxkak (batekoak) multzo batean baino gehiagotan egon daitezke.

d) Ahalik eta multzo kopuru txikiena lortu behar da bateko guztiak harrapatuz.

4. Funtzio sinplifikatuaren termino kopurua bat etorriko da diagramak duen multzo kopuruarekin. Termino bakoitza multzoan egoeraz aldatzen diren aldagaiak kenduz lortuko da.

Adibide gisa funtzio beraren bi sinplifikazio egingo dira haien forma kanonikoa oinarritzat hartuz:

F = Σ₃(0,2,3,4,7) = Π₃(1,2,6)

Aurreko urratsak jarraituz, funtzio bakoitzaren diagrama honela geratuko da:

Hiru aldagaiko funtzio baten sinplifikazioa

Funtzio sinplifikatuak hiru batugai izango ditu kasu batean eta bi biderkagai bestean. Biderketen baturari dagokion mapan erreparatzen badugu ikus dezakegu lehenengo multzoan A aldagaia dela aldatzen dena (0 gelaxkan forma ukatuan dago eta 4 gelaxkan zuzenean), 2. multzoan berriz, C da aldatzen den aldagaia eta 3.ean berriz ere A da. Beraz, ekuazio sinplifikatua honako hau izango da:

F = B’C’ + A’B + BC

Baturen biderketari dagokion mapan berdintsu eginez, hauxe geratuko da:

F = (B + C’)(A’ + B’ + C)

Quine-McCluskey-en zenbakia

Quine-McCluskey-en algoritmoa baliagarria da edozein aldagai kopuruko funtzioen sinplifikazioa egiteko.Funtzio sinplifikatuak behar dituzten aplikazio informatikoetan erabiltzen dena da.

Jarraian metodo honetan eman beharreko urratsak adierazten dira adibide batean oinarrituta.

1. Sinplifikatu beharreko funtzioa biderketen batura forma kanonikoan adierazten da.

Sinplifikatu beharreko funtzioa:

F = S₄ (0,1,2,3,5,9,11,12,13,15)

2. Taula bat osatu behar da konbinazioaren balio hamartarrarekin, aldagaien egoerarekin eta indizearekin (aldagaien egoerak dituen bateko kopurua).

Konb.	Egoera	Indizea
0	0000	0
1	0001	1
2	0010	1
3	0011	2
5	0101	2
9	1001	2
11	1011	3
12	1100	2
13	1101	3
15	1111	4

3. Aldagai bakarrean ezberdintzen diren konbinazioak elkartzen dira eta aldagai horren egoeran beheko gidoia (_) jartzen da. Erabilitako konbinazioak ixarekin (X) markatzen dira.

4. Prozesua errepikatzen da behar adina aldiz, eta egoera berdinak kentzen doaz.

5. Taula bat osatzen da bukaerako konbinazioekin eta multzokatu gabekoekin. Errenkada gisa bukaerako konbinazioak eta multzokatu gabeak hartzen dira eta zutabe bezala konbinazio horiei dagozkien balio hamartarrak. Konbinazio baten balio hamartarra duen gelaxka bakoitza ixa batekin markatzen da. Jarraian, ixa bakarra duten zutabeetan erreparatzen dugu; haien konbinazioak ezinbestekoak dira. Azkenik hautatu gabeko balio hamartarren konbinazioak hartzen dira, kontuan izanik konbinazio hauen balio hamartarrak ez direla beste konbinazio batzuetan hartuak izan. Funtzio sinplifikatua ezinbesteko konbinazioek eta azken hauek osatzen dutena da.

Zeharo zehaztu gabeko funtzioak

Orain arte ikusi diren funtzio guztiak balio logiko bat, 0 edo 1, dute esleituta konbinazio bakoitzeko. Funtzio horiei osoak edo zeharo zehaztuak esaten zaie. Badira funtzioak konbinazio batzuk definitu gabe dituztenak, hauei zeharo zehaztu gabeko funtzioak deritze. Egoera hau honako bi arrazoi hauengatik gerta daiteke:

Sarrerako konbinazioa ez delako existitzen, eta beraz, irteerako balioa 0 nahiz 1 izan daiteke.
Sarrerako konbinazio batzuetan sistema logikoaren irteera inhibituta dago, eta ondorioz, berdin da zein den bere balioa.

Zeharo zehaztu gabeko funtzio baten egi-taulan axola gabeko gaiak ixa (X) baten bidez adierazten dira. Forma kanonikoa adierazteko zehaztu gabeko gaiak bereizten dira φ ikurra erabiliz.

Zehaztu gabeko funtzioak sinplifikatzeko orduan, axola gabeko gaiak "komodin" gisa erabil daitezke multzoak egiterakoan, hau da, multzo handiagoa lortzearren batekoa interesatzen bazaigu horrela hartuko dugu, bestela 0 balioa esleituko diogu.

Minterm

n aldagaiko funtzio boolear batean, n aldagaietako bakoitza behin bakarrik (ukatuta ala ukatu gabe) ageri den biderketa boolearrari minterma esaten zaio. Hau da, minterma n aldagaiko adierazpen logikoa da, non eragileak biderketa logikoa (AND) eta ukapena (NOT) izan daitezkeen. Adibidez, hiru aldagaiko (a, b eta c) funtzio boolear batentzat abc, ab'c eta abc' minterm adibideak dira.

Maxterm

Maxterm-a n aldagaiko adierazpen logikoa da non eragileak batura logikoa (OR) eta ukapena (NOT) izango diren. Adibidez, honako gai kanoniko hauek maxterm-ak dira:

a + b' + c
a' + b + c

Ikus gainera

Kanpo estekak

Datuak: Q942353