A számítógép-építés logikai alapjai. A számítógépes tervezés logikai alapjai A kommutativitás szabálya. logikai szorzás és logikai összeadás

"A kapott egész hányados kisebb, mint 2?"

A bináris összeadás végrehajtásakor be kell tartania a következő szabályt: „A számokat számjegyekkel összegezzük, és ha többlet lép fel, akkor az egység balra kerül a legjelentősebb számjegyhez”, azaz. Folyamatosan elemezni kell:

– Túlkínálat van? "Nem igazán"

Logikai algebra

A 19. század közepén jelent meg a logikai algebra. George Boole angol matematikus munkáiban. A hagyományos logikai feladatokat algebrai módszerekkel próbálta megoldani.

Logikus kijelentés- bármely kijelentő mondat, amelyről határozottan igaznak vagy hamisnak mondható. Például a „6 páros szám” mondatot állításnak kell tekinteni, mert igaz; a „Róma Franciaország fővárosa” mondat is állítás, mivel hamis.

Természetesen nem minden mondat logikus kijelentés.

Például a mondatok nem állítások: „A 204-es csoport diákja”, „Helló!”, „Több mint 1000 diák van az egyetemen”, „Jó tanuló” - mivel lehetetlen megítélni az igazukat vagy hamisságukat (vagy további információra van szükség a mondat kijelentésévé vált, például: „Petrov jó tanuló” vagy „több mint 1000 diák van a szamarai 15. számú főiskolán”).

A logikai algebra minden állítást csak egy nézőpontból vesz figyelembe – legyen az igaz vagy hamis.

Vegye figyelembe, hogy gyakran nehéz megállapítani egy állítás igazságát. Például az „India-óceán felszíne 75 millió km2” állítás az egyik helyzetben hamisnak, a másikban igaznak tekinthető (hamis - mivel a megadott érték pontatlan és egyáltalán nem állandó; igaz - ha mintegy közelítésnek tekintjük, a gyakorlatban elfogadható).

A hétköznapi beszédben használt „nem”, „és”, „vagy”, „ha, akkor”, „akkor és csak akkor” és más szavak és kifejezések lehetővé teszik, hogy a már megadott állításokból újakat alkossanak. Az ilyen szavakat és kifejezéseket hívják logikai összeköttetések.

Más utasításokból logikai konnektívumokkal képzett utasításokat hívjuk összetett. A nem összetett állításokat ún alapvető. Például az „Ivanov tanuló”, „Ivanov kitűnő tanuló” elemi állításokból egy kötőszó segítségével megkaphatjuk az „Ivanov tanuló és kiváló tanuló” összetett állítást.

A logikai állításokra való hivatkozáshoz neveket kapnak. Jelölje A azt az állítást, hogy „Iván nyáron a tengerbe megy”, B pedig azt, hogy „Iván nyáron a hegyekbe megy”. Ezután az „Iván nyáron a tengert és a hegyeket is meglátogatja” összetett állítás röviden leírható: „A és B”. Itt az ÉS egy logikai kapcsoló; Az A, B logikai változók, amelyek csak két értéket vehetnek fel: „igaz” és „hamis”, amelyek 1-gyel, illetve 0-val vannak jelölve.

Az algebrában az állításokat logikai változók nevével jelöljük, amelyek csak két értéket vehetnek fel: „igaz” (1) és „hamis” (0).

Tekintsük a logikai utasításokkal végrehajtható műveleteket.

Negációs művelet. A NOT szóval kifejezett műveletet negációnak vagy inverziónak nevezzük, és egy sáv jelzi az utasítás felett. Az A állítás igaz, ha A hamis, és hamis, ha A igaz. Például: „A Hold a Föld műholdja” (A); „A Hold nem a Föld műholdja” (A).

Legyen A = „Kétszer kettő egyenlő négy” igaz állítás, akkor a logikai tagadás műveletével képzett állítás - „Kétszer kettő nem egyenlő négy” hamis állítás.

F állítást alkotunk, amely az A logikai tagadása:

Egy ilyen állítás igazságát a logikai negációs függvény igazságtáblázata adja meg (2.6. táblázat).

2.6. táblázat A logikai negációs függvény igazságtáblázata

A	F

A konjunkció művelete.

A kopula ÉS által kifejezett műveletet kapcsolatnak, konjunkciónak vagy logikai szorzásnak nevezzük, és „&” jellel jelöljük (jelölhetjük „l” vagy „“ jellel). Az F = A&B állítás csak akkor igaz, ha az A és B állítás is igaz. Például a „10 osztható 2-vel és az 5 nagyobb, mint 3” állítás igaz, de a „10 osztható 2-vel és 5 nem nagyobb 3-mal”, „10 nem osztható 2-vel és 5 nagyobb, mint 5” állítás. 3-nál”, „10 nem osztható 2-vel és 5 nem több 3-nál” hamisak.

Egy F logikai függvény értéke meghatározható ennek a függvénynek az igazságtáblázatával, amely megmutatja, hogy a logikai függvény milyen értékeket vesz fel az összes lehetséges argumentumhalmazhoz (2.7. táblázat).

2.7. táblázat

Igazság táblázat funkciókat logikai szorzás

A	BAN BEN	F

Vegyük például a „2 2 = 4 ÉS 3 * 3 = 10” összetett állítást. Az első egyszerű állítás igaz (A = 1), a második egyszerű állítás hamis (B = 0). táblázat szerint 2.7 meghatározzuk, hogy a logikai függvény „false” értéket vesz fel (F = 0), azaz. ez az összetett állítás hamis.

A diszjunkció működése. Az összekötő VAGY által kifejezett műveletet elválasztásnak vagy diszjunkciónak nevezzük (a lat. disjunctio - osztás), vagy logikai összeadás, és a „v” (vagy „+”) jel jelzi. Az F = A v B állítás akkor és csak akkor hamis, ha mind A, mind B állítás hamis. Például a „10 nem osztható 2-vel VAGY 5 nem nagyobb 3-mal” állítás hamis, de a „10 nem osztható 2-vel VAGY 5 nagyobb mint 3”, „10 osztható 2-vel VAGY 5” állítások nem nagyobb, mint 3”, „10 nem osztható 2-vel VAGY 5 3-nál több” igaz.

Az F függvény egy igazságtáblázat segítségével definiálható, amely megmutatja, hogy egy logikai függvény milyen értékeket vesz fel az összes lehetséges argumentumhalmazhoz (2.8. táblázat).

2.8. táblázat

A logikai összeadás függvény igazságtáblázata

A	V	F

Az implikáció művelete. A követés műveletét, amelyet a „ha..., akkor”, „honnan... következik”, „... utal...” konnektívumokkal fejeznek ki, implikációnak nevezzük, és a „->” jellel jelöljük. Az A->B állítás akkor és csak akkor hamis, ha A igaz és B hamis.

Hogyan köt össze implikáció két elemi állítást? Mutassuk meg ezt a következő állításokkal példaként: „Ez a négyszög négyzet” (A) és „E négyszög körül írható le egy kör” (B). Tekintsük az F = A-»B összetett állítást, ami azt jelenti: „Ha egy adott négyszög négyzet; akkor leírhatsz egy kört körülötte."

Az A-*B állítás háromféleképpen igaz:

1) A igaz és B igaz, azaz. ez a négyszög négyzet, és körberajzolható;

2) A hamis és B igaz, vagyis ez a négyszög nem négyzet, hanem kör írható le (persze ez nem minden négyszögre igaz);

3) A hamis és B hamis, azaz ez a négyszög nem négyzet, és kör nem írható le körülötte.

Csak egy lehetőség hamis: A igaz és B hamis, azaz. Ez a négyszög négyzet, de kör nem rajzolható köré.

Az F függvény az igazságtáblázat segítségével határozható meg (2.9. táblázat): F = A^B

2.9. táblázat

A logikai implikáció függvény igazságtáblázata

A	V	F

A logikai implikáció működése némileg eltér a „kell” szó szokásos értelmezésétől. Ha az első állítás (premissza) hamis, akkor a második állítás (következtetés) igazságától vagy hamisságától függetlenül az összetett állítás igaz. Hamis előfeltevésből bármi következhet.

A propozíciós algebrában az összes logikai függvény logikai transzformációkkal redukálható három alapvetőre: logikai szorzásra, logikai összeadásra és logikai tagadásra.

Igazságtáblázatok összehasonlításával igazoljuk, hogy az A->B implikáció művelete ekvivalens az A v B logikai kifejezéssel (2.10. táblázat).

2.10. táblázat

Az A v B logikai kifejezés igazságtáblázata

A	V	A	A vB
			én

asztal 2.10 teljesen egybeesik a táblázattal. 2.9.

Egyenértékűségi művelet. Az egyenlőség működését, amelyet a „ha és csak akkor”, „szükséges és elégséges”, „...egyenértékű...” kötőszavak fejeznek ki, ekvivalenciának vagy kettős implikációnak nevezzük, és a „<-»» или «~». Высказывание А <->B akkor és csak akkor igaz, ha A és B értéke megegyezik. Például igazak a következő állítások: „A 24 akkor és csak akkor osztható 6-tal, ha a 24 osztható 3-mal”, „23 osztható 6-tal, akkor És csak akkor, ha a 23 osztható 3-mal” - és a következő állítások hamisak: „A 24 akkor és csak akkor osztható 6-tal, ha a 24 osztható 5-tel”, „21 akkor és csak akkor osztható 6-tal, ha 21 osztható 3-mal”.

Az F = A összetett állítást alkotó A és B állítások<-»В, могут быть совершенно не связаны по содержанию.

Összetett állítás F = A<->B-nek van igazságtáblázata (2.11. táblázat).

2.11. táblázat

asztal összetett állítás igazsága A<->BAN BEN

A	V	F

Az ekvivalencia logikai műveletével alkotott összetett állítás akkor és csak akkor igaz, ha mindkét állítás egyszerre hamis vagy igaz.

Az ekvivalencia a következő logikai függvényekkel fejezhető ki:

F=AoB = (AvB)&(BvA).

A logikai műveletek sorrendjét zárójelek határozzák meg. De a zárójelek számának csökkentése érdekében megállapodtunk abban, hogy először a tagadási műveletet (NOT), majd a konjunkciót (AND), majd a diszjunkciót (OR) hajtjuk végre. És végül, de nem utolsósorban – következmények. Ezt a sorrendet a műveletek prioritásának nevezzük.

2.2.2. Az algebrai logika alaptörvényei

A logikai algebrában számos olyan törvény létezik, amelyek lehetővé teszik a logikai kifejezések egyenértékű transzformációját.

1. A kettős tagadás törvénye:

A kettős negatív kiküszöböli a negatívot.

2. Utazási (kommutatív) jog:

A logikai kiegészítéshez

A v B = B v A;

Logikai szorzáshoz

Az utasításokon végzett művelet eredménye nem függ attól, hogy V milyen sorrendben veszik ezeket a kijelentéseket? A közönséges algebrában a + b = b + a; a-b = b-a.

3. Kombinatív (asszociatív) jog:

A logikai kiegészítéshez

(A v B) v C = A v (B v C);

Logikai szorzáshoz

(A&B)&C = A&(B&C).

Ha a jelek megegyeznek, a zárójelek tetszőlegesen elhelyezhetők vagy elhagyhatók.

A közönséges algebrában (a + b) + c = a + (b + c) = a + b + c;

(a b) ■ c = a (b c) = a b c.

4. Elosztási (elosztási) törvény:

A logikai kiegészítéshez

(A v B) & C = (A&C) v (B&C);

Logikai szorzáshoz
(A&B) v C = (A v C)&(B v C).

Ez a törvény határozza meg azt a szabályt, hogy egy általános állítást zárójelbe kell tenni.

A közönséges algebrában az eloszlási törvény csak összeadásra érvényes: (a + b) c = a c + b c.

5. Az általános inverzió törvénye (de Morgan törvényei):

A logikai kiegészítéshez

Logikai szorzáshoz

6. Idempotencia törvénye (tól lat. idem - ugyanaz + potens - erős (szó szerint - egyenértékű)):

