Noskin Andrej Nikolajevič,
Učitelj informatike
najvišja kvalifikacijska kategorija,
Kandidat za vojaške vede, izredni profesor
Licej GBOU št. 1575, Moskva
Optimizirana metoda preslikave za reševanje problema 23 iz Enotnega državnega izpita KIM iz računalništva in IKT
Ena najtežjih nalog na enotnem državnem izpitu KIM je problem 23, v katerem morate najti število različnih nizov vrednosti logičnih spremenljivk, ki izpolnjujejo določen pogoj.
Ta naloga je morda najbolj težka naloga KIM Enotni državni izpit iz informatike in IKT. Praviloma ga ne obvlada več kot 5 % preiskovancev (1).
Tako majhen odstotek študentov, ki so opravili to nalogo, je razloženo z naslednjim:
- učenci lahko zamenjujejo (pozabljajo) znake logičnih operacij;
- matematične napake v procesu izvajanja izračunov;
- napake v sklepanju pri iskanju rešitve;
- napake v procesu poenostavljanja logičnih izrazov;
- učitelji priporočajo rešitev te težave po opravljenem celotnem delu, saj je verjetnost
napake so zelo velike, "teža" naloge pa je le ena primarna točka.
Poleg tega imajo nekateri učitelji sami težave pri reševanju tovrstnih problemov in zato poskušajo z otroki reševati preprostejše probleme.
Tudi zapleta situacijo je, da je v tem bloku veliko število različne naloge in je nemogoče izbrati predlogo rešitve.
Da bi popravili to situacijo, pedagoška skupnost dokončno oblikuje glavni dve metodi za reševanje problemov te vrste: rešitev z uporabo bitnih verig (2) in metode preslikave (3).
Potreba po izpopolnitvi (optimizaciji) teh metod je posledica dejstva, da se naloge nenehno spreminjajo tako po strukturi kot po številu spremenljivk (samo ena vrsta spremenljivk X, dve vrsti spremenljivk X in Y, tri vrste: X, Y , Z).
Težavnost obvladovanja teh metod za reševanje problemov potrjuje dejstvo, da na spletni strani K.Yu. Polyakova obstaja 38 analiz te vrste problema (4). Nekatere analize nudijo več kot eno rešitev problema.
Zadnje čase na enotnem državnem izpitu KIM iz računalništva so težave z dvema vrstama spremenljivk X in Y.
Optimiziral sem način prikaza in spodbujam svoje študente k uporabi izboljšanega načina.
To daje rezultate. Odstotek mojih učencev, ki se spopadejo s to nalogo, se giblje do 43 % uspešno opravljenih. Praviloma vsako leto od 25 do 33 ljudi iz vseh 11. razredov opravlja enotni državni izpit iz računalništva.
Preden so se pojavile težave z dvema vrstama spremenljivk, so učenci zelo uspešno uporabljali metodo preslikave, po pojavu Y v logičnem izrazu pa sem začel opažati, da odgovori otrok ne sovpadajo več s testi. Izkazalo se je, da jim ni čisto jasno, kako ustvariti tabelo preslikav z novo vrsto spremenljivke. Potem se mi je porodila misel, da je treba zaradi priročnosti celoten izraz zmanjšati na eno vrsto spremenljivke, kot je primerno za otroke.
To tehniko bom podrobneje predstavil. Zaradi udobja ga bom obravnaval na primeru sistema logičnih izrazov, podanega v (4).
Koliko različne rešitve ima sistem logičnih enačb
(x 1 ^ y 1)=(¬x 2 V ¬
l 2
)
(x 2 ^ y 2)= (¬
x 3
V ¬
l 3
)
...
(x 5 ^ y 5)
= (¬
x 6
V ¬
l 6
)
rešitev:
1. Iz analize sistema logičnih enačb vidimo, da obstaja 6 spremenljivk X in 6 spremenljivk U. Ker lahko katera koli od teh spremenljivk sprejme samo dve vrednosti (0 in 1), te spremenljivke nadomestimo z 12 spremenljivkami iste vrste, na primer Z.
2. Zdaj pa na novo napišimo sistem z novimi spremenljivkami istega tipa. Težavnost naloge bo skrbno beleženje pri zamenjavi spremenljivk.
(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. Sestavimo tabelo, v kateri bomo pregledali vse možnosti z 1 , z 2 , z 3 , z 4 , ker so v prvi logični enačbi štiri spremenljivke, bo imela tabela 16 vrstic (16=2 4); odstranite takšne vrednosti iz tabele z 4 , za katero prva enačba nima rešitve (prečrtana števila).
| 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. Z analizo tabele zgradimo pravilo za prikaz parov spremenljivk (na primer par Z 1 Z 2 =00 ustreza par Z 3 Z 4 = 11) .
5. Izpolnite tabelo tako, da izračunate število parov spremenljivk, za katere ima sistem rešitev. 
6. Seštejte vse rezultate: 9 + 9 + 9 + 27 = 54
7. Odgovor: 54.
Zgornja optimizirana metodologija za reševanje problema 23 iz enotnega državnega izpita KIM je študentom omogočila, da so ponovno pridobili zaupanje in uspešno rešili to vrsto problema.
Literatura:
1. FIPI. Smernice za učitelje, pripravljeno na podlagi analize tipičnih napak udeležencev Enotnega državnega izpita 2015 iz RAČUNALNIŠTVA in IKT. Način dostopa: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Polyakov, M.A. Roitberg.Sistemi logičnih enačb: rešitev z uporabo bitnih nizov. Revija za informatiko, številka 12, 2014, str. 4-12. Založba "Prvi september", Moskva.3. E.A. Mirončik, Način prikaza. Revija Informatika, številka 10, 2013, str. 18-26. Založba "Prvi september", Moskva.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kjer so J, K, L, M, N logične spremenljivke?
Razlaga.
Izraz (N ∨ ¬N) torej velja za vsak N
J ∧ ¬K ∧ L ∧ ¬M = 0.
Uporabimo negacijo na obeh straneh logične enačbe in uporabimo De Morganov zakon ¬ (A ∧ B) = ¬ A ∨ ¬ B. Dobimo ¬J ∨ K ∨ ¬L ∨ M = 1.
Logična vsota je enaka 1, če je vsaj ena od njenih sestavnih izjav enaka 1. Zato nastalo enačbo zadovolji katera koli kombinacija logičnih spremenljivk, razen v primeru, ko so vse količine, vključene v enačbo, enake 0. Vsaka od 4 spremenljivke so lahko enake 1 ali 0, zato so vse možne kombinacije 2·2·2·2 = 16. Zato ima enačba 16 −1 = 15 rešitev.
Opaziti je treba, da 15 najdenih rešitev ustreza kateri koli od obeh možne vrednosti vrednosti logične spremenljivke N, tako da ima izvirna enačba 30 rešitev.
Odgovor: 30
Koliko različnih rešitev ima enačba?
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
kjer so J, K, L, M, N logične spremenljivke?
Odgovoru ni treba navesti vseh različnih nizov vrednosti J, K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.
Razlaga.
Uporabimo formuli A → B = ¬A ∨ B in ¬(A ∨ B) = ¬A ∧ ¬B
Oglejmo si prvo podformulo:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Oglejmo si drugo podformulo
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Oglejmo si tretjo podformulo
1) M → J = 1 torej,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Združimo:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 torej 4 rešitve.
(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
Združimo:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L torej 4 rešitve.
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čnih rešitev ima enačba?
((K ∨ L) → (L ∧ M ∧ N)) = 0
kjer so K, L, M, N logične spremenljivke? V odgovoru ni treba navesti vseh različnih nizov vrednosti K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.
Razlaga.
Prepišimo enačbo z enostavnejšim zapisom za operacije:
((K + L) → (L M N)) = 0
1) iz tabele resnic operacije "implikacije" (glej prvi problem) sledi, da je ta enakost resnična, če in samo, če hkrati
K + L = 1 in L M N = 0
2) iz prve enačbe sledi, da je vsaj ena od spremenljivk, K ali L, enaka 1 (ali obe skupaj); torej razmislimo o treh primerih
3) če je K = 1 in L = 0, potem je druga enakost izpolnjena za poljubna M in N; ker obstajajo 4 kombinacije dveh logičnih spremenljivk (00, 01, 10 in 11), imamo 4 različne rešitve
4) če je K = 1 in L = 1, velja druga enakost za M · N = 0; obstajajo 3 takšne kombinacije (00, 01 in 10), imamo še 3 rešitve
5) če je K = 0, potem je L = 1 (iz prve enačbe); v tem primeru je druga enakost izpolnjena, ko je M · N = 0; obstajajo 3 takšne kombinacije (00, 01 in 10), imamo še 3 rešitve
6) skupaj dobimo 4 + 3 + 3 = 10 rešitev.
Odgovor: 10
Koliko različnih rešitev ima enačba?
(K ∧ L) ∨ (M ∧ N) = 1
Razlaga.
Izraz velja v treh primerih, ko sta (K ∧ L) in (M ∧ N) enaka 01, 11, 10.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N so enaki 1, K in L pa sta kar koli razen hkrati 1. Zato obstajajo 3 rešitve.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 rešitev.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 rešitve.
Odgovor: 7.
Odgovor: 7
Koliko različnih rešitev ima enačba?
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
kjer so X, Y, Z, P logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti, za katere velja ta enakost. Kot odgovor morate navesti samo število takih nizov.
Razlaga.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Logični ALI je napačen samo v enem primeru: ko sta oba izraza napačna.
torej
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Zato obstaja samo ena rešitev enačbe.
Odgovor: 1
Koliko različnih rešitev ima enačba?
(K ∨ L) ∧ (M ∨ N) = 1
kjer so K, L, M, N logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti samo število takih nizov.
Razlaga.
Logično In je resnično samo v enem primeru: ko so vsi izrazi resnični.
K ∨ L = 1, M ∨ N = 1.
Vsaka enačba daje 3 rešitve.
Razmislite o enačbi A ∧ B = 1, če tako A kot B sprejmeta prave vrednosti v treh primerih, potem ima enačba skupno 9 rešitev.
Zato je odgovor 9.
Odgovor: 9
Koliko različnih rešitev ima enačba?
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
kjer so A, B, C, D logične spremenljivke?
Odgovoru ni treba navesti vseh različnih nizov vrednosti A, B, C, D, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.
Razlaga.
Logični "ALI" je resničen, ko je vsaj ena od trditev resnična.
(D ∧ ¬D)= 0 za katerikoli D.
torej
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, kar nam daje 3 možne rešitve za vsako D.
(D ∧ ¬ D)= 0 za kateri koli D, kar nam da dve rešitvi (za D = 1, D = 0).
Torej: skupne rešitve 2*3 = 6.
Skupaj 6 rešitev.
Odgovor: 6
Koliko različnih rešitev ima enačba?
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
kjer so K, L, M, N logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti samo število takih nizov.
Razlaga.
Uporabimo negacijo na obeh straneh enačbe:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logični ALI velja v treh primerih.
Možnost 1.
K ∧ L ∧ M = 1, potem je K, L, M = 1 in ¬L ∧ M ∧ N = 0. N je poljubno, to je 2 rešitvi.
Možnost 2.
¬L ∧ M ∧ N = 1, potem N, M = 1; L = 0, K poljubno, to je 2 rešitvi.
Zato je odgovor 4.
Odgovor: 4
A, B in C so cela števila, za katera trditev velja
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Čemu je enako B, če je A = 45 in C = 43?
Razlaga.
1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);
2) ti preprosti stavki so povezani z operacijo ∧ (AND, konjunkcija), to pomeni, da jih je treba izvesti hkrati;
3) iz ¬(A = B)=1 takoj sledi A B;
4) predpostavimo, da je A > B, potem iz drugega pogoja dobimo 1→(B > C)=1; ta izraz je lahko resničen, če in samo če je B > C = 1;
5) torej imamo A > B > C, temu pogoju ustreza samo število 44;
6) za vsak slučaj preverimo še možnost A 0 →(B > C)=1;
ta izraz velja za vsak B; Zdaj pogledamo tretji pogoj in dobimo
ta izraz je lahko resničen, če in samo če je C > B, in tu imamo protislovje, ker ne obstaja takšno število B, za katerega bi bil C > B > A.
Odgovor: 44.
Odgovor: 44
Sestavite tabelo resnic za logično funkcijo
X = (A ↔ B) ∨ ¬(A → (B ∨ C))
v katerem je stolpec vrednosti argumenta A binarna predstavitev števila 27, stolpec vrednosti argumenta B je število 77, stolpec vrednosti argumenta C je število 120. Število v stolpcu je zapisano od zgoraj navzdol od najpomembnejšega do najmanj pomembnega (vključno z ničelnim nizom). Pretvorite dobljeno binarno predstavitev vrednosti funkcije X v decimalni številski sistem.
Razlaga.
Zapišimo enačbo z enostavnejšim zapisom za operacije:
1) to je izraz s tremi spremenljivkami, zato bodo v resnični tabeli črte; zato mora binarna predstavitev števil, ki se uporabljajo za sestavo stolpcev tabele A, B in C, sestavljati 8 števk
2) pretvorite številke 27, 77 in 120 v binarni sistem, tako da takoj dodate do 8 števk ničel na začetku številk
3) malo verjetno je, da boste lahko takoj zapisali vrednosti funkcije X za vsako kombinacijo, zato je priročno dodati dodatne stolpce v tabelo za izračun vmesnih rezultatov (glejte spodnjo tabelo)
| A | IN | Z | 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) izpolnite stolpce tabele:
| A | IN | Z | 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 |
vrednost je 1 samo v tistih vrsticah, kjer je A = B
vrednost je 1 v tistih vrsticah, kjer je B ali C = 1
vrednost je 0 samo v tistih vrsticah, kjer je A = 1 in B + C = 0
vrednost je inverzna vrednosti prejšnjega stolpca (0 se nadomesti z 1, 1 pa z 0)
rezultat X (zadnji stolpec) je logična vsota dveh stolpcev in
5) da dobite odgovor, zapišite bite iz stolpca X od zgoraj navzdol:
6) pretvorite to število v decimalni sistem:
Odgovor: 171
Katero je največje celo število X, za katerega velja izjava (10 (X+1)·(X+2))?
Razlaga.
Enačba je operacija implikacije med dvema razmerjema:
1) Seveda lahko tukaj uporabite isto metodo kot v primeru 2208, vendar boste morali rešiti kvadratne enačbe(Nočem…);
2) Upoštevajte, da nas po pogoju zanimajo samo cela števila, zato lahko poskusimo nekako preoblikovati izvirni izraz, tako da dobimo enakovredno izjavo (sploh nas ne zanimajo natančne vrednosti korenin!);
3) Razmislite o neenakosti: očitno je lahko pozitivno ali negativno število;
4) Preprosto je preveriti, ali je v domeni izjava resnična za vsa cela števila , in v domeni - za vsa cela števila (da ne bi prišlo do zmede, je bolj priročno uporabiti nestroge neenakosti in , namesto in );
5) Zato ga je za cela števila mogoče nadomestiti z enakovrednim izrazom
6) domena resnice izraza je zveza dveh neskončnih intervalov;
7) Zdaj razmislite o drugi neenakosti: očitno je, da je lahko tudi pozitivno ali negativno število;
8) V regiji izjava velja za vsa cela števila, v regiji pa za vsa cela števila, zato jo je za cela števila mogoče nadomestiti z enakovrednim izrazom
9) področje resnice izraza je zaprt interval;
10) Podani izraz velja povsod, razen na področjih, kjer in ;
11) Upoštevajte, da vrednost ni več primerna, ker tam in , kar pomeni, da implikacija daje 0;
12) Pri zamenjavi 2, (10 (2+1) · (2+2)) ali 0 → 0, ki izpolnjuje pogoj.
Torej je odgovor 2.
Odgovor: 2
Katero je največje celo število X, za katerega velja trditev
(50 (X+1)·(X+1))?
Razlaga.
Uporabimo implikacijsko transformacijo in transformirajmo izraz:
(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Logični ALI je resničen, ko je resnična vsaj ena logična izjava. Po rešitvi obeh neenačb in ob upoštevanju tega vidimo, da je največje celo število, za katerega je izpolnjena vsaj ena od njiju, 7 (na sliki je pozitivna rešitev druge neenačbe prikazana rumeno, prve pa modro).
Odgovor: 7
Navedite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
lažno. Odgovor zapišite kot niz 4 znakov: vrednosti spremenljivk K, L, M in N (v tem vrstnem redu). Tako na primer vrstica 1101 ustreza dejstvu, da je K=1, L=1, M=0, N=1.
Razlaga.
Podvaja nalogo 3584.
Odgovor: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Razlaga.
Uporabimo implikacijsko transformacijo:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Uporabimo negacijo na obeh straneh enačbe:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Pretvorimo:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Zato je M = 0, N = 0, zdaj upoštevajte (¬K ∧ L ∨ M ∧ L):
iz dejstva, da je M = 0, N = 0, sledi, da je M ∧ L = 0, potem je ¬K ∧ L = 1, torej K = 0, L = 1.
Odgovor: 0100
Določite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
lažno. Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk K, L, M in N (v tem vrstnem redu). Tako na primer vrstica 1101 ustreza dejstvu, da je K=1, L=1, M=0, N=1.
Razlaga.
Zapišimo enačbo s preprostejšim zapisom operacij (pogoj »izraz je napačen« pomeni, da je enak logični ničli):
1) iz formulacije pogoja sledi, da mora biti izraz napačen samo za en niz spremenljivk
2) iz tabele resnic operacije "implikacije" sledi, da je ta izraz napačen, če in samo, če hkrati
3) prva enakost (logični produkt je enak 1) je izpolnjena, če in samo če in ; iz tega sledi (logična vsota je enaka nič), kar se lahko zgodi samo takrat, ko ; Tako smo že definirali tri spremenljivke
4) iz drugega pogoja, , za in dobimo .
Podvaja nalogo
Odgovor: 1000
Določite vrednosti logičnih spremenljivk P, Q, S, T, pri katerih je logični izraz
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) je napačna.
Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk P, Q, S, T (v tem vrstnem redu).
Razlaga.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ Т)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Uporabimo implikacijsko transformacijo:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Odgovor: 0100
Določite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz
(K → M) ∨ (L ∧ K) ∨ ¬N
lažno. Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk K, L, M in N (v tem vrstnem redu). Tako na primer vrstica 1101 ustreza dejstvu, da je K=1, L=1, M=0, N=1.
Razlaga.
Logični ALI je napačen, če in samo če sta oba stavka napačna.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Uporabimo implikacijsko transformacijo za prvi izraz:
¬K ∨ M = 0 => K = 1, M = 0.
Razmislite o drugem izrazu:
(L ∧ K) ∨ ¬N = 0 (glej rezultat prvega izraza) => L ∨ ¬N = 0 => L = 0, N = 1.
Odgovor: 1001.
Odgovor: 1001
Določite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
prav. Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk K, L, M in N (v tem vrstnem redu). Tako na primer vrstica 1101 ustreza dejstvu, da je K=1, L=1, M=0, N=1.
Razlaga.
Logični "IN" je resničen, če in samo če sta obe izjavi resnični.
1) (K → M) = 1 Uporabite implikacijsko transformacijo: ¬K ∨ M = 1
2) (K → ¬M) = 1 Uporabite implikacijsko transformacijo: ¬K ∨ ¬M = 1
Iz tega sledi, da je K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Uporabimo implikacijsko transformacijo: K ∨ (M ∧ ¬L ∧ N) = 1 iz dejstva, da je K = 0, dobimo:
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Odgovor: 0011
Znano je, da za cela števila X, Y in Z velja naslednja izjava:
(Z Čemu je enak Z, če je X=25 in Y=48?
Razlaga.
Po zamenjavi števil dobimo, da je Z = 47.
Upoštevajte, da je ta zapletena izjava sestavljena iz treh preprostih
1) (Z 2) ti preprosti stavki so povezani z operacijo ∧ (AND, konjunkcija), kar pomeni, da jih je treba izvesti hkrati.
3) od ¬(Z+1 24 in od ¬(Z+1 47.
4) od (Z Z Odgovor: 47.
Odgovor: 47
A, B in C so cela števila, za katera velja naslednja izjava:
(C Kakšna je vrednost C, če je A=45 in B=18?
Razlaga.
Logični "IN" je resničen, če in samo če sta obe izjavi resnični.
Zamenjajmo števila v izraz:
1) (C (C 2) ¬(C+1, C ≥ 44.
3) ¬(C+1, C ≥ 17.
Iz 2) in 1) sledi, da je C
Odgovor: 44
¬(A = B) ∧ ((B A)) ∧ ((A 2C))
Kakšna je vrednost A, če je C = 8 in B = 18?
Razlaga.
Logični "IN" je resničen, če in samo če sta obe izjavi resnični.
1) ¬(A = B) = 1, to je A ≠ 18 = 1.
2) ((B A)) Uporabite implikacijsko transformacijo: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Uporabite implikacijsko transformacijo: (A > 18) ∨ (A > 16) = 1
Iz 2) in 3) sledi (18 > A) in (A > 16), saj sicer pride do protislovja: A = 17.
Odgovor: 17
A, B in C so cela števila, za katera trditev velja
¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
Kakšna je vrednost B, če je A = 45 in C = 18?
Razlaga.
Logični "IN" je resničen samo, če so vse izjave resnične.
Lahko izberete različne načine reševanje sistemov logičnih enačb. To je redukcija na eno enačbo, izdelava tabele resnic in dekompozicija.
Naloga: Rešite sistem logičnih enačb:
Razmislimo metoda redukcije na eno enačbo . Ta metoda vključuje preoblikovanje logičnih enačb tako, da so njihove desne strani enake vrednosti resnice (to je 1). Če želite to narediti, uporabite operacijo logičnega zanikanja. Nato, če enačbe vsebujejo zapletene logične operacije, jih nadomestimo z osnovnimi: "IN", "ALI", "NE". Naslednji korak je združitev enačb v eno, enakovredno sistemu, z uporabo logične operacije "IN". Po tem bi morali preoblikovati nastalo enačbo na podlagi zakonov logične algebre in dobiti specifično rešitev sistemi.
1. rešitev: Uporabite inverzijo na obeh straneh prve enačbe:
Predstavljajmo si implikacijo skozi osnovni operaciji "ALI" in "NE":
Ker so leve strani enačb enake 1, jih lahko združimo z operacijo »IN« v eno enačbo, ki je enakovredna izvirnemu sistemu:
Prvi oklepaj odpremo po De Morganovem zakonu in preoblikujemo dobljeni rezultat:
Nastala enačba ima eno rešitev: A =0, B=0 in C=1.
Naslednja metoda je sestavljanje tabel resnic . Ker imajo logične količine samo dve vrednosti, lahko preprosto pregledate vse možnosti in med njimi najdete tiste, za katere je izpolnjen dani sistem enačb. To pomeni, da ga gradimo splošna tabela resnice za vse enačbe sistema in poiščite premico z zahtevanimi vrednostmi.
Rešitev 2: Ustvarimo tabelo resnic za sistem:
|
0 |
0 |
1 |
1 |
0 |
1 |
Vrstica, za katero so izpolnjeni pogoji naloge, je označena s krepkim tiskom. Torej A=0, B=0 in C=1.
Pot razgradnja . Ideja je popraviti vrednost ene od spremenljivk (nastaviti jo na 0 ali 1) in s tem poenostaviti enačbe. Nato lahko popravite vrednost druge spremenljivke in tako naprej.
Rešitev 3: Naj bo A = 0, potem:
Iz prve enačbe dobimo B = 0, iz druge pa C = 1. Rešitev sistema: A = 0, B = 0 in C = 1.
Na Enotnem državnem izpitu iz računalništva je zelo pogosto treba določiti število rešitev sistema logičnih enačb, ne da bi našli same rešitve; za to obstajajo tudi določene metode. Glavni način za iskanje števila rešitev sistema logičnih enačb jezamenjava spremenljivk. Najprej morate vsako enačbo čim bolj poenostaviti na podlagi zakonov logične algebre, nato pa kompleksne dele enačb nadomestiti z novimi spremenljivkami in določiti število rešitev nov sistem. Nato se vrnite k zamenjavi in določite število rešitev zanjo.
Naloga: Koliko rešitev ima enačba (A →B) + (C →D) = 1? Kjer so A, B, C, D logične spremenljivke.
rešitev: Vstavimo nove spremenljivke: X = A →B in Y = C →D. Ob upoštevanju novih enačba spremenljivke bo zapisan v obliki: X + Y = 1.
Disjunkcija je resnična v treh primerih: (0;1), (1;0) in (1;1), medtem ko sta X in Y implikaciji, to pomeni, da je resnična v treh primerih in napačna v enem. Zato bo primer (0;1) ustrezal trem možnim kombinacijam parametrov. Primer (1;1) – bo ustrezal devetim možnim kombinacijam parametrov izvirne enačbe. Torej, skupaj možne rešitve te enačbe 3+9=15.
Naslednji način za določitev števila rešitev sistema logičnih enačb je binarno drevo. Razmislimo ta metoda Na primer.
Naloga: Koliko različnih rešitev ima sistem logičnih enačb:
Podani sistem enačb je enakovreden enačbi:
(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.
Pretvarjajmo se, da x 1 – je res, potem iz prve enačbe dobimo to x 2 tudi res, od drugega - x 3 =1 in tako naprej, dokler x m= 1. To pomeni, da je niz (1; 1; …; 1) m enot rešitev sistema. Naj zdaj x 1 =0, potem iz prve enačbe imamo x 2 =0 oz x 2 =1.
Kdaj x 2 res, dobimo, da so tudi preostale spremenljivke resnične, to pomeni, da je množica (0; 1; ...; 1) rešitev sistema. pri x 2 =0 to razumemo x 3 =0 oz x 3 = in tako naprej. Če nadaljujemo z zadnjo spremenljivko, ugotovimo, da so rešitve enačbe naslednji nizi spremenljivk (m +1 rešitev, vsaka rešitev vsebuje m vrednosti spremenljivk):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Ta pristop je dobro ponazorjen z izgradnjo binarnega drevesa. Število možnih rešitev je število različnih vej sestavljenega drevesa. Lahko vidimo, da je enako m +1.
|
Drevo |
Število rešitev |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
V primeru težav pri sklepanju raziskave in gradbeništvorešitev, s katerimi lahko iščete rešitev uporabo tabele resnic, za eno ali dve enačbi.
Prepišimo sistem enačb v obliki:
Ustvarimo tabelo resnic ločeno za eno enačbo:
|
x 1 |
x 2 |
(x 1 → x 2) |
Ustvarimo tabelo resnic za dve enačbi:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Metode reševanja sistemov logičnih enačb
Kirgizova E.V., Nemkova A.E.
Lesosibirsk pedagoški inštitut –
podružnica Sibirske zvezne univerze, Rusija
Sposobnost doslednega razmišljanja, prepričljivega sklepanja, postavljanja hipotez in zavračanja negativnih zaključkov ne pride sama od sebe; to veščino razvija znanost logike. Logika je veda, ki preučuje metode za ugotavljanje resničnosti ali napačnosti nekaterih trditev na podlagi resničnosti ali napačnosti drugih trditev.
Obvladovanje osnov te znanosti je nemogoče brez reševanja logičnih problemov. Preverjanje razvoja spretnosti za uporabo znanja v novi situaciji poteka s prehodom. Predvsem je to sposobnost odločanja logične težave. Naloge B15 na Enotnem državnem izpitu so naloge povečane kompleksnosti, saj vsebujejo sisteme logičnih enačb. Sisteme logičnih enačb lahko rešimo na različne načine. To je redukcija na eno enačbo, izdelava tabele resnic, dekompozicija, zaporedna rešitev enačb itd.
Naloga:Rešite sistem logičnih enačb:
Razmislimo metoda redukcije na eno enačbo . Ta metoda vključuje preoblikovanje logičnih enačb tako, da so njihove desne strani enake vrednosti resnice (to je 1). Če želite to narediti, uporabite operacijo logičnega zanikanja. Nato, če enačbe vsebujejo zapletene logične operacije, jih nadomestimo z osnovnimi: "IN", "ALI", "NE". Naslednji korak je združitev enačb v eno, enakovredno sistemu, z uporabo logične operacije "IN". Po tem bi morali preoblikovati nastalo enačbo na podlagi zakonov logične algebre in pridobiti specifično rešitev sistema.
1. rešitev:Uporabite inverzijo na obeh straneh prve enačbe:
Predstavljajmo si implikacijo skozi osnovni operaciji "ALI" in "NE":
Ker so leve strani enačb enake 1, jih lahko združimo z operacijo »IN« v eno enačbo, ki je enakovredna izvirnemu sistemu:
Prvi oklepaj odpremo po De Morganovem zakonu in preoblikujemo dobljeni rezultat:
Nastala enačba ima eno rešitev: A= 0, B =0 in C =1.
Naslednja metoda je sestavljanje tabel resnic . Ker imajo logične količine samo dve vrednosti, lahko preprosto pregledate vse možnosti in med njimi najdete tiste, za katere je izpolnjen dani sistem enačb. To pomeni, da zgradimo eno skupno tabelo resnic za vse enačbe sistema in poiščemo črto z zahtevanimi vrednostmi.
Rešitev 2:Ustvarimo tabelo resnic za sistem:
|
0 |
0 |
1 |
1 |
0 |
1 |
Vrstica, za katero so izpolnjeni pogoji naloge, je označena s krepkim tiskom. Torej A =0, B =0 in C =1.
Pot razgradnja . Ideja je popraviti vrednost ene od spremenljivk (nastaviti jo na 0 ali 1) in s tem poenostaviti enačbe. Nato lahko popravite vrednost druge spremenljivke in tako naprej.
Rešitev 3: Pustiti A = 0, potem:
Iz prve enačbe dobimo B =0, od drugega pa C=1. Rešitev sistema: A = 0, B = 0 in C = 1.
Uporabite lahko tudi metodo zaporedno reševanje enačb , pri čemer na vsakem koraku doda eno spremenljivko v obravnavani niz. Za to je potrebno transformirati enačbe tako, da so spremenljivke vnesene po abecednem vrstnem redu. Nato zgradimo drevo odločitev in mu zaporedno dodajamo spremenljivke.
Prva enačba sistema je odvisna samo od A in B, druga enačba pa od A in C. Spremenljivka A ima lahko 2 vrednosti 0 in 1:
Iz prve enačbe sledi, da 
, torej kdaj A = 0 in dobimo B = 0, za A = 1 pa imamo B = 1. Torej ima prva enačba dve rešitvi glede na spremenljivki A in B.
Pokažimo drugo enačbo, iz katere določimo vrednosti C za vsako možnost. Ko je A =1, implikacija ne more biti napačna, to pomeni, da druga veja drevesa nima rešitve. pri A= 0
dobimo edino rešitev C= 1
:
Tako smo dobili rešitev sistema: A = 0, B = 0 in C = 1.
Na Enotnem državnem izpitu iz računalništva je zelo pogosto treba določiti število rešitev sistema logičnih enačb, ne da bi našli same rešitve; za to obstajajo tudi določene metode. Glavni način za iskanje števila rešitev sistema logičnih enačb je zamenjava spremenljivk. Najprej morate vsako od enačb čim bolj poenostaviti na podlagi zakonov logične algebre, nato pa kompleksne dele enačb nadomestiti z novimi spremenljivkami in določiti število rešitev novega sistema. Nato se vrnite k zamenjavi in določite število rešitev zanjo.
Naloga:Koliko rešitev ima enačba ( A → B ) + (C → D ) = 1? Kjer so A, B, C, D logične spremenljivke.
rešitev:Uvedimo nove spremenljivke: X = A → B in Y = C → D . Ob upoštevanju novih spremenljivk bo enačba zapisana kot: X + Y = 1.
Disjunkcija velja v treh primerih: (0;1), (1;0) in (1;1), medtem ko X in Y je implikacija, kar pomeni, da je resnična v treh primerih in napačna v enem. Zato bo primer (0;1) ustrezal trem možnim kombinacijam parametrov. Primer (1;1) – bo ustrezal devetim možnim kombinacijam parametrov izvirne enačbe. To pomeni, da so skupne možne rešitve te enačbe 3+9=15.
Naslednji način za določitev števila rešitev sistema logičnih enačb je binarno drevo. Oglejmo si to metodo na primeru.
Naloga:Koliko različnih rešitev ima sistem logičnih enačb:
Podani sistem enačb je enakovreden enačbi:
( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.
Pretvarjajmo se, dax 1 – je res, potem iz prve enačbe dobimo tox 2 tudi res, od drugega -x 3 =1 in tako naprej, dokler x m= 1. Torej je množica (1; 1; …; 1) od m enot je rešitev sistema. Naj zdajx 1 =0, potem iz prve enačbe imamox 2 =0 oz x 2 =1.
Kdaj x 2 res, dobimo, da so tudi preostale spremenljivke resnične, to pomeni, da je množica (0; 1; ...; 1) rešitev sistema. prix 2 =0 to razumemo x 3 =0 oz x 3 = in tako naprej. Če nadaljujemo z zadnjo spremenljivko, ugotovimo, da so rešitve enačbe naslednji nizi spremenljivk ( m +1 rešitev, v vsaki raztopini m spremenljive vrednosti):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Ta pristop je dobro ponazorjen z izgradnjo binarnega drevesa. Število možnih rešitev je število različnih vej sestavljenega drevesa. Preprosto je videti, da je enak m +1.
|
Spremenljivke |
Drevo |
Število rešitev |
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
V primeru težav pri razmišljanju in gradnji odločitvenega drevesa lahko poiščete rešitev z uporabo tabele resnic, za eno ali dve enačbi.
Prepišimo sistem enačb v obliki:
Ustvarimo tabelo resnic ločeno za eno enačbo:
|
x 1 |
x 2 |
(x 1 → x 2) |
Ustvarimo tabelo resnic za dve enačbi:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Nato lahko vidite, da je ena enačba resnična v naslednjih treh primerih: (0; 0), (0; 1), (1; 1). Sistem dveh enačb je resničen v štirih primerih (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). V tem primeru je takoj jasno, da obstaja rešitev, sestavljena samo iz ničel in več m rešitve, pri katerih se dodaja ena enota naenkrat, začenši z zadnjega mesta, dokler niso zapolnjena vsa možna mesta. Lahko se domneva, da bo splošna rešitev imela enako obliko, a da bi tak pristop postal rešitev, je potreben dokaz, da je predpostavka pravilna.
Če povzamem vse zgoraj navedeno, bi vas rad opozoril na dejstvo, da vse obravnavane metode niso univerzalne. Pri reševanju vsakega sistema logičnih enačb je treba upoštevati njegove značilnosti, na podlagi katerih je treba izbrati način reševanja.
Literatura:
1. Logični problemi / O.B. Bogomolov – 2. izd. – M.: BINOM. Laboratorij znanja, 2006. – 271 str.: ilustr.
2. Polyakov K.Yu. Sistemi logičnih enačb / Poučno-metodični časopis za učitelje računalništva: Informatika št. 14, 2011.
Uporaba enačb je v našem življenju zelo razširjena. Uporabljajo se pri številnih izračunih, gradnji konstrukcij in celo športu. Človek je enačbe uporabljal že v pradavnini, od takrat pa se je njihova uporaba le še povečala. V matematiki obstajajo določeni problemi, ki se ukvarjajo s propozicionalno logiko. Če želite rešiti tovrstno enačbo, morate imeti določeno mero znanja: poznavanje zakonov propozicionalne logike, poznavanje tabel resničnosti logičnih funkcij 1 ali 2 spremenljivk, metode za pretvorbo logičnih izrazov. Poleg tega morate poznati naslednje lastnosti logičnih operacij: konjunkcija, disjunkcija, inverzija, implikacija in ekvivalenca.
Vsako logično funkcijo \variables - \lahko določite s tabelo resnic.
Rešimo več logičnih enačb:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Začnimo rešitev z \[X1\] in določimo, katere vrednosti lahko sprejme ta spremenljivka: 0 in 1. Nato bomo preučili vsako od zgornjih vrednosti in videli, kaj je lahko \[X2.\].
Kot je razvidno iz tabele, naš logična enačba ima 11 rešitev.
Kje lahko na spletu rešim logično enačbo?
Enačbo lahko rešite na naši spletni strani https://site. prost spletni reševalec vam bo omogočil reševanje spletnih enačb katere koli kompleksnosti v nekaj sekundah. Vse kar morate storiti je, da preprosto vnesete svoje podatke v reševalec. Ogledate si lahko tudi video navodila in se naučite reševati enačbo na naši spletni strani. In če imate še vedno vprašanja, jih lahko postavite v naši skupini VKontakte http://vk.com/pocketteacher. Pridružite se naši skupini, vedno vam z veseljem pomagamo.
