Grafické riešenie sústav logických rovníc. Metódy riešenia sústav logických rovníc

Tento materiál obsahuje prezentáciu, ktorá predstavuje metódy riešenia logické rovnice a sústavy 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 úloh jednotnej štátnej skúšky. Prezentácia môže byť užitočná pri vyučovaní na tému „Logika“ v špecializovaných triedach, ako aj pri príprave na jednotnú štátnu skúšku.

Stiahnuť ▼:

Náhľad:

Ak chcete použiť ukážky prezentácií, vytvorte si účet ( účtu) Google a prihláste sa: https://accounts.google.com

Popisy snímok:

Riešenie úlohy B15 (systémy logických rovníc) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18. novembra 2013, Saratov

Úloha B15 je jednou z najťažších na Jednotnej štátnej skúške z informatiky!!! Testujú sa tieto zručnosti: konvertovať výrazy obsahujúce logické premenné; opísať v prirodzenom jazyku množinu hodnôt logických premenných, pre ktoré je daná množina logických premenných pravdivá; spočítajte počet binárnych množín, ktoré spĺňajú dané podmienky. Najťažšia vec je, pretože... neexistujú žiadne formálne pravidlá, ako to urobiť, vyžaduje si to dohady.

Bez čoho sa nezaobídeš!

Symboly spojenie: A /\ B , A  B , AB , A & B, A a B disjunkcia: A \ / B , A + B , A | B , A alebo B negácia:  A , A, nie A ekvivalencia: A  B, A  B, A  B bez „alebo“: A  B , A xor B

