Metoda rješavanja sustava logičkih jednadžbi. Sustavi logičkih jednadžbi u zadacima Jedinstvenog državnog ispita iz informatike Rješavanje logičkih jednadžbi u informatici online

Rješenje jednadžbe 1. Prijeći na prefiksni oblik pisanja jednadžbe, zamjenjujući simbole negacija sa ¬ 2. Konstruirati naslov tablice istinitosti posebnog tipa 3. Popuniti retke tablice istinitosti za sve kombinacije A i B, zamjenjujući 0 ili 1 umjesto X. 4. Generirajte tablicu istinitosti za X = F (A,B) 5. Pomoću tablice istinitosti odredite tip funkcije X, ako je potrebno, koristeći metode konstruiranja SCNF i SDNF, o čemu će biti riječi u nastavku.

Konstrukcija tablice istinitosti posebnog oblika ¬((A+B)·(X A·B))=¬(B+¬(X A))

Tablica istinitosti X=F(A, B) ABX Odgovara negaciji implikacije B u A ODGOVORU:

Kombinacijski sklopovi logičkih uređaja Osnovni elementi (GOST): 1 A B Disjunkcija A B Ekvivalencija & A B Konjunkcija M2 A B XOR

Kombinacijski sklopovi logičkih uređaja Osnovni elementi (GOST): 1 A B Implikacija & A B Schaefferov element & A B Koimplikacija 1 A B Webb element

Primjer kruga F 1 & 1 & & 1M2 B A

Rješavanje sklopova 1. Opcija - pretvaranje sklopa u složeni logički izraz i zatim njegovo pojednostavljenje u skladu sa zakonima logike. Opcija 2 – konstrukcija tablice istinitosti i zatim, ako je potrebno, konstrukcija kroz SKNF ili SDNF (vidi dolje). Razmotrimo drugu opciju, jer je jednostavnija i razumljivija.

Konstrukcija tablice istinitosti AB A + B + · B B · A + A B A + · ·

Tablica istinitosti F(A, B) ABX Odgovara negaciji implikacije B u A ODGOVORU:

SDNF i SKNF (definicije) Elementarna konjunkcija je konjunkcija više varijabli, uzetih sa ili bez negacije, a među varijablama može biti istovjetnih.Elementarna disjunkcija se naziva disjunkcija više varijabli, uzetih sa ili bez negacije, a među varijablama mogu biti identične.Svaka disjunkcija elementarnih konjunkcija Nazovimo je disjunktivnom normalnom formom (DNF) Svaku konjunkciju elementarnih disjunkcija nazovimo konjunktivnom normalnom formom (DNF)

SDNF i SCNF (definicije) Savršena disjunktivna normalna forma (PDNF) naziva se DNF u kojoj nema identičnih elementarnih konjunkcija i sve se konjunkcije sastoje od istog skupa varijabli, u kojima se svaka varijabla pojavljuje samo jednom (eventualno s negacijom). Savršena konjunktivna normalna forma (PCNF) je CNF u kojoj nema identičnih elementarnih disjunkcija i sve se disjunkcije sastoje od istog skupa varijabli, u kojem se svaka varijabla pojavljuje samo jednom (moguće s negacijom).

Algoritam za dobivanje SDNF iz tablice istinitosti 1. Označite retke tablice istinitosti u zadnjem stupcu kojih ima 1. 2. Napišite za svaki označeni red konjunkciju svih varijabli na sljedeći način: ako je vrijednost varijable u dani redak je 1, tada uključite samu ovu varijablu u konjunkciju, ako je jednaka 0, onda je njena negacija. 3. Sve nastale veznike poveži u disjunkciju. Algoritam za dobivanje SCNF iz tablice istinitosti 1. Označite retke tablice istinitosti u zadnjem stupcu kojih ima 0. 2. Za svaki označeni red ispišite disjunkciju svih varijabli na sljedeći način: ako je vrijednost varijable u dani redak je 0, zatim uključite samu ovu varijablu u konjunkciju, ako je jednaka 1, onda je njena negacija. 3. Povežite sve nastale disjunkcije u konjunkciju.

Primjer konstruiranja SKNF XY F(X,Y) Označi nule 2. Disjunkcije: X + Y 3. Konjunkcija: (X + Y) · (X + Y)

Veličina: px

Počnite prikazivati ​​sa stranice:

Prijepis

