Metoda za rješavanje sistema logičkih jednačina. Sistemi logičkih jednačina u Jedinstvenom državnom ispitnom zadatku iz informatike Rješavanje logičkih jednačina u informatici online

Rješenje jednadžbe 1. Prijeđite na prefiksni oblik pisanja jednačine, zamjenjujući simbole negacija sa ¬ 2. Konstruirajte naslov tablice istinitosti posebnog tipa 3. Popunite redove 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. Koristeći tablicu istinitosti, odredite tip funkcije X, ako je potrebno, koristeći metode konstruiranja SCNF-a i SDNF, o čemu će biti riječi u nastavku.

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

Tabela istinitosti X=F(A, B) ABX Odgovara negaciji implikacije B u A ODGOVOR:

Kombinovana kola logičkih uređaja Osnovni elementi (GOST): 1 A B Disjunkcija A B Ekvivalentnost & A B Konjunkcija M2 A B XOR

Kombinovana kola logičkih uređaja Osnovni elementi (GOST): 1 A B Implikacija & A B Schaeffer element & A B Koimplikacija 1 A B Webb element

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

Rješavanje kola 1 Opcija - pretvaranje kola u složeni logički izraz i zatim njegovo pojednostavljivanje prema zakonima logike. Opcija 2 – izrada tabele istinitosti i zatim, ako je potrebno, konstrukcija kroz SKNF ili SDNF (vidi dole). Razmotrimo drugu opciju, jer je jednostavnija i razumljivija.

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

Tabela istinitosti F(A, B) ABX Odgovara negaciji implikacije B u A ODGOVOR:

SDNF i SKNF (definicije) Elementarna konjunkcija je konjunkcija više varijabli, uzetih sa ili bez negacije, a među varijablama mogu biti i identične. Elementarna disjunkcija se naziva disjunkcija više varijabli, uzetih sa ili bez negacije, i među varijablama mogu biti identične Svaka disjunkcija elementarnih konjunkcija Nazovimo je disjunktivnim normalnim oblikom (DNF) Nazovimo bilo koju konjunkciju elementarnih disjunkcija konjunktivnim normalnim oblikom (DNF)

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

Algoritam za dobijanje SDNF iz tabele istinitosti 1. Označite redove tabele istinitosti u poslednjoj koloni kojih ima 1. 2. Za svaki označeni red zapišite konjunkciju svih varijabli na sledeći način: ako je vrednost varijable u dati red je 1, onda uključite ovu varijablu u konjunkciju, ako je jednaka 0, onda njenu negaciju. 3. Povežite sve nastale veznike u disjunkciju. Algoritam za dobijanje SCNF-a iz tabele istinitosti 1. Označite redove tabele istinitosti u poslednjoj koloni kojih ima 0. 2. Za svaki označeni red napišite disjunkciju svih varijabli na sledeći način: ako je vrednost varijable u dati red je 0, onda uključite ovu varijablu u konjunkciju, ako je jednak 1, onda njenu negaciju. 3. Povežite sve nastale disjunkcije u konjunkciju.

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

Veličina: px

Počnite prikazivati ​​sa stranice:

Transkript

