Felhasználói eszközök

Eszközök a webhelyen


oktatas:szamitastechnika:logika

Különbségek

A kiválasztott változat és az aktuális verzió közötti különbségek a következők.

Összehasonlító nézet linkje

oktatas:szamitastechnika:logika [2019/08/22 16:19] (aktuális)
admin létrehozva
Sor 1: Sor 1:
 +[[oktatas:​Számítástechnika|<​ Számítástechnika]]
  
 +====== Logika ======
 +  * **Szerző:​** Sallai András
 +  * Copyright (c) Sallai András, 2011, 2012, 2015
 +  * Licenc: GNU Free Documentation License 1.3
 +  * Web: http://​szit.hu
 +===== 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ó ====
 +
 +Tagadás vagy NOT
 +
 +^  A  ^  ¬A  ^
 +|  0  |  1  |
 +|  1  |  0  |
 +
 +
 +==== Konjunkció ====
 +
 +AND vagyis ÉS művelet
 +
 +^  A  ^  B  ^   A ∧ B  ^
 +|  0  |  0  |  0  |
 +|  1  |  0  |  0  |
 +|  0  |  1  |  0  |
 +|  1  |  1  |  1  |
 +
 +
 +==== 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 =====
 +  * http://​oscience.info/​mathematics/​boolean-algebra-2/​
 +  * http://​www.ee.surrey.ac.uk/​Projects/​Labview/​boolalgebra/​index.html
 +  * http://​en.wikipedia.org/​wiki/​Logic_gate
 +  * [[http://​en.wikipedia.org/​wiki/​Boolean_algebra_(structure)]]
 +  * http://​en.wikipedia.org/​wiki/​Boolean_logic
 +  * http://​en.wikipedia.org/​wiki/​De_Morgan%27s_laws
 +  * http://​en.wikipedia.org/​wiki/​George_Boole
 +  * http://​hu.wikipedia.org/​wiki/​Logikai_kapu
 +  * http://​hu.wikipedia.org/​wiki/​Boole-algebra
 +  * [[http://​hu.wikipedia.org/​wiki/​Boole-algebra_(informatika)]]
 +  * http://​hu.wikipedia.org/​wiki/​De_Morgan-szab%C3%A1lyok
oktatas/szamitastechnika/logika.txt · Utolsó módosítás: 2019/08/22 16:19 szerkesztette: admin