1 Rješavanje logičkih jednadžbi i sustava logičkih jednadžbi Neka je F(x, x2, xn) logička funkcija od n varijabli. Logička jednadžba ima oblik: F(x, x2, xn) = C, gdje konstanta C ima vrijednost odn. Logička jednadžba može imati do 2 n različitih rješenja. Ako je C jednako, tada su rješenja svi oni skupovi varijabli iz tablice istinitosti na kojima funkcija F poprima vrijednost true (). Preostali skupovi su rješenja jednadžbe s C jednakim nuli. Uvijek možete razmatrati samo jednadžbe oblika: F(x, x2, xn) = Doista, neka je dana jednadžba: F(x, x2, xn) = U ovom slučaju možete prijeći na ekvivalentnu jednadžbu: F( x, x2, xn) = Razmotrimo sustav od k logičkih jednadžbi: F(x, x2, xn) = F2(x, x2, xn) = ( Fk(x, x2, xn) = Rješenje sustava je skup varijabli na kojima su zadovoljene sve jednadžbe sustava. U logičkim terminima funkcija da bi se dobilo rješenje sustava logičkih jednadžbi, treba pronaći skup na kojem je istinita logička funkcija F, koja predstavlja konjunkciju izvornih funkcija F: F = F F2 Fk Ako je broj varijabli mali, npr. manji od 5, tada nije teško konstruirati tablicu istine za funkciju F, koja omogućuje reći koliko rješenja ima sustav i koji su skupovi koji pružiti rješenja. U nekim USE problemima pronalaženja rješenja sustava logičkih jednadžbi, broj varijabli dosegne vrijednost. Tada konstruiranje tablice istinitosti postaje praktički nerješiv zadatak. Da bi se problem riješio, potreban je drugačiji pristup. Za proizvoljan sustav jednadžbi ne postoji opća metoda osim nabrajanja koja omogućuje rješavanje takvih problema. U zadacima predloženim na ispitu rješavanje se obično temelji na uzimanju u obzir specifičnosti sustava jednadžbi. Međutim, ponavljam da osim isprobavanja svih opcija za skup varijabli, ne postoji opći način za rješavanje problema. Rješenje se mora graditi na temelju prezentiranog sustava. Često je korisno izvesti preliminarno pojednostavljenje sustava jednadžbi korištenjem poznatih zakona logike. Još jedna korisna tehnika za rješavanje ovog problema je sljedeća. Ne zanimaju nas svi skupovi, nego samo oni na kojima funkcija Φ ima vrijednost. Umjesto da izgradimo potpunu tablicu istine, izgradit ćemo njen analog - binarno stablo odlučivanja. Svaka grana ovog stabla odgovara

2 na jedno rješenje i specificira skup na kojem funkcija F ima vrijednost. Broj grana u stablu odlučivanja podudara se s brojem rješenja sustava jednadžbi. Objasnit ću što je binarno stablo odlučivanja i kako se gradi koristeći primjere nekoliko problema. Problem Koliko različitih skupova vrijednosti logičkih varijabli x, x2, x3, x4, x5, y, y2, y3, y4, y5 postoji koji zadovoljavaju sustav dviju jednadžbi? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ( (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Odgovor: Sustav ima 36 različitih rješenja. Sustav jednadžbi uključuje dvije jednadžbe. Nađimo broj rješenja za prvu jednadžbu ovisno o 5 varijabli x, x2, x5. Prva jednadžba se može smatrati sustavom od 5 jednadžbi. Kao što je bilo prikazano, sustav jednadžbi zapravo predstavlja konjunkciju logičkih funkcija. Obrnuta izjava je također istinita - konjunkcija uvjeta može se smatrati sustavom jednadžbi. Izgradimo stablo odlučivanja za implikaciju (x x2) - prvi član od konjunkcija, koja se može smatrati prvom jednadžbom. Evo kako izgleda grafički prikaz ovog stabla: X X2 Stablo se sastoji od dvije razine prema broju varijabli u jednadžbi. Prva razina opisuje prvu varijablu X Dvije grane ove razine odražavaju moguće vrijednosti ove varijable i. Na drugoj razini, grane stabla odražavaju samo one moguće vrijednosti varijable X2 za koje je jednadžba točna. Budući da jednadžba specificira implikaciju, grana na kojoj X ima vrijednost zahtijeva da X2 ima vrijednost na toj grani. Grana na kojoj X ima vrijednost daje dvije grane s vrijednostima X2 jednakim i. Konstruirano stablo specificira tri rješenja kod kojih implikacija X X2 poprima vrijednost. Na svakoj grani ispisuje se odgovarajući skup vrijednosti varijable, dajući rješenje jednadžbe. Ovi skupovi su: ((,), (,), (,)) Nastavimo graditi stablo odlučivanja, dodajući sljedeću jednadžbu, sljedeću implikaciju X2 X3. Specifičnost našeg sustava jednadžbi je u tome što svaka nova jednadžba sustava koristi jednu varijablu iz prethodne jednadžbe, dodajući jednu novu varijablu. Budući da varijabla X2 već ima vrijednosti u stablu, tada će na svim granama gdje varijabla X2 ima vrijednost, varijabla X3 također imati vrijednost. Za takve grane, konstrukcija stabla nastavlja se na sljedeću razinu, ali se nove grane ne pojavljuju. Jedina grana u kojoj varijabla X2 ima vrijednost granat će se u dvije grane u kojima će varijabla X3 primati vrijednosti i. Dakle, svakim dodavanjem nove jednadžbe, uzimajući u obzir njezine specifičnosti, dodaje se jedno rješenje.

3 Izvorna prva jednadžba: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ima 6 rješenja. Evo kako izgleda kompletno stablo rješenja za ovu jednadžbu: X X2 X3 X4 X5 Druga jednadžba našeg sustava slična je prvoj: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Jedina razlika je u tome što jednadžba koristi varijable Y. Ova jednadžba također ima 6 rješenja. Budući da se svako rješenje za varijable Xi može kombinirati sa svakim rješenjem za varijable Yj, ukupan broj rješenja je 36. Napominjemo da konstruirano stablo odlučivanja ne daje samo broj rješenja (po broju grana), već i sama rješenja ispisana na svakoj grani stabla. Problem 2 Koliko različitih skupova vrijednosti logičkih varijabli x, x2, x3, x4, x5, y, y2, y3, y4, y5 postoji koji zadovoljavaju sve uvjete navedene u nastavku? (x x2) ^ (x2 x3) ^ (x3 x4) ^ (x4 x5) = ((y y2) ^ (y2 y3) ^ (y3 y4) ^ (y4 y5) = (x y) = Odgovor: 3 Ovaj problem je modifikacija prethodnog problema. Razlika je u tome što je dodana još jedna jednadžba koja povezuje varijable X i Y. Iz jednadžbe X Y slijedi da kada X ima vrijednost (jedno takvo rješenje postoji), onda Y ima vrijednost. Dakle, postoji jedan skup , na kojem

4 X i Y imaju značenja. Kada je X jednako, Y može imati bilo koju vrijednost, i. Dakle, svaki skup s X jednakim, a ima 5 takvih skupova, odgovara svih 6 skupova s ​​varijablama Y. Dakle, ukupan broj rješenja je 3. Zadatak 3. Koliko rješenja ima jednadžba: (X X2) ( X2 X3) (X3 X4) (X4 X5) (X5 X) = Odgovor: 2 Podsjećajući se na osnovne ekvivalencije, zapisujemo našu jednadžbu u obliku: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Ciklički lanac implikacija znači identičnost varijabli, tako da je naša jednadžba ekvivalentna jednadžbi: X X2 X3 X4 X5 = Ova jednadžba ima dva rješenja kada su svi Xi ili ili. Problem 4 Koliko rješenja ima jednadžba: (X X2) (X2 X3) (X3 X4) (X4 X2) (X4 X5) = Odgovor: 4 Baš kao u problemu 2, prijeđimo s cikličkih implikacija na identitete, prepisujući jednadžba u obliku: (X X2) (X2 X3 X4) (X4 X5) = Izgradimo stablo odlučivanja za ovu jednadžbu: X X2 X3 X4 X5

5 Zadatak 4 Koliko rješenja ima sljedeći sustav jednadžbi? Odgovor: 64 ((X X2) (X3 X4)) ((X X2) (X3 X4)) = ((X3 X4) (X5 X6)) ((X3 X4) (X5 X6)) = ((X5 X6) (X7 X8)) ((X5 X6) (X7 X8)) = (((X7 X8) (X9 X)) ((X7 X8) (X9 X)) = Prijeđimo s varijabli na 5 varijabli uvođenjem sljedeće promjene varijabli: Y = (X X2); Y2 = (X3 X4); Y3 = (X5 X6); Y4 = (X7 X8); Y5 = (X9 X); Tada će prva jednadžba poprimiti oblik: (Y Y2 ) (Y Y2) = Jednadžba se može pojednostaviti zapisivanjem u obliku: (Y Y2) = Prelazeći na tradicionalni oblik, zapisujemo sustav nakon pojednostavljenja u obliku: (Y Y2) = (Y2 Y3) = ( (Y3 Y4) = (Y4 Y5) = Stablo odlučivanja za ovaj sustav je jednostavno i sastoji se od dvije grane s izmjeničnim vrijednostima varijabli: Y Y2 Y3 Y4 Y5 Vraćajući se na izvorne varijable X, primjećujemo da svaka vrijednost varijable Y odgovara 2 vrijednosti varijabli X, stoga svako rješenje u varijabli Y generira 2 5 rješenja u varijabli X. Dvije grane proizvode 2 * 2 5 rješenja, tako da je ukupan broj rješenja 64. Kao što vidite, svaki problem rješavanja sustava jednadžbi zahtijeva drugačiji pristup. Uobičajena tehnika je izvođenje ekvivalentnih transformacija za pojednostavljenje jednadžbi.

6 Uobičajena tehnika je konstruirati stabla odlučivanja. Pristup koji se koristi djelomično podsjeća na konstruiranje tablice istinitosti s tom posebnošću da nisu konstruirani svi skupovi mogućih vrijednosti varijabli, već samo oni na kojima funkcija poprima vrijednost (true). Često u predloženim problemima nema potrebe za izgradnjom potpunog stabla odlučivanja, budući da je već u početnoj fazi moguće uspostaviti obrazac pojavljivanja novih grana na svakoj sljedećoj razini, kao što je učinjeno, na primjer, u problemu .

Putilov Viktor Vasilievich MAOU Srednja škola 46 Sustavi logičkih jednadžbi. Sadržaj Napomena o zamjeni varijabli... Zadaci koji sadrže implikaciju ili njezin ekvivalentni zapis....2 Prisutnost dodatnog uvjeta...6

Rješavanje sustava logičkih jednadžbi. Koliko rješenja ima jednadžba A BB C C D = 0 Broj skupova varijabli je =. Možete izraditi tablicu istinitosti i provjeriti koliko skupova odgovara

Konstrukcija i analiza tablica istinitosti logičkih izraza. Jedinstveni državni ispit 2015. 2 (osnovna razina, vrijeme 3 minute) Primjer P-13. Svaki Booleov izraz A i B ovisi o istom skupu od 5 varijabli.

N B Rogov Kako naučiti riješiti zadatak B15 Jedinstvenog državnog ispita iz informatike (sustavi logičkih jednadžbi) u 180+ minuta Materijali za nastavu Online odjeljak: http://basicschoolru/?page=eam_info_b15 Teorijski uvod:

B4 Tema: Pretvaranje logičkih izraza. O notacijama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematičkoj logici (,), nezgodne su i nisu intuitivno jasne.

Matematika i matematičko modeliranje UDK 004.023 Semenov Sergej Maksimovič Vladivostok Državno sveučilište ekonomije i usluga Rusija. Vladivostok O jednom načinu rješavanja logičkih sustava

B4 (visoka razina, vrijeme 1 min) Tema: Pretvaranje logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematičkoj logici (,),

B0 (visoka razina, vrijeme 0 min) Tema: Pretvaranje logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematičkoj logici (,),

19022017 Bit operacije u problemima Jedinstvenog državnog ispita KIM iz računarstva II dio KYu Polyakov, dt.

Samostalni rad na temi “Metode zadavanja logičkih funkcija” 1. Izračunati vrijednost funkcije F(x, y, z) = na skupu varijabli (1, 1, 0). 3. Odredite ekvivalentnost funkcija F(x, y, z) = i G(x,

Logika je znanost koja proučava metode utvrđivanja istinitosti ili netočnosti nekih izjava na temelju istinitosti ili netočnosti drugih izjava. Iskaz (presuda) je neka rečenica koja

B visoka razina, vrijeme 0 min) K. Polyakov, 009-0 Tema: Transformacija logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

Problem 1: Zadan je fragment tablice istinitosti izraza F: Kakav F može biti izraz? X Y Z F 0 0 0 0 0 0 1 0 1 1 1 1 1) X /\ Y /\ Z 2) X \/ Y \/ Z 3) X \/ Y \/ Z 4) X /\ Y /\ Z Razmotrite prvi izraz

FUNKCIJE LOGIČKE ALGEBRE (nastavak) Broj Booleovih funkcija od n varijabli nalazi se po formuli: P2 (n) = 2 2n Logičke funkcije dviju varijabli 6 Najčešće se koriste sljedeće funkcije: f (x,

Rješenja problema u dvovrijednoj logici F.G. Korablev Problem 1. Za funkciju f(x, y, z) = ((x y) (x z)) (z x) pronaći bitne i fiktivne varijable, izvesti operaciju eliminacije fiktivnih varijabli. Riješenje.

051216 Bit operacije u problemima Jedinstvenog državnog ispita KIM-a iz informatike II. dio KYu Polyakov, doktor tehničkih znanosti, nastavnik informatike GBOU Srednja škola 163, Sankt Peterburg Ovaj članak raspravlja o problemima sljedećeg tipa po prvi put ove

Mironchik E.A., učitelj informatike, Novokuznetsk Rješavanje zadatka Jedinstvenog državnog ispita-18 s bitnim operacijama Opisana metoda demonstrira metodu rješavanja koja se temelji na identičnim prijelazima, tj. = "radi"

Tema: Osnovni pojmovi matematičke logike. Primjeri pitanja O notacijama Nažalost, oznake za logičke operacije I, ILI i NE, usvojene u "ozbiljnoj" matematičkoj logici (,), nezgodne su i intuitivne

1. dio 1. Označite koji je logički izraz ekvivalentan izrazu A /\ (B \/ C). 1) A \/ B \/ C 2) A /\ B /\ C 3) A /\ B /\ C 4) A /\ B /\ C Rješenje: pomoću de Morganove formule (B \/ C) = B /\ C i

