Boole algebra

A Boole algebra a nevét George Boole angol matematikus után kapta. Felfedezése sokáig homályban maradt, azonban halála után 70 évvel rátalált Claude Shannon, aki rámutatott arra, hogy a Boole algebra segítségével optimalizálni lehet az elektromechanikus relék rendszerének tervezését. A számítástechnika fejlődésével Boole felfedezése még nagyobb jelentőséget kapott.

A Boole algebra logikai műveleteket definiál bináris számjegyeken. Ezen műveletek közül a legegyszerűbb és az egyetlen egyváltozós: a tagadás, negáció. Angolul a szakirodalomban NOT műveletnek nevezik, melynek lényege, hogy a bemeneti érték inverzét fogja eredményül adni.

A műveletek leírása igazságtáblázatokkal történik, amelyben fel van tüntetve az összes lehetséges bemeneti kombinációhoz a kimenet értéke. Két bemenet esetén 16 különböző művelet definiálható, azonban ezek közül három kombinációjával az összes többi megvalósítható. Ezeket nevezzük a Boole algebra alapműveleteinek. Ezek a NEM (NOT), ÉS (AND) és VAGY (OR) műveletek.

Az ÉS művelet akkor fog igaz eredményt adni, ha mind a két bemeneti változó értéke igaz. Igazságtáblázata:

A VAGY művelet akkor fog igaz értéket adni, ha a bemeneti változók közül bármelyik igaz.

Ezen műveleteket feltételes utasításokban, logikai típuson (bool) is tudjuk alkalmazni, vagy számokon. Ha számokon alkalmazzuk őket, akkor a két szám minden egyes bitjére helyiértékenként egyenként lefuttatjuk az adott bináris műveletet és az így kialakuló szám és az így kialakuló új szám lesz a művelet végső eredménye. Számokon van még egy művelet, amit szokás alkalmazni. Ez a KIZÁRÓ VAGY. A KIZÁRÓ VAGY művelet igaz értéket csak akkor ad, ha a bemeneti változók értéke nem azonos. Ez és az inverze az EKVIVALENCIA logikai típusok esetén nincs implementálva, pontosabban más néven: Egyenlőség és nem egyenlőség.

Mivel algebráról beszélünk, az alapműveletek között némi gondolkodással egy azonossági rendszer definiálható. Ezen azonosságokat 6 fő csoportba szokták sorolni, valamint az azonosságokat szokás egy sorszámmal is jelölni.

Azonban még mielőtt algebráról beszélnénk, egy jelölés rendszert kell bevezetnünk. C# esetén egész számok esetén a következő szimbólumok vannak hozzárendelve a logikai műveletekhez:

Logikai típus (bool) esetén a következő szimbólumok használatosak:

A logikai típus minden modern típusos programozási nyelvben megtalálható. A klasszikus C esetén még nem tartották külön típusnak és lényegében úgy kezelték, hogy ami nem 0 értékű, az igaz. Ez problémákat tudott okozni, ezért már a C++ első változataiban felbukkant a bool, mint külön típus, ami a program vezérlési elágazások biztonságos és jó leírására szolgált.

Az azonosságokat szokás egy-egy sorszámmal is jelölni. Az azonosságok jelölésénél a bool típus jelöléseit alkalmaztam, de ettől függetlenül egész számok esetén is helytállnak az azonosságok, de a műveletek bitenként alkalmazódnak, így az azonosságok is egy bitre értendőek.

Az első azonossági csoport az igaz és hamis konstans értékek és a változók között fennálló azonosságokat tartalmazza:

1. A || false == A
2. A || true == true
3. A && false == false
4. A && true == A

A második azonossági csoport a ponált (nem tagadott) és a negált változó azonosságait tartalmazza:

5. A || !A == true
6. A || A == A
7. A && !A == false
8. A && A == A
9. !!A == A

A harmadik csoport a műveletek közötti kommutativitásra (felcserélhetőség) vonatkozik:

10. A || B == B || A
11. A && B == B && A

A negyedik csoportba az asszociativitás (csoportosíthatóság) azonosságai tartoznak:

12. A || B || C == (A || B) || C == A || (B || C)
13. A && B && C == (A && B) && C == A && (B && C)

Az ötödik csoportba a disztributivitás (kiemelhetőség) azonosságai tartoznak:

14. A && (B || C) == (A && B) || (A && C)
15. A || (B && C) == (A || B) && (A || C)

A hatodik csoportba a De Morgan-azonosságok tartoznak. Ezek teljes kifejezések negálására vonatkoznak:

16. !(A || B) == !A && !B
17. !(A && B) == !A || !B

Az ismertetett 17 azonosságon kívül érdemes még megjegyezni a következőket:

18. A || (!A && B) == A || B
19. A && (!A || B) == A && B
20. A || (A && B) == A
21. A && (A || B) == A