Noskin Andrej Nikolajevič,
učitelj informatike
najviša kvalifikacijska kategorija,
Kandidat vojnih znanosti, izvanredni profesor
GBOU licej br. 1575, Moskva
Optimizirana metoda mapiranja za rješavanje problema 23 s KIM Jedinstvenog državnog ispita iz računarstva i ICT-a
Jedan od najtežih zadataka na Jedinstvenom državnom ispitu KIM je problem 23, u kojem morate pronaći broj različitih skupova vrijednosti logičkih varijabli koje zadovoljavaju navedeni uvjet.
Ovaj zadatak je možda najviše težak zadatak KIM Jedinstveni državni ispit iz informatike i ICT-a. U pravilu se s njim nosi najviše 5% ispitanika (1).
Tako mali postotak učenika koji su riješili ovaj zadatak objašnjava se sljedećim:
- učenici mogu pobrkati (zaboraviti) znakove logičkih operacija;
- matematičke pogreške u procesu izvođenja izračuna;
- pogreške u zaključivanju pri traženju rješenja;
- pogreške u procesu pojednostavljivanja logičkih izraza;
- učitelji preporučuju rješavanje ovog problema nakon završetka cijelog posla, budući da je vjerojatnost
pogreške su vrlo velike, a "težina" zadatka je samo jedna primarna točka.
Osim toga, neki učitelji i sami teško rješavaju ovu vrstu problema pa pokušavaju s djecom rješavati jednostavnije probleme.
Također komplicira situaciju je da u ovom bloku postoji veliki broj razne zadatke i nemoguće je odabrati šablonsko rješenje.
Kako bi ispravili ovu situaciju, pedagoška zajednica dovršava dvije glavne metode za rješavanje problema ove vrste: rješenje pomoću lanaca bitova (2) i metode preslikavanja (3).
Potreba za usavršavanjem (optimiziranjem) ovih metoda proizlazi iz činjenice da se zadaci stalno mijenjaju kako u strukturi tako i u broju varijabli (samo jedna vrsta varijabli X, dvije vrste varijabli X i Y, tri vrste: X, Y , Z).
Teškoće svladavanja ovih metoda za rješavanje problema potvrđuje činjenica da na web stranici K.Yu. Polyakova postoji 38 analiza ove vrste problema (4). Neke analize daju više od jedne vrste rješenja za problem.
U zadnje vrijeme na KIM Jedinstvenom državnom ispitu iz informatike postoje problemi s dvije vrste varijabli X i Y.
Optimizirao sam metodu prikaza i potičem svoje učenike da koriste poboljšanu metodu.
Ovo daje rezultate. Postotak mojih učenika koji se nose s ovim zadatkom varira do 43% prolaznih. U pravilu svake godine od 25 do 33 osobe iz svih 11. razreda polažu jedinstveni državni ispit iz informatike.
Prije pojave problema s dvije vrste varijabli učenici su vrlo uspješno koristili metodu mapiranja, ali nakon pojave Y u logičkom izrazu počeo sam primjećivati da se odgovori djece više ne poklapaju s testovima. Ispostavilo se da im nije baš jasno kako napraviti tablicu preslikavanja s novom vrstom varijable. Tada mi je pala na pamet da bi zbog praktičnosti cijeli izraz trebalo svesti na jednu vrstu varijable, kako je zgodno za djecu.
Ovu metodu ću dati detaljnije. Radi praktičnosti, razmotrit ću to koristeći primjer sustava logičkih izraza danih u (4).
Koliko razna rješenja ima sustav logičkih jednadžbi
(x 1 ^ y 1)=(¬x 2 V ¬
g 2
)
(x 2 ^ y 2)= (¬
x 3
V ¬
g 3
)
...
(x 5 ^ y 5)
= (¬
x 6
V ¬
g 6
)
Otopina:
1. Iz analize sustava logičkih jednadžbi vidimo da postoji 6 varijabli X i 6 varijabli U. Budući da bilo koja od ovih varijabli može poprimiti samo dvije vrijednosti (0 i 1), te varijable zamijenimo s 12 varijabli istog tipa, na primjer Z.
2. Sada prepravimo sustav s novim varijablama istog tipa. Teškoća zadatka bit će pažljivo vođenje bilješki prilikom zamjene varijabli.
(z 1 ^ z 2)=
(¬z 3V¬
z 4
)
(z 3 ^ z 4)=
(¬
z 5
V¬
z 6
)
...
(z 9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Napravimo tablicu u kojoj ćemo proći kroz sve opcije z 1 , z 2 , z 3 , z 4 , budući da u prvoj logičkoj jednadžbi postoje četiri varijable, tablica će imati 16 redaka (16=2 4); uklonite takve vrijednosti iz tablice z 4 , za koju prva jednadžba nema rješenja (precrtani brojevi).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Analizirajući tablicu, gradimo pravilo za prikaz parova varijabli (npr. par Z 1 Z 2 =00 odgovara par Z 3 Z 4 = 11) .
5. Ispunite tablicu izračunavanjem broja parova varijabli za koje sustav ima rješenje. 
6. Zbrojite sve rezultate: 9 + 9 + 9 + 27 = 54
7. Odgovor: 54.
Gore navedena optimizirana metoda za rješavanje zadatka 23 s Jedinstvenog državnog ispita KIM omogućila je studentima da vrate samopouzdanje i uspješno riješe ovu vrstu problema.
Književnost:
1. FIPI. Metodičke preporuke za nastavnike, pripremljeno na temelju analize tipičnih pogrešaka sudionika Jedinstvenog državnog ispita iz INFORMACIJSKIH ZNANOSTI i ICT-a 2015. Način pristupa: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Polyakov, M.A. Roitberg.Sustavi logičkih jednadžbi: rješavanje nizovima bitova. Časopis za informatiku, broj 12, 2014., str. 4-12 (prikaz, stručni). Izdavačka kuća "Prvi rujan", Moskva.3. E.A. Mironchik, Način prikaza.Časopis Informatika, broj 10, 2013., str. 18-26 (prikaz, ostalo). Izdavačka kuća "Prvi rujan", Moskva.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, gdje su J, K, L, M, N logičke varijable?
Obrazloženje.
Stoga je izraz (N ∨ ¬N) istinit za bilo koji N
J ∧ ¬K ∧ L ∧ ¬M = 0.
Primijenimo negaciju na obje strane logičke jednadžbe i upotrijebimo De Morganov zakon ¬ (A ∧ B) = ¬ A ∨ ¬ B. Dobivamo ¬J ∨ K ∨ ¬L ∨ M = 1.
Logički zbroj jednak je 1 ako je barem jedan od njegovih sastavnih iskaza jednak 1. Stoga je rezultirajuća jednadžba zadovoljena bilo kojom kombinacijom logičkih varijabli osim u slučaju kada su sve veličine uključene u jednadžbu jednake 0. Svaki od 4 varijable mogu biti jednake ili 1 ili 0, stoga su sve moguće kombinacije 2·2·2·2 = 16. Prema tome, jednadžba ima 16 −1 = 15 rješenja.
Ostaje primijetiti da 15 pronađenih rješenja odgovaraju bilo kojem od ta dva moguće vrijednosti vrijednosti logičke varijable N, tako da izvorna jednadžba ima 30 rješenja.
Odgovor: 30
Koliko različitih rješenja jednadžba ima?
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (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.
Obrazloženje.
Koristimo formule A → B = ¬A ∨ B i ¬(A ∨ B) = ¬A ∧ ¬B
Razmotrimo prvu podformulu:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Razmotrimo drugu podformulu
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Razmotrimo treću podformulu
1) M → J = 1 prema tome,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Kombinirajmo:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 dakle 4 rješenja.
(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
Kombinirajmo:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L dakle 4 rješenja.
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.
Odgovor: 4 + 4 = 8.
Odgovor: 8
Koliko različitih rješenja jednadžba ima?
((K ∨ L) → (L ∧ M ∧ N)) = 0
gdje su K, L, M, N logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti K, L, M i N za koje ova jednakost vrijedi. Kao odgovor morate navesti broj takvih skupova.
Obrazloženje.
Prepišimo jednadžbu koristeći jednostavniji zapis za operacije:
((K + L) → (L M N)) = 0
1) iz tablice istinitosti operacije “implikacija” (vidi prvi problem) slijedi da je ova jednakost istinita ako i samo ako u isto vrijeme
K + L = 1 i L M N = 0
2) iz prve jednadžbe proizlazi da je barem jedna od varijabli, K ili L, jednaka 1 (ili obje zajedno); pa razmotrimo tri slučaja
3) ako je K = 1 i L = 0, onda je druga jednakost zadovoljena za bilo koji M i N; budući da postoje 4 kombinacije dviju Booleovih varijabli (00, 01, 10 i 11), imamo 4 različita rješenja
4) ako je K = 1 i L = 1, onda druga jednakost vrijedi za M · N = 0; postoje 3 takve kombinacije (00, 01 i 10), imamo još 3 rješenja
5) ako je K = 0, tada je L = 1 (iz prve jednadžbe); u ovom slučaju, druga jednakost je zadovoljena kada je M · N = 0; postoje 3 takve kombinacije (00, 01 i 10), imamo još 3 rješenja
6) ukupno dobijemo 4 + 3 + 3 = 10 rješenja.
Odgovor: 10
Koliko različitih rješenja jednadžba ima?
(K ∧ L) ∨ (M ∧ N) = 1
Obrazloženje.
Izraz je točan u tri slučaja, kada su (K ∧ L) i (M ∧ N) jednaki 01, 11, 10, redom.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N su jednaki 1, a K i L su sve osim istovremeno 1. Dakle, postoje 3 rješenja.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 rješenje.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 rješenja.
Odgovor: 7.
Odgovor: 7
Koliko različitih rješenja jednadžba ima?
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
gdje su X, Y, Z, P logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti za koje ova jednakost vrijedi. Kao odgovor trebate samo navesti broj takvih skupova.
Obrazloženje.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Logički ILI je lažan samo u jednom slučaju: kada su oba izraza lažna.
Stoga,
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Stoga postoji samo jedno rješenje jednadžbe.
Odgovor: 1
Koliko različitih rješenja jednadžba ima?
(K ∨ L) ∧ (M ∨ N) = 1
gdje su K, L, M, N logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti K, L, M i N za koje ova jednakost vrijedi. Kao odgovor trebate samo navesti broj takvih skupova.
Obrazloženje.
Logičko I je istinito samo u jednom slučaju: kada su svi izrazi istiniti.
K ∨ L = 1, M ∨ N = 1.
Svaka od jednadžbi daje 3 rješenja.
Razmotrimo jednadžbu A ∧ B = 1, ako i A i B imaju prave vrijednosti u po tri slučaja, tada jednadžba ukupno ima 9 rješenja.
Stoga je odgovor 9.
Odgovor: 9
Koliko različitih rješenja jednadžba ima?
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
gdje su A, B, C, D logičke varijable?
Odgovor ne mora navesti sve različite skupove vrijednosti A, B, C, D za koje ova jednakost vrijedi. Kao odgovor morate navesti broj takvih skupova.
Obrazloženje.
Logičko "ILI" je istinito kada je barem jedna od izjava istinita.
(D ∧ ¬D)= 0 za bilo koji D.
Stoga,
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, što nam daje 3 moguća rješenja za svaki D.
(D ∧ ¬ D)= 0 za bilo koji D, što nam daje dva rješenja (za D = 1, D = 0).
Prema tome: ukupna rješenja 2*3 = 6.
Ukupno 6 rješenja.
Odgovor: 6
Koliko različitih rješenja jednadžba ima?
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
gdje su K, L, M, N logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti K, L, M i N za koje ova jednakost vrijedi. Kao odgovor trebate samo navesti broj takvih skupova.
Obrazloženje.
Primijenimo negaciju na obje strane jednadžbe:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logički ILI je istinit u tri slučaja.
Opcija 1.
K ∧ L ∧ M = 1, zatim K, L, M = 1 i ¬L ∧ M ∧ N = 0. N je proizvoljno, odnosno 2 rješenja.
opcija 2.
¬L ∧ M ∧ N = 1, zatim N, M = 1; L = 0, K bilo koje, odnosno 2 rješenja.
Stoga je odgovor 4.
Odgovor: 4
A, B i C su cijeli brojevi za koje je tvrdnja istinita
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Čemu je jednako B ako je A = 45 i C = 43?
Obrazloženje.
1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);
2) ovi jednostavni iskazi povezani su operacijom ∧ (AND, konjunkcija), odnosno moraju se izvršavati istovremeno;
3) iz ¬(A = B)=1 odmah slijedi da je A B;
4) pretpostavimo da je A > B, tada iz drugog uvjeta dobivamo 1→(B > C)=1; ovaj izraz može biti istinit ako i samo ako je B > C = 1;
5) dakle imamo A > B > C, ovom uvjetu odgovara samo broj 44;
6) za svaki slučaj, provjerimo i opciju A 0 →(B > C)=1;
ovaj izraz je istinit za bilo koji B; sada pogledajte treći uvjet koji dobivamo
ovaj izraz može biti istinit ako i samo ako je C > B, a ovdje imamo kontradikciju, jer ne postoji takav broj B za koji je C > B > A.
Odgovor: 44.
Odgovor: 44
Konstruirajte tablicu istine za logičku funkciju
X = (A ↔ B) ∨ ¬(A → (B ∨ C))
u kojem je stupac vrijednosti argumenta A binarna reprezentacija broja 27, stupac vrijednosti argumenta B je broj 77, stupac vrijednosti argumenta C je broj 120. Broj u stupcu se piše odozgo prema dolje od najznačajnijeg do najmanje značajnog (uključujući nulti skup). Pretvorite dobiveni binarni prikaz vrijednosti funkcije X u decimalni brojevni sustav.
Obrazloženje.
Napišimo jednadžbu koristeći jednostavniji zapis za operacije:
1) ovo je izraz s tri varijable, pa će u tablici istine biti linija; stoga se binarna reprezentacija brojeva korištenih za konstrukciju stupaca tablice A, B i C mora sastojati od 8 znamenki
2) pretvoriti brojeve 27, 77 i 120 u binarni sustav, odmah dodajući do 8 znamenki nula na početku brojeva
3) malo je vjerojatno da ćete moći odmah napisati vrijednosti funkcije X za svaku kombinaciju, pa je zgodno dodati dodatne stupce u tablicu za izračun međurezultata (pogledajte tablicu u nastavku)
| A | U | 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) ispunite stupce tablice:
| A | U | 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 |
vrijednost je 1 samo u onim linijama gdje je A = B
vrijednost je 1 u onim redovima gdje je B ili C = 1
vrijednost je 0 samo u onim linijama gdje je A = 1 i B + C = 0
vrijednost je inverzna u odnosu na prethodni stupac (0 se zamjenjuje s 1, a 1 se zamjenjuje s 0)
rezultat X (zadnji stupac) je logički zbroj dvaju stupaca i
5) da biste dobili odgovor, ispišite bitove iz stupca X od vrha prema dnu:
6) pretvorite ovaj broj u decimalni sustav:
Odgovor: 171
Koji je najveći cijeli broj X za koji je tvrdnja (10 (X+1)·(X+2)) točna?
Obrazloženje.
Jednadžba je operacija implikacije između dva odnosa:
1) Naravno, ovdje možete primijeniti istu metodu kao u primjeru 2208, ali ćete morati riješiti kvadratne jednadžbe(Ne želim...);
2) Imajte na umu da nas prema uvjetu zanimaju samo cijeli brojevi, tako da možemo pokušati nekako transformirati izvorni izraz, dobivajući ekvivalentnu izjavu (uopće nas ne zanimaju točne vrijednosti korijena!);
3) Razmotrimo nejednadžbu: očito, ona može biti ili pozitivan ili negativan broj;
4) Lako je provjeriti da je u domeni izjava istinita za sve cijele brojeve , au domeni - za sve cijele brojeve (kako se ne bi zbunili, prikladnije je koristiti nestriktne nejednakosti, a , umjesto i );
5) Stoga se za cijele brojeve može zamijeniti ekvivalentnim izrazom
6) područje istinitosti izraza je unija dvaju beskonačnih intervala;
7) Razmotrimo sada drugu nejednakost: očito je da ona također može biti ili pozitivan ili negativan broj;
8) U domeni izjava je istinita za sve cijele brojeve, au domeni - za sve cijele brojeve, stoga se za cijele brojeve može zamijeniti ekvivalentnim izrazom
9) područje istinitosti izraza je zatvoreni interval;
10) Dani izraz je istinit posvuda, osim u područjima gdje i ;
11) Imajte na umu da vrijednost više nije prikladna, jer postoji i , to jest, implikacija daje 0;
12) Prilikom zamjene 2, (10 (2+1) · (2+2)), ili 0 → 0 što zadovoljava uvjet.
Dakle, odgovor je 2.
Odgovor: 2
Koji je najveći cijeli broj X za koji je izjava točna
(50 (X+1)·(X+1))?
Obrazloženje.
Primijenimo transformaciju implikacije i transformirajmo izraz:
(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Logički ILI je istinit kada je barem jedna logička izjava istinita. Nakon što smo riješili obje nejednadžbe i uzevši to u obzir vidimo da je najveći cijeli broj za koji je barem jedna od njih zadovoljena 7 (na slici je pozitivno rješenje druge nejednadžbe prikazano žutom, a prve plavom bojom).
Odgovor: 7
Navedite vrijednosti varijabli K, L, M, N, na kojima je logički izraz
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
lažno. Napišite svoj odgovor kao niz od 4 znaka: vrijednosti varijabli K, L, M i N (tim redoslijedom). Tako, na primjer, linija 1101 odgovara činjenici da je K=1, L=1, M=0, N=1.
Obrazloženje.
Duplicira zadatak 3584.
Odgovor: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Obrazloženje.
Primijenimo transformaciju implikacije:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Primijenimo negaciju na obje strane jednadžbe:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Preobrazimo se:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Prema tome, M = 0, N = 0, sada razmotrimo (¬K ∧ L ∨ M ∧ L):
iz činjenice da je M = 0, N = 0 slijedi da je M ∧ L = 0, tada je ¬K ∧ L = 1, odnosno K = 0, L = 1.
Odgovor: 0100
Navedite vrijednosti varijabli K, L, M, N na kojima je logički izraz
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
lažno. Napišite svoj odgovor kao niz od četiri znaka: vrijednosti varijabli K, L, M i N (tim redoslijedom). Tako, na primjer, linija 1101 odgovara činjenici da je K=1, L=1, M=0, N=1.
Obrazloženje.
Napišimo jednadžbu jednostavnijim zapisom operacija (uvjet “izraz je lažan” znači da je jednak logičkoj nuli):
1) iz formulacije uvjeta slijedi da izraz mora biti lažan samo za jedan skup varijabli
2) iz tablice istinitosti operacije “implikacija” slijedi da je ovaj izraz lažan ako i samo ako u isto vrijeme
3) prva jednakost (logički umnožak je jednak 1) zadovoljena je ako i samo ako je i ; iz ovoga slijedi (logička suma je jednaka nuli), što se može dogoditi samo kada ; Dakle, već smo definirali tri varijable
4) iz drugog uvjeta, , za i dobivamo .
Duplicira zadatak
Odgovor: 1000
Navedite vrijednosti logičkih varijabli P, Q, S, T, na kojima je logički izraz
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) je lažna.
Odgovor napišite kao niz od četiri znaka: vrijednosti varijabli P, Q, S, T (tim redoslijedom).
Obrazloženje.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ T)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ T)) = 0 Primijenimo implikacijsku transformaciju:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Odgovor: 0100
Navedite vrijednosti varijabli K, L, M, N na kojima je logički izraz
(K → M) ∨ (L ∧ K) ∨ ¬N
lažno. Napišite svoj odgovor kao niz od četiri znaka: vrijednosti varijabli K, L, M i N (tim redoslijedom). Tako, na primjer, linija 1101 odgovara činjenici da je K=1, L=1, M=0, N=1.
Obrazloženje.
Logičko ILI je lažno ako i samo ako su oba iskaza lažna.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Primijenimo transformaciju implikacije za prvi izraz:
¬K ∨ M = 0 => K = 1, M = 0.
Razmotrimo drugi izraz:
(L ∧ K) ∨ ¬N = 0 (vidi rezultat prvog izraza) => L ∨ ¬N = 0 => L = 0, N = 1.
Odgovor: 1001.
Odgovor: 1001
Navedite vrijednosti varijabli K, L, M, N na kojima je logički izraz
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
pravi. Napišite svoj odgovor kao niz od četiri znaka: vrijednosti varijabli K, L, M i N (tim redoslijedom). Tako, na primjer, linija 1101 odgovara činjenici da je K=1, L=1, M=0, N=1.
Obrazloženje.
Logički "I" je istinit ako i samo ako su obje izjave istinite.
1) (K → M) = 1 Primijenite transformaciju implikacije: ¬K ∨ M = 1
2) (K → ¬M) = 1 Primijenite implikacijsku transformaciju: ¬K ∨ ¬M = 1
Slijedi da je K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Primijenimo implikacijsku transformaciju: K ∨ (M ∧ ¬L ∧ N) = 1 iz činjenice da je K = 0 dobivamo:
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Odgovor: 0011
Poznato je da za cijele brojeve X, Y i Z vrijedi sljedeća tvrdnja:
(Z Koliko je Z jednako ako je X=25 i Y=48?
Obrazloženje.
Nakon zamjene brojeva dobivamo da je Z = 47.
Imajte na umu da se ova složena izjava sastoji od tri jednostavna
1) (Z 2) ovi jednostavni iskazi povezani su operacijom ∧ (AND, konjunkcija), odnosno moraju se izvršavati istovremeno.
3) od ¬(Z+1 24, i od ¬(Z+1 47.
4) od (Z Z Odgovor: 47.
Odgovor: 47
A, B i C su cijeli brojevi za koje vrijedi sljedeća izjava:
(C Koja je vrijednost C ako je A=45 i B=18?
Obrazloženje.
Logički "I" je istinit ako i samo ako su obje izjave istinite.
Zamijenimo brojeve u izrazu:
1) (C (C 2) ¬(C+1, C ≥ 44.
3) ¬(C+1, C ≥ 17.
Iz 2) i 1) slijedi da je C
Odgovor: 44
¬(A = B) ∧ ((B A)) ∧ ((A 2C))
Kolika je vrijednost A ako je C = 8 i B = 18?
Obrazloženje.
Logički "I" je istinit ako i samo ako su obje izjave istinite.
1) ¬(A = B) = 1, odnosno A ≠ 18 = 1.
2) ((B A)) Primijenite implikacijsku transformaciju: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Primijenite transformaciju implikacije: (A > 18) ∨ (A > 16) = 1
Iz 2) i 3) slijedi da je (18 > A) i (A > 16), jer u suprotnom dolazi do kontradikcije: A = 17.
Odgovor: 17
A, B i C su cijeli brojevi za koje je tvrdnja istinita
¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
Kolika je vrijednost B ako je A = 45 i C = 18?
Obrazloženje.
Logički "I" je istinit samo ako su svi iskazi istiniti.
Možete odabrati razne načine rješavanje sustava logičkih jednadžbi. To je svođenje na jednu jednadžbu, konstrukcija tablice istinitosti i dekompozicija.
Zadatak: Riješite sustav logičkih jednadžbi:
Razmotrimo metoda svođenja na jednu jednadžbu . Ova metoda uključuje transformaciju logičkih jednadžbi tako da su njihove desne strane jednake istinitoj vrijednosti (tj. 1). Da biste to učinili, upotrijebite operaciju logičke negacije. Zatim, ako jednadžbe sadrže složene logičke operacije, zamjenjujemo ih osnovnim: “I”, “ILI”, “NE”. Sljedeći korak je kombiniranje jednadžbi u jednu, ekvivalentnu sustavu, koristeći logičku operaciju "I". Nakon toga trebate transformirati dobivenu jednadžbu na temelju zakona logičke algebre i dobiti specifično rješenje sustava.
Rješenje 1: Primijenite inverziju na obje strane prve jednadžbe:
Zamislimo implikaciju kroz osnovne operacije "ILI" i "NE":
Budući da su lijeve strane jednadžbi jednake 1, možemo ih kombinirati pomoću operacije "I" u jednu jednadžbu koja je ekvivalentna izvornom sustavu:
Otvaramo prvu zagradu prema De Morganovom zakonu i transformiramo dobiveni rezultat:
Rezultirajuća jednadžba ima jedno rješenje: A =0, B=0 i C=1.
Sljedeća metoda je konstruiranje tablica istinitosti . Budući da logičke veličine imaju samo dvije vrijednosti, možete jednostavno proći kroz sve opcije i pronaći među njima one za koje je zadani sustav jednadžbi zadovoljen. Odnosno, gradimo jedan opći stol istinitost za sve jednadžbe sustava i pronaći pravac s traženim vrijednostima.
Rješenje 2: Kreirajmo tablicu istine za sustav:
|
0 |
0 |
1 |
1 |
0 |
1 |
Podebljano je istaknuta linija za koju su ispunjeni uvjeti zadatka. Dakle, A=0, B=0 i C=1.
Način raspad . Ideja je popraviti vrijednost jedne od varijabli (postaviti je na 0 ili 1) i time pojednostaviti jednadžbe. Zatim možete popraviti vrijednost druge varijable, i tako dalje.
Rješenje 3: Neka je A = 0, tada je:
Iz prve jednadžbe dobivamo B = 0, a iz druge - C = 1. Rješenje sustava: A = 0, B = 0 i C = 1.
Na Jedinstvenom državnom ispitu iz informatike vrlo je često potrebno odrediti broj rješenja sustava logičkih jednadžbi, bez pronalaženja samih rješenja; za to postoje i određene metode. Glavni način da se pronađe broj rješenja sustava logičkih jednadžbi jezamjena varijabli. Najprije morate pojednostaviti svaku od jednadžbi što je više moguće na temelju zakona logičke algebre, a zatim zamijeniti složene dijelove jednadžbi novim varijablama i odrediti broj rješenja novi sustav. Zatim se vratite na zamjenu i odredite broj rješenja za nju.
Zadatak: Koliko rješenja ima jednadžba (A →B) + (C →D) = 1? Gdje su A, B, C, D logičke varijable.
Otopina: Uvedimo nove varijable: X = A →B i Y = C →D. Uzimajući u obzir nove jednadžba varijable bit će zapisan u obliku: X + Y = 1.
Disjunkcija je istinita u tri slučaja: (0;1), (1;0) i (1;1), dok su X i Y implikacije, odnosno istinita je u tri slučaja, a netočna u jednom. Stoga će slučaj (0;1) odgovarati trima mogućim kombinacijama parametara. Slučaj (1;1) – odgovarat će devet mogućih kombinacija parametara izvorne jednadžbe. Dakle, ukupno moguća rješenja ove jednadžbe 3+9=15.
Sljedeći način određivanja broja rješenja sustava logičkih jednadžbi je binarno stablo. Razmotrimo ovu metodu primjerom.
Zadatak: Koliko različitih rješenja ima sustav logičkih jednadžbi:
Zadani sustav jednadžbi ekvivalentan je jednadžbi:
(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.
Pretpostavimo to x 1 – je istina, onda iz prve jednadžbe dobivamo to x 2 također istina, od drugog - x 3 =1, i tako dalje sve dok x m= 1. To znači da je skup (1; 1; …; 1) od m jedinica rješenje sustava. Neka sada x 1 =0, tada iz prve jednadžbe imamo x 2 =0 ili x 2 =1.
Kada x 2 true, dobivamo da su i preostale varijable istinite, odnosno skup (0; 1; ...; 1) je rješenje sustava. Na x 2 =0 to dobivamo x 3 =0 ili x 3 =, i tako dalje. Nastavljajući na posljednju varijablu, nalazimo da su rješenja jednadžbe sljedeći skupovi varijabli (m +1 rješenje, svako rješenje sadrži m vrijednosti varijabli):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Ovaj pristup je dobro ilustriran konstruiranjem binarnog stabla. Broj mogućih rješenja je broj različitih grana izgrađenog stabla. Lako je vidjeti da je jednak m +1.
|
Drvo |
Broj rješenja |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
U slučaju poteškoća u zaključivanju istraživanja i izgradnjerješenja pomoću kojih možete tražiti rješenje korištenjem tablice istine, za jednu ili dvije jednadžbe.
Prepišimo sustav jednadžbi u obliku:
I napravimo tablicu istinitosti zasebno za jednu jednadžbu:
|
x 1 |
x 2 |
(x 1 → x 2) |
Napravimo tablicu istinitosti za dvije jednadžbe:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Metode rješavanja sustava logičkih jednadžbi
Kirgizova E.V., Nemkova A.E.
Lesosibirsk pedagoški institut –
podružnica Sibirskog federalnog sveučilišta, Rusija
Sposobnost dosljednog razmišljanja, uvjerljivog zaključivanja, izgradnje hipoteza i pobijanja negativnih zaključaka ne dolazi sama od sebe; ovu vještinu razvija znanost logike. Logika je znanost koja proučava metode utvrđivanja istinitosti ili netočnosti nekih izjava na temelju istinitosti ili netočnosti drugih izjava.
Ovladavanje osnovama ove znanosti nemoguće je bez rješavanja logičkih problema. Provjera razvoja sposobnosti za primjenu znanja u novoj situaciji provodi se polaganjem. Konkretno, to je sposobnost odlučivanja logički problemi. Zadaci B15 na Jedinstvenom državnom ispitu su zadaci povećane složenosti, jer sadrže sustave logičkih jednadžbi. Postoje različiti načini rješavanja sustava logičkih jednadžbi. To je svođenje na jednu jednadžbu, konstrukcija tablice istine, dekompozicija, sekvencijalno rješavanje jednadžbi itd.
Zadatak:Riješite sustav logičkih jednadžbi:
Razmotrimo metoda svođenja na jednu jednadžbu . Ova metoda uključuje transformaciju logičkih jednadžbi tako da su njihove desne strane jednake istinitoj vrijednosti (tj. 1). Da biste to učinili, upotrijebite operaciju logičke negacije. Zatim, ako jednadžbe sadrže složene logičke operacije, zamjenjujemo ih osnovnim: “I”, “ILI”, “NE”. Sljedeći korak je kombiniranje jednadžbi u jednu, ekvivalentnu sustavu, koristeći logičku operaciju "I". Nakon toga trebate transformirati dobivenu jednadžbu na temelju zakona logičke algebre i dobiti specifično rješenje sustava.
Rješenje 1:Primijenite inverziju na obje strane prve jednadžbe:
Zamislimo implikaciju kroz osnovne operacije "ILI" i "NE":
Budući da su lijeve strane jednadžbi jednake 1, možemo ih kombinirati pomoću operacije "I" u jednu jednadžbu koja je ekvivalentna izvornom sustavu:
Otvaramo prvu zagradu prema De Morganovom zakonu i transformiramo dobiveni rezultat:
Dobivena jednadžba ima jedno rješenje: A= 0, B =0 i C =1.
Sljedeća metoda je konstruiranje tablica istinitosti . Budući da logičke veličine imaju samo dvije vrijednosti, možete jednostavno proći kroz sve opcije i pronaći među njima one za koje je zadani sustav jednadžbi zadovoljen. To jest, gradimo jednu zajedničku tablicu istine za sve jednadžbe sustava i pronalazimo liniju s traženim vrijednostima.
Rješenje 2:Kreirajmo tablicu istine za sustav:
|
0 |
0 |
1 |
1 |
0 |
1 |
Podebljano je istaknuta linija za koju su ispunjeni uvjeti zadatka. Dakle, A =0, B =0 i C =1.
Način raspad . Ideja je popraviti vrijednost jedne od varijabli (postaviti je na 0 ili 1) i time pojednostaviti jednadžbe. Zatim možete popraviti vrijednost druge varijable, i tako dalje.
Rješenje 3: Neka A = 0, tada:
Iz prve jednadžbe dobivamo B =0, a iz drugog – C=1. Rješenje sustava: A = 0, B = 0 i C = 1.
Također možete koristiti metodu sekvencijalno rješavanje jednadžbi , u svakom koraku dodajući jednu varijablu skupu koji se razmatra. Za to je potrebno transformirati jednadžbe tako da se varijable upisuju abecednim redom. Zatim gradimo stablo odlučivanja, uzastopno mu dodajući varijable.
Prva jednadžba sustava ovisi samo o A i B, a druga jednadžba o A i C. Varijabla A može imati 2 vrijednosti 0 i 1:
Iz prve jednadžbe slijedi da 
, dakle kada A = 0 i dobivamo B = 0, a za A = 1 imamo B = 1. Dakle, prva jednadžba ima dva rješenja u odnosu na varijable A i B.
Oslikajmo drugu jednadžbu iz koje određujemo vrijednosti C za svaku opciju. Kada je A =1, implikacija ne može biti lažna, odnosno druga grana stabla nema rješenja. Na A= 0
dobivamo jedino rješenje C= 1
:
Tako smo dobili rješenje sustava: A = 0, B = 0 i C = 1.
Na Jedinstvenom državnom ispitu iz informatike vrlo je često potrebno odrediti broj rješenja sustava logičkih jednadžbi, bez pronalaženja samih rješenja; za to postoje i određene metode. Glavni način da se pronađe broj rješenja sustava logičkih jednadžbi je zamjena varijabli. Najprije morate pojednostaviti svaku od jednadžbi što je više moguće na temelju zakona logičke algebre, a zatim zamijeniti složene dijelove jednadžbi novim varijablama i odrediti broj rješenja novog sustava. Zatim se vratite na zamjenu i odredite broj rješenja za nju.
Zadatak:Koliko rješenja ima jednadžba ( A → B ) + (C → D ) = 1? Gdje su A, B, C, D logičke varijable.
Otopina:Uvedimo nove varijable: X = A → B i Y = C → D . Uzimajući u obzir nove varijable, jednadžba će biti zapisana kao: X + Y = 1.
Disjunkcija je istinita u tri slučaja: (0;1), (1;0) i (1;1), dok X i Y je implikacija, to jest istinita je u tri slučaja, a lažna u jednom. Stoga će slučaj (0;1) odgovarati trima mogućim kombinacijama parametara. Slučaj (1;1) – odgovarat će devet mogućih kombinacija parametara izvorne jednadžbe. To znači da su ukupna moguća rješenja ove jednadžbe 3+9=15.
Sljedeći način određivanja broja rješenja sustava logičkih jednadžbi je binarno stablo. Pogledajmo ovu metodu na primjeru.
Zadatak:Koliko različitih rješenja ima sustav logičkih jednadžbi:
Zadani sustav jednadžbi ekvivalentan je jednadžbi:
( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.
Pretpostavimo tox 1 – je istina, onda iz prve jednadžbe dobivamo tox 2 također istina, od drugog -x 3 =1, i tako dalje sve dok x m= 1. Dakle, skup (1; 1; …; 1) od m jedinica je rješenje sustava. Neka sadax 1 =0, tada iz prve jednadžbe imamox 2 =0 ili x 2 =1.
Kada x 2 true, dobivamo da su i preostale varijable istinite, odnosno skup (0; 1; ...; 1) je rješenje sustava. Nax 2 =0 to dobivamo x 3 =0 ili x 3 =, i tako dalje. Nastavljajući na posljednju varijablu, nalazimo da su rješenja jednadžbe sljedeći skupovi varijabli ( m +1 rješenje, u svakom rješenju m varijabilne vrijednosti):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Ovaj pristup je dobro ilustriran konstruiranjem binarnog stabla. Broj mogućih rješenja je broj različitih grana izgrađenog stabla. Lako je vidjeti da je jednak m +1.
|
Varijable |
Drvo |
Broj rješenja |
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
U slučaju poteškoća u zaključivanju i izgradnji stabla odlučivanja, rješenje možete potražiti pomoću tablice istine, za jednu ili dvije jednadžbe.
Prepišimo sustav jednadžbi u obliku:
I napravimo tablicu istinitosti zasebno za jednu jednadžbu:
|
x 1 |
x 2 |
(x 1 → x 2) |
Napravimo tablicu istinitosti za dvije jednadžbe:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Dalje, možete vidjeti da je jedna jednadžba točna u sljedeća tri slučaja: (0; 0), (0; 1), (1; 1). Sustav dviju jednadžbi je istinit u četiri slučaja (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). U ovom slučaju odmah je jasno da postoji rješenje koje se sastoji od samo nula i više m rješenja u kojima se dodaje jedna po jedna jedinica, počevši od posljednjeg mjesta dok se ne popune sva moguća mjesta. Može se pretpostaviti da će opće rješenje imati isti oblik, ali da bi takav pristup postao rješenje, potreban je dokaz da je pretpostavka točna.
Rezimirajući sve gore navedeno, želio bih vam skrenuti pozornost na činjenicu da nisu sve metode koje se raspravljaju univerzalne. Pri rješavanju svakog sustava logičkih jednadžbi treba voditi računa o njegovim značajkama, na temelju kojih treba odabrati način rješavanja.
Književnost:
1. Logički problemi / O.B. Bogomolov – 2. izd. – M.: BINOM. Laboratorij znanja, 2006. – 271 str.: ilustr.
2. Polyakov K.Yu. Sustavi logičkih jednadžbi / Nastavno metodičke novine za nastavnike informatike: Informatika broj 14, 2011.
Upotreba jednadžbi široko je rasprostranjena u našim životima. Koriste se u mnogim izračunima, izgradnji građevina, pa čak i sportu. Čovjek je koristio jednadžbe u davna vremena, a od tada se njihova upotreba samo povećava. U matematici postoje određeni problemi koji se bave iskaznom logikom. Za rješavanje ovakve jednadžbe potrebno je imati određeno znanje: poznavanje zakona logike iskaza, poznavanje tablica istinitosti logičkih funkcija 1 ili 2 varijable, metode za pretvaranje logičkih izraza. Osim toga, potrebno je poznavati sljedeća svojstva logičkih operacija: konjunkciju, disjunkciju, inverziju, implikaciju i ekvivalenciju.
Bilo koja logička funkcija \varijable - \može se specificirati tablicom istine.
Riješimo nekoliko logičkih jednadžbi:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Započnimo rješenje s \[X1\] i odredimo koje vrijednosti ova varijabla može poprimiti: 0 i 1. Zatim ćemo razmotriti svaku od gornjih vrijednosti i vidjeti što može biti \[X2.\].
Kao što je vidljivo iz tablice, naš logička jednadžba ima 11 rješenja.
Gdje mogu riješiti logičku jednadžbu online?
Jednadžbu možete riješiti na našoj web stranici https://site. Besplatno online rješavač omogućit će vam rješavanje online jednadžbi bilo koje složenosti u nekoliko sekundi. Sve što trebate učiniti je jednostavno unijeti svoje podatke u Solver. Također možete pogledati video upute i naučiti kako riješiti jednadžbu na našoj web stranici. A ako još uvijek imate pitanja, možete ih postaviti u našoj VKontakte grupi http://vk.com/pocketteacher. Pridružite se našoj grupi, uvijek ćemo vam rado pomoći.
