szit

Felhasználói eszközök

Eszközök a webhelyen

Itt vagy: start » oktatas » szamitastechnika » logika
Nyomvonal: • logika
oktatas:szamitastechnika:logika

Tartalomjegyzék

< Számítástechnika

Logika

Boole-algebra

A „Boole-algebrát” George Boole (1815–1864) írta le, a „A gondolkodás törvényei” (The Laws of Thought) című művében (1854). Mivel a számítógépeink kettes számrendszerben működnek, áramköreit logikai kapukból építjük fel, ezért fontos számunkra annak ismerete.

Igazságtáblák

Minden művelethez felírható egy igazságtábla, amely segít megállapítani, az adott művelet esetén milyen értéket kapunk eredményül.

Negáció

A legegyszerűbb logikai művelet a negáció. Ha van egy 0 értékünk, negáláskor 1 lesz. Ha 1 értéket negálunk, annak eredménye 0 lesz.

Tagadás vagy NOT

A ¬A
0 1
1 0

Konjunkció

A konjunkciót másként ÉS műveletnek is hívjuk. Az ÉS művelethez már érték szükséges, legyen az egyik „A”, a másik „B” érték. Ha A és B érték is 0, akkor egy ÉS művelet eredménye is nulla lesz. Ha akár A, akár B értéke 1, de a másik 0, akkor még mindig 0 értéket kapunk. Csak akkor kapunk eredményül 1 értéket, ha A és B érték is 1.

AND vagyis ÉS művelet igazságtáblája:

A B A ∧ B
0 0 0
1 0 0
0 1 0
1 1 1

A továbbiakban csak az igazságtáblákat tüntetem fel.

Diszjunkció

OR, illetve VAGY

Ha pontosítani akarunk: megengedő vagy.

A B A ∨ B
0 0 0
1 0 1
0 1 1
1 1 1

NAND

Az ÉS tagadása

A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0

NOR

A VAGY tagadása

A B A NOR B
0 0 1
0 1 0
1 0 0
1 1 0

Antivalencia

Kizáró vagy (XOR)

A B A XOR B
0 0 0
1 0 1
0 1 1
1 1 0

kizáró vagy

Ekvivalencia

Egyértelműség.

A B A ↔ B
0 0 1
1 0 0
0 1 0
1 1 1

Implikáció

Következtetés.

Amikor leírom A → B úgy mondjuk „A” implikálja „B”-t.

A B A → B
0 0 1
1 0 0
0 1 1
1 1 1

Az implikáció megegyezik negált A vagy B értékével: 

¬A∨B

Bizonyítás:

A B ¬A ¬A∨B
0 0 1 1
1 0 0 0
0 1 1 1
1 1 0 1

Egyenletek megoldása

A számítógépekben összerakott áramkörök működése leírható egy egyenlettel. A lehetséges bemenetekre a logikai műveletek után kapunk egy értéket. Ilyen egyenletekre látunk példákat.

Az egyenletek megoldásán azt értjük, hogy felírjuk az összes lehetséges bemenő paramétert, majd kifejtjük az egyes bemenő állapotok esetén milyen eredményt kapunk.

Példa 001

Egy példa a megoldandó egyenletre:

¬A∧(B∨¬C) = D

A feladat, hogy megadjuk A, B és C összes lehetséges értéke esetén D értékét.

Az egyenlet baloldalán három ismeretlen van. Először felírom a három ismeretlen összes lehetséges változatát.

A B C
0 0 0
1 0 0
0 1 0
0 0 1
0 1 1
1 0 1
1 1 0
1 1 1

Érdemes a zárójelen belül kezdeni a megoldást, azon belül is a negálással:

A B C ¬C
0 0 0 1
1 0 0 1
0 1 0 1
0 0 1 0
0 1 1 0
1 0 1 0
1 1 0 1
1 1 1 0

A zárójelen belül a következő művelet a VAGY. A VAGY műveletet B és negált C között kell végrehajtani:

A B C ¬C B∨¬C
0 0 0 1 1
1 0 0 1 1
0 1 0 1 1
0 0 1 0 0
0 1 1 0 1
1 0 1 0 0
1 1 0 1 1
1 1 1 0 1

A zárójelen kívül van egy negálás, negált A. Először ezt végzem el:

A B C ¬C B∨¬C ¬A
0 0 0 1 1 1
1 0 0 1 1 0
0 1 0 1 1 1
0 0 1 0 0 1
0 1 1 0 1 1
1 0 1 0 0 0
1 1 0 1 1 0
1 1 1 0 1 0

Az utolsó művelet a zárójel előtti ÉS. Ha ezt is elvégezzük, akkor már D-ét kapjuk. Az utolsó oszlop fejlécébe leírhatnám az egyenlet baloldalát, de az egyenlő D-vel, így D-t írunk a helyére. A negált A és a zárójeles rész között kell ÉS műveletet csinálnunk. A zárójeles rész az ötödik oszlopban van. A negált A hatodik oszlopban. E két oszlop között kell az ÉS műveletet elvégeznünk:

A B C ¬C B∨¬C ¬A D
0 0 0 1 1 1 1
1 0 0 1 1 0 0
0 1 0 1 1 1 1
0 0 1 0 0 1 0
0 1 1 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0

Az A, B és C változatai esetén megkaptuk D értékét. Amit kaptunk az egyenlet igazságtáblája.

Példa 002

¬A∨¬(¬B∧C) = D

