Boole-algebra (informatika)

(Kizáró vagy szócikkből átirányítva)
Ez a szócikk a Boole-algebra informatikai, illetve digitális technikai alkalmazásait tartalmazza – ily módon a bináris értékekkel történő számítást. A Boole-algebra mint matematikai struktúra a Boole-algebra szócikkben, mint matematikai logikai interpretáció a logikai függvények szócikkben keresendő.

A Boole-algebra (George Boole-ról kapta a nevét) a programvezérelt digitális számítógép kidolgozásának matematikai alapja. A Boole-algebra informatikai értelmeben olyan mennyiségek közötti összefüggések törvényszerűségeit vizsgálja, amelyek csak két értéket vehetnek fel. A kijelentéslogika pl., amely a logika algebrájának egy interpretációjaként fogható fel, olyan kijelentésekkel dolgozik, amelyek vagy "igazak", vagy "hamisak", és keressük az olyan kijelentések valóságtartalmát, amelyek helyes vagy hamis elemi kijelentésekből tevődnek össze.

A Boole-algebra másik interpretációja a kapcsolási algebra. Alapjául olyan kapcsolási elemek szolgálnak, amelyek csupán két, egymástól különböző állapotot vehetnek fel, például egy áramkörben vagy folyik áram, vagy nem; mágneses állapot fennáll vagy sem stb. A kapcsolási algebra azt vizsgálja, hogy az ilyen kapcsolási elemekből összeállított háló kimenetén a lehetséges két állapot melyike valósul meg, ha az elemek az egyik vagy másik lehetséges állapotban vannak. Ezért a Boole-algebra az elektronikus digitális számítógép konstruálásának nélkülözhetetlen elméleti alapja.

A bináris, logikai vagy Boole-féle változóknak nevezett mennyiségek kétértékűségét két jel bevezetésével fejezik ki. Ezek: "0" és "1" vagy "O" és "L". A logikai változók közötti összefüggéseket matematikailag a függvény fogalmával lehet leírni. Nevezhetjük ezeket logikai függvényeknek, valóságfüggvényeknek vagy kapcsolási függvényeknek.

Operátorok, műveletekSzerkesztés

Logikai alapműveletek az   (ÉS, Konjunkció),   (VAGY, Diszjunkció) és   (NEGÁLT, Negáció). Minden további definiált alapművelet összetett, ezekből levezethető:

ImplikációSzerkesztés

olyan kétváltozós művelet, amelynek értéke csak akkor nem igaz, ha A logikai értéke igaz és B logikai értéke nem igaz. Ezt az összetett műveletet – gyakori használata miatt – önálló műveletnek tekintjük.

Az implikáció jele:  
Alapműveletekkel kifejezve:
 

EkvivalenciaSzerkesztés

olyan kétváltozós logikai művelet, amely az A, B állításokhoz az "A akkor és csak akkor, ha B" állítást rendeli hozzá. A művelet eredménye abban az esetben igaz, amikor A állítás és B állítás is igaz, vagy amikor sem az A sem a B állítás nem igaz. A feltétel tehát a két logikai érték egyezése.

Az ekvivalencia jele:  
Definíciója az alapműveletek segítségével kifejezve:
 
Mivel az implikáció előállítható diszjunkció és negáció segítségével, ezért másképp is kifejezhetjük az ekvivalenciát:
 

Kizáró vagySzerkesztés

a kizáró vagy művelet abban különbözik a diszjunkciótól, hogy nem engedi meg, hogy a két állítás logikai értéke egyszerre igaz legyen. A művelet eredménye akkor hamis, ha mindkét állítás logikai értéke megegyezik.

Igazságtáblázata

A   (másképp írva   vagy  ) igazságtáblája a következő:

p q
H H H
H I I
I H I
I I H

Vegyük észre, hogy a végeredmény hármas szimmetriát mutat: a táblázat fejlécében levő  ,  , és   feliratok bármelyikét felcserélve is igaz marad a táblázat.

Venn-diagram

Az   Venn-diagramja (az igaz érték pirossal van jelölve)

 

Scheffer-féle művelet

A logikai változók értékeSzerkesztés

Kétváltozós kifejezések értéke, a változók értékétől és a rájuk alkalmazott művelettől függ, amit igazságtáblázat segítségével szemléltetünk. A Boole-algebra alapműveleteinek igazságtáblázata így néz ki:

Konjunkció
  0 1
0 0 0
1 0 1
 
Diszjunkció
  0 1
0 0 1
1 1 1
 
Negáció
   
0 1
1 0

A logikai függvényekSzerkesztés

Egy logikai függvény az n független, bemenő változó valamely meghatározott érték- vagy bemeneti kombinációjához a kimenő, függő változó egy értékét rendeli hozzá. Ezt a hozzárendelést logikai műveletnek is nevezik.

Ha a logikai függvénynek csak egyetlen változója van:  , és ennek csak két kombinációja lehet,  -ra   és  -re  , és értéke    -nál    -nél pedig  , akkor ez a negáció.

A negáció
   
  0 1
  1 0

A negációt szimbolikusan   alakban szokták írni. Két egymás utáni negáció egymás hatását nyilván lerontja,  . A kettes számrendszerbeli számok negációjára érvényesek a következő szabályok:  ,  .

A logikai függvényeknek a kapcsolási algebrában való alkalmazásánál különösen jelentősek az  ,   kétváltozós függvények. Összesen 16 ilyen függvény van. Két bemenetnél   kimeneti kombináció lehet, mivel mindegyik változó a másiktól függetlenül felveheti a 0 vagy az 1 értékét; minden bemeneti változóhoz hozzárendelhető az   kimeneti változó 0 vagy 1 értéke, és így összesen   különböző hozzárendelés lehetséges.

