Boolean functions and operations. Logic gates and circuits


Logikai függvények

A számítógép mint fekete doboz működését leegyszerűsítve a következőképpen tudjuk megfogalmazni:

Formálisan ezt az alábbi 'p' függvénnyel tudjuk leírni:
p(x1,x2,...,xn) : G1Χ G2Χ ...Χ Gn → H1Χ H2Χ ...Χ Hm
ahol
– Gi={0,1} (1≤i≤n) azokat a bináris értékeket tartalmazó halmazokat jelöli, amelyekből a számítógép az input értékeket kapja,
– Hj={0,1} (1≤j≤m) pedig azokat a bináris értékeket tartalmazó halmazokat jelöli, amelyekből a számítógép az output értékeket előállítja.

A fenti 'p' függvény megadása ekvivalens az alábbi 'm' darab logikai függvény megadásával:
p1(x1,x2,...,xn) : G1Χ G2Χ ...Χ Gn → H1
p2(x1,x2,...,xn) : G1Χ G2Χ ...Χ Gn → H2
...
pm(x1,x2,...,xn) : G1Χ G2Χ ...Χ Gn → Hm
ahol Gi={0,1} (1≤i≤n) és Hj={0,1} (1≤j≤m) az egyes fk (1≤k≤m) függvények értelmezési tartományát, ill. értékkészletét megadó kétértékű halmazok.

Jegyezzük meg, hogy a számítógép működését leíró 'p' függvény értéke (azaz a 'p' függvényt megadó algoritmus kimenete) függhet azoktól az értékektől is, amelyeket a számítógép korábbi működése során előállított és/vagy eltárolt (például adatbázisokat használó alkalmazások esetében nyilvánvalóan ez a helyzet; de a számítógép korábbi állapotai is meghatározhatják a számítógép működését, pl. tanuló neurális hálózatok esetén). Erre a kérdésre később még visszatérünk, de egyelőre az egyszerűség kedvéért tételezzük fel, hogy a 'p' függvény független változói (azaz a számítógép bemenetei) teljes mértékben meghatározzák a függvény értékét. Ezt úgy is megfogalmazhatjuk, hogy nincsenek olyan "rejtett paraméterek", amelyek egyfajta formális "emlékezetként" befolyásolnák a 'p' függvény értékét (azaz a számítógép által szolgáltatott kimenetet).

Az, hogy a függvényekben a bemenetet és a kimenetet bináris értékek segítségével adtuk meg, nem jelent semmilyen korlátozást a számítógép működésére nézve. Korábban láttuk, hogy lényegében bármilyen típusú adat (például a számok) ábrázolhatók bináris értékek meghatározott sorozatával.

A számítógép működésének leírásakor használt {0,1} bináris értékeket egyaránt tekinthetjük
– bináris számjegyeknek,
logikai értékeknek (például 0↔'hamis', 1↔'igaz' értelemben), ill.
– egy digitális áramkör feszültségszintjeinek (például 0↔'alacsony feszültségszint', 1↔'magas feszültségszint' értelemben).

Először azzal a kérdéssel foglalkozunk, hogyan tudunk logikai függvényeket előállítani, utána pedig azt vizsgáljuk meg, milyen eszközök állnak rendelkezésünkre, hogy ezeket a logikai függvényeket technikailag is megvalósítsuk, és egy működőképes (elektronikus) rendszert állítsunk elő.

A továbbiakban bevezetünk három logikai alapműveletet, amelyek segítségével bármilyen logikai függvény előállítható. A digitális számítógépek működésének alapja, hogy a logikai alapműveletek (és ezáltal a logikai függvények) technikailag megvalósíthatók digitális áramkörök, ún. kapuáramkörök segítségével.

A három logikai alapművelet a következő:

A továbbiakban jelöljük a logikai változókat A, B, C, ...-vel. Jegyezzük meg, hogy a logikai változók csak két értéket vehetnek fel, a 0 ("hamis") vagy az 1 ("igaz") értékeket.

Egyes esetekben szükségünk lesz még két logikai konstansra is: azt a szimbólumot, amely mindig igaz, módon (ún. "szabvány igaz"), azt a szimbólumot pedig, amely mindig hamis, módon (ún. "szabvány hamis") fogjuk jelölni.


A logikai alapműveletek egyváltozós és kétváltozós logikai függvények. Ezért a logikai műveleteket legegyszerűbben ún. igazságtáblázatokkal tudjuk leírni, amelyben az értelmezési tartomány minden lehetséges értékéhez megadjuk az értékkészlet megfelelő elemét.

(1) negáció vagy tagadás ("nem A" vagy "NOT A"; jele ⌝A, de szokásos az A jelölés is)

A negáció ⌝A:{0,1}→{0,1} módon leírható egyváltozós logikai függvény. Igazságtáblázata a következő:

negáció
A ( ⌝A )
0 1
1 0

(2) konjunkció vagy logikai "és" ("A és B", "A AND B"; jele: A∧B, de szokásos egyszerűen az AB jelölés is)

A konjunkció A∧B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Igazságtáblázata a következő:

konjunkció
A B ( A ∧ B )
0 0 0
0 1 0
1 0 0
1 1 1

(3) diszjunkció vagy logikai (megengedő) "vagy" ("A vagy B", "A OR B"; jele: A∨B, de szokásos az A+B jelölés is)

A diszjunkció A∨B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Igazságtáblázata a következő:

diszjunkció
A B ( A ∨ B )
0 0 0
0 1 1
1 0 1
1 1 1

A három alapvető logikai művelet igazságtáblázatai alapján könnyen ellenőrizhetők a logikai alapműveletek alapvető tulajdonságait leíró alábbi logikai azonosságok, más néven logikai törvények:

A logikai alapműveletekkel kifejezhető legfontosabb azonosságok:

  • kettős tagadás: ⌝(⌝A) = A
  • a konjunkció idempotenciája: A∧A = A
  • a konjunkció kommutativitása: A∧B = B∧A
  • a konjunkció asszociativitása: (A∧B)∧C = A∧(B∧C)
  • konjunkció szabványkijelentésekkel:
    • A∧⊤ = A
    • A∧⊥ = 
  • a diszjunkció idempotenciája: A∨A = A
  • a diszjunkció kommutativitása: A∨B = B∨A
  • a diszjunkció asszociativitása: (A∨B)∨C = A∨(B∨C)
  • diszjunkció szabványkijelentésekkel:
    • A∨⊤ = 
    • A∨⊥ = A
  • disztributivitás:
    • A∧(B∨C) = (A∧B)∨(A∧C)
    • A∨(B∧C) = (A∨B)∧(A∨C)
  • abszorpció (elnyelés; elimináció):
    • A∧(A∨B) = A
    • A∨(A∧B) = A
  • de Morgan-féle azonosságok:
    • ⌝(A∧B) = ⌝A∨⌝B
    • ⌝(A∨B) = ⌝A∧⌝B

Logikai alapelvek:

  • az ellentmondás törvénye:
    • (A∧⌝A)  = 
  • a kizárt harmadik törvénye:
    • (A∨⌝A)  = 

