Noskin Andrej Nikolajevič,
IT-učiteľ
najvyššia kvalifikačná kategória,
Kandidát vojenských vied, docent
Lýceum GBOU č. 1575, Moskva

Optimalizovaná metóda mapovania na riešenie úlohy 23 z Jednotnej štátnej skúšky KIM z informatiky a IKT

Jednou z najťažších úloh v rámci Unified State Exam KIM je problém 23, v ktorom musíte nájsť počet rôznych množín hodnôt logických premenných, ktoré spĺňajú zadanú podmienku.
Táto úloha je možno najťažšou úlohou jednotnej štátnej skúšky KIM z informatiky a IKT. Spravidla sa s ňou nevyrovná viac ako 5 % skúšaných (1).
Takéto malé percento študentov, ktorí dokončili túto úlohu, sa vysvetľuje takto:
- žiaci si môžu pomýliť (zabudnúť) znaky logických operácií;
- matematické chyby v procese vykonávania výpočtov;
- chyby v uvažovaní pri hľadaní riešenia;
- chyby v procese zjednodušovania logických výrazov;
- učitelia odporúčajú vyriešiť tento problém po dokončení všetkých prác, pretože pravdepodobnosť
chyby sú veľmi veľké a „váha“ úlohy je len jedným primárnym bodom.
Navyše niektorí učitelia sami majú problém riešiť tento typ problémov, a preto sa snažia s deťmi riešiť jednoduchšie problémy.
Situáciu komplikuje aj to, že v tomto bloku je veľké množstvo rôznych úloh a nie je možné zvoliť žiadne šablónové riešenie.
Na nápravu tohto stavu pedagogická obec finalizuje hlavné dve metódy riešenia problémov tohto typu: riešenie pomocou bitových reťazcov (2) a metódu mapovania (3).
Potreba spresniť (optimalizovať) tieto metódy je daná tým, že úlohy sa neustále menia ako v štruktúre, tak aj v počte premenných (len jeden typ premenných X, dva typy premenných X a Y, tri typy: X, Y , Z).
Náročnosť zvládnutia týchto metód na riešenie problémov potvrdzuje skutočnosť, že na webovej stránke K.Yu. Polyakov, existuje 38 analýz tohto typu problému (4). Niektoré analýzy poskytujú viac ako jeden typ riešenia problému.
Nedávno sa v rámci KIM Unified State Examination v informatike vyskytli problémy s dvoma typmi premenných X a Y.
Optimalizoval som metódu zobrazovania a povzbudzujem svojich študentov, aby používali vylepšenú metódu.
To dáva výsledky. Percento mojich študentov, ktorí sa s touto úlohou vyrovnajú, sa líši až u 43 % tých, ktorí prešli. Jednotnú štátnu skúšku z informatiky absolvuje spravidla každý rok 25 až 33 ľudí zo všetkých 11. ročníkov.
Pred objavením sa problémov s dvoma typmi premenných študenti veľmi úspešne používali metódu mapovania, ale po objavení sa Y v logickom vyjadrení som si začal všímať, že odpovede detí sa už nezhodujú s testami. Ukázalo sa, že nemajú celkom jasno v tom, ako vytvoriť tabuľku mapovaní s novým typom premennej. Potom mi napadlo, že pre pohodlie by sa mal celý výraz zredukovať na jeden typ premennej, ako je to vhodné pre deti.
Túto metódu uvediem podrobnejšie. Pre pohodlie to zvážim na príklade systému logických výrazov uvedených v (4).
Koľko rôznych riešení má systém logických rovníc?

(x 1 ^ y 1)=(¬x 2 V ¬ r 2 )
(x 2 ^ y 2)= (¬ X 3 V ¬ r 3 )
...
(x 5 ^ y 5) = (¬ X 6 V ¬ r 6 )

KdeX 1 , …, X 6 , r 1 , …, r 6 , - logické premenné? Odpoveď nemusí uvádzať všetky rôzne sady hodnôt premenných, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie:
1. Z rozboru sústavy logických rovníc vidíme, že existuje 6 premenných X a 6 premenných U. Keďže ktorákoľvek z týchto premenných môže mať iba dve hodnoty (0 a 1), nahradíme tieto premenné 12 premennými rovnakého typu, napríklad Z.
2. Teraz prepíšme systém novými premennými rovnakého typu. Náročnosť úlohy bude v robení si starostlivých poznámok pri nahrádzaní premenných.

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

3. Zostavme si tabuľku, v ktorej si prejdeme všetky možnosti z 1 , z 2 , z 3 , z 4 , keďže v prvej logickej rovnici sú štyri premenné, tabuľka bude mať 16 riadkov (16=2 4); odstráňte takéto hodnoty z tabuľky z 4 , pre ktorú prvá rovnica nemá riešenie (prečiarknuté čísla).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Analýzou tabuľky vytvoríme pravidlo pre zobrazenie párov premenných (napríklad pár Z 1 Z 2 =00 zodpovedá pár Z 3 Z 4 = 11) .

5. Vyplňte tabuľku spočítaním počtu párov premenných, pre ktoré má systém riešenie.