A logikai kiegészítéshez

Logikai szorzáshoz

A törvény azt jelenti, hogy nincsenek kitevők.

7. Az állandók kizárásának törvénye:

A logikai kiegészítéshez

Avl = l; AvO = A;

Logikai szorzáshoz

A&1 = A; A&0 = 0.

8. Ellentmondás törvénye:

Lehetetlen, hogy az egymásnak ellentmondó állítások egyszerre igazak legyenek.

9. A harmadik kizárásának törvénye:

Az ugyanarról a témáról szóló két egymásnak ellentmondó állítás közül az egyik mindig igaz, a másik pedig hamis; Nincs harmadik.

10. Az abszorpció törvénye:

A logikai kiegészítéshez:

Logikai szorzáshoz

A&(A v B) = A.

11. Kizárási törvény (ragasztás):

A logikai kiegészítéshez

(A&B)v(A&B) = B;

Logikai szorzáshoz

(AvB)&(AvB) = B.

12. Kontrapozíció törvénye (inverziós szabály):

(A*+B)= (ВвА).

A fenti törvények érvényessége táblázatos módon igazolható: írja fel az összes A és B értékkészletet, számítsa ki azokon a bizonyított kifejezés bal és jobb oldalának értékét, és győződjön meg arról, hogy a a kapott oszlopok értékei egybeesnek.

1. példa Keresse meg X-et, ha XvAvXvA=B.

Az egyenlőség bal oldalának átalakításához egymás után De Morgan törvényét használjuk a logikai összeadáshoz és a kettős tagadás törvényét:

(X&A) v (X&A).

A logikai összeadás elosztási törvénye szerint

A harmadok kizárásának törvénye és az állandók kizárásának törvénye szerint

X&1 = X. Tegyük egyenlővé a kapott bal oldalt a jobb oldallal:

Végül megkapjuk: X = BAN BEN.

2. példa A logikai kifejezés egyszerűsítése (AvBvC)&

&A v B v C. Ellenőrizze az egyszerűsítés helyességét igazságtáblázatok segítségével az eredeti és a kapott logikai kifejezésekhez.

A logikai összeadás általános inverziójának törvénye (de Morgan első törvénye) és a kettős tagadás törvénye szerint

(A v B v C)&A v B v C = (A v B v C)&(A&B&C).

A logikai összeadás elosztási törvénye szerint

(A v B v C)&(A&B&C) = (A&A) v (B&A) v (C&A) v (A&B) v v (B&B) v (C&B) v (A&C) v (B&C) v (C&C).

Az ellentmondás törvénye szerint"

(A&A) = 0; (C&C) = 0.

Az idempotencia törvénye szerint

Az értékeket behelyettesítjük, és a kommutatív törvényt alkalmazva és a kifejezéseket csoportosítva a következőt kapjuk:

O v (A&B) v (A&B) v B v (C&B) v (C&B) v (C&A) v (A&C) v 0.

A kizárás törvénye szerint (ragasztás)

(A&B) v (A&B) = B; (C&B) v (C&B) = B.

OvBvBvBv (C&A) v (A&C) v 0.

A logikai összeadás konstansainak kiküszöbölésének törvénye és az idempotencia törvénye szerint

Behelyettesítjük az értékeket, és megkapjuk:

A logikai szorzás eloszlási törvénye szerint

(C&A) v (A&C) = (C v A) & (C v C) & (A v A) & (A v C). A harmadik kizárás törvénye szerint

(CvC) = l; (AvA) = l. Behelyettesítjük az értékeket, és végül megkapjuk:

A logikai feladatok megoldása hozzájárul az absztrakt gondolkodás fejlesztéséhez, edzi a memóriát és fejleszti a logikát.

2.2.3. A számítógépes tervezés logikai alapjai

A logikai algebra matematikai berendezése nagyon kényelmes a számítógépes hardver működésének leírására, mivel a számítógép fő számrendszere bináris, amely az 1-es és a 0-s számokat használja, és a logikai változóknak két értéke van: 1 (igaz). ) és 0 (hamis).

Ebből két következtetés következik:

Ugyanazok a számítógépes eszközök használhatók a kettes számrendszerben bemutatott numerikus információk és logikai változók feldolgozására és tárolására.

A hardvertervezés szakaszában a logikai algebra lehetővé teszi a számítógépes áramkörök működését leíró logikai függvények jelentős egyszerűsítését, és ennek következtében az elemi logikai elemek számának csökkentését, amelyekből több tízezer alkotja a számítógépes áramkörök fő összetevőit. számítógép.

A számítógépes logikai elem egy elektronikus logikai áramkör része, amely elemi logikai funkciót valósít meg.

A számítógépek logikai elemei az elektronikus áramkörök AND, OR, NOT, NAND, NOR stb. (más néven kapuk), valamint a flip-flop. Ezekkel az áramkörökkel bármilyen logikai függvényt megvalósíthat, amely leírja a számítógépes eszközök működését. A szelepeknek általában kettő-nyolc bemenetük és egy vagy két kimenetük van. A két logikai állapot (1 és 0) ábrázolására a kapukban, a hozzájuk tartozó bemeneti és kimeneti jelek két beállított feszültségszinttel rendelkeznek. Például: 5 és O V.

A magas szint jellemzően igaz értéknek (1), az alacsony szint pedig hamis értéknek (0) felel meg.

Minden logikai elemnek megvan a maga szimbóluma, amely kifejezi logikai funkcióját, de nem jelzi, hogy milyen elektronikus áramkör van benne megvalósítva. Ez megkönnyíti az összetett logikai áramkörök írását és megértését.

A logikai elemek működését igazságtáblázatokkal írjuk le (hasonlóan a függvények igazságtáblázataihoz).

Tekintsük a számítógépes logikai elemek blokkdiagramjait és azok igazságtáblázatait (2.12. táblázat).

Egy ÉS áramkör két vagy több logikai érték konjunkcióját valósítja meg. Az ÉS áramkör kimenete akkor és csak akkor lesz 1, ha minden bemenet 1. Ha legalább egy bemenet 0, a kimenet is 0 lesz;

Egy VAGY áramkör két vagy több logikai érték diszjunkcióját valósítja meg. Ha a vagy áramkör legalább egyik kimenete 1, a kimenete is 1 lesz;

A NOT (inverter) áramkör a negációs műveletet valósítja meg. Ennek az áramkörnek az x bemenete és a z kimenete közötti kapcsolat z = x-ként írható fel. Ha az áramkör bemenete 0, akkor a kimenet 1. Ha a bemenet értéke 1, akkor a kimenet 0;

A NAND áramkör egy ÉS elemből és egy inverterből áll, és az ÉS áramkör eredményét negálja A z kimenet és az áramkör x és y kimenetei közötti összefüggést a következőképpen írjuk fel: z = x & y;

2.12. táblázat

Számítógépes logikai elemek blokkdiagramjai és igazságtáblázataik

Szimbólum	Szerkezeti séma	Igazság táblázat
ÉS
X Y			x	U	x&y
&	X&Y





VAGY
			x	U	xvy
X_Y		XvY






NEM
X_		()X	x	x




ÉS NEM
			x	U	x&y
X Y	& <
X&Y




VAGY NEM
			x	U	xvy