Glinka N.V. Korišteni zapis Negacija Množenje (konjunkcija) Zbrajanje (disjunkcija) Implikacija Ekvivalencija Primjeri zadataka prije školske godine 2010. Koliko različitih rješenja ima jednadžba ((K

Bit operacije u KIM problemima u informatici Vrste problema Ovaj webinar raspravlja o problemima sljedećeg tipa (ovi problemi su se prvi put pojavili u KIM na Jedinstvenom državnom ispitu 2015): Uvedite izraz M & K, označavajući

Praktični rad 6 Rješavanje logičkih problema korištenjem zakona logičke algebre Cilj rada: jačanje sposobnosti transformacije logičkih izraza korištenjem zakona logičke algebre, izračunavanje

A10 (osnovna razina, vrijeme 1 min) Tema: Transformacija logičkih izraza. De Morganove formule. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

Gurskaya K.A., Ivin V.V., Semenov S.M. Rješavanje problema matematičke logike na Jedinstvenom državnom ispitu iz računarstva 1 UDC 004.9 Gurskaya K.A., Ivin V.V., Semenov S.M. Udžbenik "Rješavanje problema matematičke logike na Jedinstvenom državnom ispitu"

SADRŽAJ Predgovor.................................. 3 Poglavlje 1. Matematička logika...... ........ .... 4 1. Propozicijska algebra.................. 4 2. Booleove algebre.......... ........ .... 12 3. Račun

PREDAVANJE 5 LOGIČKE OPERACIJE U INFORMACIJSKIM ZNANOSTIMA 1. Matematička logika i računarstvo 2. Logički izrazi i logičke operacije 3. Konstrukcija tablica istine i logičkih funkcija 4. Logički zakoni i pravila

B5 visoka razina, vrijeme 0 min) Tema: Transformacija logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematičkoj logici, su nezgodne,

Logička algebra Logička algebra je formalna logička teorija, grana matematičke logike koju je u 19. stoljeću razvio engleski matematičar George Boole. Algebra logike koristi algebarske metode

2 (osnovna razina, vrijeme min) Tema: Konstrukcija i analiza istinitosnih tablica logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

A8 (osnovna razina, vrijeme 1 min) Tema: Transformacija logičkih izraza. De Morganove formule. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

B15 Navedite vrijednosti varijabli K, L, M, N za koje je logički izraz (K M) (L K) N netočan. Napišite svoj odgovor kao niz od četiri znaka: vrijednosti varijabli K, L, M i N (tim redoslijedom).

Osnove logike. Logičke operacije i tablice istine. Osnove logike. Logičke operacije i tablice istine Ova stranica govori o 6 logičkih operacija: konjunkcija, disjunkcija, inverzija,

Identiteti Booleove algebre Glavna zadaća matematičke logike je odrediti značenje složenog iskaza na temelju lažnosti ili istinitosti jednostavnih iskaza. Logičke operacije u iskaznoj algebri

Općinska proračunska obrazovna ustanova grada Abakana "Srednja škola 11" Metodološki razvoj na temu Rješenje zadataka tipa 18 Jedinstveni državni ispit iz informatike Atyushkina Marina Valerievna,

Tema 4. Logičke osnove RAČUNALA 1. OSNOVNE INFORMACIJE IZ LOGIČKE ALGEBRE... 1 2. ZAKONI LOGIČKE ALGEBRE... 4 3. KONCEPT MINIMIZACIJE LOGIČKIH FUNKCIJA... 6 4. TEHNIČKA INTERPRETACIJA LOGIČKIH FUNKCIJA...

Tema 9. Logičke osnove računala. 1. Logika. Informacije koje se obrađuju u računalu predstavljaju pomoću fizičkih veličina koje mogu poprimiti samo dva stabilna stanja i nazivaju se "binarne varijable".

Iracionalne nejednadžbe Nejednadžbe u kojima je varijabla sadržana pod predznakom korijena nazivaju se iracionalnim. Glavna metoda za rješavanje iracionalnih nejednadžbi je metoda redukcije izvorne

26 transformacije, izgraditi točan lanac zaključivanja i napraviti aritmetičku pogrešku u posljednjoj radnji. Imajte na umu da se pri rješavanju ovog zadatka postiže broj samo aritmetičkih operacija

Regionalno natjecanje obrazovnih, istraživačkih i dizajnerskih radova učenika „Primijenjena pitanja matematike” Algebra Algebra logike Alena Sergeevna Semusheva, Gradska obrazovna ustanova „Lyceum” Perm, klasa. Borkova Olga Vladimirovna,

K. Polyakov, 009-0 B5 visoka razina, vrijeme 0 min) Tema: Transformacija logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