6. Spočítajte všetky výsledky: 9 + 9 + 9 + 27 = 54
7. odpoveď: 54.
Vyššie optimalizovaná metóda na riešenie úlohy 23 z Jednotnej štátnej skúšky KIM umožnila študentom znovu získať sebadôveru a úspešne vyriešiť tento typ problémov.

Literatúra:

1. FIPI. Metodické odporúčania pre učiteľov, vypracované na základe analýzy typických chýb účastníkov Jednotnej štátnej skúšky 2015 z INFORMAČNÝCH VEDENÍ a IKT. Režim prístupu: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. K.Yu. Polyakov, M.A. Roitberg.Systémy logických rovníc: riešenie pomocou bitových reťazcov. Časopis informatiky, č. 12, 2014, s. 4-12. Vydavateľstvo "Prvý september", Moskva.
3. E.A. Mironchik, Spôsob zobrazenia.Časopis Informatika, číslo 10, 2013, s. 18-26. Vydavateľstvo "Prvý september", Moskva.

Riešenie sústav logických rovníc zmenou premenných

Metóda substitúcie premenných sa používa, ak sú niektoré premenné zahrnuté do rovníc iba vo forme konkrétneho výrazu a nič iného. Potom môže byť tento výraz označený novou premennou.

Príklad 1

Koľko rôznych množín hodnôt logických premenných x1, x2, x3, x4, x5, x6, x7, x8 existuje, ktoré spĺňajú všetky podmienky uvedené nižšie?

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt premenných x1, x2, x3, x4, x5, x6, x7, x8, pre ktoré je tento systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie:

(x1 -> x2) = y1; (x3 -> x4) = y2; (x5 -> x6) = y3; (x7 → x8) = y4.

Potom môžeme systém napísať vo forme jedinej rovnice:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunkcia je 1 (pravda), keď každý operand nadobúda hodnotu 1. To znamená každá z implikácií musí byť pravdivá, a to platí pre všetky hodnoty okrem (1 → 0). Tie. v tabuľke hodnôt premenných y1, y2, y3, y4 by jedna nemala byť naľavo od nuly:

Tie. podmienky sú splnené pre 5 sád y1-y4.

Pretože y1 = x1 → x2, potom sa hodnota y1 = 0 dosiahne na jednej množine x1, x2: (1, 0) a hodnota y1 = 1 – na troch množinách x1, x2: (0,0) , (0 ,1), (1.1). Podobne pre y2, y3, y4.

Keďže každá množina (x1,x2) pre premennú y1 je kombinovaná s každou množinou (x3,x4) pre premennú y2 atď., počet množín premenných x sa vynásobí:

				Počet sád na x1…x8

Spočítajme počet sád: 1 + 3 + 9 + 27 + 81 = 121.

odpoveď: 121

Príklad 2

Koľko rôznych množín hodnôt logických premenných x1, x2, ... x9, y1, y2, ... y9 existuje, ktoré spĺňajú všetky podmienky uvedené nižšie?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

V odozve netreba uveďte všetky rôzne množiny hodnôt premenných x1, x2, ... x9, y1, y2, ... y9, pre ktoré je daný systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie:

Urobme zmenu premenných:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Systém možno zapísať ako jednu rovnicu:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Ekvivalencia je pravdivá iba vtedy, ak sú oba operandy rovnaké. Existujú dve sady riešení tejto rovnice:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Pretože zi = (xi ≡ yi), potom hodnota zi = 0 zodpovedá dvom množinám (xi,yi): (0,1) a (1,0) a hodnota zi = 1 zodpovedá dvom množinám (xi,yi ): (0,0) a (1,1).

Potom prvej množine z1, z2,…, z9 zodpovedá 2 9 množín (x1,y1), (x2,y2),…, (x9,y9).

Rovnaké číslo zodpovedá druhej množine z1, z2,…, z9. Potom je spolu 2 9 + 2 9 = 1024 sád.

odpoveď: 1024

Riešenie sústav logických rovníc metódou vizuálneho určenia rekurzie.

Táto metóda sa používa, ak je sústava rovníc celkom jednoduchá a poradie zvyšovania počtu množín pri pridávaní premenných je zrejmé.

Príklad 3

Koľko rôznych riešení má sústava rovníc?

¬x9 ∨ x10 = 1,

kde x1, x2, … x10 sú logické premenné?

Odpoveď nemusí uvádzať všetky rôzne sady hodnôt x1, x2, ... x10, pre ktoré je tento systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie:

Poďme vyriešiť prvú rovnicu. Disjunkcia sa rovná 1, ak sa aspoň jeden z jej operandov rovná 1. To znamená Riešením sú sady:

Pre x1=0 existujú dve hodnoty x2 (0 a 1) a pre x1=1 je len jedna hodnota x2 (1), takže množina (x1,x2) je riešením rovnice. Celkovo sú 3 sady.

Pridajme premennú x3 a zvážme druhú rovnicu. Je podobný prvému, čo znamená, že pre x2=0 existujú dve hodnoty x3 (0 a 1) a pre x2=1 je len jedna hodnota x3 (1), takže množina (x2 ,x3) je riešením rovnice. Celkovo sú 4 sady.

