Boole-algebra (informatika)
A Wikipédiából, a szabad lexikonból.
- 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, pl. 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.
[szerkesztés] A logikai függvények
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: x, és ennek csak két kombinációja lehet, k0-ra x = 0 és k1-re x = 1, és értéke (y) k0-nál y = 1 k1-nél pedig y = 0, akkor ez a negáció.
A negáció
| k0 | k1 | |
| x = | 0 | 1 |
| y = | 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: O = L, L = O.
A logikai függvényeknek a kapcsolási algebrában való alkalmazásánál különösen jelentősek az x1, x2 kétváltozós függvények. Összesen 16 ilyen függvény van. Két bemenetnél 22 = 4ki 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 y kimeneti változó 0 vagy 1 értéke, és így összesen (22)2 = 16 különböző hozzárendelés lehetséges.
A diszjunkció az y kimeneti változóhoz y = 0 értéket rendel, ha mind a két bemeneti változó: x1 és x2, vagy mind a kettő az 1 értéket veszi fel, akkor y = 1.
A diszjunkció értéktáblázata
| k0 | k1 | k2 | k3 | |
| x1 = | 0 | 0 | 1 | 1 |
| x2 = | 0 | 1 | 0 | 1 |
| y = | 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 "x1 vagy x2", szimbolikusan
.
A konjunkció csak akkor rendeli el az y kimeneti változóhoz az y = 1-et, ha mind az x1, mind az x2 értéke 1.
A konjunkció függvénytáblázata
| k0 | k1 | k2 | k3 | |
| x1 = | 0 | 0 | 1 | 1 |
| x2 = | 0 | 1 | 0 | 1 |
| y = | 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. Pl. a "sem-sem" művelet (antivalencia), amit szavakban "sem x1, sem x2"-nek mondhatunk, kifejezhető a fenti három függvénnyel.
A sem-sem művelet függvénytáblázata
| k0 | k1 | k2 | k3 | |
| x1 = | 0 | 1 | 0 | 1 |
| x2 = | 0 | 0 | 1 | 1 |
| y = | 0 | 1 | 1 | 0 |
A sem-sem művelet negációból, diszjunkcióból és konjunkcióból tevődik össze
| x1 = | 0 | 1 | 0 | 1 |
| x2 = | 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.
[szerkesztés] A számítóberendezések működése
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.
Pl. az
konjunkciónak leegyszerűsített ábrázolással - két, sorba kapcsolt munkakapcsoló felel meg; a lámpa csak akkor ég (y = 1), ha az x1 és x2 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 - pl. 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.







Based on work by