Boole-algebra (informatika)

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 értelemben 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űveletek

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

Implikáció

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: $A\Rightarrow B$

Alapműveletekkel kifejezve:

$A\Rightarrow B=\neg A\vee B$

Ekvivalencia

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: $A\Leftrightarrow B$

Definíciója az alapműveletek segítségével kifejezve:

$A\Leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)$

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:

$A\Leftrightarrow B=(\lnot A\lor B)\wedge (\lnot B\lor A)$

Kizáró vagy

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. Ezt úgy is lehet értelmezni, mint „különböző / nem azonos” műveletet a két operandus között.

Igazságtáblázata

A $p\,\mathrm {XOR} \,q$ (másképp írva $p\oplus q$ vagy $p\neq q$) 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ő $p$, $q$, és $\oplus$ feliratok bármelyikét felcserélve is igaz marad a táblázat.

Venn-diagram

Az $A\oplus B$ Venn-diagramja (az igaz érték pirossal van jelölve)

Scheffer-féle művelet

A logikai változók értéke

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ó $\land$ 0 1 0 0 0 1 0 1

Diszjunkció $\lor$ 0 1 0 0 1 1 1 1

Negáció   $\neg$ 0 1 1 0

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, $k_{0}$-ra $x=0$ és $k_{1}$-re $x=1$, és értéke $(y)$ $k_{0}$-nál $y=1$ $k_{1}$-nél pedig $y=0$, akkor ez a negáció.

A negáció

	$k_{0}$	$k_{1}$
$x=$	0	1
$y=$	1	0

A negációt szimbolikusan $y={\bar {x}}$ alakban szokták írni. Két egymás utáni negáció egymás hatását nyilván lerontja, ${\bar {\bar {x}}}=x$. 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 $x_{1}$, $x_{2}$ kétváltozós függvények. Összesen 16 ilyen függvény van. Két bemenetnél $2^{2}=4k_{i}$ 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 $(2^{2})^{2}=16$ különböző hozzárendelés lehetséges.

A diszjunkció

A diszjunkció az $y$ kimeneti változóhoz $y=0$ értéket rendel, ha mind a két bemeneti változó: $x_{1}$ és $x_{2}$, vagy mind a kettő az 1 értéket veszi fel, akkor $y=1$.

A diszjunkció értéktáblázata

	$k_{0}$	$k_{1}$	$k_{2}$	$k_{3}$
$x_{1}=$	0	0	1	1
$x_{2}=$	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$\vee$O=O
L$\vee$O=L
O$\vee$L=L
L$\vee$L=L

A diszjunkció közvetlenül érthető, szavakban való megfogalmazása "$x_{1}$ vagy $x_{2}$", szimbolikusan $y=x_{1}\vee x_{2}$.

A konjunkció csak akkor rendeli el az $y$ kimeneti változóhoz az $y=1$-et, ha mind az $x_{1}$, mind az $x_{2}$ értéke 1.

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

	$k_{0}$	$k_{1}$	$k_{2}$	$k_{3}$
$x_{1}=$	0	0	1	1
$x_{2}=$	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
$O\wedge O=O$
$L\wedge O=O$
$O\wedge L=O$
$L\wedge L=L$
A konjunkció műveletét $\wedge$ 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 $x_{1}$, sem $x_{2}$"-nek mondhatunk, kifejezhető a fenti három függvénnyel.

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

	$k_{0}$	$k_{1}$	$k_{2}$	$k_{3}$
$x_{1}=$	0	1	0	1
$x_{2}=$	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

$x_{1}=$	0	1	0	1
$x_{2}=$	0	0	1	1
$z_{1}=x_{2}\vee x_{1}=$	0	1	1	1
${\overline {x}}_{1}=$	1	0	1	0
${\overline {x}}_{2}=$	1	1	0	0
$z_{2}={\overline {x}}_{2}\vee {\overline {x}}_{1}=$	1	1	1	0
$y=z_{1}\wedge z_{2}=$	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ó, $z_{1}=x_{2}\vee x_{1}$;
2. diszjunkció, $z_{2}={\overline {x}}_{2}\vee {\overline {x}}_{1}$ és
3. konjunkció $y=z_{1}\wedge z_{2}$.

Á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é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.

Például az $y=x_{1}\wedge x_{2}$ 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 $x_{1}$ és $x_{2}$ 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 á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ő lapkán lehetséges egy digitális számítógép teljes funkcionalitását megvalósítani. 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.