PRAKTIČNA NASTAVA 1 Linearne jednadžbe prvog reda, Bernoullijeva jednadžba Jednadžba u totalnim diferencijalima Linearna diferencijalna jednadžba prvog reda je jednadžba + p(= q(Ako

Moskovsko državno tehničko sveučilište nazvano po N.E. Bauman Fakultet temeljnih znanosti Zavod za matematičko modeliranje A.N. KAPITAL DASHMANN

A9 (osnovna razina, vrijeme 2 min) Tema: Konstrukcija istinitosnih tablica logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

Mironchik E.A., MB NOU "Lyceum", Novokuznetsk Metoda prikaza Zadatak. Koliko rješenja ima sustav: Sve jednadžbe uključene u sustav su istog tipa, a svaka jednadžba uključuje tri varijable. znajući

Savezna agencija za obrazovanje Uralsko državno ekonomsko sveučilište Yu. B. Melnikov Boolean i logičke funkcije Odjeljak elektroničkog udžbenika koji prati predavanje E-mail: [e-mail zaštićen],

E.V.Prosolupov 42. Booleova algebra. Funkcije logičke algebre 1 Booleove funkcije Razmotrit ćemo Booleove funkcije - funkcije čiji argumenti i vrijednosti imaju vrijednosti true i false. Bit će i istine i laži

Savezna agencija za obrazovanje Uralsko državno ekonomsko sveučilište Yu. B. Melnikov Boolean i logičke funkcije Odjeljak elektroničkog udžbenika koji prati predavanje Ed. 3., rev.

MINISTARSTVO OBRAZOVANJA I ZNANOSTI RF Savezna državna autonomna obrazovna ustanova visokog stručnog obrazovanja "NACIONALNO ISTRAŽIVAČKO TOMSK POLYTEHNIC SVEUČILIŠTE"

Praktičan rad 1. Logičke operacije. Ekvivalencija formula Cilj rada: Naučiti graditi tablice istinitosti logičkih izjava i transformirati formule pomoću osnovnih ekvivalencija Sadržaj

Kažu da je Aristotel, kada je došao na logiku, proslavio s gozbom i naredio klanje 40 ovaca. Od tada ovce više ne vole logiku. Osnovni pojmovi logičke algebre, 10. razred, 2017.-2018.

Diferencijalne jednadžbe prvog reda riješene s obzirom na derivaciju Teorem postojanja i jedinstvenosti rješenja U općem slučaju diferencijalna jednadžba prvog reda ima oblik F ()

Predavanje 2. Konjunktivni normalni oblici. Implicenta, jednostavna implicenta funkcije. Reducirana CNF funkcija logičke algebre. Metode konstruiranja skraćene CNF. Predavač Svetlana Nikolaevna Selezneva [e-mail zaštićen]

LOGIKA ISKAZA Izjave Izjava je deklarativna rečenica, čiji se sadržaj može ocijeniti kao istinit ili netočan. Razlikovati: apsolutno istinite izjave, apsolutno

Podijeli P.G. Kharkov Nacionalno sveučilište za mehaniku i matematiku Fakultet diskretne matematike. Bilješke s predavanja. Sadržaj 1. Iskazna algebra i logika. 1.1 Izjave i logičke operacije...

Zakoni algebarske logike Ovo je zanimljivo! Matematika i De Morganov zakon Kako matematički napisati da li točka x pripada segmentu? To se može učiniti ovako: 2 x 5. To znači da u isto vrijeme moramo

Matematička logika i teorija algoritama Pervukhin Mikhail Aleksandrovich Logička posljedica u AB Kažu da je formula ψ x 1, x n AB logična posljedica formula φ 1 (x 1, x n), φ m x 1,

Moskovsko državno tehničko sveučilište nazvano po N.E. Bauman Fakultet temeljnih znanosti Zavod za matematičko modeliranje A.N. KASIATOVIKOV

PREDAVANJE 21 POISSONOVE ZAGRADE. JACOBI-POISSONOVA TEOREMA. KANONIČKE TRANSFORMACIJE 1. Poissonove zagrade U prošlom predavanju uveden je pojam Lagrangeove zagrade. Ovaj izraz je sastavljen od parcijalnih izvedenica

USE zadatak 8 (“Poznavanje osnovnih pojmova i zakona matematičke logike”) ZAKONI LOGIČKE ALGEBRE X = X X /\ Y = Y /\ X X \/ Y = Y \/ X (X /\ Z) \/ (Y / \ Z )=(X \/ Y) /\ Z A\/ = A A/\ = A A/\ =. ZAKONI ALGEBRE

POGLAVLJE 6 Formalizam Poissonovih zagrada u klasičnoj mehanici 61 Poissonove zagrade Poissonove zagrade Neka su dane dvije dinamičke veličine, dvije funkcije kanonskih varijabli i vrijeme t: (i (Poissonova zagrada)

Laboratorijski rad BERLEKAMP-MESSIE ALGORITAM ZA PRONALAŽENJE KOEFICIJENATA POVRATNE SVEZE GENERATORA PSEUDO-SLUČAJNOG SLIJEDA Razmotrimo kako možemo vratiti polinom koji definira povratnu spregu

K.Yu. Polyakov, M.A. Roitberg Sustavi logičkih jednadžbi u problemima Jedinstvenog državnog ispita iz informatike K.Yu. Polyakov, M.A. Roitberg, 0 http://kpolkov.sp.ru K.Yu. Polyakov, M.A. Roitberg, 0 http://kpolkov.sp.ru Proizvodnja

Bit operacije u problemima Jedinstvenog državnog ispita KIM iz informatike K.Yu. Polyakov, doktor tehničkih znanosti, nastavnik informatike GBOU Srednja škola 163, St. Petersburg Ovaj članak raspravlja o sljedećoj vrsti problema (ovi problemi su se prvi put pojavili

Ministarstvo obrazovanja Ruske Federacije Donsko državno tehničko sveučilište Odsjek za višu matematiku Problemi u diskretnoj matematici Rostov na Donu 2001. UDK 517 Sastavio: Baranov

Dečki, nastavljamo proučavati veliku temu logaritma, danas ćemo pogledati kako riješiti razne jednadžbe koje sadrže logaritme. Logaritamska jednadžba je jednadžba poput ove

A3 (osnovna razina, vrijeme 2 min) Tema: Konstrukcija istinitosnih tablica logičkih izraza. O oznakama Nažalost, oznake za logičke operacije I, ILI i NE, prihvaćene u “ozbiljnoj” matematici

Trajanje 4 sata. LABORATORIJSKI RAD 2 ALGEBRA LOGIKE Svrha rada Proučiti osnove algebre logike. Ciljevi laboratorijskog rada Kao rezultat odrađene lekcije student mora: 1) znati: definicije

Nejednakosti C C Priprema za jedinstveni državni ispit 0 (materijal za predavanja za nastavnike 8040) Prokofjev AA aaprokof@yanderu Osnovne metode rješavanja: Zadaci C Rješavanje nejednakosti na intervalima Pojednostavljenje nejednakosti i redukcija

Dodatak 1 GRUPE, PRSTENOVI, POLJA Za kriptografiju, algebra je jedan od glavnih alata u teoretskom istraživanju i praktičnoj konstrukciji kriptografskih transformacija. Stoga, u ovom

Općinska proračunska obrazovna ustanova

"Srednja škola br. 18"

gradski okrug grada Salavata u Republici Baškortostan

Sustavi logičkih jednadžbi

u problemima Jedinstvenog državnog ispita iz informatike

Odjeljak "Osnove algebre logike" u zadacima Jedinstvenog državnog ispita smatra se jednim od najtežih i najtežih za rješavanje. Prosječan postotak riješenih zadataka na ovu temu je najmanji i iznosi 43,2.

Dio tečaja	Prosječni postotak izvršenja po grupama zadataka
Kodiranje informacija i mjerenje njihove količine
Informacijsko modeliranje
Sustavi brojeva
Osnove logičke algebre
Algoritmizacija i programiranje
Osnove informacijskih i komunikacijskih tehnologija

Na temelju KIM specifikacije za 2018., ovaj blok uključuje četiri zadatka različitih razina težine.

№ zadaci	Provjerljivo elementi sadržaja	Razina težine zadatka
	Sposobnost konstruiranja tablica istine i logičkih sklopova
	Mogućnost traženja informacija na internetu
	Poznavanje osnovnih pojmova i zakona matematička logika
	Sposobnost konstruiranja i transformiranja logičkih izraza

Zadatak 23 je visoke razine težine, stoga ima najniži postotak dovršenosti. Među pripremljenim maturantima (81-100 bodova) zadatak je riješilo 49,8%, srednje pripremljenih maturanata (61-80 bodova) 13,7%, preostala skupina studenata nije riješila ovaj zadatak.

Uspješnost rješavanja sustava logičkih jednadžbi ovisi o poznavanju logičkih zakona i preciznoj primjeni metoda rješavanja sustava.

Razmotrimo rješavanje sustava logičkih jednadžbi metodom preslikavanja.

(23.154 Polyakov K.Yu.) Koliko različitih rješenja ima sustav jednadžbi?

((x1  g1 )  (x2  g2 ))  (x1  x2 )  (g1  g2 ) =1

((x2  g2 )  (x3  g3 ))  (x2  x3 )  (g2  g3 ) =1

((x7  g7 )  (x8  g8 ))  (x7  x8 )  (g7  g8 ) =1

Gdje x1 , x2 ,…, x8, na1 ,y2 ,…,y8 - logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti varijabli za koje ova jednakost vrijedi. Kao odgovor morate navesti broj takvih skupova.

Riješenje. Sve jednadžbe uključene u sustav su istog tipa, a svaka jednadžba uključuje četiri varijable. Poznavajući x1 i y1, možemo pronaći sve moguće vrijednosti x2 i y2 koje zadovoljavaju prvu jednadžbu. Rezonirajući na sličan način, iz poznatih x2 i y2 možemo pronaći x3, y3 koji zadovoljavaju drugu jednadžbu. Odnosno, znajući par (x1, y1) i određujući vrijednost para (x2, y2), pronaći ćemo par (x3, y3), što će zauzvrat dovesti do para (x4, y4) i tako dalje.

Nađimo sva rješenja prve jednadžbe. To se može učiniti na dva načina: konstruirajte tablicu istinitosti, kroz zaključivanje i primjenu zakona logike.

Tablica istinitosti:

				x 1  y 1	x 2  y 2	(x 1  y 1)  (x2  y2)	(x 1  x2)	(y 1  y2)	(x 1  x2)  (y 1  y2)

Izrada tablice istine je naporna i vremenski neučinkovita, pa koristimo drugu metodu - logičko zaključivanje. Umnožak je jednak 1 ako i samo ako je svaki faktor jednak 1.

(x1  g1 )  (x2  g2 ))=1

(x1  x2 ) =1

(g1  g2 ) =1

Pogledajmo prvu jednadžbu. Posljedica je jednaka 1 kada je 0 0, 0 1, 1 1, što znači (x1 y1)=0 za (01), (10), tada je par (x2  g2 ) može biti bilo koji (00), (01), (10), (11), a kada (x1 y1) = 1, odnosno (00) i (11) par (x2 y2) = 1 uzima iste vrijednosti (00) i (11). Isključimo iz ovog rješenja one parove za koje su druga i treća jednadžba netočne, to jest x1=1, x2=0, y1=1, y2=0.

(x1 , g1 )	(x2 , g2 )

Ukupan broj parova 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Koliko različitih rješenja ima sustav logičkih jednadžbi?

(x 1  (x 2  g 2 ))  (g 1  g 2 ) = 1

(x 2  (x 3  g 3 ))  (g 2  g 3 ) = 1

...

( x 6  ( x 7  g 7 ))  ( g 6  g 7 ) = 1

x 7  g 7 = 1

Riješenje. 1) Jednadžbe su istog tipa, pa ćemo zaključivanjem pronaći sve moguće parove (x1,y1), (x2,y2) prve jednadžbe.

(x1  (x2  g2 ))=1

(g1  g2 ) = 1

Rješenje druge jednadžbe su parovi (00), (01), (11).

Pronađimo rješenja prve jednadžbe. Ako je x1=0, onda je x2, y2 - bilo koji, ako je x1=1, tada x2, y2 ima vrijednost (11).

Povežimo parove (x1, y1) i (x2, y2).

(x1 , g1 )	(x2 , g2 )

Napravimo tablicu za izračun broja parova u svakoj fazi.

							0

Uzimajući u obzir rješenja posljednje jednadžbe x 7  g 7 = 1, isključimo par (10). Odredite ukupan broj rješenja 1+7+0+34=42

3)(23.180) Koliko različitih rješenja ima sustav logičkih jednadžbi?

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Riješenje. 1) Jednadžbe su istog tipa, pa ćemo zaključivanjem pronaći sve moguće parove (x1,x2), (x3,x4) prve jednadžbe.

