Boole-függvény olyan függvény, amelyben a változók csak két értéket vesznek fel: egy logikai egyet vagy egy logikai nullát. Az összetett állítások igazsága vagy hamissága az egyszerű állítások igazságának vagy hamisságának függvénye. Ezt a függvényt f (a, b) logikai ítéletfüggvénynek nevezzük.

Bármely logikai függvény megadható egy igazságtáblázat segítségével, amelynek bal oldalán egy argumentumkészlet van írva, a jobb oldalon pedig a logikai függvény megfelelő értékei.

Az igazságtábla felépítésénél figyelembe kell venni a logikai műveletek végrehajtásának sorrendjét. A logikai kifejezésben a műveletek balról jobbra haladva, a zárójeleket is beleértve, a következő sorrendben hajtják végre:

• 1. inverzió;
• 2. kötőszó;
• 3. diszjunkció;
• 4. implikáció és egyenértékűség.

A zárójelek a logikai műveletek meghatározott sorrendjének megváltoztatására szolgálnak.

A következő igazságtábla algoritmus.

• 1. Határozza meg a bemeneti változók készleteinek száma- a kifejezésekben szereplő változók értékeinek összes lehetséges kombinációja a következő képlet szerint: Q=2 n, ahol n a bemeneti változók száma. Meghatározza a táblázat sorainak számát.
• 2. Írja be a táblázatba a bemeneti változók összes készletét.
• 3. Határozza meg a logikai műveletek számát és végrehajtásuk sorrendjét!
• 4. Töltse ki az oszlopokat a logikai műveletek végrehajtásának eredményeivel a megadott sorrendben!

Annak érdekében, hogy a bemeneti változók értékeinek bármilyen lehetséges kombinációját ne ismételje meg vagy ne hagyja ki, a táblázat kitöltésének alábbi módjait kell használni.

1. módszer. A bemeneti változók minden egyes értékkészlete egy számkód a bináris számrendszerben, és a szám számjegyeinek száma megegyezik a bemeneti változók számával. Az első halmaz a 0. Ha az aktuális számhoz minden alkalommal hozzáadunk 1-et, akkor a következő halmazt kapjuk. Az utolsó halmaz egy bináris szám maximális értéke egy adott kódhosszhoz.

Például egy három változóból álló függvény esetén a halmazok sorozata számokból áll:

2. módszer. Három változó függvényében az adatsort a következő módon kaphatjuk meg:

• a) oszd ketté az első változó értékoszlopát, és töltsd fel a felső felét nullákkal, az alsót pedig egyesekkel;
• b) a következő oszlopban a második változóhoz osszuk újra a felét, és töltsük ki nullák és egyesek csoportjaival; hasonlóan töltse ki a második felét;
• c) addig csináld ezt, amíg a nullák és egyesek csoportjai egy karakterből állnak.

3. módszer. Használja az ismert igazságtáblázatot két argumentumhoz. A harmadik argumentum hozzáadásakor először írja be a táblázat első 4 sorát, kombinálva a harmadik argumentum 0-val egyenlő értékével, majd írja be újra ugyanazt a 4 sort, de most a harmadik argumentum 1-es értékével Ennek eredményeként a három argumentum táblázata 8 soros lesz:

Például készítsünk igazságtáblázatot egy logikai függvényhez:

A bemeneti változók száma az adott kifejezésben három (ABC). Tehát a bemeneti halmazok száma Q=2 3 =8 .

Az igazságtáblázat oszlopai megfelelnek az eredeti kifejezések értékeinek ABC, köztes eredmények és ( B V C), valamint egy összetett aritmetikai kifejezés kívánt végső értékét:

• 0 0 0 1 0 0
• 0 0 1 1 1 1
• 0 1 0 1 1 1
• 0 1 1 1 1 1
• 1 0 0 0 0 0
• 1 0 1 0 1 0
• 1 1 0 0 1 0
• 1 1 1 0 1 0
• 7.4. Logikai függvények és transzformációik. A logika törvényei

A konjunkció, a diszjunkció és az inverzió műveleteihez a Boole-algebra törvényei vannak meghatározva, amelyek lehetővé teszik az logikai kifejezések azonos (ekvivalens) transzformációi.

A logika törvényei

• 1. ¬¬ A
• 2.A&B
• 3. AVB
• 4. A&(B&C)
• 5.AV(BVC)
• 6. A&(BVC)
• 7.AV(B&C)
• 8.A&A
• 9. Ava
• 10. AV-A
• 11. A&¬A
• 12. A&I
• 13. AVI
• 14. A&L
• 15. AVL
• 16. ¬(A&B)
• 17. ¬(AVB)
• 18. A => B

A törvények alapján egyszerűsítheti az összetett logikai kifejezéseket. Ezt a folyamatot, amikor egy összetett logikai függvényt egy egyszerűbb, de egyenértékű függvényre cserélünk, függvényminimalizálásnak nevezzük.

1. példa Egyszerűsítse a kifejezéseket, hogy az eredményül kapott képletek ne tartalmazzák az összetett utasítások tagadását.

Megoldás

2. példa Funkció minimalizálása

A kifejezés egyszerűsítéséhez az abszorpciós és ragasztási képleteket használtam.

3. példa Keresse meg a következő állítás tagadását: "Ha az óra érdekes, akkor egyik diák (Misha, Vika, Sveta) sem fog kinézni az ablakon."

Megoldás

Jelöljük az állításokat:

Y- "Érdekes a lecke";

M- "Misha kinéz az ablakon";

B- "Vika kinéz az ablakon";

C- "Sveta kinéz az ablakon."

A kifejezés egyszerűsítésekor a műveletek helyettesítő képletét és de Morgan törvényét használtuk.

4. példa Határozza meg a bűncselekmény résztvevőjét két feltétel alapján: logikai számítógép asztal

• 1) "Ha Ivanov nem vett részt, vagy Petrov részt vett, akkor Sidorov részt vett";
• 2) "Ha Ivanov nem vett részt, akkor Sidorov nem vett részt."

Megoldás

Tegyünk kifejezéseket:

én- "Ivanov részt vett a bűncselekményben";

P- "Petrov részt vett a bűncselekményben";

S- "Sidorov részt vett a bűncselekményben."

A csomagokat képletek formájában írjuk le:

Ellenőrizzük az eredményt az igazságtáblázat segítségével:

Válasz: Ivanov részt vett a bűncselekményben.

Logikai függvény felépítése az igazságtáblázatból

Megtanultuk, hogyan készítsünk igazságtáblázatot egy logikai függvényhez. Próbáljuk meg megoldani a fordított problémát.

Tekintsük azokat a sorokat, ahol a Z függvény igazságértéke igaz (Z=1). Ennek az igazságtáblázatnak a függvénye a következőképpen írható fel: Z(X,Y) = (¬X& ¬Y)V(X& ¬Y).

Minden sor, ahol a függvény igaz (egyenlő 1-gyel), egy zárójelnek felel meg, ami argumentumok konjunkciója, és ha az argumentum értéke 0, akkor tagadással vesszük. Az összes konzolt a szétválasztási művelet köti össze. A kapott képlet a logika törvényeinek alkalmazásával egyszerűsíthető:

Z(X,Y)<=>((¬X& ¬Y) VX)&((¬X&Y)V ¬Y)<=>(XV(¬X& ¬Y)) &(¬YV(¬X&¬Y))<=>((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y))<=>(1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=>(XV ¬Y)&((¬YV ¬X)& ¬Y).

Ellenőrizze a kapott képletet: készítsen igazságtáblázatot a Z(X,Y) függvényhez.

Írja le a logikai függvény összeállításának szabályait az igazságtáblázata szerint:

• 1. Válassza ki az igazságtáblázatban azokat a sorokat, amelyekben a függvény értéke 1.
• 2. Írja fel a kívánt képletet több logikai elem diszjunkciójaként! Ezen elemek száma megegyezik a kiválasztott sorok számával.
• 3. Írjon minden logikai elemet ebben a diszjunkcióban függvényargumentumok konjunkciójaként.
• 4. Ha a táblázat megfelelő sorában bármely függvény argumentum értéke 0, akkor ezt az argumentumot tagadással vesszük.

1. definíció

Boole-függvény egy olyan függvény, amelynek változói két érték egyikét veszik fel: $1$ vagy $0$.

Bármely logikai függvény megadható igazságtáblázat segítségével: az összes lehetséges argumentum halmaza a táblázat bal oldalán, a logikai függvény megfelelő értékei pedig a jobb oldalon találhatók.

2. definíció

igazságtáblázat- egy táblázat, amely megmutatja, hogy egy összetett kifejezés milyen értékeket vesz fel a benne szereplő egyszerű kifejezések összes lehetséges értékkészletéhez.

3. definíció

Egyenértékű logikai kifejezéseknek nevezzük, amelyek igazságtáblázatának utolsó oszlopai egybeesnek. Az egyenértékűséget a $"="$ jel jelzi.

Az igazságtáblázat összeállításakor fontos figyelembe venni a logikai műveletek következő végrehajtási sorrendjét:

1. kép

A műveletek végrehajtási sorrendjében a zárójelek élveznek elsőbbséget.

Algoritmus egy logikai függvény igazságtáblázatának elkészítésére

Határozza meg a sorok számát: sorok száma= $2^n + 1$ (a címsorhoz), $n$ az egyszerű kifejezések száma. Például két változóból álló függvények esetén $2^2 = 4$ változó értékhalmaz kombinációja van, három változóból álló függvényeknél $2^3 = 8$ és így tovább.

Határozza meg az oszlopok számát: oszlopok száma = változók száma + logikai műveletek száma. A logikai műveletek számának meghatározásakor figyelembe veszik a végrehajtásuk sorrendjét is.

Töltse ki az oszlopokat a logikai műveletek végrehajtásának eredményeivel meghatározott sorrendben, figyelembe véve az alapvető logikai műveletek igazságtáblázatait.

2. ábra.

1. példa

Készítsen igazságtáblázatot a $D=\bar(A) \vee (B \vee C)$ logikai kifejezésből.

Megoldás:

Határozzuk meg a sorok számát:

sorok száma = $2^3 + 1=9$.

A változók száma $3$.

1. invert ($\bar(A)$);
2. diszjunkció, mert zárójelben van ($B \vee C$);

3. diszjunkció ($\overline(A)\vee \left(B\vee C\right)$) a szükséges logikai kifejezés.

   Oszlopok száma = $3 + 3=6$.

Töltsük ki a táblázatot, figyelembe véve a logikai műveletek igazságtáblázatait!

3. ábra

2. példa

A megadott logikai kifejezés alapján készítsünk igazságtáblázatot:

Megoldás:

Határozzuk meg a sorok számát:

Az egyszerű kifejezések száma $n=3$, tehát

sorok száma = $2^3 + 1=9$.

Határozzuk meg az oszlopok számát:

A változók száma $3$.

A logikai műveletek száma és sorrendje:

1. tagadás ($\bar(C)$);
2. diszjunkció, mert zárójelben van ($A \vee B$);
3. kötőszó ($(A\vee B)\bigwedge \overline(C)$);
4. tagadás, amit $F_1$-val jelölünk ($\overline((A\vee B)\bigwedge \overline(C))$);
5. diszjunkció ($A \vee C$);
6. kötőszó ($(A\vee C)\bigwedge B$);
7. tagadás, amit $F_2$-val jelölünk ($\overline((A\vee C)\bigwedge B)$);

8. a diszjunkció a kívánt logikai függvény ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

Alapján: demó HASZNÁLJON lehetőségeket Informatikából 2015-re Ljudmila Leonidovna Bosova tankönyvéről

Az előző 1. részben a Disjunktion és Conjunction logikai műveleteket elemeztük veled, nekünk maradt az inverzió elemzése, és továbblépünk az USE feladat megoldására.

Inverzió

Inverzió- logikai művelet, amely minden állítást egy új kijelentéshez társít, amelynek jelentése ellentétes az eredetivel.

Az inverzió írásához a következő karakterek használhatók: NOT, `¯` , ` ¬ `

Az inverziót a következő igazságtáblázat határozza meg:

Az inverziót más néven logikai negációnak nevezik.

Bármilyen összetett állítás felírható így logikai kifejezés- logikai változókat, logikai műveletek jeleit és zárójeleket tartalmazó kifejezés. A logikai kifejezésekben a logikai műveletek végrehajtása a következő sorrendben történik: inverzió, konjunkció, diszjunkció. Zárójelek elhelyezésével módosíthatja a műveletek végrehajtásának sorrendjét.

A logikai műveletek prioritása a következő: inverzió, konjunkció, diszjunkció.

Így van a 2. számú feladatunk az Egységes Informatikai Államvizsga 2015-ből

Alexandra kitöltötte az F kifejezés igazságtáblázatát. Csak egy kis töredéket sikerült kitöltenie a táblázatból:

x1	x2	x3	x4	x5	x6	x7	x8	F
	0						1	0
1			0					1
			1				1	1

Milyen kifejezés lehet F?

A feladat megoldását nagyban megkönnyíti, hogy az F összetett kifejezés minden változatában csak egyetlen logikai művelet van: szorzás vagy összeadás. Szorzás esetén /\ ha legalább egy változó nulla, akkor a teljes F kifejezés értékének is nullának kell lennie. V összeadás esetén pedig, ha legalább egy változó egyenlő eggyel, akkor a teljes F kifejezés értékének 1-gyel kell egyenlőnek lennie.

A táblázatban szereplő adatok az F kifejezés mind a 8 változójához elegendőek a megoldáshoz.

Ellenőrizzük az 1-es számú kifejezést:

• ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
• a táblázat második sorában x1=1, x4=0 azt látjuk, hogy F lehetséges és egyenlő lehet = 1-gyel, ha az összes többi változó egyenlő 1-gyel (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
• táblázat harmadik sora szerint x4=1, x8=1 azt látjuk, hogy F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), és a táblázatban van F=1, és ez azt jelenti, hogy az első számú kifejezés we BIZTOSAN NEM ALKALMAS.

Nézzük a 2-es számú kifejezést:

• a táblázat első sorából x2=0, x8=1 láthatjuk, hogy F lehetséges és egyenlő lehet = 0-val, ha az összes többi változó egyenlő 0-val (? V 0 V ? V ? V ? V ? V ? V 0 )
• a táblázat második sorában x1=1, x4=0 azt látjuk, hogy F = 1 ( 1 V ? V ? V 1 V ? V ? V ? V ? )
• a táblázat harmadik sorából x4=1, x8=1 láthatjuk, hogy F lehetséges és egyenlő lehet = 1-gyel, ha a fennmaradó változók közül legalább egy egyenlő 1-gyel ( ? V ? V ? V 0 V ? V ? V ? V 0 )
  

Nézzük a 3-as számú kifejezést:

• a táblázat első sorában x2=0, x8=1 azt látjuk, hogy F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
• a táblázat második sorában x1=1, x4=0 azt látjuk, hogy F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), és a táblázatban van F=1, és ez azt jelenti, hogy a hármas számú kifejezés we BIZTOSAN NEM ALKALMAS.