Először felírom A, B és C esetén az összes lehetséges értéket:

A B C
0 0 0
1 0 0
0 1 0
0 0 1
0 1 1
1 0 1
1 1 0
1 1 1

A zárójelen belül ¬B látunk. Először ezt végezzük el:

A B C ¬B
0 0 0 1
1 0 0 1
0 1 0 0
0 0 1 1
0 1 1 0
1 0 1 1
1 1 0 0
1 1 1 0

Fel kellett írnunk a B oszlop ellentéteit.

Ezek után felírhatjuk az egész zárójelben lévő részt: 

¬B∧C

Ebben a B negálását már az előbb megcsináltuk. A C értékei pedig adottak. A két oszlop között kell ÉS (∧) műveletet végezni.

A B C ¬B ¬B∧C
0 0 0 1 0
1 0 0 1 0
0 1 0 0 0
0 0 1 1 1
0 1 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 1 0 0

Az ötödik oszlopban csak a negyedik és a hatodik sorban kapunk igazat (1), mivel és művelet esetén mindkét oszlopban, amelyben végezzük a műveletet igaznak (1) kell szerepelnie. Ez az ÉS (∧) művelet igazságtáblájából tudjuk.

Megkaptuk az ötödik oszlopban az egész zárójeles részt. Az egyenletben az egész zárójeles rész negálva van, ezért az ötödik oszlopt negáljuk, vagyis felírjuk az ellentétét:

A B C ¬B ¬B∧C ¬(¬B∧C)
0 0 0 1 0 1
1 0 0 1 0 1
0 1 0 0 0 1
0 0 1 1 1 0
0 1 1 0 0 1
1 0 1 1 1 0
1 1 0 0 0 1
1 1 1 0 0 1

A hatodik oszlopban megkaptuk a zárójelen belüli rész negáltját.

A zárójelen kívül van egy negálás, először ezt végezzük el, mivel célszerű mindig a negálással kezdeni. Az A oszlopot kell negálni vagyis ellentétét felírni:

A B C ¬B ¬B∧C ¬(¬B∧C) ¬A
0 0 0 1 0 1 1
1 0 0 1 0 1 0
0 1 0 0 0 1 1
0 0 1 1 1 0 1
0 1 1 0 0 1 1
1 0 1 1 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 1 0

A hetedik oszlopban így az A oszlop negáltját kaptuk.

Már csak egyetlen műveletünk van az egyenlet baloldalán. 

¬A∨¬(¬B∧C)

Ez egy VAGY (∨) művelet. Vagy művelet esetén ha az egyik vizsgált oszlopban 1-s van, akkor máris 1-t kapunk. Meg kell keresni a két oszlopot, amelyen végrehajtjuk a VAGY műveletet. A VAGY művelet baloldalán negált A van (¬A), a jobboldalán a negált zárójeles rész. A negált A hetedik oszlopunk, a negált zárójeles rész pedig az hatodik. Ezen két oszlop között kell soronként a VAGY műveletet elvégezni:

A B C ¬B ¬B∧C ¬(¬B∧C) ¬A ¬A∨¬(¬B∧C)
0 0 0 1 0 1 1 1
1 0 0 1 0 1 0 1
0 1 0 0 0 1 1 1
0 0 1 1 1 0 1 1
0 1 1 0 0 1 1 1
1 0 1 1 1 0 0 0
1 1 0 0 0 1 0 1
1 1 1 0 0 1 0 1

Csak a hatodik sorban kaptunk nullát, mert hatodik és hetedik oszlopban csak ott szerepel mindkét helyen nulla (0).

Az utolsó oszlop fejlécének ezt írtuk: 

¬A∨¬(¬B∧C)

De mivel ez megegyezik a D értékével (ez magából az egyenletből következik, hiszen egyenlőség jel van közöttük), ezért akár D-t is írhatunk a helyére mint azt az első példában tettük:

A B C ¬B ¬B∧C ¬(¬B∧C) ¬A D
0 0 0 1 0 1 1 1
1 0 0 1 0 1 0 1
0 1 0 0 0 1 1 1
0 0 1 1 1 0 1 1
0 1 1 0 0 1 1 1
1 0 1 1 1 0 0 0
1 1 0 0 0 1 0 1
1 1 1 0 0 1 0 1

de Morgan azonosság

Azonosságok

¬(a ∧ b) = ¬a ∨ ¬b
¬(a ∨ b) = ¬a ∧ ¬b

Következmény

a ∧ b = ¬( ¬a ∨ ¬b)
a ∨ b = ¬( ¬a ∧ ¬b)

Függelék

Az összes lehetséges
érték 2 változó esetén
A B
0 0
1 0
0 1
1 1
Az összes lehetséges
érték 3 változó esetén
A B C
0 0 0
1 0 0
0 1 0
0 0 1
0 1 1
1 0 1
1 1 0
1 1 1
Az összes lehetséges érték 4 változó esetén
A B C D
0 0 0 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1
1 0 1 0
0 1 0 1
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
1 1 1 1
Az összes lehetséges érték 5 változó esetén
A B C D E
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 0 1 1
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 1 0 1 0
0 0 1 1 1
1 0 0 1 1
1 1 0 0 1
1 1 1 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 1 1 0
1 1 0 1 0
1 0 1 0 1
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
1 1 1 1 1

Linkek

oktatas/szamitastechnika/logika.txt · Utolsó módosítás: 2023/09/11 05:59 szerkesztette: admin