A fenti logikai azonosságokban használt "kiemelt" egyenlőségjel ( = ) az általa összekapcsolt logikai kifejezések ekvivalenciáját fejezi ki: a logikai azonosságokban az egyenlőségjel bal- és jobboldalán szereplő logikai kifejezések a bennük szereplő logikai változók minden lehetséges értéke mellett azonos logikai értéket adnak. (A logikai kifejezések ekvivalenciájának jelölésére szokásos az A~B jelölés is.)

Az igazságtáblázatokat könnyen és kényelmesen létrehozhatjuk JavaScript programok segítségével is. A JavasScript programok legegyszerűbben a már korábban használt online JavaScript interpreter segítségével futtathatók.

Example: let us create the truth table of negation (⌝A), conjunction (A∧B), disjunction (A∨B), and a more complex logic or Boolean function using the online JavaScript interpreter.

The truth table of negation (⌝A):

// truth table of negation

function neg(x) { // 'x' is an input parameter of integer type  
 var a=Boolean(x); // converting into a Boolean type
 var c=!a;
 return Number(c); // converting back the output into an integer type
 }

writeln("A"+" "+"⌝A");
writeln("-----");

for(i=0;i<=1;i++) { // first 'i' is 0; then 'i' will be 1
 var k=neg(i);
 writeln(i+"  "+k);
 }

writeln("-----");

The truth table of conjunction (A∧B):

// truth table of conjunction

function con(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a && b;
 return Number(c);
 }

writeln("A"+" " +"B"+" "+"A∧B");
writeln("-------");

for(i=0;i<=1;i++) {
 for(j=0;j<=1;j++) {
  var k=con(i,j);
  writeln(i+" " +j+"  "+k);
  }
 }

writeln("-------");

The truth table of conjunction (A∨B):

// truth table of disjunction

function dis(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a || b;
 return Number(c);
 }

writeln("A"+" " +"B"+" "+"A∨B");
writeln("-------");

for(i=0;i<=1;i++) {
 for(j=0;j<=1;j++) {
  var k=dis(i,j);
  writeln(i+" " +j+"  "+k);
  }
 }

writeln("-------");

Now let us create the truth table of a more compex logic or Boolean function named p(A,B,C). (Note that function 'p' has three variables.)

// truth table of p(A,B,C)=(⌝A∧⌝B∧⌝C) ∨ (⌝A∧B∧C) 

function neg(x) {
 var a=Boolean(x);
 var c=!a;
 return Number(c);
 }

function con(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a && b;
 return Number(c);
 }

function dis(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a || b;
 return Number(c);
 }

writeln("A"+" " +"B"+" "+"C"+" "+
        "(⌝A∧⌝B∧⌝C)"+" "+
        "(⌝A∧B∧C)"+" "+"p(A,B,C)");
writeln("----------------------"+
        "--------------");

for(i=0;i<=1;i++) {
 for(j=0;j<=1;j++) {
  for(k=0;k<=1;k++) {
   var m1=con(neg(i),neg(j));
       m1=con(m1,neg(k));
   var m2=con(neg(i),j);
       m2=con(m2,k);
   var p=dis(m1,m2);
   writeln(i+" " +j+" "+k+"       "+
           m1+"          "+
           m2+"        "+p);
   }
  }
 }

writeln("----------------------"+
        "--------------");

A fenti logikai alapműveletek mellett három további logikai műveletet érdemes megismerni. Ezek a kizáró vagy, az implikáció és az ekvivalencia.

(4) kizáró vagy ("A XOR B", jele: A⨁B)

A kizáró vagy A⨁B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Igazságtáblázata a következő:

kizáró vagy
A B ( A ⨁ B )
0 0 0
0 1 1
1 0 1
1 1 0
A kizáró vagy műveletet az
A⨁B = (A∨B)∧⌝(A∧B)
vagy az
A⨁B = (A∧⌝B)∨(⌝A∧B)
azonosságokkal vissza tudjuk vezetni a korábban megismert logikai alapműveletekre.

(5) implikáció ("...-ból következik", jele: A⊃B, de előfordul az A⇒B jelölés is)

Az implikáció A⊃B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Igazságtáblázata a következő:

implikáció
A B ( A ⊃ B )
0 0 1
0 1 1
1 0 0
1 1 1
Az implikációt az
A⊃B = ⌝A∨B
azonossággal vissza tudjuk vezetni a korábban megismert logikai alapműveletekre.

(6) ekvivalencia ("ekvivalens", jele: A≡B)

Az ekvivalencia A≡B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Igazságtáblázata a következő:

ekvivalencia
A B ( A ≡ B )
0 0 1
0 1 0
1 0 0
1 1 1
Az ekvivalenciát az
A≡B = (A⊃B)∧(B⊃A)
vagy az
A≡B = (A∧B)∨(⌝A∧⌝B)
azonossággal vissza tudjuk vezetni a korábban megismert logikai alapműveletekre.

Végezetül jegyezzük meg, hogy az igazságértékeket tartalmazó H={0,1} alaphalmaz a fenti tulajdonságokkal rendelkező három logikai alapművelettel ún. Boole-algebrát alkot.


Az értéktáblázatok gyakorlása

1. feladat: Töltse ki az értéktáblázat harmadik oszlopát az oszlop fejrészében megadott formulának megfelelően!

p q p⊃q
0 0
0 1
1 0
1 1

Hibás válaszok száma: ?


2. feladat: Töltse ki az értéktáblázat utolsó oszlopát az oszlop fejrészében megadott formulának megfelelően! (A táblázat ötödik és hatodik oszlopa segédoszlop, amit a program az utolsó oszlop ellenőrzése során nem vesz figyelembe. Ezek kitöltése nem kötelező, de ajánlott, mivel az oszlopok kitöltése segíti a végső formula meghatározását.)

p q ⌝p ⌝q ? ? ?
0 0 1 1
0 1 1 0
1 0 0 1
1 1 0 0

Hibás válaszok száma: ?

Gyakorló feladatok

Igazolja értéktáblázattal és azonos átalakítások segítségével az alábbi logikai azonosságokat, ill. törvényeket!

Jelölések:
(1) Ha egy 'p' formula "azonosan igaz", vagyis logikai törvény, ezt ⊨ p módon jelöljük. Ha a 'p' formula logikai törvény, akkor p = ⊤ teljesül.
(2) Ha egy művelet után a '.' (pont) operátor szerepel, akkor az adott kifejezésben a ponttal jelölt műveletet utoljára kell végrehajtani. A pont operátor mindig helyettesíthető a kijelölt művelet elé és után írt zárójelekkel. Ennek megfelelően például a q∧r∨.p∧q kifejezés ekvivalens a (q∧r)∨(p∧q) kifejezéssel.
(3) A kizáró vagy műveletét (A⨁B) helyettesíthetjük a vele ekvivalens (A∧⌝B)∨(⌝A∧B) kifejezéssel.
(4) Az implikáció műveletét (A⊃B) helyettesíthetjük a vele ekvivalens ⌝A∨B kifejezéssel.
(4) Az ekvivalencia műveletét (A≡B) szintén helyettesíthetjük a vele ekvivalens (A∧B)∨(⌝A∧⌝B) kifejezéssel.


(a) p∧(p⊃q) = p∧q

Induljunk ki a bizonyítandó azonosság bal oldalából. Célunk az, hogy a korábbi logikai azonosságokat felhasználva olyan azonos átalakításokat végezzünk, amelynek végén eljutunk a bizonyítandó azonosság jobb oldalán szereplő logikai kifejezéshez:
    p∧(p⊃q) =  (implikáció helyettesítése)
    p∧(⌝p∨q) = 
    (p∧⌝p)∨(p∧q) = 
    ⊥∨(p∧q) = 
    p∧q (q.e.d)

(b) ⌝p∨(p∧q) = p⊃q

(c) q⊃(p∧q) = q⊃p

(d) p∧(⌝p⊃q) = p

(e) p∨⌝(p⊃q) = p

(f) (p⊃q)⊃p = p


(g)  ⌝p⊃(p⊃q) (ennek a logikai törvénynek a jelentése az, hogy "az ellentmondásból bármi következik", vö. Dragálin-Buzási 1986: 88)

Induljunk ki a bizonyítandó logikai törvényből. Célunk az, hogy a korábbi logikai azonosságokat felhasználva olyan azonos átalakításokat végezzünk, amelynek végén eljutunk a "szabvány igaz" (⊤) kijelentéshez:
    ⌝p⊃(p⊃q)  =  (→ implikáció kifejezése)
    ⌝p⊃(⌝p∨q)  =  (→ implikáció kifejezése)
    ⌝⌝p∨(⌝p∨q)  =  (→ kettős tagadás)
    p∨(⌝p∨q)  =  (→ asszociativitás)
    (p∨⌝p)∨q  =  (→ kizárt harmadik törvénye)
    ⊤∨q  =  (→ diszjunkció szabvány-igaz kijelentéssel)
    ⊤ (q.e.d.)

(h)  p⊃(q⊃p)

(i)  p⊃(q⊃.p∧q)

(j)  p∧(p⊃q)⊃.q

(k)  (p⊃q)∧⌝q⊃.⌝p


(l) A⨁B⨁C  =  (⌝A∧B∧⌝C) ∨ (A∧⌝B∧⌝C) ∨ (⌝A∧⌝B∧C) ∨ (A∧B∧C)
(A fenti kifejezés az egybites teljes összeadó által szolgáltatott összeget adja meg.)

(m) (A∧B∧C) ∨ (⌝A∧B∧C) ∨ (A∧⌝B∧C) ∨ (A∧B∧⌝C)  =  (A∧B) ∨ (A∧C) ∨ (B∧C)
(A fenti kifejezés az egybites teljes összeadó által szolgáltatott átvitelt adja meg.)
(Megjegyzés: mivel az egyszerűsítendő kifejezés t.d.n.f. alakban van, a levezetés a Karnaugh-tábla alapján könnyen megkapható.)



Examples of how to express and simplify various logic functions

A logikai alapműveletek (negáció, konjunkció és diszjunkció) segítségével minden logikai függvény kifejezhető. Az alapműveleteknek ezt a tulajdonságát úgy fejezzük ki, hogy a NOT, AND és OR logikai függvények funkcionálisan teljes rendszert alkotnak.

A kapuáramkörök technológiai megvalósítása szempontjából lényeges, hogy mind a NAND logikai függvény, mind pedig a NOR logikai függvény egymagában is teljes rendszert alkot.

A NAND művelet A NAND B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Definíció szerint
A NAND B ⇋ ⌝(A∧B)
teljesül, tehát igazságtáblázata a következő:

NAND
A B ⌝(A∧B)
0 0 1
0 1 1
1 0 1
1 1 0

A NOR művelet A NOR B:{0,1}Χ{0,1}→{0,1} módon leírható kétváltozós logikai függvény. Definíció szerint
A NOR B ⇋ ⌝(A∨B)
teljesül, tehát igazságtáblázata a következő:

NOR
A B ⌝(A∨B)
0 0 1
0 1 0
1 0 0
1 1 0

Legyenek A és B logikai változók; ekkor az alapműveletek kifejezhetők a NAND és NOR műveletek segítségével:

A továbbiakban az egyszerűség kedvéért a korábban bevezetett három alapműveletet (NOT, AND és OR) fogjuk használni. Ezek funkcionálisan teljes rendszert alkotnak, vagyis bármilyen logikai függvény kifejezhető a segítségükkel. Nézzük meg, hogyan.


Define a three-variable Boolean function p(A,B,C) with its truth table:

(refresh: CRTL R)
A B C p(A,B,C)

Using the basic logical operations AND, OR and NOT, one of the possible productions of the Boolean function p(A,B,C) given by the truth table shown above is as follows:

p(A,B,C) = 

The above production of the Boolean function p(A,B,C) is called disjunctive normal form (DNF). In the DNF there are
– several conjunctive expressions called minterms (e.g. (ABC), (⌝ABC) etc.)
– connected with disjunctions (e.g. (A∧B∧C) (⌝A∧B∧C) etc.).

The number of minterms equals with the number of those rows in the truth table where the value of the p(A,B,C) function is true, i.e. where p(A,B,C)=1 for a given combination of the variables A, B and C.

We assign a corresponding minterm to each row in the truth table where the the value of the p(A,B,C) function is true. In a given minterm the form of each logical variable depends on its value in the row to which the minterm is assigned; e.g. for the row where (A,B,C)=(1,0,1) the corresponding minterm is (A∧B∧C) etc.


Általánosítva a fenti alakot, az igazságtáblázattal megadott három változós
p(A,B,C)
függvény teljes diszjunktív normálformáját (t.d.n.f.) a függvény igazságtáblázatából a következőképpen állíthatjuk elő:

(0) A táblázat első három oszlopában szereplő A, B és C logikai változók bármelyikét jelöljük X-szel.
(1) A táblázat minden sorának, amelyben a p(A,B,C) függvény értéke 1 (azaz a táblázat jobb szélső oszlopában 1 szerepel), megfeleltetünk egy ún. elemi konjunkciót, amelyet az alábbi tényezők konjunkciójaként állítunk elő:
– az elemi konjunkció tényezője lesz a függvény minden olyan X logikai változója, amelynek az (adott sornak megfelelő) oszlopában 1 található, és
– az elemi konjunkció tényezője lesz a függvény minden olyan X logikai változójának ⌝X negáltja, amelynek (az adott sornak megfelelő) oszlopában 0 található.
(2) A p(A,B,C) függvény t.d.n.f. előállítását a fenti módon előállított elemi konjunkciók diszjunkciója adja.

Összefoglalva:
(1.a) Minden elemi konjunkció X∧Y∧Z alakú, ahol
    X vagy A vagy ⌝A,
    Y vagy B vagy ⌝B,
    Z vagy C vagy ⌝C,
attól függően, hogy az A, B és C logikai változók oszlopában 1 vagy 0 logikai érték szerepel.
(1.b) Annyi elemi konjunkció van, ahány 1 érték szerepel a p(A,B,C) függvény értékeinek az oszlopában (azaz az igazságtáblázat utolsó, jobb szélső oszlopában).
(2) A keresett t.f.n.f. alakot az elemi konjunkciók diszjunkciója adja.

Szemléletesen megfogalmazva:
– egy logikai függvény értéke akkor és csak akkor igaz, ha t.d.n.f. alakjában van olyan elemi konjunkció, amelyik igaz;
– egy elemi konjunkció pedig akkor és csak akkor igaz, ha minden tényezője igaz.

