Mathematics | Logic » Amit a logikáról tudni illik

Amit a logikáról tudni illik 1. MATEMATIKAI LOGIKA Ítélet fogalma: egy mondat, mely speciális feltételeknek eleget tesz, azaz olyan szavakkal, vagy más szimbólumokkal kifejezett mondat, objektum, amely egyértelműen igaz, vagy hamis. Ezeket a jelzőket az ítélet logikai értékének/logikai változónak nevezzük Az ítélet kétértékű változó. Jelölése: latin betűkkel (pld. i (igaz), h (hamis), T (true), F (false) Lehet: - egyszerű ítélet: melyek nem bonthatók fel ítéletekre. - összetett ítélet: szerkezetük bonyolultabb, több ítéletet tartalmaznak. 2. LOGIKAI MŰVELETEK Negáció: „NEM” egyoperandusos logikai művelet, egy állítás logikai értékét ellenkezőjére változtatja. Jele:  Definíció: A logikai értéke igaz, ha A hamis és hamis, ha A értéke igaz. A A i h h i Konjukció: „ÉS” művelet. Két ítélet összekapcsolása A két ítélet egyszerre, együtt igaz, melyből egy egészen más, harmadik ítélet születik

A két ítélet összekapcsolása a konjukció (ÉS) Jele:  Definíció: Az AB konjukció logikai értéke akkor és csak akkor igaz, ha A és B logikai értéke (egyszerre mind a kettő) igaz. A i i h h B i h i h A B i h h h Diszjunkció: „VAGY” művelet összetett ítéletek előállítására. Az A vagy B kapcsolat azt jelenti, hogy vagy az A, vagy a B ítélet igaz, de megengedjük azt is, hogy egyszerre álljon fenn a két tény, az összetett ítélet ekkor is igaz. Ezt a logikai kapcsolatot diszjunkciónak – logikai VAGY, logikai összeadás – nevezzük. Jele: V Definíció: A v B diszjunkció logikai értéke akkor és csak akkor igaz, ha A és B közül legalább az egyik igaz. A i i h h B i h i h AvB i i i h Implikáció: A-ból következik B, azaz az egyik ítéletből következik a másik. AB új ítélet születik, vagyis A implikálja B-t. Jele:  Az AB implikáció megfordításán a BA implikációt értjük Definíció: Az AB

implikáció akkor és csak akkor hamis, ha A igaz és B hamis. A i i h h B i h i h AB i h i i 1 Ekvivalencia: Ha AB implikáció igaz, akkor a megfordítottja a BA implikáció lehet igaz is, hamis is. Ha a két implikáció logikai értéke megegyezik, vagyis ha két ítélet mindig azonos értékű, akkor AB, azaz A ekvivalens B-vel. Jele:  Definíció: AB akkor és csak akkor igaz, ha AB és BA is igaz. A i i h h Példa: B i h i h AB i h h i pq (p V q)  (p  s) V (p V s) D p i i i i h h h h q i i h h h h i i p V q i i i i i i h h s i h i h h i h i p  s h i h i h h h h D h i h i h h h h p V s i h i h i i i i i i i i i i i i 3. TOVÁBBI LOGIKAI MŰVELETEK NAND művelet: „NEM-ÉS” művelet, olyan logikai áramkör, amely a NEM-ÉS műveletet valósítja meg, vagyis az adott bemeneti logikai változókra a NEM-ÉS művelet eredményét képezi. A NAND több-bementű logikai elem. Jele:  Definíció: Az AB

ítélet akkor és csak akkor hamis, ha mindkét ítélet igaz. Felírható még az AB =  (AB) formában. A i i h h B i h i h AB h i i i NOR művelet: „NEM-VAGY” művelet. olyan logikai áramkör, amely a NEM-VAGY műveletet valósítja meg, vagyis az adott bemeneti logikai változókra a NEM-VAGY művelet eredményét képezi. A NOR több-bementű logikai elem, amelynek a kimenetén akkor és csak akkor jelenik meg L szint, ha legalább egy bemenetén H szint van. Jele:  Definíció: Az AB ítélet akkor és csak akkor igaz, ha mind az A, mind a B hamis. A i i h h B i h i h AB h h h i 2 4. LOGIKAI KIFEJEZÉSEK Logikai kifejezés: a logikai műveleti jelek, zárójelek, zárójel-párok és operandusok (ítéletek) sorozata. A logikai kifejezések logikai (kétértékű) függvények, leképezések, melyek a bennük szereplő ítéletek értékeire vagy igaz, vagy hamis értékeket vesznek fel. Logikai értékek kiszámítása: a bennük szereplő

változóknak adott értékekre elvétezzük a műveleteket. A műveletek végrehajtásának sorrendje: a) a műveletek közötti elsőbbségi sorrend (precedencia): - elsődleges a negáció (NEM művelet) - másodlagos a konjukció (ÉS művelet) - harmadlagos diszjunkció (VAGY művelet) - negyedleges az implikáció (művelet) - ötödleges az ekvivalencia (művelet) Minden operandus a vele szomszédos operandus közül ahhoz tartozik, amelyhez a magasabb precedenciájú műveleti jel kapcsolja. b) „balról jobbra” szabály: egy operandus, amelynek két oldalán egyenértékű műveleti jelek állnak, a tőle balra lévő operandushoz csatlakozik. Logikai kifejezések igazságtáblázata: a logikai kifejezés egy függvény (annyi változós, ahány ítélet szerepel benne), amelynek konkrét értékét (igaz, vagy hamis) a változók konkrét értékei határozzák meg. A logikai függvényt igazságtáblázattal is megadhatjuk. Ez annak felel meg, ahogyan a valós