Je ľahké vidieť, že pri pridávaní ďalšej premennej sa pridáva jedna množina. Tie. rekurzívny vzorec pre počet množín (i+1) premenných:

N i +1 = N i + 1. Potom pre desať premenných dostaneme 11 množín.

odpoveď: 11

Riešenie sústav logických rovníc rôznych typov

Príklad 4.

Koľko rôznych množín hodnôt logických premenných x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 existuje, ktoré spĺňajú všetky nižšie uvedené podmienky ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

V odozve netreba uveďte všetky rôzne množiny hodnôt premenných x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, pre ktoré je tento systém rovnosti splnený.

Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie:

Všimnite si, že tri rovnice systému sú rovnaké na rôznych nezávislých súboroch premenných.

Pozrime sa na prvú rovnicu. Spojka je pravdivá (rovná sa 1) iba vtedy, ak sú všetky jej operandy pravdivé (rovná sa 1). Dôsledok je 1 pre všetky n-tice okrem (1,0). To znamená, že riešením prvej rovnice budú nasledujúce množiny x1, x2, x3, x4, v ktorých 1 nie je umiestnená naľavo od 0 (5 množín):

Podobne riešenia druhej a tretej rovnice budú úplne rovnaké množiny y1,…,y4 a z1,…, z4.

Teraz rozoberme štvrtú rovnicu sústavy: x 4 ∧ y 4 ∧ z 4 = 0. Riešením budú všetky množiny x4, y4, z4, v ktorých sa aspoň jedna z premenných rovná 0.

Tie. pre x4 = 0 sú vhodné všetky možné množiny (y4, z4) a pre x4 = 1 sú vhodné množiny (y4, z4), v ktorých je aspoň jedna nula: (0, 0), (0,1 ), (1, 0).

				Počet súprav

Celkový počet sád je 25 + 4*9 = 25 + 36 = 61.

odpoveď: 61

Riešenie sústav logických rovníc konštrukciou opakujúcich sa vzorcov

Metóda konštrukcie opakujúcich sa vzorcov sa používa pri riešení zložitých systémov, v ktorých nie je zrejmé poradie zvyšovania počtu množín a konštrukcia stromu je nemožná kvôli objemom.

Príklad 5.

Koľko rôznych množín hodnôt logických premenných x1, x2, ... x7, y1, y2, ... y7 existuje, ktoré spĺňajú všetky nižšie uvedené podmienky?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt premenných x1, x2, ..., x7, y1, y2, ..., y7, pre ktoré je tento systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie:

Všimnite si, že prvých šesť rovníc systému je identických a líšia sa iba množinou premenných. Pozrime sa na prvú rovnicu. Jeho riešením budú nasledujúce množiny premenných:

Označme:

počet n-tic (0,0) na premenných (x1,y1) až A 1,

počet n-tic (0,1) na premenných (x1,y1) až B 1,

počet n-tic (1,0) na premenných (x1,y1) až C 1,

počet n-tic (1,1) na premenných (x1,y1) až D 1 .

počet n-tic (0,0) na premenných (x2,y2) až A2,

počet n-tic (0,1) na premenných (x2,y2) až B 2,

počet n-tic (1,0) na premenných (x2,y2) až C 2,

počet n-tic (1,1) na premenných (x2,y2) až D2.

Z rozhodovacieho stromu to vidíme

A1 = 0, B1 = 1, C1 = 1, D1 = 1.

Všimnite si, že množina (0,0) o premenných (x2,y2) je získaná z množín (0,1), (1,0) a (1,1) o premenných (x1,y1). Tie. A2=Bi+Ci+Di.

Množinu (0,1) o premenných (x2,y2) získame z množín (0,1), (1,0) a (1,1) o premenných (x1,y1). Tie. B2=Bi+Ci+Di.

Argumentujúc podobne si všimneme, že C2=B1+C1+D1. D2 = D1.

Takto získame opakujúce sa vzorce:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

Cj+i = Bj + Cj + Di

Di+1 = A i + B i + C i + D i

Urobme si stôl

Súpravy	Označenie.	Vzorec	Počet súprav
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 = B i + C i + D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 = B i + C i + D i	1	3	7	15	31	63	127
(1,0)	C i	Cj+1=Bi+Ci+Di	1	3	7	15	31	63	127
(1,1)	D i	Di+1 =Di	1	1	1	1	1	1	1

Poslednú rovnicu (x7 ∨ y7) = 1 spĺňajú všetky množiny okrem tých, v ktorých x7=0 a y7=0. V našej tabuľke je počet takýchto súborov A 7.

Potom je celkový počet sád B 7 + C 7 + D 7 = 127+127+1 = 255

odpoveď: 255

Metódy riešenia sústav logických rovníc

Kirgizová E.V., Nemková A.E.

Pedagogický inštitút Lesosibirsk –

pobočka Sibírskej federálnej univerzity v Rusku