X Y	1 (
XvY

A NOR áramkör egy VAGY elemből és egy inverterből áll, és az OS elvégzi a VAGY áramkör eredményének negálását. A z kimenet és az áramkör x és y bemenetei közötti kapcsolatot a következőképpen írjuk fel: z = xVy.

Kioldó

A számítógép RAM-jának, valamint a processzor belső regisztereinek legfontosabb szerkezeti egysége a trigger. Ez az eszköz lehetővé teszi az információk emlékezését, tárolását és olvasását (minden trigger 1 bitnyi információt tárolhat).

Egy trigger két logikai VAGY elemből és két NEM elemből építhető fel (2.3. ábra, A). Megfelelnek az igazságtáblázatnak (2.13. táblázat).

A triggerek leggyakoribb típusa az RS trigger (tól angol set - install + reset - reset). Két szimmetrikus R és S bemenete, valamint két szimmetrikus Q és Q kimenete van. Impulzusok formájában bemeneti jelek szállíthatók mind a két kimenetre (az impulzus jelenléte a bemeneten egy impulzusnak minősül, és annak hiánya - nulla). Normál állapotban a flip-flop R és S bemenetére 0 jel kerül, a flip-flop pedig 0-t tárol. 1 írásához az S (setup) bemenetre 1-es jel kerül. a jel áthaladása az áramkör szerint, egyértelmű, hogy a flip-flop STATE"

Rizs. 2.3. Trigger áramkör: A- OR és NOT elemeken; b- OR-NOT elemeken

2.13. táblázat Igazságtáblázat

S	R	K	K
		Tiltott


		Bit tárolás

„1” pozícióba kerül, és ott még az S bemenet jelének eltűnése után is stabil marad. A kiváltó 1-re emlékezett, azaz. a Q flip-flop kimenete 1-ként olvasható.

Az információk visszaállítása és az új információk fogadására való felkészülés érdekében az R bemenetre 1-es jel kerül (reset), amely után a trigger visszatér eredeti (nulla) állapotába. Ha az R és S bemenetekre logikai 1-et alkalmazunk, akkor Q és Q állapota nem változik, mindkét bemenetre logikai 0 alkalmazása rendkívüli eredményhez vezethet, ezért a bemeneti jelek ilyen kombinációja tilos.

ábrán. 2.3, b egy trigger megvalósítását mutatja NOR kapuk használatával.

2.2.5. Bináris számösszeadó

A számítógép működésének lehető legegyszerűsítése érdekében a processzorban a matematikai műveletek teljes választéka bináris számok összeadására redukálódik, ezért a processzor fontos eleme az összeadó, amely ezt az összeadást biztosítja.

Bináris számok összeadásakor az aktuális számjegyben összeg keletkezik; ebben az esetben lehetőség van az egységet a legjelentősebb számjegyre átvinni. Jelöljük a kifejezéseket - A, B, carry - P és az összeget - S.

2.14. táblázat

Egyjegyű bináris számösszeadás táblázat

Az asztalról A 2.14 azt mutatja, hogy egy egység átvitele megvalósítható a logikai szorzási művelettel:

ahol P jelentése transzfer; A és B szorzók.

Az összeg meghatározásához a következő kifejezést használhatja:

S = (AvB)&(A&B).

Készítsünk igazságtáblázatot ehhez a logikai kifejezéshez, és győződjünk meg arról, hogy a feltételezésünk helyes (2.15. táblázat).

2.15. táblázat

Az F = (A v B) & (A & B) függvény igazságtáblázata

A	BAN BEN	AvB	A&B	A&B	(AvB)&(A&B)

Rizs. 2.4. Bináris szám félösszeadó áramkör

A kapott logikai kifejezések alapján fel lehet építeni egy félösszeadó áramkört alapvető logikai elemek felhasználásával.

A logikai átviteli képlet segítségével könnyen megállapítható, hogy egy átvitel eléréséhez ÉS kaput kell használni.

Az összeg logikai képletének elemzése azt mutatja, hogy a kimenetnek tartalmaznia kell egy ÉS logikai szorzóelemet, amelynek két bemenete van. Az A v B kezdeti értékek logikai összeadásának eredménye az egyik bemenetre kerül, azaz a VAGY logikai összeadási elemből jelet kell adni rá.

A második bemenethez az eredeti A&B jelek fordított logikai szorzásának eredményére van szükség, pl. a második bemenet a NOT elemtől kap jelet, melynek bemenete az ÉS logikai szorzóelemtől kap jelet (2.4. ábra).

Ezt az áramkört félösszeadónak nevezik, mivel az egyjegyű bináris számok összegzését valósítja meg anélkül, hogy figyelembe venné az alacsony rendű számjegyről való átvitelt.

Ellenőrző kérdések

1. Összefügg-e a logikai algebra megjelenése a személyi számítógép fejlődésével?

2. Nevezze meg az alapvető logikai műveleteket.”

3. Mondjon példákat olyan mondatokra, amelyek nem logikai állítások!

4. Mutassa be az összefüggést a logikai algebra és az információ bináris kódolása között!

5. Melyik logikai elemet kell a legjelentősebb számjegybe elhelyezni, hogy emlékezzen a -5 negatív egészre?

6. Nevezze meg a logikai műveletek prioritásait!

7. Fogalmazza meg a következő állítások tagadását: „2 > 5”;
"10< 7»; «а = 2».

8 Rajzolja meg a derékszögű koordinátarendszerben a területeket (|x|< 1) и

9. Határozza meg az „(A & B) & (C v D)” összetett állítás igazát,
egyszerű kijelentésekből áll: A = „A nyomtató egy kimeneti eszköz
igen információ", B = "Feldolgozó - információtároló eszköz",
C = "Monitor - információs kimeneti eszköz", D = "Billentyűzet -
információfeldolgozó eszköz."

10. Igazságtáblázatok segítségével igazolja, hogy az ekvivalenciaművelet ekvivalens A logikai kifejezésekkel<-» В = (А & В) v (А & В) и A<->B = (AvB)&(AvB).

11. Igazságtáblázatok segítségével bizonyítsa be, hogy az A v B és az A & B logikai kifejezések egyenértékűek.

12. Két argumentum milyen logikai függvényeinek a neve?

13. Hány logikai függvénye van három argumentumnak?

14. Egyszerűsítse a következő logikai kifejezéseket:

(AvA) A&(AvB)&(BvB).

15. Mondjon példákat a mindennapi életből:

ha (nem a és nem b), akkor (c vagy d); (a vagy b) akkor és csak akkor, ha (c vagy nem d).

16. Kövesse nyomon a trigger logikai diagramon, hogy mi történik, amikor az 1. jel érkezik az R bemenetre.

17. Hány alapvető logikai elem szükséges 512 MB információ tárolásához?

a francia nyelv elmélyült tanulmányozásával"

A számítógép logikai alapjai

Számítástechnika tankönyv

10. osztály számára

Tartalom

§1. A logika alapjai……………………………………..…….…………3

2. § Logikai műveletek………………………………..…..….…..5

3. § Logikai képletek. Logikai képlet igazságtáblázata………………………………………………..…………….….8

4. § A logika algebrai alaptörvényei. Logikai képletek egyszerűsítése………………………………………………………………

5. § Logikai feladatok megoldása……………………………………….13

6. § Logikai függvény………………………………………..18

7. § A számítógépek logikai alapjai. Alapvető logikai elemek………………………………………………………………….21

8. § A számítógép logikai elemei. Kioldó és összeadó................................................ ...................................................... ...25

Kérdések az önkontrollhoz……………………………………..29

1. § A logika alapjai.

A bináris információ feldolgozása során a számítógép aritmetikai és logikai műveleteket hajt végre. Ezért a számítógép felépítésének megértéséhez meg kell ismerkedni a számítógép felépítésének alapjául szolgáló alapvető logikai elemekkel. Kezdjük ezt a bevezetést a logika alapvető kezdeti fogalmaival.

Maga a „logika” kifejezés az ókori görög logoszból származik, ami „szót, gondolatot, fogalmat, érvelést, törvényt” jelent.

Logikák– a törvények és a gondolkodási formák tudománya.

Az első tanítások az érvelés formáiról és módszereiről az ókori kelet országaiban (Kína, India) születtek, de a modern logika az ókori görög gondolkodók tanításain alapul. Arisztotelész elsőként különítette el a beszéd logikai formáit annak tartalmától, feltárta a logika terminológiáját, részletesen megvizsgálta a következtetések és bizonyítékok elméletét, számos logikai műveletet leírt, és megfogalmazta a gondolkodás alapvető törvényeit.

A logika alapfogalmai közé tartoznak a következők.

Logikus kijelentés bármely kijelentő mondat, amelyre vonatkozóan egyértelműen meg lehet mondani, hogy igaz vagy hamis.

Tehát például a következő mondat: 6 - páros szám"állításnak kell tekinteni, mert igaz. Mondat" Róma Franciaország fővárosa" is állítás, mert hamis.

Nyilatkozat- Ez egy olyan javaslat, amelyet bizonyítani vagy cáfolni kell.

Például bármely tétel olyan állítás, amely bizonyítást igényel.

Érvelés- állítások vagy állítások sorozata, amelyek bizonyos módon kapcsolódnak egymáshoz.

Például egy tétel bizonyításának folyamatát nevezhetjük érvelésnek.

Következtetés- ez egy olyan gondolkodási forma, amelyen keresztül egy vagy több ítéletből új ítélet születik. A következtetések lehetnek deduktívak, induktívak vagy analógia alapján.

A deduktív érvelésben az érvelés az általánostól a konkrét felé halad. Például két állításból: „Minden fém elektromosan vezetőképes” és „A higany fém”, arra a következtetésre juthatunk, hogy „a higany elektromosan vezető”.

Az induktív érvelésben az érvelés a konkréttól az általános felé halad. Például, miután megállapítottuk, hogy az egyes fémek - vas, réz, cink, alumínium stb. - rendelkeznek elektromos vezetőképességgel, arra a következtetésre jutottunk, hogy minden fém elektromosan vezetőképes.

Következtetés analógiávalátadja az egyik tárgyról szóló tudást a másiknak. Például a Nap és a Föld kémiai összetétele sok tekintetben hasonló. Ezért amikor a Földön ismeretlen hélium kémiai elemet felfedezték a Napon, analógia útján arra a következtetésre jutottak, hogy létezik ilyen elem a Földön.

természetesen nem minden mondat logikus kijelentés. Az állítások nem például mondatok " tizedik osztályos tanuló"És" az informatika érdekes tárgy". Az első mondat nem mond semmit a diákról, a második pedig túl homályos fogalmat használ" érdekes téma A kérdő és felkiáltó mondatok sem állítások, mivel nincs értelme igazukról vagy hamisságukról beszélni.

Olyan mondatok, mint " a városbanA több mint egymillió lakos", "kék szeme van" nem állítások, hiszen igazságuk vagy hamisságuk megállapításához további információra van szükség: melyik városról vagy személyről van szó. Az ilyen mondatokat ún. logikai kifejezések.

Logikai kifejezés egy kijelentő mondat, amely közvetlenül vagy közvetve tartalmaz legalább egy változót, és akkor válik állítássá, ha az összes változót az értékükre cseréljük.

Az állítások igazságát vagy hamisságát vizsgáló tudásterületet ún matematikai logika.

Ahogyan a matematikának egy ágát, az algebrát a változókon végzett műveletek leírására fejlesztették ki, úgy az állítások algebráját vagy a logikai algebrát a matematikai logika logikai kifejezéseinek feldolgozására hozták létre.

Logikai algebra A matematikai logika egyik ága, amely a logikai jelentésük (igazság vagy hamisság) és a rájuk vonatkozó logikai műveletek szempontjából vizsgált állításokat vizsgálja.

A logika algebra a tizenkilencedik század közepén jelent meg az angol matematikus munkáiban. George Boole. Létrehozása kísérlet volt a hagyományos logikai problémák algebrai módszerekkel történő megoldására.

A logikai algebra minden állítást csak egy nézőpontból vesz figyelembe – legyen az igaz vagy hamis. vegye észre, az Gyakran nehéz megállapítani egy állítás igazságát. Tehát például a " felülete indiai Az óceán területe 75 millió négyzetméter. km" egyik helyzetben hamisnak, másikban igaznak tekinthető. Hamis - mert a megadott érték pontatlan és egyáltalán nem állandó. Igaz - ha a gyakorlatban elfogadható közelítésnek tekintjük.

§ 2. Logikai műveletek.

A hétköznapi beszédben használt szavak és kifejezések „nem”, „és”, „vagy”, „ha..., akkor”, „akkor és csak akkor” mások pedig lehetővé teszik, hogy a már megadott állításokból új állításokat hozzon létre. Az ilyen szavakat és kifejezéseket hívják logikai összeköttetések.

Más utasításokból logikai konnektívumokkal képzett utasításokat hívjuk összetett. A nem összetett állításokat ún alapvető.

Tehát például az elemi állításokból " Petrov - orvos", "Petrov - sakkozó"kopula segítségével" És"összetett nyilatkozatot kaphat" Petrov - orvos és sakkozó"úgy értve" Petrov orvos, aki jól sakkozik".

A link segítségével " vagy"ugyanazokból az állításokból összetett állítást kaphatunk" Petrov - orvos vagy sakkozó", ami a logika algebrájában értendő: " Petrov vagy orvos, vagy sakkozó, vagy orvos és sakkozó egyszerre".

Az így kapott összetett állítások igazsága vagy hamissága az elemi állítások igazságától vagy hamisságától függ.

A logikai állításokra való hivatkozáshoz neveket kapnak. Engedd át A az állítást jelzik "Timur nyáron a tengerhez megy"és azon keresztül BAN BEN- nyilatkozat – Timur nyáron a hegyekbe megy. Aztán az összetett állítás "Timur nyáron a tengert és a hegyeket is ellátogatja" röviden így írható A és B. Itt "És"- logikai összeköttetés, A, B- logikai változók, amelyek csak két értéket vehetnek fel - „igaz” vagy „hamis”, „1” és „0” jelöléssel.

Az "és" kötőszóval kifejezett műveletet nevezzük kötőszó(lat. conjunctio - kapcsolat) ill logikai szorzásés egy ponttal jelöljük " . " (jelölhető  vagy & jellel is).

Nyilatkozat A . BAN BEN akkor és csak akkor igaz, ha mindkét állítás AÉs BAN BEN igazak.

Például az állítás "10 osztható 2-vel és 5 nagyobb, mint 3" igaz és állítások "10 nem osztható 2-vel és 5 nem több 3-mal", "10 nem osztható 2-vel és 5 nem több, mint 3", "10 nem osztható 2-vel és 5 nem több 3-nál"- hamisak.

Az összekötő "vagy" (a szó nem kizárólagos értelmében) által kifejezett műveletet ún diszjunkció(lat. disjunctio - felosztás) ill logikus kiegészítésés v (vagy plusz) jellel jelöljük.

Nyilatkozat A v B akkor és csak akkor hamis mindkét állítás AÉs BAN BEN hamis.

Például az állítás "10 nem osztható 2-vel, vagy 5 nem nagyobb 3-nál" hamis és állítások "10 osztható 2-vel vagy 5-tel nagyobb, mint 3", "10 osztható 2-vel vagy 5-tel, nem nagyobb, mint 3", "10 nem osztható 2-vel vagy 5-tel nagyobb, mint 3"- igaz.

A „nem” szóval kifejezett műveletet nevezzük logikustagadás vagy inverzióés az állítás feletti vonal jelzi (vagy egy  jel).

Nyilatkozat  A igaz mikor A hamis, és hamis mikor A igaz.

Például, " A Hold a Föld műholdja"(Egy igaz;" A Hold nem a Föld műholdja" ( A) - hamis.

Az „ha..., akkor”, „a... következik”, „... magában foglalja...” konnektivívákkal kifejezett műveletet ún. következmény(latin implico - szorosan összefüggő), és a  jel jelzi.

Nyilatkozat A BAN BEN hamis akkor és csak akkor A igaz, de BAN BEN hamis.

Hogyan köt össze implikáció két elemi állítást?

Mutassuk meg ezt egy példával az állításokra: "ez a négyszög egy négyzet" (A) És "Egy adott négyszög köré kör írható"(BAN BEN). Vegyünk egy összetett állítást A BAN BEN, úgy értve "Ha egy adott négyszög négyzet, akkor kört lehet körberajzolni."

Eszik három lehetőség, amikor az állítás A BAN BEN igaz:

A igaz és BAN BEN igaz, vagyis ez a négyszög négyzet, és körbeírható kör;

A hamis és BAN BEN igaz, vagyis ez a négyszög nem négyzet, hanem kör írható le körülötte (persze ez nem minden négyszögre igaz);

A hamis és B false, vagyis ez a négyszög nem négyzet, és kör nem rajzolható köré.

Csak egy lehetőség hamis, ha A igaz és B hamis, vagyis ez a négyszög négyzet, de körülötte nem lehet kört leírni.

A hétköznapi beszédben a kötő "ha akkor" az állítások közötti ok-okozati összefüggést írja le. De a logikai műveletekben az állítások jelentését nem veszik figyelembe. Csak azok igazságát vagy hamisságát veszik figyelembe. Ezért nem szabad zavarba hozni a tartalmilag teljesen független kijelentések implikációinak „értelmetlenségét”. Például így: "ha az Egyesült Államok elnöke demokrata, akkor Afrikában vannak zsiráfok", "ha a görögdinnye bogyó, akkor van benzin a benzinkútban."

A „ha és csak akkor”, „szükséges és elégséges”, „...egyenértékű...” konnektívumokkal kifejezett műveletet ún. egyenértékű vagy kettős implikációés  vagy ~ jelöli.

Nyilatkozat A BAN BEN akkor és csak akkor igaz, ha az értékek AÉs BAN BEN egyeznek meg.

Például nyilatkozatok "A 24 akkor és csak akkor osztható 6-tal, ha a 24 osztható 3-mal", "23 akkor és csak akkor osztható 6-tal, ha a 23 osztható 3-mal." igazak és állítások "A 24 akkor és csak akkor osztható 6-tal, ha a 24 osztható 5-tel", "21 akkor és csak akkor osztható 6-tal, ha a 21 osztható 3-mal." hamis.

Nyilatkozatok AÉs BAN BEN,összetett állítást alkotva A BAN BEN, tartalmilag teljesen független lehet, például: "három több mint kettő" (A), "Pingvinek élnek az Antarktiszon" (BAN BEN). Ezen állítások tagadásai az állítások "három nem több kettőnél"( A), "A pingvinek nem élnek az Antarktiszon"( B). Kijelentésekből alakult ki AÉs BAN BENösszetett állítások A BÉs  A  B igazak és állítások A  BÉs  A B- hamisak.

3. § Logikai képletek. Logikai igazság táblázat

képletek.

A logikai változók és a logikai műveletek szimbólumai segítségével bármilyen állítás lehet formalizálni vagyis cserélje ki egy logikai képlettel.

Meghatározás logikai képlet:

Minden logikai változó és az „igaz” („1”) és „hamis” („0”) szimbólumok képletek.

Ha A és B képletek, akkor  A, A. B, A v B, A  B, A  B képletek.

3. A logika algebrájában nincs más képlet.

Az 1. szakasz meghatározza elemi képletek; a (2) bekezdésben megadott szabályok az új képletek bármely adott képletből történő képzésére.

Példaként tekintsük az állítást "Ha veszek almát vagy sárgabarackot, készítek gyümölcstortát." Ez az állítás így van formalizálva (A v B) C. Ugyanez a képlet felel meg az állításnak – Ha Igor tud angolul vagy japánul, akkor fordítói állást kap.

Ahogy a képlet elemzése mutatja (A v B) C, a változóértékek bizonyos kombinációihoz A, BÉs C az "igaz" értéket veszi fel, néhány más kombinációnál pedig a "false" értéket. Az ilyen képleteket ún megvalósítható.

Néhány képlet elfogadja az "igaz" értéket a benne szereplő változók bármely igazságértékére. Például a képlet A v A, az állításnak megfelelő – Helyes ez a háromszög vagy nem? akkor is igaz, ha a háromszög derékszögű, és akkor is, ha a háromszög nem jó. Az ilyen képleteket ún azonosan igaz képletek vagy tautológiák. A tautológiákkal formalizált állításokat nevezzük logikailag igaz állítások.

Egy másik példaként tekintsük a képletet A .  A, ami megfelel például az állításnak "Katya a legmagasabb lány az osztályban, és vannak Kátyánál magasabb lányok az osztályban." Nyilvánvaló, hogy ez a képlet hamis, hiszen bármelyik A, vagy  A szükségszerűen hamis. Az ilyen képleteket ún azonosan hamis képletek vagy ellentmondások. Az ellentmondásokkal formalizált állításokat nevezzük logikailag hamis állítások.

Ha két A és B képlet egyidejűleg, vagyis a bennük lévő változók azonos értékkészletével ugyanazokat az értékeket veszi fel, akkor ezeket az ún. egyenértékű.

Két logikai algebrai képlet egyenértékűségét a "="" szimbólum jelzi. Egy képlet lecserélése egy vele egyenértékűre ún. ekvivalens transzformáció ebből a képletből.

Öt logikai műveletet vettünk figyelembe : tagadás, kötőszó, diszjunkció, implikáció és ekvivalencia.

Következmény keresztül lehet kifejezni diszjunkcióÉs tagadás:

A  B =  Аv В.

Egyenértékűség keresztül lehet kifejezni tagadás , diszjunkció És kötőszó :

A  B = ( A v B) . ( Bv A).

És így, tevékenységektagadás, diszjunkció és konjunkció elegendő a logikai állítások leírásához és feldolgozásához.

A logikai műveletek sorrendjét zárójelek határozzák meg. De a zárójelek számának csökkentése érdekében megállapodtunk abban, hogy először a tagadási műveletet („nem”) hajtjuk végre, majd a kötőszót („és”), a kötőszó után a diszjunkciót („vagy”), végül az implikációt.

Logikai képlet igazságtáblázata– egy táblázat, amely kifejezi a változóértékek és a képletértékek összes lehetséges halmaza közötti megfelelést.

Egy két változót tartalmazó képletnél csak négy ilyen változóérték-készlet létezik: (0, 0), (0, 1), (1, 0), (1, 1).

Ha a képlet három változót tartalmaz, akkor nyolc ilyen halmaz létezik: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0) , 0) , (1, 0, 1), (1, 1, 0), (1, 1, 1).

