Boole-algebra (informatika)

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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.

Tartalomjegyzék

1 Operátorok, műveletek
2 A logikai változók értéke
3 A logikai függvények
- 3.1 A számítóberendezések működése

Operátorok, műveletek

Logikai alapműveletek az $\land$ (ÉS), $\lor$ (VAGY) és $\lnot$ (NEGÁLT). 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) \vee (\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.

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 $22 = 4 k 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. Pl. 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.

Pl. 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 [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.

A lap eredeti címe: „http://hu.wikipedia.org/wiki/Boole-algebra_(informatika)”

Kategória: Informatika

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net