Institute of Information Science - University of Miskolc

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Boole algebra alapjai =====

Definíció:

a \( \lbrace0,1\rbrace^n\rightarrow\lbrace0,1\rbrace \) alakú függvényeket Boole függvényeknek nevezzük.

A Boole függvényeket felírhatjuk:

\( y=f(x_1, x_2, ..., x_n) \) alakban. Ezek egy n változós Boole függvényt definiálnak.

A Boole függvényt definiálhatjuk az igazságtáblájával is. Belátható, hogy n bemenet esetén \( 2^n \) sort tartalmazna ez az igazságtábla.

A bemenetek és kimenetek kapcsolatának leírására Boole egyenleteket használhatunk

Legyen n darab bemenet és m darab kimenet.
Ennek a rendszernek a leírásához m egyenlet felírására van szükség.

\(y_1=f(x_1, x_2, ..., x_n)\)

.

..
 
...


\(y_m=f(x_1, x_2, ..., x_n)\)

=== Differencia egyenletek ===

A következő felírás sorrendiséget is meghatároz. Egy t+1 időpontban a rendszer állapotát úgy írhatjuk le, hogy azok a bemenő változók és a kimenő változók egy előző, t. időpontban vizsgált értékének a függvénye.

Ezeket az egyenleteket differencia egyenleteknek nevezzük.

\( y^{t+1}_1=f(x_1, x_2, ..., x_n, y^t_1,y^t_2,...,y^t_m) \)

.

..
 
...

\( y^{t+1}_m=f(x_1, x_2, ..., x_n, y^t_1,y^t_2,...,y^t_m) \)

==== Tulajdonságai ====

=== Asszociatív ===

A Boole algebra asszociatív - csoportosítható - tulajdonsága így írható le:

\( a+(b+c) = (a+b)+c \)

\( a \cdot (b \cdot c) = (a \cdot b) \cdot c \)

=== Kommutatív ===

A Boole algebra kommutatív tulajdonsága így írható le:

\( a + b = b + a \)

\( a \cdot b  = b \cdot a \)

=== Elnyelés ===

Az elnyelési tulajdonság így írható fel:

\( a + (a \cdot b) \equiv a \)

\( a \cdot (a + b) \equiv a \)

=== Disztributív ===

A Boole algebra disztributív tulajdonsága így írható le:

\(a+(b \cdot c) = (a+b) \cdot (a+c)\)

\(a \cdot (b + c) = (a \cdot b) + (a \cdot c)\)

=== Komplementer ===

A komplementer képzés így írható le:

\( a + \bar a = 1 \)

\( a \cdot \bar a = 0 \)

=== Idempotencia/korlátosság ===

\( a + a \equiv a \)

\( a + 0 \equiv a \)

\( a \cdot a \equiv a \)

\( a \cdot 1 \equiv a \)

\( a + 1 =1 \)

\( a \cdot 0 = 0 \)

=== de Morgan azonosság ===

A **de Morgan** azonosságokkal összetett negált kifejezéseket bonthatunk fel. Két azonosságot is felírhatunk:

\( \overline {(a + b)} \equiv \bar a \cdot \bar b  \)

\( \overline {(a \cdot b)} \equiv \bar a + \bar b \)

Terjesszük ki az egyenlőséget három változóra:

\( \overline {(a + b + c)} = (\overline {(a + b) + c}) = \overline{(a+b)} \cdot \bar c = (\bar a \cdot \bar b) \cdot \bar c = \bar a \cdot \bar b \cdot \bar c \)

\( \overline {(a \cdot b \cdot c)} = \overline{(a \cdot b)} + \bar c = (\bar a + \bar b) + \bar c = \bar a + \bar b + \bar c  \)

Ezek az azonosságok tetszőleges sok elemre is érvényben maradnak, beleértve a véges, megszámlálhatóan végtelen és nem megszámlálható I indexhalmazok esetét is:

\( \overline {\sum_{i \in I}A_i} \equiv \prod_{i \in I} \overline {A_i} \)

\( \overline {\prod_{i \in I}A_i} \equiv \sum_{i \in I} \overline {A_i} \)

Látható, hogy összetett függvényeket úgy negálunk, hogy a VAGY kapcsolatokból ÉS lesz, az ÉS kapcsolatokból VAGY, és minden változót külön invertálnunk kell.

Igazoljuk a de Morgan azonosságokat!  Ehhez minden létező kombinációban kiszámítjuk az egyenlet bal és jobb oldalát.

\( \overline {(a + b)} \equiv \bar a \cdot \bar b \)

^a^b^\(a+b\)^\( \overline{(a + b)} \)^\(\bar a\)^\(\bar b\)^\(\bar a \cdot \bar b\)^
|0|0|0|1|1|1|1|
|0|1|1|0|1|0|0|
|1|0|1|0|0|1|0|
|1|1|1|0|0|0|0|

Igazoljuk a de Morgan azonosságokat!  Ehhez minden létező kombinációban kiszámítjuk az egyenlet bal és jobb oldalát.

\( \overline {(a \cdot b)} \equiv \bar a + \bar b \)

^a^b^\(a \cdot b\)^\( \overline{(a \cdot b)} \)^\(\bar a\)^\(\bar b\)^\(\bar a + \bar b\)^
|0|0|0|1|1|1|1|
|0|1|0|1|1|0|1|
|1|0|0|1|0|1|1|
|1|1|1|0|0|0|0|