Knihovnícke logické rovnice. Riešenie logických rovníc v matematike

Ako vyriešiť niektoré z problémov častí A a B skúšky z informatiky

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

Veľký počet problémov USE je venovaných logike príkazov. 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. Tu sú 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 ^ c) ≡ (a ˅ b) ^ (a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negácia:
   ¬ (¬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 logickej funkcie

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 2 n množín premenných, pre každú z nich je špecifikovaná hodnota funkcie na tejto množine. Táto metóda je dobrá, keď je počet premenných relatívne malý. Dokonca aj pre n> 5 sa zobrazenie stáva zle viditeľné.

Ďalším spôsobom je definovať funkciu nejakým vzorcom pomocou známych pomerne jednoduchých funkcií. Systém funkcií (f 1, f 2,… f k) sa nazýva úplný, ak ľubovoľnú logickú funkciu možno vyjadriť vzorcom obsahujúcim iba funkcie f i.

Systém funkcií (¬, ˄, ˅) je kompletný. Zákony 9 a 10 sú príklady, ktoré ukazujú, ako sa implikácia a identita vyjadrujú prostredníctvom negácie, konjunkcie a disjunkcie.

V skutočnosti je kompletný aj systém dvoch funkcií – negácie a konjunkcie alebo negácie a disjunkcie. Z de Morganových zákonov vyplývajú reprezentácie, ktoré umožňujú vyjadrenie konjunkcie prostredníctvom negácie a disjunkcie, a teda vyjadrenie disjunkcie prostredníctvom negácie a konjunkcie:

(a ˅ b) ≡ ¬ (¬a ˄ ¬b)
(a ˄ b) ≡ ¬ (¬a ˅ ¬b)

Paradoxne je systém pozostávajúci len z jednej funkcie kompletný. Existujú dve binárne funkcie – antikonjunkcia a antidisjunkcia, nazývané Peirceov šíp a Schaefferov ťah, ktoré predstavujú dutý systém.

Medzi základné funkcie programovacích jazykov zvyčajne patrí identita, negácia, konjunkcia a disjunkcia. V úlohách skúšky sa spolu s týmito funkciami často stretávame s implikáciami.

Pozrime sa na niekoľko jednoduchých booleovských úloh.

Problém 15:

Je uvedený fragment pravdivostnej tabuľky. Ktorá z troch vyššie uvedených funkcií zodpovedá tomuto úryvku?

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 potrebujete 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áva sa pred disjunkciou (logickým sčítaním). Pri výpočte je ľahké si všimnúť, že funkcie s číslami 1 a 2 na 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 najvýznamnejšou číslicou, idú zostupne) → (číslo - párne) ˄ (najmenšia významná číslica - párne) ˄ (najvýznamnejšia číslica - 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 najmenej významná číslica je nepárna. Konjunkcia podmienok je nepravdivá, ak je jedna z podmienok konjunkcie nepravdivá. Pri treťom čísle nie je splnená podmienka pre najvýznamnejšiu číslicu. Pre štvrté číslo sú splnené podmienky kladené na nižšiu a vyššiu číslicu čí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 presne jeden zo zvyšných je vinný a vinný, ale neviem povedať, kto presne.

Aké závery o vine A, B a C možno vyvodiť na základe svedeckej 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, ako sa to dá urobiť prísne a formálne.

Prvá vec, ktorú musíte urobiť, je formalizovať vyhlásenia. Predstavme si tri booleovské premenné – A, B a C, z ktorých každá 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ýpovede oboch svedkov sa považujú za pravdivé a predstavujú spojenie zodpovedajúcich vzorcov.

Zostavme pravdivostnú tabuľku pre tieto hodnoty:

Súhrnné svedectvo je pravdivé iba v jednom prípade, čo vedie k jednoznačnej odpovedi - A a B sú vinní a C je nevinný.

Aj z rozboru tejto tabuľky vyplýva, že výpoveď druhého svedka má väčšiu výpovednú hodnotu. Z pravdivosti jeho svedectva vyplývajú len dve 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 5 rôznych možností zodpovedajúcich jeho výpovedi. Spoločne výpovede oboch svedkov dávajú jednoznačnú odpoveď o vine podozrivých.

Logické rovnice a sústavy rovníc

Nech F (x 1, x 2,… x n) je logická funkcia n premenných. Logická rovnica je:

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

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, riešeniami sú všetky tie množiny premenných z pravdivostnej tabuľky, na ktorých má funkcia F hodnotu true (1). Zostávajúce množiny sú riešeniami rovnice s C rovným nule. Vždy môžete zvážiť iba rovnice tvaru:

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

Vskutku, nech je uvedená rovnica:

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

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

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

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

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

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

Fk (x 1, x 2, ... x n) = 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, ktoré dávajú 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 neriešiteľným problémom. Na vyriešenie problému je potrebný iný prístup. Pre ľubovoľný systém rovníc neexistuje iná všeobecná metóda ako enumerácia, ktorá umožňuje riešiť takéto problémy.

V úlohách navrhnutých na skúšku je riešenie zvyčajne založené na zohľadnení špecifík sústavy rovníc. Opakujem, okrem vymenovania všetkých možností pre množinu premenných neexistuje žiadny všeobecný spôsob riešenia problému. Riešenie musí byť postavené na základe špecifík systému. Často je užitočné vykonať predbežné zjednodušenie systému rovníc pomocou dobre 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 úplnej pravdivostnej tabuľky zostrojíme jej analóg - binárny rozhodovací strom. Každá vetva tohto stromu zodpovedá jednému riešeniu a definuje 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 úloh vysvetlím, čo je binárny rozhodovací strom a ako sa vytvára.

Úloha 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í pre prvú rovnicu v závislosti od 5 premenných - x 1, x 2,… x 5. Prvú rovnicu možno považovať za sústavu 5 rovníc. Ako je znázornené, systém rovníc v skutočnosti predstavuje spojenie logických funkcií. Platí aj opačné tvrdenie – konjunkciu podmienok možno považovať za sústavu rovníc.

Zostrojme 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 dáva implikáciu, vetva, na ktorej X 1 je 1, vyžaduje, aby na tejto vetve X 2 bolo 1. Vetva, na ktorej je X 1 0, generuje dve vetvy s hodnotami X 2 0 a 1. Skonštruovaný strom definuje tri riešenia, na ktorých implikácia X 1 → X 2 nadobúda hodnotu 1. Na každej vetve sa zapíše zodpovedajúca množina hodnôt premenných, ktorá dáva riešenie rovnice.

Tieto množiny sú: ((1, 1), (0, 1), (0, 0))

Pokračujeme v budovaní rozhodovacieho stromu pridaním nasledujúcej rovnice, nasledujúca implikácia X 2 → X 3. Špecifikom nášho systému rovníc je, že každá nová rovnica v systéme používa jednu premennú z predchádzajúcej rovnice, pričom pridáva jednu novú premennú. Keďže premenná X 2 už má hodnoty v strome, potom na všetkých vetvách, kde má premenná X 2 hodnotu 1, bude mať premenná X 3 tiež hodnotu 1. Pre takéto vetvy pokračuje stromová konštrukcia ďalšiu úroveň, ale neobjavia sa žiadne nové vetvy. Jediná vetva, kde má premenná X 2 hodnotu 0, sa rozvetví na dve vetvy, kde premenná X 3 získa hodnoty 0 a 1. Každé pridanie novej rovnice teda vzhľadom na jej špecifickosť pridáva jedno riešenie . Pôvodná prvá rovnica:

(x1 → x2) / \ (x2 → x3) / \ (x3 → x4) / \ (x4 → x5) = 1
má 6 riešení. Úplný rozhodovací strom pre túto rovnicu vyzerá takto:

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.

Všimnite si, že vytvorený rozhodovací strom udáva nielen počet riešení (podľa počtu vetiev), ale aj samotné riešenia napísané na každej vetve stromu.

Úloha 19

Koľko rôznych množín hodnôt pre booleovské premenné x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa všetky nasledujúce podmienky?

(x1 → x2) / \ (x2 → x3) / \ (x3 → x4) / \ (x4 → x5) = 1
(y1 → y2) / \ (y2 → y3) / \ (y3 → y4) / \ (y4 → y5) = 1
(x1 → y1) = 1

Táto úloha je modifikáciou predchádzajúcej úlohy. Rozdiel je v tom, že sa pridáva ďalšia rovnica na prepojenie premenných X a Y.

Z rovnice X 1 → Y 1 vyplýva, že keď má X 1 hodnotu 1 (jedno také riešenie existuje), potom má aj Y 1 hodnotu 1. Existuje teda jedna množina, na ktorej majú X 1 a Y 1 hodnoty ​​1. Pre 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, všetkých 6 množín s premennými Y zodpovedá. , celkový počet riešení je 31 ...

Úloha 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 na základnú ekvivalenciu zapíšeme našu rovnicu ako:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Cyklický reťazec implikácií znamená identitu premenných, 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ú rovné 1 alebo 0.

Úloha 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:

Úloha 22

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

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

((X 3 ≡X 4) ˄ (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: Poďme 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:

¬ (Y 1 ≡ Y 2) = 1

¬ (Y 2 ≡ Y 3) = 1

¬ (Y 3 ≡ Y 4) = 1

¬ (Y 4 ≡ Y 5) = 1

Rozhodovací strom pre tento systém je jednoduchý a pozostáva z dvoch vetiev so striedajúcimi sa hodnotami premenných:

Ak sa vrátime k pôvodným premenným X, všimnite si, že každá hodnota premennej Y zodpovedá 2 hodnotám premenných X, takže každé riešenie v premenných Y generuje 2 5 riešení v premenných X. Dve vetvy generujú 2 * 2 5 riešení , takže celkový počet riešení je 64.

Ako vidíte, každý problém na riešenie 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. Budovanie rozhodovacích stromov je tiež bežnou technikou. Použitý prístup čiastočne pripomína konštrukciu pravdivostnej tabuľky s tou zvláštnosťou, že nie sú zostavené všetky množiny možných hodnôt premenných, ale iba tie, na ktorých funkcia nadobúda hodnotu 1 (true). V navrhovaných problémoch často nie je potrebné zostaviť úplný rozhodovací strom, pretože už v počiatočnom štádiu je možné stanoviť pravidelnosť výskytu nových vetiev na každej ďalšej úrovni, ako sa to urobilo napríklad v Problém 18.

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

Ak je problém manuálne vyriešiť, 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 skúške.

Napodiv, ale problém hľadania riešení systémov logických rovníc je pre počítač ťažký a ukazuje sa, že počítač má svoje limity. Počítač si celkom jednoducho poradí s úlohami, kde je počet premenných 20-30, no nad väčšími úlohami začne dlho rozmýšľať. Ide o to, že funkcia 2 n, ktorá udáva počet množín, je exponenciála, ktorá s rastúcim n rýchlo rastie. Tak rýchlo, že bežný osobný počítač nezvládne úlohu so 40 premennými za deň.

C # program na riešenie logických rovníc

Napísať program na riešenie logických rovníc je užitočné z mnohých dôvodov, už len preto, že ho možno použiť na kontrolu správnosti vlastného riešenia úloh testu USE. Ďalším dôvodom je, že takýto program je výborným príkladom programátorského problému, ktorý spĺňa požiadavky na úlohy kategórie C na skúške.

Myšlienka zostavenia programu je jednoduchá - je založená na úplnom vymenovaní všetkých možných sád premenných hodnôt. Keďže je pre danú logickú rovnicu alebo sústavu rovníc známy počet premenných n, je známy aj počet množín - 2 n, ktoré je potrebné vyčísliť. Pomocou základných funkcií jazyka C # - negácie, disjunkcie, konjunkcie a identity je jednoduché napísať program, ktorý pre danú množinu premenných vypočíta hodnotu logickej funkcie zodpovedajúcej logickej rovnici alebo sústave rovníc. .

V takomto programe musíte zostaviť cyklus podľa počtu množín, v tele cyklu podľa čísla množiny, vytvoriť samotnú množinu, vypočítať hodnotu funkcie na tejto množine, a ak je táto hodnota 1, potom množina dáva riešenie rovnice.

Jediný problém, ktorý vzniká pri implementácii programu, je spojený s úlohou vytvoriť súbor premenných hodnôt podľa nastaveného čísla. Krása tejto úlohy spočíva v tom, že táto zdanlivo náročná úloha sa v skutočnosti scvrkáva na jednoduchú, opakujúcu sa úlohu. V skutočnosti stačí pochopiť, že množina hodnôt premenných zodpovedajúcich číslu i, pozostávajúca z núl a jednotiek, predstavuje binárny zápis čísla i. Zložitá úloha získania súboru premenných hodnôt z nastaveného čísla sa teda redukuje na dobre známu úlohu prevodu čísla na binárny systém.

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

///

///

/// booleovská funkcia - metóda,

/// ktorej podpis nastavuje delegát DF

///

/// počet premenných

/// počet rozhodnutí

static int SolveEquations (DF fun, int n)

množina boolov = nový bool [n];

int m = (int) Math.Pow (2, n); // počet sád

int p = 0, q = 0, k = 0;

// Úplná iterácia cez počet sád

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

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

// dané binárnym vyjadrením čísla i

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

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

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

Na pochopenie programu dúfam, že vysvetlenia myšlienky programu a komentárov v jeho texte stačia. Pozastavím sa len pri vysvetlení názvu danej funkcie. Funkcia SolveEquations má dva vstupné parametre. Parameter fun špecifikuje logickú funkciu zodpovedajúcu rovnici alebo systému rovníc, ktoré sa majú riešiť. Parameter n určuje počet premenných pre zábavu. Výsledkom je, že funkcia SolveEquations vráti logickej funkcii počet riešení, teda počet tých množín, pri ktorých sa funkcia vyhodnotí ako pravdivá.

U školákov je zvykom, že vstupným parametrom x niektorej funkcie F (x) je premenná aritmetického, reťazcového alebo logického typu. V našom prípade je použitá mohutnejšia konštrukcia. Funkcia SolveEquations označuje funkcie vyššieho rádu - funkcie typu F (f), ktorých parametrami môžu byť nielen jednoduché premenné, ale aj funkcie.

Trieda funkcií, ktoré možno odovzdať ako parameter funkcii SolveEquations, je definovaná takto:

delegovať bool DF (bool vars);

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

Na záver uvediem program, v ktorom funkcia SolveEquations slúži na riešenie viacerých sústav logických rovníc. Funkcia SolveEquations je súčasťou nižšie uvedenej triedy ProgramCommon:

trieda ProgramCommon

delegovať bool DF (bool vars);

static void Main (reťazcové argumenty)

Console.WriteLine ("Mať funkcie a rozhodnutia -" +

SolveEquations (FunAnd, 2));

Console.WriteLine ("Riešenia funkcií 51 -" +

SolveRovnice (Zábava51, 5));

Console.WriteLine ("Riešenia funkcií 53 -" +

SolveRovnice (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)));

Výsledky riešenia tohto programu vyzerajú takto:

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. Je uvedený fragment pravdivostnej tabuľky:

Ktorej z troch funkcií zodpovedá tento úryvok:

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 sa po hodení mince trikrát hodia hlavy. Zadajte boolovskú funkciu popisujúcu výhry X.
6. Slová vo vete sú číslované od jednotky. Veta sa považuje za dobre zostavenú, ak sú splnené tieto pravidlá:
   1. Ak párne slovo v číslovaní končí samohláskou, potom ďalšie slovo, ak existuje, musí začínať samohláskou.
   2. Ak sa nepárne slovo v číslovaní končí spoluhláskou, potom ďalšie slovo, ak existuje, musí začínať spoluhláskou a končiť samohláskou.
      Ktoré z nasledujúcich viet sú správne napísané:
   3. Mama umyla Mášu mydlom.
   4. Líder je vždy príkladom.
   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ázor členov poroty. Logická funkcia, ktorá určuje prijatie kladného rozhodnutia, môže byť napísaná takto:
   P ˄ (M 1 ˅ M 2)
4. Nech booleovská premenná P i nadobudne hodnotu 1, keď „hlavy“ vypadnú pri i-tom hode mincou. Logická funkcia, ktorá nastavuje výplatu 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. Ponuka 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)

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

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, riešeniami sú všetky tie množiny premenných z pravdivostnej tabuľky, na ktorých má funkcia F hodnotu true (1). Zostávajúce množiny sú riešeniami 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ôžete 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 by sme mali 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, ktoré dávajú 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 neriešiteľným problémom. Na vyriešenie problému je potrebný iný prístup. Pre ľubovoľný systém rovníc neexistuje iná všeobecná metóda ako enumerácia, ktorá umožňuje riešiť takéto problémy.

V úlohách navrhnutých na skúšku je riešenie zvyčajne založené na zohľadnení špecifík sústavy rovníc. Opakujem, okrem vymenovania všetkých možností pre množinu premenných neexistuje žiadny všeobecný spôsob riešenia problému. Riešenie musí byť postavené na základe špecifík systému. Často je užitočné vykonať predbežné zjednodušenie systému rovníc pomocou dobre 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 definuje 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 úloh vysvetlím, čo je binárny rozhodovací strom a ako sa vytvára.

Úloha 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. Poďme nájsť počet riešení pre prvú rovnicu v závislosti od 5 premenných -. Prvú rovnicu možno považovať za sústavu 5 rovníc. Ako je znázornené, systém rovníc v skutočnosti predstavuje spojenie logických funkcií. Platí aj opačné tvrdenie – konjunkciu podmienok možno považovať za sústavu rovníc.

Zostrojme rozhodovací strom pre implikáciu () - prvý člen konjunkcie, ktorý možno považovať za prvú rovnicu. Takto vyzerá grafický obrázok 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é platí rovnica. Keďže rovnica definuje implikáciu, vetva, na ktorej má hodnotu 1, vyžaduje, aby na tejto vetve mala hodnotu 1. Vetva, na ktorej má hodnotu 0, generuje dve vetvy s hodnotami rovnými 0 a 1. Zostrojený strom definuje tri riešenia, na ktorých implikácia nadobúda hodnotu 1. Na každej vetve je zapísaná zodpovedajúca množina hodnôt premenných, ktorá dáva riešenie rovnice.

Tieto množiny sú: ((1, 1), (0, 1), (0, 0))

Pokračujme v budovaní rozhodovacieho stromu pridaním nasledujúcej rovnice, nasledujúcej implikácie. Špecifikom nášho systému rovníc je, že každá nová rovnica v systéme používa jednu premennú z predchádzajúcej rovnice, pričom 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 žiadne nové objavia sa vetvy. Jediná vetva, kde má premenná hodnotu 0, sa rozvetví na dve vetvy, kde premenná dostane 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í. Úplný rozhodovací strom pre túto rovnicu vyzerá takto:

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.

Všimnite si, že vytvorený rozhodovací strom udáva nielen počet riešení (podľa počtu vetiev), ale aj samotné riešenia napísané na každej vetve stromu.

Úloha 19

Koľko rôznych množín hodnôt pre booleovské premenné x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa všetky nasledujúce podmienky?

Táto úloha je modifikáciou predchádzajúcej úlohy. Rozdiel je v tom, že sa pridáva ďalšia rovnica na prepojenie premenných 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ždej množine rovnajúcej sa 0 a takýchto množín je 5 zodpovedá všetkých 6 množín s premennými Y. Celkový počet riešení je teda 31.

Úloha 20

Riešenie: Pamätajúc na základnú ekvivalenciu zapíšeme našu rovnicu ako:

Cyklický reťazec implikácií znamená identitu premenných, takže naša rovnica je ekvivalentná rovnici:

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

Úloha 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:

Úloha 22

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

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

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

Zvážte metóda redukcie na jednu rovnicu ... Táto metóda zahŕňa transformáciu logických rovníc takým spôsobom, aby sa ich pravá strana rovnala pravdivostnej hodnote (tj 1). Na to sa používa operácia logickej negácie. Potom, ak sú v rovniciach zložité logické operácie, nahradíme ich základnými: „A“, „ALEBO“, „NIE“. Ďalším krokom je spojenie rovníc do jednej, ekvivalentnej systému, pomocou logickej operácie „AND“. Potom by ste mali urobiť transformáciu výslednej rovnice na základe zákonov logickej algebry a získať konkrétne riešenie systému.

Riešenie 1: Použite inverznú metódu na obe strany prvej rovnice:

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

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

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

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

Ďalší spôsob je vytváranie pravdivostných tabuliek ... Keďže logické hodnoty majú iba dve hodnoty, môžete jednoducho prejsť všetkými možnosťami a nájsť medzi nimi tie, pre ktoré je daný systém rovníc splnený. To znamená, že zostavíme jednu spoločnú pravdivostnú tabuľku pre všetky rovnice v systéme a nájdeme riadok s požadovanými hodnotami.

Riešenie 2: Zostavme 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 (urovnať ju 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.

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

Z prvej rovnice dostaneme B = 0 a z druhej - C = 1. Systémové riešenie: A = 0, B = 0 a C = 1.

Pri skúške z informatiky sa veľmi často vyžaduje určiť počet riešení systému logických rovníc bez toho, aby sa našli samotné riešenia, na to existujú aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, jezmena premenných... Najprv je potrebné každú z rovníc čo najviac zjednodušiť na základe zákonov logickej algebry a následne nahradiť zložité časti rovníc novými premennými a určiť počet riešení novej sústavy. Potom sa vráťte k náhrade a určite počet riešení pre ňu.

Úloha: Koľko riešení má rovnica (A → B) + (C → D) = 1? Kde A, B, C, D sú boolovské 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), kým 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 existuje 3 + 9 = 15 možných riešení tejto rovnice.

Ďalším spôsobom, ako určiť počet riešení systému logických rovníc, je binárny strom... Uvažujme o tejto metóde s príkladom.

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

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

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

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

Kedy X 2 skutočne dostaneme, že ostatné premenné sú tiež pravdivé, to znamená, že množina (0; 1;…; 1) je riešením systému. o X 2 = 0 dostaneme to X 3 = 0 alebo X 3 = a tak ďalej. Pokračujúc k poslednej premennej zistíme, že riešenia rovnice sú nasledujúce množiny premenných (m + 1 riešenie, každé riešenie obsahuje m hodnôt premenných):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

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

V prípade ťažkostí s uvažovaním niyah a budovanie derev riešení, môžete hľadať riešenie s použitím pravdivostné tabuľkypre jednu alebo dve rovnice.

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

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

Zostavme pravdivostnú tabuľku pre dve rovnice:

Tento materiál obsahuje prezentáciu, ktorá prezentuje metódy riešenia logických rovníc a sústav logických rovníc v úlohe B15 (№ 23, 2015) Jednotnej štátnej skúšky z informatiky. Je známe, že táto úloha je jednou z najťažších medzi úlohami skúšky. Prezentácia môže byť užitočná pri vedení lekcií na tému „Logika“ v špecializovaných triedach, ako aj pri príprave na zloženie skúšky.

Stiahnuť ▼:

Náhľad:

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

Popisy snímok:

Riešenie úlohy B15 (systémy logických rovníc) MP Višnevskaja, MAOU "Gymnázium č. 3" 18. novembra 2013, Saratov

Úloha B15 je jedna z najťažších na skúške z informatiky !!! Testujú sa schopnosti: transformovať výrazy obsahujúce booleovské 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é zodpovedajú zadaným podmienkam. Najťažšia vec, pretože neexistujú žiadne formálne pravidlá, ako to urobiť, je potrebný odhad.

Bez čoho sa nezaobídeš!

Bez čoho sa nezaobídeš!

Konjunkcia legendy: 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 ekvivalent: A  B, A  B, A  B bez „alebo“: A  B, A xor B

Metóda zmeny premennej Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x9, x10 existuje, ktoré spĺňajú všetky nasledujúce podmienky: ((x1 ≡ x2) \ / (x3 ≡ x4)) / \ (¬ (x1 ≡ x2) \ / ¬ (x3 ≡ x4)) = 1 ((x3 ≡ x4) \ / (x5 ≡ x6)) / \ (¬ (x3 ≡ x4) \ / ¬ (x5 ≡ x6)) = 1 ((x5 ≡ x6) \ / (x7 ≡ x8)) / \ (¬ (x5 ≡ x7) \ / ¬ (x7 ≡ x8)) = 1 ((x7 ≡ x8) \ / (x9 ≡ x10)) / \ (¬ (x7 ≡ x8) \ / ¬ (x9 ≡ x10)) = 1 Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, ..., x9, x10, pod ktorými daný systém rovnosti je spokojný. 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 Na vyjadrenie operácie XOR pomocou konjunkcie a disjunkcie používame vzorec: (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 Т 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 sú páry (0,0) a (1,1).

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

Metóda eliminácie č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 nasledujúce podmienky: (x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4 ) ∧ (x4 → x5) = 1; (y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) = 1; y5 → x5 = 1. Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2,…, x5, y 1, y2,…, y5, pre ktoré je daný systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie. Krok 1. Postupné riešenie rovníc х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Prvá rovnica je konjunkcia viacerých implikačných operácií, rovná sa 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 vo forme tabuľky:

Krok 1. Sekvenčné riešenie T.®. Získalo sa 6 sád riešení pre x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Ak budeme argumentovať podobným spôsobom, dôjdeme k záveru, že pre y1, y2, y3, y4, y5 existuje rovnaká množina riešení. Pretože tieto rovnice sú nezávislé, t.j. nemajú žiadne spoločné premenné, potom riešenie tohto systému rovníc (bez zohľadnenia tretej rovnice) bude 6 * 6 = 36 párov "x" a "igrykov". Uvažujme tretiu rovnicu: y5 → x5 = 1 Riešením sú dvojice: 0 0 0 1 1 1 Nie je riešením dvojice: 1 0

Porovnajme získané riešenia Kde y5 = 1, x5 = 0 nesedí. takéto dvojice 5. Počet riešení sústavy: 36-5 = 31. Odpoveď: 31 Kombinatorika bola potrebná !!!

Metóda dynamického programovania Koľko rôznych riešení má logická rovnica x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kde x 1, x 2,…, x 6 sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne sady hodnôt premenných, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť množstvá takýchto sád.

Riešenie Krok 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á ďalšia premenná nezávisí od predchádzajúcej, ale od výsledku predchádzajúcej implikácie!

Krok 2. Odhalenie vzoru Uvažujme o prvej implikácii, X 1 → X 2. Tabuľka pravdivosti: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednej 0 sme dostali 2 jednotky a z 1 sme dostal jednu 0 a jednu 1. Len jednu 0 a tri 1, to je výsledok prvej operácie.

Krok 2. Odhalenie vzoru Po pripojení x 3 k výsledku prvej operácie dostaneme: F (x 1, x 2) x 3 F (x 1, x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Z dvoch 0 - dve 1, z každej 1 (sú 3) po jednej 0 a 1 (3 + 3)

Krok 3. Odvodenie vzorca. môžete napísať 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 podľa vyššie uvedených vzorcov; tabuľka ukazuje, ako je zostavený nasledujúci stĺpec podľa predchádzajúceho:: počet premenných 1 2 3 4 5 6 Počet núl N i 1 1 3 5 11 21 Počet jednotiek E i 1 2 * 1 + 1 = 3 2 * 1 + 3 = 5 11 21 43 Odpoveď: 43

Metóda využívajúca zjednodušenia logických výrazov Koľko rôznych riešení má rovnica ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1, kde J, K, L, M, N sú booleovské premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt J, K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie Všimnite si, že J → K = ¬ J  K Zaveďte zmenu premenných: J → K = A, M  N  L = B Prepíšte 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 Je to možné, ak: M = J = 0 M = 0, J = 1 M = J = 1

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

Riešenie 10. Pri M = J = 1 dostaneme 0 + K = 1 * N * L, alebo K = N * L, 4 riešenia: 11. Celkom má 4 + 4 = 8 riešení Odpoveď: 8 KNL 0 0 0 0 0 1 0 1 0 1 1 1

Zdroje informácií: O.B. Bogomolová, D.Yu. Usenkov. В15: nové úlohy a nové riešenie Informatika, č.6, 2012, s. 35 - 39. K.Yu. Polyakov. Logické rovnice // Informatika, č.14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronický zdroj]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronický zdroj].

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

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

Vzdelávacie : podporovať rozvoj schopnosti počúvať názory iných, podporovať vôľu a vytrvalosť 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ácej úlohy (10 minút)

V predchádzajúcich lekciách sme sa zoznámili so základnými zákonmi algebry logiky, naučili sme sa tieto zákony použiť na zjednodušenie logických výrazov.

Pozrime sa na našu domácu úlohu, aby sme zjednodušili logické výrazy:

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

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

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

Predstavme si notáciu:

A - prvé písmeno spoluhlásky

B - druhé písmeno spoluhlásky

C - posledné písmeno samohlásky

D - predposledné písmeno samohlásky

Zostavme si výraz:

Urobme si tabuľku:

2. Označte, ktorý boolovský výraz je ekvivalentný výrazu

Zjednodušme si písanie pôvodného výrazu a navrhovaných variantov:

3. Fragment pravdivostnej tabuľky výrazu F je daný:

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

Oboznámenie sa s témou hodiny, prezentácia nového materiálu (30 minút)

Pokračujeme v štúdiu základov logiky a témy našej dnešnej lekcie „Riešenie logických rovníc“. Po preštudovaní tejto témy sa naučíte hlavné 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

Svoju odpoveď zapíšte 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:

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

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

Odpoveď: 0100

2. Koľko riešení má rovnica (do odpovede napíšte len číslo)?

Riešenie: transformujte výraz

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

A + B = 1 a C + D = 1

Metóda 2: zostavenie pravdivostnej tabuľky

Pôvodný výraz transformujeme, rozšírime zátvorky, aby sme dosiahli disjunkciu spojok:

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

Spojky dopĺňame na kompletné spojky (súčin všetkých argumentov), ​​rozširujeme zátvorky:

Zoberme do úvahy rovnaké spojky:

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

3. Koľko riešení má rovnica (do odpovede doplňte len číslo)?

Zjednodušme výraz:

,

3 spôsob: budova SDNF

Zoberme do úvahy rovnaké spojky:

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

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

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

Príklad: daná pravdivostná tabuľka výrazu. Vytvorte boolovský výraz.

3. Úloha doma (5 minút)

Vyriešte rovnicu:

Koľko riešení má rovnica (doplňte len číslo)?

Pre danú pravdivostnú tabuľku zostavte logické vyjadrenie a

zjednodušiť to.