A négy változós képlet halmazainak száma tizenhat stb. Vagyis ha N akkor a változók száma 2 N– változó értékkészletek száma.

Elemi logikai képletek igazságtáblázata

Konjunkció

Diszjunkció

Inverzió

Következmény

Egyenértékűség

nál nél

x y

nál nél

x  at

 x

nál nél

x  y

nál nél

x  y

A több logikai műveletet tartalmazó képlet értékeinek megtalálásakor kényelmes rögzítési forma egy táblázat, amelyben a változók és a képlet értékei mellett az értékek

köztes képletek.

Példák.

1. Készítsünk igazságtáblázatot a képlethez  x y  (X y) X, amely két x és y változót tartalmaz. A táblázat első két oszlopában felírjuk ezeknek a változóknak négy lehetséges értékpárját, a következő oszlopokban - a közbenső képletek értékeit és az utolsó oszlopban - a képlet értékét.

Változók

Képlet

nál nél

 x

 x y

x  at

 (X  y)

 x y   (x  y)

 x y   (x  y)  x

A táblázatból egyértelműen kiderül az x és y változók összes értékkészletére a képlet 1 értéket vesz fel, azaz van azonos az igaz .

2. Igazságtáblázat a képlethez: (x  y) · (x · y)

Változók

Köztes logikai képletek

Képlet

nál nél

x  at

 (X  y)

 nál nél

X ·  at

 (X  y) · (x · y)

A táblázatból egyértelműen kiderül az x és y változók összes értékkészletére a képlet 0 értéket vesz fel, azaz van egyformán hamis .

3. A képlet igazságtáblázata: (X  y)  X ·z

Változók

Köztes logikai képletek

Képlet

 nál nél

x   y

 (X   y)

 x

 X · z

 (X   y)   x z

A táblázat azt mutatja, hogy a képlet bizonyos esetekben 1-et vesz fel, másokban - 0-t, vagyis megvalósítható.

4. § A logika algebrai alaptörvényei. Egyszerűsítés

logikai képletek.

A logikai képletek ekvivalens transzformációinak célja ugyanaz, mint a közönséges algebrai képletek transzformációinak. A képletek egyszerűsítésére vagy egy bizonyos formára való redukálására szolgálnak a logikai algebra alaptörvényeinek felhasználásával.

Alatt a képlet egyszerűsítése, amely nem tartalmazza az implikáció és az ekvivalencia műveleteit, olyan ekvivalens transzformációt értünk, amely olyan formulához vezet, amely vagy az eredetihez képest kevesebb konjunkciós és diszjunkciós műveletet tartalmaz, és nem tartalmaz nem elemi formulák tagadását, vagy kisebb számú változó előfordulását tartalmazza.

A logika algebrájában a következő alaptörvények teljesülnek, lehetővé téve az előállítást logikai kifejezések azonosságtranszformációi.

Törvény

Teljesítmény

az algebrai logikában

Kommutatív (kommutatív)

a  b = b  a, a  b = b  a

Konjunktív (asszociatív)

a  (b  c) = (a  b)  c,

a  (b  c) = (a  b)  c

Elosztó (elosztó)

a  (b  c) = (a  b)  (a  c) ,

a  (b  c) = (a  b)  (a  c)

De Morgan szabályai

 (a  b) =  a  b ,

 (a  b) =  a  b

A kettős tagadás törvénye (involúció)

  a = a

Műveletek változóval és annak inverziójával

a   a = 0, a  a =1

Műveletek konstansokkal

a  1 = 1, a  1 = a,

a  0 = a, a  0 = 0

Az Idempotencia törvényei

a  a = a , a  a = a

Az abszorpció törvényei

x  (x  y) = x, x  (x  y) = x

A ragasztás törvényei

(x  y)  ( x  y) = y,

(x  y)  ( x  y) = y

A logikai képletek egyes átalakításai hasonlóak a közönséges algebra képleteihez(a közös tényezőt zárójelből kivéve, kommutatív és asszociatív törvények alkalmazása stb.), míg más transzformációk olyan tulajdonságokon alapulnak, amelyekkel a közönséges algebra műveletei nem rendelkeznek(a disztributív törvény használata kötőszóra, abszorpciós törvények, ragasztás, de Morgan stb.).

Nézzünk néhány példát a logikai képletek egyszerűsítésére használt technikák és módszerek.

1. példa

 (X  y) (x)  y) =  X · y (x) y) = x · x · y · y = 0 · y · y = 0 · y =0
(A logikai algebra törvényeit a következő sorrendben alkalmazzuk: de Morgan szabálya, kombinációs törvénye, egy változó műveleti szabálya annak inverziójával és a konstansokkal végzett műveletek szabálya).

2. példa

 x y  (X  y)  x =  x y  X · nál nél x = x (y y) x = x x =1
(A De Morgan-szabályt alkalmazzuk, a közös tényezőt zárójelből kivesszük, a változó műveletek szabályát annak megfordításával alkalmazzuk).

3. példa

(X  y) · (  x  y) · (  x   y) = (x y) · ( x y) · ( x y) · ( x  y) =y ·  x
(A második tényező megismétlődik, amit az idempotencia törvénye megenged; majd az első két és az utolsó két tényezőt kombináljuk, és a ragasztás törvényét alkalmazzuk).

4. példa

 (x y   z ) =  (x · y) ·  z =  (x · y) · z
(Először is biztosítjuk, hogy a tagadójel csak az egyes változók előtt jelenjen meg, és ne azok kombinációja előtt, ehhez De Morgan szabályát alkalmazzuk; ezután a kettős tagadás törvényét alkalmazzuk);

5. példa.

x y x · y ·z  x · r ·z= x · (y  y · z  z · р) = x · (y · (1  z )  z · р) =

= x (y z · R)

(A közös tényezőket zárójelből kivesszük; a konstansokkal végzett műveletek szabályát alkalmazzuk);

Példa 6.

x  y  x y z  x  y z  x  (y z)= x (  y  y z   y z   (y z)) =

