Mestská rozpočtová vzdelávacia inštitúcia
"Stredná škola č. 18"
mestská časť mesta Salavat v Republike Bashkortostan
Systémy logických rovníc
v úlohách skúšky z informatiky
Časť „Základy algebry logiky“ v úlohách skúšky sa považuje za jednu z najťažších a zle vyriešených. Priemerné percento dokončenia úloh na túto tému je najnižšie a je 43,2.
| Sekcia kurzu | Priemerné percento dokončenia podľa skupín úloh |
| Kódovanie informácií a meranie ich množstva | |
| informačné modelovanie | |
| Číselné sústavy | |
| Základy algebry logiky | |
| Algoritmizácia a programovanie | |
| Základy informačných a komunikačných technológií |
Na základe špecifikácie KIM 2018 tento blok zahŕňa štyri úlohy rôznej úrovne zložitosti.
| № úlohy | Skontrolované obsahové prvky | Úroveň obtiažnosti úlohy |
| Schopnosť zostaviť pravdivostné tabuľky a logické obvody | ||
| Schopnosť vyhľadávať informácie na internete | ||
| Znalosť základných pojmov a zákonitostí matematická logika | ||
| Schopnosť vytvárať a transformovať logické výrazy |
Úloha 23 má vysoký stupeň obtiažnosti, preto má najnižšie percento dokončenia. Spomedzi vyškolených absolventov (81-100 bodov) ju splnilo 49,8 %, priemerne pripravených (61-80 bodov) zvláda 13,7 %, zvyšná skupina študentov túto úlohu neplní.
Úspešnosť riešenia sústavy logických rovníc závisí od znalosti zákonov logiky a od presnej aplikácie metód riešenia sústavy.
Uvažujme o riešení sústavy logických rovníc mapovacou metódou.
(23.154 Polyakov K.Yu.) Koľko rôznych riešení má sústava rovníc?
((X1 r1 ) (X2 r2 )) (X1 X2 ) (y1 r2 ) =1
((X2 r2 ) (X3 r3 )) (X2 X3 ) (y2 r3 ) =1
((X7 r7 ) (X8 r8 )) (X7 X8 ) (r7 r8 ) =1
kde X1 , X2 ,…, X8, pri1 ,y2 ,…,y8 - Booleovské 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.
rozhodnutie. Všetky rovnice zahrnuté v systéme sú rovnakého typu a v každej rovnici sú zahrnuté štyri premenné. Keď poznáme x1 a y1, môžeme nájsť všetky možné hodnoty x2 a y2, ktoré spĺňajú prvú rovnicu. Argumentujúc podobným spôsobom, zo známych x2 a y2 môžeme nájsť x3, y3, ktoré spĺňajú druhú rovnicu. To znamená, že ak poznáme pár (x1 , y1) a určíme hodnotu páru (x2 , y2) , nájdeme pár (x3 , y3 ), čo zase povedie k páru (x4 , y4 ) atď. na.
Nájdite všetky riešenia prvej rovnice. Dá sa to urobiť dvoma spôsobmi: zostavením pravdivostnej tabuľky pomocou uvažovania a uplatňovania zákonov logiky.
Tabuľka pravdy:
| x 1 y 1 | x2 y2 | (x 1 y1) (x 2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
Zostavenie pravdivostnej tabuľky je prácne a časovo neefektívne, preto používame druhý spôsob – logické uvažovanie. Súčin je 1 práve vtedy, ak je každý faktor 1.
(X1 r1 ) (X2 r2 ))=1
(X1 X2 ) =1
(r1 r2 ) =1
Zvážte prvú rovnicu. Nasledujúce sa rovná 1, keď 0 0, 0 1, 1 1, potom (x1 y1)=0 v (01), (10), potom pár (X2 r2 ) môže byť ľubovoľný (00), (01), (10), (11) a pre (x1 y1)=1, t.j. (00) a (11) má pár (x2 y2)=1 rovnaké hodnoty (00) a (11). Z tohto riešenia vylúčime tie dvojice, pre ktoré sú druhá a tretia rovnica nepravdivé, teda x1=1, x2=0, y1=1, y2=0.
| (X1 , r1 ) | (X2 , r2 ) |
Celkový počet párov 1+1+1+22= 25
2) (23,160 Polyakov K.Yu.) Koľko rôznych riešení má systém logických rovníc
(X 1 (X 2 r 2 )) (y 1 r 2 ) = 1
(X 2 (X 3 r 3 )) (y 2 r 3 ) = 1
...
( X 6 ( X 7 r 7 )) ( r 6 r 7 ) = 1
X 7 r 7 = 1
rozhodnutie. 1) Rovnice sú rovnakého typu, takže uvažovaním nájdeme všetky možné dvojice (x1,y1), (x2,y2) prvej rovnice.
(X1 (X2 r2 ))=1
(r1 r2 ) = 1
Riešením druhej rovnice sú dvojice (00), (01), (11).
Poďme nájsť riešenia prvej rovnice. Ak x1=0, potom x2 , y2 - ľubovoľné, ak x1=1, potom x2 , y2 nadobudne hodnotu (11).
Urobme spojenia medzi pármi (x1 , y1) a (x2 , y2).
| (X1 , r1 ) | (X2 , r2 ) |
Urobme tabuľku na výpočet počtu párov v každej fáze.
| 0 |
|||||||
Berúc do úvahy riešenia poslednej rovnice X 7 r 7 = 1, vylúčime dvojicu (10). Nájdite celkový počet riešení 1+7+0+34=42
3)(23.180) Koľko rôznych riešení má sústava logických rovníc
(X1 X2 ) (X3 X4 ) = 1
(X3 X4 ) (X5 X6 ) = 1
(X5 X6 ) (X7 X8 ) = 1
(X7 X8 ) (X9 X10 ) = 1
X1 X3 X5 X7 X9 = 1
rozhodnutie. 1) Rovnice sú rovnakého typu, teda metódou uvažovania nájdeme všetky možné dvojice (x1,x2), (x3,x4) prvej rovnice.
(X1 X2 ) (X3 X4 ) = 1
Z riešenia vylúčime dvojice, ktoré v ďalšom dávajú 0 (1 0), sú to dvojice (01, 00, 11) a (10).
Vytvárajte odkazy medzi pármi (x1,x2), (x3,x4)
Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, konštrukciu pravdivostnej tabuľky a rozklad.
Úloha: Vyriešte sústavu logických rovníc:
Zvážte metóda redukcie na jednu rovnicu . Táto metóda zahŕňa transformáciu logických rovníc tak, aby sa ich pravá strana rovnala pravdivostnej hodnote (teda 1). Na tento účel použite operáciu logickej negácie. Potom, ak sú v rovniciach 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 vykonať transformácie výslednej rovnice na základe zákonov algebry logiky 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“, „NIE“:
Keďže ľavé strany rovníc sa rovnajú 1, môžete 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 výsledok:
Výsledná rovnica má jedno riešenie: A=0, B=0 a C=1.
Ďalší spôsob je konštrukcia 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 vytvorí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: Urobme pravdivostnú tabuľku pre systém:
|
0 |
0 |
1 |
1 |
0 |
1 |
Tučným písmom je čiara, pre ktorú sú splnené podmienky problému. Takže A=0, B=0 a C=1.
spôsob rozklad . Cieľom je zafixovať hodnotu jednej z premenných (urovnať ju 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.
Riešenie 3: Nech A = 0, potom:
Z prvej rovnice dostaneme B = 0 az druhej - С=1. Systémové riešenie: A = 0, B = 0 a C = 1.
Pri POUŽITÍ v informatike je veľmi často potrebné určiť počet riešení sústavy logických rovníc, bez toho, aby sa nachádzali samotné riešenia, existujú na to aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, jezmena premenných. Najprv je potrebné každú z rovníc čo najviac zjednodušiť na základe zákonov algebry logiky a následne nahradiť zložité časti rovníc novými premennými a určiť počet riešení novej sústavy. Potom sa vráťte k náhrade a určite pre ňu počet riešení.
Úloha: Koľko riešení má rovnica (A → B ) + (C → D ) = 1? Kde A, B, C, D sú boolovské premenné.
rozhodnutie: Zavedieme nové premenné: X = A → B a Y = C → D . S prihliadnutím na nové premenné bude rovnica napísaná v tvare: X + Y = 1.
Disjunkcia je pravdivá v troch prípadoch: (0;1), (1;0) a (1;1), pričom X a Y sú implikácia, to znamená, že je pravdivá v troch prípadoch a nepravdivá v jednom. 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. Existuje teda 3+9=15 možných riešení tejto rovnice.
Nasledujúci spôsob určenia počtu riešení sústavy logických rovníc je − binárny strom. Uvažujme o tejto metóde s príkladom.
Ú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 to X 1 je pravda, potom z prvej rovnice dostaneme, že X 2 tiež pravda, od druhého - X 3 =1, a tak ďalej, kým x m= 1. To znamená, že množina (1; 1; …; 1) m jednotiek je riešením sústavy. Nechaj teraz X 1 =0, potom z prvej rovnice máme X 2 =0 alebo X 2 =1.
Kedy X 2 true, získame, že aj ostatné premenné sú pravdivé, teda množina (0; 1; ...; 1) je riešením systému. o X 2 =0 chápeme to X 3 =0 alebo X 3 = a tak ďalej. Pokračujúc k poslednej premennej, dostaneme, že riešenia rovnice sú nasledujúce množiny premenných (m + 1 riešenie, každé riešenie má m hodnôt premenných):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Tento prístup je dobre ilustrovaný vytvorením binárneho stromu. Počet možných riešení je počet rôznych vetiev zostrojeného stromu. Je ľahké vidieť, že sa rovná m + 1.
|
Drevo |
Počet rozhodnutí |
|
|
x 1 |
|
|
|
x2 |
||
|
x 3 |
||
|
… |
V prípade ťažkostí s uvažovaním niyah a stavebníctvo derevu riešení, môžete hľadať riešenie pomocou použitím pravdivostné tabuľkypre jednu alebo dve rovnice.
Prepíšeme sústavu rovníc do tvaru:
A urobme pravdivostnú tabuľku samostatne pre jednu rovnicu:
|
x 1 |
x2 |
(x 1 → x 2) |
Urobme pravdivostnú tabuľku pre dve rovnice:
|
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Téma lekcie: Riešenie logických rovníc
vzdelávacie - štúdium spôsobov riešenia logických rovníc, vytváranie zručností a schopností riešiť logické rovnice a zostaviť logické vyjadrenie podľa pravdivostnej tabuľky;vzdelávacie - vytvárať podmienky pre rozvoj kognitívneho záujmu žiakov, podporovať rozvoj pamäti, pozornosti, logického myslenia;
Vzdelávacie : prispievať k výchove schopnosti počúvať názory iných, výchova vôle a vytrvalosti k dosiahnutiu konečných výsledkov.
Typ lekcie: kombinovaná lekcia
Vybavenie: počítač, multimediálny projektor, prezentácia 6.
Počas vyučovania
Opakovanie a aktualizácia základných vedomostí. Kontrola domácich úloh (10 minút)
V predchádzajúcich lekciách sme sa zoznámili so základnými zákonmi algebry logiky, naučili sme sa tieto zákony použiť na zjednodušenie logických výrazov.
Pozrime sa na domácu úlohu o zjednodušení logických výrazov:
1. Ktoré z nasledujúcich slov spĺňa logickú podmienku:
(prvá spoluhláska → druhá spoluhláska)٨ (posledná samohláska → predposledná samohláska)? Ak existuje niekoľko takýchto slov, uveďte najmenšie z nich.
1) ANNA 2) MARIA 3) OLEG 4) ŠTEPÁN
Predstavme si notáciu:
A je prvé písmeno spoluhlásky
B je druhé písmeno spoluhlásky
S je posledná samohláska
D - predposledná samohláska
Urobme výraz:
Urobme si tabuľku:
2. Uveďte, ktorý logický výraz je ekvivalentný výrazu
Zjednodušme si písanie pôvodného výrazu a navrhovaných možností:
3. Fragment pravdivostnej tabuľky výrazu F je daný:
Aký výraz zodpovedá F?
Poďme určiť hodnoty týchto výrazov pre zadané hodnoty argumentov:
Oboznámenie sa s témou hodiny, prezentácia nového materiálu (30 minút)
Pokračujeme v štúdiu základov logiky a témy našej dnešnej lekcie „Riešenie logických rovníc“. Po preštudovaní tejto témy sa naučíte základné spôsoby riešenia logických rovníc, získate zručnosti na riešenie týchto rovníc pomocou jazyka logickej algebry a schopnosť zostaviť logický výraz na pravdivostnej tabuľke.
1. Vyriešte logickú rovnicu
(¬K M) → (¬L M N) = 0
Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá K=1, L=1, M=0, N=1.
rozhodnutie:
Transformujme výraz(¬K M) → (¬L M N)
Výraz je nepravdivý, keď sú oba pojmy nepravdivé. Druhý člen sa rovná 0, ak M=0, N=0, L=1. V prvom člene je K = 0, pretože M = 0 a 
.
Odpoveď: 0100
2. Koľko riešení má rovnica (v odpovedi uveďte len číslo)?
Riešenie: transformujte výraz
(A+B)*(C+D)=1
A+B=1 a C+D=1
Metóda 2: zostavenie pravdivostnej tabuľky
3 spôsob: konštrukcia SDNF - dokonalý disjunktívny normálny tvar pre funkciu - disjunkcia úplných pravidelných elementárnych konjunkcií.Transformujme pôvodný výraz, otvorme zátvorky, aby sme získali disjunkciu spojok:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Doplňme spojky na úplné spojky (súčin všetkých argumentov), otvorme zátvorky:
Zvážte rovnaké spojky:
Výsledkom je, že získame SDNF obsahujúci 9 konjunkcií. Pravdivostná tabuľka pre túto funkciu má preto hodnotu 1 na 9 riadkoch z 2 4 =16 množín hodnôt premenných.
3. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?
Zjednodušme výraz:
,
3 spôsob: výstavba SDNF
Zvážte rovnaké spojky:
Výsledkom je SDNF obsahujúci 5 konjunkcií. Preto pravdivostná tabuľka pre túto funkciu má hodnotu 1 na 5 riadkoch 2 4 = 16 množín hodnôt premenných.
Zostavenie logického výrazu podľa pravdivostnej tabuľky:
pre každý riadok pravdivostnej tabuľky obsahujúcej 1 skladáme súčin argumentov a premenné rovné 0 sú zahrnuté v súčine s negáciou a premenné rovné 1 - bez negácie. Požadovaný výraz F bude zložený zo súčtu získaných produktov. Potom, ak je to možné, tento výraz by sa mal zjednodušiť.
Príklad: je daná pravdivostná tabuľka výrazu. Vytvorte logické vyjadrenie.
rozhodnutie:3. domáca úloha (5 minút)
Vyriešte rovnicu:
Koľko riešení má rovnica (odpovedzte len číslo)?
Podľa uvedenej pravdivostnej tabuľky urobte logické vyjadrenie a
zjednodušiť to.
Spôsoby 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 argumentovať, vytvárať hypotézy, vyvracať negatívne závery neprichádza sama od seba, túto zručnosť rozvíja veda o 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. Kontrola formovania zručností na uplatnenie svojich vedomostí v novej situácii sa vykonáva absolvovaním. Ide najmä o schopnosť riešiť logické problémy. Úlohy B15 na skúške sú úlohy so zvýšenou zložitosťou, pretože obsahujú sústavy 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:
Zvážte metóda redukcie na jednu rovnicu . Táto metóda zahŕňa transformáciu logických rovníc tak, aby sa ich pravá strana rovnala pravdivostnej hodnote (teda 1). Na tento účel použite operáciu logickej negácie. Potom, ak sú v rovniciach 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 vykonať transformácie výslednej rovnice na základe zákonov algebry logiky 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“, „NIE“:
Keďže ľavé strany rovníc sa rovnajú 1, môžete 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 výsledok:
Výsledná rovnica má jedno riešenie: A= 0, B = 0 a C = 1.
Ďalší spôsob je konštrukcia 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 vytvorí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:Urobme pravdivostnú tabuľku pre systém:
|
0 |
0 |
1 |
1 |
0 |
1 |
Tučným písmom je čiara, pre ktorú sú splnené podmienky problému. Takže A = 0, B = 0 a C = 1.
spôsob rozklad . Cieľom je zafixovať hodnotu jednej z premenných (urovnať ju 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.
Riešenie 3: Nechať byť A = 0, potom:
Z prvej rovnice dostaneme B = 0 a od druhého - С = 1. Systémové riešenie: A = 0 , B = 0 a C = 1 .
Môžete tiež použiť metódu sekvenčné riešenie rovníc pridaním jednej premennej do uvažovanej množiny v každom kroku. 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 vyplýva, že 
, takže keď A = 0 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 .
Nakreslíme druhú rovnicu, z ktorej určíme hodnoty C pre každú možnosť. Pre A = 1 nemôže byť implikácia 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 POUŽITÍ v informatike je veľmi často potrebné určiť počet riešení sústavy logických rovníc, bez toho, aby sa nachádzali samotné riešenia, existujú na to aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, je zmena premenných. Najprv je potrebné každú z rovníc čo najviac zjednodušiť na základe zákonov algebry logiky a následne nahradiť zložité časti rovníc novými premennými a určiť počet riešení novej sústavy. Potom sa vráťte k náhrade a určite pre ňu počet riešení.
Úloha:Koľko riešení má rovnica ( A → B) + (C → D ) = 1? Kde A, B, C, D sú boolovské premenné.
rozhodnutie:Predstavme si nové premenné: X = A → B a Y = C → D . Berúc do úvahy nové premenné, rovnicu možno zapísať 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. Existuje teda 3+9=15 možných riešení tejto rovnice.
Nasledujúci spôsob určenia počtu riešení sústavy logických rovníc je − binárny strom. Uvažujme o tejto metóde s príkladom.
Ú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 z prvej rovnice dostaneme, žeX 2 tiež pravda, od druhého -X 3 =1, a tak ďalej, kým x m= 1. Preto množina (1; 1; …; 1) z m jednotiek je riešením systému. Nechaj terazX 1 =0, potom z prvej rovnice mámeX 2 =0 alebo X 2 =1.
Kedy X 2 true, získame, že aj ostatné premenné sú pravdivé, teda 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 roztok v každom roztoku m premenné hodnoty):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Tento prístup je dobre ilustrovaný vytvorením binárneho stromu. Počet možných riešení je počet rôznych vetiev zostrojeného stromu. Je ľahké vidieť, že áno m+1.
|
Premenné |
Drevo |
Počet rozhodnutí |
|
x 1 |
|
|
|
x2 |
||
|
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íšeme sústavu rovníc do tvaru:
A urobme pravdivostnú tabuľku samostatne pre jednu rovnicu:
|
x 1 |
x2 |
(x 1 → x 2) |
Urobme pravdivostnú tabuľku pre dve rovnice:
|
x 1 |
x2 |
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 je pravdivý 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, 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 pravdivosti predpokladu.
Zhrnutím vyššie uvedeného by som chcel upozorniť na skutočnosť, že nie všetky uvažované metódy sú univerzálne. Pri riešení každého systému logických rovníc by sa mali brať do úvahy jeho vlastnosti, na základe ktorých by sa mala zvoliť metóda riešenia.
Literatúra:
1. Logické úlohy / O.B. Bogomolov - 2. vyd. – M.: BINOM. Vedomostné laboratórium, 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
Metódy riešenia sústav logických rovníc
Systém logických rovníc môžete vyriešiť napríklad pomocou pravdivostnej tabuľky (ak počet premenných nie je príliš veľký) alebo pomocou rozhodovacieho stromu po zjednodušení každej rovnice.
1. Metóda zmeny premenných.
Zavedenie nových premenných umožňuje zjednodušiť systém rovníc znížením počtu neznámych.Nové premenné musia byť navzájom nezávislé. Po vyriešení zjednodušeného systému je potrebné sa opäť vrátiť k pôvodným premenným.
Zvážte použitie tejto metódy na konkrétnom príklade.
Príklad.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
rozhodnutie:
Zavedme nové premenné: А=(X1≡X2); B = (X3 = X4); С=(X5 ≡ X6); D = (X7 = X8); E = (X9 = X10).
(Pozor! Každá ich premenná x1, x2, ..., x10 musí byť zahrnutá len v jednej z nových premenných A, B, C, D, E, t.j. nové premenné sú od seba nezávislé).
Potom bude systém rovníc vyzerať takto:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Zostavme rozhodovací strom výsledného systému:
Uvažujme rovnicu A=0, t.j. (X1≡ X2) = 0. Má 2 korene:
X1 ≡ X2 |
||
Z tej istej tabuľky je vidieť, že rovnica A \u003d 1 má tiež 2 korene. Usporiadajme počet koreňov v rozhodovacom strome:
Ak chcete zistiť počet riešení pre jednu pobočku, musíte vynásobiť počet riešení na každej úrovni. Ľavá vetva má 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 32 roztokov; pravá vetva má tiež 32 riešení. Tie. celý systém má 32+32=64 riešení.
odpoveď: 64.
2. Spôsob uvažovania.
Zložitosť riešenia sústav logických rovníc spočíva v objemnosti úplného rozhodovacieho stromu. Metóda uvažovania vám umožňuje nepostaviť celý strom úplne, ale zároveň pochopiť, koľko vetiev bude mať. Uvažujme o tejto metóde na konkrétnych príkladoch.
Príklad 1 Koľko rôznych množín hodnôt booleovských premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa všetky nasledujúce podmienky?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 = 1
Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, pod ktorými je daný systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.
rozhodnutie:
Prvá a druhá rovnica obsahujú nezávislé premenné, ktoré súvisia s treťou podmienkou. Zostavme rozhodovací strom pre prvú a druhú rovnicu.
Na reprezentáciu rozhodovacieho stromu systému z prvej a druhej rovnice je potrebné pokračovať v každej vetve prvého stromu stromom pre premenné pri . Takto skonštruovaný strom bude obsahovať 36 konárov. Niektoré z týchto vetiev nespĺňajú tretiu rovnicu systému. Všimnite si na prvom strome počet vetiev stromu"at" , ktoré spĺňajú tretiu rovnicu:
Ujasnime si: pre splnenie tretej podmienky pri x1=0 musí byť y1=1, teda všetky vetvy stromu"X" , kde x1=0 môže pokračovať len jednou vetvou zo stromu"at" . A to len na jednu vetvu stromu"X" (vpravo) zapadajú všetky vetvy stromu„at“. Kompletný strom celého systému teda obsahuje 11 vetiev. Každá vetva predstavuje jedno riešenie pôvodného systému rovníc. Celý systém má teda 11 riešení.
odpoveď: 11.
Príklad 2 Koľko rôznych riešení má sústava rovníc
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1
(X1 ≡ X10) = 0
kde x1, x2, …, x10 sú boolovské 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.
rozhodnutie: Zjednodušme systém. Zostavme pravdivostnú tabuľku časti prvej rovnice:
X1 ∧ X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10) |
||
Venujte pozornosť poslednému stĺpcu, zhoduje sa s výsledkom akcie X1 ≡ X10.
X1 ≡ X10 |
Po zjednodušení dostaneme:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Zvážte poslednú rovnicu:(X1 ≡ X10) = 0, t.j. x1 by nemalo byť to isté ako x10. Aby sa prvá rovnica rovnala 1, musí platiť rovnosť(X1 ≡ X2) = 1, t.j. x1 sa musí zhodovať s x2.
Zostavme rozhodovací strom pre prvú rovnicu:
Zvážte druhú rovnicu: pre x10=1 a pre x2=0 zátvorkumusí sa rovnať 1 (t. j. x2 je rovnaké ako x3); pri x10=0 a pri x2=1 zátvorka(X2 ≡ X10)=0 , takže zátvorka (X2 ≡ X3) sa musí rovnať 1 (t. j. x2 je rovnaké ako x3):
Týmto spôsobom vytvoríme rozhodovací strom pre všetky rovnice:
Sústava rovníc má teda len 2 riešenia.
odpoveď: 2.
Príklad 3
Koľko rôznych množín hodnôt booleovských premenných x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 spĺňa všetky nasledujúce podmienky?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
rozhodnutie:
Zostavme rozhodovací strom 1. rovnice:
Zvážte druhú rovnicu:
- Keď x1=0 : druhá a tretia zátvorka bude 0; aby sa prvá zátvorka rovnala 1, musí y1=1 , z1=1 (t.j. v tomto prípade - 1 riešenie)
- S x1=1 : prvá zátvorka bude 0; druhý alebo tretia zátvorka sa musí rovnať 1; druhá zátvorka sa bude rovnať 1, keď y1=0 a z1=1; tretia zátvorka sa bude rovnať 1 pre y1=1 a z1=0 (t.j. v tomto prípade - 2 riešenia).
Podobne pre zvyšok rovníc. Všimnite si počet riešení získaných pre každý uzol stromu:
Aby sme zistili počet riešení pre každú vetvu, vynásobíme získané čísla zvlášť pre každú vetvu (zľava doprava).
1 vetva: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 roztok
2 vetvy: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 riešenia
3. vetva: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 riešenia
4 vetvy: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 riešení
5 vetva: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 riešení
Pridajme získané čísla: spolu 31 riešení.
odpoveď: 31.
3. Pravidelné zvyšovanie počtu koreňov
V niektorých systémoch závisí počet koreňov nasledujúcej rovnice od počtu koreňov predchádzajúcej rovnice.
Príklad 1 Koľko rôznych množín hodnôt booleovských premenných x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 spĺňa všetky nasledujúce podmienky?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Zjednodušiť prvá rovnica:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Potom bude mať systém podobu:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
Atď.
Každá nasledujúca rovnica má o 2 korene viac ako predchádzajúca.
4 rovnica má 12 koreňov;
Rovnica 5 má 14 koreňov
8 rovnica má 20 koreňov.
Odpoveď: 20 koreňov.
Niekedy počet koreňov rastie podľa zákona Fibonacciho čísel.
Riešenie sústavy logických rovníc si vyžaduje kreatívny prístup.
