Logikai műveletek

A Boole-algebra a matematikának egy speciális részterülete. Elnevezését George Boole után kapta, aki a 19. század közepén megjelent művében először foglalkozott ezzel a tudományterülettel. Az algebrához hasonlóan értékek között végzett műveletek leírásával foglalkozik, de a számok helyett igazságértékeket, a matematikai műveletek helyett pedig logikai műveleteket használ.

Első ránézésre ugyan elvontnak tűnik, mégis sokszor használjuk a hétköznapokban is anélkül, hogy észrevennénk. Ráadásul a számítógépek működésének az alapját adja, mivel könnyen átültethető a kettes számrendszerre.

Igazságértékek

A Boole-algebra egyik különlegessége, hogy számok helyett igazságértékekkel dolgozik. Ez jelentősen leegyszerűsíti a dolgunkat, mivel számokból végtelen sok van, igazságértékekből viszont csak kettő. Egy logikai kifejezés (eldöntendő kérdés) igazságértéke csak igaz vagy hamis lehet.

De mi az a logikai kifejezés? Minden olyan állítás, amelyről egyértelműen eldönthető, hogy igaz vagy hamis. Öt nagyobb, mint három. (I) Az ember emlős. (I) A Föld lapos. (H) Ezeket a kifejezéseket az egyszerűség kedvéért betűkkel szoktuk jelölni. Hasonlóan ahhoz, ahogy a matematikában is használjuk a változókat.

I = 1, H = 0
Igazságértékek számokra fordítva

Hogy kapcsolódik ez a számítógépekhez? Az igazságértékeket könnyű számokká alakítani. Megegyezés szerint a 0 jelenti a hamis értéket, az összes többi szám pedig az igaz értéket. Ez viszont így elég bonyolult lenne, ezért az egyszerűség kedvéért az 1-et szoktuk használni az igaz párjaként. Ha viszont csak 0 és 1 áll rendelkezésre, akkor máris kettes számrendszerben vagyunk.

Műveletek

A Boole-algebra tehát logikai kifejezések igazságértékeivel végez műveleteket. Ezekből a műveletekből összesen 20 van, de mi csak azt a négyet tekintjük át, amit a hétköznapokban is használunk a számítógéppel végzett munka során. A definíciók mellett mindegyik műveletnél részletezzük a matematikai alapműveletekkel és halmazműveletekkel való kapcsolatot.

Nem (¬)

A ¬A ¬¬A
I H I
H I H
Halmazábra
A nem művelet igazságtáblája és halmazábrája

A nem művelet a logikai kifejezés igazságértékét az ellentettjére cseréli. Ha A = I, akkor ¬A = H, és fordítva. A dupla tagadás viszont visszaállítja a kifejezés eredeti igazságértékét, vagyis ¬¬A = ¬(¬A) = A

A halmazműveletek közül megfelelője a komplementer. A̅ azoknak az elemeknek a halmaza, amik az A halmaznak nem elemei.

És (∧)

A B A ∧ B
I I I
I H H
H I H
H H H
Halmazábra
Az és művelet igazságtáblája és halmazábrája

Az és művelet eredménye csak akkor lesz igaz, ha mindkét logikai kifejezés igazságértéke igaz. Ha bármelyik kifejezés hamis, akkor az eredmény is hamis lesz.

A halmazműveletek közül megfelelője a metszet. A ∩ B azoknak az elemeknek a halmaza, amik az A és a B halmaznak is az elemei.

Az algebrai műveletek közül megfelelője a szorzás. Betűk helyett számokkal kifejezve látszik, hogy 1 * 1 = 1, 1 * 0 = 0, 0 * 1 = 0 és 0 * 0 = 0.

Vagy (∨)

A B A ∨ B
I I I
I H I
H I I
H H H
Halmazábra
A vagy művelet igazságtáblája és halmazábrája

A vagy művelet eredménye akkor lesz igaz, ha legalább az egyik logikai kifejezés igazságértéke igaz. Az eredmény csak akkor lesz hamis, ha mindkét kifejezés hamis.

A halmazműveletek közül megfelelője az unió. A ∪ B azoknak az elemeknek a halmaza, amik vagy az A vagy a B vagy mindkét halmaz elemei.

Az algebrai műveletek közül megfelelője az összeadás. Betűk helyett számokkal kifejezve látszik, hogy 1 + 1 = 10*, 1 + 0 = 1, 0 + 1 = 1 és 0 + 0 = 0.

Kizáró vagy (⊕)

A B A ⊕ B
I I H
I H I
H I I
H H H
Halmazábra
A kizáró vagy művelet igazságtáblája és halmazábrája

A kizáró vagy művelet eredménye akkor lesz igaz, ha pontosan az egyik logikai kifejezés igazságértéke igaz. Az eredmény akkor is hamis, ha mindkét kifejezés igaz. Erre azért van szükség, mert a beszélt nyelvben a "vagy" szó sokszor nem engedi meg az egyenlőséget. Pl.: alma vagy körte, kisebb vagy nagyobb, egyik vagy másik.

A halmazműveletek közül megfelelője a szimmetrikus különbség, vagyis a halmazok különbségeinek uniója. (A / B) ∪ (B / A) azoknak az elemeknek a halmaza, amik vagy csak az A vagy csak a B halmaznak az elemei.

Az algebrai műveletek közül megfelelője szintén az összeadás. Azzal a különbséggel, hogy az összegnek csak az utolsó számjegyét nézzük, ami 1 + 1 esetén 0, tehát hamis.

Műveleti sorrend

Egy-egy logikai műveltet már el tudunk végezni, de mi a helyzet akkor, ha több áll egymás után? Ebben az esetben ugyanazokat a szabályokat kell alkalmazni, mint a matematikában.

1. példa

Legyen három logikai kifejezésünk a következő igazságértékekkel: A = I, B = I, C = H. Nézzük az alábbi műveletsort: A ∨ ¬B ∧ C

							I ∨ ¬I ∧ H

							I ∨ ¬I ∧ H

							I ∨  H ∧ H

							  I    ∧ H

							       H
  1. Helyettesítsük be az igazságértékeket a változók helyére!
  2. Mivel a nem művelet a magasabb rangú, ezért először azt végezzük el.
  3. A másik két művelet egyenrangú, ezért balról jobbra haladva a vagy művelet következik.
  4. Végül az és művelet, hogy megkapjuk a műveletsor végeredményét.

2. példa

A következő példánk legyen egy bonyolultabb műveletsor, de ugyanazokkal a változókkal: ¬(A ∨ (B ∧ C))

							¬(I ∨ (I ∧ H))

							¬(I ∨ (I ∧ H))

							¬(I ∨    H   )

							¬   I

							    H
  1. Helyettesítsük be az igazságértékeket a változók helyére!
  2. A zárójelek miatt belülről kifelé haladunk, ezért először az és műveletet hajtjuk végre.
  3. Bár a nem műveletet magasabb rangú, a zárójel miatt mégis a vagy műveletet végezzük el.
  4. Végül elvégezzük a nem műveletet, hogy megkapjuk a műveletsor végeredményét.