= x · (( y  y · z )  (y · z   (y · z )) = x · ( y  y · z  1) = x · 1 =x
(A közös x tényezőt kivesszük a zárójelekből, a zárójelben lévő kifejezéseket összevonjuk - az elsőt a harmadikkal, a másodikat a negyedikkel, a diszjunkcióra a változó inverziós műveletének szabálya érvényes);

Ezekből a példákból jól látható, hogy a logikai képletek egyszerűsítésekor nem mindig nyilvánvaló, hogy a logikai algebra melyik törvényét kell alkalmazni egy adott lépésben. A készségek tapasztalattal jönnek.

5. § Logikai feladatok megoldása.

A logikai problémák sokfélesége igen nagy. Megoldásukra is számos mód van. De a legelterjedtebb a következő három módszer a logikai problémák megoldására:

a logikai algebra segítségével;

táblázatos;

érvelés révén.

Ismerjük meg őket egyenként.

I. Logikai feladatok megoldása logikai algebra segítségével

A következőket gyakran használják megoldási diagram:

tanulmányozzák a probléma állapotát;

bevezetik a logikai utasítások jelölési rendszerét;

egy logikai képletet készítünk, amely leírja a logikai összefüggéseket a problémafeltételek összes állítása között;

meghatározzák ennek a logikai képletnek az igazságértékeit;

A képlet kapott igazságértékeiből meghatározzák a bevitt logikai állítások igazságértékeit, amelyek alapján következtetést vonnak le a megoldásról.

1. példa Három barát, a Forma-1-es versenyrajongók vitatkoztak a közelgő verseny eredményeiről.

- Meglátod, nem Schumacher lesz az első” – mondta John. Hill lesz az első.

- Nem, a győztes, mint mindig, Schumacher lesz” – kiáltott fel Nick. - Nincs mit mondani Alesiről, nem ő lesz az első.

Peter, akihez Nick fordult, felháborodott:

- Hill nem látja az első helyet, de Alesi pilóta a legerősebb autót.

A versenyszakasz végén kiderült, hogy a két barát két feltételezése beigazolódott, és a harmadik barát mindkét feltételezése téves. Ki nyerte a versenyszakaszt?

Megoldás.

Vezessünk be jelölést a logikai állításokhoz:

SH- Schumacher nyerni fog; x- Hill fog nyerni; A- Alesi fog nyerni.

Nick „Alesi vezeti a legerősebb autót” sora nem tartalmaz semmilyen kijelentést arról, hogy ez a sofőr hol fog elfoglalni, ezért a további megbeszélések során nem veszik figyelembe.

Jegyezzük fel az egyes barátok nyilatkozatait:

János:  W · X, Nick: SH · A, Péter:  x

Tekintettel arra, hogy két barát feltételezése beigazolódott, a harmadik feltételezései pedig tévesek, leírjuk és leegyszerűsítjük az igaz állítást

( W · X)·(W · A) · Х  ( W · Х)· (W · А)· Х   ( W · X)·(W · A)·  X = =( W · X · W · A · X) ( W · X ·  (W · A) ·  X) (W  X) · W · A ·  X = = 0  0  W · A ·  X = W · A ·  X

Nyilatkozat SH · A · x csak akkor igaz W=1, A=0, X=0.

Válasz. A versenyszakasz győztese Schumacher lett.

II. Logikai feladatok megoldása igazságtáblázatok segítségével.

Ennek a módszernek a használatakor a feladatban foglalt feltételeket és az érvelés eredményeit speciálisan összeállított táblázatok segítségével rögzítjük.

2. példa A szimfonikus zenekar három zenészt fogadott fel: Brownt, Smitht és Wissont, akik hegedülni, furulyán, brácsán, klarinéton, oboán és trombitán tudtak játszani.

Ismeretes, hogy:

Smith a legmagasabb;

a hegedűs alacsonyabb, mint a furulyás;

hegedűs és furulyás játékosok és Brown szeretik a pizzát;

amikor veszekedés támad egy brácsás és egy trombitás között, Smith kibékíti őket;

Brown nem tud trombitán vagy oboán játszani.

Milyen hangszereken játszik minden zenész, ha mindegyik két hangszeren játszik?

Megoldás.

Készítsünk egy táblázatot, és tükrözzük benne a probléma feltételeit, töltsük ki a megfelelő cellákat 0 és 1 számokkal, attól függően, hogy a megfelelő állítás hamis vagy igaz.

Mivel három zenész van, hat hangszer, és mindegyik csak két hangszeren játszik, kiderül, hogy mindegyik zenész olyan hangszeren játszik, amit a többiek nem ismernek.

A 4. feltételből az következik, hogy Smith nem brácsázik vagy trombitál, a 3. és 5. feltételből pedig az, hogy Brown nem hegedülhet, furulyázhat, trombitálhat és oboán. Ezért Brown hangszerei a brácsa és a klarinét. Tegyük ezt a táblázatba, és töltsük fel nullákkal a "brácsa" és a "klarinét" oszlop többi celláját:

hegedű

fuvola

alt

klarinét

oboa

cső

Barna

Kovács

Visson

A táblázat azt mutatja, hogy csak Visson tud trombitálni.

Az 1. és 2. feltételből az következik, hogy Smith nem hegedűművész. Mivel sem Brown, sem Smith nem hegedül, Wisson a hegedűs. A Visson által játszott két hangszer definiálva van, így a "Visson" húr többi cellája nullákkal tölthető fel:

hegedű

fuvola

alt

klarinét

oboa

cső

Barna

Kovács

Visson

A táblázat azt mutatja, hogy csak Smith tud furulyán és oboán játszani.

hegedű

fuvola

alt

klarinét

oboa

cső

Barna

Kovács

Visson

Válasz: Brown brácsán és klarinéton játszik, Smith furulyán és oboán, Wisson pedig hegedűn és trombitán játszik.

3. példa Három osztálytárs - Vlad, Timur és Yura - találkozott 10 évvel az érettségi után. Kiderült, hogy egyikük orvos, másikuk fizikus, harmadikuk jogász lett. Az egyik a turizmusba, a másik a futásba, a harmadik a rögbibe esett bele.

Yura azt mondta, hogy nincs elég ideje a turizmusra, bár a nővére az egyetlen orvos a családban és lelkes turista.

Az orvos azt mondta, hogy osztja kollégája szenvedélyét.

Vicces, de két barát nevének egyetlen betűje sem szerepel a szakmájuk és a hobbijaik nevében.

Határozza meg, hogy ki mit szeret szabadidejében csinálni, és kinek milyen szakmája van.

Megoldás.

Itt a kezdeti adatok hármasokra vannak osztva (név - szakma - hobbi).

Yura szavaiból egyértelmű, hogy nem érdekli a turizmus, és nem is orvos. Az orvos szavaiból az következik, hogy turista.

Név

Yura

Szakma

orvos

Lelkesedés

idegenforgalom

Az „a” betű az „orvos” szóban azt jelzi, hogy Vlad szintén nem orvos, ezért Timur orvos. Nevében a "t" és az "r" betűk szerepelnek, amelyek a "turizmus" szóban találhatók, ezért a második barátja, akinek szakmájának és hobbijainak nevében egyetlen betű sem szerepel nevének - Yura. Yura nem ügyvéd vagy rögbijátékos, mivel a neve „u” és „r” betűket tartalmaz. Ezért végre megvan:

Név

Yura

Timur

Vlad

Szakma

fizikus

orvos

jogász

Lelkesedés

fuss

idegenforgalom

rögbi

Válasz. Vlad ügyvéd és rögbijátékos, Timur orvos és turista, Yura fizikus és futó.

III. Logikai feladatok megoldása érvelés segítségével

Ezt a módszert általában egyszerű logikai problémák megoldására használják.

4. példa Vadim, Szergej és Mihail különféle idegen nyelveket tanul: kínait, japánt és arabot. Arra a kérdésre, hogy melyik nyelvet tanulják, az egyik azt válaszolta: „Vadim kínaiul tanul, Szergej nem tanul kínaiul, és Mihail nem tanul arabul.” Később kiderült, hogy ebben a válaszban csak egy állítás igaz, a másik kettő pedig hamis. Milyen nyelvet tanulnak az egyes fiatalok?

Megoldás. Három állítás létezik:

Vadim kínaiul tanul;

Szergej nem tanul kínaiul;

Mihail nem tanul arabul.

Ha az első állítás igaz, akkor a második is igaz, hiszen a fiatalok különböző nyelveket tanulnak. Ez ellentmond a probléma kijelentésének, így az első állítás hamis.

Ha a második állítás igaz, akkor az elsőnek és a harmadiknak hamisnak kell lennie. Kiderült, hogy senki sem tanul kínaiul. Ez ellentmond a feltételnek, így a második állítás is hamis.

Válasz: Szergej kínaiul tanul, Mihail japánul, Vadim arabul tanul.

5. példa. Oroszország, az Egyesült Államok és Kína külügyminisztere zárt ajtók mögött tárgyalta az egyes országok által benyújtott, a teljes leszerelésről szóló megállapodástervezetet. Majd az újságírói kérdésre: „Kinek a projektjét fogadták el pontosan?” a miniszterek a következő válaszokat adták:

Oroszország - „A projekt nem a miénk, a projekt nem az USA”;
USA - „Ez nem orosz projekt, hanem kínai projekt”;
Kína – „A projekt nem a miénk, hanem Oroszország projektje.”

Egyikük (a legszókimondóbb) mindkétszer igazat mondott; a második (legtitkosabb) mindkétszer hazudott, a harmadik (óvatos) egyszer igazat mondott, máskor pedig hazugságot.

Határozza meg, mely országokat képviselik az őszinte, titkolózó és óvatos miniszterek.

Megoldás. A rögzítés megkönnyítése érdekében számozzuk meg a diplomaták nyilatkozatait:

Oroszország - „A projekt nem a miénk” (1), „A projekt nem az USA” (2);
USA – „Not Russia Project” (3), „China Project” (4);
Kína - „A projekt nem a miénk” (5), „Oroszország projektje” (6).

Nézzük meg, melyik miniszter a legszókimondóbb.

Ha orosz miniszterről van szó, akkor az (1) és (2) érvényességéből az következik, hogy a kínai projekt nyert. De akkor az amerikai külügyminiszter mindkét állítása is igaz, ami a feltétel szerint nem lehet így.

Ha a legszókimondóbb az amerikai miniszter, akkor megint azt kapjuk, hogy a kínai projekt nyert, vagyis az orosz miniszter mindkét állítása igaz is, ami nem lehet így.

Kiderült, hogy a kínai miniszter volt a legszókimondóbb. Abból ugyanis, hogy az (5) és (6) igaz, az következik, hogy az orosz projekt nyert. Aztán kiderül, hogy az orosz miniszter két állítása közül az első hamis, a második pedig igaz. Az Egyesült Államok külügyminiszterének mindkét állítása helytelen.

Válasz: A kínai miniszter szókimondóbb, az orosz miniszter óvatosabb, az amerikai miniszter pedig titkolózóbb volt.

6. § Logikai funkció.

A logika algebrában az egyszerű állításokat logikai változók helyettesítik, ellenkező esetben a változók értéke csak 0 és 1 lehet. A logikai konnektívumokat a megfelelő matematikai szimbólumokkal helyettesítjük. Ebben az esetben egy összetett állítás logikai függvényté alakul.

Logikai függvény A logikai változók halmazából (a, b, c, ...) származó F-et olyan függvénynek nevezzük, amely csak két értéket vehet fel: 0 és 1.

F(a, b) = a  b - logikai szorzás (kötőszó).

F (a, b) = a v b - logikai összeadás (disjunkció).

F (a) =  a - negáció (inverzió).

F(a, b) = a  b - implikáció.

F(a, b) = a  b - egyenértékűség.

A logikai függvények kiszámíthatók igazságtáblázatok segítségével.

A logikai függvény igazságtáblázata a logikai változók számától függ, és 2n változóhalmazt tartalmaz.

1. példa: Egy logikai függvény értékének kiszámítása

F (a , b ) =  (a v b )  (a   b )

Válasszunk köztes logikai függvényeket, és töltsük ki az igazságtáblázatot a megfelelő logikai változóhalmazokhoz.

a v b

 (a v b)

 b

a  b

F(a, b)

A táblázat azt mutatja, hogy a logikai változók bármely halmaza esetén az F (a, b) függvény azonosan egyenlő nullával.

2. példa: Egy logikai függvény értékének kiszámítása a változók adott értékeihez.

F (a, b, c) = a v b  (a  c   b).

Kiszámítja: F (1, 0, 1).

Megoldás:

F (1, 0, 1) = 1 v 0  (1  1   0)

A zárójelben lévő kifejezés értékét nem kell kiszámolni, mert akkor a 0 konjunkcióját és a zárójelben lévő kifejezéseket hajtjuk végre. Akkor nálunk van:

F (1, 0, 1) = 1 v 0 = 1.

Válasz: F (1, 0, 1) = 1.

A jelölésben eltérő logikai függvények logikai egyenlőségének bizonyítására is használják az igazságtáblázatok felépítésének módszerét. Ezenkívül, ha a függvények értékei egybeesnek a logikai változók minden azonos halmazán, akkor ekvivalensnek nevezzük őket.

A két logikai függvényt ún egyenértékű, ha a függvényértékek a logikai változók minden azonos halmazán egybeesnek.

3. példa Két logikai függvény egyenlőségének bizonyítása.

Bizonyítsuk be, hogy a függvények F 1 ( a , b ) =  a v b És F 2 ( a , b ) = a  b egyenértékűek.

 a

 a v b

a  b

A táblázatból megállapítjuk, hogy a logikai változók minden azonos halmazán a függvények értéke egybeesik, ezért ekvivalensek.

A logika törvényeinek alkalmazása lehetővé teszi a logikai kifejezésekben a változók számának csökkentését és a logikai függvények egyszerűsítését.

A logika törvényei is érvényesek logikai függvények felépítéséhez igazságtáblázatok segítségével. Ebben az esetben az embert irányítani kell a következő szabályt:

Az igazságtábla minden egységértékkel rendelkező sorához készítsünk egy mintermet (változók konjunkcióját), amelyben a változónak egyszer kell előfordulnia (negáció nélkül vagy tagadással). Ha az igazságtáblázatban a változók nulla értéket tartalmaznak egy sorban, akkor a mintermet tagadással, az egy értékű változók pedig a mintermet negáció nélkül írják be.

Kombinálja az összes mintermet a diszjunkciós művelet segítségével.

Ha lehetséges, egyszerűsítse a kapott logikai képletet.

4. példa Logikai függvény felépítése adott igazságtáblázatból.

F(a, b, c)

Jelöljük ki azokat a sorokat, amelyekben a függvény 1-gyel egyenlő, és készítsünk hozzájuk mintermeket:

1. sor:  a  b  c ;

2. sor:  a  b  c .

Kombináljuk a mentális kifejezéseket: F ( a , b , c ) =  a  b  c   a  b  c .

Egyszerűsítsük a logikai függvényt: F ( a , b , c ) =  a  b  c   a  b  c = {3} =  a  b  (  c  c ) = {6} =  a  b  1= {7} =  a  b = {4} =  ( a  b )

Tehát van egy logikai függvényünk F ( a , b , c ) =  ( a  b ).

7. § A számítógépek logikai alapjai. Alapvető logikai elemek.

Ebből két következtetés következik:

Ugyanazok a számítógépes eszközök használhatók mind a kettes számrendszerben bemutatott numerikus információk, mind a logikai változók feldolgozására és tárolására;

Az adatok és parancsok különböző szerkezetű és hosszúságú bináris sorozatokként jelennek meg. A bináris információ kódolásának különféle fizikai módjai vannak. Számítógépes elektronikai eszközökben A binárisokat leggyakrabban magasabb feszültségszinten kódolják, mint a bináris nullákat.

Logikai elem A számítógép egy elektronikus logikai áramkör része, amely elemi logikai funkciót valósít meg.

A számítógépek alapvető logikai elemei a logikai funkciók megvalósítására az elektronikus áramkörök AND, OR, NOT, NAND, NOR (más néven szelepek).

Ezekkel az áramkörökkel bármilyen logikai függvényt megvalósíthat, amely leírja a számítógépes eszközök működését. A szelepek általában egy-nyolc bemenettel és egy vagy két kimenettel rendelkeznek.

A két „1” és „0” logikai állapot megjelenítéséhez a kapukban a megfelelő bemeneti és kimeneti jelek két beállított feszültségszinttel rendelkeznek. Például +5 volt és 0 volt. A magas szint általában az „igaz” („1”), az alacsony szint pedig a „hamis” („0”) értéknek felel meg.

És (kötőszó)

Egy ÉS áramkör két vagy több logikai érték konjunkcióját valósítja meg.

x. y

Akkor és csak akkor lesz egy az ÉS áramkör kimenetén, ha minden bemeneten van. Ha legalább egy bemenet nulla, a kimenet is nulla lesz.

Az áramkör z kimenete és az x és y bemenetek közötti kapcsolatot a következő összefüggés írja le: z = x . y

A konjunkció működését blokkdiagramokban a jel jelzi "&" (olvasd úgy "és"), amely az angol szó rövidítése és.

VAGY (disjunktor)

Egy VAGY áramkör két vagy több logikai érték diszjunkcióját valósítja meg.

x  y

Ha a VAGY áramkör legalább egy bemenete egy, a kimenete is egy lesz.

Kommunikáció a kimenetek között z ez az áramkör és a bemenetek xÉs yösszefüggés írja le: z = x v y

Jel "1" diagramban - a diszjunkció elavult megjelölésétől mint ">=1" (azaz a diszjunkció értéke eggyel egyenlő, ha az operandusok értékeinek összege nagyobb vagy egyenlő, mint 1).

NEM (inverter)
x

y

 (x . y)

0

0

1

0

1

1

1

0

1

1

1

0

Rendszer ÉS NEM elemből áll ÉS ÉS.

Kommunikáció a kimenetek között zés bejáratok xÉs y a diagramokat a következőképpen írjuk: z = (x . y), ahol x . y tetszik "x és y inverziója".

NOR (Pierce elem)

Rendszer VAGY NEM elemből áll VAGYés inverter és negálja az áramkör eredményét VAGY. c)
F = a (  b   c)  (a  e d) (  a  időszámításunk előtt)
F = a b c  a b c  a b  c d
F=a   a · (b  c)  (  a  d  g) · (b  d) · (c   d  g h)