Schopnosť dôsledne myslieť, presvedčivo uvažovať, vytvárať hypotézy a vyvracať negatívne závery neprichádza sama od seba, táto zručnosť sa nevyvíja v logike. Logika je veda, ktorá študuje metódy stanovenia pravdivosti alebo nepravdivosti niektorých tvrdení na základe pravdivosti alebo nepravdivosti iných tvrdení.

Zvládnutie základov tejto vedy je nemožné bez riešenia logických problémov. Testovanie rozvoja zručností na uplatnenie svojich vedomostí v novej situácii sa uskutočňuje prostredníctvom absolvovania. Ide najmä o schopnosť riešiť logické problémy. Úlohy B15 v Jednotnej štátnej skúške sú úlohy so zvýšenou zložitosťou, pretože obsahujú systémy logických rovníc. Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, zostavenie pravdivostnej tabuľky, rozklad, sekvenčné riešenie rovníc atď.

Úloha:Vyriešte sústavu logických rovníc:

Uvažujme redukčná metóda na jednu rovnicu . Táto metóda zahŕňa transformáciu logických rovníc tak, aby sa ich pravá strana rovnala pravdivostnej hodnote (tj 1). Na tento účel použite operáciu logickej negácie. Potom, ak rovnice obsahujú zložité logické operácie, nahradíme ich základnými: „A“, „ALEBO“, „NIE“. Ďalším krokom je spojenie rovníc do jednej, ekvivalentnej systému, pomocou logickej operácie „AND“. Potom by ste mali transformovať výslednú rovnicu na základe zákonov logickej algebry a získať konkrétne riešenie systému.

Riešenie 1:Použite inverziu na obe strany prvej rovnice:

Predstavme si implikáciu prostredníctvom základných operácií „ALEBO“ a „NIE“:

Keďže ľavé strany rovníc sú rovné 1, môžeme ich spojiť pomocou operácie „AND“ do jednej rovnice, ktorá je ekvivalentná pôvodnému systému:

Otvoríme prvú zátvorku podľa De Morganovho zákona a transformujeme získaný výsledok:

Výsledná rovnica má jedno riešenie: A= 0, B = 0 a C = 1.

Ďalšia metóda je vytváranie pravdivostných tabuliek . Keďže logické veličiny majú len dve hodnoty, môžete jednoducho prejsť všetky možnosti a nájsť medzi nimi tie, pre ktoré daný systém rovníc vyhovuje. To znamená, že zostavíme jednu spoločnú pravdivostnú tabuľku pre všetky rovnice systému a nájdeme riadok s požadovanými hodnotami.

Riešenie 2:Vytvorme pravdivostnú tabuľku pre systém:

0	0	1	1	0	1

Riadok, pre ktorý sú splnené podmienky úlohy, je zvýraznený tučným písmom. Takže A = 0, B = 0 a C = 1.