Metóda nahradenia premennej Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x9, x10 existuje, ktoré spĺňajú všetky podmienky uvedené nižšie: ((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, pre ktoré tento systém rovnosti platí. 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. Systémová analýza ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 0 1 0 Т1 .Do. 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 – dvojice (0,0) a (1,1).

Krok 3. Počítanie počtu riešení. Každé t má 2 riešenia, počet ts je 5. Teda. pre premenné t je 2 5 = 32 riešení. Ale pre každé t zodpovedá dvojica riešení x, t.j. pôvodný systém má 2*32 = 64 riešení. odpoveď: 64

Spôsob eliminácie časti riešení Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x5, y1,y2,..., y5 existuje, ktoré spĺňajú všetky nižšie uvedené 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, pre ktoré tento systém rovnosti platí. V odpovedi musí byť uvedený počet takýchto sád.

Riešenie. Krok 1. Postupné 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 Prvá rovnica je konjunkcia viacerých operácií implikácie, rovná 1, t.j. 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 do tabuľky:

Krok 1. Sekvenčné riešenie rovníc T.o. Získalo sa 6 sád riešení pre x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Podobne dospejeme 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. nemajú spoločné premenné, potom riešenie tohto systému rovníc (bez zohľadnenia tretej rovnice) bude 6 * 6 = 36 párov „X“ a „Y“. Uvažujme tretiu rovnicu: y5→ x5 =1 Riešením sú dvojice: 0 0 0 1 1 1 Dvojica nie je riešením: 1 0

Porovnajme získané riešenia Kde y5 =1, x5=0 nie je vhodné. takýchto dvojíc je 5. Počet riešení sústavy: 36-5= 31. Odpoveď: Bolo treba 31 kombinatoriky!!!

Metóda dynamického programovania Koľko rôzne riešenia má logickú rovnicu 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ť množstvo takýchto sád.

Krok riešenia 1. Analýza podmienky Vľavo v rovnici sú operácie implikácie zapísané postupne, priorita je rovnaká. Prepíšme: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Poznámka! Každá nasledujúca premenná nezávisí od predchádzajúcej, ale od výsledku predchádzajúcej implikácie!

Krok 2. Odhalenie vzoru Uvažujme prvú implikáciu, X 1 → X 2. Tabuľka pravdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednej 0 sme dostali 2 jednotky a z 1 dostali sme jednu 0 a jednu 1. Existuje len jedna 0 a tri 1, toto 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 Od dvoch 0 – dvoch 1, od každého 1 (sú 3) jedna 0 a jedna 1 (3+3)

Krok 3. Odvodenie vzorca T.o. 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 zľava doprava pre i = 6, pričom vypočítame počet núl a jednotiek pomocou vyššie uvedených vzorcov; tabuľka ukazuje, ako je nasledujúci stĺpec zostavený z 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 Zavedme zmenu premenných: J → K=A, M  N  L =B Prepíšme rovnicu 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 Toto je možné, ak: M= J=0 M=0, J=1 M=J=1

Riešenie Pretože A  B, potom Keď M=J=0 dostaneme 1 + K=0. Žiadne riešenia. Keď M=0, J=1 dostaneme 0 + K=0, K=0 a N a L sú ľubovoľné, 4 riešenia: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Riešenie 10. Keď 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 K N L 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šenia // 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].

Nech je logická funkcia n premenných. Logická rovnica vyzerá takto:

Konštanta C má hodnotu 1 alebo 0.

Logická rovnica môže mať od 0 po rôzne riešenia. Ak sa C rovná 1, potom riešeniami sú všetky tie množiny premenných z pravdivostnej tabuľky, pre ktoré funkcia F nadobúda hodnotu true (1). Zostávajúce množiny sú riešenia rovnice s C rovným nule. Vždy môžete zvážiť iba rovnice tvaru:

Vskutku, nech je uvedená rovnica:

V tomto prípade môžeme prejsť na ekvivalentnú rovnicu:

Zvážte systém k logických rovníc:

Riešením systému je množina premenných, na ktorých sú splnené všetky rovnice systému. 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í:

Ak je počet premenných malý, napríklad menší ako 5, potom nie je ťažké zostrojiť pre funkciu pravdivostnú tabuľku, ktorá nám umožňuje povedať, koľko riešení má systém a aké sú množiny poskytujúce riešenia.

V niektorých problémoch USE pri hľadaní riešení systému logických rovníc dosahuje počet premenných 10. Potom sa zostrojenie pravdivostnej tabuľky stáva takmer nemožnou úlohou. Riešenie problému si vyžaduje iný prístup. Pre ľubovoľný systém rovníc neexistujú žiadne všeobecná metóda, odlišnú od hrubej sily, 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 systému rovníc. Opakujem, okrem vyskúšania všetkých možností pre množinu premenných neexistuje všeobecný spôsob, ako problém vyriešiť. 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 zostavenia kompletnej pravdivostnej tabuľky postavíme jej 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.

Na príkladoch niekoľkých problémov vysvetlím, čo je binárny rozhodovací strom a ako sa vytvára.

Problém 18

Koľko rôznych množín hodnôt logických premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa systém 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í prvej rovnice v závislosti od 5 premenných - . Prvú rovnicu možno považovať za sústavu 5 rovníc. Ako bolo ukázané, sústava rovníc vlastne predstavuje konjunkciu 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 () - prvý člen konjunkcie, ktorý možno považovať za prvú rovnicu. Takto to vyzerá grafický obrázok tento strom

Strom pozostáva z dvoch úrovní podľa počtu premenných v rovnici. Prvá úroveň popisuje prvú premennú. 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, pre ktoré je rovnica vyhodnotená ako pravdivá. Keďže rovnica určuje implikáciu, vetva, na ktorej má hodnotu 1, vyžaduje, aby na tejto vetve bola hodnota 1. Vetva, na ktorej má hodnotu 0, generuje dve vetvy s hodnotami rovnými 0 a 1. strom špecifikuje tri riešenia, z ktorých implikácia nadobúda hodnotu 1. Na každej vetve je zapísaná zodpovedajúca množina premenných hodnôt, ktoré poskytujú 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. Špecifikom nášho systému rovníc je, že každá nová rovnica systému používa jednu premennú z predchádzajúcej rovnice a pridáva jednu novú premennú. Keďže premenná už má hodnoty v strome, potom na všetkých vetvách, kde má premenná hodnotu 1, bude mať premenná tiež hodnotu 1. Pre takéto vetvy pokračuje konštrukcia stromu na ďalšiu úroveň, ale neobjavia sa žiadne nové vetvy. Jedna vetva, kde má premenná hodnotu 0, sa rozvetví na dve vetvy, kde premenná získa hodnoty 0 a 1. Každé pridanie novej rovnice teda vzhľadom na jej špecifickosť pridáva jedno riešenie. Pôvodná prvá rovnica:

má 6 riešení. Takto vyzerá úplný rozhodovací strom pre túto rovnicu:

Druhá rovnica nášho systému je podobná prvej:

Jediný rozdiel je v tom, že rovnica používa premenné Y. Aj táto rovnica má 6 riešení. Pretože každé variabilné riešenie je možné kombinovať s každým variabilným riešením celkový počet Existuje 36 riešení.

Upozorňujeme, ž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 logických premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa všetky nižšie uvedené podmienky?

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 vyplýva, že keď má hodnotu 1 (existuje jedno takéto riešenie), potom má hodnotu 1. Existuje teda jedna množina, na ktorej a majú hodnoty 1. Keď sa rovná 0, môže majú akúkoľvek hodnotu, 0 aj 1. Preto každá množina s , ktorá sa rovná 0 a takýchto množín je 5, zodpovedá všetkým 6 množinám s premennými Y. Preto je celkový počet riešení 31.

Problém 20

Riešenie: Pamätajúc si základné ekvivalencie napíšeme našu rovnicu ako:

Cyklický reťazec implikácií znamená, že premenné sú identické, takže naša rovnica je ekvivalentná rovnici:

Táto rovnica má dve riešenia, keď sú všetky 1 alebo 0.

Problém 21

Koľko riešení má rovnica:

Riešenie: Rovnako ako v úlohe 20 prejdeme od cyklických implikácií k identitám, pričom rovnicu prepíšeme do tvaru:

Zostavme rozhodovací strom pre túto rovnicu:

Problém 22

Koľko riešení má nasledujúca sústava rovníc?

Ako vyriešiť niektoré problémy v častiach A a B skúšky z informatiky

Lekcia č. 3. Logika. Logické funkcie. Riešenie rovníc

Výrokovej logike je venované veľké množstvo úloh jednotnej štátnej skúšky. 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.

Komutivita disjunkcie a konjunkcie:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Distribučné právo týkajúce sa disjunkcie a konjunkcie:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Negácia negácie:
¬(¬a) ≡ a
konzistencia:
a ^ ¬а ≡ nepravda
Exkluzívna tretina:
a ˅ ¬а ≡ pravda
De Morganove zákony:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Zjednodušenie:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ pravda ≡ a
a ˄ nepravda ≡ nepravda
Absorpcia:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
Nahradenie implikácie
a → b ≡ ¬a ˅ b
Nahradenie identity
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Reprezentácia logických funkcií

Akákoľvek logická funkcia n premenných - F(x 1, x 2, ... x n) môže byť špecifikovaná pravdivostnou tabuľkou. Takáto tabuľka obsahuje 2n 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ý. Už 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íklady, ktoré demonštrujú, ako sa implikácia a identita vyjadrujú prostredníctvom negácie, konjunkcie a disjunkcie.

V skutočnosti je systém dvoch funkcií – negácie a konjunkcie alebo negácie a disjunkcie – tiež úplný. Z De Morganových zákonov vyplývajú myšlienky, ktoré umožňujú vyjadriť konjunkciu prostredníctvom negácie a disjunkcie, a teda vyjadriť disjunkciu 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á Peirceova šípka 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 problémoch s jednotnou štátnou skúškou sa spolu s týmito funkciami často nachádza implikácia.

Pozrime sa na niekoľko jednoduchých problémov týkajúcich sa logických funkcií.

Problém 15:

Je uvedený fragment pravdivostnej tabuľky. Ktorá z troch uvedených funkcií zodpovedá tomuto fragmentu?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

(X 1 → X 2) ˄ ¬ X 3 ˅ X 4
(¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Číslo funkcie 3.

Na vyriešenie problému musíte poznať pravdivostné tabuľky základných funkcií a pamätať si priority operácií. Pripomínam, že spojka (logické násobenie) má vyššiu prioritu a vykoná sa skôr ako disjunkcia (logické sčítanie). Pri výpočtoch je ľahké si všimnúť, že funkcie s číslami 1 a 2 v tretej množine majú hodnotu 1 az tohto dôvodu nezodpovedajú fragmentu.

Problém 16:

Ktoré z uvedených čísel spĺňa podmienku:

(číslice začínajúce od najvýznamnejšej číslice sú v zostupnom poradí) → (číslo - párne) ˄ (nízke číslice - párne) ˄ (vysoké číslice - nepárne)

Ak existuje niekoľko takýchto čísel, uveďte najväčšie.

13579
97531
24678
15386

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 nízke a vysoké číslice čísla. Prvý člen spojky je tiež pravdivý, pretože implikácia je pravdivá, ak je jej premisa nepravdivá, čo je prípad v tomto prípade.

Problém 17: Dvaja svedkovia poskytli nasledujúce svedectvo:

Prvý svedok: Ak je A vinný, potom B je ešte viac vinný a C je nevinný.

Druhý svedok: Dvaja sú vinní. A jeden zo zostávajúcich je určite vinný a vinný, ale nemôžem povedať, kto presne.

Aké závery o vine A, B a C možno vyvodiť z výpovede?

Odpoveď: Zo svedectva vyplýva, že A a B sú vinní a 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. Uveďme si tri logické premenné – A, B a C, z ktorých každá má hodnotu true (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ýpoveď oboch svedkov sa považuje za pravdivú a predstavuje spojenie zodpovedajúcich vzorcov.

Zostavme pravdivostnú tabuľku pre tieto hodnoty:

A	B	C	F 1	F 2	Ž 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ý.

Z rozboru tejto tabuľky tiež vyplýva, že výpoveď druhého svedka je informatívnejšia. Z pravdivosti jeho svedectva vyplývajú len dve 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 informatívna - je ich 5 rôzne možnosti, čo zodpovedá jeho svedectvu. Spoločne výpoveď oboch svedkov dáva jasnú 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 vyzerá takto:

F(x 1, x 2, …x n) = C,

Konštanta C má hodnotu 1 alebo 0.

Logická rovnica môže mať 0 až 2 n rôznych riešení. Ak sa C rovná 1, potom riešeniami sú všetky tie množiny premenných z pravdivostnej tabuľky, pre ktoré funkcia F nadobúda hodnotu true (1). Zostávajúce množiny sú riešenia rovnice s C rovným nule. Vždy môžete zvážiť iba rovnice tvaru:

F(x1, x2, ...xn) = 1

Vskutku, nech je uvedená rovnica:

F(x 1, x 2, ... x n) = 0

V tomto prípade môžeme prejsť na ekvivalentnú rovnicu:

¬F(x 1 , x 2 , …x n) = 1

Zvážte systém k logických rovníc:

F1 (x 1, x 2, ... x n) = 1

F2 (x 1, x 2, ... x n) = 1

Fk (x1, x2, ...xn) = 1

Ф = F 1 ˄ F 2 ˄ … F k

Ak je počet premenných malý, napríklad menší ako 5, potom nie je ťažké zostrojiť pravdivostnú tabuľku pre funkciu Ф, ktorá nám umožňuje povedať, koľko riešení má systém a aké sú množiny poskytujúce riešenia.

V niektorých problémoch USE pri hľadaní riešení systému logických rovníc dosahuje počet premenných 10. Potom sa zostrojenie pravdivostnej tabuľky stáva takmer nemožnou úlohou. Riešenie problému si vyžaduje iný prístup. Pre ľubovoľný systém rovníc neexistuje iná všeobecná metóda ako enumerácia, ktorá umožňuje riešenie takýchto problémov.

V problémoch navrhnutých na skúške je riešenie zvyčajne založené na zohľadnení špecifík systému rovníc. Opakujem, okrem vyskúšania všetkých možností pre množinu premenných neexistuje všeobecný spôsob, ako problém vyriešiť. 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 zostavenia kompletnej pravdivostnej tabuľky postavíme jej 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.

Na príkladoch niekoľkých problémov vysvetlím, čo je binárny rozhodovací strom a ako sa vytvára.

Problém 18

Koľko rôznych množín hodnôt logických premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa systém 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í prvej rovnice 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 bolo ukázané, sústava rovníc vlastne predstavuje konjunkciu logických funkcií. Platí to aj naopak: konjunkciu podmienok možno považovať za systém 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 pozostáva z dvoch úrovní podľa počtu premenných v rovnici. 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é platí rovnica. Keďže rovnica určuje implikáciu, vetva, na ktorej má X 1 hodnotu 1, vyžaduje, aby na tejto vetve X 2 mala hodnotu 1. Vetva, na ktorej má X 1 hodnotu 0, vytvára dve vetvy s hodnotami X 2 rovná 0 a 1 Zostrojený strom definuje 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 premenných hodnôt, ktoré dávajú 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 a 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 bude konštrukcia stromu pokračuje na ďalšiu úroveň, ale nové vetvy sa nezobrazujú. Jedna vetva, kde má premenná X 2 hodnotu 0, sa rozvetví na dve vetvy, kde premenná X 3 dostane hodnoty 0 a 1. Každé pridanie novej rovnice teda vzhľadom na jej špecifiká pridáva jedno 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í. Keďže každé riešenie pre premenné X i možno kombinovať s každým riešením pre premenné Y j , celkový počet riešení je 36.

Upozorňujeme, ž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 logických premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa všetky nižšie uvedené 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á aj 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 s X 1 rovná 0 a existuje 5 takýchto množín, zodpovedá všetkým 6 množinám s premennými Y. Celkový počet riešení je teda 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é ekvivalencie napíš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á rovnici:

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, pričom rovnicu prepíšeme 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?

((X1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X10)) = 0

odpoveď: 64

Riešenie: Presuňme sa z 10 premenných na 5 premenných zavedením nasledujúcej zmeny premenných:

Y1 = (Xi = X2); Y2 = (X3 = X4); Y3 = (X5 = X6); Y4 = (X7 = X8); Y5 = (X9 = X10);

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

Prechod na tradičnou formou, systém zapíšeme po zjednodušeniach v tvare:

¬(Y1≡Y2) = 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 pre každú hodnotu v premennej Y existujú 2 hodnoty v 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ý problém riešenia sústavy rovníc si vyžaduje svoj vlastný prístup. Všeobecná recepcia je vykonať ekvivalentné transformácie na zjednodušenie rovníc. Bežnou technikou je konštrukcia rozhodovacích stromov. Použitý prístup čiastočne pripomína zostrojenie pravdivostnej tabuľky s tou zvláštnosťou, že nie všetky množiny sú zostrojené možné hodnoty premenné, ale len tie, na ktorých funkcia nadobúda hodnotu 1 (pravda). V navrhovaných problémoch často nie je potrebné budovať úplný rozhodovací strom, pretože už počiatočná fáza je možné vytvoriť vzor vzhľadu nových vetiev na každej ďalšej úrovni, ako sa to urobilo napríklad v probléme 18.

Vo všeobecnosti sú problémy týkajúce sa hľadania riešení systému logických rovníc dobrými matematickými cvičeniami.

Ak sa problém ťažko rieši ručne, potom môžete jeho riešenie zveriť počítaču napísaním vhodného programu na riešenie rovníc a sústav rovníc.

Napísať takýto program nie je ťažké. Takýto program sa ľahko vyrovná so všetkými úlohami ponúkanými v jednotnej štátnej skúške.

Napodiv, úloha nájsť riešenia systémov logických rovníc je pre počítač náročná a ukazuje sa, že počítač má svoje limity. Počítač sa celkom ľahko vyrovná s úlohami, kde je počet premenných 20-30, ale začne dlho premýšľať o problémoch väčšia veľkosť. Faktom je, že funkcia 2 n, ktorá špecifikuje počet množín, je exponenciála, ktorá rýchlo rastie so zvyšujúcim sa n. Tak rýchlo, že bežný osobný počítač nezvládne za deň úlohu, ktorá má 40 premenných.

Program v jazyku C# na riešenie logických rovníc

Napísanie programu na riešenie logických rovníc je užitočné z mnohých dôvodov, už len preto, že ho môžete použiť na kontrolu správnosti vlastného riešenia úloh testu Unified State Exam. Ďalším dôvodom je, že takýto program je výborným príkladom programátorskej úlohy, ktorá spĺňa požiadavky na úlohy kategórie C v Jednotnej štátnej skúške.

Myšlienka zostavenia programu je jednoduchá - je založená na úplnom vyhľadávaní všetkých možných sád 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é vytriediť. Pomocou základných funkcií jazyka C# - negácie, disjunkcie, konjunkcie a identity nie je ťažké 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 vytvoriť slučku na základe počtu množín, v tele cyklu pomocou čísla množiny vytvoriť samotnú množinu, vypočítať hodnotu funkcie na tejto množine a ak toto hodnota je 1, potom množina dáva riešenie rovnice.

Jediný problém, ktorý vzniká pri implementácii programu, súvisí s úlohou generovania samotnej sady premenných hodnôt na základe nastaveného čísla. Krása tohto problému spočíva v tom, že táto zdanlivo ťažká úloha v skutočnosti spočíva v jednoduchom probléme, ktorý sa už mnohokrát vyskytol. V skutočnosti stačí pochopiť, že množina premenných hodnôt zodpovedajúcich číslu i, pozostávajúca z núl a jednotiek, predstavuje binárne znázornenie čísla i. Takže náročná úloha získanie množiny premenných hodnôt nastaveným číslom prichádza k dobre známemu problému prevodu čísla do binárneho systému.

Takto vyzerá funkcia v 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,

/// ktorého podpis určí delegát DF

///

/// počet premenných

/// počet riešení

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é vyhľadávanie podľa počtu sád

pre (int i = 0; i< m; i++)

//Vytvorenie ďalšej množiny - množiny,

//určené binárnym vyjadrením čísla i

pre (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Vypočítajte hodnotu funkcie na množine

Pre pochopenie programu dúfam, že vysvetlenia myšlienky programu a komentáre v jeho texte sú dostatočné. Sústredím sa len na vysvetlenie názvu danej funkcie. Funkcia SolveEquations má dva vstupné parametre. Parameter fun určuje 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 tých množín, na ktorých sa funkcia vyhodnotí ako true.

Pre školákov je bežné, že nejaká funkcia F(x) má vstupný parameter x, ktorý je premennou aritmetického, reťazcového alebo logického typu. V našom prípade je použitá výkonnejšia konštrukcia. Funkcia SolveEquations patrí medzi funkcie vyššia moc– 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 špecifikovaná takto:

delegovať bool DF(bool vars);

Táto trieda vlastní všetky funkcie, ktoré sa odovzdávajú ako parameter množiny hodnôt logických premenných špecifikovaných poľom vars. Výsledkom je boolovská hodnota predstavujúca hodnotu funkcie v tejto množine.

Nakoniec je tu program, ktorý využíva funkciu SolveEquations na riešenie niekoľkých systémov logických rovníc. Funkcia SolveEquations je súčasťou nižšie uvedenej triedy ProgramCommon:

trieda ProgramCommon

delegovať bool DF(bool vars);

static void Main (reťazcové argumenty)

Console.WriteLine("A funkcie - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Funkcia má 51 riešení - " +

SolveEquations(Zábava51, 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);

statický bool Fun53 (bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Takto vyzerajú výsledky riešenia pre tento program:

10 úloh na samostatnú prácu

Ktoré z týchto troch funkcií sú ekvivalentné:
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
Uvedený je fragment pravdivostnej tabuľky:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Ktorej z troch funkcií zodpovedá tento fragment:

(X 1 ˅ ¬ X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
Porotu tvoria traja ľudia. Rozhodnutie je prijaté, ak zaň hlasuje predseda poroty, ktorý podporí aspoň jeden z členov poroty. V opačnom prípade sa nerozhodne. Zostavte logickú funkciu, ktorá formalizuje proces rozhodovania.
X zvíťazí nad Y, ak výsledkom štyroch hodov mincí sú tri krát hlavy. Definujte logickú funkciu, ktorá popisuje odmenu X.
Slová vo vete sú číslované od jednotky. Veta sa považuje za správne zostavenú, ak sú splnené nasledujúce pravidlá:
1. Ak párne slovo končí samohláskou, potom ďalšie slovo, ak existuje, musí začínať samohláskou.
2. Ak sa slovo s nepárnym číslom končí na spoluhlásku, potom ďalšie slovo, ak existuje, musí začínať spoluhláskou a končiť samohláskou.
  Ktoré z nasledujúcich viet sú správne zostavené:
3. Mama umyla Mashu mydlom.
4. Líder je vždy model.
5. Pravda je dobrá, ale šťastie je lepšie.
Koľko riešení má rovnica:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Uveďte všetky riešenia rovnice:
(a → b) → c = 0
Koľko riešení má nasledujúca sústava rovníc:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X0 → X5 = 1
Koľko riešení má rovnica:
((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Odpovede na problémy:

Funkcie b a c sú ekvivalentné.
Fragment zodpovedá funkcii b.
Nech má logická premenná P hodnotu 1, keď predseda poroty hlasuje „za“ rozhodnutie. Premenné M 1 a M 2 predstavujú názory členov poroty. Logická funkcia, ktorá určuje prijatie kladného rozhodnutia, môže byť napísaná takto:
P ˄ (M 1 ˅ M 2)
Nech logická premenná P i nadobudne hodnotu 1, keď i-tý hod mincou dopadne na hlavu. Logická funkcia, ktorá špecifikuje odmenu X, môže byť napísaná takto:
¬((¬P 1 ˄ (¬P 2˅ ¬P 3˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
Veta b.
Rovnica má 3 riešenia: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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ť rozvíja veda o logike. Logika je veda, ktorá študuje metódy na zistenie 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ť rozhodovať sa 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. Môžete si vybrať 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:

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 dostať konkrétne riešenie systémov.

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 sa rovnajú 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 jeden staviame všeobecná tabuľka pravda pre všetky rovnice sústavy a nájdite čiaru 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.

Na Jednotnej štátnej skúške z informatiky 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 nahradenie premenných. Najprv musíte čo najviac zjednodušiť každú z rovníc 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ý systém. 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á rovnica bude napísané v tvare: 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 celkom možné riešenia tejto rovnice 3+9=15.

Ďalším spôsobom, ako určiť počet riešení systému logických rovníc, je binárny strom. Uvažujme túto metódu Napríklad.

Ú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 až do 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. Sústavy logických rovníc / Náučné a metodické noviny pre učiteľov informatiky: Informatika č.14,2011.

Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, zostavenie pravdivostnej tabuľky a rozklad.

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

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: Nech A = 0, potom:

Z prvej rovnice dostaneme B = 0 a z druhej - C = 1. Riešenie sústavy: A = 0, B = 0 a C = 1.

Na Jednotnej štátnej skúške z informatiky 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, jenahradenie 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: Zavedme nové premenné: X = A →B a Y = C →D. Ak vezmeme do úvahy nové premenné, rovnica bude napísaná ako: X + Y = 1.

Disjunkcia je pravdivá v troch prípadoch: (0;1), (1;0) a (1;1), zatiaľ čo X a Y sú implikácie, 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. 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 to X 1 – je pravda, potom to z prvej rovnice dostaneme 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 systému. Nechaj to teraz X 1 =0, potom z prvej rovnice máme X 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. O X 2 =0 chápeme to X 3 =0 alebo X 3 = a tak ďalej. Pokračovaním k poslednej premennej zistíme, že riešenia rovnice sú nasledujúce sady premenných (m + 1 riešenie, každé riešenie obsahuje m hodnôt premenných):