(x1  x2 )  (x3  x4 ) = 1

Isključimo iz rješenja parove koji u nizu daju 0 (1 0), to su parovi (01, 00, 11) i (10).

Povežimo parove (x1,x2), (x3,x4)

Svrha usluge. Online kalkulator je dizajniran za konstruiranje tablice istine za logički izraz.
Tablica istinitosti – tablica koja sadrži sve moguće kombinacije ulaznih varijabli i njihovih odgovarajućih izlaznih vrijednosti.
Tablica istinitosti sadrži 2n redaka, gdje je n broj ulaznih varijabli, a n+m su stupci, gdje su m izlazne varijable.

upute. Kada unosite s tipkovnice, koristite sljedeće oznake: Na primjer, logički izraz abc+ab~c+a~bc mora se unijeti ovako: a*b*c+a*b=c+a=b*c
Za unos podataka u obliku logičkog dijagrama koristite ovu uslugu.

Pravila za unos logičke funkcije

1. Umjesto simbola v (disjunkcija, ILI) koristite znak +.
2. Nema potrebe navesti oznaku funkcije prije logičke funkcije. Na primjer, umjesto F(x,y)=(x|y)=(x^y) trebate jednostavno unijeti (x|y)=(x^y) .
3. Maksimalan broj varijabli je 10.

Projektiranje i analiza računalnih logičkih sklopova provodi se pomoću posebne grane matematike – logičke algebre. U algebri logike mogu se razlikovati tri glavne logičke funkcije: “NE” (negacija), “I” (konjunkcija), “ILI” (disjunkcija).
Za izradu bilo kojeg logičkog uređaja potrebno je odrediti ovisnost svake od izlaznih varijabli o postojećim ulaznim varijablama; ta se ovisnost naziva funkcija preklopa ili funkcija logičke algebre.
Funkcija logičke algebre naziva se potpuno definiranom ako je zadano svih 2n njezinih vrijednosti, gdje je n broj izlaznih varijabli.
Ako nisu definirane sve vrijednosti, funkcija se naziva djelomično definirana.
Uređaj se naziva logičkim ako je njegovo stanje opisano pomoću funkcije logičke algebre.
Za predstavljanje funkcije logičke algebre koriste se sljedeće metode:
U algebarskom obliku, možete izgraditi krug logičkog uređaja pomoću logičkih elemenata.


Slika 1 - Dijagram logičkog uređaja

Definirane su sve operacije logičke algebre tablice istine vrijednosti. Tablica istinitosti određuje rezultat operacije za svi su mogući x logičke vrijednosti izvornih izjava. Broj opcija koje odražavaju rezultat primjene operacija ovisit će o broju iskaza u logičkom izrazu. Ako je broj iskaza u logičkom izrazu N, tada će tablica istinitosti sadržavati 2 N redaka, jer postoji 2 N različitih kombinacija mogućih vrijednosti argumenata.

Operacija NOT - logička negacija (inverzija)

Logička operacija se NE primjenjuje na jedan argument, koji može biti jednostavan ili složen logički izraz. Rezultat operacije NIJE sljedeći:

• ako je izvorni izraz istinit, tada će rezultat njegove negacije biti lažan;
• ako je izvorni izraz lažan, tada će rezultat njegove negacije biti istinit.

Sljedeće konvencije NE prihvaćaju se za operaciju negacije:
ne A, Ā, ne A, ¬A, !A
Rezultat operacije negacije NIJE određen sljedećom tablicom istine:

A	ne A
0	1
1	0

Rezultat operacije negacije je istinit kada je izvorni iskaz netočan, i obrnuto.

ILI operacija - logičko zbrajanje (disjunkcija, unija)

Logička operacija ILI obavlja funkciju kombiniranja dviju izjava, koje mogu biti jednostavni ili složeni logički izrazi. Iskazi koji su polazne točke za logičku operaciju nazivaju se argumentima. Rezultat operacije ILI je izraz koji će biti istinit ako i samo ako je barem jedan od originalnih izraza istinit.
Korištene oznake: A ili B, A V B, A ili B, A||B.
Rezultat operacije ILI određen je sljedećom tablicom istine:
Rezultat operacije ILI je istinit kada je A istinit, ili B je istinit, ili su i A i B istiniti, i lažan kada su argumenti A i B netočni.

Operacija I - logičko množenje (konjunkcija)

Logička operacija AND obavlja funkciju presjeka dvaju iskaza (argumenata), koji mogu biti jednostavni ili složeni logički izrazi. Rezultat operacije AND je izraz koji će biti istinit ako i samo ako su oba originalna izraza istinita.
Korištene oznake: A i B, A Λ B, A & B, A i B.
Rezultat operacije AND određen je sljedećom tablicom istine:

A	B	A i B
0	0	0
0	1	0
1	0	0
1	1	1

Rezultat operacije AND je istinit ako i samo ako su iskazi A i B istiniti, a lažni u svim ostalim slučajevima.

Operacija “IF-THEN” - logična posljedica (implikacija)

Ova operacija povezuje dva jednostavna logička izraza od kojih je prvi uvjet, a drugi posljedica tog uvjeta.
Korištene oznake:
ako A, onda B; A povlači za sobom B; ako A onda B; A→B.
Tablica istinitosti:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Rezultat operacije implikacije je lažan samo ako je premisa A istinita i zaključak B (posljedica) je lažan.

Operacija “A ako i samo ako B” (ekvivalencija, ekvivalencija)

Korištena oznaka: A ↔ B, A ~ B.
Tablica istinitosti:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operacija "Adicija modulo 2" (XOR, isključiva ili stroga disjunkcija)

Korištena oznaka: A XOR B, A ⊕ B.
Tablica istinitosti:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Rezultat operacije ekvivalencije je istinit samo ako su A i B istodobno istiniti ili lažni.

Prioritet logičkih operacija

• Radnje u zagradama
• Inverzija
• veznik (&)
• Disjunkcija (V), Isključivo ILI (XOR), zbroj modulo 2
• Implikacija (→)
• Ekvivalencija (↔)

Savršeni disjunktivni normalni oblik

Savršeni disjunktivni normalni oblik formule(SDNF) je ekvivalentna formula, koja je disjunkcija elementarnih konjunkcija i ima sljedeća svojstva:

1. Svaki logički član formule sadrži sve varijable uključene u funkciju F(x 1,x 2,...x n).
2. Svi logički pojmovi formule su različiti.
3. Niti jedan logički pojam ne sadrži varijablu i njezinu negaciju.
4. Nijedan logički izraz u formuli ne sadrži istu varijablu dva puta.

SDNF se može dobiti pomoću tablica istinitosti ili pomoću ekvivalentnih transformacija.
Za svaku funkciju, SDNF i SCNF su jedinstveno definirani do permutacije.

Perfektni konjunktivni normalni oblik

Savršeni konjunktivni normalni oblik formule (SCNF) Ovo je njemu ekvivalentna formula, koja je konjunkcija elementarnih disjunkcija i zadovoljava svojstva:

1. Sve elementarne disjunkcije sadrže sve varijable uključene u funkciju F(x 1 ,x 2 ,...x n).
2. Sve elementarne disjunkcije su različite.
3. Svaka elementarna disjunkcija jednom sadrži varijablu.
4. Niti jedna elementarna disjunkcija ne sadrži varijablu i njezinu negaciju.

Ovaj materijal sadrži prezentaciju koja predstavlja metode za rješavanje logičkih jednadžbi i sustava logičkih jednadžbi u zadatku B15 (br. 23, 2015.) Jedinstvenog državnog ispita iz informatike. Poznato je da je ovaj zadatak jedan od najtežih zadataka Jedinstvenog državnog ispita. Prezentacija može biti korisna pri podučavanju lekcija na temu "Logika" u specijaliziranim razredima, kao i prilikom pripreme za Jedinstveni državni ispit.

Preuzimanje datoteka:

Pregled:

Kako biste koristili preglede prezentacije, stvorite Google račun i prijavite se na njega: https://accounts.google.com

Naslovi slajdova:

Rješenje zadatka B15 (sustavi logičkih jednadžbi) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18. studenog 2013., Saratov

Zadatak B15 jedan je od najtežih na Jedinstvenom državnom ispitu iz informatike!!! Provjeravaju se sljedeće vještine: pretvaranje izraza koji sadrže logičke varijable; opisati prirodnim jezikom skup vrijednosti logičkih varijabli za koje je zadani skup logičkih varijabli istinit; izbrojati broj binarnih skupova koji zadovoljavaju zadane uvjete. Najteže je jer... ne postoje formalna pravila o tome kako to učiniti, potrebno je nagađanje.

Ono bez čega ne možete!

Ono bez čega ne možete!

Simboli konjunkcija: A /\ B , A  B , AB , A &B, A i B disjunkcija: A \ / B , A + B , A | B , A ili B negacija:  A , A, ne A ekvivalentnost: A  B, A  B, A  B isključivo “ili”: A  B , A xor B

Metoda zamjene varijabli Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, ..., x9, x10 postoji koji zadovoljavaju sve dolje navedene uvjete: ((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 Odgovor ne treba navesti sve različite skupove x1, x2, …, x9, x10 za koje ovaj sustav jednakosti vrijedi. Kao odgovor morate navesti broj takvih skupova (demo verzija 2012.)

Rješenje Korak 1. Pojednostavite mijenjanjem varijabli t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Nakon pojednostavljenja: (t1 \/ t2) /\ (¬t1 \/ ¬ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Razmotrimo jednu od jednadžbi: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Očito, to je =1 samo ako je jedna od varijabli 0, a druga 1 . Upotrijebimo formulu da izrazimo operaciju XOR kroz konjunkciju i disjunkciju: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Korak 2. Analiza sustava ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 T .Do. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), tada svaka vrijednost tk odgovara dvama parovima vrijednosti x2k-1 i x2k, na primjer: tk =0 odgovara dvama parovima - (0 ,1) i (1, 0) , a tk =1 – parovi (0,0) i (1,1).

Korak 3. Brojanje broja rješenja. Svaki t ima 2 rješenja, broj ts je 5. Dakle. za varijable t postoje 2 5 = 32 rješenja. Ali svakom t odgovara par rješenja x, tj. izvorni sustav ima 2*32 = 64 rješenja. Odgovor: 64

Metoda eliminacije dijela rješenja Koliko postoji različitih skupova vrijednosti logičkih varijabli x1, x2, ..., x5, y1,y2,..., y5 koji zadovoljavaju sve dolje navedene uvjete: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. Odgovor ne treba navesti sve različite skupove x1, x2, ..., x5, y 1 , y2, ... , y5 za koje vrijedi ovaj sustav jednakosti. U odgovoru mora biti naznačen broj takvih skupova.

Riješenje. Korak 1. Sekvencijalno rješavanje jednadžbi 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 Prva jednadžba je konjunkcija nekoliko operacija implikacije, jednaka 1, tj. svaka od implikacija je istinita. Implikacija je lažna samo u jednom slučaju, kada je 1  0, u svim ostalim slučajevima (0  0, 0  1, 1  1) operacija vraća 1. Zapišimo to u obliku tablice:

Korak 1. Sekvencijalno rješavanje jednadžbi T.o. Dobiveno je 6 skupova rješenja za x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Slično razmišljajući, dolazimo do zaključka da za y1, y2, y3, y4, y5 postoji isti skup rješenja. Jer ove jednadžbe su nezavisne, tj. nemaju zajedničke varijable, tada će rješenje ovog sustava jednadžbi (bez uzimanja u obzir treće jednadžbe) biti 6 * 6 = 36 parova "X" i "Y". Razmotrimo treću jednadžbu: y5→ x5 =1 Rješenje su parovi: 0 0 0 1 1 1 Par nije rješenje: 1 0

Usporedimo dobivena rješenja, gdje y5 =1, x5=0 nije pogodno. takvih parova je 5. Broj rješenja sustava: 36-5= 31. Odgovor: Trebala je 31 kombinatorika!!!

Metoda dinamičkog programiranja Koliko različitih rješenja ima logička jednadžba x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, gdje su x 1, x 2, …, x 6 logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti varijabli za koje ova jednakost vrijedi. Kao odgovor morate navesti količine takvih setova.

Rješenje Korak 1. Analiza uvjeta S lijeve strane u jednadžbi redom su ispisane operacije implikacije, prioritet je isti. Prepišimo: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Svaka sljedeća varijabla ne ovisi o prethodnoj, već o rezultatu prethodne implikacije!

Korak 2. Otkrivanje uzorka Razmotrimo prvu implikaciju, X 1 → X 2. Tablica istinitosti: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Od jedne 0 dobili smo 2 jedinice, a od 1 dobili smo jednu 0 i jednu 1. Postoji samo jedna 0 i tri 1, to je rezultat prve operacije.

Korak 2. Otkrivanje uzorka Povezivanjem x 3 s rezultatom prve operacije dobivamo: 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 dvije 0 – dvije 1, od svake 1 (ima ih 3) jedna 0 i jedna 1 (3+3)

Korak 3. Derivacija formule T.o. možete stvoriti formule za izračunavanje broja nula N i i broja jedinica E i za jednadžbu s i varijabli: ,

Korak 4. Ispunjavanje tablice Ispunimo tablicu slijeva nadesno za i = 6, računajući broj nula i jedinica pomoću gornjih formula; tablica pokazuje kako je sljedeći stupac izgrađen od prethodnog: broj varijabli 1 2 3 4 5 6 Broj nula N i 1 1 3 5 11 21 Broj jedinica E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Odgovor: 43

Metoda koja koristi pojednostavljenja logičkih izraza Koliko različitih rješenja ima jednadžba ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 gdje su J, K, L, M, N logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti J, K, L, M i N za koje ova jednakost vrijedi. Kao odgovor morate navesti broj takvih skupova.

Rješenje Uočimo da je J → K = ¬ J  K Uvedimo promjenu varijabli: J → K=A, M  N  L =B Prepišimo jednadžbu uzimajući u obzir promjenu: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Očito, A  B za iste vrijednosti A i B 6. Razmotrimo posljednju implikaciju M → J =1 Ovo je moguće ako je: M= J=0 M=0, J=1 M=J=1

Rješenje Jer A  B, tada kada je M=J=0 dobivamo 1 + K=0. Nema rješenja. Kada je M=0, J=1 dobivamo 0 + K=0, K=0, a N i L su bilo koji, 4 rješenja: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Rješenje 10. Kada je M=J=1 dobivamo 0+K=1 *N * L, ili K=N*L, 4 rješenja: 11. Ukupno ima 4+4=8 rješenja Odgovor: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Izvori informacija: O.B. Bogomolova, D.Yu. Usenkov. B15: novi zadaci i nova rješenja // Informatika, br. 6, 2012., str. 35 – 39. K.Yu. Polyakov. Logičke jednadžbe // Informatika, broj 14, 2011., str. 30-35 (prikaz, stručni). http://ege-go.ru/zadania/grb/b15/, [Elektronički izvor]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronički izvor].