Megjegyzések:
– Az elemi konjunkciók egy másik szokásos elnevezése minterm.
– A mintermekben nem negált alakban előforduló logikai változók ún. ponált alakban fordulnak elő. Ennek megfelelően egy mintermben minden logikai változónak elő kell fordulnia vagy ponált, vagy negált alakban.

A logikai függvények t.d.n.f. alakját a legtöbb esetben algebrai átalakításokkal egyszerűbb alakra hozhatjuk, felhasználva a logikai műveletek alaptulajdonságait. Tipikus példa erre az ún. szomszédos mintermek vagy általánosan a szomszédos termek egyszerűsítése.

Ha például a t.d.n.f. alakban a ... ∨ (⌝A∧⌝B∧⌝C) ∨ (⌝A∧B∧⌝C) ∨ ... kifejezés fordul elő, akkor először is vegyük észre, hogy az A és B logikai változók sorrendjétől eltekintve a (⌝A∧⌝C) konjunktív kifejezés az egymással diszjunkcióban levő mindkét mintermben előfordul, miközben a termeket egymástól kizárólag a 'B' változó különbözteti meg. A mindkét mintermben előforduló közös konjunktív kifejezést kiemelve a kifejezést átalakíthatjuk a következőképpen:
... ∨ (⌝A∧⌝B∧⌝C) ∨ (⌝A∧B∧⌝C) ∨ ...=
... ∨ [(⌝A∧⌝C) ∧ (⌝B∨B)] ∨ ...=
... ∨ [(⌝A∧⌝C) ∧ ⊤] ∨ ...=
... ∨ (⌝A∧⌝C) ∨ ...
Ez nyilvánvaló egyszerűsítést jelent, mivel a kiindulásként adott két szomszédos mintermből kiiktattuk a 'B' változót. Vegyük észre, hogy a kifejezés már az első lépés után is egyszerűsödött, mivel az eredeti kifejezésben öt AND-OR művelet, az átalakított kifejezésben viszont már csak három AND-OR művelet szerepelt. A 'B' megkülönböztető változó eltűnése után kapott egyszerűsített kifejezés pedig már csak egy AND műveletet tartalmazott.

A szomszédos mintermek egyszerűsíthetők a bennük közösen előforduló változók vagy konjunktív kifejezések kiemelésével, ami a termeket egymástól megkülönböztető változó eltűnéséhez vezet.

A szomszédos mintermek grafikus megjelenítésére szolgálnak az ún. Karnaugh-táblák. Ennek megjelenítéséhez rendezzük át a korábbi igazságtáblázatot a következőképpen:

(megjelenített formula)
A B C
0 1

A táblázatban csak a megjelenített formula mintermjeit tüntetjük fel. (Jegyezzük meg, hogy az "eredeti" Karnaugh-táblákban nem a mintermek szerepelnek, hanem helyettük egyszerűen 1 értékek.)

A szomszédos mintermek a Karnaugh-táblázatokban háromféleképpen jelenhetnek meg:

Ha több formula esetén is kipróbáljuk az egyszerűsítést, észrevehetjük, hogy a Karnaugh-tábla alapján a megjelenített formula rendszerint többféleképpen is egyszerűsíthető.

Ha a táblázatban két-két szomszédos cellának van közös oldala, akkor az egyszerűsített mintermek maguk is tovább egyszerűsíthetők, azaz ilyen esetekben két logikai változó is kiiktatható. Például az alábbi Karnaugh-tábla alapján az
példa egyszerűsítésre a Karnaugh-tábla alapján
p(A,B,C) =
(⌝A∧B∧⌝C) ∨ (⌝A∧B∧C) ∨ (A∧B∧⌝C) ∨ (A∧B∧C) =
(⌝A∧B) ∨ (A∧B) =
B
egyszerűsítés hajtható végre.

Ha a Karnaugh-táblában a szomszédos mintermek átfedik egymást, mindkettő alapján egyszerűsíthetünk. Például tekintsük az alábbi Karnaugh-táblázatot:
példa egyszerűsítésre a Karnaugh-tábla alapján
p(A,B,C) =
(⌝A∧⌝B∧C) ∨ (⌝A∧B∧⌝C) ∨ (⌝A∧B∧C) =
(⌝A∧⌝B∧C) ∨ (⌝A∧B∧C) ∨ (⌝A∧B∧⌝C) ∨ (⌝A∧B∧C) =
(⌝A∧C) ∨ (⌝A∧B)
Figyeljük meg, hogy a (⌝A∧B∧C) mintermet megkettőztük (amit a logikai 'vagy' művelet idempotenciája alapján megtehetünk).

Próbáljunk meg néhány t.d.n.f. alakú kifejezést egyszerűsíteni az alábbi, interaktívan kitölthető Karnaugh-tábla segítségével. Az egyszerűsítendő logikai függvény mintermjeinek megadásához kattintsunk a megfelelő cellára (egy megjelenített minterm eltüntetéséhez pedig a megfelelő mintermre kattintsunk):

interaktív Karnaugh-tábla
A B C
0 1
0 0 0 0
0 1 0 0
1 1 0 0
1 0 0 0

Ha például a táblázatban kijelölt celláknak megfelelő logikai függvény

p(A,B,C) = (A∧B∧C) ∨ (⌝A∧B∧C) ∨ (A∧⌝B∧C) ∨ (A∧B∧⌝C)

alakú, akkor először jelenítsük meg a függvény mintermjeit a fenti Karnaugh-táblában, majd alakítsuk át a p(A,B,C) logikai függvényt a megfelelő változók kiiktatásával.

(1) Először adjuk a kifejezéshez még kétszer hozzá az (A∧B∧C) kifejezést, mivel a Karnaugh-táblában három "szomszédja" is van (ezt megtehetjük az ∨ művelet idempotenciája miatt, ugyanis A~A∨A tetszőleges 'A' logikai kifejezés esetén igaz):
p(A,B,C) =
(A∧B∧C) ∨ (⌝A∧B∧C) ∨
(A∧B∧C) ∨ (A∧⌝B∧C) ∨
(A∧B∧C) ∨ (A∧B∧⌝C)

(2) Ezután iktassuk ki a megfelelő kifejezések kiemelésével először az 'A', majd a 'B', és végül a 'C' változókat:
p(A,B,C) = (B∧C) ∨ (A∧C) ∨ (A∧B)

(3) Végül rendezzük át a kifejezést:
p(A,B,C) = (A∧B) ∨ (A∧C) ∨ (B∧C)

Az így kapott kifejezés a p(A,B,C) logikai függvény legegyszerűbb alakja.

Ha egy logikai kifejezést logikai kapuáramkörök segítségével akarunk megvalósítani, a kifejezés egyszerűsítése lehetővé teszi, hogy kevesebb áramkört kelljen használnunk.


Kapuáramkörök

A számítógép egy műszakilag megvalósított rendszer, amelynek a legfontosabb eleme a számítógép központi egysége, ezen belül a központi feldolgozó egysége (CPU), amely a számítógép programozott működését hardver szinten megvalósítja, ill. vezérli (metaforikusan kifejezve a működés alapvető "logikáját" szolgáltatja).

