Riešenie logických rovníc. Priorita logických operácií

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 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 - . 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 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ú. 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í. Keďže každé variabilné riešenie je možné kombinovať s každým variabilným riešením, 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?

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?

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

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

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

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

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

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

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

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

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

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

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

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

Riešenie logických rovníc

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

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

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

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

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

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

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

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

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

Aby sme si uľahčili ďalšiu prácu, najprv zjednodušíme pravú a ľavú stranu logickej rovnice a nájdeme ich negácie:

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

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

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

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

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

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

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

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

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

Označme teda T = A B

X T+ X T= X↔ T.

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

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

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

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

Sériové pripojenie kontaktov

Paralelné pripojenie kontaktov

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

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

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

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

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

diagram zodpovedajúci funkcii:

&F(X, Y, Z)

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

A disjunktívny-normálny formulárov

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Zápis logickej funkcie z tabuľky

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

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

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

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

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

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

Algoritmus na konštrukciu SDNF pomocou pravdivostnej tabuľky

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

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

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

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

Algoritmus na konštrukciu SCNF pomocou pravdivostnej tabuľky

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

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

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

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

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

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

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

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

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

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

Riešenie problémov

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

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

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

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

Teraz vytvoríme logický diagram tejto funkcie.

B&1F(A,B,C)

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

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

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

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

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

x ↔ y= x y+ x y

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

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

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

Funkcie SKNF vytvárame pomocou týchto riadkov:

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

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

Požadovaná odpoveď je teda 4.

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

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

Funkcie SDNF vytvárame pomocou týchto riadkov:

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

Požadovaná odpoveď je teda 2.

Referencie

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

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

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

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ť riešiť logické problémy. Úlohy B15 v jednotnej štátnej skúške sú úlohy so zvýšenou zložitosťou, pretože obsahujú systémy logických rovníc. Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, zostavenie pravdivostnej tabuľky, rozklad, sekvenčné riešenie rovníc atď.

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

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

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

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

Keďže ľavé strany rovníc 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 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:

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 každú z rovníc čo najviac zjednodušiť na základe zákonov logickej algebry a potom nahradiť zložité časti rovníc novými premennými a určiť počet riešení nového systému. Potom sa vráťte k náhrade a určite počet riešení pre ňu.

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

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

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

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

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

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

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

Predstierajme toX 1 – je pravda, potom to z prvej rovnice dostanemeX 2 tiež pravda, od druhého -X 3 =1 a tak ďalej 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.

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:

Vytvorme pravdivostnú tabuľku pre dve rovnice:

Ď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.

Téma lekcie: Riešenie logických rovníc

vývojové - vytvárať podmienky pre rozvoj kognitívneho záujmu žiakov, podporovať rozvoj pamäti, pozornosti a logického myslenia;

Vzdelávacie : podporovať schopnosť počúvať názory iných, pestovanie vôle a vytrvalosti dosiahnuť konečné výsledky.

Typ lekcie: kombinovaná lekcia

Vybavenie: počítač, multimediálny projektor, prezentácia 6.

Počas vyučovania

Opakovanie a aktualizácia základných vedomostí. Kontrola domácich úloh (10 minút)

V predchádzajúcich lekciách sme sa oboznámili so základnými zákonmi logickej algebry a naučili sme sa tieto zákony využívať na zjednodušenie logických výrazov.

Pozrime sa na našu domácu úlohu o zjednodušení logických výrazov:

1. Ktoré z nasledujúcich slov spĺňa logickú podmienku:

(prvopísmenová spoluhláska→druhá písmenová spoluhláska)٨ (posledná samohláska → predposledná samohláska)? Ak existuje niekoľko takýchto slov, uveďte najmenšie z nich.

1) ANNA 2) MARIA 3) OLEG 4) ŠTEPÁN

Predstavme si nasledujúci zápis:

A – spoluhláska prvého písmena

B – spoluhláska druhého písmena

S – samohláska posledného písmena

D – predposledné samohláskové písmeno

Urobme si výraz:

Urobme si tabuľku:

2. Uveďte, ktorý logický výraz je ekvivalentný výrazu

Zjednodušme nahrávanie pôvodného výrazu a navrhovaných možností:

3. Daný fragment pravdivostnej tabuľky výrazu F:

Určme hodnoty týchto výrazov pre zadané hodnoty argumentov:

Úvod do témy lekcie, prezentácia nového materiálu (30 minút)

Pokračujeme v štúdiu základov logiky a témou našej dnešnej lekcie je „Riešenie logických rovníc“. Po preštudovaní tejto témy sa naučíte základné spôsoby riešenia logických rovníc, získate zručnosti na riešenie týchto rovníc pomocou jazyka logickej algebry a schopnosť zostaviť logický výraz pomocou pravdivostnej tabuľky.