függvényeket is táblázattal adjuk meg. Tautológ logikai kifejezések: Az L logikai kifejezést tautológiának hívjuk, ha L értéke a benne szereplő ítéletek (változók) bármilyen értékére mindig igaz. Ha viszont L értéke mindig hamis, akkor ellentmondásnak hívjuk a kifejezést. Tautológia: azonosan igaz Ellentmondás: azonosan hamis Logikai kifejezések ekvivalenciája: Az A és B logikai kifejezések ekvivalensek, ha P 1 , P 2 , .P n változók minden konkrét n-esére az A és B kifejezések ugyanazt az értéket veszik fel. Jele: = Logikai kifejezések egyszerűsítése: a kifejezésben szereplő bármelyik kifejezést vele ekvivalens (egyenlő) kifejezéssel helyettesíthetünk. A tétel alapján egy logikai kifejezést átalakíthatunk, egyszerűsíthetünk, helyettesítés-sorozatokat végzünk. Ez a származtatás Jele: : Duális logikai kifejezések: bármilyen logikai kifejezés helyettesíthető vele ekvivalens ilyen kifejezéssel. Definíció: Az A

és A* logikai kifejezések egymás duálisai, ha egymásból úgy származtathatók, hogy a VAGY műveletet (v) az ÉS művelettel (), az ÉS-t pedig a VAGY művelettel helyettesítjük. A változók is a kifejezések duálisai. Végtelen logikai kifejezések: végtelen sok logikai kifejezés véges számú csoportba helyezhető. Funkcionálisan teljes művelethalmaz: a logikai műveletek azon halmazát, amelynek elemeivel bármely logikai kifejezés felírható, funkcionálisan teljes művelethalmaznak nevezzük. Pld a {, ) és a {v, ) halmaz 5. LOGIKAI KIFEJEZÉSEK NORMÁLFORMÁJA Elemi kifejezések: Elemi kifejezés része is elemi, egy változó és negáltja (fordítottja) is szerepel. Definíció: a P 1 , P 2 , .P n logikai változóknak (ítéleteknek) és negáltjaiknak konjukcióját (szorzatát) elemi szorzatnak, diszjunkcióját (összegét) elemi összegnek nevezzük. Diszjunktív normálformák: minden logikai kifejezés felírható elemi szorzatok