A CPU működésének elvi szintű megértéséhez az első lépés azoknak az alapáramköröknek a megismerése, amelyekből komplex logikai hálózatokat tudunk felépíteni. Ezek a hálózatok teszik lehetővé, hogy a CPU képes legyen a számítógép működése szempontjából alapvető feladatok elvégzésére (például az éppen futó program utasításainak beolvasására, az utasítások értelmezésére és végrehajtására, a megfelelő műveletek elvégzésére, szükség esetén a futó programok megszakítására stb.).

Összetett, komplex logikai függvényeket megvalósító rendszereknél (és a számítógépek túlnyomó többsége ilyen), "nem célszerű egyetlen, ugyancsak bonyolult logikai hálózatot tervezni. Előnyösebb, ha ilyenkor a bonyolult logikai feladatot több, de önmagukban viszonylag egyszerű logikai hálózat létrehozásával, azok összehangolt működtetésével oldjuk meg. A logikai hálózatoknak az így kialakuló rendszere alapján bevezethetjük a logikai rendszer fogalmát." (Arató 1996: 18)

Egy logikai rendszerben az egyes részfeladatokat végző funkcionális egységek vezérlését egy ún. vezérlő egységgel kell biztosítanunk. A vezérlő egységet megvalósíthatjuk például egy olyan logikai hálózattal, amely a megfelelő vezérlő jelek kiadásával hangolja össze és ütemezi a funkcionális egységek működését:
(1) A vezérlő jeleket a vezérlő egység meghatározott logikai feltételek teljesülése esetén adja ki; a logikai feltételeket meghatározó logikai értékek származhatnak
    ○ az (egy vagy többfázisú) órajelgenerátor által kiadott órajelekből,
    ○ más funkcionális egységek vagy áramkörök által kiadott vezérlő jelekből (például egy kétállapotú gomb kimenetéből, a megszakításvezérlő egység kimeneteiből stb.),
    ○ a vezérlő egység, ill. a funkcionális egységek belső állapotát tároló regiszterekből (például az állapotregiszterből, a megszakításregiszterből, a fázisregiszterből stb.),
    ○ stb.
(2) A vezérlő egység által kiadott vezérlő jelek végzik a funkcionális egységek vezérlését (például szinkron sorrendi hálózatok esetén az órajelek engedélyezik vagy tiltják azoknak a tároló áramköröknek ("flip-flopoknak") a működését, amelyek a bemeneteket, a belső állapotokat, a kimeneteket stb. tárolják).

Egy logikai hálózat vagy egy logikai rendszer funkcionális egységeinek működését meghatározott vezérlő jelek segítségével vezérelhetjük. (Ilyenek lehetnek például az órajelek, a vezérlő áramkörök kimenetei, egyes tárolók vezérlőjelként értelmezett értékei stb.)

Függetlenül technikai megvalósításuktól, a kapuáramkörök olyan fekete dobozoknak tekinthetőek, amelyekben az inputot és az outputot jelentő feszültségjelek a logikai 0 és 1 állapotoknak felelnek meg. Ebben az értelemben egy kapuáramkör egy adott logikai műveletet reprezentál. A kapuáramkör bemenetét az adott logikai művelet független változóinak lehetséges értékei ("kombinációi") adják, a kapuáramkör kimenete pedig az adott logikai művelet eredménye lesz.

A kapuáramkörök, valamint a bemenetükön, ill. kimenetükön megjelenő bináris jelek szemléltethetőek olyan áramkörök ("kapcsolások") segítségével, amelyek csak telepeket, mechanikus kapcsolókat és izzólámpákat tartalmaznak (vö. pl. Urbán 1987: 14-22). Érdemes megjegyeznünk, hogy ha mechanikus kapcsolók helyett elektromechanikus, kivülről elektromos jelekkel vezérelhető kapcsolókat (jelfogókat vagy reléket) használunk, akkor nemcsak a kapuáramkörök, hanem összetett logikai hálózatok is kialakíthatók (elvileg akár egy programvezérelt számítógép is).

A kapuáramkörök tényleges kialakítása számos módon lehetséges. Korábban például telefonreléket, elektroncsöveket, diódákat ill. tranzisztorokat használtak. Ezek közül a tranzisztorok kiemelt jelentőségűek, mivel ezek képezik az alapját a napjainkban használt integrált áramköröknek, amelyekből a modern digitális elektronikus számítógépek felépülnek.

A mai számítógépekben nagy bonyolultságú (ún. VLSI) integrált áramkörökben, "chipekben" hozzák létre a kapuáramköröket és a belőlük kialakított összetett logikai hálózatokat.

Using only electromechanical relays we can (at least theoretically) implement any logic function. For example the simple circuit below
The implementation of the AND logic function with relays
implements the AND logic function. Note that if we change the voltage levels of the contacts of the relay's switches as in the circuit below
The implementation of the NOR logic function with relays
we can easily get the NOR logic function.

In the following, we briefly discuss the issue of how transistors work.

A transistor is a semiconductor device that usually contains three terminals or electrodes; in the case of an npn or pnp type bipolar transistor, these are called emitter, base and collector. The transistor is one of the basic building blocks of modern electronics. It is composed of doped semiconductor material. For example, when silicon (whose valency is 4) is doped with a very small amount of phosphorus (whose valency is 5) we get an n-type semiconductor; and when silicon is doped with boron (whose valency is 3) we get a p-type semiconductor.

The major aim of doping silicon is to change its electrical and other properties. For example, the conductivity of silicon can be increased by adding a small amount (of the order of 1 in 108) of doping elements or dopants like pentavalent (antimony, phosphorus, or arsenic) or trivalent (boron, gallium, indium) atoms.

The basic idea behind the transistor is that it lets you control the flow of current between two electrodes by varying the intensity of the voltage which is imposed on and the current which is flowing through the third electrode.
The device is capable of current or voltage amplification. In that case the intensity of the control signal is much smaller than the controlled one.

With respect to digital circuits, it is much more important that the transistor can be used as an electronic switch to open or close the controlled circuit depending on the electrical signal transmitted through the base of the transistor.
The TRANSISTOR IS A FAUCET metaphor in picture form

We will no longer deal with the technical implementation of logic gates. But remember that using only the NOR logic function we can build up any logic function (however complex they are).


Tárgyalásunk szempontjából alapvető, hogy a logikai alapműveletek megvalósíthatók digitális áramkörök, ún. kapuáramkörök segítségével.

A logikai alapműveleteket megvalósító kapuáramköröket például az alábbi szimbólumokkal ábrázolhatjuk:


AND:
vagy


OR:
vagy


NOT:
vagy
vagy vagy


Korábban láttuk, hogy a logikai alapműveletek segítségével minden logikai függvény kifejezhető. Ennek megfelelően a kapuáramkörök megfelelő összekapcsolásával tetszőleges logikai függvény műszakilag megvalósítható.

A kapuáramkörök összekapcsolásával létrehozott logikai hálózatok elvileg bármilyen logikai függvény műszaki megvalósítását lehetővé teszik.

Példa: egy egyszerű egybites összeadó, ún. félösszeadó áramkör igazságtáblázata és kapuáramkörökkel történő megvalósítása (HA, half adder; vö. Wikipédia, Sulinet Tudásbázis):

A fenti igazságtábla két egybites szám (A és B) összegét adja meg (S), valamint az összeadáskor fellépő maradékot (C). Az igazságtáblázat alapján a félösszeadót megvalósító logikai függvények t.d.n.f. alakja a következő:

S = ( ⌝A ∧ B ) ∨ ( A ∧ ⌝B ) = A⨁B és
C = ( A ∧ B )

Figyeljük meg, hogy a félösszeadó kapuáramkörökkel történő megvalósítása során
(1) a ⌝A és ⌝B jeleket egy-egy NOT kapuval állítjuk elő,
(2) a három AND kapu bemeneteit vagy közvetlenül a félösszeadó valamelyik bemenetéről (A és B), vagy valamelyik NOT kapu kimenetéről (⌝A és ⌝B) állítjuk elő,
(3) az összeget (S) egy OR kapu állítja elő, amelynek a bemenetét két AND kapu kimenete szolgáltatja, és
(4) az átvitelt a magasabb helyi értékek felé (C) egy AND kapu állítja elő, amelynek a bemenetét közvetlenül a félösszeadó bemenetei (A és B) szolgáltatják.


A félösszeadó működésének ismeretében felépíthető egy több bites bináris összeadó (ún. teljes összeadó). Ha a félösszeadó igazságtáblázatát egy oszloppal kibővítjük, amely az előző helyi értékről származó átvitelt (Ci vagy cin) tartalmazza, az ún. egybites teljes összeadó igazságtáblázatát kapjuk:

Az egybites teljes összeadó igazságtáblázatában

Feladat:
Valósítsuk meg az igazságtábla alapján az egybites teljes összeadót (FA, Full Adder). Az összeadás megszokott algoritmusát alkalmazva a feladat két félösszeadóval (HA, Half Adder) könnyen megoldható:

Ellenőrizzük a fenti logikai áramkör működését egy igazságtáblázattal, amelyben az ábrán jelölt logikai értékeket ábrázoljuk:

egybites teljes összeadó igazságtáblázata
A B C=Cin Stmp Ctmp S Csec Cout
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0
1 0 0 1 0 1 0 0
1 1 0 0 1 0 0 1
0 0 1 0 0 1 0 0
0 1 1 1 0 0 1 1
1 0 1 1 0 0 1 1
1 1 1 0 1 1 0 1

Ellenőrzésként vessük össze a táblázat első három oszlopának, valamint a pirossal és sárgával kijelölt oszlopoknak az értékeit az egybites teljes összeadó korábban elkészített igazságtáblázatával.

Az egybites teljes összeadó kimenetének leírása logikai függvényekkel:
S(A,B,C) = (⌝A∧B∧⌝C) ∨ (A∧⌝B∧⌝C) ∨ (⌝A∧⌝B∧C) ∨ (A∧B∧C) = A⨁B⨁C
Cout(A,B,C) = (A∧B∧⌝C) ∨ (⌝A∧B∧C) ∨ (A∧⌝B∧C) ∨ (A∧B∧C) = (A∧B) ∨ (A∧C) ∨ (B∧C)

Az egybites teljes összeadó áramkörök összekapcsolásával pedig könnyen megvalósíthatunk egy 'n' bites teljes összeadót. Például az alábbi ábrán egy 4 bites teljes összeadó látható (vö. Wikipédia, Sulinet Tudásbázis).

Vegyük észre, hogy a kép valamilyen oknál fogva nem a szokásos, balról jobbra történő jelterjedési irányt ábrázolja, hanem pont fordítva (azaz az álló helyzetben megjelenített ábra jobbról balra "olvasandó".)

Jegyezzük meg, hogy

A túlcsordulás rendszerint azt jelzi, hogy adott számú bit esetén az összeadás nem végezhető el, mivel a kapott összeg több bitből áll, mint a számok ábrázolására vagy tárolására rendelkezésre álló bitek száma. (Például 11012+10002=101012 esetén az összeadandók 4 bitesek, az összeg viszont 5 bites.)

Emeljük ki, hogy a példákban szereplő logikai hálózatok esetében
(1) a kimenet kizárólag a bemenetre adott jelektől függ, és
(2) ideális esetben feltételezzük, hogy a kimeneti jelek a bemeneti jelek hatására "azonnal" (azaz késleltetés nélkül) megjelennek.

A kapuáramkörök felhasználásával interaktívan különböző logikai hálózatokat alakíthatunk ki az alábbi internetes címeken:

Logic Gate Simulator | Academo.org – Free, interactive, education.
https://academo.org/demos/logic-gate-simulator/ (2022-11-19)

simulator.io - Build and simulate logic circuits.
https://simulator.io/ (2022-11-19)

Gyakorló feladatok

Hozzunk létre kombinációs hálózatokat, amelyek az alábbi logikai függvényeket valósítják meg ("realizálják"). Ahol lehet, próbáljuk meg egyszerűsíteni is a függvényeket! (vö. Fodor-Nagy 1982: 82-90):

(a) p(A,B)=(A∧⌝B) ∨ (⌝A∧B)

(b) p(A,B,C)=(A∧B∧⌝C) ∨ (A∧⌝B∧C) ∨ (A∧B∧C)

(c) p(A,B,C)=(A∧B) ∨ (⌝A∧B∧C) ∨ (⌝A∧B∧⌝C)

(d) p(A,B,C)=(A∧B) ∨ (⌝A∧⌝B) ∨ (A∧C)

(e) p(A,B,C)=(A∧B) ∨ (⌝A∧⌝B∧C) ∨ (⌝A∧B∧⌝C)

(f) p(A,B,C,D)=((A∧B∧C) ∨ ⌝B) ∧ ⌝D



Logikai hálózatok

Láttuk, hogy a számítógépet fekete doboznak tekintve a számítógép működését elvi szinten egy megfelelő függvény (ill. függvények) segítségével adhatjuk meg. Korábban utaltunk rá, hogy a függvény értéke a bemenetek mellett függhet a számítógép korábbi működése során előállított és/vagy tárolt adatoktól is.

A továbbiakban azzal a kérdéssel foglalkozunk, hogy hogyan tudunk megvalósítani kapuáramkörök segítségével egy
p(x1,x2,...,xn):{0,1}Χ{0,1}Χ...Χ{0,1}→{0,1}
'n' változós logikai függvényt.

Több logikai függvény használata esetén használhatjuk a korábbi p1, p2, ..., pn jelöléseket. A számítógép elvi működésének leírásához nyilvánvalóan több logikai függvényre van szükségünk, de ennek most nincs különösebb jelentősége, mivel ha egy tetszőleges 'p' logikai függvényt meg tudunk műszakilag valósítani, ezt akárhány logikai függvény esetében ugyanúgy megtehetjük.

A fenti 'p' logikai függvényt műszakilag egy meghatározott alapáramkörökből felépülő logikai hálózattal tudjuk megvalósítani. Attól függően, hogy
– a 'p' logikai függvény értékének meghatározásához elegendők pusztán a függvény független változóinak az értékei, vagy pedig
– a függvény értékének meghatározásához szükség van a független változók értékén kívül további adatokra, "rejtett paraméterekre" is,
a számítógép működésének műszaki alapját képező logikai hálózatok két típusáról beszélhetünk:

Egy sorrendi logikai hálózatot egy olyan kombinációs hálózatnak tekinthetünk, amely visszacsatolást tartalmaz, vagyis a kimenet egyértelmű meghatározásához ismernünk kell a bemeneti kombinációk mellett olyan szekunder értékeket ("kombinációkat") is, amelyeket a hálózat korábbi működése során állított elő (és közvetlenül vagy tárolás után visszacsatolta ezeket az értékeket a hálózat bemenetére).