Nézzük a 4-es számú kifejezést:

• a táblázat első sorában x2=0, x8=1 azt látjuk, hogy F=1 ( ? V 1 V ? V ? V ? V ? V ? V 0 ), és a táblázatban van F=0, és ez azt jelenti, hogy a négyes számú kifejezés számunkra BIZTOSAN NEM ALKALMAS.

Egységes államvizsgán egy feladat megoldásakor pontosan ugyanezt kell tenni: azokat a lehetőségeket, amelyek a táblázatban szereplő adatok szerint nem pontosan illeszkednek, el kell dobni. Többi lehetséges változata(mint esetünkben a 2-es számú opció), és ez lesz a helyes válasz.

Digitális áramkörben digitális jel egy olyan jel, amely két értéket vehet fel, egy logikai "1"-nek és egy logikai "0"-nak.

A logikai áramkörök akár 100 millió bemenetet is tartalmazhatnak, és léteznek ilyen óriási áramkörök. Képzelje el, hogy egy ilyen áramkör Boole-függvénye (egyenlete) elveszett. Hogyan lehet visszaállítani a legkevesebb időveszteséggel és hiba nélkül? A legtermékenyebb módja a séma szintekre bontása. Ezzel a módszerrel az előző réteg minden egyes elemének kimeneti függvénye megírásra kerül, és behelyettesíti a megfelelő bemenetet a következő rétegben. Ma megvizsgáljuk a logikai áramkörök elemzésének ezt a módszerét minden árnyalattal.

A logikai áramkörök a következő logikai elemeken vannak megvalósítva: "NOT", "AND", "OR", "AND-NOT", "OR-NOT", "XOR" és "Equivalence". Az első három logikai elem lehetővé teszi bármely tetszőlegesen összetett logikai függvény logikai alapon történő megvalósítását. Meg fogjuk oldani a logikai áramkörök problémáit, amelyek logikai alapon vannak megvalósítva.

Számos szabványt használnak a logikai elemek kijelölésére. A leggyakoribbak az amerikai (ANSI), európai (DIN), nemzetközi (IEC) és orosz (GOST). Az alábbi ábra a logikai elemek megnevezéseit mutatja ezekben a szabványokban (a képre a bal egérgombbal kattintva nagyítható).

Ebben a leckében olyan logikai áramkörök problémáit oldjuk meg, amelyekben a logikai elemek a GOST szabványban vannak kijelölve.

A logikai áramkörökre vonatkozó feladatok kétfélék: a logikai áramkörök szintetizálásának problémája és a logikai áramkörök elemzésének problémája. Kezdjük a második típusú feladattal, mivel ebben a sorrendben gyorsan elsajátítható a logikai diagramok olvasása.

Leggyakrabban a logikai áramkörök felépítésével kapcsolatban a logikai algebra funkcióit veszik figyelembe:

• három változó (az elemzési és egy szintézisproblémánál figyelembe kell venni);
• négy változó (a szintézis feladatokban, vagyis az utolsó két bekezdésben).

Tekintsük a logikai áramkörök felépítését (szintézisét).

• logikai alapon "ÉS", "VAGY", "NEM" (az utolsó előtti bekezdésben);
• a szintén gyakori "ÉS-NEM" és "VAGY-NEM" alapokon (az utolsó bekezdésben).

A logikai áramkörök elemzésének feladata

Az elemzés feladata a függvény meghatározása f adott logikai áramkör által megvalósított. Egy ilyen probléma megoldása során célszerű követni a következő műveletsort.

1. A logikai séma szintekre van osztva. A szintek sorszámokat kapnak.
2. Az egyes logikai elemek kimeneteit a kívánt függvény neve jelzi, digitális indexszel ellátva, ahol az első számjegy a réteg száma, a fennmaradó számjegyek pedig a rétegben lévő elem sorszáma.
3. Minden elemhez írunk egy analitikus kifejezést, amely a kimeneti függvényét a bemeneti változókhoz kapcsolja. A kifejezést az adott logikai elem által megvalósított logikai függvény határozza meg.
4. Egyes kimeneti függvények másokkal való helyettesítését addig hajtják végre, amíg egy logikai függvényt nem kapunk, amelyet bemeneti változókkal fejezünk ki.

1. példa

Megoldás. A logikai áramkört rétegekre osztjuk, ami már az ábrán is látható. Írjuk fel az összes függvényt az 1. szinttől kezdve:

x, y, z :

x	y	z					f
1	1	1	0	1	1	1	1
1	1	0	0	0	0	1	0
1	0	1	0	0	0	1	0
1	0	0	0	0	0	1	0
0	1	1	0	0	0	1	0
0	1	0	0	0	0	1	0
0	0	1	0	0	0	1	0
0	0	0	1	0	1	0	0

2. példa Keresse meg a logikai áramkör logikai függvényét, és készítsen igazságtáblázatot a logikai áramkör számára.

3. példa Keresse meg a logikai áramkör logikai függvényét, és készítsen igazságtáblázatot a logikai áramkör számára.

Továbbra is együtt keressük a logikai áramkör logikai függvényét

4. példa Keresse meg a logikai áramkör logikai függvényét, és készítsen igazságtáblázatot a logikai áramkör számára.

Megoldás. A logikai áramkört szintekre bontjuk. Írjuk fel az összes függvényt az 1. szinttől kezdve:

Most írjuk fel az összes függvényt, helyettesítve a bemeneti változókat x, y, z :

Ennek eredményeként azt a függvényt kapjuk, amelyet a logikai áramkör a kimeneten megvalósít:

.

Igazságtáblázat egy adott logikai áramkörhöz:

x	y	z			f
1	1	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
1	0	0	0	0	0
0	1	1	0	1	1
0	1	0	0	1	1
0	0	1	0	1	1
0	0	0	0	1	1

5. példa Keresse meg a logikai áramkör logikai függvényét, és készítsen igazságtáblázatot a logikai áramkör számára.

Megoldás. A logikai áramkört szintekre bontjuk. Ennek a logikai áramkörnek az előző példákkal ellentétben 5 rétege van, nem 4. De egy bemeneti változó - a legalacsonyabb - átfut az összes rétegen, és közvetlenül belép az első réteg logikai elemébe. Írjuk fel az összes függvényt az 1. szinttől kezdve:

Most írjuk fel az összes függvényt, helyettesítve a bemeneti változókat x, y, z :

Ennek eredményeként azt a függvényt kapjuk, amelyet a logikai áramkör a kimeneten megvalósít:

.

Igazságtáblázat egy adott logikai áramkörhöz:

x	y	z			f
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	0	1
0	0	0	1	0	1

Logikai áramkörök logikai alapon történő szintetizálásának problémája

