Funtzio boolear

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.

${\displaystyle {\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.

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)

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)

Bi funtzio logikoen adierazpen grafikoa

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.

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

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

Konbinazioen multzokaketa

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

Kobinazioen multzokaketa berria

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.