8. § A számítógép logikai elemei. Kioldó és összeadó.

Kioldó egy elektronikus áramkör, amelyet széles körben használnak a számítógépes regiszterekben a bináris kód egy számjegyének megbízható tárolására. A triggernek két stabil állapota van, amelyek közül az egyik egy bináris, a másik egy bináris nullának felel meg.

Term ravaszt az angol szóból származik ravaszt- retesz, kioldó. Ennek a sémának az angol nyelvű jelölésére a kifejezést gyakrabban használják strand papucs, ami lefordítva azt jelenti: „taps”. Az elektronikus áramkörnek ez a névadó neve arra utal, hogy szinte azonnal át tud váltani ("átkapcsolni") egyik elektromos állapotból a másikba és fordítva.

A triggerek legelterjedtebb típusa az úgynevezett RS trigger (az angolból S, illetve R készlet- beépítés és Visszaállítás- Visszaállítás).

S0

1

1

0

1

0

0

1

1

1

bittárolás
S Q
R  K

Elemezzük a flip-flop R és S bemeneteinek lehetséges értékkombinációit az áramköre és a NOR-NOT áramkör igazságtáblázata segítségével

Ha a trigger bemenetekre S=“1”, R=“0” kerül, akkor (állapottól függetlenül) „0” jelenik meg a felső kapu Q kimenetén. Ezt követően az alsó szelep bemenetei R=“0”, Q=0” és a kimenet  K"1" lesz.
Ugyanígy, ha „0”-t alkalmazunk az S bemenetre és „1”-et az R bemenetre, akkor a kimenet  K A „0” jelenik meg, a Q-n pedig az „1”.
Ha az R és S bemenetekre logikai „1” kerül, akkor a Q és állapot  K nem változik.
A logikai „0” R és S bemenetre történő alkalmazása kétértelmű eredményekhez vezethet, ezért a bemeneti jelek ilyen kombinációja tilos.

Mivel egy trigger csak egy bit bináris kódot tud megjegyezni, egy bájt emlékezéséhez 8 flip-flop szükséges, egy kilobájt emlékezéséhez pedig 8 x 2 10 = 8192 flip-flop szükséges. A modern memóriachipek több millió triggert tartalmaznak.

Annak érdekében, hogy a számítógép működését a lehető legnagyobb mértékben leegyszerűsítsük, a matematikai műveletek teljes választékát bináris számok hozzáadására redukáljuk.

Emlékezzünk vissza, hogy bináris számok összeadásakor egy adott számjegyben összeg keletkezik, és azt is át lehet vinni a legjelentősebb számjegyre.

Alkatrészek

Átruházás

Összeg

A

B

P

S

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

Ebből a táblázatból látható, hogy az átvitel az „ÉS” logikai elem segítségével valósul meg.

Az összeget tekintve a legalkalmasabb logikai kapu az "OR" kapu. A negyedik számpár összeadásakor azonban az eredménynek 0-nak kell lennie, nem 1-nek. A kívánt eredmény elérése érdekében átviteli jelet adhatunk a „NOT” kapura, majd annak kimenetéről és a „VAGY” kapu, küldjön jelet a „NEM” kapunak. ÉS”. Az „AND” elem kimenetén megkapjuk a szükséges jelet.

A (0,0,1,1) P (0,0,0,1)

B (0,1,0,1)

0,0,0,1 1,1,1,0 S (0,1,1,0)

0,1,1,1

Ezt a sémát az ún fél összeadó, mert egyjegyű bináris számok összegzését valósítja meg anélkül, hogy figyelembe venné a legkisebb jelentőségű számjegytől való átvitelt.

Vipera egy elektronikus logikai áramkör, amely bináris számok összegzését végzi

Az összeadó elsősorban a számítógép aritmetikai-logikai eszközének központi egységeként szolgál, de a gép más eszközeiben is alkalmazásra talál.

a i

b i

p i

p i-1

c i

Az A és B számok összeadásakor én A számjegynek három számjegynek kell lennie:

1. számjegy a én első időszak;

2. számjegy b én második időszak;

3. átadás p i–1 junior rangtól.

Az összeadás eredményeként két számjegyet kapunk: c számjegyet énösszegért; átadás p én ebből a kategóriából a senior.

És így, Az egybites bináris összeadó három bemenettel és két kimenettel rendelkező eszköz, melynek működése a következő igazságtáblázattal írható le:

Bemenetek

Kilépések

Első időszak

Második időszak

Átruházás

Összeg

Átruházás

a i

b i

p i-1

c i

p i

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Ha két vagy több bites bináris szavakat kell hozzáadnia, használhatja az ilyen összeadók soros kapcsolatát, és két szomszédos összeadó esetén az egyik összeadó átviteli kimenete a másik bemenete.

Többbites bináris összeadó, többjegyű bináris számok hozzáadására tervezték, egybites összeadók kombinációja.

Például egy séma két háromjegyű bináris szám A = (a 2 a 1 a 0) és B = (b 2 b 1 b 0) C = (c 3 c 2 c 1 c 0) összegének kiszámítására, ahol c 0 az összeg legkisebb számjegye, 3 pedig az összeg legjelentősebb számjegye, így nézhet ki:

a 0 a 1 a 2

b 0 b 1 b 2

0 a 3-ból

s 0 s 1 s 2

Ebből arra következtethetünk, hogy a logikai elemek azok az építőelemek, amelyekből logikai áramkörök felépítésével minden modern számítógép „épülete” felépül.

Kérdések az önkontrollhoz:

Mit tanul a logika, a matematikai logika és a logikai algebra?
Határozza meg a következő fogalmakat: állítás, állítás, érvelés, következtetés, logikai kifejezés!
Alapvető logikai konnektívumok, elemi és összetett állítások.
Sorolja fel az alapvető logikai műveleteket és azok megírását!
Határozzon meg egy logikai képletet.
Magyarázza meg a következő fogalmak jelentését: megvalósítható logikai formula, tautológia, ellentmondás, a képlet ekvivalens átalakítása!
Írjon le képleteket az implikáció és az ekvivalencia más alapvető logikai műveletek kombinációjával való helyettesítésére.
A logikai képlet igazságtáblázatának fogalma. Elemi képletek igazságtáblázatai.
Mi a képlet egyszerűsítése?
A logikai algebra alaptörvényei.
Sorolja fel és jellemezze a logikai problémák megoldásának főbb módjait!
Adja meg a logikai függvény definícióját!
Az ekvivalens logikai függvények fogalma.
A szabály a logikai függvények igazságtáblázatok segítségével történő felépítésére.
A számítógép logikai elemének meghatározása. Alapvető logikai elemek.
Kioldó és összeadó. Megfelelő igazságtáblázatok és logikai áramkörök.

Modern trendek az új szerkezeti anyagok fejlesztésében.

A bányaüzemek rögzítésének javítása terén további előrelépés lehetséges új, rendkívül hatékony rögzítőanyagok kifejlesztésével és felhasználásával. A földalatti körülmények közötti támogatási működés jellemzői:

· megnövekedett páratartalom és a környezet agresszivitása;

· váltakozó feszültségek az elemekben;

· a kőzetnyomás dinamikus megnyilvánulásai és a szeizmikus-robbanásveszélyes terhelések, valamint a robbantott kőzetek hatása egyrészt korlátozza az új anyagok alkalmazási körét a földalatti építésben;

· másrészt a hőmérséklet állandósága a bányában és a bányában, valamint az esetek túlnyomó többségében a viszonylag korlátozott üzemidő (felszíni szerkezeteknél 60-100 év helyett 5-15 év) kiterjeszti a hatókört. alkalmazásukról.

Következésképpen az új anyagok tartószerkezetekben való felhasználásának lehetőségének kérdéskörének bővítéséhez szükséges ezek fizikai és kémiai tulajdonságainak laboratóriumi körülmények közötti vizsgálata, figyelembe véve a föld alatti munkavégzés sajátosságait. Ugyanakkor ezek a tulajdonságok szükségessé teszik a tartószerkezetekhez új anyagok keresését.

1. Mi a logika algebrája?

A logikai algebra megalkotója a 19. században élt angol matematikus, George Boole, akiről a logikai algebrát is ún. Boole algebra .

Így például a „6 - páros szám” logikus állításnak kell tekinteni, mivel igaz.

A logikai algebra minden állítást csak abból a szempontból vesz figyelembe, hogy igaz vagy hamis.

A hétköznapi beszédben használt szavak és kifejezések „nem”, „és”, „vagy”, „ha..., akkor”, „akkor és csak akkor”és néhány másik lehetővé teszi új logikai utasítások összeállítását a már megadott utasításokból. Az ilyen szavakat és kifejezéseket hívják logikai összeköttetések .

Más utasításokból logikai konnektívumokkal képzett utasításokat hívjuk összetett . Olyan állítások, amelyek nem összetettek, pl. szalagok nélkül, ún alapvető.

Az összetett állítások igazsága vagy hamissága az elemi állítások igazságától vagy hamisságától függ.

Nak nek formálisan logikai utasításokra hivatkoznak, változóneveket kapnak. Engedd át A kijelölt alapvető mondván „ Timur nyáron a tengerhez megy”, és azon keresztül BAN BEN - nyilatkozat " Timur nyáron a hegyekbe megy" Akkor összetett mondván „ Timur nyáron a tengert és a hegyeket is ellátogatja” formálisan így írható A és B . Itt " És ” - logikai összekötő, A, B - logikai változók , amely csak két értéket vehet fel - " igaz "vagy" fekszik " A számítógépben az „igaz” és „hamis” értékeket egyszerűen „1”-nek és „0-nak” jelölik.

Minden egyes logikai összekötő a Boole-algebrában mint logikai működés logikai utasítások felett, és saját neve és megnevezése van:

1. Művelet" szóval kifejezve Nem ”, a logika algebrájában hívják tagadás és általában a jel jelzi ù vagy egy sor egy állítás felett. Egy állítás igaz, ha A hamis, és hamis, ha A igaz. Például, " A Hold a Föld műholdja"(A); " A Hold nem a Föld műholdja” ().

2. Művelet, amelyet a kopula fejez ki És ”, hívták kötőszó vagy logikai szorzás és a „szóval jelöljük és ”, vagy egy pont „ ”, vagy az Ù és & jelek (és jelek).

Szabályművelet végrehajtása: A B állítás igaz o akkor és csak akkor, ha mind az A, mind a B állítás igazak, különben az hamis. Például az állítás

„A 10 osztható 2-vel, az 5 pedig nagyobb, mint 3” igaz és állítások

„a 10 osztható 2-vel, és az 5 nem több, mint 3”, hamis.

3. Működés, amelyet a kapcsoló " vagy " nak, nek hívják diszjunkció vagy logikus kiegészítés és a logikai képletekben a „szóval jelöljük VAGY ”, vagy aláírja U , Ú vagy plusz "+".

Szabálya művelet elvégzése: Nyilatkozat A UBAN BEN akkor és csak akkor hamis, ha mind az A, mind a B állítás hamis, különben az lesz igaz.

Például az állítás

"10 nem osztható egyenletesen 2-vel, vagy 5 nem nagyobb 3-nál" - hamis,

és mindhárom állítás: „10 osztható 2-vel vagy 5-tel nagyobb, mint 3”, „10 osztható 2-vel vagy 5-tel, nem nagyobb 3-nál” vagy „A 10 nem osztható 2-vel, vagy az 5 nagyobb, mint 3”- igaz lesz.

4. Művelet, a következő formájú konnektívumokkal kifejezve ha akkor...”, “ebből következik..."vagy" ...vonz...”, hívták következmény és a képletekben à jellel jelöljük.

Művelet végrehajtási szabály: A à B állítás hamis O akkor és csak akkor, ha A igazés B - hamis.

Hogyan köt össze egy implikáció két elemi állítást? Mutassuk meg ezt az állítások példáján: " ez a négyszög négyzet” (A ) és " adott négyszög köré kör rajzolható” (BAN BEN ). Vegyünk egy összetett állítást A à BAN BEN , értve: " Ha egy adott négyszög négyzet, akkor körberajzolható”.

Három lehetőség van, amikor az A AB utasítás lesz igaz:

1. A - igazés B- igaz, azaz ez a négyszög négyzet, és kör írható le körülötte;

2. A- hamisés B- igaz, vagyis ez a négyszög nem négyzet, hanem kör írható le körülötte (persze ez nem minden négyszögre igaz);

3. A - hamisés B- hamis, vagyis ez a négyszög nem négyzet, és kör nem rajzolható köré.

Csak egy lehetőség hamis: A- igazÉs BAN BEN - hamis, vagyis ez a négyszög négyzet, de körülötte nem lehet kört leírni.

A hétköznapi beszédben az összekötő " ha akkor” az állítások közötti ok-okozati összefüggést írja le. De a logikai műveletekben az állítások jelentését nem veszik figyelembe, hanem csak azok igazságát vagy hamisságát.

5. Összekötőkkel kifejezett működés akkor és csak akkor”, "szükséges és elégséges”, “... egyenértékű...", nak, nek hívják egyenértékű vagy kettős implikáció és a tábla jelzi ~ (tilde) ill º ( identitás ).

Szabály: Nyilatkozat A ~ BAN BEN akkor és csak akkor igaz, ha az értékek A És BAN BEN egyeznek meg.

A logikai műveletek sorrendje logikai kifejezésekben ez adott a műveletek prioritása és zárójelek.

