DIGITÁLIS TECHNIKA I
LOGIKAI (BOOLE-) FÜGGVÉNYEK
Dr. Pıdör Bálint
1. Logikai függvények: alapfogalmak
BMF KVK Mikroelektronikai és Technológia Intézet
2. Kétváltozós logikai függvények (összefoglaló)
3. ELİADÁS: LOGIKAI FÜGGVÉNYEK
3. Határozott és nem teljesen határozott logikai függvények és kombinációs hálózatok. 4. Logikai függvények kanonikus algebrai alakjai, diszjunktív és konjunktív normálalakok.
2008/2009 tanév 1. félév
5. Minterm és maxterm fogalma, alkalmazások. 1
MI A BOOLE (LOGIKAI) FÜGGVÉNY? A Boole algebra egy- és kétváltozós mőveletei egyúttal egy- és kétváltozós függvényeknek is tekinthetık. A függvény fogalma a változók számának kiterjesztésével általánosítható. n-változós Boole függvény vagy logikai függvény
2
LOGIKAI FÜGGVÉNYEK ÉS KOMBINÁCIÓS HÁLÓZATOK Minden egyes logikai függvényhez megadható egy kombinációs hálózat, illetve minden egyes logikai feladathoz és kombinációs hálózathoz tartozik egy logikai függvény. A logikai függvények segítségével egyértelmően leírható a kombinációs hálózatok mőködése.
Z = f(X1, X2, .........Xn) A Z függı változó logikai értékét az n db Xi független változó értékei határozzák meg.
Ezért célszerő, ha a logikai függvények tulajdonságaival részletesebben megismerkedünk.
3
4
EGYVÁLTOZÓS LOGIKAI FÜGGVÉNYEK Egy változó esetén négy különbözı logikai függvénykapcsolat állhat fenn. Egy- és kétváltozós logikai függvények: részletes ismertetés
5
A fo1(A) f11(A) f21(A) f31(A) ————————————————————— 0 0 0 1 1 1 0 1 0 1 ————————————————————— Az egyes függvényeket fin jelöli. Az i index annak a bináris számnak decimális értéke melyet az oszlopba írt logikai értékek mint bináris számjegyek alkotnak. _ Két logikai konstans 0, 1, és két „igazi” függvény A,6 A.
AZ fo1 FÜGGVÉNY
AZ f11 FÜGGVÉNY
A fo1 ———— 0 0 1 0 ————
A f11 ———— 0 0 1 1 ————
Az F = fo1(A) = 0 függvény logikailag az A és F esemény között logikailag az azt a kapcsolatot írja le, ami szerint az F esemény az A eseménytıl függetlenül sohasem következik be. Ekkor F logikai konstans.
Az F = f11(A) = A függvény logikailag azt fejezi ki, hogy F értéke mindig megegyezik A értékével, vagyis az A és F esemény egyszerre következik be. 7
AZ f21 FÜGGVÉNY
8
AZ f31 FÜGGVÉNY
A f21 ———— 0 1 1 0 ————
A f31 ———— 0 1 1 1 ———— Az F = f31(A) = 1 függvénykapcsolat azt fejezi ki, hogy az F esemény az A eseménytıl függetlenül mindig bekövetkezik.
Az F = f21(A) = Ā függvénykapcsolat a tagadás (negáció) mőveletét írja le, F = Ā. Szokásos elnevezése negálás, invertálás, komplementálás.
Ekkor F logikai konstans 9
KÉTVÁLTOZÓS LOGIKAI FÜGGVÉNYEK
10
KÉTVÁLTOZÓS LOGIKAI FÜGGVÉNYEK Két változó esetén a bemeneti kombinációk száma 22 = 4, és így a lehetséges kétváltozós függvények száma 24 = 16. Mindegyik függvény a változókra nézve egy-egy mőveletet vagy összetett mőveletet ír le. Általános esetben, n változó esetén a bemeneti kombinációk száma k = 2n, és a lehetséges nváltozós logikai függvények száma 2k, rendkívül gyorsan (exponenciálisan) nı.
Kétváltozós logikai függvények osztályozása, Boole algebrai alakja és tulajdonságai
11
12
Hányféle „n” változós Boole függvény van?
KÉTVÁLTOZÓS LOGIKAI FÜGGVÉNYEK
A kétargumentumos mőveletekbıl (a triviális eseteket is beleértve)
2 2 = 16 2
Ez itt az argumentumok száma
különbözı volt. Az „n” változós függvényekbıl
22 különbözı van.
n
n=3 esetén 256 n=4 esetén 65 536 n=5 esetén 4 294 967 296 A függvények száma a változók számával igen gyorsan növekszik 13
KÉTVÁLTOZÓS FÜGGVÉNYEK CSOPORTOSÍTÁSA
MEGJEGYZÉS A JELÖLÉSEKRİL Az elıírt jegyzetek (Zsom illetve Rımer féle) azt a jelölést alkalmazzák, mikor az i index annak a bináris számnak decimális értéke melyet az oszlopba írt logikai értékek mint bináris számjegyek alkotnak, a legfelsıt tekintve a legkisebb helyértéknek. Lehet ennek fordítottját is használni (a legalsó a legkisebb helyérték), ezt használja pl. az Arató-féle könyv (Mőegyetem), illetve az említett web-es anyag (BMF Székesfehérvár). 15
LOGIKAI ÁLLANDÓK A B fo2 f12 f22.... f142 f152 ——————————————— 0 0 0 1 0 ..... 0 1 0 1 0 0 1 ..... 1 1 1 0 0 0 0 ..... 1 1 1 1 0 0 0 ..... 1 1 ———————————————
A B fo2 f12 f22..... f82 ..... f142 f152 ————————————————————— 0 0 0 1 0 ..... 0 ..... 0 1 0 1 0 0 1 ..... 0 ..... 1 1 1 0 0 0 0 ..... 0 ..... 1 1 1 1 0 0 0 ..... 1 ..... 1 1 ————————————————————— Az egyes függvényeket fin jelöli. Az i index annak a bináris számnak decimális értéke melyet az oszlopba írt logikai értékek mint bináris számjegyek alkotnak, a legfelsıt tekintve a legkisebb helyértéknek. 14 Ld. Rımer 9. old.,illetve Zsom (I) 71. old.
Az egymást 15-re kiegészítı indexő függvények egymás negáltjai.
fo2 null-függvény, váltózó értékétıl függetlenül mindig 0 értékő. f152 egység-függvény, váltózó értékétıl függetlenül mindig 1 értékő. 17 Lényegében logikai konstansokról van szó.
Függvény neve f(A,B) —————————————————————— Logikai konstansok 0, 1 —
—
Egyváltozós függvények
A, A, B, B
AND, OR, NAND, NOR
A•B, A+B, A•B, A+B
—— ——— —
—
——
XOR (A⊕B ), XNOR (AB) A B+A B, A B+A B INHIBÍCIÓ (TILTÁS) A ⊃ B, B ⊃ A IMPLIKÁCIÓ (KÖVETKEZTETÉS) A → B, B → B
16
EGYARGUMENTUMOS FÜGGVÉNYEK A táblázatból
f122 (A,B) = A —
f32 (A,B) = A f102 (A,B) = B —
f52 (A,B) = B
Ezek nem valódi (kétváltozós) függvények, az egyes változók ponált vagy negált értékeit állítják elı. Lényegében egyargumentumos függvények. Az i és 15-i indexő függvények egymás negáltjai.
18
LOGIC FUNCTIONS: AND, OR, NAND, NOR
KÉTVÁLTOZÓS FÜGGVÉNYEK A B
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10 f11 f12 f13
f14 f15
0 0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
01
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
10
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
11
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
ÉS
VAGY
VAGY-NEM
ÉS-NEM
1
A
B
B
A
A B f12 ..... f72..... f82 ..... f142 ——————————————— 0 0 1 ..... 1 ..... 0 ..... 0 0 1 0 ..... 1 ..... 0 ..... 1 1 0 0 ..... 1 ..... 0 ..... 1 1 1 0 ..... 0 ..... 1 ..... 1 ——————————————— ——
A+B
——
AB
AB
A+B
NOR NAND AND
Egyargumentumos
OR
Egyargumentumos Logikai konstansok 19
NAND, NOR: UNIVERZÁLIS MŐVEKLETEK
NEM-VAGY
NEM-ÉS
ÉS
VAGY
20
NAND KAPU MINT UNIVERZÁLIS ELEM: TTL
A NAND és az NOR univerzális mőveletek: mind a
NAND kapus univerzális rendszer a gyakorlatban elterjedt transistor-transistor-logic (TTL) logikai
NAND mind a NOR kapukból bármilyen logikai kapcsolat, illetve rendszer megvalósítható.
kapurendszer, mely szilícium bipoláris tranzisztor, illetve integrált áramkör technológián alapul.
Elvileg elég csak NAND vagy csak NOR kapukat tartatni, azokból bármilyen logikai áramkör felépíthetı. Ennek óriási a gyakorlati jelentısége. Néhány példa erre már szerepelt, alább megint láthatók:
21
NOR KAPU MINT UNIVERZÁLIS ELEM
22
KÉTVÁLTOZÓS FÜGGVÉNYEK: ANTIVALENCIA, EKVIVALENCIA Függvény neve f(A,B) —————————————————————— Logikai konstansok 0, 1
A NOR kapu is elterjedt mint univerzális elem. Gyakorlati példa az emitter-coupled-logic (ECL) logikai áramkörrendszer, illetve a CMOS
—
—
Egyváltozós függvények
A, A, B, B
AND, OR, NAND, NOR
A•B, A+B, A•B, A+B
(complementary metal-oxide-semiconductor)
—— ———
technológiájú (integrált) áramkörök, melyek
—
alapeleme a szilícium térvezérléső tranzisztor.
—
——
XOR (A⊕B ), XNOR (AB) A B+A B, A B+A B
23
INHIBÍCIÓ (TILTÁS) A ⊃ B, B ⊃ A IMPLIKÁCIÓ (KÖVETKEZTETÉS) A → B, B → B
24
ANTIVALENCIA ÉS EKVIVALENCIA
A B f62 f92 —————— 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 ——————
Antivalencia (más neve kizáró vagy) XOR (A ⊕ B ), Ekvivalencia XNOR (A B) Angolul:
ANTIVALENCIA (XOR) XNOR EKVIVALENCIA (XNOR)
A két függvény egymás ellentetje (negáltja) ____ A⊕B = AB —
antivalency (exclusive-or) equivalency vagy coincidence
—
XOR
f62 = A⊕B = A B+A B,
XNOR
f92 = AB = A B+A B
——
25
ANTIVALENCIA, EXCLUSIVE-OR
26
EKVIVALENCIA, EXCLUSIVE-NOR
A B f62 ———— _ _ 0 0 1 f62 = A B + A B 0 1 1 1 0 1 szokásos jelölése: 1 1 0 ———— f62 = A ⊕ B
A B f92 ———— __ 0 0 1 f92 = AB + AB 0 1 0 1 0 0 szokásos jelölése: 1 1 1 ———— f92 = A B
ANTIVALENCIA más néven KIZÁRÓ-VAGY (EXCLUSIVE-OR), a függvény akkor 1, ha vagy az egyik, vagy a másik változó 1, és 0, ha mindkét 27 változó egyszerre 0 vagy 1.
EKVIVALENCIA (EXCLUSIVE-NOR), a függvény akkor 1, ha mindkét változó egyszerre 0 vagy 1, és akkor 0 ha az egyik, vagy a másik változó 1.
KIZÁRÓ-VAGY
28
ANTIVALENCIA
Az EXCLUSIVE-OR megvalósítása történhet a definiáló Boole algebrai egyenlet alapján NEM, ÉS és VAGY kapukkal, vagy megfelelı átalakítás után NAND kapukkal mint univerzális elemmel. A TTL áramköri családban van külön kész EXCLUSIVE-OR kapu is.
29
A B f62 Az igazságtáblázat szerint ————— a f62 = A ⊕ B mővelet egy0 0 1 ben megvalósítja a két bites 0 1 1 maradéknélküli bináris össze1 0 1 adás aritmetikai mőveletét 1 1 0 (”fél összeadó”). ————— Az antivalencia kapu felfogható egy-bites ”digitális komparátor”-nak is, ha a bemenetére érkezı két bit azonos értékő, a kimeneten 0 jelet ad, ha eltérı, 30 akkor 1-et.
EXCLUSIVE-OR NEM, ÉS, VAGY KAPUS MEGVALÓSÍTÁSA
EXCLUSIVE-OR, ANTIVALENCIA —
—
A⊕B = A B+A B, ⇒ Az XOR megvalósítja két bit átvitel nélküli összeadását (fél-összeadó). ⇒ Funkcionál mint vezérelt inverter (vezérlıjel: A, feldolgozandó jel: B). ⇒ Funkcionál mint ”páratlanság-vizsgáló”: ha páratlan számú bemeneten van 1, akkor a kimenet 1, ellenkezı esetben 0. Itt már implikáltuk az XOR kiterjesztését több bementre (értelmezés az MSz szerint, részletes magyarázat Zsom I, 76-77 old.!) 31
EXCLUSIVE-OR (ANTIVALENCIA) NAND KAPUS MEGVALÓSÍTÁSA
1. Az XOR a Boole-egyenlet szerint megvalósítása. 2. Az XOR szabványos rajzjele. 3. Az XOR régebbi rajzjele. 32
EXCLUSIVE-NOR: EKVIVALENCIA ——
AB = A B+A B
—
—
——————— ——— ——— — —
A⊕B = A B+A B = (A B)•(A B)
Itt feltételezzük, hogy a negált változók rendelkezésre állnak.
33
EKVIVALENCIA (XNOR) NEM, ÉS, VAGY KAPUS MEGVALÓSÍTÁSA
1. Az XNOR a Boole-egyenlet szerinti megvalósítása. 2. Az XNOR (EKVIVALENCIA) szabványos rajzjele. 3. Az XNOR régebbi rajzjele. 35
Az igazságtáblázat szerint az XNOR az XOR negáltja. Több változóra való kiterjesztéskor az XNOR függvénynek többféle értelmezése is elıfordul! Pl. az MSZ szerint három változó esetén a függvény értéke csak a 0 0 0 és az 1 1 1 bemeneti kombinációkra 1, az összes többire 0. A másik szokásos értelmezés esetén a függvény értéke akkor 1, ha a változók között páros számú 1 van. 34
EXCLUSIVE-NOR (EKVIVALENCIA) NAND KAPUS MEGVALÓSÍTÁSA
A NAND kapus realizálás a De Morgan azonosságok felhasználásával végzett átalakítások eredménye. 36
ANTIVALENCIA (XOR) REALIZÁLÁSA NOR KAPUKKAL
NOR KAPUS REALIZÁLÁSOK Természetesen mind az ANTIVALENCIA (XOR) mind az EKVIVALENCIA (XNOR) megvalósítható kizárólag NOR kapuk felhasználásával.
37
EKVIVALENCIA (XNOR) REALIZÁLÁSA NOR KAPUKKAL
38
KÉTVÁLTOZÓS FÜGGVÉNYEK: INHIBÍCIÓ ÉS IMPLIKÁCIÓ Függvény neve f(A,B) —————————————————————— Logikai konstansok 0, 1 —
—
Egyváltozós függvények
A, A, B, B
AND, OR, NAND, NOR
A•B, A+B, A•B, A+B
—— ——— —
—
——
XOR (A⊕B ), XNOR (AB) A B+A B, A B+A B
39
INHIBÍCIÓ (TILTÁS) IMPLIKÁCIÓ (KÖVETKEZTETLÉS)
40
INHIBÍCIÓ, TILTÁS
Ezt a négy függvényt illetve mőveletet itt csak megemlítjük, bıvebb anyag a jegyzetekben található. Szerepük inkább a formális logikában van. A négy függvény: A⊃B B⊃A A→B B→B
INHIBÍCIÓ (TILTÁS) A ⊃ B, B ⊃ A IMPLIKÁCIÓ (KÖVETKEZTETÉS) A → B, B → B
A TILTJA B-T B TILTJA A-T HA A AKKOR B IS HA B AKKOR A IS
A B f22 f42 —————— 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 —————— —
A TILTJA B-T
f22 = A ⊃ B = A B
B TILTJA A-T
f42 = B ⊃ A = A B
—
41
42
KÉTVÁLTOZÓS FÜGGVÉNYEK ÖSSZEFOGLALÁSA
IMPLIKÁCIÓ, KÖVETKEZTETÉS
Függvény neve f(A,B) —————————————————————— Logikai konstansok 0, 1
A B f112 f132 ——————— 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 ———————
—
—
Egyváltozós függvények
A, A, B, B
AND, OR, NAND, NOR
A•B, A+B, A•B, A+B
—— ——— —
—
HA A AKKOR B IS
f112 = A → B = A + B
HA B AKKOR A IS
f132 = B → A = A + B
—
——
XOR (A⊕B ), XNOR (AB) A B+A B, A B+A B
—
43
A KÉTVÁLTOZÓS FÜGGVÉNYEK ILLETVE BOOLE MŐVELETEK ÖSSZEFOGLALÁSA
INHIBÍCIÓ (TILTÁS) A ⊃ B, B ⊃ A IMPLIKÁCIÓ (KÖVETKEZTETÉS) A → B, B → B
44
LOGIKAI FÜGGVÉNYEK KANONIKUS ALGEBRAI ALAKJAI
A 16 lehetséges, kétargumentumos Boole mővelet illetve kétváltozós függvény közül 6 triviálisnak tekinthetı, amelyek közül kettı állandó (logikai konstans), négy pedig egyváltozós. Az utóbbiak közül kettı a negáció. A 10 nem triviális függvény közül elsısorban kettıt (ÉS, VAGY), illetve negáltjaikat (NEM-ÉS,NAND és NEM-VAGY,NOR), valamint az ANTIVALENCIA (XOR) és EKVIVALENCIA (XNOR) függvényeket tárgyaltuk. 45
LOGIKAI FÜGGVÉNYEK MEGADÁSI MÓDJAI
A kombinációs hálózatok tervezésének kiindulási lépése a logikai függvény felírása a megoldandó feladat alapján. Általában az algebrai alak használatos. Egyazon függvény többféle algebrai alakban is megadható. Közöttük kitüntetett szerepük van az ún. normalizált vagy kanonikus alakoknak. 46
LOGIKAI FÜGGVÉNY MEGADÁSA IGAZSÁGTÁBLÁZATTAL
A logikai függvény többféle módon megadható,
Egy logikai függvény egyértelmően megadható, ha a független változók összes lehetséges
illetve ábrázolható. Az alábbi módokat fogjuk alkalmazni.
kombinációjához megadjuk a függvénykapcsolat által elıírt függvényértéket.
1. Igazságtáblázat 2. Algebrai alak
Az ilyen függvénydefiníció egyértelmő.
3. Grafikus ábrázolás 4. Szimbolikus jelölés 47
48
LOGIKAI FÜGGVÉNY MEGADÁSA IGAZSÁGTÁBLÁZATTAL ILLETVE ALGEBRAI ALAKBAN i A B C Y _________________ 0 0 0 0 0 1 0 0 1 0 2 0 1 0 1 3 0 1 1 0 4 1 0 0 1 5 1 0 1 0 6 1 1 0 1 7 1 1 1 0 _________________
FÜGGVÉNY MEGADÁSA ALGEBRAI ALAKBAN
– – –– – Y(A,B,C) = ABC + ABC + ABC Egy logikai függvény egyértelmő megadása: a független változók összes lehetséges kombinációjához megadjuk a függvénykapcsolat által elıírt függvényértéket. Ez az ún. igazságtáblázat. Az ilyen függvénydefiníció 49 egyértelmő.
A logikai függvény megadható oly módon, hogy a logikai mőveletek szimbólumaival (ÉS, VAGY és NEM) definiáljuk a logikai függvényt. Egyazon függvény többféle algebrai alakban is megadható. Közöttük kitüntetett szerepük van az un. normalizált vagy kanonikus alakoknak.
50
SZIMBÓLIKUS JELÖLÉS
GRAFIKUS ÁBRÁZOLÁS A logikai függvény értékei pl. az igazságtáblázat segítségével grafikusan is szemléltethetık un. függvénytáblázatokon (Karnaugh-táblázatok, ill. Veitch-diagramok). Ez az ábrázolási mód korlátozott független változó szám esetén igen szemléletes, és az ún. függvény-minimalizáláskor jól felhasználható.
Az egyes logikai mőveleteket szimbólumok jelölhetik (pl. a rajzjelek). Elektronikus logikai rendszerekben minden szimbólum egy-egy, a logikai mőveletet realizáló áramkörre utal. Így a logikai függvények szimbolikus megadása egyúttal az áramköri megvalósításról is információt nyújt.
51
KOMBINÁCIÓS HÁLÓZAT ÉS LOGIKAI FÜGGVÉNY
52
LOGIKAI FÜGGVÉNYEK KANONIKUS ALAKJAI A most következı anyagot egy háromváltozós,
Egy kombinációs hálózatban egyetlen kimeneti pont esetén minden logikai feladat megadható egyetlen logikai függvénnyel. Az egyes bementeti-változó kombinációkhoz
teljesen határozott logikai függvény igazságtáblázata fogja illusztrálni, az új fogalmakat ennek alapján vezetjük be, és az elméletet is ez alapján építjük fel.
tartozó függvényérték a hálózat kimeneti változójának logikai értékével azonos.
A tárgyalásmód Arató Péter (ajánlott) könyvét (Logikai rendszerek tervezése) követi.
53
54
TELJESEN HATÁROZOTT LOGIKAI FÜGGVÉNY (LOGIKAI FELADAT) A B C F ————— 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 —————
Teljesen határozott logikai függvény megadható azon változókombinációk felsorolásával,amelyekhez F = 1, vagy azokéval amihez F = 0 tartozik. — —
—
——
———
——
&
—
——
—
Az egyes bementekre értelemszerően az egyes ponált vagy negált változók kerülnek.
Analóg módon alakítható ki a csak NAND kapukból álló hálózat is.
F(ABC) = A B C + A BC + ABC + ABC —
F és F egyaránt logikai szorzatok VAGY kapcsolataként adható meg.
—
&
1
& 55
NEM TELJESEN HATÁROZOTT LOGIKAI FÜGGVÉNY (FELADAT) A B C F ————— 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 —————
— —
F(ABC) = ABC + ABC + ABC + ABC
&
—
F(ABC) = ABC + ABC + ABC + ABC vagy ————
KÉTSZINTŐ ÉS-VAGY KAPUS REALIZÁLÁS
56
NEM TELJESEN HATÁROZOTT LOGIKAI FÜGGVÉNY
Nem teljesen határozott logikai függvény, van olyan változókombináció, amelyekhez nincs elıírt függvényérték. A táblázat négy olyan egymástól különbözı de teljesen határozott logikai függvényt definiál, melyekkel megvalósított kombinációs hálózatok mindegyike megoldja az adott logikai feladatot. A két közömbös F érték négyféleképpen tehetı határozottá. A tervezés során kell kiválasztani a négy 57 hálózat közül a legkedvezıbbet.
A B C F ————— 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 —————
A nem teljesen határozott logikai függvények algebrai alakjában a közömbös kombinációknak megfelelı tagokat általában zárójelben írják fel. ———
— —
—
F(ABC) = A B C + ABC + ABC + ABC ——
—
+ (AB C) + (ABC) 58
DISZJUNKTÍV KANONIKUS ALAK (EXTENDED SUM-OF-PRODUCTS)
LOGIKAI FÜGGVÉNYEK KANONIKUS ALAKJAI A kombinációs hálózatok tervezésénél célszerő az algebrai alakból kiindulni. Mivel egy logikai függvénynek több algebrai alakja is van, olyan
A logikai szorzatok logikai összegeként (ÉS-VAGY) képzett algebrai alak kanonikus vagy normál alak. A példa szerinti függvényalak tulajdonságai: — —
—
——
—
F(ABC) = ABC + ABC + ABC + ABC
speciális tulajdonságú alakot kell keresni, mely olyan, hogy a logikai függvényhez más, ilyen tulajdonságú algebrai alak nem rendelhetı. Az ilyen alak a logikai függvény normál vagy kanonikus alakja. 59
- mindegyik szorzat egy olyan független-változó kombináció, melyhez F = 1 tartozik; - mindegyik szorzatban az összes független változó szerepel ponált vagy negált alakban. A teljesen határozott függvénynek csak egy ilyen algebrai alakja van a diszjunktív kanonikus alak. 60
MINTERM (DEFINICIÓ)
KONJUNKTÍV KANONIKUS ALAK
A diszjunktív kanonikus alak tagjai neve minterm m in
itt n a független változók száma,
i a független változók adott kombinációjának megfelelı bináris szám decimális értéke. — —
—
——
————
———
——
—
F(ABC) = A B C + A B C + A B C + ABC ————
F(ABC) = m03 + m13 + m53 + m73
—
F(ABC) = ABC + ABC + ABC + ABC (emlékeztetı: (2) (3) (4) (6) )
A függvény negáltja azokat a mintermeket tartalmazza, melyeket a függvény nem tartalmaz (ez csak a teljesen határozott logikai függvényekre igaz!)
F(ABC) = m23 + m33 + m43 + m63 más jelölés: 3 F = Σ (2,3,4,6)
61
KONJUNKTÍV KANONIKUS ALAK (2) A De Morgan képletek felhasználásával elvégzett átalakításokkal elıállítható az F függvény konjunktív kanonikus alakja, mely az un. maxtermek szorzataként adható meg
62
MINTERMEK ÉS MAXTERMEK KAPCSOLATA Eredeti függvény, diszjunktív normálalak F(ABC) = m23 + m33 + m43 + m63
————
Negált függvény, diszjunktív normálalak (index i)
————
F(ABC) = F(ABC) = — —
———— —
—
—
F(ABC) = m03 + m13 + m53 + m73
—
(A + B + C) (A + B + C) (A + B + C) (A + B + C) Eredeti függvény, konjunktív normálalak (index I) F(ABC) = M73M63M23M03
63
MINTERMEK ÉS MAXTERMEK
F(ABC) = M73M63M23M03
64
ELVI LOGIKAI RAJZ Minden logikai függvény megadható ÉS, VAGY, NEM mőveletekkel. Eltekintve a bemeneti változók negáltját adó NEM kapuktól (INVERTER), a két kanonikus alak kétszintő ÉS-VAGY illetve VAGYÉS kapuhálózattal realizálható.
A negált függvény mintermjeinek i indexe és a ponált függvény maxtermjeinek I indexei közötti összefüggés (esetünkben három változós a függvény) i + I = 7 = 23 - 1
Mivel az ÉS, VAGY és NEM mőveletek akár kizárólag NAND akár kizárólag NOR kapukkal megvalósíthatók, ezért a diszjunktív normálalakból kiindulva bármely logikai függvény realizálható kétszintő NAND kapus vagy NOR kapus hálózattal.
n-változós függvényre i + I = 2n -1 65
66
— —
&
—
— —
F(ABC) = ABC + ABC —
+ ABC + ABC
&
o
——
&
&
o
——
&
Az ÉS kapuk bementeire értelemszerően az egyes ponált vagy negált változók 67 kerülnek.
&
LOGIKAI FÜGGVÉNY EGYSZERŐSÍTÉSE: MINIMALIZÁLÁS Logikai hálózat tervének gazdaságossága: 1. Felhasznált kapuk számának csökkentése; 2. Összekötetések számának csökkentése; 3. Kapukat megvalósító építıelem-fajták optimális kiválasztása. A 3. pontbeli feladat megoldására nincs általános módszer, az 1. és 2. pontbeli feladatokra adhatók használható eljárások. Az optimalizálás (minimalizálás) bizonyos korlátokkal, mint a kapubementek számának csökkentése (minimalizálása) is megfogalmazható.
A NAND kapuk bemeneteire értelemszerően az egyes ponált vagy negált változók kerülnek.
o
&
—
+ ABC + ABC
1 &
—
F(ABC) = ABC + ABC
o
&
AZ F(A,B,C) NAND KAPUS REALIZÁLÁSA o
AZ F(A,B,C) ÉS-VAGY KAPUS REALIZÁLÁSA
LOGIKAI FÜGGVÉNY EGYSZERŐSÍTÉSE: ILLUSZTRÁCIÓ — —
—
——
—
F(ABC) = ABC + ABC + ABC + ABC ”kiemelések” alkalmazásával —
—
— —
—
—
= AB(C + C) + AC(B + B) = AB + AC Az eredmény egy jóval egyszerőbb algebrai alak melyet realizálva mind a kapuk, mind az összekötetések száma jelentısen csökken.
69
EGYSZERŐSÍTETT FÜGGVÉNY ÉS-VAGY KAPUS REALIZÁLÁSA
70
LOGIKAI FÜGGVÉNYEK MINIMALIZÁLÁSA — —
A
1
o
& —
1
——
—
m23 + m33 + m43 + m63
mintermek
1 o
—
F(ABC) = ABC + ABC + ABC + ABC
B C
68
—
— —
—
—
= AB(C + C) + AC(B + B) = AB + AC
&
—
Az összevonható mintermek egy helyértékben és csakis egyben térnek el egymástól:
—
F(A,B,C) = AB + AC
(010) és (011), illetve (100) és (110) 71
Ez az összevonások és a minimalizálás kulcsa!
72
SZOMSZÉDOS MINTERMEK, MINIMALIZÁLÁS
MINIMALIZÁLÁS, PRÍMIMPLIKÁNSOK
Szomszédos mintermek: egy logikai változó ponált illetve negált, a többi azonos. A minimalizálás menete: 1. A szomszédos mintermeket összevonják, a megfelelı változó kiesik. 2. Az új alakban az esetleges szomszédos termeket megint összevonják. 3. Az eljárást addig folytatják míg olyan szorzatok összegét kapjuk, melyekbıl már egy változó sem hagyható el. Az így kapott szorzatok, termek a prímimplikáns-ok. 73
A logikai függvény minimalizált (diszjunktív) alakja tehát prímimplikáns-ok összege. — —
az algebrai alak —
F(A,B,C) = A BC + ABC + ABC + ABC —
—
—
—
—
—
—
itt a prímimplikánsok AB és AC A logikai függvényt egyszerősítı eljárások célja a prímimplikánsok megkeresése. Egy függvénynek több ekvivalens legegyszerőbb alakja is lehet!
74
Hasonló gondolatmenet érvényes a függvények konjunktív vagy maxtermes alakjára is. Két szomszédos maxterm szintén összevonható egyetlen összeggé, mely nem tartalmazza a két maxtermet megkülönböztetı változót. —
= AC(B + B) + AC(B + B) (1) (1) —
—
MINIMALIZÁLÁS KONJUNKTÍV ALAKBAN
F = m13 + m33 + m53 + m73 = F = Σ3 (1,3,5,7)
—
——
F(ABC) = AB + AC
TOVÁBBI ILLUSZTRÁCIÓ
——
—
F(ABC) = ABC + ABC + ABC + ABC
—
—
—
—
—
—
—
—
—
(A + B + C)(A + B + C) = (A + (B + C))(A + (B + C))
—
—
= AC + AC = C(A + A) = C (1)
— —
—
—
—
—
—
= AA + (A + A)(B + C) + (B + C) = B + C 75
76
FÜGGVÉNYMINIMALIZÁLÁSI ELJÁRÁSOK 1. Grafikus (táblázatos) minimalizálás: Karnaughtáblázat alapján.
VÉGE
2. Számjegyes minimalizálás (Quine-McCluskeymódszer). 3. ”Egzakt” algebrai, számítógépre adaptálható algoritmusok, pl. irredundás lefedési-algoritmus csoport . 4. Egyéb (többnyire heurisztikus) eljárások.
77
78