összegeként. Egy logikai kifejezéshez nem feltétlenül egyetlen diszjunktív normálformát lehet hozzárendelni. 3 Konjuktív normálformák: az elemi összegek szorzatából álló kifejezést konjuktív normálformának nevezzük. Pld. (P v Q)  (R v Q)  (R v Q), vagy pld P  (P  Q) : P  (P v Q) Perfekt normálformák: speciális elemiek, primitív elemi szorzatok, összegek. Definíció: a P 1 , P 2 , P n logikai változók azon elemi szorzatait (összegeit), melyekben mindegyik változó szerepel, de egyidejűleg nem tartalmazzák a változót és negáltját, teljes (primitív) elemi szorzatoknak (összegeknek) nevezzük. Perfekt diszjunkt normálformák: azokat a logikai kifejezéseket, amelyek primitív elemi szorzatok összegeiből állnak, perfekt (teljes) diszjunkt normálformának nevezzük. A perfekt diszjunkt normálformákat 4 lépéssorozattal hozzuk létre. Perfekt konjuktív normálformák: az elemi összegek konjukciójából

álló logikai kifejezéseket perfekt konjuktív normálformának nevezzük. 6. LOGIKAI ÁRAMKÖRÖK Logikai áramkörök: a matematikai logika két értéket felvevő ítéletekkel (logikai változókkal) foglalkozik, így az ítéletek jól reprezentálhatók két egymástól jól megkülönböztethető – kétállapotú – elemekkel, szerkezetekkel, melyek lehetnek mechanikusak, elektromosak, elektronikusak, mágnesesek stb. Egyszerű áramkör: az áramkörökkel reprezentált ítéleteknél az igaz érték = 1, a hamis érték = 0. Pld P kapcsoló nyitva, akkor az égő nem világít, ha bekapcsoljuk világít. S: az égő világít Azaz P: a p kapcsoló bekacsolva, S: az s égő világít. p kapcsoló P 1 0 + S 1 0 s lámpa - ÉS művelet áramköre: 1-gyel bekapcsolva, világít, 0-val az ellenkezőjét jelöljük. Az égő akkor és csak akkor világít, ha mindkét kapcsoló be van kapcsolva, konjukció azaz S = P  Q p kapcsoló q kapcsoló s VAGY művelet

áramköre: az áramkör a P, Q logikai változók diszkunkciójának felel meg, az égő akkor világít, ha a P, vagy a Q, mindkét kapcsoló be van kapcsolva, azaz S = P v Q p kapcs. P 1 1 0 0 Q 1 0 1 0 P 1 1 0 0 S 1 0 0 0 Q 1 0 1 0 S 1 1 1 0 vagy q kapcs. s 4 Kapuáramkörök: szimbolikus áramkörök, ezekből épülnek fel a bonyolultabb összetett logikai kifejezéseket reprezentáló áramkörök. Az alkalmazott szimbólumok a számítógépek, illetve más digitális mikroelektronikai berendezések tervezésénél ténylegesen alkalmazott jelek, ebből alkotott blokkdiagrammal írják le az adott berendezés működését. VAGY-kapu: más néven OR-kapu, a v műveletet (diszjunkciót) valósítja meg. input p q 1 1 1 0 0 1 0 0 p r q output p+q 1 1 1 0 ÉS-kapu: más néven AND-kapu, a  műveletet (konukciót) valósítja meg. input p q 1 1 1 0 0 1 0 0 p q r output p q 1 0 0 0 NEM-kapu: más néven NOT-kapu a  műveletet (negációt) valósítja meg.

p NOR-kapu szimbóluma: a b input p 1 0 r output p 0 1 NAND-kapu szimbóluma: a b 5