spôsob rozklad . Cieľom je zafixovať hodnotu jednej z premenných (nastaviť ju na 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.

Riešenie 3: Nechaj A = 0, potom:

Z prvej rovnice dostaneme B =0 a od druhého – C=1. Riešenie sústavy: A = 0, B = 0 a C = 1.

Môžete tiež použiť metódu sekvenčné riešenie rovníc v každom kroku pridanie jednej premennej do uvažovanej množiny. Na to je potrebné transformovať rovnice tak, aby sa premenné zadávali v abecednom poradí. Ďalej vytvoríme rozhodovací strom, do ktorého postupne pridávame premenné.

Prvá rovnica systému závisí iba od A a B a druhá rovnica od A a C. Premenná A môže mať 2 hodnoty 0 a 1:

Z prvej rovnice to vyplýva , takže keď A = 0 a dostaneme B = 0 a pre A = 1 máme B = 1. Prvá rovnica má teda dve riešenia vzhľadom na premenné A a B.

Ukážme si druhú rovnicu, z ktorej určíme hodnoty C pre každú možnosť. Keď A = 1, implikácia nemôže byť nepravdivá, to znamená, že druhá vetva stromu nemá riešenie. O A= 0 dostaneme jediné riešenie C= 1 :

Takto sme dostali riešenie sústavy: A = 0, B = 0 a C = 1.

Pri Jednotnej štátnej skúške z informatiky je veľmi často potrebné určiť počet riešení sústavy logických rovníc, pričom na to existujú aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, je nahradenie premenných. Najprv musíte každú z rovníc čo najviac zjednodušiť na základe zákonov logickej algebry a potom nahradiť zložité časti rovníc novými premennými a určiť počet riešení nového systému. Potom sa vráťte k náhrade a určite počet riešení pre ňu.

Úloha:Koľko riešení má rovnica ( A → B) + (C → D ) = 1? Kde A, B, C, D sú logické premenné.

Riešenie:Predstavme si nové premenné: X = A → B a Y = C → D . S prihliadnutím na nové premenné bude rovnica napísaná takto: X + Y = 1.

Disjunkcia je pravdivá v troch prípadoch: (0;1), (1;0) a (1;1), zatiaľ čo X a Y je implikácia, to znamená, že v troch prípadoch je pravdivá a v jednom nepravdivá. Preto prípad (0;1) bude zodpovedať trom možným kombináciám parametrov. Prípad (1;1) – bude zodpovedať deviatim možným kombináciám parametrov pôvodnej rovnice. To znamená, že celkové možné riešenia tejto rovnice sú 3+9=15.

Ďalším spôsobom, ako určiť počet riešení systému logických rovníc, je binárny strom. Pozrime sa na túto metódu pomocou príkladu.

Úloha:Koľko rôznych riešení má systém logických rovníc:

Daný systém rovníc je ekvivalentný rovnici:

( X 1 → X 2 )*( X 2 → X 3 )*…*( x m -1 → x m) = 1.

Predstierajme toX 1 – je pravda, potom to z prvej rovnice dostanemeX 2 tiež pravda, od druhého -X 3 =1, a tak ďalej, kým x m= 1. Takže množina (1; 1; …; 1) z m jednotiek je riešením systému. Nechaj to terazX 1 =0, potom z prvej rovnice mámeX 2 =0 alebo X 2 =1.

Kedy X 2 true, získame, že zostávajúce premenné sú tiež pravdivé, to znamená, že množina (0; 1; ...; 1) je riešením systému. OX 2 =0 chápeme to X 3 =0 alebo X 3 = a tak ďalej. Pokračovaním k poslednej premennej zistíme, že riešením rovnice sú nasledujúce množiny premenných ( m +1 riešenie v každom riešení m premenné hodnoty):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Tento prístup je dobre ilustrovaný zostrojením binárneho stromu. Počet možných riešení je počet rôznych vetiev zostrojeného stromu. Je ľahké vidieť, že je to rovnaké m + 1.

Premenné	Strom	Počet riešení
x 1
x 2
x 3

V prípade ťažkostí pri uvažovaní a zostavovaní rozhodovacieho stromu môžete hľadať riešenie pomocou pravdivostné tabuľky, pre jednu alebo dve rovnice.

Prepíšme sústavu rovníc do tvaru:

A vytvorte pravdivostnú tabuľku samostatne pre jednu rovnicu:

x 1	x 2	(x 1 → x 2)

Vytvorme pravdivostnú tabuľku pre dve rovnice:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Ďalej môžete vidieť, že jedna rovnica platí v nasledujúcich troch prípadoch: (0; 0), (0; 1), (1; 1). Systém dvoch rovníc platí v štyroch prípadoch (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). V tomto prípade je hneď jasné, že existuje riešenie pozostávajúce len z núl a viac m riešenia, v ktorých sa pridáva jedna jednotka naraz, začínajúc od poslednej pozície, kým sa nezaplnia všetky možné miesta. Dá sa predpokladať, že všeobecné riešenie bude mať rovnakú formu, ale aby sa takýto prístup stal riešením, je potrebný dôkaz o správnosti predpokladu.

Aby som zhrnul všetky vyššie uvedené, rád by som upriamil vašu pozornosť na skutočnosť, že nie všetky diskutované metódy sú univerzálne. Pri riešení každého systému logických rovníc je potrebné vziať do úvahy jeho vlastnosti, na základe ktorých by sa mala zvoliť metóda riešenia.

Literatúra:

1. Logické problémy / O.B. Bogomolov – 2. vyd. – M.: BINOM. Laboratórium vedomostí, 2006. – 271 s.: ill.

2. Polyakov K.Yu. Systémy logických rovníc / Náučné a metodické noviny pre učiteľov informatiky: Informatika č.14,2011.

Koncom roka sa ukázalo, že len jeden z troch predpokladov bol pravdivý. Ktoré divízie dosiahli na konci roka zisk?

Riešenie. Predpoklady z problémových podmienok si zapíšme formou logických tvrdení: „Poberanie zisku delením B nie je nevyhnutnou podmienkou získania

zisk delením A ":F 1 (A, B, C) = A → B

„Získanie zisku z aspoň jednej divízie B a C nestačí na to, aby divízia A dosiahla zisk“: F 2 (A, B, C) = (B + C) → A

„Divízie A a B nebudú dosahovať zisk súčasne“: F 3 (A, B, C) = A B

Z podmienky je známe, že iba jeden z troch predpokladov je pravdivý. To znamená, že musíme nájsť, ktorý z nasledujúcich troch logických výrazov nie je rovnako nepravdivý:

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (A→B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A → B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Následne sa na konci roka ukázal ako pravdivý druhý predpoklad a prvý a tretí nepravdivý.

									A = 0
	F1 F2 F3 = A B C = 1
									vtedy a len vtedy, ak B = 0.
									C = 1

Preto divízia C získa zisk, ale divízie A a B zisk nedostanú.

Riešenie logických rovníc

V textoch štátneho centralizovaného testovania je úloha (A8), ktorá žiada nájsť koreň logickej rovnice. Pozrime sa na spôsoby riešenia takýchto úloh pomocou príkladu.

Nájdite koreň logickej rovnice: (A + B) (X AB) = B + X → A.

Prvým riešením je zostaviť pravdivostnú tabuľku. Poďme zostaviť pravdivostné tabuľky pre pravú a ľavú stranu rovnice a uvidíme, pri akom X sa zhodujú hodnoty v posledných stĺpcoch týchto tabuliek.

F1 (A, B, X) = (A+ B) (X AB)

					A+B	(A+ B)(X AB)	F 1 (A, B, X)

F2 (A, B, X) = B+ X → A

			X → A							F 2 (A, B, X)
					X → A			X → A

Porovnajme výsledné pravdivostné tabuľky a vyberte tie riadky, v ktorých sa hodnoty F 1 (A, B, X) a F 2 (A, B, X) zhodujú.

			F 1 (A, B, X)	F 2 (A, B, X)

Prepíšme len vybrané riadky, ponechajme len stĺpce argumentov. Pozrime sa na premennú X ako funkciu A a B.

Je zrejmé, že X = B → A.

Druhým riešením je nahradiť znamienko rovnosti v rovnici znamienkom ekvivalentu a následne zjednodušiť výslednú logickú rovnicu.

Na uľahčenie ďalšej práce si najprv zjednodušíme pravú a ľavú stranu logickej rovnice a nájdime ich negácie:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Nahraďte znamienko rovnosti v našej logickej rovnici znamienkom ekvivalencie:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B + X A B + X A B) (B + X A) =

= (X A B + X B + X A B) + (X A B + X A B) =

Preusporiadame logické pojmy tohto výrazu, pričom faktory X a X vyjmeme zo zátvoriek.

X(AB) + X(B+ AB) = X(AB) + X(B+ A) =

Označme teda T = A B

X T+ X T= X↔ T.

Preto, aby logická rovnica mala riešenie: X = A B = B + A = B → A.

Logické prvky počítača. Konštrukcia funkčných schém

S rozvojom výpočtovej techniky sa ukázalo, že matematická logika úzko súvisí s otázkami návrhu a programovania výpočtovej techniky. Algebra logiky našla široké uplatnenie spočiatku vo vývoji reléový kontakt schém Prvý základný výskum, ktorý upriamil pozornosť inžinierov zapojených do počítačového dizajnu na možnosť analyzovať elektrické obvody pomocou Booleovej algebry, publikoval v decembri 1938 Američan Claude Shannon, „Symbolic Analysis of Ladder Circuits“. Po tomto článku sa počítačový dizajn nezaobišiel bez použitia booleovskej algebry.

Logický prvok je obvod, ktorý implementuje logické operácie disjunkcie, konjunkcie a inverzie. Uvažujme o implementácii logických prvkov prostredníctvom elektrických reléových kontaktných obvodov, ktoré sú vám známe zo školského kurzu fyziky.

Sériové pripojenie kontaktov

Paralelné pripojenie kontaktov

Zostavme si tabuľku závislostí stavu obvodov na všetkých možných stavoch kontaktov. Uveďme si nasledovné označenia: 1 – kontakt je zopnutý, v obvode je prúd; 0 – kontakt je otvorený, v obvode nie je prúd.

		Stav obvodu	Stav obvodu s paralelou
		sériové pripojenie	spojenie

Ako vidíte, obvod so sériovým pripojením zodpovedá logickej operácii spojenia, pretože prúd v obvode sa objaví iba vtedy, keď sú kontakty A a B súčasne zatvorené. Obvod s paralelným pripojením zodpovedá logickému fungovaniu disjunkcie, pretože v obvode nie je žiadny prúd iba v okamihu, keď sú oba kontakty otvorené.

Logická prevádzka inverzie sa realizuje prostredníctvom kontaktného obvodu elektromagnetického relé, ktorého princíp sa študuje v školskom kurze fyziky. Kontakt x je otvorený, keď je x zatvorený a naopak.

Použitie reléových kontaktných prvkov na konštrukciu logických obvodov počítačov sa neosvedčilo z dôvodu nízkej spoľahlivosti, veľkých rozmerov, vysokej spotreby energie a nízkeho výkonu. Nástup elektronických zariadení (vákuových a polovodičových) vytvoril možnosť konštrukcie logických prvkov s rýchlosťou 1 milión prepnutí za sekundu a vyššou. Polovodičové logické prvky pracujú v spínacom režime podobne ako elektromagnetické relé. Celá teória prezentovaná pre kontaktné obvody je prenesená na polovodičové prvky. Logické prvky na polovodičoch nie sú charakterizované stavom kontaktov, ale prítomnosťou signálov na vstupe a výstupe.

Zoberme si logické prvky, ktoré implementujú základné logické operácie:

Invertor - implementuje operáciu negácie alebo inverzie. U

menič má jeden vstup a jeden výstup. Zobrazí sa výstupný signál

keď na vstupe nie je žiadny a naopak.

Spojka -

X1 X2 ... Xn

implementuje operáciu spojenia.

U spojky

jeden výstup a aspoň dva vstupy. Signál zapnutý

sa objaví vo výstupe vtedy a len vtedy

všetky vstupy sú signalizované.

X2 + ... Xn

Disjunktor - implementuje operáciu disjunkcie. U

disjunktor má jeden východ a aspoň dva

Výstupný signál sa neobjaví vtedy a len vtedy

keď do všetkých vstupov neprichádzajú žiadne signály.

	Stavať	funkčné
F(X, Y, Z) = X(Y+ Z)
			X + Z

diagram zodpovedajúci funkcii:

&F(X, Y, Z)

Riešenie problémov pomocou konjunktívneho normálu

A disjunktívny-normálny formulárov

IN Knihy logických problémov často obsahujú štandardné problémy, kde potrebujete napísať funkciu, ktorá ich implementuje rebríkový diagram, zjednodušte ho a zostrojte pravdivostnú tabuľku pre túto funkciu. Ako vyriešiť inverzný problém? Vzhľadom na ľubovoľnú pravdivostnú tabuľku musíte zostaviť funkčný alebo reléový diagram. Touto problematikou sa dnes budeme zaoberať.

Akákoľvek funkcia logickej algebry môže byť reprezentovaná kombináciou troch operácií: konjunkcie, disjunkcie a inverzie. Poďme zistiť, ako sa to robí. Aby sme to dosiahli, napíšme si niekoľko definícií.

Minterm je funkcia vytvorená spojením určitého počtu premenných alebo ich negácií. Minterm má hodnotu 1 pre jedinú zo všetkých možných množín

argumenty a hodnota je 0 pre všetky ostatné. Príklad: x 1 x 2 x 3 x 4 .

Maxterm je funkcia vytvorená disjunkciou určitého počtu premenných alebo ich negáciami. Maxterm má hodnotu 0 v jednej z možných množín a 1 vo všetkých ostatných.

Príklad: x 1 + x 2 + x 3.

Funkcia v disjunktívna normálna forma(DNF) je logický súčet mintermov.

Príklad: x 1x 2+ x 1x 2+ x 1x 2x 3.

Konjunktívna normálna forma(CNF) je logickým produktom elementárnych disjunkcií (maxterms).

Príklad: (x 1+ x 2+ x 3) (x 1+ x 2) .

Dokonalá disjunktívna normálna forma sa nazýva DNF, v každom minterme sú prítomné všetky premenné alebo ich negácie.

Príklad: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Dokonalá konjunktívna normálna forma sa nazýva CNF, v každom maxterme ktorého sú prítomné všetky premenné alebo ich negácie.

Príklad: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Zápis logickej funkcie z tabuľky

Akákoľvek logická funkcia môže byť vyjadrená ako SDNF alebo SCNF. Ako príklad uvažujme funkciu f uvedenú v tabuľke.

			f(x1 , x2 , x3 )

Funkcie G0, G1, G4, G5, G7 sú mintermy (pozri definíciu). Každá z týchto funkcií je súčinom troch premenných alebo ich inverzných hodnôt a má hodnotu 1 iba v jednej situácii. Je vidieť, že na získanie 1 v hodnote funkcie f je potrebný jeden minterm. Preto sa počet mintermov, ktoré tvoria SDNF tejto funkcie, rovná počtu jednotiek v hodnote funkcie: f= G0+G1+G4+G5+G7. SDNF má teda tvar:

f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.

Podobne môžete postaviť SKNF. Počet faktorov sa rovná počtu núl vo funkčných hodnotách:

f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

Každá logická funkcia zadaná vo forme tabuľky môže byť teda napísaná ako vzorec.

Algoritmus na konštrukciu SDNF pomocou pravdivostnej tabuľky

Je uvedená pravdivostná tabuľka nejakej funkcie. Ak chcete vytvoriť SDNF, musíte vykonať nasledujúcu postupnosť krokov:

1. Vyberte všetky riadky tabuľky, v ktorých má funkcia hodnotu 1.

2. Ku každému takémuto riadku priraďte spojenie všetkých argumentov alebo ich inverzie (minterm). V tomto prípade je argument s hodnotou 0 zahrnutý do minterm s negáciou a hodnota 1 je zahrnutá bez negácie.

3. Nakoniec vytvoríme disjunkciu všetkých získaných mintermov. Počet mintermov sa musí zhodovať s počtom jednotiek logickej funkcie.

Algoritmus na konštrukciu SCNF pomocou pravdivostnej tabuľky

Je uvedená pravdivostná tabuľka nejakej funkcie. Ak chcete zostaviť SKNF, musíte vykonať nasledujúcu postupnosť krokov:

1. Vyberte všetky riadky tabuľky, v ktorých má funkcia hodnotu 0.

2. Pre každý takýto riadok priraďte disjunkciu všetkých argumentov alebo ich inverzie (maxterm). V tomto prípade je argument s hodnotou 1 zahrnutý do maxterm s negáciou a hodnota 1 je zahrnutá bez negácie.

3. Nakoniec vytvoríme konjunkciu všetkých získaných maxtermov. Počet maxtermov sa musí zhodovať s počtom núl logickej funkcie.

Ak sa z dvoch foriem (SDNF alebo SKNF) dohodneme na uprednostnení tej, ktorá obsahuje menej písmen, potom je SDNF vhodnejšie, ak je medzi hodnotami funkcie pravdivostnej tabuľky, SKNF, menej jednotiek, ak je menej núl.

Príklad. Je uvedená pravdivostná tabuľka logickej funkcie troch premenných. Zostavte logický vzorec, ktorý implementuje túto funkciu.

			F(A, B, C)

Vyberme tie riadky v tejto pravdivostnej tabuľke, v ktorých je funkčná hodnota 0.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Skontrolujme odvodenú funkciu vytvorením pravdivostnej tabuľky.

Porovnaním počiatočných a konečných pravdivostných tabuliek môžeme konštatovať, že logická funkcia je skonštruovaná správne.

Riešenie problémov

1. Traja učitelia vyberajú úlohy na olympiádu. Na výber je viacero úloh. Ku každej úlohe každý učiteľ vyjadrí svoj názor: ľahká (0) alebo ťažká (1) úloha. Úloha je zaradená do úlohy olympiády, ak ju aspoň dvaja učitelia označia ako ťažkú, ale ak ju všetci traja učitelia považujú za ťažkú, potom takáto úloha nie je zaradená do úlohy olympiády ako príliš ťažká. Vytvorte logickú schému zariadenia, ktoré vydá 1, ak je úloha zahrnutá v úlohe olympiády, a 0, ak nie je zahrnutá.

Zostavme pravdivostnú tabuľku pre požadovanú funkciu. Máme tri vstupné premenné (traja učitelia). Preto bude požadovaná funkcia funkciou troch premenných.

Analýzou stavu problému získame nasledujúcu pravdivostnú tabuľku:

Budujeme SDNF. F(A, B, C) = ABC+ ABC+ ABC

Teraz zostavíme logický diagram tejto funkcie.

B&1F(A,B,C)

2. Mestská olympiáda v základnom kurze informatiky, 2007.Zostavte schému elektrického obvodu pre vchod do trojposchodového domu tak, aby vypínač na ktoromkoľvek poschodí mohol zapínať alebo vypínať svetlá v celom dome.

Máme teda tri spínače, ktoré musíme použiť na zapnutie a vypnutie svetla. Každý prepínač má dva stavy: hore (0) a dole (1). Predpokladajme, že ak sú všetky tri spínače v polohe 0, svetlá vo vchode sú vypnuté. Potom, keď presuniete ktorýkoľvek z troch spínačov do polohy 1, malo by sa rozsvietiť svetlo vo vchode. Je zrejmé, že keď presuniete akýkoľvek iný spínač do polohy 1, svetlo vo vchode zhasne. Ak sa prepne tretí spínač do polohy 1, rozsvieti sa svetlo vo vchode. Vytvárame tabuľku pravdy.

Potom F(A, B, C) = ABC+ ABC+ ABC+ ABC.

	3. Zmeňte stav			hodnoty logických funkcií			F(A, B, C) = C->		A+B
	zmena argumentov B a C súčasne sa rovná:
		A → (B C)						(B C) → A
					A(B C)
	4) (BC) → A				A → (B C)

