Boole-algebra

A Wikipédiából, a szabad lexikonból.

Az absztrakt algebra területén a George Boole nevét viselő Boole-algebra egy algebrai struktúra (elemek és azokon értelmezett utasítások gyűjteménye, melyekre bizonyos axiómák érvényesek) amely a halmazműveletek és a logikai műveletek legalapvetőbb tulajdonságait gyűjti össze. Speciálisan a metszet, az unió, a komplementer műveletekét a halmazelméletből és a konjunkció (ÉS, AND), diszjunkció (VAGY, OR) és a negáció (NEM, NOT) műveletét a logikából.

Például egy logikai kijelentés: egy a állítás és a ¬a negáltja nem lehet egyszerre igaz,

Részhalmazok Boole-hálója
Nagyít
Részhalmazok Boole-hálója
a\land(\lnot a) = \mbox{hamis},

az ennek megfelelő halmazelméleti állítás a következő: egy A részhalmaz és annak AC komplementerének a metszete üres halmaz,

A\cap(A^C) = \varnothing.

Mivel az igaz értéket bináris számokkal vagy logikai áramkörök feszültségszintjeivel is azonosíthatjuk, a párhuzam ezekre is fennáll. Így a Boole-algebra elmélete rengeteg gyakorlati alkalmazással bír a villamosmérnöki szakma és a számítógéptudomány területén, valamint a matematikai logikában.

A Boole-algebrát Boole-hálónak is nevezik. A hálókkal (a speciális részben rendezett halmazokkal) való kapcsolatot a részhalmaz reláció (A ⊆ B) és a rendezés (a ≤ b) közötti hasonlóság adja. Tekintsük a {x,y,z} halmaz összes részhalmazát a részhalmaz reláció szerint rendezve. Ez a Boole-háló részben rendezett halmaz, amelyben {x}  ≤ {x,y}. Bármely két eleme a hálónak, pl. p = {x,y} és q = {y,z}, rendelkezik egy legkisebb felső korláttal, itt {x,y,z}, és egy legnagyobb alsó korláttal, itt {y}. Suggestively, legkisebb felső korlát (vagy szuprémum) jelölése egyezik a logikai VAGY-éval, pq; és a legnagyobb alsó korláté (vagy infimumé) a logikai ÉS jelölésével, p q.

A hálóinterpretáció lehetőséget biztosít a Boole-algebra általánosításának megalkotására. A Heyting-algebra a Boole-algebra olyan általánosítása, mely nem tartalmazza azt a megkötést, hogy egy kijelentésnek mindenképpen igaznak vagy hamisnak kell lennie. Érdemes megjegyezni, hogy míg a Boole-algebra a klasszikus propozicionális logika algebrai interpretációjának tekinthető, addig a Heyting-algebra az intuicionista logika algebrai interpretációját adja.

Tartalomjegyzék

[szerkesztés] Operátorok, műveletek

Logikai alapműveletek az (ÉS), \lor (VAGY) és \lnot (NEGÁLT). Minden további definiált alapművelet összetett, ezekből levezethető:

  • implikáció      a \Rightarrow b = \neg a \vee b
  • ekvivalencia      a \Leftrightarrow b = (a\wedge b) \vee (\neg a \wedge \neg b)
  • kizáró vagy (SEM-SEM)
  • Scheffer-féle művelet

[szerkesztés] 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

[szerkesztés] Ítéletlogikai műveletek tulajdonságai, azonosságok

A főbb logikai azonosságok egy, kettő illetve három változóra az \land (ÉS), \lor (VAGY) és \lnot (NEGÁLT) operátorokkal. A logikai változók értékénél 0 hamis állítást (üres halmazt), 1 pedig igaz állítást (az a, b és c elemeket tartalmazó halmazt) jelöli.

a \lor (b \lor c) = (a \lor b) \lor c a \land (b \land c) = (a \land b) \land c asszociatív
a \lor b = b \lor a a \land  b = b \land a kommutatív
a  \lor (a \land b) = a a  \land (a \lor b) = a absorption
a \lor  (b \land c) = (a \lor b) \land (a \lor c) a \land  (b \lor c) = (a \land b) \lor (a \land c) disztributív
a \lor  \lnot a = 1 a \land \lnot a = 0 komplementerek

Ezek az állítások ugyanis a halmazelméletben is megtalálhatóak, következésképpen halmazelméleti azonosságokként is értelmezhetőek. (Például a következő logikai műveletek halmazelméleti fogalmaknak felelnek meg.: ÉS→metszet, VAGY→unió, negált→komplementer, kizáró vagy→halmazok különbsége stb.)

A De-Morgan azonosságok igazságtáblázattal való bizonyítása:

Függvény Igazságtáblázat
\overline{ a + b } = \overline{a} . \overline{b}
a b a+b \overline{ a . b } \overline{ a } \overline{ b } \overline{a} . \overline{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
Függvény Igazságtáblázat
\overline{ a . b } = \overline{a} + \overline{b}
a b a.b \overline{ a . b } \overline{ a } \overline{ b } \overline{a} + \overline{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

[szerkesztés] Prioritás

Boole-algebrában a műveletek sorrendje szigorúan meghatározott:

  1. negált
  2. konjunkció, diszjunkció

A műveleti sorrend természetesen zárójelekkel megbontható.

[szerkesztés] Példa logikai függvény alkalmazására

[szerkesztés] Logikai áramkörök

A logikai műveleteket elektromos kapcsolásokként (kapuáramkörökként) is értelmezhetjük. A logikai függvényeket így kapuáramkörök kombinálásával is felírhatjuk. Az ÉS, VAGY és NEGÁLT műveletek soros és párhuzamos kapcsolásnak, valamint invertereknek felelnek meg.

[szerkesztés] Története

A „Boole-algebrát” George Boole (1815–1864) tiszteletére nevezték el, aki autodidakta angol matematikus volt. A logika algebrai rendszerét 1854-es monográfiájában, A gondolkodás törvényeiben (The Laws of Thought) fogalmazta meg. Ez különbözött a fent leírttól pár fontos pontban. Például a konjunkció és a diszjunkció számára nem egy duális operátorpár volt. A Boole-algebra 1860-ban jött létre William Jevons és Charles Peirce cikkeiben. Ernst Schröder 1890-es Vorlesungenjének idejére már rendelkeztünk a Boole-algebra és a disztributív hálók első rendszerezett bemutatásával. Angol nyelvterületen a Boole-algebra első kiterjedt tárgyalása A. N. Whitehead 1898-ban írt Univerzális algebra (Universal Algebra) című műve volt. A Boole-algebrának az első axiomatikus algebrai struktúraként történő tárgyalása Edward Vermilye Huntington 1904-es dolgozatával kezdődött meg. Komoly matematikává Marshall Stone 1930-as években végzett munkájával és Garrett Birkhoff 1940-es Hálóelmélet (Lattice Theory) című művével vált. Az 1960-as években Paul Cohen, Dana Scott és mások mélyenszántó új eredményeket találtak a matematikai logika és az axiomatikus halmazelmélet területén a Boole-algebra ágainak használatával, név szerint a forszolással és a Boole-értékű modellekkel.

[szerkesztés] Lásd még