BAN BEN zárójel nélküli kifejezések először a műveletet hajtják végre tagadás (“ Nem "), akkor kötőszó (“ És "), Akkor - diszjunkció (“vagy "és végül - először következmény, és akkor egyenértékűség.

2. Mi a logikai képlet?

A logikai változók és a logikai műveletek szimbólumai segítségével bármilyen utasítás formalizálható, azaz helyettesíthető logikai képlet.

Példaként tekintsük a „ ha almát vagy sárgabarackot veszek, készíthetek gyümölcstortát" Ezt az állítást képletként formalizáljuk ( A Ú B ) à C . Ahogy a képlet elemzése mutatja

(A Ú B) à C, a változóértékek bizonyos kombinációihoz A, B És C értelmet kap" igaz ”, és néhány más kombináció esetén a „ fekszik " Az ilyen képleteket ún megvalósítható .

Néhány képlet a " igaz ” a bennük szereplő változók bármely igazságértékére. Például ez lenne a képlet A Ú , amely megfelel a „ Ez a háromszög derékszögű vagy ferde" Ez a képlet igaz akkor is, ha a háromszög derékszögű, és amikor a háromszög nem derékszögű. Az ilyen képleteket ún ugyanúgy igaz képletek ill tautológiák .

A tautológiákkal formalizált állításokat logikailag igaz állításoknak nevezzük.

Egy másik példaként tekintsük a képletet A , amely megfelel például a „ Katya a legmagasabb lány az osztályban, és vannak Kátyánál magasabb lányok az osztályban" Nyilvánvaló, hogy ez a képlet mindig hamis , hiszen akár A , vagy szükségszerűen hamis. Az ilyen képleteket ún egyformán hamis képletek ill ellentmondások . Az ellentmondásokkal formalizált állításokat nevezzük logikailag hamis állítások.

Ha két képlet A És B ha a bennük szereplő változók azonos értékhalmazai ugyanazokat az értékeket veszik fel, akkor ezeket ún. egyenértékű .

Két képlet egyenértékűségét a logikai algebrában a " szimbólum jelöli = ” vagy az „ О ” szimbólumot. A képlet lecserélése egy másikra egyenértékű, hívott ekvivalens transzformáció ebből a képletből.

3.Mi a kapcsolat a logikai algebra és a bináris kódolás között?

A logikai algebra matematikai berendezése alkalmas az adatok feldolgozására egy számítógépen, ahol használják kettes számrendszer, amely az 1 és 0 számokat használja, és logikai változó értékek kettő is: „1” és „0”.

Ezért ugyanazok a számítógépes eszközök használhatók mind a bináris számrendszerben bemutatott numerikus információk, mind a logikai változók értékeinek feldolgozására és tárolására.

Adatok és parancsok a számítógépben különböző struktúrájú és hosszúságú 0 és 1 bináris sorozatokként vannak ábrázolva (szemben a 0 és 1 logikai értékekkel).

A számítógépes elektronikában bináris információ kódolásakor Mértékegység kódolt magasabb feszültségszint nullánál (vagy fordítva).

4. Mi az a számítógépes logikai elem?

A számítógépek logikai elemei az olyan elektronikus áramkörök, mint az ÉS, VAGY, NEM, NAND, NOR és mások (más néven szelepek), valamint egy indítóeszköz.

Ezekkel a logikai áramkörökkel bármilyen logikai függvény megvalósítható, amely leírja a számítógépes eszközök működését. A szelepeknek általában kettő-nyolc bemenetük és egy vagy két kimenetük van.

A két „1” és „0” logikai állapot ábrázolásához a kapukban a megfelelő bemeneti és kimeneti elektromos jelek két beállított feszültségszinttel rendelkeznek. Például +5 volt és 0 volt. A magas szint általában az „igaz” („1”), az alacsony szint pedig a „hamis” („0”) értéknek felel meg.

Minden logikai elemnek megvan a saját szimbóluma az áramkörben, amely meghatározza a logikai funkcióját, de nem jelzi, hogy milyen elektronikus áramkör van benne megvalósítva. Ez megkönnyíti az összetett logikai áramkörök írását és megértését.

A logikai elemek működését a segítségével írjuk le igazságtáblázatok.

3. sz. előadás.

A számítógép LOGIKAI alapjai.

Mi a logika algebrája?

Mi az a logikai képlet?

Mi a kapcsolat a logikai algebra és a bináris kódolás között?

Milyen formában íródnak az adatok és a parancsok a számítógép memóriájába és a processzor regisztereibe?

Mi az a számítógépes logikai elem?

Mik azok az ÉS, VAGY, NEM, NAND, NOR áramkörök?

Mi az a trigger?

Mi az az összeadó?

Milyen alaptörvények érvényesülnek a logika algebrájában?

Hogyan készítsünk igazságtáblázatot?

Hogyan lehet leegyszerűsíteni egy logikai képletet?

Mi az a kapcsoló áramkör?

Hogyan lehet megoldani a logikai feladatokat?

Mi a logika algebrája?

Mi az a logikai állítás?

Tehát például a következő mondat: 6 - páros szám"állításnak kell tekinteni, mert igaz. Mondat" Róma Franciaország fővárosa" is állítás, mert hamis.

Olyan mondatok, mint " a városban A több mint egymillió lakos", "kék szeme van" nem állítások, hiszen igazságuk vagy hamisságuk megállapításához további információra van szükség: melyik városról vagy személyről van szó. Az ilyen mondatokat ún. kifejező formák.

A logikai algebra minden állítást csak egy nézőpontból vesz figyelembe – legyen az igaz vagy hamis. vegye észre, az Gyakran nehéz megállapítani egy állítás igazságát. Tehát például a " Az Indiai-óceán felszíne 75 millió négyzetméter. km" egyik helyzetben hamisnak, másikban igaznak tekinthető. Hamis - mert a megadott érték pontatlan és egyáltalán nem állandó. Igaz - ha a gyakorlatban elfogadható közelítésnek tekintjük.

A hétköznapi beszédben használt szavak és kifejezések „nem”, „és”, „vagy”, „ha... akkor”, „akkor és csak akkor” mások pedig lehetővé teszik, hogy a már megadott állításokból új állításokat hozzon létre. Az ilyen szavakat és kifejezéseket hívják logikai összeköttetések.

Más utasításokból logikai konnektívumokkal képzett utasításokat hívjuk összetett. A nem összetett állításokat ún alapvető.

Az így kapott összetett állítások igazsága vagy hamissága az elemi állítások igazságától vagy hamisságától függ.

Minden egyes logikai összeköttetés logikai utasításokon végzett műveletnek minősül, és saját neve és jelölése van:

NEM Egy szóval kifejezett művelet "Nem", hívott tagadás és az állítás (vagy jel) feletti vonal jelzi. Egy állítás igaz, ha A hamis, és hamis, ha A igaz. Példa. " A Hold a Föld műholdja" (A); " A Hold nem a Föld műholdja" ().

ÉS "És", hívott kötőszó (lat. conjunctio - kapcsolat) vagy logikai szorzás, és pont jelzi " . " (táblákkal is jelezhető, ill & ). Nyilatkozat A. B akkor és csak akkor igaz, ha mindkét állítás AÉs BAN BEN igazak. Például az állítás "10 osztható 2-vel és 5 nagyobb, mint 3" igaz és állítások "10 nem osztható 2-vel és 5 nem több 3-mal", "10 nem osztható 2-vel és 5 nem több, mint 3", "10 nem osztható 2-vel és 5 nem több 3-nál"- hamisak.

VAGY Kopula által kifejezett művelet "vagy"(a szó nem kizárólagos értelmében) nevezzük diszjunkció (lat. disjunctio - osztás) vagy logikai összeadás, és a jel jelzi v(vagy plusz). Nyilatkozat A v B akkor és csak akkor hamis, ha mind A, mind B állítás hamis. Például az állítás "10 nem osztható 2-vel, vagy 5 nem nagyobb 3-nál" hamis és állítások "10 osztható 2-vel vagy 5-tel nagyobb, mint 3", "10 osztható 2-vel vagy 5-tel, nem nagyobb, mint 3", "10 nem osztható 2-vel vagy 5-tel nagyobb, mint 3"- igaz.

HA AKKOR A konnektívumokkal kifejezett működés „ha... akkor”, „a...-tól következik”, „... magával vonja...”, hívott következmény (lat. implico- szorosan összefüggenek), és a jel jelzi. Egy állítás akkor és csak akkor hamis A igaz, de BAN BEN hamis.

Hogyan köt össze implikáció két elemi állítást? Mutassuk meg ezt egy példával az állításokra: "ez a négyszög egy négyzet" (A) És "Egy adott négyszög köré kör írható" (BAN BEN). Tekintsünk egy összetett állítást, amely így értendő "Ha egy adott négyszög négyzet, akkor kört lehet körberajzolni." Eszik három lehetőség, ha igaz az állítás:

A igaz és BAN BEN igaz, vagyis ez a négyszög négyzet, és körbeírható kör;
A hamis és BAN BEN igaz, vagyis ez a négyszög nem négyzet, hanem kör írható le körülötte (persze ez nem minden négyszögre igaz);
A hamis és B false, vagyis ez a négyszög nem négyzet, és kör nem rajzolható köré.

Csak egy lehetőség hamis, ha A igaz és B hamis, vagyis ez a négyszög négyzet, de körülötte nem lehet kört leírni.

EGYENSÚLYOS A működés konnektorokkal kifejezve" akkor és csak akkor", "szükséges és elégséges", "... egyenértékű...", hívták egyenértékű vagy kettős vonatkozású és a vagy jel jelzi ~. Egy állítás akkor és csak akkor igaz, ha a jelentések AÉs BAN BEN egyeznek meg. Például nyilatkozatok "A 24 akkor és csak akkor osztható 6-tal, ha a 24 osztható 3-mal", "23 akkor és csak akkor osztható 6-tal, ha a 23 osztható 3-mal." igazak és állítások "A 24 akkor és csak akkor osztható 6-tal, ha a 24 osztható 5-tel", "21 akkor és csak akkor osztható 6-tal, ha a 21 osztható 3-mal." hamis.

Nyilatkozatok AÉs BAN BEN, Az összetett állítás kialakítása tartalmilag teljesen független lehet, például: "három több mint kettő" (A), "Pingvinek élnek az Antarktiszon" (BAN BEN). Ezen állítások tagadásai az állítások "három nem több kettőnél" (), "A pingvinek nem élnek az Antarktiszon"(). Kijelentésekből alakult ki AÉs BAN BENösszetett állítások A Bés igaz, és állítások AÉs B- hamisak.

Szóval nálunk öt logikai műveletet veszünk figyelembe: tagadás, konjunkció, diszjunkció, implikáció és ekvivalencia.

Így a tagadás, a diszjunkció és a konjunkció műveletei elegendőek a logikai állítások leírásához és feldolgozásához.

I. séma

Egy ÉS áramkör két vagy több logikai érték konjunkcióját valósítja meg. ÉSábrán látható két bemenettel. 5.1.

Áramköri igazságtáblázat ÉS

x	y	x. y

VAGY áramkör

VAGY áramkör megvalósítja diszjunkció két vagy több logikai érték.

Amikor az áramkör legalább egy bemenete VAGY egy lesz, a kimenete is egy lesz.

Szimbólum az áramkör blokkvázlatain VAGYábrán látható két bemenettel. 5.2.

Kommunikáció a kimenetek között z ez az áramkör és a bemenetek xÉs yösszefüggés írja le:

z = x v y(olvasd úgy "x vagy y").

Áramköri igazságtáblázat VAGY

x	y	x v y

SÉMA NEM

Rendszer NEM(inverteres) eszközök tagadó művelet.

Kommunikáció a bemenetek között x ez az áramkör és a kimenet zúgy írható fel

z = , x ahol úgy olvasható "nem x" vagy "inverz x".

Ha az áramkör bemenetén 0, majd a kijáratnál 1. Amikor a bejáratnál 1, a kijáratnál 0. Szimbólum az inverter blokkvázlatain - az 5.3. ábrán

Áramköri igazságtáblázat NEM

x

Séma ÉS-NEM

Rendszer ÉS NEM elemből áll ÉS ÉS.

Kommunikáció a kimenetek között zés bejáratok xÉs y Az áramkörök a következőképpen vannak felírva: , ahol így olvasható "x és y inverziója".

Szimbólum az áramkör blokkvázlatain ÉS NEM két bemenettel az 5.4. ábra mutatja.

NAND áramköri igazságtáblázat

x	y

VAGY NEM áramkör

Rendszer VAGY NEM elemből áll VAGYés inverter és negálja az áramkör eredményét VAGY.

Kommunikáció a kimenetek között zés bejáratok xÉs y Az áramkörök a következőképpen írhatók: , ahol , így olvasható "x vagy y inverze".

Szimbólum az áramkör blokkvázlatain VAGY NEMábrán látható két bemenettel. 5.5.

A NOR áramkör igazságtáblázata

Term ravaszt az angol szóból származik ravaszt- retesz, kioldó.

Ennek a sémának az angol nyelvű jelölésére a kifejezést gyakrabban használják strand papucs, ami lefordítva azt jelenti: „taps”. Az elektronikus áramkörnek ez a névadó neve arra utal, hogy szinte azonnal át tud váltani ("átkapcsolni") egyik elektromos állapotból a másikba és fordítva.

A trigger leggyakoribb típusa az ún RS trigger(S, illetve R angolból készlet- beépítés és Visszaállítás- Visszaállítás). A trigger szimbólum az ábrán látható. 5.6.

Rizs. 5.6

Két szimmetrikus S és R bemenete és két szimmetrikus Q és kimenete van, ahol a Q kimeneti jel a jel logikai negációja.

A két S és R bemenet mindegyike képes bemenő jeleket fogadni rövid távú impulzusok formájában ().

ábrán. Az 5.7. ábra egy flip-flop megvalósítását mutatja NOR kapukkal és a megfelelő igazságtáblázattal.

Rizs. 5.7

S	R	K
		tiltott


		bittárolás

Elemezzük a flip-flop R és S bemenetei értékeinek lehetséges kombinációit az áramköre és a NOR-NOT áramkör igazságtáblázata segítségével (5.5. táblázat).

Mivel egy trigger csak egy bit bináris kódot tud megjegyezni, egy bájt emlékezéséhez 8 flip-flop szükséges, egy kilobájt emlékezéséhez pedig 8 x 2 10 = 8192 flip-flop szükséges. A modern memóriachipek több millió triggert tartalmaznak.

Mi az az összeadó?

Az összeadó elsősorban a számítógép aritmetikai-logikai eszközének központi egységeként szolgál, de a gép más eszközeiben is alkalmazásra talál.

Többbites bináris összeadó, többjegyű bináris számok hozzáadására tervezték, egy számjegyű összeadók kombinációja, amivel kezdjük. Egy számjegyű összeadó szimbóluma az ábrán. 5.8.

Rizs. 5.8

Az A és B számok összeadásakor én A számjegynek három számjegynek kell lennie:

1. számjegy a én első időszak;

2. számjegy b én második időszak;

3. átadás p i–1 junior rangtól.

Az összeadás eredményeként két számot kapunk:

1. számjegy c énösszegért;

2. átadás p én ebből a kategóriából a senior.

És így, Az egybites bináris összeadó három bemenettel és két kimenettel rendelkező eszköz, melynek működése a következő igazságtáblázattal írható le:

Bemenetek	Kilépések
Első időszak	Második időszak	Átruházás	Összeg	Átruházás

Ha két vagy több bites bináris szavakat kell hozzáadnia, használhatja az ilyen összeadók soros kapcsolatát, és két szomszédos összeadó esetén az egyik összeadó átviteli kimenete a másik bemenete.

Például egy séma két bináris háromjegyű szám A = (a 2 a 1 a 0) és B = (b 2 b 1 b 0) C = (c 3 c 2 c 1 c 0) összegének kiszámítására. hasonló:

Példák.

1. Készítsünk igazságtáblázatot a képlethez, amely két x és y változót tartalmaz. A táblázat első két oszlopában felírjuk ezeknek a változóknak négy lehetséges értékpárját, a következő oszlopokban - a közbenső képletek értékeit és az utolsó oszlopban - a képlet értékét. Ennek eredményeként a következő táblázatot kapjuk:

Változók	Köztes logikai képletek	Képlet

A táblázatból egyértelműen kiderül az x és y változók összes értékkészletére a képlet 1 értéket vesz fel, azaz van azonos az igaz.

2. A képlet igazságtáblázata: