DIGITÁLIS TECHNIKA I
2. ELİADÁS LOGIKAI (BOOLE-ALGEBRA)
Dr. Pıdör Bálint BMF KVK Mikroelektronikai és Technológia Intézet 2. ELİADÁS: LOGIKAI (BOOLE) ALGEBRA
1. Bevezetés a logikai (Boole-) algebrába 2. A Boole-algebra axiómái 3. Logikai alapmőveletek (logikai ÉS, VAGY, NEM, stb.) 4. A Boole-algebra tételei és alkalmazásaik
2008/2009 tanév 1. félév
BOOLE-ALGEBRA, DIGITÁLIS TECHNIKA, LOGIKAI HÁLÓZAZOK
LOGIKAI (BOOLE-)ALGEBRA A logikai algebra, a logikai mőveletek rövid, tömör matematikai formában való leírásával foglalkozik. Megalkotója George Boole (1815-1864) angol
A Boole-algebra a logikai hálózatok analízisének és szintézisének legalapvetıbb eszköze
matematikus. Nevét viseli a logikai algebra mint Boole-algebra. Jelentıs még Augustus De Morgan (1806-1871) brit (skót) matematikus hozzájárulása is (De Morgan tételek).
BOOLE-ALGEBRA Boole és De Morgan 1847-tıl kezdve dolgozták ki a formális logikát (Boole-algebrát). Ekkor már régóta használták a bináris kapcsolásokat órák, automaták vezérlésére. The Mathematical Analysis of Logic (1847) illetve An Investigation of Laws of Thought (1854) a két alapvetı munkája George Boole-nak
BOOLE-ALGEBRA ÉS KAPCSOLÓ ÁRAMKÖRÖK A Boole-algebrát az 1930-as évek végén kezdték alkalmazni a kapcsolóáramkörök tervezésére. Claude Elwood Shannon (1916-2001) az információelmélet úttörıje, az MIT hallgatója, majd a Bell Labs munkatársa ismerte fel 1938-ban a Boole algebra alkalmazhatóságát a relékbıl felépített (telefon-)kapcsoló-rendszerek vizsgálatára és tervezésére. Ma a Boole-algebra a logikai hálózatok analízisének és szintézisének legalapvetıbb eszköze.
Jelfogó és kapcsoló áramkörök szimbolikus analízise
7
8
LOGIKAI VÁLTOZÓK
LOGIKAI VÁLTOZÓK ÉRTÉKKÉSZLETE
A logikai változók az egyes események absztrakt leírására alkalmasak. Két értéket vehetnek fel, 1 vagy 0, attól függıen, hogy az esemény bekövetkezik vagy sem.
IGAZ/HAMIS,TRUE/FALSE, illetve IGEN/NEM az esemény bekövetkezésére vonatkozik. Az 1 és 0 itt nem számjegy, jelentésük szimbolikus:
Ha az esemény bekövetkezik, akkor a logikai változó értéke 1. Ha az esemény nem következik be, akkor a logikai változó értéke 0.
LOGIKAI VÁLTOZÓK: FÜGGİ ÉS FÜGGETLEN VÁLTOZÓK
IGAZ↔ 1 és HAMIS ↔ 0. A HIGH/LOW jelentése a logikai értékek szokásos elektromos reprezentációjához kapcsolódik, alacsony és magas feszültségszintnek felel meg, pl. (névlegesen) 0 V illetve + 5 V.
LOGIKAI VÁLTOZÓK SZEMLÉLTETÉSE •
VENN diagram: A
A logikai változók két csoportba oszthatók, úm.
C
A
A
B A
B
•VEITCH diagram: B
független-, és függı változókra.
C
D D
C C
C D
Jelölés: A, B, C, .... X, Y, Z.
B
B
A A A A
Az elsı betőket általában a független változókra tartjuk fent.
•Idıdiagram A B C
t
A BOOLE ALGEBRA AXIÓMÁI Az axiómák olyan elıre rögzített kikötések, alap állítások, amelyek az algebrai rendszerben mindig érvényesek, viszont nem igazolhatók. Ezen állítások a halmaz elemeit, a mőveleteket, azok tulajdonságait, stb. határozzák meg. A tételek viszont az axiómák segítségével bizonyíthatók.
BOOLE-ALGEBRA: 1.- 3. AXIÓMÁK 1.
Az Boole-algebra kétértékő elemek halmazára értelmezett.
2.
A halmaz minden elemének létezik a komplemens -e is, amely ugyancsak eleme a halmaznak.
3.
Az elemek között végezhetı mőveletek a konjunkció ( logikai ÉS ), illetve a diszjunkció (logikai VAGY).
A Boole algebra az alábbi öt axiómára épül:
BOOLE-ALGEBRA: 4. ÉS 5. AXIÓMA 4. A logikai mőveletek: kommutatívak ( a tényezık felcserélhetık ), asszociatívak (a tényezık csoportosíthatók), disztributívak ( a két mővelet elvégzésének sorrendje felcserélhetı ). 5. A halmaz kitüntetett elemei az egység elem (értéke a halmazon belül mindig IGAZ, azaz 1), és a nulla elem (értéke a halmazon belül mindig HAMIS, azaz 0).
KOMPLEMENSKÉPZÉS: TAGADÁS A logikai algebra illetve a Boole-algebra a felsorolt axiómákra épül. A logikai feladatok technikai megvalósításáh oz a halmaz egy elemének komplemens-ét képezı mővelet is szükséges. Ezért a mőveletek között a logikai TAGADÁS is szerepel. _ _ A • A = 0 és A+A=1
EGYSÉG ÉS NULLA ELEM A halmaz kitüntetett elemei, melyek mindig léteznek az egység elem (értéke a halmazon belül mindig IGAZ, azaz 1), A•1=1•A=A és a null/zérus elem (értéke a halmazon belül mindig HAMIS, azaz 0) A+0=0+A=A
LOGIKAI MŐVELETEK A változókkal végezhetı logikai mőveletek: ÉS (konjunkció) - logikai szorzás; VAGY (diszjunkció) - logikai összeadás; NEM (negáció, invertálás, komplementálás) logikai tagadás. Az ÉS, illetve a VAGY logikai mővelet két-, vagy többváltozós, a változók legalább két eleme, vagy csoportja között értelmezett logikai kapcsolatot határoz meg. A tagadás egyváltozós mővelet, amely a változók, vagy változócsoportok bármelyikére vonatkozhat.
AZ ÉS (AND) MŐVELET, LOGIKAI SZORZÁS (KONJUNKCIÓ)
ÉRTÉKTÁBLÁZAT, IGAZSÁGTÁBLÁZAT
A logikai változókkal végzett ÉS mővelet eredménye akkor és csak akkor IGAZ, ha mindegyik változó értéke egyidejőleg IGAZ. A logikai algebrában az ÉS kapcsolatot szorzással jelölik (logikai szorzás), de a logikai szorzás jelét általában nem szokás kitenni. A
A logikai függvénykapcsolatok többféleképen is megadhatók, az egyik általánosan használt a táblázatos megadási mód. Mivel minden változó csak két értéket vehet fel ezért n változó esetén összesen 2n különbözı kombináció különböztethetı meg (2 elembıl álló n-ed osztályú ismétléses variáció!). Így két változó esetén az összes lehetséges kombinációk száma négy. Az igazságtáblázat bal oldalán adjuk meg a bemeneti vagy független változók értékét, míg jobb oldalán a kimentei vagy függı változó értékei szerepelnek.
K=A•B algebrai egyenlıségben A és B a független változók, és K a függı változó, vagy eredmény. Jelentése pedig az, hogy a K akkor IGAZ, ha egyidejőleg az A és a B is IGAZ.
AZ ÉS MŐVELET IGAZSÁGTÁBLÁJA B 0 1 0 1
A 0 0 1 1
K= A• B 0 0 0 1
LOGIKAI SZORZÁS (KONJUNKCIÓ), (LOGIKAI ÉS KAPCSOLAT) Definícíó:
0•0=0 0•1=0 1•0=0 1•1=1
A mővelet eredménye tehát csak akkor a logikai 1 érték, ha mindkét tényezı logikai értéke 1. A mővelet a definíció szerint kommutatív. Formailag megegyezik az aritmetikai szorzással, de az 1 és 0 értékek jelentése csak logikai.
ÉS (AND) ÁRAMKÖRI SZIMBÓLUMOK Kapuáramkörök esetében X Z
Kapcsoló áramkörök esetében X
Y
Y Z X
& Y .
Z
Sorbakötött és nyugalmi állapotban nyitott (=MAKE) kapcsolók
A VAGY (OR) MŐVELET A logikai változókkal végzett VAGY mővelet eredménye akkor IGAZ, ha a független változók közül legalább az egyik IGAZ. Algebrai formában ezt a független változók összegeként írjuk le (logikai összeadás). A K=A+B alakú algebrai egyenlıségben a K eredmény akkor IGAZ, ha vagy az A, vagy a B, vagy mindkettı IGAZ. A VAGY mőveletet leíró táblázat tehát az alábbi:
VAGY MŐVELET IGAZSÁGTÁBLÁJA
LOGIKAI ÖSSZEDÁS (DISZJUNKCIÓ), (LOGIKAI VAGY KAPCSOLAT) Definíció:
B 0 1 0 1
A 0 0 1 1
K=A+B 0 1 1 1
LOGIKAI ÖSSZEDÁS (DISZJUNKCIÓ), (LOGIKAI VAGY KAPCSOLAT) 0+0=0 Definíció: 0+1=1 1+0=1 1+1=1 A mővelet eredménye tehát csak akkor a logikai 1 érték, ha vagy az elsı, vagy a második tag (vagy mindkettı) logikai értéke 1. A mővelet a definíció szerint kommutatív. Az utolsó definíciós összefüggés kivételével formailag az aritmetikai összeadás szabályai is alkalmazhatók a logikai értékekre.
0+0=0 0+1=1 1+0=1 1+1=1
A mővelet eredménye tehát csak akkor a logikai 1 érték, ha vagy az elsı, vagy a második tag (vagy mindkettı) logikai értéke 1. A mővelet a definíció szerint kommutatív. Az utolsó definíciós összefüggés kivételével formailag az aritmetikai összeadás szabályai is alkalmazhatók a logikai értékekre.
VAGY (OR) ÁRAMKÖRI RAJZJELEK Kapcsoló áramkörök esetében
Kapuáramkörök esetében
X
X Z
Y
Y
Z
X
1 Y .
Z
Párhuzamosan kötött, nyugalmi állapotban nyitott (= MAKE) kapcsolók
LOGIKAI SZORZÁS ÉS ÖSSZEADÁS KETTİNÉL TÖBB VÁLTOZÓRA
A TAGADÁS (INVERZ, KOMPLEMENTÁLÁS) MŐVELET
Mindkét definiált logikai mővelet értelemszerően kiterjeszthetı kettınél több tényezıre, illetve tagra is. Ekkor természetesen a mőveletek elvégzésének sorrendjét megfelelı zárójelek alkalmazásával kell jelölni, akárcsak aritmetikai mőveletek esetén.
A logikai tagadást egyetlen változón, vagy csoporton végrehajtott mőveletként értelmezzük. Jelentése pedig az, hogy ha a változó IGAZ, akkor a tagadottja HAMIS és fordítva. Algebrai leírásban a tagadást a változó jele fölé húzott vonallal jelöljük. Ezek szerint a K=Ā egyenlıség azt jelenti, hogy a K akkor IGAZ, ha az A HAMIS. Szóban A nem - nek, A felülvonás-nak vagy A tagadott-nak mondjuk.
A TAGADÁS MŐVELET IGAZSÁGTÁBLÁJA K
K=Ā
LOGIKAI NEGÁCIÓ (INVERTÁLÁS, KOMPLEMENTÁLÁS), LOGIKAI TAGADÁS MŐVELET —
Definíció:
0
—
0
1
1
0
1
=1 =0
A mővelet tehát logikai értékekhez ellentettjüket rendeli hozzá. A mőveletet páros számú esetben alkalmazva, eredményül a kiindulási logikai érték adódik: ––
0
=0
és
––
1
=1
Páratlan számú alkalmazás az ellentett, negált értéket eredményezi.
A negáció (folytatás) • A negáció nem két- hanem csak egyargumentumos mővelet. • A gyakorlatban sokszor szükség van egy X változó negáltjának az elıállítására. • Az erre való eszköz az inverter. inverter (A negációt a köröcske jelenti):
X
X
Talán éppen azért tekintik sokszor a negációt „mőveletnek” mert a kapuáramkörök között van eszköz a végrehajtására.
NEM-VAGY (NOR) ÁRAMKÖRI RAJZJELEK Kapuáramkörök esetében
Kapcsoló áramkörök esetében
X
NEM-ÉS (NAND) ÁRAMKÖRI RAJZJELEK Kapuáramkörök esetében
Kapcsoló áramkörök esetében
X
X
Z Y
Y Z
X
& Y
Z
Párhuzamosan kötött, nyugalmi állapotban zárt (=BREAK) kapcsolók
POZITÍV ÉS NEGATÍV LOGIKA IGAZ/HAMIS,TRUE/FALSE, illetve IGEN/NEM az esemény bekövetkezésére vonatkozik. Az 1 és 0 itt nem számjegy, jelentésük szimbolikus:
Z
X
Y
Y Z
X
1 Y
Z
Sorosan kötött, nyugalmi állapotban zárt (=BREAK) kapcsolók
IGAZ↔ 1 és HAMIS ↔ 0. A HIGH/LOW jelentése a logikai értékek szokásos elektromos reprezentációjához kapcsolódik, alacsony és magas feszültségszintnek felel meg, pl. (névlegesen) 0 V illetve + 5 V.
Positive vs. Negative Logic
Positive and Negative Logic (Cont’d.)
•Positive logic: truth, or assertion is represented by logic 1, higher voltage; falsity, de- or unassertion, logic 0, is represented by lower voltage. •Negative logic: truth, or assertion is represented by logic 0 , lower voltage; falsity, de- or unassertion, logic 1, is represented by lower voltage
Voltage levels
Gate Logic: Positive vs. Negative Logic Normal Convention: Postive Logic/Active High Low Voltage = 0; High Voltage = 1
Negative logic levels
B
F
A B
F
A B
F
low
low
0
0
0
1
1
1
low
high
low
0
1
0
1
0
1
high low
low
1
0
0
0
1
1
high high
high
1
1
1
0
0
0
A B
Alternative Convention sometimes used: Negative Logic/Active Low
Positive logic levels
A low
Physical AND gate
F
A B
F=AB
A B
F=A+B
F V oltage Truth T able A low low high high
B low high low high
F low low low high
Positive Logic A 0 0 1 1
Behavior in terms of Electrical Levels
B 0 1 0 1
Voltage levels
Negative Logic F 0 0 0 1
A 1 1 0 0
B 1 0 1 0
Two Alternative Interpretations Positive Logic AND Negative Logic OR
A B
Positive logic levels
Negative logic levels
A B
F
A B
F
high
0
0
1
1
1
0
high
0
1
1
1
0
0
high low
high
1
0
1
0
1
0
high high
low
1
1
0
0
0
1
A
F 1 1 1 0
B
F
low
low
low
high
Physical NAND gate
F
A B
F=AB
A B
F=A+B
Dual Operations
LOGIKAI MŐVELETEK TULAJDONSÁGAI • Kommutativitás • Asszociativitás
LOGIKAI MŐVELETEK TULAJDONSÁGAI: KOMMUTATIVÍTÁS Az ÉS (logikai vagy) és VAGY (logikai összeadás) mőveletek alapvetı tulajdonsága a kommutativitás, azaz az operandusok sorrendjének felcserélhetısége:
• Disztributivitás A•B=B•A A+B=B+A
LOGIKAI MŐVELETEK TULAJDONSÁGAI: ASSZOCIATIVÍTÁS Az ÉS (logikai vagy) és VAGY (logikai összeadás) mőveletek másik alapvetı tulajdonsága az asszociativítás, azaz az operandusok csoportosíthatósága: A • (B • C) = (A • B) • C = A • B • C A + (B + C) = (A + B)+ C = A + B + C A zárójelek a mőveletei sorrendjét adják meg. Igazolás: logikai értékek behelyettesítésével.
LOGIKAI MŐVELETEK TULAJDONSÁGAI: DISZTRIBUTIVÍTÁS Az ÉS (logikai vagy) és VAGY (logikai összeadás) mőveletek harmadik alapvetı tulajdonsága a disztributívitás, azaz az operandusok átrendezhetısége: A • (B + C) = A • B + A • C A + (B • C) = (A + B) • (A + C) Igazolás: logikai értékek behelyettesítésével.
A MŐVELETEK DISZTRIBUTIVÍTÁSA AZ ÉS és a VAGY mőveletek azonos értékőek. Mindkettı disztributív a másikra nézve. Az elsı azonosság alakilag megegyezik a közönséges matematikai mőveletvégzési szabályokkal. A második azonosság csak a logikai algebrában érvényes. Kifejezi azt, hogy egy logikai szorzat (ÉS) és egy logikai érték (állítás) logikai összege (VAGY) úgy is képezhetı, hogy elıször képezzük a VAGY mőveletet a szorzat tényezıivel és az így kapott eredményekkel hajtjuk végre az ÉS mőveletet.
A LOGIKAI ALGEBRA TÉTELEI Fontosabb tételek, azok részletes bizonyítása nélkül. Helyességükrıl a logikai értékek összes lehetséges kombinációinak behelyettesítésével lehet meggyızıdni. A kitüntetett (1 illetve 0) elemekkel végzett mőveletek:
LOGIKAI KIFEJEZÉSEK ÁTALAKÍTÁSA A logikai mőveletek tulajdonságai segítségével a logikai kifejezések algebrai átalakítása hajtható végre, és így lehetıség van a legegyszerőbb alakú kifejezés megkeresésére. Ezt a késıbbiekben még részletesebben fogjuk tárgyalni.
A LOGIKAI ALGEBRA TÉTELEI: AZONOS VÁLTOZÓK Az azonos változókkal végzett mőveletek: Tautológia (idempotencia): A•A=A
A+A=A
Negáció szabályai: 1•1=1 1•A=A 1+1=1 1+A=1
0•0=0 0•A=0 0+0=0 0 + A =A
LOGIKAI ALGEBRA TÉTELEI: TAGADÁS A logikai tagadásra vonatkozó tétel (kettıs negáció): _ _ A= A Általánosan: a páros számú tagadás nem változtatja meg az értéket, míg a páratlan számú tagadás azt az ellenkezıjére változtatja.
A•Ā=0
A+Ā=1
Az A-val jelzett logikai változó nem csak egy változó, hanem egy logikai mőveletsor eredménye is lehet.
TOVÁBBI ÖSSZEFÜGGÉSEK Abszorpciós szabály A • (A + B) = A A+A•B=A A fenti, a logikai algebrában érvényes összefüggések természetesen nem érvényesek a szokásos algebrában.
DE MORGAN TÉTELEK
DE MORGAN TÉTELEK
A logikai algebrában kitüntetett szereppel bírnak a De Morgan-azonosságok ––––––
—
––––––
—
–––––
A+B=A•B –––––
—
—
—
A+B=A•B —
—
A•B=A+B
—
A•B=A+B
Break the line, change the operation!
Logikai összeg negáltja azonos a tagok negáltjainak logikai szorzatával. Logikai szorzat negáltja pedig azonos a tényezık negáltjainak összegével.
Vágd el a vonalat, cseréld fel a mőveletet!
A DE MORGAN AZONOSSÁGOK A logikai (Boole) algebrában centrális helyet foglalnak el az ún. De Morgan tételek vagy azonosságok. A De Morgan-azonosságokat a középkori skolasztika logikusai már ismerték, de az idı folyamán jelentıségük elhomályosult. A két matematikai logikai azonosságot egzakt formában Augustus De Morgan fogalmazta meg 1847-ben, William Ockham korábbi megállapításai (1325) alapján.
DE MORGAN TÉTELEK A De Morgan tételek vagy azonosságok általánosan azt fogalmazzák meg, hogy egy logikai kifejezés tagadása úgy is elvégezhetı, hogy az egyes változókat tagadjuk, és a logikai mőveleteket felcseréljük (VAGY helyett ÉS, illetve ÉS helyett VAGY mőveletet végzünk).
DE MORGAN SZABÁLYOK ALKALMAZÁSA
DeMorgan’s Theorem A B
A De Morgan szabályok alapján az ÉS és a VAGY mőveletek csak egyikét a NEM mővelettel együtt használva a harmadik mővelet elıállítható.
0 0 1 1
0 1 0 1
AB = A + B 1 1 1 0
1 1 1 0
A + B = AB 1 0 0 0
1 0 0 0
———— —
—
DeMorgan’s theorem: A + B = A + B = A B
A • B = (A + B) ———— —
—
A + B = (A • B)
A B
F=A+B
A B
F=AB
DE MORGAN TÉTELEK ÁLTALÁNOSÍTÁSA
DE MORGAN TÉTELEK ALKALMAZÁSA LOGIKAI HÁLÓZATOK KIALAKÍTÁSÁBAN
A digitális rendszerek analízisében és szintézisében fontos szerepet játszanak a De Morgan-féle tételek. Több változóra érvényes alakjuk az alábbi _____ _ _ _ A B C ... = A + B + C + ... ________ __ _ A + B + C + ... = A B C ...
ÁLTALÁNOSÍTOTT DE MORGAN(SHANNON) FÉLE TÉTEL Az általánosított De Morgan (Shannon) tétel a logikai összeadás és szorzás segítségével felépített logikai függvényekre vonatkozik _____________ _ _ _ f(A, B, C, ..., +, •) = f(A, B, C, ..., •, +) Az egész függvény tagadása helyettesíthetı az egyes változók tagadásával, ha a függvényben valamennyi logikai összeadást szorzásra, és valamennyi szorzást összeadásra cserélünk fel.
LOGIKAI ÁRAMKÖRÖK KIALAKÍTÁSA A GYAKORLATBAN A gyakorlatban kétféle áramköri technológia terjedt el. A szilícium CMOS (complementary metal oxide semiconductor) technológián alapuló áramköri rendszerben többnyire a NEM-VAGY (NOR) kapu az áramköri alapelem. A szilícium bipoláris technológián alapuló transistortransistor-logic (TTL) áramköri rendszerben a NEM-ÉS (NAND) kapu az alapelem.
LOGIKAI ÁRAMKÖRÖK KIALAKÍTÁSA Tetszıleges logikai összefüggés, vagy logikai függvény is elıállítható a NEM-ÉS vagy NEM-VAGY alapmővelet párokkal. Vagyis tetszıleges logikai áramkör kialakítható csupán NEM-ÉS, vagy csupán NEM-VAGY kapuk alkalmazásával. Gyakorlati jelentıség: az elektronikus erısítık általában invertáló jellegőek (180 fokos fázistolás). Ezért a gyakorlatban a NEM-ÉS (NAND) és a NEMVAGY (NOR) a szokásos alapelem. Végsı soron mindez a De Morgan tételeken alapul!
LOGIKAI KAPUK • A logikai áramkörök építıkockái. • A logikai alapmőveleteket valósítják meg. • Ezek egyszerő kombinációjával további áramköröket tudunk felépíteni pl. az aritmetikai mőveletek megvalósítására.
NEM-ÉS ÉS NEM-VAGY KAPUS MEGVALÓSÍTÁSOK
LOGIKAI ALAPKAPUK Áramköri magvalósítás elvei. Pozitív logika: magas feszültségszint ⇒1, alacsony szint⇒0
NEM
ÉS
VAGY Az ábra bemutatja, hogyan realizálható a NEM, ÉS és a VAGY mővelet kizárólag NEM-ÉS, illetve NEMVAGY mőveleti elemekkel (kapukkal).
LOGIKAI ALAPKAPUK REALIZÁLÁSA
LOGIKAI KAPUK RAJZJELEI
A logikai alapáramkörök két általánosan elterjedt elektronikus áramköri megvalósításában a kapcsolóelem • az n- és p-csatornás (szilícium) térvezérléső tranzisztor pár (CMOS FET, complementary metal-oxide-semiconductor field effect transistor), illetve • a (szilícium) dióda és a bipoláris tranzisztor (TTL áramkörök). Az erısítı-elem mindkét esetben a megfelelı tranzisztor.
REALIZÁLÁS KAPUKKAL MSZ A F 0 1 1 0
1
A 0 0 1 1
B 0 1 0 1
F 0 0 0 1
&
A 0 0 1 1
B 0 1 0 1
F 0 1 1 1
1
A 0 0 1 1
B 0 1 0 1
F 1 0 0 1
•Negáció A
•ÉS (AND) A*B
•VAGY (OR) A+B
•EKVIVALENCIA A ⊗ B = A∗B+ A∗B
USA
Ugyanazon logikai funkció illetve logikai kapu jelölésére az irodalomban, mint pl. könyvek, folyóiratok, tervrajzok, gyártó- és kereskedelmi cégek alkalmazási segédletei és katalógusai, stb., (sajnos) többféle jelölési rendszer, és ennek megfelelıen többféle szabvány létezik. Az MSZ 9200/33-73 szám alatt rögzíti a kötelezı elıírásokat kétállapotú (bináris) logikai elemek rajzjeleire vonatkozóan.
REALIZÁLÁS KAPUKKAL jelkép
MSZ •NEM-ÉS (NAND) A*B
•NEM-VAGY (NOR) A+B
•ANTIVALENCIA
≡
A⊕B = A∗B+ A∗B
USA
A 0 0 1 1
B 0 1 0 1
F 1 1 1 0
&
A 0 0 1 1
B 0 1 0 1
F 1 0 0 0
1
A 0 0 1 1
B 0 1 0 1
F 0 1 1 0
=1
jelkép
LOGIKAI KIFEJEZÉSEK ALGEBRAI ÁTALKÍTÁSA A következıkben néhány példával illusztráljuk a logikai függvények algebrai átalakítását. Hangsúlyozni kell, hogy a logikai algebra mőveleti szabályai eltérnek a szokásos algebra szabályaitól!
LOGIKAI ALGEBRAI ÁTALAKÍTÁS (1) Hozzuk egyszerőbb alakra az alábbi kifejezést _ _ Y = AB + AB + ABCD Az A változó kiemelhetı, utána a zárójelben lévı kifejezés fokozatosan egyszerősíthetı _ _ _ Y = A(B + B + BCD) = A(1 + BCD) = A Válasz: Y = A
LOGIKAI ALGEBRAI ÁTALAKÍTÁS (2) Hozzuk egyszerőbb alakra az alábbi kifejezést ____ ________ Y = ABC + A + B + C Alkalmazzuk a De Morgan azonosságokat! _ _ _ _ __ _ __ _ _ Y = A + B + C + A B C = A(1 + B C) + B + C =
LOGIKAI ALGEBRAI ÁTALAKÍTÁS (3) Hozzuk egyszerőbb alakra az alábbi kifejezést _ _ _ Y = CBA + CBA + CBA + CBA A jobboldalon szereplı CBA tagot kétszer hozzáadva, a logikai kifejezés nem változik meg! Páronként kiemelést végezve _ _ _ Y = AB(C + C) + BC(A + A) + CA(B + B) =
_ _ _ =A+B+C
= AB + BC +CA
IGAZSÁGTÁBLÁZATTAL MEGADOTT LOGIKAI FELADAT ÉS MEGOLDÁSA Példaként egy igazságtáblázatával megadott logikai függvény algebrai alakját határozzuk meg, majd azt megfelelıképen átalakítjuk, és kapuáramkörökkel realizáljuk.
PÉLDA LOGIKAI KIFEJEZÉS ALGEBRAI ÁTALAKÍTÁSÁRA SOR 0 1 2 3 4 5 6 7
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
Y Az igazságtáblázatával 0 megadott Y(A,B,C) logikai 0 függvény algebrai alakja 1 az Y oszlopból kiolvas0 ható, és három konjunkció 1 (ahol Y = 1) diszjunk0 ciójaként írható fel: 1 0 – – –– – Y(A,B,C) = ABC + ABC + ABC
LOGIKAI ALGEBRAI ÁTALAKÍTÁS – – –– – Y(A,B,C) = ABC + ABC + ABC Megfelelı kiemelésekkel – – – – – Y(A,B,C) = (AB + A(B + B))C = (AB + A)C Most alkalmazzuk az X + Y Z = (X +Y) (X + Z) tételt – – – – – Y(A,B,C) = (A + A)(A + B)C = (A + B)C = AC + BC Látható, hogy többféle ekvivalens algebrai alak létezhet, bármelyik realizálható. Az utolsó konjunktív / diszjunktív alak a pl. a Karnaugh táblán végzett minimalizálással nyerhetı forma.
LOGIKAI FÜGGVÉNY REALIZÁLÁSA Mind az eredeti függvény – – –– – Y(A,B,C) = ABC + ABC + ABC mind az ún. minimalizált alak – – Y(A,B,C) = AC + BC kétszintő, ÉS és VAGY kapus hálózattal illetve a De Morgan szabály szerint NEM-ÉS (NAND) és NEM-ÉS (NAND) kapus hálózattal realizálható, 12, illetve 6 kapubemenettel.
LOGIKAI MŐVELETEK ÉS DUALITÁS • A kétargumentumos mőveletek közül kettıtkettıt alapmő alapmőveletvelet-párokké rokként választhatunk. (Egyiket vagy a másikat, de nem mindkettıt.) • Ezek a mővelet-párok a következık: – ÉS ( szorzás) — VAGY (összeadás: +) – NEMNAND) — NEMNOR)) NEM-ÉS (NAND NEM-VAGY (NOR • A mőveletpárok egyik tagja a másik un. duá duális párja. rja
• A duális mőveletpárokat De Morgan tételek kapcsolják össze.
AZ ALKALMAZOTT TÉTEL: X + Y Z = (X +Y) (X + Z) Igazolás X + Y Z = (X +Y) (X + Z) = X X + X Y +X Z + Y Z =X+XY+XZ+YZ = X (1 + Y + Z) + Y Z =X+YZ
Q. E. D.
NAND KAPUS REALIZÁLÁS A kétszintő NAND kapus realizálás az alábbi átalakításon alapul (De Morgan szabályok!)
———— —— —— – – – – Y(A,B,C) = AC + BC = (AC) (BC)
A – C B – C
X
&
Z
X
Y
&
Z
Y
Y
X
&
Z
Y
Az alapmőveletekre való visszavezetés • A duális mővelet-párokkal (és a negációval) kifejezhetjük bármelyik másik mőveletet. • Itt a következıkben a logikai szorzással (ÉS) és a logikai összeadással (VAGY) valamint a negációval fejezzük ki a továbbiakban még megvizsgálandó (nem triviális) mőveleteket.
Duális mőveletpárok és a De Morgan tételek • A duális mőveletpárokat az ún. De Morgan tételek kapcsolják össze. • Szóban: Egy kétváltozós mővelet negáltja a duális mőveletpárt adja a változók negáltjaival. • A De Morgan tételek:
X .Y = X + Y ; X + Y = X .Y
VÉGE A 2. ELİADÁSNAK