A diszjunkció

A diszjunkció az   kimeneti változóhoz   értéket rendel, ha mind a két bemeneti változó:   és  , vagy mind a kettő az 1 értéket veszi fel, akkor  .

A diszjunkció értéktáblázata

       
  0 0 1 1
  0 1 0 1
  0 1 1 1

A függvénytáblázatból megkaphatók a kettes számrendszerbeli számokra vonatkozó számolási szabályok.

Duális számok diszjunktív kapcsolata
O O=O
L O=L
O L=L
L L=L

A diszjunkció közvetlenül érthető, szavakban való megfogalmazása "  vagy  ", szimbolikusan  .

A konjunkció csak akkor rendeli el az   kimeneti változóhoz az  -et, ha mind az  , mind az   értéke 1.

A konjunkció függvénytáblázata

       
  0 0 1 1
  0 1 0 1
  0 0 0 1

A függvénytáblázatból megkapjuk a kettes rendszerbeli számokra vonatkozó számolási szabályokat.

Duális számok konjunktív kapcsolata
 
 
 
 
A konjunkció műveletét   vagy & jelöljük.

Kétbemenetű tetszés szerinti logikai összefüggés előállításához nincs szükség mind a 16 lehetséges logikai függvényre. Elég erre a konjunkció és a diszjunkció, ha hozzávesszük még a negációt is. Például a "sem-sem" művelet (antivalencia), amit szavakban "sem  , sem  "-nek mondhatunk, kifejezhető a fenti három függvénnyel.

A sem-sem művelet függvénytáblázata

       
  0 1 0 1
  0 0 1 1
  0 1 1 0

A sem-sem művelet negációból, diszjunkcióból és konjunkcióból tevődik össze

  0 1 0 1
  0 0 1 1
  0 1 1 1
  1 0 1 0
  1 1 0 0
  1 1 1 0
  0 1 1 0

Ha követjük a táblázat sorait felülről lefelé, észrevehető, hogy a "sem-sem" a következő kapcsolatokkal helyettesíthető:
1. diszjunkció,  ;
2. diszjunkció,   és
3. konjunkció  .

Általánosan igaz:
n bináris változó minden logikai kapcsolata kivétel nélkül visszavezethető az egyes változók diszjunkcióira, konjunkcióira és negációira.

A számítóberendezések működéseSzerkesztés

Az elektronikus digitális számítógépekben információkat dolgoznak fel: az elsődleges jelekből logikai összefüggések segítségével másodlagos jeleket állítanak elő. Az ehhez szükséges kapcsolási elemek csak két állapotot vehetnek fel, a 0-t és az 1-et. Az elérendő kapcsolatok létrehozására a kapcsolási elemeket a kapcsolási hálózat áramköreivé, kapcsolási hálózatokká kötik össze. A kapcsolásalgebrában nem az a lényeges, hogy a kapcsolási elemeket mechanikus kapcsolók, jelfogók vagy elektronikus kapcsolók valósítják meg, hanem az, hogy milyen szerepet játszanak egy rendszerben.

A következő példában a kapcsolási elemek jelfogók.

Elvileg a jelfogó olyan tekercs, amely egy kapcsolót nyit vagy zár aszerint, hogy a tekercsben áram folyik – 1 állapot – vagy nem folyik rajta keresztül áram (0 állapot). Megkülönböztetünk munkakapcsolót és nyugalmi kapcsolót.

A munkakapcsoló a 0 helyzetben nyitott, így a vezetékben, amit a kapcsoló megszakít, nem folyik áram; az 1 állapotban a tekercs mágneses tere zárja a kapcsolót, és a vezetékben is folyik áram.

Munkakapcsoló és nyugalmi kapcsoló

munkakapcsoló nyugalmi kapcsoló
a tekercsen át folyik-e áram nem igen nem igen
jelfogó állapota 0 1 0 1
lámpa állapota 0 1 1 0

A nyugalmi kapcsoló nyilvánvalóan a munkakapcsoló negációját állítja elő.

Minden logikai függvényhez találhatók analóg elektromos kapcsolások.

Például az   konjunkciónak leegyszerűsített ábrázolással – két, sorba kapcsolt munkakapcsoló felel meg; a lámpa csak akkor ég ( ), ha az   és   kapcsolók mindegyike zárt. A diszjunkciónak két, párhuzamosan kapcsolt munkakapcsoló felel meg; a lámpa akkor ég, ha vagy az egyik, vagy a másik, vagy mind a két kapcsoló zárt.

A logikai kapcsolásoknál még további részletektől is el szoktak tekinteni, és az áramköröket csak szimbolikusan ábrázolják.

Mivel a modern integrált áramkörök a fenti logikai alapösszefüggéseket vagy azok bonyolult kombinációját tartalmazzák egyetlen alkatrészként, ezért a modern gépek logikai vázlata egyben a kapcsolási rajzzal azonos. (Egy-egy integrált áramkör félvezető kristály általában csak több logikai szimbólum segítségével írható le.) Egészen magas szintű integrálásnál pedig egyetlen félvezető kristály egész digitális számítógépet tartalmaz. Ilyen esetben az alkatrész és a számítógép tervezése azonossá válik.

A kapcsolási algebra a szintézisben elemi logikai függvényeket – például negációkat, diszjunkciókat, konjunkciókat – olyan hálózattá kapcsol össze, amely előre megadott teljes logikai kapcsolatot állít elő. Az analízis viszont megadott hálózatot elemez.