A sorrendi hálózatok két fajtáját különböztetjük meg:

Aszinkron hálózatra példa egy két állapotú statikus tárolóáramkör (ún. flip-flop); szinkron hálózatra pedig egy soros bináris összeadó, amely meghatározott ütemezésben kapja meg az összeadandók adott helyi értékű bináris számjegyeit, állítja elő az egyes helyi értékeken képződő átvitelt, és az összeg megfelelő helyi értékű bináris számjegyeit (vö. Arató 1996: 17-18, 139-141 et passim; Könyves Tóth 1982: 105-106 et passim).


1. példa: R-S flip-flop (NOR kapukkal megvalósítva)

Az R-S flip-flop egy 1 bites tárolóáramkör, amelyet NOR kapukkal a következőképpen alakíthatunk ki:

Aszinkron R-S flip-flopot megvalósító visszacsatolt kombinációs hálózat NOR kapukkal megvalósítvaAszinkron R-S flip-flop jelölése fekete dobozként

Az ábra jelölései:

Mivel a Q' és Q' kimeneteket visszacsatoljuk (Q←Q', QQ'), a visszacsatolt értékek a flip-flop R és S bemenetei mellett szekunder adatokként befolyásolják a flip-flop Q' és Q' kimeneteit.

Az R-S flip-flop működését leíró logikai függvény az alapműveletekkel
    Q'= f(R,S,Q)= S∨(⌝R∧Q)
módon írható fel. A függvényt NAND művelettel megvalósítva a
    Q'= (S NAND S) NAND ((R NAND R) NAND Q)= S∨(⌝R∧Q)
függvényt kapjuk. Ha a függvényt NOR művelettel valósítjuk meg, ez például a
    Q'= R NOR (S NOR Q)= (⌝R∧S)∨(⌝R∧Q)
függvénnyel lehetséges.
Jegyezzük meg, hogy a NOR művelettel kifejezett függvény R=1 és S=1 esetén eltérő eredményt szolgáltat, mint a másik két függvény.

Írassuk ki a fenti logikai függvények igazságtáblázatát egy JavaScript program segítségével:

// R-S flip-flop igazságtáblázatai (visszacsatolás nélkül)

function neg(x) {
 var a=Boolean(x);
 var c=!a;
 return Number(c);
 }

function kon(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a && b;
 return Number(c);
 }

function dis(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a || b;
 return Number(c);
 }

function nand(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=!(a && b);
 return Number(c);
 }

function nor(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=!(a || b);
 return Number(c);
 }

writeln("R"+" " +"S"+" "+"Q"+"  "+
        "S∨(⌝R∧Q)"+" "+"(R NOR (S NOR Q))"+" "+
        "(⌝S NAND (⌝R NAND Q))");
writeln("------------------------------"+
        "--------------------------");

for(i=0;i<=1;i++) {
 for(j=0;j<=1;j++) {
  for(k=0;k<=1;k++) {
   var m=kon(neg(i),k);
       m=dis(j,m);
   var n=nor(j,k);
       n=nor(i,n);
   var s=nand(j,j);
   var p=nand(i,i);
       p=nand(p,k);
       p=nand(s,p);
   writeln(i+" " +j+" "+k+"      "+m+
           "             "+n+
           "                   "+p);
   }
  }
 }

writeln("------------------------------"+
        "--------------------------");

A program képernyőképe a következő:

Az R-S flip-flop igazságtáblázatai különböző műveletekkel megvalósítva

