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, učiteljska 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čne enačbe
(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.
Metode reševanja sistemov logičnih enačb
Sistem logičnih enačb lahko rešite na primer z uporabo tabele resnic (če število spremenljivk ni preveliko) ali z uporabo odločitvenega drevesa, tako da najprej poenostavite vsako enačbo.
1. Metoda zamenjave spremenljivke.
Uvedba novih spremenljivk vam omogoča poenostavitev sistema enačb in zmanjšanje števila neznank.Nove spremenljivke morajo biti neodvisne druga od druge. Po rešitvi poenostavljenega sistema se moramo vrniti k prvotnim spremenljivkam.
Oglejmo si uporabo te metode na posebnem primeru.
Primer.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
rešitev:
Uvedimo nove spremenljivke: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Pozor! Vsaka od spremenljivk x1, x2, ..., x10 mora biti vključena le v eno od novih spremenljivke A, B, C, D, E, tj. nove spremenljivke so neodvisne druga od druge).
Potem bo sistem enačb videti takole:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Zgradimo drevo odločitev za nastali sistem:
Upoštevajte enačbo A=0, tj. (X1≡ X2)=0. Ima 2 korena:
X1 ≡ X2 |
||
Iz iste tabele je razvidno, da ima tudi enačba A=1 2 korena. Uredimo število korenin na odločitvenem drevesu:
Če želite najti število rešitev ene veje, morate pomnožiti število rešitev na vsaki ravni. Leva veja ima 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 rešitev; tudi desna veja ima 32 rešitev. Tisti. celoten sistem ima 32+32=64 rešitev.
Odgovor: 64.
2. Metoda sklepanja.
Težavnost reševanja sistemov logičnih enačb je v okornosti celotnega odločitvenega drevesa. Metoda sklepanja vam omogoča, da ne zgradite celotnega drevesa, ampak razumete, koliko vej bo imelo. Oglejmo si to metodo na konkretnih primerih.
Primer 1. Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, za katere je ta sistem enakosti izpolnjen. Kot odgovor morate navesti število takih nizov.
rešitev:
Prva in druga enačba vsebujeta neodvisne spremenljivke, ki so povezane s tretjim pogojem. Zgradimo drevo rešitev za prvo in drugo enačbo.
Za predstavitev drevesa rešitev za sistem prve in druge enačbe je treba vsako vejo prvega drevesa nadaljevati z drevesom za spremenljivke pri . Tako zgrajeno drevo bo vsebovalo 36 vej. Nekatere od teh vej ne zadoščajo tretji enačbi sistema. Na prvem drevesu označimo število vej drevesa"y" , ki zadoščajo tretji enačbi:
Naj pojasnimo: za izpolnitev tretjega pogoja, ko je x1=0, mora obstajati y1=1, tj. vse veje drevesa."X" , kjer je x1=0 mogoče nadaljevati samo z eno vejo iz drevesa"y" . In samo za eno vejo drevesa"X" (desno) se prilegajo vse veje drevesa"y". Tako celotno drevo celotnega sistema vsebuje 11 vej. Vsaka veja predstavlja eno rešitev izvirnega sistema enačb. To pomeni, da ima celoten sistem 11 rešitev.
Odgovor: 11.
Primer 2. Koliko različnih rešitev ima sistem enačb?
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1
(X1 ≡ X10) = 0
kjer so x1, x2, …, x10 logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.
rešitev: Poenostavimo sistem. Sestavimo tabelo resnic za del prve enačbe:
X1 ∧ X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Bodite pozorni na zadnji stolpec, ujema se z rezultatom akcije X1 ≡ X10.
X1 ≡ X10 |
Po poenostavitvi dobimo:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Razmislite o zadnji enačbi:(X1 ≡ X10) = 0, tj. x1 ne sme sovpadati z x10. Da je prva enačba enaka 1, mora biti enakost resnična(X1 ≡ X2)=1, tj. x1 se mora ujemati z x2.
Zgradimo drevo rešitev za prvo enačbo:
Razmislite o drugi enačbi: za x10=1 in za x2=0 oklepajmora biti enako 1 (tj. x2 sovpada z x3); za x10=0 in za x2=1 oklepaj(X2 ≡ X10)=0, kar pomeni oklepaj (X2 ≡ X3) mora biti enako 1 (tj. x2 sovpada z x3):
S tem načinom razmišljanja zgradimo drevo odločitev za vse enačbe:
Tako ima sistem enačb le 2 rešitvi.
Odgovor: 2.
Primer 3.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
rešitev:
Zgradimo drevo rešitev za 1. enačbo:
Razmislite o drugi enačbi:
- Ko je x1=0 : drugi in tretji oklepaj bosta enaka 0; da je prvi oklepaj enak 1, y1=1, z1=1 (tj. v tem primeru - 1 rešitev)
- Ko je x1=1 : prvi oklepaj bo enak 0; drugo oz tretji oklepaj mora biti enak 1; drugi oklepaj bo enak 1, ko je y1=0 in z1=1; tretji oklepaj bo enak 1, ko je y1=1 in z1=0 (tj. v tem primeru - 2 rešitvi).
Podobno velja za preostale enačbe. Zabeležimo nastalo število rešitev za vsako vozlišče drevesa:
Če želite izvedeti število rešitev za vsako vejo, pomnožite dobljena števila posebej za vsako vejo (od leve proti desni).
1 veja: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 rešitev
Veja 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 rešitvi
3. veja: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 rešitve
4. veja: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 rešitev
5. veja: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 rešitev
Seštejmo dobljena števila: skupaj je 31 rešitev.
Odgovor: 31.
3. Naravni prirast števila korenin
V nekaterih sistemih je število korenov naslednje enačbe odvisno od števila korenov prejšnje enačbe.
Primer 1. Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Poenostavimo prva enačba:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Nato bo sistem dobil obliko:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
itd.
Vsaka naslednja enačba ima 2 korena več kot prejšnja.
4 enačba ima 12 korenin;
Enačba 5 ima 14 korenin
Enačba 8 ima 20 korenin.
Odgovor: 20 korenin.
Včasih število korenin raste po Fibonaccijevem zakonu.
Reševanje sistema logičnih enačb zahteva kreativen pristop.
Reševanje sistemov logičnih enačb s spreminjanjem spremenljivk
Metoda substitucije spremenljivk se uporablja, če so nekatere spremenljivke vključene v enačbe samo v obliki določenega izraza in nič drugega. Nato lahko ta izraz označimo z novo spremenljivko.
Primer 1.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, x6, x7, x8 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk x1, x2, x3, x4, x5, x6, x7, x8, za katere je izpolnjen ta sistem enakosti. Kot odgovor morate navesti število takih nizov.
rešitev:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Nato lahko sistem zapišemo v obliki ene enačbe:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunkcija je 1 (true), ko ima vsak operand vrednost 1. To je vsaka od implikacij mora biti resnična in to velja za vse vrednosti razen (1 → 0). Tisti. v tabeli vrednosti spremenljivk y1, y2, y3, y4 ena ne sme biti levo od ničle:
Tisti. pogoji so izpolnjeni za 5 nizov y1-y4.
Ker y1 = x1 → x2, potem je vrednost y1 = 0 dosežena na enem nizu x1, x2: (1, 0), vrednost y1 = 1 pa na treh nizih x1, x2: (0,0) , (0 ,1), (1.1). Enako za y2, y3, y4.
Ker je vsak niz (x1,x2) za spremenljivko y1 združen z vsakim nizom (x3,x4) za spremenljivko y2 itd., se števila nizov spremenljivk x pomnožijo:
|
Število nizov na x1…x8 |
||||
Seštejmo število nizov: 1 + 3 + 9 + 27 + 81 = 121.
odgovor: 121
Primer 2.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, ... x9, y1, y2, ... y9 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
V odgovor ni potrebno naštejte vse različne nize vrednosti spremenljivk x1, x2, ... x9, y1, y2, ... y9, za katere je izpolnjen dani sistem enačb. Kot odgovor morate navesti število takih nizov.
rešitev:
Spremenimo spremenljivke:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Sistem lahko zapišemo kot eno samo enačbo:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Enakovrednost velja samo, če sta oba operanda enaka. Obstajata dva niza rešitev te enačbe:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Ker zi = (xi ≡ yi), potem vrednost zi = 0 ustreza dvema nizoma (xi,yi): (0,1) in (1,0), vrednost zi = 1 pa dvema nizoma (xi,yi ): (0 ,0) in (1,1).
Potem prvi niz z1, z2,…, z9 ustreza 2 9 nizom (x1,y1), (x2,y2),…, (x9,y9).
Enako število ustreza drugemu nizu z1, z2,…, z9. Potem je skupaj 2 9 + 2 9 = 1024 nizov.
odgovor: 1024
Reševanje sistemov logičnih enačb z metodo vizualnega določanja rekurzije.
Ta metoda se uporablja, če je sistem enačb precej preprost in je vrstni red povečevanja števila nizov pri dodajanju spremenljivk očiten.
Primer 3.
Koliko različnih rešitev ima sistem enačb?
¬x9 ∨ x10 = 1,
kjer so x1, x2, … x10 logične spremenljivke?
Odgovoru ni treba navesti vseh različnih nizov vrednosti x1, x2, ... x10, za katere je ta sistem enakosti izpolnjen. Kot odgovor morate navesti število takih nizov.
rešitev:
Rešimo prvo enačbo. Disjunkcija je enaka 1, če je vsaj eden od njenih operandov enak 1. To je rešitve so sklopi:
Za x1=0 obstajata dve vrednosti x2 (0 in 1), za x1=1 pa samo ena vrednost x2 (1), tako da je množica (x1,x2) rešitev enačbe . Skupaj so 3 kompleti.
Dodajmo spremenljivko x3 in razmislimo o drugi enačbi. Podobno je prvemu, kar pomeni, da za x2=0 obstajata dve vrednosti x3 (0 in 1), za x2=1 pa samo ena vrednost x3 (1), tako da je množica (x2 ,x3) je rešitev enačbe. Skupaj so 4 kompleti.
Preprosto je videti, da se pri dodajanju druge spremenljivke doda en niz. Tisti. rekurzivna formula za število nizov (i+1) spremenljivk:
N i +1 = N i + 1. Potem za deset spremenljivk dobimo 11 nizov.
odgovor: 11
Reševanje sistemov logičnih enačb različnih vrst
Primer 4.
Koliko različnih nizov vrednosti logičnih spremenljivk x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 obstaja, ki izpolnjujejo vse spodaj navedene pogoje ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
V odgovor ni potrebno naštejte vse različne nize vrednosti spremenljivk x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, za katere je ta sistem enakosti izpolnjen.
Kot odgovor morate navesti število takih nizov.
rešitev:
Upoštevajte, da so tri enačbe sistema enake na različnih neodvisnih nizih spremenljivk.
Poglejmo prvo enačbo. Konjunkcija je resnična (enaka 1) le, če so vsi njeni operandi resnični (enaki 1). Implikacija je 1 za vse tuple razen (1,0). To pomeni, da bodo rešitve prve enačbe naslednje množice x1, x2, x3, x4, v katerih 1 ni levo od 0 (5 skupin):
Podobno bosta rešitvi druge in tretje enačbe popolnoma enaki množici y1,…,y4 in z1,…, z4.
Zdaj pa analizirajmo četrto enačbo sistema: x 4 ∧ y 4 ∧ z 4 = 0. Rešitev bodo vse množice x4, y4, z4, v katerih je vsaj ena od spremenljivk enaka 0.
Tisti. za x4 = 0 so primerne vse možne množice (y4, z4), za x4 = 1 pa so primerne množice (y4, z4), v katerih je vsaj ena ničla: (0, 0), (0,1 ), (1, 0).
|
Število kompletov |
||||
Skupno število nizov je 25 + 4*9 = 25 + 36 = 61.
odgovor: 61
Reševanje sistemov logičnih enačb s konstruiranjem rekurentnih formul
Metoda konstruiranja ponavljajočih se formul se uporablja pri reševanju kompleksnih sistemov, v katerih vrstni red povečevanja števila nizov ni očiten, konstrukcija drevesa pa je nemogoča zaradi volumnov.
Primer 5.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, ... x7, y1, y2, ... y7 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk x1, x2, ..., x7, y1, y2, ..., y7, za katere je izpolnjen ta sistem enakosti. Kot odgovor morate navesti število takih nizov.
rešitev:
Upoštevajte, da je prvih šest enačb sistema enakih in se razlikujejo le v nizu spremenljivk. Poglejmo prvo enačbo. Njegova rešitev bodo naslednji nizi spremenljivk:
Označimo:
število tupl (0,0) na spremenljivkah (x1,y1) do A 1,
število tuplov (0,1) na spremenljivkah (x1,y1) do B 1,
število tuplov (1,0) na spremenljivkah (x1,y1) do C 1,
število tupl (1,1) na spremenljivkah (x1,y1) do D 1 .
število tuplov (0,0) na spremenljivkah (x2,y2) do A 2,
število tulp (0,1) na spremenljivkah (x2,y2) do B 2,
število tuplov (1,0) na spremenljivkah (x2,y2) do C 2,
število tork (1,1) na spremenljivkah (x2,y2) do D 2 .
Iz odločitvenega drevesa to vidimo
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Upoštevajte, da je množica (0,0) spremenljivk (x2,y2) pridobljena iz množic (0,1), (1,0) in (1,1) spremenljivk (x1,y1). Tisti. A 2 =B 1 +C 1 +D 1.
Množico (0,1) na spremenljivkah (x2,y2) dobimo iz množic (0,1), (1,0) in (1,1) na spremenljivkah (x1,y1). Tisti. B 2 =B 1 +C 1 +D 1.
Če trdimo podobno, opazimo, da je C 2 =B 1 +C 1 +D 1. D2 = D1.
Tako dobimo ponavljajoče se formule:
A i+1 = B i + C i + D i
B i+1 = B i + C i + D i
C i+1 = B i + C i + D i
D i+1 = A i +B i + C i + D i
Naredimo mizo
| Kompleti | Imenovanje. | Formula |
Število kompletov |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Zadnjo enačbo (x7 ∨ y7) = 1 izpolnjujejo vse množice razen tistih, v katerih je x7=0 in y7=0. V naši tabeli je število takih nizov A 7.
Potem je skupno število nizov B 7 + C 7 + D 7 = 127+127+1 = 255
odgovor: 255
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, ima naša logična enačba 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.
Tema lekcije: Reševanje logičnih enačb
Izobraževalni – preučevanje metod reševanja logičnih enačb, razvijanje veščin reševanja logičnih enačb in sestavljanja logičnega izraza z uporabo tabele resnic;Razvojni - ustvariti pogoje za razvoj kognitivni interes učenci, spodbujajo razvoj spomina, pozornosti, logično razmišljanje;
Poučna : spodbujati sposobnost poslušanja mnenj drugih, negovanje volje in vztrajnosti za doseganje končni rezultati.
Vrsta lekcije: kombinirani pouk
Oprema: računalnik, multimedijski projektor, predstavitev 6.
Med poukom
Ponavljanje in obnavljanje osnovnega znanja. Pregled Domača naloga(10 minut)
V prejšnjih urah smo se seznanili z osnovnimi zakoni logične algebre in se naučili uporabljati te zakone za poenostavljanje logičnih izrazov.
Preverimo domačo nalogo o poenostavljanju logičnih izrazov:
1. Katera od naslednjih besed izpolnjuje logični pogoj:
(soglasnik prve črke→ soglasnik druge črke)٨ (samoglasnik zadnje črke → samoglasnik predzadnje črke)? Če je takih besed več, navedite najmanjšo izmed njih.
1) ANNA 2) MARIJA 3) OLEG 4) STEPAN
Vstavimo naslednji zapis:
A – soglasnik prve črke
B – soglasnik druge črke
S – zadnji samoglasnik
D – predzadnji samoglasnik
Naredimo izraz:
Naredimo tabelo:
2. Označite, kateri logični izraz je enakovreden izrazu
Poenostavimo snemanje izvirnega izraza in predlaganih možnosti:
3. Podan je fragment resničnostne tabele izraza F:
Kateri izraz se ujema s F?
Določimo vrednosti teh izrazov za podane vrednosti argumentov:
Uvod v temo lekcije, predstavitev novega gradiva (30 minut)
Še naprej preučujemo osnove logike in tema naše današnje lekcije je "Reševanje logičnih enačb." Po študiju te teme se boste naučili osnovnih načinov reševanja logičnih enačb, pridobili spretnosti za reševanje teh enačb z uporabo jezika logične algebre in sposobnost sestavljanja logičnega izraza z uporabo tabele resnic.
1. Rešite logično enačbo
(¬K M) → (¬L M N) =0
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.
rešitev:
Preoblikujemo izraz(¬K M) → (¬L M N)
Izraz je napačen, če sta oba izraza napačna. Drugi člen je enak 0, če je M =0, N =0, L =1. V prvem členu je K = 0, ker je M = 0 in 
.
Odgovor: 0100
2. Koliko rešitev ima enačba (pri odgovoru navedite le število)?
Rešitev: transformirajte izraz
(A +B )*(C +D )=1
A + B = 1 in C + D = 1
2. način: sestavljanje tabele resnic
3 način: konstrukcija SDNF - popolna disjunktivna normalna oblika za funkcijo - disjunkcija popolnih regularnih elementarnih konjunkcij.Preoblikujemo prvotni izraz, odpremo oklepaje, da dobimo disjunkcijo veznikov:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Dopolnimo veznike do popolnih veznikov (zmnožek vseh argumentov), odpremo oklepaje:
Upoštevajmo enake veznike:
Kot rezultat dobimo SDNF, ki vsebuje 9 konjunkcij. Zato ima tabela resnic za to funkcijo vrednost 1 v 9 vrsticah 2 4 =16 nizov vrednosti spremenljivk.
3. Koliko rešitev ima enačba (pri odgovoru navedite le število)?
Poenostavimo izraz:
,
3 način: izgradnja SDNF
Upoštevajmo enake veznike:
Kot rezultat dobimo SDNF, ki vsebuje 5 konjunkcij. Zato ima tabela resnic za to funkcijo vrednost 1 na 5 vrstic 2 4 =16 nizov vrednosti spremenljivk.
Sestavljanje logičnega izraza z uporabo tabele resnic:
za vsako vrstico tabele resnic, ki vsebuje 1, sestavimo produkt argumentov, pri čemer so spremenljivke enake 0 vključene v produkt z negacijo, spremenljivke enake 1 pa brez negacije. Želeni izraz F bo sestavljen iz vsote dobljenih produktov. Potem, če je mogoče, je treba ta izraz poenostaviti.
Primer: podana je resničnostna tabela izraza. Sestavite logični izraz.
rešitev:3. Domača naloga (5 minut)
Reši enačbo:
Koliko rešitev ima enačba (pri odgovoru navedite le število)?
S pomočjo podane tabele resnic sestavite logični izraz in
poenostavite.
