Spôsoby riešenia systémov logické rovnice
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. Predovšetkým je to schopnosť riešiť logické úlohy. Úlohy B15 na skúške sú úlohy so zvýšenou zložitosťou, pretože obsahujú sústavy logických rovníc. Dá sa rozlíšiť rôznymi spôsobmi riešenie sústav 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é hodnoty majú iba dve hodnoty, môžete jednoducho prejsť všetkými možnosťami 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: Nechaj 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é čo najviac zjednodušiť každú z rovníc na základe zákonov algebry logiky a potom nahradiť zložité časti rovníc novými premennými a určiť počet riešení. nový systém. 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é.
Riešenie: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. Takže celkovo možné riešenia daná rovnica 3+9=15.
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 až do 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é |
Strom |
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 spoločné rozhodnutie bude mať rovnakú formu, ale na to, aby bol takýto prístup riešením, je potrebný dôkaz, že predpoklad je pravdivý.
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
Tento materiál obsahuje prezentáciu, ktorá prezentuje metódy riešenia logických rovníc a sústav logických rovníc v úlohe B15 (č. 23, 2015) Jednotnej štátnej skúšky z informatiky. Je známe, že táto úloha je jednou z najťažších medzi úlohami skúšky. Prezentácia môže byť užitočná pri vedení lekcií na tému „Logika“ v špecializovaných triedach, ako aj pri príprave na zloženie skúšky.
Ak chcete použiť ukážku prezentácií, vytvorte si Google účet (účet) a prihláste sa: https://accounts.google.com
Riešenie úlohy B15 (systém logických rovníc) Vishnevskaya M.P., MAOU "Gymnasium No. 3" 18. novembra 2013, Saratov
Úloha B15 je jedna z najťažších na skúške z informatiky !!! Kontrolujú sa schopnosti: transformovať výrazy obsahujúce logické premenné; popísať na prirodzený jazyk množina hodnôt logických premenných, pre ktoré je daná množina logických premenných pravdivá; spočítajte počet vyhovujúcich binárnych množín dané podmienky. Najťažšie, pretože neexistujú žiadne formálne pravidlá, ako to urobiť, je potrebné hádanie.
Bez čoho sa nezaobísť!
Bez čoho sa nezaobísť!
Konvencie spojenie: A /\ B , A B , AB , А & B, A a B disjunkcia: A \ / B , A + B , A | B , A alebo B negácia: A , A, nie A ekvivalent: A B, A B, A B XOR: A B , A xor B
Metóda substitúcie premenných Koľko rôznych množín hodnôt booleovských premenných x1, x2, ..., x9, x10 existuje, ktoré spĺňajú všetky nasledujúce podmienky: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, …, x9, x10, pod ktorými daný systém rovnosti je splnený. Ako odpoveď musíte uviesť počet takýchto sád (demo verzia 2012)
Riešenie Krok 1. Zjednodušte zmenou premenných t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 Po zjednodušení: (t1 \/ t2) /\ (¬t1 \/\ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Uvažujme jednu z rovníc: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Je zrejmé, že je to =1 iba vtedy, ak jedna z premenných je 0 a druhá je 1 Použime vzorec na vyjadrenie operácie XOR pomocou konjunkcie a disjunkcie: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
Krok 2. Analýza systému .To. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), potom každá hodnota tk zodpovedá dvom párom hodnôt x2k-1 a x2k , napríklad: tk =0 zodpovedá dvom párom - (0, 1) a (1, 0) a tk = 1 sú dvojice (0,0) a (1,1).
Krok 3. Počítanie počtu riešení. Každé t má 2 riešenia, počet t je 5. Teda pre premenné t je 2 5 = 32 riešení. Každé t ale zodpovedá dvojici riešení x, t.j. pôvodný systém má 2*32 = 64 riešení. odpoveď: 64
Metóda eliminácie čiastočného riešenia Koľko rôznych množín hodnôt logických premenných x1, x2, …, x5, y1,y2,…, y5 existuje, ktoré spĺňajú všetky nasledujúce podmienky: (x1→ x2)∧(x2→ x3)∧ (x3→x4)∧(x4→x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 = 1. Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, ..., x5, y 1, y2, ..., y5, podľa ktorých je tento systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie. Krok 1. Sekvenčné riešenie rovníc x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 každá z implikácií je pravdivá. Implikácia je nepravdivá iba v jednom prípade, keď 1 0, vo všetkých ostatných prípadoch (0 0, 0 1, 1 1) vráti operácia 1. Zapíšme si to vo forme tabuľky:
Krok 1. Sekvenčné riešenie rovníc Т.о. Prijme sa 6 sád riešení pre х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Ak budeme argumentovať podobne, dôjdeme k záveru, že pre y1, y2, y3, y4, y5 existuje rovnaká množina riešení. Pretože tieto rovnice sú nezávislé, t.j. v nich nie sú žiadne spoločné premenné, potom riešenie tohto systému rovníc (bez zohľadnenia tretej rovnice) bude 6 * 6 = 36 párov „xes“ a „áno“. Uvažujme tretiu rovnicu: y5→ x5 =1 Dvojice sú riešením: 0 0 0 1 1 1 Dvojica nie je riešením: 1 0
Porovnajme získané riešenia Kde y5 =1, x5=0 nesedí. takýchto dvojíc je 5. Počet riešení sústavy: 36-5= 31. odpoveď: 31 Chcelo to kombinatoriku!!!
Metóda dynamického programovania Koľko rôznych riešení má logická rovnica x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kde x 1, x 2, ..., x 6 sú 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 Krok 1. Analýza podmienky Na ľavej strane rovnice sú postupne zapísané implikačné operácie, priorita je rovnaká. Prepíšte: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Poznámka! Každá ďalšia premenná nezávisí od predchádzajúcej, ale od výsledku predchádzajúcej implikácie!
Krok 2. Odhalenie vzoru Zvážte prvú implikáciu, X 1 → X 2. Tabuľka pravdivosti: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednej 0 máme 2 jednotky a z 1 sme dostal jednu 0 a jednu 1. Len jednu 0 a tri 1, to je výsledok prvej operácie.
Krok 2. Odhalenie vzoru Spojením x 3 s výsledkom prvej operácie dostaneme: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Z dvoch 0 - dve 1, z každej 1 (sú 3) po jednej 0 a 1 (3 + 3)
Krok 3. Odvodenie vzorca môžete vytvoriť vzorce na výpočet počtu núl N i a počtu jednotiek E i pre rovnicu s premennými i: ,
Krok 4. Vyplnenie tabuľky Vyplňte tabuľku pre i = 6 zľava doprava, pričom vypočítajte počet núl a jednotiek pomocou vyššie uvedených vzorcov; tabuľka ukazuje, ako je zostavený nasledujúci stĺpec podľa predchádzajúceho: : počet premenných 1 2 3 4 5 6 Počet núl N i 1 1 3 5 11 21 Počet jednotiek E i 1 2*1+1= 3 2 *1+3= 5 11 21 43 Odpoveď: 43
Metóda využívajúca zjednodušenia logických výrazov Koľko rôznych riešení má rovnica ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 kde J , K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt J, K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie Všimnite si, že J → K = ¬ J K Zavádzame zmenu premenných: J → K=A, M N L =B Rovnicu prepíšeme s prihliadnutím na zmenu: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Je zrejmé, že A B pre rovnaké hodnoty A a B 6. Uvažujme poslednú implikáciu M → J =1 To je možné, ak: M=J=0 M=0, J=1 M=J=1
Riešenie A B , potom s M=J=0 dostaneme 1 + K=0. Neexistujú žiadne riešenia. S M=0, J=1 dostaneme 0 + K=0, K=0 a N a L - ľubovoľné, 4 riešenia: ¬ J K = M N LKNL 0 0 0 0 0 1 0 1 0 0 1 jeden
Riešenie 10. Pri M=J=1 dostaneme 0+K=1 *N * L , alebo K=N*L, 4 riešenia: 11. Celkom má 4+4=8 riešení Odpoveď: 8 KNL 0 0 0 0 0 1 0 1 0 1 1 1
Zdroje informácií: O.B. Bogomolová, D.Yu. Usenkov. B15: nové úlohy a nové riešenie // Informatika, č. 6, 2012, s. 35 – 39. K.Yu. Polyakov. Logické rovnice // Informatika, č. 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronický zdroj]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronický zdroj].
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é hodnoty majú iba dve hodnoty, môžete jednoducho prejsť všetkými možnosťami 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é.
Riešenie: 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 až do 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.
|
Strom |
Počet rozhodnutí |
|
|
x 1 |
|
|
|
x2 |
||
|
x 3 |
||
|
… |
V prípade ťažkostí s uvažovaním niyah a stavebníctvo derevu riešení, pomocou ktorých môžete hľadať riešenie 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) |
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kde J, K, L, M, N sú booleovské premenné?
Vysvetlenie.
Výraz (N ∨ ¬N) platí pre ľubovoľné N, takže
J ∧ ¬K ∧ L ∧ ¬M = 0.
Aplikujte negáciu na obe strany logickej rovnice a použite De Morganov zákon ¬ (A ∧ B) = ¬ A ∨ ¬ B. Dostaneme ¬J ∨ K ∨ ¬L ∨ M = 1.
Logický súčet sa rovná 1, ak sa aspoň jeden z jeho základných výrokov rovná 1. Výslednú rovnicu teda spĺňa akákoľvek kombinácia logických premenných, s výnimkou prípadu, keď sa všetky veličiny zahrnuté v rovnici rovnajú 0. Každá zo 4 premenných sa môže rovnať buď 1 alebo 0, preto možné kombinácie 2 2 2 2 = 16. Rovnica má teda 16 −1 = 15 riešení.
Zostáva poznamenať, že nájdených 15 riešení zodpovedá ktorejkoľvek z dvoch možných hodnôt hodnôt logickej premennej N, takže pôvodná rovnica má 30 riešení.
odpoveď: 30
Koľko rôznych riešení má rovnica
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
kde J, K, L, M, N sú booleovské premenné?
Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt J, K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Vysvetlenie.
Používame vzorce A → B = ¬A ∨ B a ¬(A ∨ B) = ¬A ∧ ¬B
Zvážte prvý podvzorec:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Zvážte druhý podvzorec
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬
Zvážte tretí podvzorec
1) M → J = 1 teda
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Kombinovať:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 teda 4 riešenia.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Kombinovať:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L, takže existujú 4 riešenia.
c) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Odpoveď: 4 + 4 = 8.
odpoveď: 8
Koľko rôznych riešení má rovnica
((K ∨ L) → (L ∧ M ∧ N)) = 0
kde K, L, M, N sú booleovské premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Vysvetlenie.
Prepíšme rovnicu pomocou jednoduchšieho zápisu operácií:
((K + L) -> (L M N)) = 0
1) z pravdivostnej tabuľky operácie „implikácia“ (pozri prvý problém) vyplýva, že táto rovnosť je pravdivá vtedy a len vtedy, ak súčasne
K + L = 1 a LMN = 0
2) z prvej rovnice vyplýva, že aspoň jedna z premenných, K alebo L, sa rovná 1 (alebo obe spolu); takže zvážte tri prípady
3) ak K = 1 a L = 0, potom druhá rovnosť platí pre ľubovoľné M a N; keďže existujú 4 kombinácie dvoch boolovských premenných (00, 01, 10 a 11), máme 4 rôzne riešenia
4) ak K = 1 a L = 1, potom druhá rovnosť platí pre M · N = 0; sú 3 takéto kombinácie (00, 01 a 10), máme ďalšie 3 riešenia
5) ak K = 0, potom nevyhnutne L = 1 (z prvej rovnice); v tomto prípade je druhá rovnosť splnená pri М · N = 0; sú 3 takéto kombinácie (00, 01 a 10), máme ďalšie 3 riešenia
6) celkovo dostaneme 4 + 3 + 3 = 10 riešení.
odpoveď: 10
Koľko rôznych riešení má rovnica
(K ∧ L) ∨ (M ∧ N) = 1
Vysvetlenie.
Výraz je pravdivý v troch prípadoch, keď (K ∧ L) a (M ∧ N) sú 01, 11, 10, v tomto poradí.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N sú 1 a K a L sú ľubovoľné, okrem oboch 1. Preto 3 riešenia.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 roztok.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 riešenia.
odpoveď: 7.
odpoveď: 7
Koľko rôznych riešení má rovnica
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
kde X, Y, Z, P sú booleovské premenné? Odpoveď nemusí uvádzať všetky rôzne súbory hodnôt, pre ktoré platí táto rovnosť. Ako odpoveď je potrebné uviesť iba počet takýchto súprav.
Vysvetlenie.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Logické OR je nepravdivé iba v jednom prípade: keď sú oba výrazy nepravdivé.
teda
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Preto existuje len jedno riešenie rovnice.
odpoveď: 1
Koľko rôznych riešení má rovnica
(K ∨ L) ∧ (M ∨ N) = 1
kde K, L, M, N sú booleovské premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď je potrebné uviesť iba počet takýchto súprav.
Vysvetlenie.
Logické AND je pravdivé iba v jednom prípade: keď sú všetky výrazy pravdivé.
K ∨ L = 1, M ∨ N = 1.
Každá z rovníc dáva 3 riešenia.
Uvažujme rovnicu A ∧ B = 1, ak A aj B nadobúdajú pravdivé hodnoty v troch prípadoch, potom má rovnica vo všeobecnosti 9 riešení.
Preto je odpoveď 9.
odpoveď: 9
Koľko rôznych riešení má rovnica
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
kde A, B, C, D sú booleovské premenné?
Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt A, B, C, D, pre ktoré platí táto rovnosť. Ako odpoveď musíte zadať počet takýchto sád.
Vysvetlenie.
Logické „ALEBO“ je pravdivé, keď je pravdivé aspoň jedno z tvrdení.
(D ∧ ¬D) = 0 pre ľubovoľné D.
teda
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, čo nám dáva 3 riešenia pre každé D.
(D ∧ ¬ D)=0 pre ľubovoľné D, čo nám dáva dve riešenia (pre D = 1, D = 0).
Preto: celkové riešenia 2*3 = 6.
Celkom 6 riešení.
odpoveď: 6
Koľko rôznych riešení má rovnica
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
kde K, L, M, N sú booleovské premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď je potrebné uviesť iba počet takýchto súprav.
Vysvetlenie.
Použite negáciu na obe strany rovnice:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logické ALEBO je pravdivé v troch prípadoch.
Možnosť 1.
K ∧ L ∧ M = 1, potom K, L, M = 1 a ¬L ∧ M ∧ N = 0. Akékoľvek N, teda 2 riešenia.
Možnosť 2.
¬L ∧ M ∧ N = 1, potom N, M = 1; L = 0, K ľubovoľné, teda 2 riešenia.
Preto je odpoveď 4.
odpoveď: 4
A, B a C sú celé čísla, pre ktoré je výrok pravdivý
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Čomu sa rovná B, ak A = 45 a C = 43?
Vysvetlenie.
1) ¬(A = B); (A > B) -> (B > C); (B>A) -> (C>B);
2) tieto jednoduché príkazy sú spojené operáciou ∧ (AND, spojka), to znamená, že musia byť vykonané súčasne;
3) z ¬(А = B)=1 okamžite vyplýva, že А B;
4) predpokladajme, že A > B, potom z druhej podmienky dostaneme 1→(B > C)=1; tento výraz môže byť pravdivý vtedy a len vtedy, ak B > C = 1;
5) teda máme A > B > C, tejto podmienke zodpovedá len číslo 44;
6) pre každý prípad skontrolujte variant A 0 →(B > C)=1;
tento výraz platí pre akékoľvek B; teraz sa pozrieme na tretiu podmienku, dostaneme
tento výraz môže byť pravdivý vtedy a len vtedy, ak C > B, a tu máme rozpor, pretože neexistuje také číslo B, pre ktoré by C > B > A.
odpoveď: 44.
odpoveď: 44
Vytvorte pravdivostnú tabuľku pre logickú funkciu
X = (A ↔ B) ∨ ¬ (A → (B ∨ C))
v ktorom stĺpec hodnôt argumentu A je binárny zápis čísla 27, stĺpec hodnôt argumentu B je číslo 77, stĺpec hodnôt argumentu C je číslo 120. Číslo v stĺpci sa píše zhora nadol od najvýznamnejšej číslice po najmenej významnú (vrátane nulovej sady). Preveďte výslednú binárnu reprezentáciu hodnôt funkcie X do desiatkovej číselnej sústavy.
Vysvetlenie.
Rovnicu napíšeme pomocou jednoduchšieho zápisu operácií:
1) toto je výraz s tromi premennými, takže v pravdivostnej tabuľke budú riadky; preto binárny zápis čísel, ktorými sú stĺpce tabuľky A, B a C zostavené, musí pozostávať z 8 číslic
2) čísla 27, 77 a 120 preložíme do dvojkovej sústavy, pričom zadanie ihneď doplníme na 8 znakov s nulami na začiatku čísel
3) je nepravdepodobné, že budete môcť okamžite zapísať hodnoty funkcie X pre každú kombináciu, takže je vhodné pridať do tabuľky ďalšie stĺpce na výpočet medzivýsledkov (pozri tabuľku nižšie)
| A | V | S | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) vyplňte stĺpce tabuľky:
| A | V | S | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
hodnota je 1 iba v tých riadkoch, kde A = B
hodnota je 1 v tých riadkoch, kde buď B alebo C = 1
hodnota je 0 len v tých riadkoch, kde A = 1 a B + C = 0
hodnota je inverzná hodnota predchádzajúceho stĺpca (0 sa nahradí 1 a 1 sa nahradí 0)
výsledok X (posledný stĺpec) je logický súčet dvoch stĺpcov a
5) aby sme dostali odpoveď, vypíšeme bity zo stĺpca X zhora nadol:
6) preložte toto číslo do desiatkovej sústavy:
odpoveď: 171
Aké je najväčšie celé číslo X, pre ktoré platí výrok (10 (X+1)·(X+2))?
Vysvetlenie.
Rovnica je implikačná operácia medzi dvoma vzťahmi:
1) Samozrejme, tu môžete použiť rovnakú metódu ako v príklade 2208, ale v tomto prípade budete musieť vyriešiť kvadratické rovnice(nechcem…);
2) Všimnite si, že podľa podmienky nás zaujímajú iba celé čísla, takže sa môžete pokúsiť nejako transformovať pôvodný výraz a získať ekvivalentné vyhlásenie (presné hodnoty koreňov nás vôbec nezaujímajú!);
3) Zvážte nerovnosť: je zrejmé, že to môže byť kladné aj záporné číslo;
4) Je ľahké skontrolovať, či je výrok pravdivý pre všetky celé čísla v doméne a pre všetky celé čísla v doméne (aby nedošlo k zámene, je vhodnejšie použiť neprísne nerovnosti a , namiesto a );
5) Preto ho pre celé čísla možno nahradiť ekvivalentným výrazom
6) oblasť pravdivosti výrazu je spojením dvoch nekonečných intervalov;
7) Teraz zvážte druhú nerovnosť: je zrejmé, že to môže byť aj kladné aj záporné číslo;
8) V regióne je výrok pravdivý pre všetky celé čísla a v regióne - pre všetky celé čísla, preto ho pre celé čísla možno nahradiť ekvivalentným výrazom
9) oblasť pravdivosti výrazu je uzavretý interval;
10) Daný výraz platí všade okrem oblastí, kde a ;
11) Všimnite si, že hodnota už nesedí, pretože tam a , teda implikácia dáva 0;
12) Pri dosadzovaní 2, (10 (2+1) · (2+2)), alebo 0 → 0, ktorá podmienku spĺňa.
Takže odpoveď je 2.
odpoveď: 2
Aké je najväčšie celé číslo X, pre ktoré je výrok pravdivý?
(50 (X+1) (X+1))?
Vysvetlenie.
Aplikujte implikačnú transformáciu a transformujte výraz:
(50 (X+1) (X+1)) ⇔ ¬(X2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Logické OR je pravdivé, keď je pravdivé aspoň jedno logické tvrdenie. Po vyriešení oboch nerovností a pri zohľadnení toho, že vidíme, že najväčšie celé číslo, pre ktoré platí aspoň jedna z nich, je 7 (na obrázku je kladné riešenie druhej nerovnosti znázornené žltou a prvé modrou) .
odpoveď: 7
Zadajte hodnoty premenných K, L, M, N, pre ktoré je logický výraz
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
falošné. Napíšte svoju odpoveď ako reťazec 4 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.
Vysvetlenie.
Duplikuje úlohu 3584.
Odpoveď: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Vysvetlenie.
Aplikujme implikačnú transformáciu:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Použite negáciu na obe strany rovnice:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Poďme sa transformovať:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Preto M = 0, N = 0, zvážte teraz (¬K ∧ L ∨ M ∧ L):
skutočnosť, že M = 0, N = 0, znamená, že M ∧ L = 0, potom ¬K ∧ L = 1, t. j. K = 0, L = 1.
Odpoveď: 0100
Zadajte hodnoty premenných K, L, M, N, pre ktoré je logický výraz
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
falošné. 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.
Vysvetlenie.
Napíšme rovnicu pomocou jednoduchšieho zápisu operácií (podmienka „výraz je nepravdivý“ znamená, že sa rovná logickej nule):
1) z vyjadrenia podmienky vyplýva, že výraz musí byť nepravdivý len pre jednu množinu premenných
2) z pravdivostnej tabuľky operácie „implikácie“ vyplýva, že tento výraz je nepravdivý vtedy a len vtedy, keď súčasne
3) prvá rovnosť (logický súčin sa rovná 1) je pravdivá vtedy a len vtedy a ; z toho vyplýva (logický súčet sa rovná nule), čo môže byť len vtedy, keď ; teda už sme definovali tri premenné
4) z druhej podmienky, , for a získame .
Duplicitná úloha
Odpoveď: 1000
Uveďte hodnoty logických premenných P, Q, S, T, pre ktoré je logický výraz
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) je nepravda.
Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných P, Q, S, T (v tomto poradí).
Vysvetlenie.
(1) (Р ∨ ¬Q) = 0
(2) (Q → (S ∨ T)) = 0
(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Použiť implikačnú transformáciu:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Odpoveď: 0100
Zadajte hodnoty premenných K, L, M, N, pre ktoré je logický výraz
(K → M) ∨ (L ∧ K) ∨ ¬N
falošné. 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.
Vysvetlenie.
Logické "ALEBO" je nepravdivé vtedy a len vtedy, ak sú oba výroky nepravdivé.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Aplikujme implikačnú transformáciu na prvý výraz:
¬K ∨ M = 0 => K = 1, M = 0.
Zvážte druhý výraz:
(L ∧ K) ∨ ¬N = 0 (pozri výsledok prvého výrazu) => L ∨ ¬N = 0 => L = 0, N = 1.
Odpoveď: 1001.
Odpoveď: 1001
Zadajte hodnoty premenných K, L, M, N, pre ktoré je logický výraz
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
pravda. 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.
Vysvetlenie.
Logické "AND" je pravdivé vtedy a len vtedy, ak sú pravdivé oba výroky.
1) (K → M) = 1 Použiť implikačnú transformáciu: ¬K ∨ M = 1
2) (K → ¬M) = 1 Použiť implikačnú transformáciu: ¬K ∨ ¬M = 1
To znamená, že K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Odpoveď: 0011
Je známe, že pre celé čísla X, Y a Z je tvrdenie pravdivé
(Z Čo sa rovná Z, ak X=25 a Y=48?
Vysvetlenie.
Dosadením čísel dostaneme, že Z = 47.
Všimnime si, že toto zložený výrok pozostáva z troch jednoduchých
1) (Z 2) tieto jednoduché výroky sú spojené operáciou ∧ (AND, spojka), to znamená, že musia byť vykonané súčasne.
3) od ¬(Z+1 24 a od ¬(Z+1 47.
4) z (Z Z Odpoveď: 47.
odpoveď: 47
A, B a C sú celé čísla, pre ktoré platí výrok:
(C Čo sa rovná C, ak A=45 a B=18?
Vysvetlenie.
Logické "AND" je pravdivé vtedy a len vtedy, ak sú pravdivé oba výroky.
Nahraďte hodnoty čísel vo výraze:
1) (C(C2)¬(C+1, C ≥ 44.
3) ¬(C+1, C ≥ 17.
Z bodov 2) a 1) vyplýva, že C
odpoveď: 44
¬(A = B) ∧ ((B A)) ∧ ((A 2C))
Čomu sa rovná A, ak C = 8 a B = 18?.
Vysvetlenie.
Logické "AND" je pravdivé vtedy a len vtedy, ak sú pravdivé oba výroky.
1) ¬(A \u003d B) \u003d 1, teda A ≠ 18 \u003d 1.
2) ((B A)) Použite implikačnú transformáciu: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Použite implikačnú transformáciu: (A > 18) ∨ (A > 16) = 1
Z 2) a 3) vyplýva, že (18 > A) a (A > 16), pretože inak vzniká rozpor A = 17.
odpoveď: 17
A, B a C sú celé čísla, pre ktoré je výrok pravdivý
¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
Čomu sa rovná B, ak A = 45 a C = 18?
Vysvetlenie.
Logické „A“ je pravdivé iba vtedy, keď sú pravdivé všetky výroky.
Ako vyriešiť niektoré problémy v častiach A a B skúšky z informatiky
Lekcia číslo 3. Logika. Logické funkcie. Riešenie rovníc
Logike návrhov sa venuje veľké množstvo úloh USE. Na vyriešenie väčšiny z nich stačí poznať základné zákony výrokovej logiky, znalosť pravdivostných tabuliek logických funkcií jednej a dvoch premenných. Uvediem základné zákony výrokovej logiky.
Reprezentácia logických funkcií
Akákoľvek logická funkcia n premenných - F(x 1 , x 2 , ... x n) môže byť definovaná pravdivostnou tabuľkou. Takáto tabuľka obsahuje 2 n množín premenných, pre každú z nich je špecifikovaná hodnota funkcie na tejto množine. Táto metóda je dobrá, keď je počet premenných relatívne malý. Dokonca aj pre n > 5 sa zobrazenie stáva zle viditeľné.
Ďalším spôsobom je definovať funkciu nejakým vzorcom pomocou známych pomerne jednoduchých funkcií. Systém funkcií (f 1 , f 2 , … f k ) sa nazýva úplný, ak ľubovoľnú logickú funkciu možno vyjadriť vzorcom obsahujúcim iba funkcie f i.
Systém funkcií (¬, ˄, ˅) je kompletný. Zákony 9 a 10 sú príkladmi toho, ako sa implikácia a identita vyjadrujú prostredníctvom negácie, konjunkcie a disjunkcie.
V skutočnosti je kompletný aj systém dvoch funkcií – negácie a konjunkcie alebo negácie a disjunkcie. Reprezentácie vyplývajú z De Morganových zákonov, ktoré umožňujú vyjadrenie konjunkcie prostredníctvom negácie a disjunkcie, a teda vyjadrenie disjunkcie prostredníctvom negácie a konjunkcie:
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Paradoxne je systém pozostávajúci len z jednej funkcie kompletný. Existujú dve binárne funkcie – antikonjunkcia a antidisjunkcia, nazývaná Pierceov šíp a Schaefferov ťah, predstavujúci dutý systém.
Medzi základné funkcie programovacích jazykov zvyčajne patrí identita, negácia, konjunkcia a disjunkcia. V úlohách skúšky, spolu s týmito funkciami, je často implikácia.
Zvážte niekoľko jednoduché úlohy spojené s logickými funkciami.
Úloha 15:
Je uvedený fragment pravdivostnej tabuľky. Ktorá z troch uvedených funkcií zodpovedá tomuto fragmentu?
| x1 | x2 | x3 | x4 | F |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
Funkcia číslo 3.
Na vyriešenie problému potrebujete poznať pravdivostné tabuľky základných funkcií a mať na pamäti priority operácií. Pripomínam, že konjunkcia (logické násobenie) má vyššiu prioritu a vykonáva sa pred disjunkciou (logickým sčítaním). Pri výpočte je dobre vidieť, že funkcie s číslami 1 a 2 na tretej množine majú hodnotu 1 az tohto dôvodu nezodpovedajú fragmentu.
Úloha 16:
Ktoré z nasledujúcich čísel spĺňa podmienku:
(číslice začínajúce najvýznamnejšou číslicou v zostupnom poradí) → (číslo - párne) ˄ (najnižšia číslica - párne) ˄ (najvyššia číslica - nepárne)
Ak existuje niekoľko takýchto čísel, uveďte najväčšie.
Podmienka je splnená číslom 4.
Prvé dve čísla nespĺňajú podmienku z dôvodu, že najnižšia číslica je nepárna. Konjunkcia podmienok je nepravdivá, ak je jedna z podmienok konjunkcie nepravdivá. Pre tretie číslo nie je splnená podmienka pre najvyššiu číslicu. Pre štvrté číslo sú splnené podmienky kladené na vedľajšie a veľké číslice čísla. Prvý člen spojky je tiež pravdivý, pretože implikácia je pravdivá, ak je jej premisa nepravdivá, čo je tento prípad.
Problém 17: Dvaja svedkovia vypovedali takto:
Prvý svedok: Ak je A vinný, potom B je určite vinný a C je nevinný.
Druhý svedok: Dvaja sú vinní. A jeden zo zostávajúcich je určite vinný a vinný, ale neviem presne povedať kto.
Aké závery o vine A, B a C možno vyvodiť z dôkazov?
Odpoveď: Zo svedectva vyplýva, že A a B sú vinní, ale C je nevinný.
Riešenie: Samozrejme, odpoveď možno dať na základe zdravý rozum. Pozrime sa však na to, ako sa to dá urobiť striktne a formálne.
Prvá vec, ktorú musíte urobiť, je formalizovať vyhlásenia. Predstavme si tri booleovské premenné, A, B a C, z ktorých každá je pravdivá (1), ak je príslušný podozrivý vinný. Potom je výpoveď prvého svedka daná vzorcom:
A → (B ˄ ¬C)
Výpoveď druhého svedka je daná vzorcom:
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
Výpovede oboch svedkov sa považujú za pravdivé a predstavujú spojenie zodpovedajúcich vzorcov.
Zostavme pravdivostnú tabuľku pre tieto hodnoty:
| A | B | C | F1 | F2 | Ž 1 Ž 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Súhrnné dôkazy sú pravdivé iba v jednom prípade, čo vedie k jasnej odpovedi - A a B sú vinní a C je nevinný.
Aj z rozboru tejto tabuľky vyplýva, že výpoveď druhého svedka má väčšiu výpovednú hodnotu. Z pravdivosti jeho svedectva vyplývajú len dve veci. možné možnosti A a B sú vinní a C je nevinný, alebo A a C sú vinní a B je nevinný. Výpoveď prvého svedka je menej vypovedajúca – existuje 5 rôznych možností, ktoré zodpovedajú jeho výpovedi. Spoločne výpovede oboch svedkov dávajú jednoznačnú odpoveď o vine podozrivých.
Logické rovnice a sústavy rovníc
Nech F(x 1 , x 2 , …x n) je logická funkcia n premenných. Logická rovnica je:
F(x 1, x 2, ... x n) \u003d C,
Konštanta C má hodnotu 1 alebo 0.
Logická rovnica môže mať 0 až 2n rôznych riešení. Ak sa C rovná 1, potom riešeniami sú všetky tie množiny premenných z pravdivostnej tabuľky, na ktorých má funkcia F hodnotu true (1). Zostávajúce množiny sú riešenia rovnice pre C rovné nule. Vždy môžeme brať do úvahy iba rovnice tvaru:
F(x 1, x 2, ... x n) = 1
Vskutku, nech je uvedená rovnica:
F(x1, x2, ...xn) = 0
V tomto prípade môžete prejsť na ekvivalentnú rovnicu:
¬F(x 1 , x 2 , …x n) = 1
Zvážte systém k logických rovníc:
F 1 (x 1, x 2, ... x n) \u003d 1
F 2 (x 1, x 2, ... x n) \u003d 1
Fk (x1, x2, ...xn) = 1
Riešením sústavy je množina premenných, na ktorej sú splnené všetky rovnice sústavy. Pokiaľ ide o logické funkcie, na získanie riešenia systému logických rovníc je potrebné nájsť množinu, na ktorej platí logická funkcia Ф, ktorá predstavuje spojenie pôvodných funkcií F:
Ф = F 1 ˄ F 2 ˄ … F k
Ak je počet premenných malý, napríklad menší ako 5, potom nie je ťažké zostaviť pravdivostnú tabuľku pre funkciu Ф, ktorá vám umožní povedať, koľko riešení má systém a aké sú množiny, ktoré dávajú riešenia.
V niektorých úlohách Jednotnej štátnej skúšky z hľadania riešení sústavy logických rovníc dosahuje počet premenných hodnotu 10. Potom sa zostavenie pravdivostnej tabuľky stáva takmer neriešiteľnou úlohou. Riešenie problému si vyžaduje iný prístup. Pre ľubovoľný systém rovníc neexistuje všeobecným spôsobom, čo sa líši od enumerácie, ktorá umožňuje takéto problémy riešiť.
V problémoch navrhnutých na skúške je riešenie zvyčajne založené na zohľadnení špecifík sústavy rovníc. Opakujem, okrem enumerácie všetkých variantov množiny premenných neexistuje všeobecný spôsob riešenia problému. Riešenie musí byť postavené na základe špecifík systému. Často je užitočné vykonať predbežné zjednodušenie systému rovníc pomocou známych logických zákonov. Ďalšia užitočná technika na riešenie tohto problému je nasledovná. Nezaujímajú nás všetky množiny, ale iba tie, na ktorých má funkcia Φ hodnotu 1. Namiesto zostrojenia kompletná tabuľka v skutočnosti vytvoríme jeho analóg - binárny rozhodovací strom. Každá vetva tohto stromu zodpovedá jednému riešeniu a špecifikuje množinu, na ktorej má funkcia Ф hodnotu 1. Počet vetiev v rozhodovacom strome sa zhoduje s počtom riešení sústavy rovníc.
Čo je to binárny rozhodovací strom a ako sa vytvára, vysvetlím na príkladoch niekoľkých úloh.
Problém 18
Koľko rôznych množín hodnôt booleovských premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existuje v systéme dvoch rovníc?
Odpoveď: Systém má 36 rôznych riešení.
Riešenie: Sústava rovníc obsahuje dve rovnice. Nájdite počet riešení pre prvú rovnicu v závislosti od 5 premenných – x 1 , x 2 , …x 5 . Prvú rovnicu možno považovať za sústavu 5 rovníc. Ako sa ukázalo, systém rovníc v skutočnosti predstavuje spojenie logických funkcií. Platí aj opačné tvrdenie – konjunkciu podmienok možno považovať za sústavu rovníc.
Zostavme rozhodovací strom pre implikáciu (x1→ x2), prvý člen konjunkcie, ktorý možno považovať za prvú rovnicu. Takto vyzerá grafické znázornenie tohto stromu:
Strom má dve úrovne premenné rovnice. Prvá úroveň popisuje prvú premennú X 1 . Dve vetvy tejto úrovne odrážajú možné hodnoty tejto premennej - 1 a 0. Na druhej úrovni vetvy stromu odrážajú iba tie možné hodnoty premennej X 2, pre ktoré má rovnica hodnotu true. Keďže rovnica definuje implikáciu, vetva, na ktorej má X 1 hodnotu 1, vyžaduje, aby na tejto vetve mala X 2 hodnotu 1. Vetva, na ktorej má X 1 hodnotu 0, generuje dve vetvy s hodnotami X 2 rovnými 0 a 1 Zostrojený strom špecifikuje tri riešenia, na ktorých implikácia X 1 → X 2 nadobúda hodnotu 1. Na každej vetve je vypísaná zodpovedajúca množina hodnôt premenných, ktorá dáva riešenie rovnice.
Tieto množiny sú: ((1, 1), (0, 1), (0, 0))
Pokračujme v budovaní rozhodovacieho stromu pridaním nasledujúcej rovnice, nasledujúcej implikácie X 2 → X 3 . Špecifikom nášho systému rovníc je, že každá nová rovnica systému používa jednu premennú z predchádzajúcej rovnice, pričom pridáva jednu novú premennú. Keďže premenná X 2 už má hodnoty v strome, potom na všetkých vetvách, kde má premenná X 2 hodnotu 1, bude mať premenná X 3 tiež hodnotu 1. Pre takéto vetvy pokračuje konštrukcia stromu ďalšiu úroveň, ale neobjavia sa žiadne nové vetvy. Jediná vetva, kde premenná X 2 má hodnotu 0, poskytne vetvu na dve vetvy, kde premenná X 3 získa hodnoty 0 a 1. Každé pridanie novej rovnice teda vzhľadom na jej špecifickosť pridáva jednu Riešenie. Pôvodná prvá rovnica:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
má 6 riešení. Takto vyzerá úplný rozhodovací strom pre túto rovnicu:
Druhá rovnica nášho systému je podobná prvej:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
Jediný rozdiel je v tom, že rovnica používa premenné Y. Aj táto rovnica má 6 riešení. Pretože každé premenné riešenie X i možno kombinovať s každým premenným riešením Y j , potom celkový počet riešení je 36.
Všimnite si, že vytvorený rozhodovací strom udáva nielen počet riešení (podľa počtu vetiev), ale aj samotné riešenia, napísané na každej vetve stromu.
Problém 19
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
Táto úloha je modifikáciou predchádzajúcej úlohy. Rozdiel je v tom, že sa pridáva ďalšia rovnica, ktorá spája premenné X a Y.
Z rovnice X 1 → Y 1 vyplýva, že keď má X 1 hodnotu 1 (existuje jedno takéto riešenie), potom má Y 1 hodnotu 1. Existuje teda jedna množina, na ktorej majú X 1 a Y 1 hodnoty 1. Keď sa X 1 rovná 0, Y 1 môže mať akúkoľvek hodnotu, 0 aj 1. Preto každá množina, kde sa X 1 rovná 0 a existuje 5 takýchto množín, zodpovedá všetkým 6 množinám s premennými Y. Preto , celkový počet riešení je 31 .
Problém 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Riešenie: Pamätajúc si základnú ekvivalenciu, zapíšeme našu rovnicu ako:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
Cyklický reťazec implikácií znamená, že premenné sú identické, takže naša rovnica je ekvivalentná:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
Táto rovnica má dve riešenia, keď všetky X i sú 1 alebo 0.
Problém 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Riešenie: Rovnako ako v úlohe 20 prejdeme od cyklických implikácií k identitám prepísaním rovnice do tvaru:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Zostavme rozhodovací strom pre túto rovnicu: 
Problém 22
Koľko riešení má nasledujúca sústava rovníc?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0
((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X6)) = 0
((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0
((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0
odpoveď: 64
Riešenie: Poďme z 10 premenných na 5 premenných zavedením nasledujúcej zmeny premenných:
Y1 = (Xi = X2); Y2 \u003d (X3 ≡ X 4); Y3 = (X5 = X6); Y 4 \u003d (X 7 ≡ X 8); Y5 \u003d (X9 = X 10);
Potom bude mať prvá rovnica tvar:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
Rovnicu možno zjednodušiť tak, že ju napíšeme takto:
(Yi = Y2) = 0
Po prechode na tradičnú formu zapíšeme systém po zjednodušeniach vo forme:
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
Rozhodovací strom pre tento systém je jednoduchý a pozostáva z dvoch vetiev so striedajúcimi sa hodnotami premenných:
Ak sa vrátime k pôvodným premenným X, všimnite si, že každá hodnota premennej Y zodpovedá 2 hodnotám premenných X, takže každé riešenie v premenných Y generuje 2 5 riešení v premenných X. Dve vetvy generujú 2 * 2 5 riešení , takže celkový počet riešení je 64.
Ako vidíte, každá úloha na riešenie sústavy rovníc si vyžaduje svoj vlastný prístup. Bežným trikom je vykonávanie ekvivalentných transformácií na zjednodušenie rovníc. Bežnou technikou je konštrukcia rozhodovacích stromov. Použitý prístup čiastočne pripomína konštrukciu pravdivostnej tabuľky s tou zvláštnosťou, že nie sú zostrojené všetky množiny možných hodnôt premenných, ale iba tie, na ktorých má funkcia hodnotu 1 (true). Často v navrhovaných úlohách nie je potrebné stavať plný strom riešenia, pretože už v počiatočnom štádiu je možné stanoviť pravidelnosť výskytu nových pobočiek na každej ďalšej úrovni, ako sa to stalo napríklad v probléme 18.
Vo všeobecnosti sú úlohy na hľadanie riešení sústavy logických rovníc dobrými matematickými cvičeniami.
Ak je problém manuálne vyriešiť, môžete jeho vyriešenie zveriť počítaču napísaním vhodného programu na riešenie rovníc a sústav rovníc.
Je ľahké napísať takýto program. Takýto program sa ľahko vyrovná so všetkými úlohami ponúkanými v skúške.
Napodiv, ale úloha nájsť riešenia systémov logických rovníc je náročná aj pre počítač, ukazuje sa, že počítač má svoje limity. Počítač si bez problémov poradí s úlohami, kde je počet premenných 20-30, no nad väčšími úlohami začne dlho rozmýšľať. Ide o to, že funkcia 2 n, ktorá udáva počet množín, je exponent, ktorý rýchlo rastie s n. Tak rýchlo, že bežný osobný počítač nezvládne úlohu so 40 premennými za deň.
C# program na riešenie logických rovníc
Napísať program na riešenie logických rovníc je užitočné z mnohých dôvodov, už len preto, že ho možno použiť na kontrolu správnosti vlastného riešenia úloh testu USE. Ďalším dôvodom je, že takýto program je výborným príkladom programovacieho problému, ktorý spĺňa požiadavky na problémy kategórie C v USE.
Myšlienka vytvorenia programu je jednoduchá - je založená na úplnom vymenovaní všetkých možných množín premenných hodnôt. Keďže pre danú logickú rovnicu alebo sústavu rovníc je známy počet premenných n, je známy aj počet množín - 2 n , ktoré je potrebné roztriediť. Pomocou základných funkcií jazyka C# - negácie, disjunkcie, konjunkcie a identity je jednoduché napísať program, ktorý pre danú množinu premenných vypočíta hodnotu logickej funkcie zodpovedajúcej logickej rovnici alebo sústave rovníc.
V takomto programe musíte zostaviť cyklus podľa počtu množín, v tele cyklu, podľa čísla množiny, vytvoriť samotnú množinu, vypočítať hodnotu funkcie na tejto množine a ak sa táto hodnota rovná do 1, potom množina dáva riešenie rovnice.
Jediný problém, ktorý vzniká pri implementácii programu, súvisí s úlohou vytvoriť súbor premenných hodnôt samotným nastaveným číslom. Krása tejto úlohy spočíva v tom, že táto zdanlivo ťažká úloha v skutočnosti vedie k jednoduchej úlohe, ktorá sa už opakovane objavila. V skutočnosti stačí pochopiť, že množina hodnôt premenných zodpovedajúcich číslu i, pozostávajúca z núl a jednotiek, predstavuje binárne znázornenie čísla i. Zložitá úloha získania množiny hodnôt premenných stanoveným číslom sa teda redukuje na dobre známy problém prevodu čísla do binárneho systému.
Takto vyzerá funkcia C#, ktorá rieši náš problém:
///
/// program na počítanie počtu riešení
/// logická rovnica (systém rovníc)
///
///
/// logická funkcia - metóda,
/// ktorej podpis nastavuje delegát DF
///
/// počet premenných
///
static int RiešiťRovnice (DF zábava, int n)
sada bool = new bool[n];
int m = (int)Math.Pow(2, n); //počet sád
int p = 0, q = 0, k = 0;
//Úplný zoznam podľa počtu sád
pre (int i = 0; i< m; i++)
//Vytvorenie ďalšej množiny — množiny,
//dané binárnym vyjadrením čísla i
pre (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Výpočet hodnoty funkcie na súprave
Na pochopenie programu dúfam, že vysvetlenia myšlienky programu a komentáre v jeho texte budú stačiť. Pozastavím sa len pri vysvetlení nadpisu vyššie uvedenej funkcie. Funkcia SolveEquations má dva vstupné parametre. Parameter fun špecifikuje logickú funkciu zodpovedajúcu riešenej rovnici alebo sústave rovníc. Parameter n určuje číslo funkčné premenné zábava. Výsledkom je, že funkcia SolveEquations vráti počet riešení logickej funkcie, teda počet množín, na ktorých sa funkcia vyhodnotí ako true.
Pre školákov je zvykom, že pre niektorú funkciu F(x) je vstupným parametrom x premenná aritmetického, reťazcového alebo booleovského typu. V našom prípade je použitá výkonnejšia konštrukcia. Funkcia SolveEquations označuje funkcie vyššieho rádu - funkcie typu F(f), ktorých parametrami môžu byť nielen jednoduché premenné, ale aj funkcie.
Trieda funkcií, ktoré možno odovzdať ako parameter funkcii SolveEquations, je definovaná takto:
delegovať bool DF(bool vars);
Táto trieda zahŕňa všetky funkcie, ktoré sa odovzdávajú ako parameter množiny hodnôt booleovských premenných špecifikovaných poľom vars. Výsledkom je boolovská hodnota predstavujúca hodnotu funkcie v tejto množine.
Na záver uvediem program, v ktorom funkcia SolveEquations slúži na riešenie viacerých sústav logických rovníc. Funkcia SolveEquations je súčasťou nasledujúcej triedy ProgramCommon:
trieda ProgramCommon
delegovať bool DF(bool vars);
static void Main (reťazcové argumenty)
Console.WriteLine("Funkcia a riešenia - " +
SolveEquations(FunAnd, 2));
Console.WriteLine("Funkcia má 51 riešení - " +
SolveEquations(Fun51, 5));
Console.WriteLine("Funkcia má 53 riešení - " +
SolveEquations(Zábava53, 10));
statický bool FunAnd(bool vars)
return vars && vars;
statický bool Fun51 (bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
statický bool Fun53 (bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vars) || (vars == vars)));
Takto vyzerajú výsledky riešenia tohto programu:
10 úloh na samostatnú prácu
| x1 | x2 | x3 | x4 | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Ktorá z týchto troch funkcií zodpovedá tomuto fragmentu:
Odpovede na úlohy:
