Mathematics | Logic » Logikai műveletek

Logikai műveletek Augustus de Morgan nevéhez fűződik az arisztotelészi logika alapján a logikai műveletek algoritmizálására tett első kísérlet. Formális logika című könyve veti meg a formális logika törvényeit. Georg Boole angol matematikus a formális matematika törvényeit a matematikában alkalmazta, de nem kapott számottevő visszajelzést. Claude E. Shannon tárgyalta a számítógépek kialakításával, magvalósításával kapcsolatos problémákat, hogy az elekronikus relék rendszerével logikai műveletek során hogyan lehet megvalósítani. A matematikai logika következtetések szerestésének vizsgálatával foglalkozik. Fontos fogalma az ítélet, vagy más néven kijelentés. Ez egy olyan kijelentő mondat, amelynek csak két értéke lehet: igaz vagy hamis, ez a logikai érték. A kijelentés-logika azzal foglalkozik, hogy vizsgálja a kijelentések közötti műveleteket. Csak azt tekintjük kijelentés-logikai műveletnek, amelynek az

eredménye szintén kijelentés és logikai értékét egyértelműen maghatározza a komponensek logikai értéke (igaz, hamis). Három fő műveletet különböztetünk meg: tagadás (negáció), összekapcsolás (konjunkció) és szétválasztás (diszjunkció). A logikai kifejezés elemi alkotóinak összes lehetséges kombinációját táblázatba foglalva kapujuk meg az igazságtáblát. Negáció – tagadás - not művelet Egy kijelentés negációján a „nem igaz P” vagy „nem P” kijelentést értjük. Jele: not P vagy ¬ P P not P Igaz Hamis Hamis Igaz Tulajdonságai: A kettős tagadás az eredeti kijelentés logikai értékével egyenlő. not not P = P Konjunkció – összekapcsolás – ÉS – and művelet Tetszőleges P és Q kijelentések összekapcsolásán vagy konjunkcióján a P és Q kijelentést értjük. Jele: P and Q P Q P and Q Igaz Igaz Igaz Igaz Hamis Hamis Hamis Igaz Hamis Hamis Hamis Hamis Tulajdonságai: A művelet

szempontjából az állítások sorrendje közömbös, a logikai művelet eredményét nem befolyásolja. P and Q = P and Q Többszörös és kapcsolat esetén a művelet végeredménye szempontjából közömbös, hogy mely kijelentés-párokra végezzük el előbb. P and (Q and R) = (P and Q) and R A művelettel egyazon kijelentés két példányát összekapcsolva a kijelentés értéke nem változik. P and P = P Diszjunkció – szétválasztás – or művelet Tetszőleges P és Q kijelentések diszjunkcióján a „P vagy Q” kijelentést értjük. Jele: P v Q vagy P or Q P Q P or Q Igaz Igaz Igaz Igaz Hamis Igaz Hamis Igaz Igaz Hamis Hamis Hamis Tulajdonságai: A jelentése megegyezik a konjunkciónál bemutatottakkal. P or Q = Q or P P or (Q or R) = (P or Q) or R Itt is igaz, hogy egyazon kijelentés két példányát összekapcsolva diszjunkcióval, a kijelentés értéke nem változik. P or P = P Exclusive or vagy xor – kizáró vagy művelet A művelet

értéke akkor és csak akkor igaz, ha a benne található műveletek közül pontosan és csakis az egyik igaz (minden más esetben a művelet értéke hamis). P Igaz Igaz Hamis Hamis Q Igaz Hamis Igaz Hamis P xor Q Hamis Igaz Igaz Hamis Összetett műveletek az elemi műveletek bizonyos kombinációi. Kódok Kódolásnak nevezzük azt a folyamatot, amikor egy jelhalmaz minden elmének valamely szabály szerint egy másik jelhalmaz elemét feleltetjük meg. A kódolás igen gyakori a hétköznapi életben (hangok betűkké alakítása). Kódképzésnek számos célja lehet: egyik jelkészletből kezelhetőség okán egy másikba való átfordítás (karakterkódolás), a kódolt jelsorozat kisebb mérete (tömörítés), az eredeti jelsorozat értelmezésének nehezítése (titkosítás). Alapvetően két fajtát különböztetünk meg: reverzibilis és irreverzibilis. A kódolás reverzibilis, ha a két jelsorozat elemeinek megfeleltetése kölcsönösen egyértelmű, azaz a

kódolással kapott jelsorozatból a kódolási folyamat ellentétjével a kódolás előtti jelsorozat visszakapható. Ilyet alkalmazunk a karakterek kódolásakor Irreverzibilis kódoláskor a kódolt jelsorozatból nem lehet a kódolás előtti jelsorozatot visszaállítani. A kódolási folyamat nem megfordítható, azaz irreverzibilis Ilyet alkalmazunk egyes titkosítási igények esetén (az így kódolt jelszó nem fejthető vissza). Karakterek kódolása Karakterek számítógépes kezelése csak kódolás útján valósítható meg (betű-számra). A számítógép csak számokat tud kezelni, a karaktereket ezért számokká kell alakítani. A kódolásnak természetesen reverzibilisnek kell lennie. Több megoldás is lehetséges BCD A decimálisan ábrázolt szám számjegyeit kettes számrendszerben jelenítni meg, a tízes számrendszerbeli jegyekhez digitenként négy-négy kettes számrendszerbeli számjegy szükséges. EBCDIC Egy korai egységesítési kísérlet