A visszacsatolásokat figyelembe véve a NOR műveletekkel megvalósított R-S flip-flop kimeneti értékeit a következő algoritmussal számíthatjuk ki:

  1. Kiindulásként az R S és Q bemenetekhez rendeljünk adott értékeket (azaz ne vegyük figyelembe a Q←Q' visszacsatolást); tároljuk Q kezdeti értékét (Q0=Q); tároljuk a kiszámítási ciklusok számát is (n=0) A NOR kapus R-S flip-flop rajza a gerjesztési tábla elkészítéséhez
  2. Számítsuk ki Q' értékét a
    Q' = ⌝(S∨Q)
    képlet alapján
  3. vegyük figyelembe a QQ' visszacsatolást, és Q=Q' feltétel mellett számítsuk ki Q' értékét a
    Q' = ⌝(R∨Q)
    képlet alapján
  4. rögzítsük, hogy egy számítási ciklus véget ért (n=n+1); ezután tároljuk Q kiszámított értékét (Qn=Q'), vegyük figyelembe a Q ← Q' visszacsatolást, és
  5. folytassuk az algoritmust az alábbiak szerint:
    • ha Q értéke a számítási ciklus után megegyezik az előző értékével (Qn=Qn−1), álljunk meg (stabil állapothoz jutottunk)
    • ha n=1 és Q értéke az első számítási ciklus után nem egyezik meg az előző értékével (Q1≠Q0), folytassuk az algoritmust a 2. lépéstől kezdve (átmeneti állapothoz jutottunk)
    • ha n=2 és Q értéke a második számítási ciklus után megegyezik a kezdeti értékével (Q2=Q0), ne folytassuk tovább az algoritmust, mert Q értéke innentől kezdve állandóan váltakozni fog (instabil állapothoz jutottunk)

Az igazságtáblát ezek után úgy tudjuk megkonstruálni, hogy az S és R bemenetek lehetséges értékei mellett a Q kimenet lehetséges kezdeti értékeit is felvesszük a táblázatba, és ennek megfelelően számítjuk ki az R-S flip-flop kimenetét.

A fenti algoritmus alapján az R-S flip-flop igazságtáblázata a következő lesz:

R-S flip-flop
R S Q=Qn Q'=Qn+1
0 0 0 0 (=Qn) Q értéke változatlan (előzőleg beállított 0 vagy 1 állapot tárolása) R-S flip-flop 0-0-0 állapota R-S flip-flop 0-0-1 állapota
1 1 (=Qn)
0 1 0 1 SET (1 beállítása, "flip") R-S flip-flop 0-1-0 állapota R-S flip-flop 0-1-1 állapota R-S flip-flop 0-1 állapotai
1 1 (=Qn)
1 0 0 0 (=Qn) RESET (0 beállítása, "flop"; a flip-flop törlése) R-S flip-flop 1-0-0 állapota R-S flip-flop 1-0-1 állapota R-S flip-flop 1-0 állapotai
1 0
1 1 0 0 (=Qn) (tiltott állapot, mivel mindkét kimenet 0 értékű lesz) R-S flip-flop 1-1-0 állapota R-S flip-flop 1-1-1 állapota
1 0

Az R-S flip-flop NOR kapukkal megvalósított formájában a flip-flop két kimenetétől elvárjuk, hogy egymás negáltjai legyenek (azaz Q=⌝Q teljesüljön). Az R-S flip-flop NOR kapus megvalósításában ez S=1 és R=1 esetén nem áll fenn (mivel Q=Q teljesül), ezért ezt az állapotot nem engedjük meg.

Az R-S flip-flop NOR kapukkal megvalósított formájában az S=1 és R=1 kombináció tiltott.

Az RS flip-flop korábban megismert kiszámítási algoritmusa alapján a következő esetek lehetségesek:

Az R-S flip-flop teljes igazságtáblázata ennek megfelelően (a visszacsatolásokat is feltüntetve) a következő lesz, ha NOR kapukkal valósítjuk meg:

R-S flip-flop (NOR)
S R Q ⌝(S∨Q)=Q'→Q ⌝(Q∨R)=Q'→Q ellenőrzés: Q=Q'?

Jegyezzük meg, hogy mivel R=0 és S=0 bemenetek mellett az R-S flip-flop a korábban beállított logikai értéket tárolja, a bemeneteket egy órajellel kapuzva csak akkor változhat meg az R-S flip-flop állapota, ha ezt az órajel engedélyezi.

Ha az R-S flip-flop bemenetét egy órajellel (C) vezéreljük, egy ún. szinkron R-S flip-flop áramkört kapunk:

Szinkron R-S flip-flop visszacsatolt NOR kapukkal megvalósítva

Ha pedig a szinkron R-S flip-flop 'R' bemenetét egy inverter (azaz NOT kapu) segítségével állítjuk elő, egy ún. D flip-flop áramkört kapunk:

D flip-flop visszacsatolt NOR kapukkal megvalósítva

A D flip-flop előnye, hogy megszünteti az R-S flip-flop tiltott állapotát (vagyis nem fordulhat elő az R=1 és S=1 bemenet).


2. példa: R-S flip-flop (NAND kapukkal megvalósítva)

Az R-S flip-flopot megvalósíthatjuk NAND kapukkal is:

Aszinkron R-S flip-flopot megvalósító visszacsatolt kombinációs hálózat NAND kapukkal megvalósítva

Az R-S flip-flop igazságtáblázata a következő:

R-S flip-flop (NAND)
S R y q=⌝(⌝R∧y) Y=⌝(S∧q) (ellenőrzés)

Ha ebben a megvalósításban is két kimenetet szeretnénk (mint a NOR kapukkal megvalósított R-S flip-flop esetén), akkor a tiltott S=1 és R=1 kombinációk elkerülése érdekében célszerű az Y kimenetből egy inverter segítségével közvetlenül előállítani a negált ⌝Y értéket.

Vegyük észre, hogy ha megengedjük az S=1 és R=1 kombinációt, akkor az Y kimenet megegyezik az S=1 és R=0 kombinációnak megfelelő bemenettel, azaz 1 tárolása történik meg. (Ebben az esetben a flip-flopot S-dominánsnak nevezzük, mert ha S=1 teljesül, akkor az R bemenet értékétől függetlenül a flip-flop tárolni fogja az 1 értéket.)


3. példa: Master-Slave J-K flip-flop

A korábban tárgyalt R-S flip-flop áramkörök "hátránya, hogy az órajel ideje alatt a bemeneti vezérlés megváltozása megjelenik a kimeneten. A jelenségre azt szokták mondani, hogy a flip-flop átlátszik. Ez azt jelenti, hogy tárolónk egy óraütemben több állapotváltozást is végrehajthat. Az ebből eredő hátrány összetett hálózatokban jelentkezik, amikor ugyanazon órajellel több, egymást vezérlő tárolót kapuzunk" (Takács 1995: 40).

Ezt a hátrányt küszöböli ki a master-slave (MS) J-K flip-flop, amely egy kétütemű, élvezérelt tároló. A J-K flip-flop úgy működik, hogy
– az órajel megjelenésekor, azaz az órajel "felfutó" élének hatására a bemeneti jelet elhelyezi egy ún. előtárba (master);
– az órajel eltűnésekor, azaz az órajel "lefutó" élének hatására az előtárban tárolt jelet átírja egy ún. főtárba (slave).
A főtárban tárolt információ fog megjelenni a flip-flop kimenetén. (vö. Takács 1995: 40-41)

Az MS J-K flip-flop egy 1 bites tárolóáramkör, amelyben két, egymás után következő R-S flip-flopot egy órajellel vezérlünk. Az MS J-K flip-flop elvi kialakítása a következő:

Szinkron, órajellel vezérelt MS J-K flip-flopot megvalósító visszacsatolt kombinációs hálózat

A J-K flip-flop igazságtáblázata a következő:

J-K flip-flop
J K Qn+1 Qn+1
0 0 Qn Qn
0 1 0 1
1 0 1 0
1 1 Qn Qn

Jegyezzük meg, hogy a J-K flip-flop 'J' bemenete az R-S flip-flop 'S' bemenetének, a J-K flip-flop 'K' bemenete pedig az R-S flip-flop 'R' bemenetének felel meg.

Az MS J-K flip-flop igazságtáblázata nyilvánvalóan függ a flip-flopban levő R-S flip-flopok által tárolt értékektől (azaz az MS J-K flip-flop belső állapotaitól). Az ábrából látszik, hogy az MS J-K flip-flop működése során az órajel hatására a Master R-S flip-flop tartalma mindig átmásolódik a Slave R-S flip-flopba. Az MS J-K flip-flop által tárolt értéket a Slave R-S flip-flop tartalma adja, amely a tárolt információ átírása után megegyezik a Master R-S flip-flop tartalmával. (Jegyezzük meg, hogy ha ez nem állna fenn, azaz a kiinduló állapotban a Slave R-S flip-flop és a Master R-S flip-flop tartalma különböző lenne, az MS J-K flip-flop hibásan működne.)

Az MS J-K flip-flop igazságtáblázatának C=1 és C=0 értékeknek megfelelő értékeit attól függően kaphatjuk meg, hogy milyen értékeket jelentenek a J és K bemenetek, a Master flip-flop által tárolt y2 tartalom, és a Slave flip-flop által tárolt y1 tartalom. A beállított paraméterek különböző értékei mellett egy teljes óraciklus után a J-K flip-flop állapotai egyszerűen kiszámíthatók.

Az alábbi táblázatban a paraméterek értékére kattintva a megfelelő értékek beállíthatók:

a J-K flip-flop paramétereinek beállítása
J K y2 y1=Qn
0 0 0 0
J K C q←y1 S(m) R(m) y2 S(s) R(s) y1=Qn+1
                   
                   

A táblázatban
– az órajel felfutó ágának az órajel C=1 értéke felel meg;
– az órajel lefutó ágának az órajel C=0 értéke felel meg;
– a stabil állapotot az jelenti, amikor a visszacsatolt 'y1' jel kezdeti értéke (Qn) egy teljes óraciklus után megegyezik az 'y1' jel számított értékével (Qn+1).

Figyeljük meg, hogy hogyan változnak az MS J-K flip-flop (J-K-y2-y1) állapotai. Az állapotok stabilak, ha a Master FF és Slave FF kezdeti állapotai megegyeznek. Ezt a továbbiakban feltételezzük. (A teljesség kedvéért megadjuk az y2≠y1 eseteket is.)


A fenti példák esetében "ideális" áramköröket tételeztünk fel, amelyek késleltetés nélkül működnek. A gyakorlatban azonban számos probléma merülhet fel (például amiatt, mert az órajel véges időtartamú, és az áramkörök véges működési sebességgel rendelkeznek, ennek megfelelően meghatározott időre van szükségük egy művelet elvégzéséhez).



Boda István, 2018-2022.