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 |