Ako vyriešiť niektoré problémy v častiach A a B skúšky z informatiky
Lekcia č. 3. Logika. Logické funkcie. Riešenie rovníc
Výrokovej logike je venované veľké množstvo úloh jednotnej štátnej skúšky. Na vyriešenie väčšiny z nich stačí poznať základné zákony výrokovej logiky, znalosť pravdivostných tabuliek logických funkcií jednej a dvoch premenných. Uvediem základné zákony výrokovej logiky.
- Komutivita disjunkcie a konjunkcie:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - Distribučné právo týkajúce sa disjunkcie a konjunkcie:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Negácia negácie:
¬(¬a) ≡ a - konzistencia:
a ^ ¬a ≡ nepravda - Exkluzívna tretina:
a ˅ ¬а ≡ pravda - De Morganove zákony:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Zjednodušenie:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ pravda ≡ a
a ˄ nepravda ≡ nepravda - Absorpcia:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Nahradenie implikácie
a → b ≡ ¬a ˅ b - Nahradenie identity
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Reprezentácia logických funkcií
Akákoľvek logická funkcia n premenných - F(x 1, x 2, ... x n) môže byť špecifikovaná pravdivostnou tabuľkou. Takáto tabuľka obsahuje 2n množín premenných, pre každú z nich je špecifikovaná hodnota funkcie na tejto množine. Táto metóda je dobrá, keď je počet premenných relatívne malý. Už pre n > 5 sa zobrazenie stáva zle viditeľné.
Ďalším spôsobom je definovať funkciu nejakým vzorcom pomocou známych pomerne jednoduchých funkcií. Systém funkcií (f 1, f 2, ... f k) sa nazýva úplný, ak ľubovoľnú logickú funkciu možno vyjadriť vzorcom obsahujúcim iba funkcie f i.
Systém funkcií (¬, ˄, ˅) je kompletný. Zákony 9 a 10 sú príklady, ktoré demonštrujú, ako sa implikácia a identita vyjadrujú prostredníctvom negácie, konjunkcie a disjunkcie.
V skutočnosti je kompletný aj systém dvoch funkcií – negácie a konjunkcie alebo negácie a disjunkcie. Z De Morganových zákonov vyplývajú myšlienky, ktoré umožňujú vyjadriť konjunkciu prostredníctvom negácie a disjunkcie, a teda vyjadriť disjunkciu prostredníctvom negácie a konjunkcie:
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Paradoxne je systém pozostávajúci len z jednej funkcie kompletný. Existujú dve binárne funkcie – antikonjunkcia a antidisjunkcia, nazývaná Peirceova šípka a Schaefferov ťah, predstavujúci dutý systém.
Medzi základné funkcie programovacích jazykov zvyčajne patrí identita, negácia, konjunkcia a disjunkcia. V problémoch s jednotnou štátnou skúškou sa spolu s týmito funkciami často nachádza implikácia.
Pozrime sa na niekoľko jednoduchých problémov týkajúcich sa logických funkcií.
Problém 15:
Je uvedený fragment pravdivostnej tabuľky. Ktorá z troch uvedených funkcií zodpovedá tomuto fragmentu?
| X 1 | X 2 | X 3 | X 4 | F |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Číslo funkcie 3.
Na vyriešenie problému musíte poznať pravdivostné tabuľky základných funkcií a pamätať si priority operácií. Pripomínam, že spojka (logické násobenie) má vyššiu prioritu a vykoná sa skôr ako disjunkcia (logické sčítanie). Pri výpočtoch je ľahké si všimnúť, že funkcie s číslami 1 a 2 v tretej množine majú hodnotu 1 az tohto dôvodu nezodpovedajú fragmentu.
Problém 16:
Ktoré z uvedených čísel spĺňa podmienku:
(číslice začínajúce od najvýznamnejšej číslice sú v zostupnom poradí) → (číslo - párne) ˄ (nízke číslice - párne) ˄ (vysoké číslice - nepárne)
Ak existuje niekoľko takýchto čísel, uveďte najväčšie.
- 13579
- 97531
- 24678
- 15386
Podmienka je splnená číslom 4.
Prvé dve čísla nespĺňajú podmienku z dôvodu, že najnižšia číslica je nepárna. Konjunkcia podmienok je nepravdivá, ak je jedna z podmienok konjunkcie nepravdivá. Pre tretie číslo nie je splnená podmienka pre najvyššiu číslicu. Pre štvrté číslo sú splnené podmienky kladené na nízke a vysoké číslice čísla. Prvý člen spojky je tiež pravdivý, pretože implikácia je pravdivá, ak je jej premisa nepravdivá, čo je 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:
| A | B | C | F 1 | F 2 | F 1 ˄ F 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Súhrnné dôkazy sú pravdivé iba v jednom prípade, čo vedie k jasnej odpovedi - A a B sú vinní a C je nevinný.
Z rozboru tejto tabuľky tiež vyplýva, že výpoveď druhého svedka je informatívnejšia. Z pravdivosti jeho svedectva vyplývajú len dve možné možnosti - A a B sú vinní a C je nevinný, alebo A a C sú vinní a B je nevinný. Výpoveď prvého svedka je menej informatívna – 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 ≡X10)) = 0
odpoveď: 64
Riešenie: Presuňme sa z 10 premenných na 5 premenných zavedením nasledujúcej zmeny premenných:
Y1 = (Xi = X2); Y2 = (X3 = X4); Y3 = (X5 = X6); Y4 = (X7 = X8); Y5 = (X9 = X10);
Potom bude mať prvá rovnica tvar:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
Rovnicu možno zjednodušiť tak, že ju napíšeme takto:
(Yi = Y2) = 0
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 konštrukciu pravdivostnej tabuľky s tou zvláštnosťou, že nie sú zostrojené všetky množiny možných hodnôt premenných, ale iba tie, na ktorých má funkcia hodnotu 1 (true). V navrhovaných problémoch často nie je potrebné budovať úplný rozhodovací strom, pretože už v počiatočnej fáze je možné vytvoriť vzor vzhľadu nových vetiev na každej ďalšej úrovni, ako sa to urobilo napríklad v probléme 18. .
Vo všeobecnosti sú problémy týkajúce sa hľadania riešení systému logických rovníc dobrými matematickými cvičeniami.
Ak sa problém ťažko rieši ručne, potom môžete jeho riešenie zveriť počítaču napísaním vhodného programu na riešenie rovníc a sústav rovníc.
Napísať takýto program nie je ťažké. Takýto program sa ľahko vyrovná so všetkými úlohami ponúkanými v jednotnej štátnej skúške.
Napodiv, úloha nájsť riešenia systémov logických rovníc je pre počítač náročná a ukazuje sa, že počítač má svoje limity. Počítač 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:
///
/// program na počítanie počtu riešení
/// logická rovnica (systém rovníc)
///
///
/// logická funkcia - metóda,
/// ktorého podpis určí delegát DF
///
/// počet premenných
///
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
- Ktoré z týchto troch funkcií sú ekvivalentné:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄Y
- Uvedený je fragment pravdivostnej tabuľky:
| X 1 | X 2 | X 3 | X 4 | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Ktorej z troch funkcií zodpovedá tento fragment:
- (X 1 ˅ ¬ X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- Porotu tvoria traja ľudia. Rozhodnutie je prijaté, ak zaň hlasuje predseda poroty, ktorý podporí aspoň jeden z členov poroty. V opačnom prípade sa nerozhodne. Zostavte logickú funkciu, ktorá formalizuje proces rozhodovania.
- X zvíťazí nad Y, ak výsledkom štyroch hodov mincí sú tri krát hlavy. Definujte logickú funkciu, ktorá popisuje odmenu X.
- Slová vo vete sú číslované od jednotky. Veta sa považuje za správne zostavenú, ak sú splnené nasledujúce pravidlá:
- Ak párne slovo končí samohláskou, potom ďalšie slovo, ak existuje, musí začínať samohláskou.
- 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é: - Mama umyla Mashu mydlom.
- Líder je vždy model.
- Pravda je dobrá, ale šťastie je lepšie.
- Koľko riešení má rovnica:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - Uveďte všetky riešenia rovnice:
(a → b) → c = 0 - Koľko riešení má nasledujúca sústava rovníc:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X0 → X5 = 1 - Koľko riešení má rovnica:
((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
Odpovede na problémy:
- Funkcie b a c sú ekvivalentné.
- Fragment zodpovedá funkcii b.
- Nech má logická premenná P hodnotu 1, keď predseda poroty hlasuje „za“ rozhodnutie. Premenné M 1 a M 2 predstavujú názory členov poroty. Logická funkcia, ktorá určuje prijatie kladného rozhodnutia, môže byť napísaná takto:
P ˄ (M 1 ˅ M 2) - Nech logická premenná P i nadobudne hodnotu 1, keď i-tý hod mincou dopadne na hlavu. Logická funkcia, ktorá špecifikuje odmenu X, môže byť napísaná takto:
¬((¬P 1 ˄ (¬P 2˅ ¬P 3˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Veta b.
- Rovnica má 3 riešenia: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)
Používanie rovníc je v našich životoch veľmi rozšírené. Používajú sa pri mnohých výpočtoch, stavbe konštrukcií a dokonca aj v športe. Človek používal rovnice v staroveku a odvtedy sa ich používanie len zvyšuje. V matematike existujú určité problémy, ktoré sa zaoberajú výrokovou logikou. Na vyriešenie tohto druhu rovnice je potrebné mať určité znalosti: znalosť zákonov výrokovej logiky, znalosť pravdivostných tabuliek logických funkcií 1 alebo 2 premenných, metódy na prevod logických výrazov. Okrem toho musíte poznať nasledujúce vlastnosti logických operácií: konjunkcia, disjunkcia, inverzia, implikácia a ekvivalencia.
Akákoľvek logická funkcia \premenných - \môže byť špecifikovaná pravdivostnou tabuľkou.
Poďme vyriešiť niekoľko logických rovníc:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Začnime riešenie s \[X1\] a určme, aké hodnoty môže mať táto premenná: 0 a 1. Ďalej zvážime každú z vyššie uvedených hodnôt a uvidíme, čo môže byť \[X2.\].
Ako vidno z tabuľky, naša logická rovnica má 11 riešení.
Kde môžem vyriešiť logickú rovnicu online?
Rovnicu môžete vyriešiť na našej webovej stránke https://site. Bezplatný online riešiteľ vám umožní vyriešiť online rovnice akejkoľvek zložitosti v priebehu niekoľkých sekúnd. Všetko, čo musíte urobiť, je jednoducho zadať svoje údaje do riešiteľa. Na našej stránke si môžete pozrieť aj video návod a naučiť sa riešiť rovnicu. A ak máte stále otázky, môžete sa ich opýtať v našej skupine VKontakte http://vk.com/pocketteacher. Pridajte sa do našej skupiny, vždy vám radi pomôžeme.
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 nové pobočky sa neobjavia. 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?
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kde J, K, L, M, N sú logické premenné?
Riešenie.
Výraz (N ∨ ¬N) teda platí pre ľubovoľné N
J ∧ ¬K ∧ L ∧ ¬M = 0.
Aplikujme negáciu na obe strany logickej rovnice a použijeme De Morganov zákon ¬ (A ∧ B) = ¬ A ∨ ¬ B. Dostaneme ¬J ∨ K ∨ ¬L ∨ M = 1.
Logický súčet sa rovná 1, ak sa aspoň jeden z jeho základných výrokov rovná 1. Výsledná rovnica je teda splnená ľubovoľnou kombináciou logických premenných okrem prípadu, keď sú všetky veličiny zahrnuté v rovnici rovné 0. Každá z 4 premenné sa môžu rovnať buď 1 alebo 0, preto sú všetky možné kombinácie 2·2·2·2 = 16. Preto rovnica má 16 −1 = 15 riešení.
Zostáva poznamenať, že nájdených 15 riešení zodpovedá ktorejkoľvek z dvoch možných hodnôt logickej premennej N, takže pôvodná rovnica má 30 riešení.
odpoveď: 30
Koľko rôznych riešení má rovnica?
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
kde J, K, L, M, N sú logické premenné?
Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt J, K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie.
Používame vzorce A → B = ¬A ∨ B a ¬(A ∨ B) = ¬A ∧ ¬B
Zoberme si prvý podvzorec:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Zoberme si druhý podvzorec
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬
Zoberme si tretí podvzorec
1) M → J = 1 teda,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Poďme kombinovať:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 teda 4 riešenia.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Poďme kombinovať:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L teda 4 riešenia.
c) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Odpoveď: 4 + 4 = 8.
odpoveď: 8
Koľko rôznych riešení má rovnica?
((K ∨ L) → (L ∧ M ∧ N)) = 0
kde K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie.
Prepíšme rovnicu pomocou jednoduchšieho zápisu operácií:
((K + L) -> (L M N)) = 0
1) z pravdivostnej tabuľky operácie „implikácia“ (pozri prvý problém) vyplýva, že táto rovnosť je pravdivá vtedy a len vtedy, ak súčasne
K + L = 1 a LMN = 0
2) z prvej rovnice vyplýva, že aspoň jedna z premenných, K alebo L, sa rovná 1 (alebo obe spolu); pozrime sa teda na tri prípady
3) ak K = 1 a L = 0, potom je druhá rovnosť splnená pre všetky M a N; keďže existujú 4 kombinácie dvoch booleovských premenných (00, 01, 10 a 11), máme 4 rôzne riešenia
4) ak K = 1 a L = 1, potom druhá rovnosť platí pre M · N = 0; sú 3 takéto kombinácie (00, 01 a 10), máme ešte 3 riešenia
5) ak K = 0, potom L = 1 (z prvej rovnice); v tomto prípade je splnená druhá rovnosť, keď M · N = 0; sú 3 takéto kombinácie (00, 01 a 10), máme ešte 3 riešenia
6) celkovo dostaneme 4 + 3 + 3 = 10 riešení.
odpoveď: 10
Koľko rôznych riešení má rovnica?
(K ∧ L) ∨ (M ∧ N) = 1
Riešenie.
Výraz je pravdivý v troch prípadoch, keď (K ∧ L) a (M ∧ N) sú rovné 01, 11, 10, v tomto poradí.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N sa rovnajú 1 a K a L sú čokoľvek okrem súčasnej 1. Preto existujú 3 riešenia.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 roztok.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 riešenia.
odpoveď: 7.
odpoveď: 7
Koľko rôznych riešení má rovnica?
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
kde X, Y, Z, P sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne súbory hodnôt, pre ktoré platí táto rovnosť. Ako odpoveď stačí uviesť počet takýchto sád.
Riešenie.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Logické OR je nepravdivé iba v jednom prípade: keď sú oba výrazy nepravdivé.
teda
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Preto existuje len jedno riešenie rovnice.
odpoveď: 1
Koľko rôznych riešení má rovnica?
(K ∨ L) ∧ (M ∨ N) = 1
kde K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď stačí uviesť počet takýchto sád.
Riešenie.
Logické A je pravdivé iba v jednom prípade: keď sú všetky výrazy pravdivé.
K ∨ L = 1, M ∨ N = 1.
Každá rovnica dáva 3 riešenia.
Uvažujme rovnicu A ∧ B = 1, ak A aj B nadobúdajú pravdivé hodnoty v troch prípadoch, potom má rovnica celkovo 9 riešení.
Preto je odpoveď 9.
odpoveď: 9
Koľko rôznych riešení má rovnica?
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
kde A, B, C, D sú logické premenné?
Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt A, B, C, D, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie.
Logické „ALEBO“ je pravdivé, ak je pravdivé aspoň jedno z tvrdení.
(D ∧ ¬D) = 0 pre ľubovoľné D.
teda
(A -> B) - C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, čo nám dáva 3 možné riešenia pre každé D.
(D ∧ ¬ D)= 0 pre ľubovoľné D, čo nám dáva dve riešenia (pre D = 1, D = 0).
Preto: celkové riešenia 2*3 = 6.
Celkom 6 riešení.
odpoveď: 6
Koľko rôznych riešení má rovnica?
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
kde K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď stačí uviesť počet takýchto sád.
Riešenie.
Aplikujme negáciu na obe strany rovnice:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logické OR je pravdivé v troch prípadoch.
Možnosť 1.
K ∧ L ∧ M = 1, potom K, L, M = 1 a ¬L ∧ M ∧ N = 0. N je ľubovoľné, to znamená 2 riešenia.
Možnosť 2.
¬L ∧ M ∧ N = 1, potom N, M = 1; L = 0, K ľubovoľné, teda 2 riešenia.
Preto je odpoveď 4.
odpoveď: 4
A, B a C sú celé čísla, pre ktoré je výrok pravdivý
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Čomu sa rovná B, ak A = 45 a C = 43?
Riešenie.
Upozorňujeme, že toto zložité vyhlásenie pozostáva z troch jednoduchých
1) ¬(A = B); (A > B) -> (B > C); (B > A) -> (C > B);
2) tieto jednoduché príkazy sú spojené operáciou ∧ (AND, spojka), to znamená, že musia byť vykonané súčasne;
3) z ¬(A = B)=1 okamžite vyplýva, že A B;
4) predpokladajme, že A > B, potom z druhej podmienky dostaneme 1→(B > C)=1; tento výraz môže byť pravdivý vtedy a len vtedy, ak B > C = 1;
5) teda máme A > B > C, tejto podmienke zodpovedá len číslo 44;
6) pre každý prípad zaškrtnime aj možnosť A 0 →(B > C)=1;
tento výraz platí pre akékoľvek B; Teraz sa pozrieme na tretiu podmienku a dostaneme
tento výraz môže byť pravdivý vtedy a len vtedy, ak C > B, a tu máme rozpor, pretože neexistuje také číslo B, pre ktoré by C > B > A.
odpoveď: 44.
odpoveď: 44
Zostrojte pravdivostnú tabuľku pre logickú funkciu
X = (A ↔ B) ∨ ¬ (A → (B ∨ C))
v ktorom stĺpec hodnôt argumentu A je binárne vyjadrenie čísla 27, stĺpec hodnôt argumentu B je číslo 77, stĺpec hodnôt argumentu C je číslo 120. Číslo v stĺpci sa píše zhora nadol od najvýznamnejšieho po najmenej významný (vrátane nulovej sady). Preveďte výslednú binárnu reprezentáciu hodnôt funkcie X do desiatkovej číselnej sústavy.
Riešenie.
Napíšme rovnicu pomocou jednoduchšieho zápisu operácií:
1) toto je výraz s tromi premennými, takže v pravdivostnej tabuľke budú riadky; preto binárne znázornenie čísel použitých na zostavenie stĺpcov tabuľky A, B a C musí pozostávať z 8 číslic
2) preveďte čísla 27, 77 a 120 do dvojkovej sústavy, pričom na začiatok čísel okamžite pridajte až 8 číslic núl
3) je nepravdepodobné, že budete môcť okamžite zapísať hodnoty funkcie X pre každú kombináciu, takže je vhodné pridať do tabuľky ďalšie stĺpce na výpočet medzivýsledkov (pozri tabuľku nižšie)
| A | IN | S | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) vyplňte stĺpce tabuľky:
| A | IN | S | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
hodnota je 1 iba v tých riadkoch, kde A = B
hodnota je 1 v tých riadkoch, kde buď B alebo C = 1
hodnota je 0 len v tých riadkoch, kde A = 1 a B + C = 0
hodnota je inverzná k predchádzajúcemu stĺpcu (0 sa nahradí 1 a 1 sa nahradí 0)
výsledkom X (posledný stĺpec) je logický súčet dvoch stĺpcov a
5) Ak chcete získať odpoveď, napíšte bity zo stĺpca X zhora nadol:
6) preveďte toto číslo do desiatkovej sústavy:
odpoveď: 171
Aké je najväčšie celé číslo X, pre ktoré platí výrok (10 (X+1)·(X+2))?
Riešenie.
Rovnica je operácia implikácie medzi dvoma vzťahmi:
1) Samozrejme, tu môžete použiť rovnakú metódu ako v príklade 2208, ale budete musieť vyriešiť kvadratické rovnice (nechcem...);
2) Všimnite si, že podľa podmienky nás zaujímajú iba celé čísla, takže sa môžeme pokúsiť nejako transformovať pôvodný výraz a získať ekvivalentný výrok (presné hodnoty koreňov nás vôbec nezaujímajú!);
3) Zvážte nerovnosť: samozrejme, môže to byť kladné alebo záporné číslo;
4) Je ľahké skontrolovať, či v doméne platí tvrdenie pre všetky celé čísla a v doméne - pre všetky celé čísla (aby nedošlo k zámene, je vhodnejšie použiť neprísne nerovnosti a namiesto a );
5) Preto ho pre celé čísla možno nahradiť ekvivalentným výrazom
6) doménou pravdivosti výrazu je spojenie dvoch nekonečných intervalov;
7) Teraz zvážte druhú nerovnosť: je zrejmé, že to môže byť aj kladné alebo záporné číslo;
8) V oblasti platí výrok pre všetky celé čísla av oblasti - pre všetky celé čísla, preto ho pre celé čísla možno nahradiť ekvivalentným výrazom
9) doménou pravdivosti výrazu je uzavretý interval;
10) Daný výraz platí všade okrem oblastí, kde a ;
11) Upozorňujeme, že hodnota už nie je vhodná, pretože tam a , čiže implikácia dáva 0;
12) Pri dosadzovaní 2, (10 (2+1) · (2+2)), alebo 0 → 0, ktorá podmienku spĺňa.
Takže odpoveď je 2.
odpoveď: 2
Aké je najväčšie celé číslo X, pre ktoré je výrok pravdivý
(50 (X+1)·(X+1))?
Riešenie.
Aplikujme implikačnú transformáciu a transformujme výraz:
(50 (X+1)·(X+1)) ⇔ ¬(X2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Logické OR je pravdivé, keď je pravdivé aspoň jedno logické tvrdenie. Po vyriešení oboch nerovností a pri zohľadnení toho, že vidíme, že najväčšie celé číslo, pre ktoré je splnená aspoň jedna z nich, je 7 (na obrázku je kladné riešenie druhej nerovnosti znázornené žltou a prvé modrou farbou).
odpoveď: 7
Uveďte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
falošné. Napíšte odpoveď ako reťazec 4 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.
Duplikuje úlohu 3584.
Odpoveď: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Riešenie.
Aplikujme implikačnú transformáciu:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Aplikujme negáciu na obe strany rovnice:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Poďme previesť:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Preto M = 0, N = 0, teraz zvážte (¬K ∧ L ∨ M ∧ L):
z toho, že M = 0, N = 0, vyplýva, že M ∧ L = 0, potom ¬K ∧ L = 1, teda K = 0, L = 1.
Odpoveď: 0100
Zadajte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
falošné. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Napíšme rovnicu pomocou jednoduchšieho zápisu operácií (podmienka „výraz je nepravdivý“ znamená, že sa rovná logickej nule):
1) z formulácie podmienky vyplýva, že výraz musí byť nepravdivý len pre jednu množinu premenných
2) z pravdivostnej tabuľky operácie „implikácia“ vyplýva, že tento výraz je nepravdivý vtedy a len vtedy, ak súčasne
3) prvá rovnosť (logický súčin sa rovná 1) je splnená vtedy a len vtedy a ; z toho vyplýva (logický súčet sa rovná nule), čo sa môže stať len vtedy, keď ; Takto sme už definovali tri premenné
4) z druhej podmienky, , for a získame .
Duplikuje úlohu
Odpoveď: 1000
Zadajte hodnoty logických premenných P, Q, S, T, pri ktorých je logický výraz
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) je nepravda.
Napíšte odpoveď ako reťazec štyroch znakov: hodnoty premenných P, Q, S, T (v tomto poradí).
Riešenie.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ Т)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Aplikujme implikačnú transformáciu:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Odpoveď: 0100
Zadajte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(K → M) ∨ (L ∧ K) ∨ ¬N
falošné. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Logické OR je nepravdivé vtedy a len vtedy, ak sú oba výroky nepravdivé.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Aplikujme implikačnú transformáciu na prvý výraz:
¬K ∨ M = 0 => K = 1, M = 0.
Zvážte druhý výraz:
(L ∧ K) ∨ ¬N = 0 (pozri výsledok prvého výrazu) => L ∨ ¬N = 0 => L = 0, N = 1.
Odpoveď: 1001.
Odpoveď: 1001
Zadajte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
pravda. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Logické "AND" je pravdivé vtedy a len vtedy, ak sú pravdivé oba výroky.
1) (K → M) = 1 Použiť implikačnú transformáciu: ¬K ∨ M = 1
2) (K → ¬M) = 1 Použiť implikačnú transformáciu: ¬K ∨ ¬M = 1
Z toho vyplýva, že K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Aplikujme implikačnú transformáciu: K ∨ (M ∧ ¬L ∧ N) = 1 z toho, že dostaneme K = 0.
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 úloh jednotnej štátnej skúšky. Prezentácia môže byť užitočná pri vyučovaní na tému „Logika“ v špecializovaných triedach, ako aj pri príprave na jednotnú štátnu skúšku.
Stiahnuť ▼:
Náhľad:
Ak chcete použiť ukážky prezentácií, vytvorte si účet Google a prihláste sa doň: https://accounts.google.com
Popisy snímok:
Riešenie úlohy B15 (systémy logických rovníc) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18. novembra 2013, Saratov
Úloha B15 je jednou z najťažších na Jednotnej štátnej skúške z informatiky!!! Testujú sa tieto zručnosti: konvertovať výrazy obsahujúce logické premenné; opísať v prirodzenom jazyku množinu hodnôt logických premenných, pre ktoré je daná množina logických premenných pravdivá; spočítajte počet binárnych množín, ktoré spĺňajú dané podmienky. Najťažšia vec je, pretože... neexistujú žiadne formálne pravidlá, ako to urobiť, vyžaduje si to dohady.
Bez čoho sa nezaobídeš!
Bez čoho sa nezaobídeš!
Symboly spojenie: A /\ B , A B , AB , A & B, A a B disjunkcia: A \ / B , A + B , A | B , A alebo B negácia: A , A, nie A ekvivalencia: A B, A B, A B bez „alebo“: A B , A xor B
Metóda nahradenia premennej Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x9, x10 existuje, ktoré spĺňajú všetky podmienky uvedené nižšie: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, …, x9, x10, pre ktoré tento systém rovnosti platí. Ako odpoveď musíte uviesť počet takýchto sád (demo verzia 2012)
Riešenie Krok 1. Zjednodušte zmenou premenných t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 Po zjednodušení: (t1 \/ t2) /\ (¬t1 \/\ t2) = 1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Uvažujme jednu z rovníc: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Je zrejmé, že je to =1 iba vtedy, ak jedna z premenných je 0 a druhá je 1 Použime vzorec na vyjadrenie operácie XOR pomocou konjunkcie a disjunkcie: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
Krok 2. Systémová analýza ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 0 1 0 Т1 .Do. tk = x2k-1 ≡ x2k (t1 = x1 x2,….), potom každá hodnota tk zodpovedá dvom párom hodnôt x2k-1 a x2k, napríklad: tk =0 zodpovedá dvom párom - (0 ,1) a (1, 0) , a tk =1 – dvojice (0,0) a (1,1).
Krok 3. Počítanie počtu riešení. Každé t má 2 riešenia, počet ts je 5. Teda. pre premenné t je 2 5 = 32 riešení. Ale pre každé t zodpovedá dvojica riešení x, t.j. pôvodný systém má 2*32 = 64 riešení. odpoveď: 64
Spôsob eliminácie časti riešení Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x5, y1,y2,..., y5 existuje, ktoré spĺňajú všetky nižšie uvedené podmienky: (x1→ x2 )∧(x2→x3)∧(x3→x4)∧(x4→x5) =1; (y1→ y2)∧(y2→y3)∧(y3→y4) ∧(y4→y5) =1; y5 → x5 = 1. Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, ..., x5, y 1 , y2, ... , y5, pre ktoré tento systém rovnosti platí. V odpovedi musí byť uvedený počet takýchto sád.
Riešenie. Krok 1. Postupné riešenie rovníc x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Prvá rovnica je konjunkcia viacerých operácií implikácie, rovná 1, t.j. každá z implikácií je pravdivá. Implikácia je nepravdivá iba v jednom prípade, keď 1 0, vo všetkých ostatných prípadoch (0 0, 0 1, 1 1) vráti operácia 1. Zapíšme si to do tabuľky:
Krok 1. Sekvenčné riešenie rovníc T.o. Získalo sa 6 sád riešení pre x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Podobne dospejeme k záveru, že pre y1, y2, y3, y4, y5 existuje rovnaká množina riešení. Pretože tieto rovnice sú nezávislé, t.j. nemajú spoločné premenné, potom riešenie tohto systému rovníc (bez zohľadnenia tretej rovnice) bude 6 * 6 = 36 párov „X“ a „Y“. Uvažujme tretiu rovnicu: y5→ x5 =1 Riešením sú dvojice: 0 0 0 1 1 1 Dvojica nie je riešením: 1 0
Porovnajme získané riešenia Kde y5 =1, x5=0 nie je vhodné. takýchto dvojíc je 5. Počet riešení sústavy: 36-5= 31. Odpoveď: Bolo treba 31 kombinatoriky!!!
Metóda dynamického programovania Koľko rô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žstvo takýchto sád.
Krok riešenia 1. Analýza podmienky Vľavo v rovnici sú operácie implikácie zapísané postupne, priorita je rovnaká. Prepíšme: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Poznámka! Každá nasledujúca premenná nezávisí od predchádzajúcej, ale od výsledku predchádzajúcej implikácie!
Krok 2. Odhalenie vzoru Zoberme si prvú implikáciu, X 1 → X 2. Tabuľka pravdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednej 0 sme dostali 2 jednotky a z 1 dostali sme jednu 0 a jednu 1. Existuje len jedna 0 a tri 1, toto je výsledok prvej operácie.
Krok 2. Odhalenie vzoru Spojením x 3 s výsledkom prvej operácie dostaneme: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Od dvoch 0 – dvoch 1, od každého 1 (sú 3) jedna 0 a jedna 1 (3+3)
Krok 3. Odvodenie vzorca T.o. môžete vytvoriť vzorce na výpočet počtu núl N i a počtu jednotiek E i pre rovnicu s premennými i: ,
Krok 4. Vyplnenie tabuľky Vyplňte tabuľku zľava doprava pre i = 6, pričom pomocou vyššie uvedených vzorcov vypočítame počet núl a jednotiek; tabuľka ukazuje, ako je nasledujúci stĺpec zostavený z predchádzajúceho: počet premenných 1 2 3 4 5 6 Počet núl N i 1 1 3 5 11 21 Počet jednotiek E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Odpoveď: 43
Metóda využívajúca zjednodušenia logických výrazov Koľko rôznych riešení má rovnica ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 kde J, K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt J, K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie Všimnite si, že J → K = ¬ J K Zavedme zmenu premenných: J → K=A, M N L =B Prepíšme rovnicu s prihliadnutím na zmenu: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Je zrejmé, že A B pre rovnaké hodnoty A a B 6. Uvažujme poslednú implikáciu M → J = 1 Toto je možné, ak: M= J=0 M=0, J=1 M=J=1
Riešenie Pretože A B, potom Keď M=J=0 dostaneme 1 + K=0. Žiadne riešenia. Keď M=0, J=1 dostaneme 0 + K=0, K=0 a N a L sú ľubovoľné, 4 riešenia: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1
Riešenie 10. Keď M=J=1 dostaneme 0+K=1 *N * L, alebo K=N*L, 4 riešenia: 11. Celkom má 4+4=8 riešení Odpoveď: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1
Zdroje informácií: O.B. Bogomolová, D.Yu. Usenkov. B15: nové úlohy a nové riešenia // Informatika, č. 6, 2012, s. 35 – 39. K.Yu. Polyakov. Logické rovnice // Informatika, č. 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronický zdroj]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronický zdroj].