A logikai áramkör analitikai leírása szerinti fejlesztését a logikai áramkör szintézisének problémájának nevezzük.

Minden diszjunkció (logikai összeg) az "OR" elemnek felel meg, amelynek bemeneteinek számát a diszjunkcióban lévő változók száma határozza meg. Minden kötőszó (logikai szorzat) az "ÉS" elemnek felel meg, amelynek bemeneteinek számát a konjunkcióban lévő változók száma határozza meg. Minden tagadás (inverzió) a "NOT" elemnek felel meg.

A logikai áramkör tervezése gyakran egy logikai függvény meghatározásával kezdődik, amelyet a logikai áramkörnek végre kell hajtania. Ebben az esetben csak a logikai áramkör igazságtáblázata van megadva. Éppen egy ilyen példát fogunk elemezni, vagyis egy olyan feladatot oldunk meg, amely teljesen fordított a logikai áramkörök elemzésének fentebb tárgyalt problémájával.

6. példa Szerkesszünk olyan logikai áramkört, amely adott igazságtáblázattal valósít meg egy függvényt.

Logikai algebra

Logikai algebra

Logikai algebra(Angol) logikai algebra) a matematikai logika egyik fő ága, amelyben az algebra módszereit használják a logikai transzformációkban.

A logikai algebra megalapítója J. Boole (1815-1864) angol matematikus és logikus, aki az algebra és a logika analógiájára alapozta logikai doktrínáját. Minden állítást az általa kidolgozott nyelv szimbólumaival lejegyzett és kapott „egyenleteket”, amelyek igazsága vagy hamissága bizonyos logikai törvények alapján igazolható volt, mint például a kommutativitás, az eloszlás, az asszociativitás stb.

Modern logikai algebra a matematikai logika egyik ága, és az állításokra vonatkozó logikai műveleteket vizsgálja azok igazságértéke (igaz, hamis) szempontjából. Az állítások lehetnek igazak, hamisak, vagy különböző arányban tartalmazhatnak igazságot és hamisságot.

logikai kijelentés minden olyan kijelentő mondat, amelyre vonatkozóan egyértelműen kijelenthető, hogy tartalma igaz vagy hamis.

Például a „3-szor 3 egyenlő 9-cel”, „Arhangelszk Vologdától északra” igaz állítások, és az „öt kevesebb, mint három”, a „Mars egy csillag” hamisak.

Nyilvánvalóan nem minden mondat lehet logikus állítás, hiszen nem mindig van értelme annak hamisságáról vagy igazságáról beszélni. Például a „Számítástechnika érdekes téma” kijelentés homályos és megköveteli további információ, valamint az „A. A. Ivanov 10. osztályos diák számára az informatika érdekes tantárgy” kijelentés A. A. Ivanov érdeklődési körétől függően „igaz” vagy „hamis” értéket vehet fel.

Kivéve kétértékű propozíciós algebra, amelyben csak két érték fogadható el - "igaz" és "hamis", van többértékű propozíciós algebra. Egy ilyen algebrában az "igaz" és a "hamis" jelentések mellett olyan igazságértékeket használnak, mint a "valószínűleg", "lehetséges", "lehetetlen" stb.

Az algebrában a logika különbözik egyszerű(alapvető) nyilatkozatok, latin betűkkel jelölve (A, B, C, D, ...), és összetett(összetett), több egyszerűből áll össze logikai konnektívumokkal, például, mint pl "nem", "és", "vagy", "ha és csak akkor", "ha ... akkor". Az így kapott összetett állítások igazát vagy hamisságát az egyszerű állítások jelentése határozza meg.

Jelölje mint A„A logikai algebrát sikeresen alkalmazták az elektromos áramkörök elméletében”, és azon keresztül BAN BEN- "A logikai algebrát reléérintkezős áramkörök szintézisében használják."

Ezután az összetett állítás: "A logika algebráját sikeresen alkalmazzák az elméletben elektromos áramkörök a reléérintkezős áramkörök szintézisében pedig "röviden így írható A és B; itt az "és" egy logikai kapcsoló. Nyilvánvalóan az elemi tételek óta A és B igazak, akkor az összetett állítás is igaz A és B.

Minden egyes logikai összeköttetés logikai utasításokon végzett műveletnek minősül, és megvan a maga neve és megnevezése.

Csak két logikai érték létezik: igazÉs hamis (FALSE). Ez megfelel a digitális ábrázolásnak − 1 És 0 . Az egyes logikai műveletek eredményeit táblázat formájában rögzíthetjük. Az ilyen táblázatokat igazságtáblázatoknak nevezzük.

A logikai algebra alapműveletei

1. Logikai tagadás, inverzió(lat. inverzió- megfordítás) - logikai művelet, amelynek eredményeként új utasítást kapunk egy adott utasításból (például A) ( nem A), amely az úgynevezett az eredeti állítás tagadása, amelyet szimbolikusan egy felső sáv ($A↖(-)$) vagy olyan konvenciók jelölnek, mint pl. ¬, "nem", és így szól: "nem A", "A hamis", "nem igaz, hogy A", "A tagadása". Például: "A Mars egy bolygó a Naprendszerben" (A állítás); "A Mars nem bolygó a Naprendszerben" ($A↖(-)$); a "10 egy prímszám" állítás (B állítás) hamis; a "10 nem prímszám" állítás (B állítás) igaz.

Egy mennyiségre vonatkozó műveletet hívunk egységes. Ennek a műveletnek az értéktáblázata a következő formában van

$A↖(-)$ hamis, ha A igaz és igaz, ha A hamis.

Geometriailag a negáció a következőképpen ábrázolható: ha A egy bizonyos ponthalmaz, akkor $A↖(-)$ az A halmaz komplementere, vagyis minden olyan pont, amely nem tartozik az A halmazba.

2.Konjunkció(lat. conjunctio- kapcsolat) - logikai szorzás, olyan művelet, amely legalább két logikai értéket (operandusokat) igényel, és két vagy több utasítást köt össze egy csomó segítségével "És"(Például, "A és B"), amelyet szimbolikusan a ∧ (A ∧ B) jel jelöl, és így szól: „A és B”. A következő jeleket is használják az együttállás jelzésére: A ∙ B; A és B, A és B, és néha nem teszünk jelet az állítások közé: AB. Példa a logikai szorzásra: "Ez a háromszög egyenlő szárú és derékszögű." Ez az állítás csak akkor lehet igaz, ha mindkét feltétel teljesül, ellenkező esetben az állítás hamis.

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

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

Geometriailag a konjunkció a következőképpen ábrázolható: ha A, B A ∧ BAN BEN halmazok metszéspontja van AÉs BAN BEN.

3. Diszjunkció(lat. diszjunkció- osztás) - logikai összeadás, olyan művelet, amely két vagy több utasítást köt össze egy csomó segítségével "vagy"(Például, "A vagy B"), amelyet szimbolikusan a ∨ jel jelöl (A∨ BAN BEN)és így szól: "A vagy B". A következő jeleket is használják a szétválás jelzésére: A + B; A vagy B; A | B. Példa logikai összeadásra: "Az x szám osztható 3-mal vagy 5-tel." Ez a tétel akkor lesz igaz, ha mindkét feltétel vagy legalább az egyik feltétel teljesül.

A művelet igazságtáblázatának alakja van

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

nyilatkozat A∨ BAN BEN csak akkor hamis, ha mindkét állítás igaz AÉs BAN BEN hamis.

Geometriailag a logikai összeadás a következőképpen ábrázolható: ha A, B akkor néhány ponthalmaz A ∨ BAN BEN a halmazok uniója AÉs BAN BEN, azaz egy négyzetet és kört is egyesítő figura.

4. Szigorú diszjunkciós diszjunkció, modulo két összeadás- egy logikai művelet, amely két utasítást kapcsol össze konnektiv segítségével "vagy", kizárólagos értelemben használva, amelyet szimbolikusan a ∨ ∨ vagy ⊕ ( A ∨ ∨ B, A ⊕ BAN BEN) és így szól: "Vagy a vagy B". Példa a modulo two összeadásra az „Ez a háromszög tompa vagy hegyesszög” kijelentés. Az állítás akkor igaz, ha valamelyik feltétel teljesül.

A művelet igazságtáblázatának alakja van

A	BAN BEN	A⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Az A ⊕ B állítás csak akkor igaz, ha az A és B állításnak eltérő jelentése van.

5. következmény(lat. imlisito- szorosan összekapcsolom) - egy logikai művelet, amely két utasítást köt össze egy csomó segítségével "ha akkor"összetett kijelentéssé, amelyet szimbolikusan a → ( A → BAN BEN) és így szól: "ha A, akkor B", "A azt jelenti, hogy B", "A-ból B következik", "A azt jelenti, hogy B". A ⊃ (A ⊃ B) jelet az implikáció jelölésére is használják. Példa az implikációra: "Ha a kapott négyszög négyzet, akkor körülírható egy kör." Ez a művelet két egyszerű logikai kifejezést köt össze, amelyek közül az első feltétele, a második pedig következménye. Egy művelet eredménye csak akkor hamis, ha az előfeltevés igaz, a következmény pedig hamis. Például: "Ha 3 * 3 = 9 (A), akkor a Nap bolygó (B)", az A → B implikáció eredménye hamis.

A művelet igazságtáblázatának alakja van

A	BAN BEN	A→BAN BEN
1	0	0
0	1	1
0	0	1
1	1	1

Az implikáció működésére igaz az az állítás, hogy a hazugságból bármi következhet, de igazságból csak az igazság.

6. Egyenértékűség, kettős implikáció, ekvivalencia(lat. aequalis- egyenlő és valentis- érvényes) - logikai művelet, amely két állítást tesz lehetővé AÉs BAN BEN kap egy új nyilatkozatot A ≡ B amely így szól: "A egyenlő B-vel". Az ekvivalencia jelzésére a következő jelek is használatosak: ⇔, ∼. Ez a művelet konnektívumokkal fejezhető ki „ha és csak akkor”, „szükséges és elégséges”, „egyenértékű”. Egy példa az ekvivalenciára a következő állítás: "A háromszög akkor és csak akkor lesz derékszögű, ha az egyik szög 90 fokkal egyenlő."

Az ekvivalencia-művelet igazságtáblázatának alakja van

A	BAN BEN	A∼ BAN BEN
1	0	0
0	1	0
0	0	1
1	1	1

Az ekvivalencia művelet a modulo 2 összeadás ellentéte, és akkor és csak akkor értékel ki igazra, ha a változók értéke megegyezik.

Az egyszerű állítások jelentésének ismeretében igazságtáblázatok alapján meg lehet határozni az összetett állítások jelentését. Ugyanakkor fontos tudni, hogy három művelet elegendő a logikai algebra bármely függvényének ábrázolásához: a konjunkció, a diszjunkció és a negáció.

A logikai műveletek prioritása a következő: negáció ( "Nem") a legmagasabb prioritású, akkor a kötőszó ( "És"), kötőszó után — diszjunkció ( "vagy").

Logikai változók és logikai műveletek segítségével bármilyen logikai állítás formalizálható, azaz logikai képlettel helyettesíthető. Ugyanakkor az összetett állítást alkotó elemi állítások jelentésükben teljesen függetlenek lehetnek, de ez nem akadályozza meg az összetett állítás igazának vagy hamisságának megállapítását. Például a „Ha öt nagyobb, mint kettő ( A), akkor a kedd mindig hétfő után jön ( BAN BEN)" - következmény A→ BAN BEN, és a művelet eredménye ebben az esetben "igaz". A logikai műveleteknél az állítások jelentését nem veszik figyelembe, csak azok igazát vagy hamisságát.

Vegyünk például egy összetett állítás felépítését állításokból AÉs BAN BEN, ami akkor és csak akkor lenne hamis, ha mindkét állítás igaz. A modulo two összeadás műveletének igazságtáblázatában ezt találjuk: 1 ⊕ 1 = 0. Az állítás pedig lehet például ez: „Ez a golyó teljesen piros vagy teljesen kék.” Ezért ha az állítás A"Ez a labda teljesen piros" igaz és kijelentés BAN BEN„Ez a labda teljesen kék” igaz, akkor az összetett állítás hamis, mivel a labda nem lehet egyszerre piros és kék.

Példák problémamegoldásra

1. példa Határozza meg X jelzett értékeihez a logikai utasítás értékét ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Megoldás. A műveletek sorrendje a következő: először a zárójelben lévő összehasonlító műveleteket hajtjuk végre, majd a diszjunkciót és az utolsó implikációs műveletet hajtjuk végre. A diszjunkciós operátor ∨ ​​akkor és csak akkor hamis, ha mindkét operandus hamis. Az implikáció igazságtáblázata az

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

Innen kapjuk:

1) X = 1 esetén:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) X = 12 esetén:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) X = 3 esetén:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

2. példa Adja meg azon X egész értékek halmazát, amelyekre az ¬((X > 2) → (X > 5)) kifejezés igaz.

Megoldás. A negációs művelet a teljes kifejezésre vonatkozik ((X > 2) → (X > 5)) , tehát ha a ¬((X > 2) → (X > 5)) kifejezés igaz, akkor az ((X > 2) →(X > 5)) hamis. Ezért meg kell határozni, hogy X mely értékeire hamis a kifejezés ((X > 2) → (X > 5)). Az implikációs operátor csak egy esetben veszi fel a "false" értéket: amikor az igazságból hamis következik. És ez csak X = 3 esetén igaz; X=4; X=5.

3. példa Az alábbi szavak közül melyikre hamis az ¬(első betű magánhangzó ∧ harmadik betű magánhangzó) ⇔ 4 karakterből álló állítás? 1) ász; 2) süti; 3) kukorica; 4) hiba; 5) erős ember.

Megoldás. Nézzük meg egyenként a következő szavakat:

1) az assa szóra a következőt kapjuk: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — az állítás igaz;

2) a kuku szóra a következőket kapjuk: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — az állítás igaz;

3) a kukorica szóra a következőket kapjuk: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - az állítás hamis;

4) a hiba szóra a következőt kapjuk: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — az állítás igaz;

5) az erősember szóra a következőt kapjuk: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - az állítás hamis.

Logikai kifejezések és konvertálásuk

Alatt logikai kifejezés olyan rekordként kell érteni, amely felveheti az „igaz” vagy „hamis” logikai értéket. Ezzel a meghatározással a logikai kifejezések között meg kell különböztetni a következőket:

• olyan kifejezések, amelyek összehasonlítási műveleteket használnak ("nagyobb, mint", "kisebb, mint", "egyenlő", "nem egyenlő" stb.) és logikai értékeket vesznek fel (például az a > b kifejezés, ahol a = 5 és b = 7, egyenlő "hamis");
• logikai értékekhez és logikai műveletekhez kapcsolódó közvetlen logikai kifejezések (például A ∨ B ∧ C, ahol A = igaz, B = hamis és C = igaz).

A logikai kifejezések tartalmazhatnak függvényeket, algebrai műveleteket, összehasonlító műveleteket és logikai műveleteket. Ebben az esetben a műveletek végrehajtásának prioritása a következő:

1. meglévő funkcionális függőségek számítása;
2. algebrai műveletek végrehajtása (először szorzás és osztás, majd kivonás és összeadás);
3. összehasonlítási műveletek végrehajtása (véletlen sorrendben);
4. logikai műveletek végrehajtása (először a negációs művelet, majd a logikai szorzás, logikai összeadás műveletei, az utolsó műveletek az implikáció és az ekvivalencia).

A logikai kifejezések zárójeleket használhatnak, amelyek megváltoztatják a műveletek végrehajtásának sorrendjét.

Példa. Keresse meg egy kifejezés értékét:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$, ha a = 2, b = 3, A = igaz, B = hamis.

Megoldás. Az értékek számlálási sorrendje:

1) b a + a b > a + b, behelyettesítés után kapjuk: 3 2 + 2 3 > 2 + 3, azaz 17 > 2 + 3 = igaz;

2) A ∧ B = igaz ∧ hamis = hamis.

Ezért a zárójeles kifejezés (b a + a b > a + b ∨ A ∧ B) = igaz ∨ hamis = igaz;

3) 1≤ a = 1 ≤ 2 = igaz;

4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

Ezen számítások után végül azt kapjuk, hogy igaz ∨ A ∧ igaz ∧ ¬B ∧ ¬igaz.

Most végre kell hajtani a negációs műveleteket, majd a logikai szorzást és összeadást:

5) ¬B = ¬hamis = igaz; ¬igaz = hamis;

6) A ∧ igaz ∧ igaz ∧ hamis = igaz ∧ igaz ∧ igaz ∧ hamis = hamis;

7) igaz ∨ hamis = igaz.

Így az adott értékek logikai kifejezésének eredménye "igaz".

Jegyzet. Tekintettel arra, hogy az eredeti kifejezés végső soron két tag összege, és az egyiknek az értéke 1 ≤ a = 1 ≤ 2 = igaz, további számítások nélkül kijelenthetjük, hogy az eredmény a teljes kifejezésre is "igaz". ”.

Logikai kifejezések identitástranszformációi

A logika algebrájában teljesülnek azok az alaptörvények, amelyek lehetővé teszik a logikai kifejezések azonos transzformációit.

Törvény	∨ számára	∧-re
elmozdítható	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Asszociációs	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
terjesztés	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
De Morgan uralkodik	$(A ∨ B)↖(-)$ = $A↖(-) ∧ B↖(-)$	$(A ∧ B)↖(-)$ = $A↖(-) ∨ B↖(-)$
Idempotencia	A ∨ A = A	A ∧ A = A
Átvételek	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Ragasztás	(A ∧ B) ∨ (A↖(-) ∧ B) = B	(A ∨ B) ∧ (A↖(-) ∨ B) = B
Változó művelet annak inverzével	$A ∨ A↖(-)$ = 1	$A ∧ A↖(-)$ = 0
Működés konstansokkal	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
dupla negatív	$A↖(=)$ = A

Ezeknek az állításoknak a bizonyítása a megfelelő rekordokhoz tartozó igazságtáblázatok felépítése alapján történik.

A logikai képletek ekvivalens transzformációinak célja ugyanaz, mint a közönséges algebra képleteinek. Arra szolgálnak, hogy a logikai algebra alaptörvényeit felhasználva a képleteket leegyszerűsítsék vagy egy bizonyos formába hozzanak. Alatt képlet egyszerűsítése, amely nem tartalmazza az implikáció és az ekvivalencia műveleteit, ekvivalens transzformáció alatt értendő, amely egy olyan képlethez vezet, amely vagy az eredetihez képest kevesebb műveletet, vagy kevesebb változót tartalmaz.

A logikai képletek egyes átalakításai hasonlóak a közönséges algebrai képletek transzformációihoz (véve közös szorzó zárójelek, kommutatív és asszociatív törvények használata stb.), míg más transzformációk olyan tulajdonságokon alapulnak, amelyekkel a közönséges algebrai műveletek nem rendelkeznek (eloszlási törvény használata konjunkcióra, abszorpciós, ragasztási, de Morgan törvényei stb.). ).

Nézzünk meg néhány példát a logikai képletek egyszerűsítéséhez használt technikákra és módszerekre:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2.

Az itt való átalakuláshoz alkalmazhatja az idempotencia törvényét, az elosztási törvényt; egy változó művelet inverzióval és egy állandó művelet.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Itt az egyszerűség kedvéért az abszorpció törvényét alkalmazzuk.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

Átalakításkor alkalmazzuk a de Morgan szabályt, a változó műveletét az inverzével, a műveletet konstanssal

Példák problémamegoldásra

1. példa Keressen egy logikai kifejezést, amely megfelel az A ∧ ¬(¬B ∨ C) kifejezésnek.

Megoldás. Alkalmazzuk de Morgan szabályát B-re és C-re: ¬(¬B ∨ C) = B ∧ ¬C .

Az eredetivel egyenértékű kifejezést kapunk: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Válasz: A ∧ B ∧ ¬C.

2. példa Adja meg azoknak az A, B, C logikai változóknak az értékét, amelyekre az (A ∨ B) → (B ∨ ¬C ∨ B) logikai kifejezés értéke hamis.

Megoldás. Az implikációs művelet csak akkor hamis, ha a hamis egy igaz premisszából. Ezért egy adott kifejezéshez az A ∨ B premisszának "igaz" értéket kell vennie, a következménynek, azaz a B ∨ ¬C ∨ B kifejezésnek pedig "false" értéket kell felvennie.

1) A ∨ B - a diszjunkció eredménye "igaz", ha legalább az egyik operandus "igaz";

2) B ∨ ¬C ∨ B - a kifejezés hamis, ha minden kifejezés "false" értékű, azaz B - "hamis"; ¬C "hamis", ezért a C változó értéke "igaz";

3) ha figyelembe vesszük a premisszát, és figyelembe vesszük, hogy B "hamis", akkor azt kapjuk, hogy A értéke "igaz".

Válasz: A igaz, B hamis, C igaz.

3. példa Mi az a legnagyobb X egész szám, amelyre az állítás (35

Megoldás.Írjuk fel az implikációs művelet igazságtáblázatát:

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

X kifejezés< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Válasz: X=5.

Logikai kifejezések használata geometriai régiók leírására

A logikai kifejezések használhatók geometriai régiók leírására. Ebben az esetben a probléma a következőképpen fogalmazódik meg: írjunk egy adott geometriai régióra egy olyan logikai kifejezést, amely akkor és csak akkor veszi fel az "igaz" értéket az x, y értékekre, ha bármely (x; y) koordinátájú pont tartozik hozzá. a geometriai tartományba.

Tekintsük egy geometriai régió leírását egy logikai kifejezés segítségével, példákon keresztül.

1. példa A geometriai terület képe be van állítva. Írjon egy logikai kifejezést, amely leírja a hozzá tartozó pontok halmazát!

1) .

Megoldás. Az adott geometriai tartomány a következő tartományok halmazaként ábrázolható: az első tartomány — D1 — félsík $(x)/(-1) +(y)/(1) ≤ 1$, a második — D2 — egy kör, amelynek középpontja az origó $x ^2 + y^2 ≤ 1$. D1 $∩$ D2 metszéspontjuk a kívánt tartomány.

Eredmény: logikai kifejezés $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Ez a terület a következőképpen írható fel: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1.

Jegyzet. A logikai kifejezés konstruálásakor nem szigorú egyenlőtlenségeket használunk, ami azt jelenti, hogy az ábrák határai is az árnyékolt területhez tartoznak. Ha szigorú egyenlőtlenségeket használ, akkor a határokat nem veszik figyelembe. Azok a határok, amelyek nem tartoznak egy régióhoz, általában szaggatott vonalként jelennek meg.

Megoldhatja az inverz problémát, nevezetesen: rajzoljon egy régiót egy adott logikai kifejezéshez.

2. példa Rajzolj és árnyékolj egy olyan területet, amelynek pontjai kielégítik az y ≥ x ∧ y + x ≥ 0 ∧ y logikai feltételt< 2 .

Megoldás. A kívánt terület három félsík metszéspontja. Az (x, y) síkra y = x egyeneseket építünk; y=-x; y = 2. Ezek a régió határai, és az utolsó y = 2 határ nem tartozik a régióhoz, ezért szaggatott vonallal húzzuk meg. Az y ≥ x egyenlőtlenség teljesítéséhez szükséges, hogy a pontok az y = x egyenestől balra legyenek, és az y = -x egyenlőtlenség teljesüljön az y = -x egyenestől jobbra eső pontokra. Feltétel y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Logikai függvények használata elektromos áramkörök leírására

A logikai függvények nagyon kényelmesek az elektromos áramkörök működésének leírására. Tehát az ábrán látható áramkör esetében, ahol az X változó értéke a kapcsoló állapota (ha be van kapcsolva, akkor X értéke "igaz", ha pedig ki van kapcsolva - "false"), ez Y értéke a villanykörte állapota (ha be van kapcsolva) - az érték "igaz", és ha nem - "false"), a logikai függvény a következőképpen íródik: Y = X . Az Y függvényt hívjuk vezetési funkció.

Az ábrán látható áramkörre az Y logikai függvény alakja: Y = X1 ∪ X2, mivel egy kapcsoló elég a villanykörte bekapcsolásához. ábra szerinti áramkörben ahhoz, hogy az izzó égjen, mindkét kapcsolót be kell kapcsolni, ezért a vezetőképesség függvény alakja: Y \u003d X1 ∧ X2.

Egy összetettebb áramkör esetén a vezetőképesség függvény a következőképpen néz ki: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

Az áramkör érintkezőket is tartalmazhat. Ebben az esetben a nyitott érintkező kapcsolóként biztosítja, hogy az izzó a gomb elengedésekor világítson, nem pedig megnyomva. Az ilyen áramköröknél a leválasztó kapcsolót negáció írja le.

A két sémát ún egyenértékű, ha az áram áthalad az egyiken, amikor áthalad a másikon. A két egyenértékű áramkör közül az az áramkör tekinthető egyszerűbbnek, amelynek vezetőképesség-függvénye kisebb számú elemet tartalmaz. A feladat megtalálni a legtöbbet egyszerű áramkörök az egyenértékek között nagyon fontos.

A logikai algebra apparátusának használata logikai áramkörök tervezésében

A logikai algebra matematikai apparátusa nagyon kényelmes a számítógép hardverei működésének leírására. A számítógépen feldolgozott bármely információ bináris formában van ábrázolva, azaz egy bizonyos 0 és 1 sorozattal kódolva. A 0-nak és 1-nek megfelelő bináris jelek feldolgozását a számítógépben logikai elemek végzik. Logikai kapuk, amelyek alapvető logikai műveleteket hajtanak végre ÉS, VAGY, NEM,ábrán mutatjuk be.

A logikai elemek szimbólumai szabványosak, és a számítógépes logikai áramkörök összeállításakor használatosak. Ezekkel az áramkörökkel bármilyen logikai függvényt megvalósíthat, amely leírja a számítógép működését.

Technikailag egy számítógépes logikai elem kerül megvalósításra az űrlapon elektromos áramkör, amely különféle alkatrészek összekötése: diódák, tranzisztorok, ellenállások, kondenzátorok. Egy logikai elem bemenete, amelyet kapunak is neveznek, nagy és alacsony feszültségű elektromos jeleket fogad, a kimenet egy kimeneti jelet kap, szintén vagy magas ill. alacsony szint. Ezek a szintek a bináris rendszer valamelyik állapotának felelnek meg: 1 - 0; IGAZ HAMIS. Minden logikai elemnek megvan a maga szimbóluma, amely kifejezi logikai funkcióját, de nem jelzi, hogy melyik elektronikus áramkör valósul meg benne. Ez megkönnyíti az összetett logikai áramkörök írását és megértését. A logikai áramkörök működését igazságtáblázatok segítségével írjuk le. A VAGY diagramon a szimbólum az "1" jel - a diszjunkció elavult jelöléséből ">=1" (a diszjunkció értéke 1, ha a két operandus összege nagyobb vagy egyenlő, mint 1). Az „&” jel az ÉS diagramban az angol és szó rövidített jelölése.

A logikai elemeket bonyolultabb logikai műveleteket végrehajtó elektronikus logikai áramkörök összeállítására szolgálnak. A NEM, VAGY, ÉS elemekből álló logikai elemek halmazát, amellyel tetszőleges bonyolultságú logikai struktúrát lehet felépíteni, az ún. funkcionálisan teljes.

Logikai kifejezések igazságtáblázatainak felépítése

Egy logikai képlethez mindig írhatsz igazságtáblázat, azaz táblázatos formában mutassa be az adott logikai függvényt. Ebben az esetben a táblázatnak mindent tartalmaznia kell lehetséges kombinációk függvényargumentumok (képletek) és a megfelelő függvényértékek (a képlet egy adott értékkészletből származik).

A függvényértékek keresésekor kényelmes jelölési forma egy táblázat, amely a változó értékeken és a függvényértékeken kívül a közbenső számítások értékeit is tartalmazza. Tekintsünk egy példát igazságtáblázat felépítésére a $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$ képlethez.