1 Rješavanje logičkih jednadžbi i sistema logičkih jednačina Neka je F(x, x2, xn) logička funkcija od n varijabli. Logička jednačina ima oblik: F(x, x2, xn) = C, gdje konstanta C ima vrijednost ili. Logička jednačina može imati do 2 n različitih rješenja. Ako je C jednako, onda su rješenja svi oni skupovi varijabli iz tablice istinitosti na kojima funkcija F uzima vrijednost true (). Preostali skupovi su rješenja jednadžbe sa C jednakim nuli. Uvijek možete uzeti u obzir samo jednačine oblika: F(x, x2, xn) = Zaista, neka je data jednačina: F(x, x2, xn) = U ovom slučaju možete prijeći na ekvivalentnu jednačinu: F( x, x2, xn) = Razmotrimo sistem od k logičkih jednačina: F(x, x2, xn) = F2(x, x2, xn) = ( Fk(x, x2, xn) = Rješenje sistema je skup varijabli na kojima su zadovoljene sve jednadžbe sistema. U logičkim terminima funkcije za dobivanje rješenja sistema logičkih jednačina, treba pronaći skup na kojem je tačna logička funkcija F, koja predstavlja konjunkciju originalnih funkcija F: F = F F2 Fk Ako je broj varijabli mali, na primjer, manji od 5, onda nije teško konstruirati tabelu istinitosti za funkciju F koja omogućava da se kaže koliko rješenja ima sistem i koji su skupovi koji daju rješenja.U nekim USE problemima nalaženja rješenja za sistem logičkih jednačina, broj varijabli dostiže vrijednost.Tada konstruiranje tablice istinitosti postaje praktično nerješiv zadatak.Za rješavanje problema potreban je drugačiji pristup. Za proizvoljan sistem jednačina ne postoji opšta metoda osim nabrajanja koja omogućava rešavanje takvih problema. U zadacima predloženim na ispitu rješenje se obično zasniva na uzimanju u obzir specifičnosti sistema jednačina. Međutim, ponavljam da osim isprobavanja svih opcija za skup varijabli, ne postoji opći način rješavanja problema. Rješenje mora biti izgrađeno na osnovu predstavljenog sistema. Često je korisno izvršiti preliminarno pojednostavljenje sistema jednačina koristeći poznate zakone logike. Još jedna korisna tehnika za rješavanje ovog problema je sljedeća. Ne zanimaju nas svi skupovi, već samo oni na kojima funkcija Φ ima vrijednost. Umjesto da gradimo kompletnu tabelu istine, izgradićemo njen analog - binarno stablo odlučivanja. Svaka grana ovog drveta odgovara

2 na jedno rješenje i specificira skup na kojem funkcija F ima vrijednost. Broj grana u stablu odlučivanja poklapa se sa brojem rješenja sistema jednačina. Objasniću šta je binarno stablo odlučivanja i kako se gradi koristeći primere nekoliko problema. Problem Koliko različitih skupova vrijednosti logičkih varijabli x, x2, x3, x4, x5, y, y2, y3, y4, y5 postoji koji zadovoljavaju sistem od dvije jednačine? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ( (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Odgovor: Sistem ima 36 različitih rješenja.Sistem jednadžbi uključuje dvije jednačine.Nađimo broj rješenja za prvu jednačinu u zavisnosti od 5 varijabli x,x2,x5.Prva jednačina se može posmatrati kao sistem od 5 jednačina. je prikazano, sistem jednadžbi zapravo predstavlja konjunkciju logičke funkcije.Tačno je i suprotna tvrdnja - konjunkcija uslova se može posmatrati kao sistem jednačina.Napravimo stablo odlučivanja za implikaciju (x x2) - prvi član konjunkcije koja se može smatrati prvom jednačinom Evo kako izgleda grafički prikaz ovog stabla: X X2 Stablo se sastoji od dva nivoa prema broju varijabli u jednačini.Prvi nivo opisuje prvu varijablu X. Dvije grane ovog nivoa odražavaju moguće vrijednosti ove varijable i. Na drugom nivou, grane stabla odražavaju samo one moguće vrijednosti varijable X2 za koje je jednačina istinita. Pošto jednačina 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 sa vrijednostima X2 jednakim i. Konstruirano stablo specificira tri rješenja na kojima implikacija X X2 poprima vrijednost. Na svakoj grani ispisuje se odgovarajući skup varijabilnih vrijednosti, što daje rješenje jednadžbe. Ovi skupovi su: ((,), (,), (,)) Nastavimo graditi stablo odlučivanja, dodajući sljedeću jednačinu, sljedeću implikaciju X2 X3. Specifičnost našeg sistema jednačina je da svaka nova jednačina sistema koristi jednu varijablu iz prethodne jednačine, dodajući jednu novu varijablu. Pošto varijabla X2 već ima vrijednosti u stablu, onda će na svim granama gdje varijabla X2 ima vrijednost, varijabla X3 također imati vrijednost. Za takve grane izgradnja stabala se nastavlja na sljedeći nivo, ali se nove grane ne pojavljuju. Jedina grana u kojoj varijabla X2 ima vrijednost će se granati na dvije grane gdje će varijabla X3 primati vrijednosti i. Dakle, svaki dodatak nove jednadžbe, uzimajući u obzir njene specifičnosti, dodaje jedno rješenje.

3 Originalna prva jednačina: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ima 6 rješenja. Evo kako izgleda kompletno stablo rješenja ove jednačine: X X2 X3 X4 X5 Druga jednačina našeg sistema je slična prvoj: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Jedina razlika je u tome što jednačina koristi varijable Y. Ova jednačina također ima 6 rješenja. Budući da se svako rješenje za varijable Xi može kombinovati sa svakim rješenjem za varijable Yj, ukupan broj rješenja je 36. Imajte na umu da konstruirano stablo odlučivanja daje ne samo broj rješenja (prema 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 dolje navedene uslove? (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 se dodaje druga jednačina koja povezuje varijable X i Y. Iz jednačine X Y slijedi da kada X ima vrijednost (jedno takvo rješenje postoji), onda Y ima vrijednost. postoji jedan set, na kojem

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

5 Zadatak 4 Koliko rješenja ima sljedeći sistem jednačina? 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)) = Pređimo sa 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 imati oblik: (Y Y2 ) (Y Y2) = Jednačina se može pojednostaviti pisanjem u obliku: (Y Y2) = Prelazeći na tradicionalni oblik, sistem nakon pojednostavljenja zapisujemo u obliku: (Y Y2) = (Y2 Y3) = ( (Y3 Y4) = (Y4 Y5) = Stablo odlučivanja za ovaj sistem je jednostavno i sastoji se od dvije grane sa naizmjeničnim vrijednostima varijabli: Y Y2 Y3 Y4 Y5 Vraćajući se na originalne varijable X, primjećujemo da svaka vrijednost varijable Y odgovara 2 vrijednosti varijabli X, stoga svako rješenje u varijablama Y generiše 2 5 rješenja u varijablama X. Dvije grane proizvode 2 * 2 5 rješenja, tako da je ukupan broj rješenja 64. Kao što vidite, svaki problem rješavanja sistema jednačina zahtijeva drugačiji pristup. Uobičajena tehnika je izvođenje ekvivalentnih transformacija kako bi se jednačine pojednostavile.

6 Uobičajena tehnika je izgradnja stabala odluka. Korišteni pristup djelomično podsjeća na konstruiranje tablice istinitosti s posebnošću da se ne konstruiraju svi skupovi mogućih vrijednosti varijabli, već samo oni na kojima funkcija uzima vrijednost (true). Često u predloženim problemima nije potrebno graditi kompletno stablo odlučivanja, jer je već u početnoj fazi moguće uspostaviti obrazac pojavljivanja novih grana na svakom sljedećem nivou, kao što je učinjeno, na primjer, u problemu .

Putilov Viktor Vasiljevič MAOU Srednja škola 46 Sistemi logičkih jednačina. Sadržaj Napomena o zamjeni varijabli.... Problemi koji sadrže implikaciju ili njen ekvivalentni zapis....2 Prisustvo dodatnog uvjeta...6

Rješavanje sistema logičkih jednačina. Koliko rješenja ima jednačina A BB C C D = 0 Broj skupova varijabli je =. Možete kreirati tabelu istinitosti i provjeriti koliko skupova odgovara

Konstrukcija i analiza tablica istinitosti logičkih izraza. Jedinstveni državni ispit 2015. 2 (osnovni nivo, vrijeme 3 minuta) Primjer P-13. Svaki logički izraz A i B zavisi od istog skupa od 5 varijabli.

N B Rogov Kako naučiti rješavati zadatak B15 Jedinstvenog državnog ispita iz informatike (sistemi logičkih jednačina) za 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, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnoj" matematičkoj logici (,), su nezgodne i nisu intuitivno jasne

Matematika i matematičko modeliranje UDK 004.023 Semenov Sergej Maksimovič Vladivostok Državni univerzitet ekonomije i usluga Rusija. Vladivostok O jednom načinu rješavanja logičkih sistema

B4 (visoki nivo, vrijeme 1 min) Tema: Pretvaranje logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnoj" matematičkoj logici (,),

B0 (visoki nivo, vrijeme 0 min) Tema: Pretvaranje logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnoj" matematičkoj logici (,),

19022017 Bitne operacije u problemima KIM Jedinstvene državne ispite iz računarstva II dio KYu Polyakov, doktor tehničkih nauka, nastavnik informatike GBOU Srednja škola 163, Sankt Peterburg Ovaj članak po prvi put razmatra probleme sljedećeg tipa

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

Logika je nauka koja proučava metode utvrđivanja istinitosti ili netačnosti nekih iskaza na osnovu istinitosti ili netačnosti drugih iskaza. Izjava (presuda) je neka rečenica koja

B visoki nivo, vrijeme 0 min) K. Polyakov, 009-0 Tema: Transformacija logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

Problem 1: Dat je fragment tablice istinitosti izraza F: Koji izraz može biti F? 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 Bulovih funkcija od n varijabli nalazi se po formuli: P2 (n) = 2 2n Logičke funkcije dvije varijable 6 Najčešće se koriste sljedeće funkcije: f (x,

Rješenja zadataka 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, izvršiti operaciju eliminacije fiktivnih varijabli. Rješenje.

051216 Bitne operacije u problemima KIM Jedinstvenog državnog ispita iz informatike II deo KYu Polyakov, doktor tehničkih nauka, nastavnik informatike GBOU Srednja škola 163, Sankt Peterburg U ovom članku se po prvi put razmatraju problemi sledećeg tipa

Mironchik E.A., nastavnik informatike, Novokuznjeck Rešavanje zadatka Jedinstvenog državnog ispita-18 sa bitskim operacijama Opisani metod pokazuje metodu rešavanja zasnovanu na identičnim prelazima, tj. = "radi"

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

Dio 1 1. Navedite 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: Koristeći de Morganovu formulu (B \/ C) = B /\ C i

Glinka N.V. Korištena notacija Negacija Množenje (konjukcija) Sabiranje (disjunkcija) Implikacija Ekvivalencija Primjeri zadataka prije školske 2010. godine Koliko različitih rješenja daje jednačina ((K

Bitne operacije u KIM problemima u informatici Vrste problema Ovaj webinar govori o problemima sljedećeg tipa (ovi problemi su se prvi put pojavili u KIM-u na Jedinstvenom državnom ispitu 2015.): Uvesti izraz M & K koji označava

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

A10 (osnovni nivo, vrijeme 1 min) Tema: Transformacija logičkih izraza. De Morganove formule. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

Gurskaja K.A., Ivin V.V., Semenov S.M. Rješavanje zadataka 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 zadataka matematičke logike na Jedinstvenom državnom ispitu”

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

PREDAVANJE 5 LOGIČKE OPERACIJE U INFORMACIJI 1. Matematička logika i informatika 2. Logički izrazi i logičke operacije 3. Konstrukcija tablica istinitosti i logičkih funkcija 4. Zakoni logike i pravila

B5 visoki nivo, vrijeme 0 min) Tema: Transformacija logičkih izraza. O notacijama Nažalost, notacije 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. vijeku razvio engleski matematičar George Boole. Algebarske metode se koriste u algebri logike

2 (osnovni nivo, vrijeme min) Tema: Konstrukcija i analiza tablica istinitosti logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

A8 (osnovni nivo, vrijeme 1 min) Tema: Transformacija logičkih izraza. De Morganove formule. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

B15 Navedite vrijednosti varijabli K, L, M, N za koje je logički izraz (K M) (L K) N laž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 istinitosti Osnove logike. Logičke operacije i tablice istinitosti Ova stranica će raspravljati o 6 logičkih operacija: konjunkcija, disjunkcija, inverzija,

Identiteti Bulove algebre Glavni zadatak matematičke logike je da odredi značenje složenog iskaza na osnovu neistinitosti ili istinitosti jednostavnih iskaza. Logičke operacije u propozicionoj algebri

Opštinska budžetska obrazovna ustanova grada Abakana “Srednja škola 11” Metodološka izrada na temu Rješenje zadataka tipa 18 Jedinstveni državni ispit iz računarstva Atyushkina Marina Valerievna,

Tema 4. Logičke osnove RAČUNARA 1. OSNOVNE INFORMACIJE IZ LOGIČKE ALGEBRE... 1 2. ZAKONI LOGIČKE ALGEBRE... 4 3. KONCEPT MINIMIZACIJE LOGIČKIH FUNKCIJA... 6 4. TEHNIČKO FUNKCIONALNO FUNKCIONALNO TUMAČENJE...

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

Iracionalne nejednačine Nejednačine u kojima je varijabla sadržana pod predznakom korijena nazivaju se iracionalne.Glavna metoda za rješavanje iracionalnih nejednačina je metoda redukcije izvorne nejednakosti.

26 transformacija, izgradite ispravan lanac zaključivanja i napravite aritmetičku grešku u posljednjoj radnji. Imajte na umu da pri rješavanju ovog zadatka dolazi do broja samo aritmetičkih operacija

Regionalno takmičenje obrazovnih, istraživačkih i dizajnerskih radova učenika „Primenjena pitanja matematike“ Algebra Algebra logike Alena Sergejevna Semuševa, Opštinska obrazovna ustanova „Licej“ Perm, kl. Borkova Olga Vladimirovna,

K. Polyakov, 009-0 B5 visoki nivo, vrijeme 0 min) Tema: Transformacija logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

PRAKTIČNA LEKCIJA 1 Linearne jednadžbe prvog reda, Bernoullijeva jednačina Jednačina u totalnim diferencijalima Linearna diferencijalna jednadžba prvog reda je jednačina + p(= q(Ako

Moskovski državni tehnički univerzitet nazvan po N.E. Bauman Fakultet fundamentalnih nauka Katedra za matematičko modeliranje A.N. CAPITAL DASHMANN

A9 (osnovni nivo, vrijeme 2 min) Tema: Konstrukcija tablica istinitosti logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

Mironchik E.A., MB NOU "Lyceum", Novokuznetsk Način prikaza Zadatak. Koliko rješenja ima sistem: Sve jednačine uključene u sistem su istog tipa, a svaka jednačina uključuje tri varijable. Znajući

Federalna agencija za obrazovanje Uralski državni ekonomski univerzitet Yu. B. Melnikov Bulove i logičke funkcije Odjeljak elektronskog udžbenika koji prati predavanje e-mail: [email protected],

E.V.Prosolupov 42. Bulova algebra. Funkcije logičke algebre 1 Bulove funkcije Razmotrit ćemo Booleove funkcije - funkcije čiji argumenti i vrijednosti uzimaju vrijednosti istinite i netočne. Istina i laži će biti

Federalna agencija za obrazovanje Ural State Economic University Yu. B. Melnikov Bulove i logičke funkcije Odjeljak elektronskog udžbenika koji prati predavanje Ed. 3., rev.

MINISTARSTVO OBRAZOVANJA I NAUKE RF Federalna državna autonomna obrazovna ustanova visokog stručnog obrazovanja "NACIONALNI ISTRAŽIVAČKI TOMSKI POLITEHNIČKI UNIVERZITET"

Praktični rad 1 Logičke operacije. Ekvivalencija formula Cilj rada: Naučite da pravite tabele istinitosti logičkih iskaza i transformišete formule koristeći osnovne ekvivalencije Sadržaj

Kažu da je Aristotel, kada je smislio logiku, proslavio gozbu i naredio da se zakolje 40 ovaca. Od tada ovce ne vole logiku. Osnovni pojmovi iz logičke algebre, 10. razred, 2017-2018 šk.

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

Predavanje 2. Konjunktivni normalni oblici. Implicenta, jednostavna implicitna funkcija. Redukovana CNF funkcija logičke algebre. Metode za konstruisanje skraćenog CNF-a. Predavač Svetlana Nikolaevna Selezneva [email protected]

LOGIKA IZJAVA Navoda Izjava je izjavna rečenica čiji se sadržaj može ocijeniti istinitim ili netačnim. Razlikovati: apsolutno istinite izjave, apsolutno

Podijeli P.G. Harkovski nacionalni univerzitet mehanike i matematike Fakultet diskretne matematike. Bilješke sa predavanja. Sadržaj 1. Propoziciona algebra i logika. 1.1 Izjave i logičke operacije...

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

Matematička logika i teorija algoritama Pervuhin Mihail Aleksandrovič Logička posledica u AB Kažu da je formula ψ x 1, x n AB logička posledica formula φ 1 (x 1, x n), φ m x 1,

Moskovski državni tehnički univerzitet nazvan po N.E. Bauman Fakultet fundamentalnih nauka Katedra za matematičko modeliranje A.N. KASIATOVIKOV

PREDAVANJE 21 POISSONOVE ZAGRADE. JACOBI-POISSONOVA TEOREMA. KANONSKE TRANSFORMACIJE 1. Poissonove zagrade U prošlom predavanju uveden je koncept Lagranžove zagrade. Ovaj izraz je sastavljen od parcijalnih izvedenica

KORISTITE 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

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

Laboratorijski rad BERLEKAMP-MESSIE ALGORITAM ZA PRONALAŽIVANJE KOEFICIJENATA POVRATNIH SREDSTAVA PSEUDO-SLUČAJNOG GENERATORA SEKVENCE Razmotrimo kako možemo vratiti polinom koji definiše povratnu vezu

K.Yu. Polyakov, M.A. Roitberg Sistemi logičkih jednačina u Jedinstvenim ispitnim zadacima iz računarstva K.Yu. Polyakov, M.A. Roitberg, 0 http://kpolkov.sp.ru K.Yu. Polyakov, M.A. Roitberg, 0 http://kpolkov.sp.ru Proizvodnja

Bitne operacije u problemima KIM Jedinstvenog državnog ispita iz računarstva K.Yu. Polyakov, doktor tehničkih nauka, nastavnik informatike GBOU srednja škola 163, Sankt Peterburg U ovom članku se govori o sljedećem tipu problema (ovi problemi su se prvi put pojavili

Ministarstvo obrazovanja Ruske Federacije Don državni tehnički univerzitet Katedra za višu matematiku Problemi u diskretnoj matematici Rostov na Donu 2001 UDK 517 Sastavio: Baranov

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

A3 (osnovni nivo, vrijeme 2 min) Tema: Konstrukcija tablica istinitosti logičkih izraza. O notacijama Nažalost, notacije za logičke operacije I, ILI i NE, prihvaćene u "ozbiljnim" matematičkim

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

Nejednačine C C Priprema za Jedinstveni državni ispit 0 (materijal za predavanje za nastavnike 8040) Prokofjev AA aaprokof@yanderu Osnovne metode rješavanja: Zadaci C Rješavanje nejednačina na intervalima Pojednostavljenje nejednakosti i redukcija

Dodatak 1 GRUPE, PRSTENOVI, POLJA Za kriptografiju, algebra je jedno od glavnih oruđa u teorijskom istraživanju i praktičnoj konstrukciji kriptografskih transformacija.

Opštinska budžetska obrazovna ustanova

"Srednja škola br. 18"

gradski okrug grada Salavat Republike Baškortostan

Sistemi logičkih jednačina

u Jedinstveni državni ispitni problemi iz računarstva

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

Sekcija kursa	Prosječan postotak izvršenja po grupama zadataka
Kodiranje informacija i mjerenje njihove količine
Informacijsko modeliranje
Sistemi brojeva
Osnove logičke algebre
Algoritamizacija i programiranje
Osnove informacionih i komunikacionih tehnologija

Na osnovu KIM specifikacije 2018, ovaj blok uključuje četiri zadatka različitih nivoa težine.

№ zadataka	Provjerljivo elementi sadržaja	Nivo težine zadatka
	Sposobnost konstruisanja tabela istinitosti i logičkih kola
	Mogućnost traženja informacija na Internetu
	Poznavanje osnovnih pojmova i zakona matematička logika
	Sposobnost konstruisanja i transformacije logičkih izraza

Zadatak 23 je visokog stepena težine, stoga ima najmanji procenat ispunjenosti. Među pripremljenim maturantima (81-100 bodova) 49,8% je završilo zadatak, umjereno pripremljenim maturantima (61-80 bodova) 13,7%, a preostala grupa studenata ovaj zadatak nije završila.

Uspješnost rješavanja sistema logičkih jednačina zavisi od poznavanja zakona logike i od precizne primjene metoda za rješavanje sistema.

Razmotrimo rješavanje sistema logičkih jednačina metodom mapiranja.

(23.154 Polyakov K.Yu.) Koliko različitih rješenja ima sistem jednačina?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (g1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (g2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

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

Rješenje. Sve jednačine uključene u sistem su istog tipa, a svaka jednačina uključuje četiri varijable. Znajući x1 i y1, možemo pronaći sve moguće vrijednosti x2 i y2 koje zadovoljavaju prvu jednačinu. Rezonirajući na sličan način, iz poznatih x2 i y2 možemo pronaći x3, y3 koji zadovoljava drugu jednačinu. 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 jednačine. To se može učiniti na dva načina: konstruirati tabelu istinitosti, kroz rasuđivanje i primjenu zakona logike.

Tabela istine:

				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 istinitosti je radno intenzivna i vremenski neefikasna, pa koristimo drugu metodu - logičko rasuđivanje. Proizvod je jednak 1 ako i samo ako je svaki faktor jednak 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Pogledajmo prvu jednačinu. 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  y2 ) može biti bilo koji (00), (01), (10), (11), a kada je (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 jednačina netačne, odnosno x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

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

2) (23.160 Polyakov K.Yu.) Koliko različitih rješenja ima sistem logičkih jednačina?

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

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

...

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

x 7  y 7 = 1

Rješenje. 1) Jednačine su istog tipa, tako da ćemo pomoću rasuđivanja pronaći sve moguće parove (x1,y1), (x2,y2) prve jednačine.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Rješenje druge jednačine su parovi (00), (01), (11).

Nađimo rješenja prve jednačine. Ako je x1=0, onda x2, y2 - bilo koji, ako je x1=1, tada x2, y2 uzima vrijednost (11).

Napravimo veze između parova (x1, y1) i (x2, y2).

(x1 , y1 )	(x2 , y2 )

Napravimo tabelu za izračunavanje broja parova u svakoj fazi.

							0

Uzimajući u obzir rješenja posljednje jednačine x 7  y 7 = 1, isključimo par (10). Pronađite ukupan broj rješenja 1+7+0+34=42

3)(23.180) Koliko različitih rješenja ima sistem logičkih jednačina?

(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

Rješenje. 1) Jednačine su istog tipa, tako da ćemo pomoću rasuđivanja pronaći sve moguće parove (x1,x2), (x3,x4) prve jednačine.

(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).

Napravimo veze između parova (x1,x2), (x3,x4)

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

Instrukcije. Prilikom unosa sa tastature koristite sljedeće oznake: Na primjer, logički izraz abc+ab~c+a~bc se mora 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 specificirati 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.

Dizajn i analiza kompjuterskih logičkih kola vrši se pomoću posebne grane matematike - logičke algebre. U algebri logike mogu se razlikovati tri glavne logičke funkcije: “NE” (negacija), “AND” (konjunkcija), “ILI” (disjunkcija).
Za kreiranje bilo kojeg logičkog uređaja potrebno je utvrditi ovisnost svake od izlaznih varijabli o postojećim ulaznim varijablama; ova ovisnost se naziva funkcija prebacivanja ili funkcija logičke algebre.
Logička algebarska funkcija naziva se potpuno definirana ako su date svih 2n njenih vrijednosti, gdje je n broj izlaznih varijabli.
Ako nisu sve vrijednosti definirane, 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 kolo logičkog uređaja koristeći logičke elemente.


Slika 1 - dijagram logičkog uređaja

Definisane su sve operacije algebre logike tabele istine vrijednosti. Tabela istinitosti određuje rezultat operacije za svako je moguć x logičke vrijednosti originalnih 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, tabela istinitosti će sadržavati 2 N reda, budući da postoje 2 N različite kombinacije mogućih vrijednosti argumenata.

Operacija NE - 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 originalni izraz istinit, onda će rezultat njegove negacije biti lažan;
• ako je originalni izraz lažan, tada će rezultat njegove negacije biti istinit.

Sljedeće konvencije NISU prihvaćene za operaciju negacije:
ne A, Ā, ne A, ¬A, !A
Rezultat operacije negacije NIJE određen sljedećom tablicom istinitosti:

A	ne A
0	1
1	0

Rezultat operacije negacije je istinit kada je originalni iskaz lažan, i obrnuto.

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

Logička operacija ILI obavlja funkciju kombinovanja dva izraza, koji mogu biti ili jednostavan ili složen logički izraz. Izjave koje su početne tačke za logičku operaciju nazivaju se argumenti. Rezultat operacije OR 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 OR određen je sljedećom tablicom istinitosti:
Rezultat operacije ILI je istinit kada je A istinito, ili je B istinito, ili su oba A i B tačna, i lažna kada su argumenti A i B lažni.

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

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

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

Rezultat operacije AND je tačan ako i samo ako su izjave A i B tačne i netačne u svim ostalim slučajevima.

Operacija “AKO-ONDA” - logična posljedica (implikacija)

Ova operacija povezuje dva jednostavna logička izraza, od kojih je prvi uslov, a drugi posledica ovog uslova.
Korištene oznake:
ako je A, onda B; A podrazumijeva B; ako je A onda B; A→B.
Tabela istine:

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

Rezultat operacije implikacije je netačan samo ako je premisa A tačna, a zaključak B (posljedica) lažan.

Operacija "A ako i samo ako B" (ekvivalencija, ekvivalencija)

Korištena oznaka: A ↔ B, A ~ B.
Tabela istine:

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

Operacija “Addition modulo 2” (XOR, isključiva ili, stroga disjunkcija)

Korištena notacija: A XOR B, A ⊕ B.
Tabela istine:

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 istovremeno istiniti ili netačni.

Prioritet logičkih operacija

• Radnje u zagradama
• Inverzija
• Veznik (&)
• Disjunkcija (V), ekskluzivno OR (XOR), zbir po modulu 2
• implikacija (→)
• Ekvivalencija (↔)

Savršena disjunktivna normalna forma

Savršena disjunktivna normalna forma 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 termini formule su različiti.
3. Niti jedan logički termin ne sadrži varijablu i njenu negaciju.
4. Nijedan logički termin u formuli ne sadrži istu varijablu dvaput.

SDNF se može dobiti bilo korištenjem tablica istinitosti ili korištenjem ekvivalentnih transformacija.
Za svaku funkciju, SDNF i SCNF su jedinstveno definirani do permutacije.

Savršena konjunktivna normalna forma

Savršena konjunktivna normalna forma formule (SCNF) Ovo je formula ekvivalentna njoj, 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 sadrži varijablu jednom.
4. Nijedna elementarna disjunkcija ne sadrži varijablu i njenu negaciju.

Ovaj materijal sadrži prezentaciju koja predstavlja metode rješavanja logičkih jednačina i sistema logičkih jednačina u zadatku B15 (br. 23, 2015.) Jedinstvenog državnog ispita iz računarstva. Poznato je da je ovaj zadatak jedan od najtežih među zadacima Jedinstvenog državnog ispita. Prezentacija može biti korisna prilikom predavanja na temu „Logika“ u specijalizovanim časovima, kao i prilikom pripreme za Jedinstveni državni ispit.

Skinuti:

Pregled:

Da biste koristili preglede prezentacija, kreirajte Google račun i prijavite se na njega: https://accounts.google.com

Naslovi slajdova:

Rješenje zadatka B15 (sistemi logičkih jednačina) Vishnevskaya M.P., MAOU “Gimnazija br. 3” 18. novembra 2013., Saratov

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

Bez čega se ne može!

Bez čega se ne može!

Konjunkcija simbola: A /\ B , A  B , AB , A &B, A i B disjunkcija: A \ / B , A + B , A | B , A ili B negacija:  A , A, a ne A ekvivalencija: A  B, A  B, A  B isključivo “ili”: A  B, A xor B

Metoda zamjene varijable Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, ..., x9, x10 postoji koji zadovoljavaju sve dolje navedene uslove: ((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 U odgovoru nije potrebno navesti sve različite skupove x1, x2, …, x9, x10 za koje ovaj sistem jednakosti važi. Kao odgovor, morate navesti broj takvih setova (demo verzija 2012)

Rješenje Korak 1. Pojednostavite promjenom 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čigledno, to je =1 samo ako je jedna od varijabli 0, a druga 1 Koristimo formulu da izrazimo XOR operaciju 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

Korak2. Analiza sistema ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 T 0 1 0 1 .To. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), tada svaka vrijednost tk odgovara dva para vrijednosti x2k-1 i x2k, na primjer: tk =0 odgovara dva para - (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. originalni sistem ima 2*32 = 64 rješenja. Odgovor: 64

Metoda eliminacije dijela rješenja Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, ..., x5, y1,y2,..., y5 postoji koji zadovoljavaju sve dolje navedene uslove: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. U odgovoru nije potrebno navesti sve različite skupove x1, x2, ..., x5, y 1 , y2, ... , y5 za koje važi ovaj sistem jednakosti. Odgovor mora navesti broj takvih setova.

Rješenje. Korak 1. Sekvencijalno rješenje jednačina 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 jednačina je konjunkcija nekoliko operacija implikacije, jednakih 1, tj. svaka od implikacija je tačna. Implikacija je netač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 ovo u obliku tabele:

Korak 1. Sekvencijalno rješavanje jednačina T.o. Dobijeno je 6 setova 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 jednačine su nezavisne, tj. nemaju zajedničke varijable, tada će rješenje ovog sistema jednačina (bez uzimanja u obzir treće jednačine) biti 6 * 6 = 36 parova "X" i "Y". Razmotrimo treću jednačinu: y5→ x5 =1 Rješenje su parovi: 0 0 0 1 1 1 Par nije rješenje: 1 0

Uporedimo dobijena rješenja gdje je y5 =1, x5=0 nije prikladno. takvih parova ima 5. Broj rješenja sistema: 36-5= 31. Odgovor: Bila je potrebna 31 kombinatorika!!!

Metoda dinamičkog programiranja Koliko različitih rješenja ima logička jednačina 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 vrijedi ova jednakost. Kao odgovor, potrebno je navesti količine takvih kompleta.

Rješenje Korak 1. Analiza uslova Na lijevoj strani u jednačini operacije implikacije su sekvencijalno ispisane, prioritet je isti. Prepišimo: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Svaka sledeća varijabla ne zavisi od prethodne, već od rezultata prethodne implikacije!

Korak2. Otkrivanje obrasca Razmotrimo prvu implikaciju, X 1 → X 2. Tabela istinitosti: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Od jednog 0 dobili smo 2 jedinice, a od 1 dobili smo jednu 0 i jednu 1. Postoji samo jedna 0 i tri 1, ovo je rezultat prve operacije.

Korak2. Otkrivanje uzorka Povezivanjem x 3 sa rezultatom prve operacije dobijamo: 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 dva 0 – dva 1, od svakog 1 (ima 3) jedan 0 i jedan 1 (3+3)

Korak 3. Izvođenje formule T.o. možete kreirati formule za izračunavanje broja nula N i i broja jedinica E i za jednačinu sa i varijablama: ,

Korak 4. Popunjavanje tabele Popunimo tabelu s lijeva na desno za i = 6, računajući broj nula i jedinica koristeći gornje formule; tabela pokazuje kako se sljedeća kolona gradi od prethodne: 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 jednačina ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 gdje su J, K, L, M, N logičke varijable? U odgovoru nije potrebno navesti sve različite skupove vrijednosti J, K, L, M i N za koje ova jednakost vrijedi. Kao odgovor, potrebno je navesti broj takvih setova.

Rješenje Imajte na umu da J → K = ¬ J  K Uvedemo promjenu varijabli: J → K=A, M  N  L =B Prepišimo jednačinu uzimajući u obzir promjenu: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Očigledno, A  B za iste vrijednosti A i B 6. Razmotrimo posljednju implikaciju M → J =1 Ovo je moguće ako: M= J=0 M=0, J=1 M=J=1

Rešenje Jer A  B, tada kada je M=J=0 dobijamo 1 + K=0. Nema rješenja. Kada je M=0, J=1 dobijamo 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 dobijamo 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, br. 14, 2011, str. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronski izvor]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronski izvor].