karakter jegyeket ez is binárisan ábrázolja. Nyolc bites kódkészlet, főleg az IBM nagyszámítógépei alkalmazták. ASCII Az USA szabványügyi hivatala tette közzé ezt a karakter-kód összerendelést. Két típusa van a 7 és a 8 bites. 7 bites: eredetileg a byte-nak csak az alsó 7 bitjét használták. Így 27=128 különféle jel kódolható. Amíg szinte kizárólag az angol nyelv támogatása volt a feladat, addig ez elegendő is volt. 8 bites: a nemzeti nyelvek megjelenésével a kódtábla bővítése vált szükségesé. A 8 bites ASCII kódtábla 28=256 különböző jel kódolására alkalmas. Mivel egy kódtábla még így sem tudja valamennyi nyelv speciális jeleinek leképezését elvégezni, különféle kódtáblák alkalmazása vált szükségessé. Az alsó 128 jel karakter megfeleltetése ezekben közös, a kódtáblák a felső 128 jel kódolásában térnek el egymástól. Az egyes kódtáblákat – operációs rendszer szintjén telepítve – az

alkalmazói programok elérhetik. A kódtáblák felismerése, az átalakítás egyikéből a másikba nem mindig lehetséges. UNICODE A kód több byte-on tárolódik. Pl 2 byte-on, 16 biten tárolva 216=65535-féle jel kódolására lehetséges, a kódtáblák megkülönböztetésére nincs szükség. A korszerű operáció rendszerek UNICODE kódolást használnak. UTF-8 Változó hosszúságú UNICODE karakterkódolási eljárás. 1-8 byte-ot használ a jel kódolására Visszafelé kompatibilis a 7 bites ASCII szabvánnyal. Egyéb kódrendszerek Morse-jelek: Samuel Finlei Morse 1837-ben szabadalmi kérelmet nyújt be két jelből (rövid, hosszú) álló jelkészlettel kódolt üzenettovábbítás céljára. Megoldása betűket kódol Eltérő a jelhossz, emiatt a jelek, betűk és szavak között elválasztó jelre van szükség, ez tömörség szempontjából nem kedvező. Baudot-kód: Emile Baudot multiplex rendszernek nevezett kódot dolgozott ki. Ez öt bináris

helyiértékben ábrázolja jeleket. A fix jelhossz miatt nem kell karaktervégre jel, e a ritkábban előforduló jeleket is öt helyiértéken ábrázolja, ezért nem nagyon tömör. Tömörítő eljárások Huffman-algoritmus: a tömörítés során ma általánosan használt kódolási eljárás. Lényege a változó jelhossz, illezve az, hogy a kódolandó adathalmazhoz igazodik. A kódolandó jelsorozat gyakrabban előforduló elemeit rövidebb jellel kódolja. Az alkalmazott eljárás (prefix kód: egyik kód sem része a másiknak) biztosítja, hogy a kódolt jelhalmazban egyértelműek legyenek az egyes jelek, jelvége nem szükséges. RLE: igen egyszerű kódolás, a sok ismétlődést, azonos jelsorozatokat tartalmazó jelsorozat méretét csökkenti. Az azonos jelekből álló sorozatok előfordulását a kódolandó jelsorozatban egy jelölővel és az ismétlődések számával kódolja a kódolt jelsorozatban. Lempel-Ziv-Welch algoritmus: szintén a tömörítés

során használt kódolási eljárás. A kódolandó jelhalmazban az azonos elemekből álló sorozatot egy jellel helyettesíti. Ezt használja például az igen elterjedt GIF képállomány típus is. RSA algoritmus: titkosításra és hitelesítésre egyaránt alkalmas kódolás. Aszimmetrikus titkosító algoritmus, a nagy számok faktorizációján alapul: az N = p*q szorzatot, amennyiben N elég nagy, valamint p és q prímszámok, nem lehet a szorzás elvégzése után elfogadható időn belül prímtényezőire bontani. N bitekben mért hossza a kódolás erősségét is jellemzi, szokásos értékei: 128, 256, 512 vagy 1024. Irreverzibilis kódolás A kódolás során a kódolandó jelsorozatról készített kódból ne lehet a módszer inverzével az eredeti jelsorozatot helyreállítani. Ilyen például az MD5 eljárás Ez egy széles körben alkalmazott úgynevezett lenyomatkészítő eljárás. Bemenete egy tetszőleges hosszúságú jelsorozat, ehhez rendel egy állandó

hosszúságú jelsorozatot. Az alkalmazott módszer egyik fontos jellemzője, hogy visszafelé nem működik, azaz az MD5 ismeretében az eredeti jelsorozat nem állítható helyre. Jellemzője még, hogy amennyiben az eredeti jelsorozat bármennyire kicsit is megváltozik, az ugyanilyen algoritmussal a megváltozott jelsorozatról készített MD5 lenyomat jelentősen eltér az előzőtől. Éppen ez a tipikus felhasználási módja: pl. letöltésre szánt állományok MD5 lenyomatát is közzéteszik, ha ez a letöltött anyagról elkészített MD5 lenyomattal nem egyezik, akkor az anyag nem tekinthető autentikusnak, azaz nem egyezik meg az eredeti MD5 készítésekor létezővel