1. Vyriešte logickú rovnicu

(¬K M) → (¬L M N) = 0

Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.

Riešenie:

Transformujme výraz(¬K  M) → (¬L  M  N)

Výraz je nepravdivý, keď sú oba pojmy nepravdivé. Druhý člen sa rovná 0, ak M = 0, N = 0, L = 1. V prvom člene K = 0, keďže M = 0, a
.

Odpoveď: 0100

2. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?

Riešenie: transformujte výraz

(A + B)* (C + D) = 1

A + B = 1 a C + D = 1

Metóda 2: zostavenie pravdivostnej tabuľky

Transformujme pôvodný výraz, otvorme zátvorky, aby sme získali disjunkciu spojok:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Doplňme spojky na úplné spojky (súčin všetkých argumentov), ​​otvorme zátvorky:

Zoberme do úvahy rovnaké spojky:

Výsledkom je, že získame SDNF obsahujúci 9 konjunkcií. Pravdivostná tabuľka pre túto funkciu má teda hodnotu 1 v 9 riadkoch 2 4 =16 množín hodnôt premenných.

3. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?

Zjednodušme výraz:

,

3 spôsob: výstavba SDNF

Zoberme do úvahy rovnaké spojky:

Výsledkom je, že získame SDNF obsahujúci 5 konjunkcií. Pravdivostná tabuľka pre túto funkciu má teda hodnotu 1 na 5 riadkoch 2 4 =16 množín hodnôt premenných.

Zostrojenie logického výrazu pomocou pravdivostnej tabuľky:

pre každý riadok pravdivostnej tabuľky obsahujúcej 1 zostavíme súčin argumentov a premenné rovné 0 sú zahrnuté v súčine s negáciou a premenné rovné 1 sú zahrnuté bez negácie. Požadovaný výraz F bude zložený zo súčtu výsledných produktov. Potom, ak je to možné, tento výraz by sa mal zjednodušiť.

Príklad: je uvedená pravdivostná tabuľka výrazu. Zostavte logický výraz.

3. domáca úloha (5 minút)

Vyriešte rovnicu:

Koľko riešení má rovnica (uveďte v odpovedi iba číslo)?

Pomocou danej pravdivostnej tabuľky zostrojte logický výraz a

zjednodušiť to.

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.

1. Komutivita disjunkcie a konjunkcie:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distribučné právo týkajúce sa disjunkcie a konjunkcie:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negácia negácie:
   ¬(¬a) ≡ a
4. konzistencia:
   a ^ ¬а ≡ nepravda
5. Exkluzívna tretina:
   a ˅ ¬а ≡ pravda
6. De Morganove zákony:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Zjednodušenie:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ pravda ≡ a
   a ˄ nepravda ≡ nepravda
8. Absorpcia:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Nahradenie implikácie
   a → b ≡ ¬a ˅ b
10. 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?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ 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.

1. 13579
2. 97531
3. 24678
4. 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 tento prípad.

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ého rozumu. 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:

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 – jeho výpovedi zodpovedá 5 rôznych možností. 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

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í F:

Ф = 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 ≡X 10)) = 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

Prejdeme na tradičnú formu a systém po zjednodušeniach napíšeme vo forme:

¬(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. Bežnou technikou 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 zostrojenie pravdivostnej tabuľky s tou zvláštnosťou, že nie sú zostrojené všetky množiny možných hodnôt premenných, ale len tie, na ktorých má funkcia hodnotu 1 (true). V navrhovaných problémoch často nie je potrebné budovať úplný rozhodovací strom, pretože už v počiatočnom štádiu je možné vytvoriť vzor vzhľadu nových vetiev na každej nasledujúcej ú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č si celkom ľahko poradí s problémami, kde je počet premenných 20-30, ale nad problémami väčších rozmerov začne dlho uvažovať. 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. Zložitá úloha získania súboru premenných hodnôt pomocou nastaveného čísla sa teda redukuje na známu úlohu prevodu čísla na binárne.

Takto vyzerá funkcia v C#, ktorá rieši náš problém:

///

///

/// 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 počet zábavných premenných. 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 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 š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);

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 pre tento program:

10 úloh na samostatnú prácu

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

Ktorej z troch funkcií zodpovedá tento fragment:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
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.
5. X zvíťazí nad Y, ak výsledkom štyroch hodov mincí sú tri krát hlavy. Definujte logickú funkciu, ktorá popisuje odmenu X.
6. 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.
7. Koľko riešení má rovnica:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Uveďte všetky riešenia rovnice:
   (a → b) → c = 0
9. 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
10. Koľko riešení má rovnica:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Odpovede na problémy:

1. Funkcie b a c sú ekvivalentné.
2. Fragment zodpovedá funkcii b.
3. 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)
4. 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))
5. Veta b.
6. Rovnica má 3 riešenia: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)