Poznámka. Ak chcete úspešne vyriešiť tento problém, zapamätajte si nasledujúce logické vzorce:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

Máme logickú funkciu troch premenných F 1 (A, B, C) = C → A + B = C + A B.

Zmeňme súčasne premenné B a C: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Zostavme pravdivostné tabuľky pre tieto dve funkcie:

Poďme analyzovať výslednú tabuľku. Z ôsmich riadkov tabuľky iba v dvoch (2. a 3.) funkcia nemení svoju hodnotu. Všimnite si, že v týchto riadkoch premenná A neobráti svoju hodnotu, ale premenné B a C áno.

Funkcie SKNF vytvárame pomocou týchto riadkov:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (BC) → A

Preto je požadovaná odpoveď 4.

4. Podmienka pre zmenu hodnoty logickej funkcie F (A, B, C) = C + AB pri súčasnej zmene argumentov A a B sa rovná:

1) C+ (A B)

C+(A B)

TAXÍK)

4) C(A B)

C → (A B)

F1(A,B,C)=

C+AB

F 2 (A , B , C ) = F 1 (

C) = A

Vytvárame tabuľku pravdy.

Poďme analyzovať výslednú tabuľku. Z ôsmich riadkov tabuľky len v dvoch (1. a 7.) funkcia mení svoju hodnotu. Upozorňujeme, že v týchto riadkoch nemení svoju hodnotu premenná C, ale premenné A a B áno.

Funkcie SDNF vytvárame pomocou týchto riadkov:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Preto je požadovaná odpoveď 2.

Referencie

1. Shapiro S.I. Riešenie logických a herných problémov(logické a psychologické štúdie). – M.: Rádio a spoje, 1984. – 152 s.

2. Šolomov L.A. Základy teórie diskrétnych logických a výpočtových zariadení. – M.: Veda. Ch. vyd. fyzické - mat. lit., 1980. - 400 s.

3. Pukhalsky G.I., Novoseltseva T.Ya. Návrh diskrétnych zariadení na integrovaných obvodoch: Príručka. – M.: Rádio a spoje, 1990.