Boolean algebra (tsz. Boolean algebras)
A Boole-algebra (vagy logikai algebra) a matematikának egy speciális ága, amely a logikai értékekkel – igaz (true) és hamis (false) – végzett műveletekkel foglalkozik. A nevét George Boole angol matematikusról kapta, aki a 19. század közepén megalkotta a logikai kalkulus alapjait. A Boole-algebra ma már alapvető szerepet játszik digitális elektronikában, számítógépes programozásban, formális logikában, valamint halmazelméletben és mesterséges intelligenciában is.
A Boole-algebra a következő elemekből épül fel:
1 vagy true) és hamis (0 vagy false)0 vagy 1 értéket vehetnek fel, pl. A, B, x, y
A három legfontosabb logikai művelet:
Jelölés: ¬A vagy A̅ vagy NOT A
Jelentése: az A logikai ellentéte
Igazságtábla:
| A | ¬A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Jelölés: A ∧ B vagy A · B vagy A AND B
Akkor igaz, ha mindkét operandus igaz
Igazságtábla:
| A | B | A ∧ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Jelölés: A ∨ B vagy A + B vagy A OR B
Akkor igaz, ha legalább az egyik operandus igaz
Igazságtábla:
| A | B | A ∨ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Jelölés: A ⊕ B
Akkor igaz, ha csak az egyik operandus igaz
Igazságtábla:
| A | B | A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
A Boole-algebra egy algebrai struktúra, mely kielégíti a következő tulajdonságokat:
A ∨ B = B ∨ AA ∧ B = B ∧ A
(A ∨ B) ∨ C = A ∨ (B ∨ C)(A ∧ B) ∧ C = A ∧ (B ∧ C)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
A ∨ 0 = AA ∧ 1 = A
A ∨ ¬A = 1A ∧ ¬A = 0
A Boole-kifejezések egyszerűsítése hasonló az algebrai kifejezésekhez, de más szabályokkal. Például:
A + A = A (idempotencia)A · A = AA + 1 = 1A · 0 = 0A + A̅ = 1A · A̅ = 0
A Karnaugh-diagram (K-tábla) egy vizuális módszer a Boole-kifejezések egyszerűsítésére. Alkalmas logikai függvények minimalizálására (pl. áramkörök tervezésekor).
Például egy kéttényezős K-tábla:
| A | 0 | 1 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 1 | 1 |
A digitális áramkörök Boole-kifejezések szerint működnek. Az alaplogikai kapuk (AND, OR, NOT) fizikai megvalósításai tranzisztorokból épülnek fel.
Példák:
if (A && B), if (A || B)x & y, x | y, ~x, x ^ y
SELECT * FROM t WHERE A = 1 AND (B = 0 OR C = 1);
Adott a következő kifejezés:
F(A, B, C) = A·B + A·B̅
Alkalmazzuk az azonosságokat:
A·B + A·B̅ = A · (B + B̅)B + B̅ = 1A · 1 = AVégeredmény: F = A
A Boole-algebra egy rendkívül hatékony eszköz a logikai problémák leírására, modellezésére és optimalizálására. Alapvető fontosságú minden olyan területen, ahol bináris döntések születnek: digitális elektronika, szoftverfejlesztés, adatkezelés, mesterséges intelligencia.