Logikai algebra, logikai műveletek

A digitális számítógépek bináris kódban dolgoznak. Az ALU tervezésekor a logikai algebra rendkívül fontos szerepet kapott. Alkalmazásával lehetővé vált, hogy a központi műveletvégző egységnek, az ALU-nak csak egészen egyszerű műveleteket kelljen végrehajtani: 838j93i

- a logikai algebra csak bináris kódokkal dolgozik, hiszen mindössze két konstanst, az       igazat és a hamisat kell kódolni.

- a négy aritmetikai műveletet (összeadás, kivonás, szorzás és osztás) áramköri szinten egyetlen műveletre, a bináris összeadásra lehet visszavezetni, a bináris összeadás pedig előállítható logikai műveletek segítségével.

- a boole algebra műveleteit szintén egyetlen logikai művelet, a "nem és" vagy a "nem vagy" segítségével megkapjuk

A III. generációs számítógépekben használt integrált áramkörök ezért szinte kizárólag "nand" kapuáramkörök voltak. A boole algebra kitüntetett szerepét a számítástechnikában egyrészt ez, másrészt pedig az indokolja, hogy az algoritmusok formális nyelveken történő leírása nem nélkülözheti a logikai változókat, műveleteket, illetve konstansokat. A logikai műveletek segít­ségével minden olyan matematikai művelet előállítható, ami számítógéppel kiszámítható.

Mint már említettük, a korábbi számítógép generációk hardverének tervezésekor, sőt még a gépi kódú programok­ban is a boole algebra igen fontos szerepet játszott. Ma már az integrált­ság foka a hardverben olyan, hogy a logikai műveleteket csak gépi utasítások szintjén találjuk meg, de bizonyos technológiai megoldások megértése (pl. kódolásban a komplemens kód), relációk, feltételek leírása, programmodellek, adatszerkezetek megadása, vagy pl. a szakértői rendszerek programozása ma is feltételezi a logikai algebra elemeinek biz­tos ismeretét.

Logikai konstansok:

- igaz(1), hamis(0), angolul: (true,false)

Logikai műveletek:

Egyváltozós logikai műveletek( 4db ):
- a = 1 : igaz
- a = 0 : hamis
- a = a : identitás művelet ( 'a'-val nem csinálunk semmit )
- NOT(a) : 'a' negálása, "nem" a.

Ezek közül az első háromnak nincs gyakorlati jelentősége, a NOT műveletet viszont nem lehet nélkülözni.

Kétváltozós logikai műveletek ( 16db )

a

0 1

0 I. II.

b

1 III. IV.

Az a és a b a két logikai változó, mindkettő lehet igaz vagy hamis, az "a (művelet) b" eredménye annyi féle lehet, ahányféleképpen kitölthetjük a fenti táblázat I.,II.III. és IV.celláját. Ez összesen 16 lehet. Ahhoz azonban, hogy egy se maradjon ki, illetve minden variációt csak egyszer vegyünk figyelembe, a 16 kétváltozós műveletet valahogy rendszerbe kell foglalnunk. Az alábbi "fa" erre való:

Elsőként bontsuk két csoportra a 16 műveletet:        bal csoport-----az I. dobozba 0-t írunk,

jobb csoport---az I. dobozba 1-et írunk.

Ezt a szisztémát folytatva a többi dobozra is előállíthatóa kétváltozós műveletek fája:

I. 1

II.------------ 1 0 1

III.---- 1 0 1 0 1 0 1

IV.- 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

A tizenhat művelet közül nem mind egyformán fontos, hasonlóan az egyváltozós műveletekhez. A fontosabbaknak nevet is adtak, a többieknek nem:
1. Azonosan hamis művelet 9. NOT(OR), NOR művelet
2. AND (és) művelet (^,and, *) 10. Ekvivalencia (=, eq)
3. A AND NOT(B) művelet 11. NOT(A) művelet
4. =A 12. Implikáció (A B)
5. NOT(A) AND B művelet 13. NOT(B) művelet
6. B művelet 14. B implikálja A-t (B A)
7. Exclusive OR -kizáró vagy, (Å,xor) művelet          15. NOT(AND), (NAND, |) művelet
8. OR (vagy) művelet (v,or,+) 16. Azonosan igaz művelet
Megmutatható, hogy a 16 kétváltozós művelet mindegyike felírható olyan kifejezésekkel is, amelyekben csak a "vagy", az "és" és a "nem" műveleteket, illetve a logikai konstansokat használjuk:

1. 0 9. not(a or b)

2. a and b 10. (a or not(b)) and (not(a) or b)

3. a and not(b) 11. not(a)

4. a 12. not(a) or b

5. not(a) and b 13. not(b)

6. b 14. not(b) or a

7. (a and not(b)) or (not(a) and b) 15. not(a and b)

8. a or b 16. 1.

A logikai algebra legfontosabb azonosságait tehát elegendő a fenti 3 műveletre megadni:

not(not(a))=a

a or 1=1 a or 0=a
a and 1=a a and 0=0
a or a =a a and a=a
a or b=b or a a and b=b and a

a or (b or c)= (a or b) or c= a or b or c a and (b and c)= (a and b) and c=a and b and c

a or (b and c)= (a or b) and (a or c) a and(b or c)= (a and b) or (a and c)

A fenti azonosságokból látszik, hogy pl. az or és az and műveletek operandusai felcserélhetők, illetve csoportosíthatók, hasonlóan a matemetika összeadás, illetve szorzás műveleteihez. Ezért az or műveletet szokás logikai összeadásnak, az add-et logikai szorzásnak is nevezni. Vigyázzunk azonban arra, hogy a párhuzam nem teljes, ezért nem is ajánlott ezeket az elnevezéseket használni. Az azonban gyakran előfordul, hogy az or műveletet + jellel, az and-et *-gal jelöljü. Gondoljunk például az Internet keresőkre. Fontos és gyakran használt azonosságok még az alábbi, Morgan-szabályoknak nevezett összefüggések:

not(a and b) = not(a) or not(b) not(a or b ) = not(a) and not(b)

A fentiszabályok alapján belátható, hogy a kettőnél több változót tartalmazó kifejezések visszavezethetők kétváltozós műveletekre, amiből már következik az is, hogy minden logikai kifejezés felírható egyetlen művelet, pl. a not(and) segítségével:

(a|a) = not(a),

(a|a)|(b|b)=a or b,

(a|b)|(a|b)=a and b.