Noskin Andrej Nikolajevič,
IT-učitelj
najviša kvalifikacijska kategorija,
Kandidat vojnih znanosti, izvanredni profesor
Licej GBOU №1575 Moskva
Optimizirana metoda prikaza za rješavanje Zadatka 23 iz Jedinstvenog državnog ispita CMM iz informatike i informatike
Jedan od najtežih zadataka u KIM USE-u je zadatak 23, u kojem je potrebno pronaći broj različitih skupova vrijednosti logičkih varijabli koji zadovoljavaju navedeni uvjet.
Ovaj zadatak je gotovo najviše težak zadatak KIM Jedinstveni državni ispit iz informatike i ICT-a. U pravilu se s njim ne može nositi više od 5% ispitanika (1).
Tako mali postotak učenika koji su se nosili s ovim zadatkom objašnjava se sljedećim:
- učenici mogu zbuniti (zaboraviti) znakove logičkih operacija;
- matematičke pogreške u procesu izvođenja prorač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 svih radova, budući da je vjerojatnost pretpostavke
pogreške su vrlo velike, a "težina" problema je samo jedna primarna točka.
Osim toga, neki učitelji i sami teško rješavaju ovakvu vrstu problema i stoga pokušavaju riješiti jednostavnije probleme s djecom.
To također komplicira situaciju koja postoji u ovom bloku veliki broj razne zadatke i nemoguće je pokupiti nekakvo rješenje predloška.
Kako bi ispravila ovu situaciju, pedagoška zajednica dovršava dvije glavne metode za rješavanje problema ovog tipa: rješenje bitstringa (2) i metoda preslikavanja (3).
Potreba za doradom (optimizacijom) ovih tehnika proizilazi iz činjenice da se zadaci stalno mijenjaju kako u strukturi tako iu broju varijabli (samo jedna vrsta varijabli X, dvije vrste varijabli X i Y, tri vrste: X, Y, Z).
Teškoću svladavanja ovih metoda rješavanja problema potvrđuje činjenica da na web stranici K.Yu. Polyakov, postoji 38 analiza ove vrste problema (4). U nekim se analizama daje više od jedne vrste rješenja problema.
Posljednja vremena u KIM USE u informatici, postoje problemi s dvije vrste varijabli X i Y.
Optimizirao sam način prikaza i pozivam svoje učenike da koriste poboljšanu metodu.
Ovo daje rezultat. Postotak mojih učenika koji se nose s ovim zadatkom varira do 43% od onih koji prolaze. U pravilu svake godine ispit iz informatike polaže od 25 do 33 osobe iz svih 11 razreda.
Prije pojave problema s dvije vrste varijabli učenici su vrlo uspješno koristili metodu prikaza, no nakon pojavljivanja logičkog izraza Y počela sam primjećivati da se odgovori djece više ne podudaraju s testovima. Pokazalo se da nisu sasvim jasno razumjeli kako stvoriti tablicu mapiranja s novom vrstom varijable. Tada mi je sinula misao da je zbog praktičnosti potrebno cijeli izraz dovesti na jednu vrstu varijable, kako je prikladno za djecu.
Detaljnije ću dati ovu tehniku. Radi praktičnosti, razmotrit ću ga na primjeru sustava logičkih izraza danog u (4).
koliko različita rješenja ima sustav logičkih jednadžbi
(x 1 ^ y 1)=(¬x 2 V ¬
y 2
)
(x 2 ^ y 2)= (¬
x 3
V ¬
y 3
)
...
(x 5 ^ y 5)
= (¬
x 6
V ¬
y 6
)
Riješenje:
1. Iz analize sustava logičkih jednadžbi vidimo da postoji 6 varijabli NS i 6 varijabli Imati... Budući da bilo koja od ovih varijabli može imati samo dvije vrijednosti (0 i 1), te ćemo varijable zamijeniti s 12 varijabli istog tipa, na primjer Z.
2. Sada prepišimo sustav s novim varijablama istog tipa. Složenost zadatka leži u pažljivom zapisu pri mijenjanju 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 razvrstati 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 koje 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 podudaranja par Z 3 Z 4 = 11) .
5. Ispunite tablicu, izračunavajući broj parova varijabli za koje sustav ima rješenje. 
6. Zbrojite sve rezultate: 9 + 9 + 9 + 27 = 54
7. Odgovor: 54.
Navedena optimizirana metodologija rješavanja problema 23 iz CIM USE omogućila je studentima da povrate samopouzdanje i uspješno riješe ovu vrstu problema.
Književnost:
1. FIPI. Smjernice za nastavnike, pripremljen na temelju analize tipičnih pogrešaka sudionika KORIŠTENJE 2015. INFORMATIKA i ICT. 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 s bitstringovima. Informatički časopis, 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, stručni). 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.
Izraz (N ∨ ¬N) vrijedi za bilo koji N, dakle
J ∧ ¬K ∧ L ∧ ¬M = 0.
Primijenite negaciju na obje strane logičke jednadžbe i upotrijebite 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. Dakle, rezultirajuća jednadžba zadovoljava bilo koju kombinaciju logičkih varijabli, osim u slučaju kada su sve vrijednosti u jednadžbi jednake 0. Svaka od 4 varijable mogu biti jednake ili 1 ili 0, stoga su sve moguće kombinacije 2 · 2 · 2 · 2 = 16. Dakle, jednadžba ima 16 −1 = 15 rješenja.
Ostaje napomenuti da 15 pronađenih rješenja odgovara 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 ima jednadžba
((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 vrijedi ova jednakost. 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, dakle,
(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 postoje 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 postoje 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 ima jednadžba
((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 vrijedi ova jednakost. 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 "implikacije" (vidi prvi problem) proizlazi da je ta 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); stoga razmotrite tri slučaja
3) ako je K = 1 i L = 0, onda druga jednakost vrijedi za bilo koje M i N; budući da postoje 4 kombinacije dvije logičke varijable (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, onda je nužno L = 1 (iz prve jednadžbe); u ovom slučaju, druga je jednakost ispunjena pri M · N = 0; postoje 3 takve kombinacije (00, 01 i 10), imamo još 3 rješenja
6) ukupno dobivamo 4 + 3 + 3 = 10 rješenja.
Odgovor: 10
Koliko različitih rješenja ima jednadžba
(K ∧ L) ∨ (M ∧ N) = 1
Obrazloženje.
Izraz je istinit u tri slučaja kada su (K ∧ L) i (M ∧ N) 01, 11, 10, redom.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N su jednaki 1, a K i L su bilo koji, osim u isto vrijeme 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 ima jednadžba
(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 vrijedi data jednakost. 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čko ILI je lažno 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 ima jednadžba
(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 vrijedi ova jednakost. Kao odgovor, trebate samo navesti broj takvih skupova.
Obrazloženje.
Logički I je istinit 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 cijela jednadžba ima 9 rješenja.
Dakle, odgovor je 9.
Odgovor: 9
Koliko različitih rješenja ima jednadžba
((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 vrijedi ova jednakost. Kao odgovor, morate navesti broj takvih skupova.
Obrazloženje.
Logično ILI je istinito kada je barem jedan od iskaza istinit.
(D ∧ ¬D) = 0 za bilo koji D.
Stoga,
(A → B) ∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, što nam daje 3 rješenja za svaki D.
(D ∧ ¬ D) = 0 za bilo koji D, što nam daje dva rješenja (za D = 1, D = 0).
Dakle: ukupna rješenja 2 * 3 = 6.
Ukupno ima 6 rješenja.
Odgovor: 6
Koliko različitih rješenja ima jednadžba
(¬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 vrijedi ova jednakost. Kao odgovor, trebate samo navesti broj takvih skupova.
Obrazloženje.
Primijeni negaciju na obje strane jednadžbe:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logično ILI je istinito u tri slučaja.
Opcija 1.
K ∧ L ∧ M = 1, zatim K, L, M = 1 i ¬L ∧ M ∧ N = 0. N je bilo koje, odnosno 2 rješenja.
Opcija 2.
¬L ∧ M ∧ N = 1, zatim N, M = 1; L = 0, K je bilo koje, odnosno 2 rješenja.
Stoga je odgovor 4.
Odgovor: 4
A, B i C su cijeli brojevi za koje je tvrdnja točna
¬ (A = B) ∧ ((A> B) → (B> C)) ∧ ((B> A) → (C> B)).
Što je B ako je A = 45 i C = 43?
Obrazloženje.
1) ¬ (A = B); (A> B) → (B> C); (B> A) → (C> B);
2) ovi jednostavni izrazi 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 provjerite opciju A 0 → (B> C) = 1;
ovaj izraz vrijedi za bilo koji B; sada gledamo treći uvjet koji dobijemo
ovaj izraz može biti istinit ako i samo ako je C> B, a ovdje smo dobili kontradikciju, jer ne postoji takav broj B za koji je C> B> A.
Odgovor: 44.
Odgovor: 44
Napravite tablicu istinitosti za logičku funkciju
X = (A ↔ B) ∨ ¬ (A → (B ∨ C))
u kojem je stupac vrijednosti argumenta A binarni zapis broja 27, stupac vrijednosti argumenta B je broj 77, stupac vrijednosti argumenta C je broj 120. Broj u stupcu ispisuje se od vrha do dna od najznačajnijeg bita do najmanje značajnog (uključujući nulti skup). Pretvorite rezultirajući binarni zapis vrijednosti funkcije X u decimalni brojevni sustav.
Obrazloženje.
Zapišimo jednadžbu jednostavnijim zapisom operacija:
1) ovo je izraz s tri varijable, tako da će u tablici istinitosti biti redaka; stoga, binarni zapis brojeva koji se koriste za konstruiranje stupaca tablice A, B i C mora se sastojati od 8 znamenki
2) prevodimo brojeve 27, 77 i 120 u binarni sustav, odmah dopunjujući unos na 8 znamenki s nulama na početku brojeva
3) malo je vjerojatno da ćete moći odmah napisati vrijednosti funkcije X za svaku kombinaciju, pa je prikladno dodati dodatne stupce u tablicu za izračunavanje međurezultata (pogledajte tablicu ispod)
| A | V | 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) ispuniti stupce tablice:
| A | V | 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 redovima gdje je A = B
vrijednost je 1 u onim redovima gdje je ili B ili C = 1
vrijednost je 0 samo u onim redovima gdje je A = 1 i B + C = 0
vrijednost je inverzna od prethodnog stupca (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, napišite bitove iz stupca X od vrha do dna:
6) ovaj broj prevodimo u decimalni sustav:
Odgovor: 171
Koji je najveći cijeli broj X za koji je (10 (X + 1) · (X + 2)) istina?
Obrazloženje.
Jednadžba je operacija implikacije između dvije relacije:
1) Naravno, ovdje možete primijeniti istu metodu kao u primjeru 2208, ali u ovom slučaju morate 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 transformirati izvorni izraz nekako da dobijemo ekvivalentnu izjavu (uopće nas ne zanimaju točne vrijednosti korijena!);
3) Razmotrimo nejednakost: očito je da to mogu biti i pozitivni i negativni brojevi;
4) Lako je provjeriti da je u regiji izjava istinita za sve cijele brojeve, a u regiji - za sve cijele brojeve (kako se ne bi zabunili, prikladnije je koristiti nestroge nejednakosti, a umjesto i);
5) Stoga, za cijele brojeve, možete zamijeniti s ekvivalentnim izrazom
6) područje istinitosti izraza - unija dva beskonačna intervala;
7) Razmotrimo sada drugu nejednakost: očito je da to mogu biti i pozitivni i negativni brojevi;
8) U regiji je tvrdnja istinita za sve cijele brojeve, au regiji - za sve cijele brojeve, stoga se za cijele brojeve može zamijeniti ekvivalentnim izrazom
9) područje istinitosti izraza - zatvoreni interval;
10) Navedeni izraz vrijedi svugdje, osim za područja gdje i;
11) Imajte na umu da vrijednost više nije prikladna, jer tamo i, to jest, implikacija daje 0;
12) Zamjena 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 tvrdnja 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čko ILI je istinito kada je barem jedan logički iskaz istinit. Nakon što smo riješili obje nejednadžbe i uzevši u obzir da vidimo da je najveći cijeli broj kod kojeg je barem jedna od njih zadovoljena 7 (na slici žuta pokazuje pozitivno rješenje druge nejednadžbe, plava - prva).
Odgovor: 7
Navedite vrijednosti varijabli K, L, M, N, na kojima je logički izraz
(¬ (M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
lažno. Zapišite svoj odgovor kao niz od 4 znaka: vrijednosti varijabli K, L, M i N (navedenim redoslijedom). Tako, na primjer, linija 1101 odgovara činjenici da je K = 1, L = 1, M = 0, N = 1.
Obrazloženje.
Duplicira posao 3584.
Odgovor: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Obrazloženje.
Primijenimo transformaciju implikacije:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Primijeni negaciju na obje strane jednadžbe:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
transformirajmo:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Stoga, M = 0, N = 0, sada razmotrite (¬K ∧ L ∨ M ∧ L):
iz činjenice da je M = 0, N = 0 slijedi da je M ∧ L = 0, zatim ¬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. Zapiš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.
Zapišimo jednadžbu jednostavnijim zapisom operacija (uvjet "izraz je netačan" znači da je jednak logičkoj nuli):
1) iz formulacije uvjeta proizlazi da izraz mora biti netočan samo za jedan skup varijabli
2) iz tablice istinitosti operacije "implikacije" proizlazi da je ovaj izraz lažan ako i samo ako je u isto vrijeme
3) prva jednakost (logički proizvod je jednak 1) je zadovoljena ako i samo ako i; odavde slijedi (logički zbroj jednak nuli), što može biti samo na; 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 netočno.
Odgovor zapišite kao niz od četiri znaka: vrijednosti varijabli P, Q, S, T (u navedenom redoslijedu).
Obrazloženje.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ T)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ T)) = 0 Primjenjujemo transformaciju implikacije:
¬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. Zapiš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čno "ILI" je lažno ako i samo ako su obje izjave netočne.
(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. Zapiš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 "AND" je istinit ako i samo ako su obje tvrdnje istinite.
1) (K → M) = 1 Primijenite transformaciju implikacije: ¬K ∨ M = 1
2) (K → ¬M) = 1 Primijenite transformaciju implikacije: ¬K ∨ ¬M = 1
Iz toga slijedi da je K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Primjenjujemo transformaciju implikacije: 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 je za cijele brojeve X, Y i Z iskaz
(Z Što je Z 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 jednostavne
1) (Z 2) ovi jednostavni izrazi povezani su operacijom ∧ (AND, konjunkcija), odnosno moraju se izvršavati istovremeno.
3) od ¬ (Z + 1 24, i od ¬ (Z + 1 47.
4) iz (Z Z Odgovor: 47.
Odgovor: 47
A, B i C su cijeli brojevi za koje je tvrdnja točna:
(C Što je C ako je A = 45 i B = 18?
Obrazloženje.
Logički "AND" je istinit ako i samo ako su obje tvrdnje istinite.
Zamijenimo vrijednosti brojeva u izraz:
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))
Što je A ako je C = 8 i B = 18?.
Obrazloženje.
Logički "AND" je istinit ako i samo ako su obje tvrdnje istinite.
1) ¬ (A = B) = 1, odnosno A ≠ 18 = 1.
2) ((B A)) Primijenite transformaciju implikacije: (18> A) ∨ (16> A) = 1
3) (A 2C) Primijenite transformaciju implikacije: (A> 18) ∨ (A> 16) = 1
Iz 2) i 3) proizlazi da (18> A) i (A> 16), jer bi inače postojala kontradikcija A = 17.
Odgovor: 17
A, B i C su cijeli brojevi za koje je tvrdnja točna
¬ (A = B) ∧ ((A> B) → (C = B)) ∧ ((B> A) → (C = A))
Što je B ako je A = 45 i C = 18?
Obrazloženje.
Logično "I" je istinito samo kada su sve tvrdnje istinite.
Može se razlikovati različiti putevi rješenja sustava logičkih jednadžbi. To je svođenje na jednu jednadžbu, građenje tablice istinitosti i dekompozicija.
Zadatak: Riješite sustav logičkih jednadžbi:
Smatrati metoda redukcije na jednu jednadžbu ... Ova metoda uključuje transformaciju logičkih jednadžbi na takav način da su njihove desne strane jednake istinitoj vrijednosti (tj. 1). Za to se koristi operacija logičke negacije. Zatim, ako u jednadžbama postoje 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 "AND". Nakon toga trebate izvršiti transformaciju rezultirajuće jednadžbe na temelju zakona algebre logike i dobiti betonsko rješenje sustava.
Rješenje 1: Primijenite inverz na obje strane prve jednadžbe:
Predstavite implikaciju kroz osnovne operacije "ILI", "NE":
Budući da su lijeve strane jednadžbe jednake 1, možete ih kombinirati pomoću operacije "AND" 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ći način je građenje tablica istine ... Budući da logičke vrijednosti imaju samo dvije vrijednosti, možete jednostavno proći kroz sve opcije i među njima pronaći one za koje je ispunjen dati sustav jednadžbi. Odnosno, gradimo jedan opći stol istinitost za sve jednadžbe sustava i pronaći red s traženim vrijednostima.
Rješenje 2: Sastavimo tablicu istinitosti za sustav:
|
0 |
0 |
1 |
1 |
0 |
1 |
Podebljana je linija za koju su ispunjeni uvjeti zadatka. Dakle, A = 0, B = 0 i C = 1.
Put raspad ... Ideja je fiksirati vrijednost jedne od varijabli (staviti je jednakom 0 ili 1) i na taj način pojednostaviti jednadžbe. Tada možete popraviti vrijednost druge varijable, itd.
Rješenje 3: Neka je A = 0, tada:
Iz prve jednadžbe dobivamo B = 0, a iz druge - C = 1. Rješenje sustava: A = 0, B = 0 i C = 1.
Na ispitu iz informatike vrlo je često potrebno odrediti broj rješenja sustava logičkih jednadžbi, a da se ne pronađu sama rješenja, za to postoje i određene metode. Glavni način pronalaženja broja rješenja sustava logičkih jednadžbi jepromjena varijabli... Najprije je potrebno svaku od jednadžbi što više pojednostaviti 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.
Riješenje: Uvedimo nove varijable: X = A → B i Y = C → D. S obzirom na novo jednadžba varijabli biće zapisano kao: 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... Smatrati ovu metodu Na primjer.
Zadatak: Koliko različitih rješenja ima sustav logičkih jednadžbi:
Zadani sustav jednadžbi je ekvivalentan jednadžbi:
(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.
Pretvarajmo se to x 1 - istina, onda iz prve jednadžbe dobivamo to x 2 također istina, od drugog - x 3 = 1, i tako redom sve dok x m= 1. Dakle, skup (1; 1;…; 1) od m jedinica je rješenje sustava. Neka sada x 1 = 0, onda iz prve jednadžbe imamo x 2 = 0 ili x 2 =1.
Kada x 2 uistinu dobivamo da su i ostale varijable istinite, odnosno da je skup (0; 1;…; 1) rješenje sustava. Na x 2 = 0 dobivamo to 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 izgradnjom binarnog stabla. Broj mogućih rješenja je broj različitih grana izgrađenog stabla. Lako je vidjeti da je jednako m +1.
|
Drvo |
Broj rješenja |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
U slučaju poteškoća u zaključivanju niyah i zgrada dehuk rješenja, možete tražiti rješenje s korištenjem tablice istine, za jednu ili dvije jednadžbe.
Prepišimo sustav jednadžbi u obliku:
I sastavimo tablicu istinitosti zasebno za jednu jednadžbu:
|
x 1 |
x 2 |
(x 1 → x 2) |
Sastavimo 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) |
Načini rješavanja sustava logičkih jednadžbi
Kirgizova E.V., Nemkova A.E.
Lesosibirsk pedagoški institut -
podružnica Sibirskog saveznog sveučilišta, Rusija
Sposobnost dosljednog razmišljanja, rasuđivanja s dokazima, izgradnje hipoteza, pobijanja negativnih zaključaka ne dolazi sama po sebi, tu vještinu razvija znanost logike. Logika je znanost koja proučava metode utvrđivanja istinitosti ili netočnosti nekih tvrdnji na temelju istinitosti ili neistinitosti drugih izjava.
Ovladavanje osnovama ove znanosti nemoguće je bez rješavanja logičkih problema. Provjera formiranja vještina primjene znanja u novoj situaciji provodi se na trošak isporuke. Konkretno, ova sposobnost rješavanja logičkih zadataka... Zadaci B15 na ispitu su zadaci povećane složenosti, budući da 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, izgradnja tablice istinitosti, dekompozicija, sekvencijalno rješavanje jednadžbi, itd.
Zadatak:Riješite sustav logičkih jednadžbi:
Smatrati metoda redukcije na jednu jednadžbu ... Ova metoda uključuje transformaciju logičkih jednadžbi na takav način da su njihove desne strane jednake istinitoj vrijednosti (tj. 1). Za to se koristi operacija logičke negacije. Zatim, ako u jednadžbama postoje 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 "AND". Nakon toga trebate izvršiti transformaciju rezultirajuće jednadžbe na temelju zakona logičke algebre i dobiti specifično rješenje sustava.
Rješenje 1:Primijenite inverz na obje strane prve jednadžbe:
Predstavite implikaciju kroz osnovne operacije "ILI", "NE":
Budući da su lijeve strane jednadžbe jednake 1, možete ih kombinirati pomoću operacije "AND" 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ći način je građenje tablica istine ... Budući da logičke vrijednosti imaju samo dvije vrijednosti, možete jednostavno proći kroz sve opcije i među njima pronaći one za koje je ispunjen dati sustav jednadžbi. To jest, gradimo jednu zajedničku tablicu istinitosti za sve jednadžbe u sustavu i pronalazimo redak s traženim vrijednostima.
Rješenje 2:Sastavimo tablicu istinitosti za sustav:
|
0 |
0 |
1 |
1 |
0 |
1 |
Podebljana je linija za koju su ispunjeni uvjeti zadatka. Dakle, A = 0, B = 0 i C = 1.
Put raspad . Ideja je fiksirati vrijednost jedne od varijabli (staviti je jednakom 0 ili 1) i na taj način pojednostaviti jednadžbe. Tada možete popraviti vrijednost druge varijable, itd.
Rješenje 3: Neka bude A = 0, tada:
Iz prve jednadžbe dobivamo B = 0, a od drugog - C = 1. Rješenje sustava: A = 0, B = 0 i C = 1.
Također možete koristiti metodu sekvencijalno rješavanje jednadžbi , pri svakom koraku dodajući jednu varijablu skupu koji se razmatra. Da biste to učinili, potrebno je jednadžbe transformirati na način da se varijable unose abecednim redom. Zatim gradimo stablo odlučivanja, uzastopno mu dodajući varijable.
Prva jednadžba u sustavu 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, za A = 0 i dobivamo B = 0, a za A = 1 dobivamo B = 1. Dakle, prva jednadžba ima dva rješenja za varijable A i B.
Nacrtajmo drugu jednadžbu iz koje određujemo vrijednosti C za svaku opciju. Za 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 ispitu iz informatike vrlo je često potrebno odrediti broj rješenja sustava logičkih jednadžbi, a da se ne pronađu sama rješenja, za to postoje i određene metode. Glavni način pronalaženja broja rješenja sustava logičkih jednadžbi je promjena varijabli... Najprije je potrebno svaku od jednadžbi što više pojednostaviti 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.
Riješenje:Hajde da predstavimo nove varijable: X = A → B i Y = C → D ... Uzimajući u obzir nove varijable, jednadžba će biti napisana u obliku: X + Y = 1.
Disjunkcija je istinita u tri slučaja: (0; 1), (1; 0) i (1; 1), dok X i Y je implikacija, odnosno istinita je u tri slučaja i 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 postoji 3 + 9 = 15 mogućih rješenja ove jednadžbe.
Sljedeći način određivanja broja rješenja sustava logičkih jednadžbi je binarno stablo... Razmotrimo ovu metodu na primjeru.
Zadatak:Koliko različitih rješenja ima sustav logičkih jednadžbi:
Zadani sustav jednadžbi je ekvivalentan jednadžbi:
( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.
Pretvarajmo se tox 1 - istina, onda iz prve jednadžbe dobivamo tox 2 također istina, od drugog -x 3 = 1, i tako redom sve dok x m= 1. Stoga je skup (1; 1; ...; 1) iz m jedinica je rješenje sustava. Neka sadax 1 = 0, onda iz prve jednadžbe imamox 2 = 0 ili x 2 =1.
Kada x 2 uistinu dobivamo da su i ostale varijable istinite, odnosno da je skup (0; 1;…; 1) rješenje sustava. Nax 2 = 0 dobivamo to 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 po m vrijednosti varijabli):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Ovaj pristup je dobro ilustriran izgradnjom binarnog stabla. Broj mogućih rješenja je broj različitih grana izgrađenog stabla. Lako je vidjeti da je jednako 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 sastavimo tablicu istinitosti zasebno za jednu jednadžbu:
|
x 1 |
x 2 |
(x 1 → x 2) |
Sastavimo 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) |
Nadalje, možete vidjeti da je jedna jednadžba istinita u sljedeća tri slučaja: (0; 0), (0; 1), (1; 1). Sustav dviju jednadžbi istinit je 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 nekoliko nula i više m rješenja u kojima se dodaje jedna jedinica, počevši od zadnje pozicije do popunjenja svih mogućih 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 istinita.
Sumirajući sve gore navedeno, želio bih vam skrenuti pozornost na činjenicu da nisu sve razmatrane metode univerzalne. Prilikom rješavanja svakog sustava logičkih jednadžbi treba uzeti u obzir njegove značajke, na temelju kojih treba odabrati metodu rješenja.
Književnost:
1. Logički zadaci / O.B. Bogomolov - 2. izd. - M .: BINOM. Laboratorij znanja, 2006. - 271 str .: ilustr.
2. Polyakov K.Yu. Sustavi logičkih jednadžbi / Nastavno-metodički list za nastavnike informatike: Informatika br.14, 2011.
Upotreba jednadžbi je raširena u našem životu. Koriste se u mnogim proračunima, građevinarstvu, pa čak i u sportu. Čovjek je u antičko doba koristio jednadžbe i od tada se njihova primjena samo povećava. U matematici postoje određeni problemi koji su posvećeni logici propozicija. Za rješavanje ovakve jednadžbe potrebno je imati određeno znanje: poznavanje zakona propozicijske logike, poznavanje tablica istinitosti logičkih funkcija 1 ili 2 varijable, metode transformacije logičkih izraza. Osim toga, potrebno je poznavati sljedeća svojstva logičkih operacija: konjunkciju, disjunkciju, inverziju, implikaciju i ekvivalentnost.
Bilo koja logička funkcija \ varijabli - \ može biti specificirana tablicom istinitosti.
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 imati: 0 i 1. Zatim razmotrite svaku od gornjih vrijednosti i pogledajte što može biti u ovom slučaju \ [X2. \]
Kao što možete vidjeti iz tablice, naš logička jednadžba ima 11 rješenja.
Gdje možete riješiti logičku jednadžbu na internetu?
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žbe bilo koje složenosti u nekoliko sekundi. Sve što trebate učiniti je samo unijeti svoje podatke u rješavač. 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.