X1	X2	$(X1)↖(-)$	$(X1)↖(-)$ \ X2	X1 ∧ X2	$(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Ha egy függvény az összes változóérték-készletre 1-re értékel, akkor az ugyanúgy igaz; ha a függvény minden bemeneti értékkészletnél 0 értéket vesz fel, akkor az egyformán hamis; ha a kimeneti értékek halmaza 0-t és 1-et is tartalmaz, a függvény meghívásra kerül megvalósítható. A fenti példa egy azonosan igaz függvény példája.

A logikai függvény analitikus formájának ismeretében mindig át lehet lépni a logikai függvények táblázatos formájára. Egy adott igazságtáblázat segítségével megoldható az inverz probléma, nevezetesen: egy adott táblához készítsünk egy analitikai képletet egy logikai függvényhez. Egy logikai függvény analitikai függőségét táblázatosan megadott függvény alapján kétféleképpen állíthatjuk elő.

1. Disjunktív normál forma (DNF) a változókból és hamis értékekre vonatkozó tagadásaikból képzett szorzatok összege.

A DNF létrehozásának algoritmusa a következő:

1. az igazságtáblázatban a függvények olyan argumentumkészleteket választanak ki, amelyek logikai alakjai 1-gyel egyenlőek ("igaz");
2. minden kiválasztott logikai halmazt mint argumentumok logikai szorzatát úgy rögzítjük, hogy azokat egy logikai összeg (diszjunkció) műveletével szekvenciálisan összekapcsoljuk egymással;
3. a hamis argumentumok esetében egy negációs műveletet írunk le a megszerkesztett jelölésben.

Példa. Hozzon létre egy függvényt, amely meghatározza, hogy az első szám egyenlő-e a másodikkal, a DNF módszer segítségével. Egy függvény igazságtáblázatának alakja van

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Megoldás. Olyan argumentumérték-készleteket választunk ki, amelyekben a függvény 1-gyel egyenlő. Ezek a táblázat első és negyedik sorai (a fejléc sorát nem vesszük figyelembe a számozásnál).

Felírjuk ezeknek a halmazoknak az argumentumainak logikai szorzatait, összevonva azokat egy logikai összeggel: X1 ∧ X2 ∨ X1 ∧ X2 .

Felírjuk a kiválasztott halmazok hamis értékű argumentumainak tagadását (a táblázat negyedik sora; a képlet második halmaza; az első és második elem): X1 ∧ X2 ∨ $(X1)↖(- )$ ∧ $(X2)↖(-)$.

Válasz: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. Konjunktív normál forma (CNF) a változókból és azok tagadásaiból képzett összegek szorzata a valódi értékekre.

A CNF létrehozásának algoritmusa a következő:

1. az igazságtáblázatban olyan argumentumkészletek kerülnek kiválasztásra, amelyek logikai alakja 0 („hamis”);
2. az argumentumok logikai összegeként kiválasztott összes logikai halmaz szekvenciálisan íródik, összekapcsolva őket egymással egy logikai szorzat (konjunkció) műveletével;
3. az igaz argumentumok esetében a tagadási műveletet a felépített jelölésben rögzítjük.

Példák problémamegoldásra

1. példa Tekintsük az előző példát, azaz olyan függvényt készítünk, amely meghatározza, hogy az első szám egyenlő-e a másodikkal, a CNF módszer segítségével. Egy adott függvény igazságtáblázatának alakja van

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Megoldás. Olyan argumentumérték-készleteket választunk ki, amelyekben a függvény 0-val egyenlő. Ez a második és a harmadik sor (a fejléc sorát nem vesszük figyelembe a számozásnál).

Felírjuk ezeknek a halmazoknak az argumentumainak logikai összegét, kombinálva egy logikai szorzattal: X1 ∨ X2 ∧ X1 ∨ X2 .

Felírjuk a kiválasztott halmazok igaz értékű argumentumainak tagadását (a tábla második sora, a képlet első halmaza, a második elem; a harmadik sorra és ez a képlet második halmaza , az első elem): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Így egy logikai függvény rekordját kaptuk a CNF-ben.

Válasz: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

A két módszerrel kapott függvényértékek egyenértékűek. Ennek bizonyítására a logika szabályait használjuk: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖ (-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2) )↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. példa. Építsünk logikai függvényt egy adott igazságtáblázathoz:

Szükséges képlet: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

Leegyszerűsíthető: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

3. példa Az adott igazságtáblázathoz készítsünk egy logikai függvényt a DNF metódussal.

X1	X2	X3	F(X1, X2, X3)
1	1	1	1		X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1		$(X1)↖(-)$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $(X3)↖(-)$
1	0	0	1		X1 ∧ $(X2)↖(-)$ ∧ $(X3)↖(-)$
0	1	0	0
0	0	0	0

Szükséges képlet: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-)$ (X3)↖(-)$.

A képlet meglehetősen nehézkes, és egyszerűsíteni kell:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ $(X3) ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Igazságtáblázatok logikai problémák megoldásához

Az igazságtáblázatok összeállítása a logikai problémák megoldásának egyik módja. Ennek a megoldási módszernek a használatakor a probléma által tartalmazott feltételeket speciálisan összeállított táblázatokkal rögzítjük.

Példák problémamegoldásra

1. példa Készítsen igazságtáblázatot egy olyan biztonsági eszközhöz, amely három érzékelőt használ, és akkor aktiválódik, ha csak kettő zár be.

Megoldás. Nyilvánvalóan a megoldás eredménye egy táblázat lesz, amelyben a kívánt Y(X1, X2, X3) függvény igaz lesz, ha bármelyik két változó igaz.

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

2. példa Készítsen órarendet az adott napra, tekintettel arra, hogy az informatika óra csak az első vagy a második, a matematika óra az első vagy a harmadik, a fizika óra a második vagy a harmadik lehet. Lehet-e olyan ütemtervet készíteni, amely minden igényt kielégít? Hány menetrendi lehetőség van?

Megoldás. A probléma könnyen megoldható, ha elkészíti a megfelelő táblázatot:

	1. lecke	2. lecke	3. lecke
Számítástechnika	1	1	0
Matematika	1	0	1
Fizika	0	1	1

A táblázat azt mutatja, hogy két lehetőség van a kívánt ütemezéshez:

1. matematika, informatika, fizika;
2. számítástechnika, fizika, matematika.

3. példa Három barát érkezett a sporttáborba - Péter, Borisz és Alekszej. Mindegyikük két sportágat szeret. Ismeretes, hogy hat ilyen sportág van: futball, jégkorong, síelés, úszás, tenisz, tollaslabda. Az is ismert, hogy:

1. Boris a legidősebb;
2. futballozni fiatalabb, mint jégkorongozni;
3. focizik és jégkorongoznak, Péter pedig ugyanabban a házban lakik;
4. amikor veszekedés támad egy síelő és egy teniszező között, Boris kibékíti őket;
5. Péter nem tud teniszezni vagy tollaslabdázni.

Milyen sportokat űznek a fiúk?

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

Mivel hat sportág van, kiderült, hogy minden fiú szereti különböző típusok sport.

A 4. feltételből az következik, hogy Boris nem szeret síelni vagy teniszezni, a 3. és 5. feltételből pedig az következik, hogy Péter nem tud focizni, jégkorongozni, teniszezni és tollaslabdázni. Következésképpen Péter kedvenc sportja a síelés és az úszás. Tegyük fel a táblázatba, és töltsük ki nullákkal a "Síelés" és az "Úszás" oszlopok többi celláját.

A táblázat azt mutatja, hogy csak Alekszej tud teniszezni.

Az 1. és 2. feltétel azt jelenti, hogy Boris nem futballista. Így Alekszej focizik. Folytassuk a táblázat kitöltését. Írjunk be nullákat az "Alexey" sor üres celláiba.

Végre megtudjuk, hogy Boris szereti a jégkorongot és a tollaslabdát. A döntő asztal így fog kinézni:

Válasz: Petr szeret síelni és úszni, Borisz hokizik és tollaslabdázik, Alexey pedig focizik és teniszez.