UDC 004.023
Semenovs Sergejs Maksimovičs
Vladivostokas Valsts ekonomikas un pakalpojumu universitāte Krievija. Vladivostoka
Par vienu veidu, kā atrisināt loģisko vienādojumu sistēmas
Aplūkota metode loģisko vienādojumu sistēmas atrisinājumu skaita noteikšanai. Metodes pamatā ir lēmumu koka konstruēšana un atkārtošanās attiecību noteikšana N līmenim. Izstrādātās metodes pielietošana nodrošina konstruktīvu pieeju vienotā valsts eksāmena B15 problēmas risināšanai.
Atslēgas vārdi un frāzes: loģisko vienādojumu sistēmas, lēmumu koks, atkārtošanās attiecības, B15, vienotais valsts eksāmens.
Praksē loģisko vienādojumu sistēmas ir noderīgas digitālo loģikas ierīču projektēšanā. Viena no datorzinātņu vienotā valsts eksāmena problēmām ir veltīta loģisko vienādojumu sistēmu risināšanai. Diemžēl dažādas zināmās metodes šīs problēmas risināšanai neļauj formulēt vienotu pieeju šīs problēmas risināšanai. Līdz ar to problēmas risināšana absolventiem sagādā lielas grūtības. Piedāvājam loģisko vienādojumu sistēmu risināšanas metodi, kas ļauj absolventam ievērot ļoti specifisku algoritmu. Šīs metodes ideja ir izklāstīta. Mēs pielietojām un attīstījām šo ideju (lēmumu koka konstruēšana), gandrīz neizmantojot patiesības tabulas visam kokam. Risinot dažādas problēmas, izrādījās, ka daudzu loģisko vienādojumu sistēmu risinājumu skaits pakļaujas atkārtošanās sakarībām, piemēram, Fibonači skaitļiem un citiem.
Loģisko vienādojumu sistēmas. Mēs pieturēsimies pie šādiem apzīmējumiem: disjunkcija (+), savienojums (), ekskluzīvs VAI (©), implikācija (->■), ekvivalence (=), noliegums (-■). Attēlos tumšais aplis apzīmē 1, bet gaišais aplis apzīmē 0. Fl ir risinājumu skaits ar X1 vienāds ar 1. Fo ir risinājumu skaits ar X1 vienāds ar 0. N ir mainīgo skaits sistēmā vienādojumu. F(N) = F1(N) + F0(N) - kopējais risinājumu skaits.
1. uzdevums. Jāatrod vienādojumu sistēmas atrisinājumu skaits (pārbaudījums Nr. 2)
Vispirms pieņemam, ka X1 = 1. Tad pirmajam vienādojumam X2 un X3 vērtības var būt jebkuras. Tādējādi koks tiek uzbūvēts līdz trešajam līmenim. Tālāk, ņemot vērā X2 un X, mēs izvēlamies X4. Pēc tam algoritms tiek atkārtots katram mainīgo trīskāršam (1. att.). Sākot no ceturtā līmeņa, var redzēt, ka Fl(4)=Fl(3)+Fl(1), Fl(5)=Fl(4)+Fl(2). Tādējādi mēs iegūstam Fl(N) = Fl(N-1) + Fl(N-3) (1)
Rīsi. 1. 1. uzdevums
No (1) vienādojuma izriet:
Bx(8) = 16 + 7 = 23,
Fl(9) = 23 + 11 = 34.
Lai izveidotu koku no nulles, varat izmantot apakšējo zaru no att. 1. Ir viegli redzēt, ka tas atkārto galveno koku, bet ar nobīdi pa labi par 2, tas ir
Kopā, F(9) = Fl(9) + Fo(9) = 34 + 16 = 50.
Veidojot lēmumu koku, varat vizuāli izveidot atkārtošanās attiecības, lai noteiktu risinājumu skaitu N līmenī.
Matemātiskās indukcijas princips saka: lai ir apgalvojumu secība Fl, F2, Fз un lai pirmais apgalvojums Fl ir patiess. Mēs varam pierādīt, ka FN derīgums nozīmē, ka FN+l ir patiess. Tad visi apgalvojumi šajā secībā ir patiesi.
Apskatīsim att. 2 1. uzdevumam.
k2 > 3 x 5 xb x7
Rīsi. 2. Lēmumu koka analīze
2. attēlā ir izcelti skaitļi, kuriem ir kopīga virsotne (mainīgo vērtību kombinācijas) sistēmas pirmajiem pieciem vienādojumiem. Katrs vienādojums ietver trīs mainīgos, tāpēc skaitļus veido trīs mainīgo (trīs koka līmeņu) vērtības. Lai identificētu figūras, būtu iespējams ieviest notāciju. Tomēr mēs rīkosimies šādi: katram skaitlim mēs piešķirsim apļu skaitu, kas to veido (mainīgās vērtības). Tad secībai iegūstam šādus vienādojumus:
4. 7, 4, 4, 1, 7
5. 7, 4, 4, 1, 7, 7, 4.
No 4. vienādojuma var redzēt, ka vienādojuma N skaitļi sastāv no vienādojuma N-1 skaitļiem un vienādojuma N-3 skaitļiem. Ir svarīgi, lai šāda veida vienādojumiem nebūtu un nevarētu būt citu skaitļu, tas ir, pāreja no viena vienādojuma uz otru tiek veikta, palielinot figūru skaitu no ierobežotas kopas saskaņā ar stingri noteiktiem noteikumiem. Šis fakts ir galvenais, lai ar indukcijas palīdzību apgalvotu, ka vienādojuma N+1 skaitļu kopa sastāvēs no vienādojuma N figūrām un vienādojuma N-2 skaitļiem.
Vēl viens veids, kā identificēt skaitļus, ir noteikt mainīgo vērtību skaitu noteiktā vienādojuma pēdējā līmenī, tas ir, jums ir jāpāriet no vienādojuma numura uz koka līmeņa numuru, jo mums ir jānosaka risinājumu skaits. vienādojumu sistēmai.Tad konstruētajam kokam iegūstam secību: 1, 2, 4 , 5, 7, 11, 16. Šai secībai der formula: FN = FN-1 + FN-3.
Saskaņā ar mūsu argumentāciju šī formula būs patiesa N+1 un indukcijas gadījumā jebkuram N.
Iepriekš minēto pierādīšanas metodi var izmantot jebkurai šāda veida sistēmai. Praksē pietiek ar N līmeņa atkārtošanās sakarības noteikšanu, jo tās pamatā ir ierobežots skaitļu kopums un to transformāciju metodes, pārejot no N līmenim atbilstoša vienādojuma uz N+1 līmenim atbilstošu vienādojumu.
2. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 4.16)
(X1 = X2) + (X1 = X3) = 1 (X2 = X3) + (X2 = X4) = 1 (X3 = X4) + (X3 = X5) = 1 (X4 = X5) + (X4 = X6) =1 (X5 = X6) + (X5 = X7) = 1
XI Х2 ХЗ >:1 Х5 Хб Х7
Rīsi. 3. 2. uzdevums
Lai iegūtu 2. uzdevuma atrisinājumu skaitu, bija iespējams neveidot pilnīgu lēmumu koku (3. att.), jo ir skaidrs, ka Fl(N) = N. Tāpat Fo(N) = N. Kopējais F( 7) = 7 + 7 = 14.
3. uzdevums. Jāatrod vienādojumu sistēmas atrisinājumu skaits (pārbaudījums Nr. 1)
(X1 ^ X2) ■ (X2 ^ X3) ■ (X3 ^ X4) ■ (X4 ^ X5) = 1
(Yl ^ Y2) ■ (Y2 ^ Yz) ■ (Yz ^ Y4) ■ (Y4 ^ Y5) = 1
(Yl ^ X1) ■ (Y2 ^ X2) ■ (Yz ^ X3) ■ (Y4 ^ X4) ■ (Y5 ^ X5) = 1
4. attēlā parādīti X un Y lēmumu koki un atbilstošās patiesības tabulas.
Rīsi. 4. 3. uzdevums
No pirmajiem diviem vienādojumiem, tā kā X un Y ir neatkarīgi, izriet, ka kopējais risinājumu skaits F(5) = 6 * 6 = 36. Lai ņemtu vērā trešo vienādojumu, katram mainīgajam Y ir nepieciešams aprēķiniet, cik kopu no tabulas X neapmierina vienādojumu. Implikācija ir Yi ^ Xi = 0, ja Yi = 1 un Xi = 0. Citiem vārdiem sakot, ja Yl = 1, trešo vienādojumu neapmierina visas X tabulas rindas, kur X1 = 0. Šādu rindu skaits ir 5. Ja Y2 = 1 šādas līnijas - 4 utt. Kopējais rindu skaits, kas neatbilst trešajam vienādojumam, ir 5 + 4 + 3 + 2 + 1 = 15.
Tādējādi kopējais iespējamo risinājumu skaits ir 36 - 15 = 21. 4. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 4.17.a)
(X1=X2) + (X1=X3)=(X2=X3)+(X2=X4)=(X4=X5)+(X4=X6)=(X5=X6)+(X5=X7)=(Xb) =X7) + (Xb = X8) = (X5=X6) = 0
Rīsi. 5. 4. uzdevums
Šim piemēram ir grūti noteikt galīgo formulu F(N), vieglāk ir izveidot lēmumu koku līdz galam (vai vismaz līdz X6). 5. attēlā parādīts konstruētais lēmumu koks. Rezultātā mēs iegūstam F(8) = Fl(8) + Fo(8) = 5 + 5 = 10.
5. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 4.17.b)
(X1 = X2) + (X1 = X3) = 1 (X2 = X3) + (X2 = X4) = 1 (X3 = X4) + (X3 = X5) = 1 (X4 = X5) + (X4 = X6) =1 (X5 = X6) + (X5 = X7) = 1 (X6 = X8) = 1
Šim piemēram, tāpat kā iepriekšējam, lēmumu koku ir vieglāk izveidot līdz galam (6. att.). Rezultātā mēs iegūstam F(8) = Fl(8) + Fo(8) = 7 + 7 = 14.
6. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai ([!]> 4.17.c)
(Х!8"Х2) + (Х2ЭХз) = 1 (Х2фХз) + (Хз = Х4) = 1 (Хз8"Х4) + (Х4 = Х5) = 1 (Х4©Х5) + (Х5 = Хб) = 1 (X5fXb) + (Xb = X7) = 1 (Xb©X7) + (X7 = X8) = 1 Lēmumu koks ir parādīts attēlā. 7.
XI X2 X3 X4 X5 X6 X7 X8 XI X2 X3 X4 X5 X6 X7 X8
Rīsi. 6. 5. uzdevums Zīm. 7. 6. uzdevums
Šai vienādojumu sistēmai nebija iespējams izveidot pilnīgu lēmumu koku, jo jau no trešā vai ceturtā soļa ir skaidrs, ka F1(N) = N. Ir viegli redzēt, ka Fo(N) var iegūt no koks, kas sākas otrajā līmenī no nulles. Tad Fo(N) = N. Tātad, F(8) = Fl(8) + Fo(8) = 8 + 8 = 16.
7. uzdevums. Jāatrod vienādojumu sistēmas atrisinājumu skaits
(X4EX5) + (X4 © X6) = 1 (X5 © Xb) + (X5 © X7) = 1
Ņemiet vērā, ka, ja X! = X2 = 1, tad pirmais vienādojums ir izpildīts Xз = 0. Vispirms izveidosim koku Xl = X2 = 1 (8. att.). Tad risinājumu skaits Fl(N) = Fll(N) + Flo(N).
XI X2 X3 X4 X5 X6 X7 X8
Rīsi. 8. 7. uzdevums
8. attēlā redzams, ka risinājumu skaits ir F11(N) = F11(N-1) + F11(N-2). Citiem vārdiem sakot, risinājumu skaitu raksturo Fibonači skaitļi. Otro koka zaru F10 var izlaist, jo tas ir iegūts no 3. att. 1, sākot no otrā līmeņa. Tad F10(N) = F11(N+1). Beidzot iegūstam, ka Fll(8) = 1з un Flo(8) = Fll(9) = 1з + 8 = 21. Tad Fl(8) = Fll(8) + Flo(8) = 1з + 21 = З4.
Lai iegūtu F0(N), arī nav nepieciešams veidot lēmumu koku, jo tas ir iegūts no att. 1 sākot no trešā līmeņa. Tad Fo(N) = Fll(N+2). No šejienes mēs iegūstam, ka Fo(8) = Fll(10) = Fll(9) + Fll(8) = 21 + 1з = з4. Tādējādi kopējais risinājumu skaits F(8) = F1(8) + F0(8) = з4 + з4 = 68.
8. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai ([z], 2. uzdevums)
(X1 + X2) ^ (X3 + X4) = 1 (X3 + X4) ^ (X5 + X6) = 1 (X5 + X6) ^ (X7 + X8) = 1 (X7 + X8) ^ (X9 + X10) = 1
Izdarīsim aizstāšanu (X1 + X2) = Yl utt. un mēs iegūstam vienādojumu sistēmu:
^ ^ Y2 = 1 Y2 ^ Yg = 1 Yg ^ Y4 = 1 Y4 ^ Y5 = 1
Šīs sistēmas lēmumu koks un patiesības tabula ir tieši tāda pati kā koks un tabula, kas parādīta attēlā. 4. Ņemot vērā aizstāšanu, mēs atzīmējam, ka izteiksme (X1 + X2) ir vienāda ar vienu no trim gadījumiem (izņemot opciju, kad abi mainīgie ir vienādi ar nulli).
Tā kā Y mainīgie ir neatkarīgi, tad patiesības tabulas pirmajai rindai, kas parādīta attēlā. 4, dažādu kombināciju skaits ir 35, otrajai rindai - 34 utt. Kopējais dažādu kombināciju skaits ir 35 + 34 + 33 + 32 + 31 + 30 = 364.
9. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 4. uzdevums)
(^ ^ b) ■ (-X ^ Xз) ■ № ^ X) ■ (-X ^ Кз) = 1 № ^ Y2) ■ (У1 ^ Yз) ■ (-Г1 ^ Y4) ■ (У1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1
Attiecībā uz X un Y mums ir šādi lēmumu koki
Rīsi. 9. 8. uzdevums
Ņemot vērā trešo vienādojumu, mēs iegūstam šādas četras kombināciju kopas:
A - C: 4 * 4 = 16 ((-1 £ + Y 1) ■ (-X + Y5) = (0 + 1) ■ (0 + 1) = 1) B - C: 4 * 4 = 16 ( (-X + Y 1) ■ (-X + Y5) = (1 + 1) ■ (1 + 1) = 1) A - D: = 0 (0 + 0) ■ (-X + Y5) = 0) B - D: 4 * 4 = 16 (1 + 0) ■ (1 + Y5) = 1) Kopā ir 48 risinājumu kopas.
10. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (^1 = b) + (Xз = X)) ■ = b) + -фз = X4)) =1 ((Xз = X4) + ( X5 = X6)) ■ ( -(X = X) + -(X = X6)) =1 ((X5 = X6) + ^7 = X«)) ■ (-(X = X6) + -(^7 = X8)) =1
((X7 = X8) + (X9 = Xlo)) ■ (-^7 = X8) + = Xlo)) =1 Veiksim aizstāšanu: (Xl = b) = Yl (Xз = X4) = Y2
(X5 = X) = Yz (X7 = X8) = Y4 (X9 = X10) = Y5
(Y^2) ■ (-b + ^)=1
(Y2+Yз) ■ Nr. + -Тз)=1
(Yz+Y4) ■ № + ^)=1
(Y4+Y5) ■ (^4 + ^)=1
10. attēlā parādīts lēmumu koks
U1 U2 UZ U4 U5
Rīsi. 10. 10. uzdevums
11. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 2. piemērs)
X1 + X2 = 1 -X2 + Xs = 1
11. attēlā parādīts lēmumu koks. Mēs aprobežojāmies ar četriem līmeņiem, nevis desmit, jo ir skaidrs, ka F1(N) = 1 un F0(N) = N. Tad P(L) = P1(L) + BoSY) = 1 + N. Mūsu gadījumā , P(10) = 1 + 10 = 11.
Rīsi. 11. 11. uzdevums
12. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (h piemērs)
(X1 = X2) + (X2 = X3) = 1
(X1 = X3) + (X3 = X4) (X1 = X4) + (X4 = X5) (X1 = X5) + (X5 = X6) (X1 = X6) + (X6 = X7) (X1 = X7) + (X7 = X8) (X1 = X) + (X8 = X9) (X1 = X9) + (X9 = X10) (X1 = X10) = 0
Rīsi. 12. 12.uzdevums
Konstruējot lēmumu koku no “1” (aprobežosimies ar pieciem līmeņiem), mēs atzīmējam, ka Fl(N) = N. Turklāt Xn vērtības sastāv no N-1 vērtībām “0” un viena vērtība “1”. Tomēr pēdējais vienādojums mūsu sistēmā aizliedz vērtību "1" X10. Tāpēc atrisinājumu skaits Fl(10) = 10 - 1. Ir viegli redzēt, ka lēmumu koks no “0” būs simetrisks (nuļļu vietā būs vieninieki). Tāpēc F0 = 10 - 1. Visbeidzot
F(N) = 2 x 9 = 18.
13. uzdevums. Jāatrod vienādojumu sistēmas atrisinājumu skaits (4. piemērs)
- (X1 = X2) + (X3 = X4) = 1
- (Xs = X4) + (X5 = X) = 1
- (X = X) + (X7 = X) = 1
- (X7 = X8) + (X9 = X10) = 1
Aizstāsim:
(X1 = X2) = Yl
(X5 = X) = Yз
(X7 = X8) = Y4
(X9 = X10) = Y5
Pārrakstīsim vienādojumu sistēmu, ņemot vērā aizstāšanu:
No 11. uzdevuma ir skaidrs, ka F(5) = 5 + 1 = 6. Patiesības tabula parādīta att. 13.
U1 U2 UZ U4 U5
Rīsi. 13. 13.uzdevums
Ņemot vērā aizstāšanu, mēs atzīmējam, ka izteiksme ^ = X2) ir vienāda ar vienu (vai nulli) divos gadījumos (kad mainīgo lielumu vērtības sakrīt). Ņemot vērā mainīgo neatkarību katrai tabulas rindai, secinām, ka risinājumu kopu skaits ir 25 = 32. Kopējais risinājumu kopu skaits ir 6 * 32 = 192.
14. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 1. uzdevums)
((X = b) ■ (Xз = X4)) + (4X1 = b) ■ -(X = X)) =0 ((Xз = X4) ■ (X5 = X6)) + (4X3 = X4) ■ - (X = X6)) =0
((X5 = X) ■ (X7 = X8)) + (-(X = X6) ■ 4X7 = X8)) =0 ((X7 = X8) ■ (X9 = X«,)) + (-(^7) = X8) ■ ^9 = Xlo)) =0 Veiksim nomaiņu:
b) = Yl (X = ^4) = Y2
(X5 = X6) = Yз ^ 7 = X8) = Y4 ^ 9 = Xlo) = Y5
Pārrakstīsim vienādojumu sistēmu, ņemot vērā aizstāšanu:
(UL) + (-U« ■ -U2)=0
(Y2 Yз) + (-У2 ■ -У3)=0 (У3-У4) + (-У3 ■ -У4)=0 (У4-У5) + (-У4 ■ -У5)=0
(U2 = Yz) = 0 (Uz = U4) = 0 (U4 = U5) = 0
14. attēlā parādīts lēmumu koks
U1 U2 UZ U4 U5
Rīsi. 14. 14. uzdevums
Ņemot vērā aizstāšanu, mēs atzīmējam, ka izteiksme (X1 = X2) ir vienāda ar vienu (vai nulli) divos gadījumos (kad mainīgo lielumu vērtības sakrīt). Ņemot vērā katra koka mainīgo neatkarību, iegūstam, ka risinājumu kopu skaits ir 25 = 32. Kopējais risinājumu komplektu skaits ir 64.
15. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 2. uzdevums)
(X4 X5) + (-X4 -X5) + (X4 = X) = 1
(X5 X) + (-X –X6) + (X5 = X7) = 1
(X X7) + (-X –X7) + (X = X8) = 1
(X7 X) + (-X7 –X8) + (X7 = X9) = 1
(X8 X9) + (-X -X9) + (X8 = X10) = 1
(X1 = X2) + (X1 = X3) = 1
(X = Xs) + (X2 = X4) = 1
(Xs = X4) + (Xs = X5) = 1
(X4 = X5) + (X4 = X) = 1
(X5 = X6) + (X5 = X7) = 1
(X = X7) + (X6 = X8) = 1
(X7 = X8) + (X7 = X9) = 1
(X = X9) + (X8 = X10) = 1
Bet šī sistēma atkārto sistēmu no 5. uzdevuma, tikai bez ierobežojuma nosacījuma un N = 10. Tad risinājumu skaits ir vienāds ar F(N) = F1(N) + F0(N) = N + N. = 10 mēs iegūstam F(N )= 20.
16. uzdevums. Jāatrod vienādojumu sistēmas atrisinājumu skaits (3. uzdevums)
(X1 X2) + (-X1 -X2) + (X1 = X3) = 1
(X2 Xs) + (-X –Xs) + (X2 = X4) = 1
(Xs X4) + (-Xs -X4) + (Xs = X5) = 1
(X4 X5) + (-X -X5) + (X4 = Xb) = 1
(X5 Xb) + (-X -Xb) + (X5 = X7) = 1
(Xb X7) + (-Xb -X7) + (Xb = X8) = 1
(X7 X8) + (-X7 –X8) + (X7 = X9) = 1
(X8 X9) + (-X8 –X9) + (X8 = X10) = 0
Šo vienādojumu sistēmu, tāpat kā iepriekšējā uzdevumā, var pārrakstīt šādi:
(XI = X2) + (XI = Xs) = 1 (X = Xs) + (X2 = X) = 1 (Xs = X) + (Xs = X5) = 1 (X = X5) + (X4 = Xb) = 1 (X5 = Xb) + (X5 = X7) = 1 (Xb = X7) + (Xb = X8) = 1 (X = X8) + (X7 = X9) = 1 (X = X9) + (X8 = Xxc) = 0
No pēdējā vienādojuma ir viegli pārbaudīt, vai pēc N = 8 risinājumu skaits pārstāj pieaugt. Tad F(10) = F(8) = 8 + 8 = 16.
17. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 4. uzdevums)
(X1 X2) + (-X1-X2) + (X2 Xs) + (-X2 -Xs) = 1
(X2 Xs) + (-X2 Xs) + (Xs X) + (-Xs ■ -X4) = 1
(Хз Х) + (-Хз -Х4) + (Х4 Х5) + (-Х4 -Х5) = 1
(X4 X) + (-X -X5) + (X5 Xb) + (-X5 -Xb) = 1
(X5 Xb) + (-X -Xb) + (Xb X7) + (-Xb ■ -X7) = 1
(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 -X8) = 1
(X7 X) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1
(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 1
Ņemiet vērā, ka vienādojumu sistēmu var pārrakstīt šādi:
(X = X2) + (X = Xs) = 1 (X = Xs) + (X = X) = 1 (Xs = X4) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X5 = Xb) + (Xb = X7) = 1
(Xb = X7) + (X7 = X) = 1 (X7 = X8) + (X8 = X9) = 1 (Xb = X 9) + (X9 = X10) = 1
15. attēlā koks ir uzbūvēts līdz piektajam līmenim un ir skaidri redzams, ka risinājumu skaits ir aprakstīts ar Fibonači skaitļiem, tas ir, Fl(N) = Fl(N-1) + Fl(N-2). Tad Fl(10) = 89. Ir viegli pārbaudīt, vai F0(N) koks būs simetrisks. Tāpēc Fo(10) = 89. B(10) = p1(10) + Po(10) = 89 + 89 =178.
Rīsi. 15. 17. uzdevums
18. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 5. uzdevums)
(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 ■ -Xs) = 1
(Х2 Хз) + (-Х -Хз) + (Хз Х4) + (-Хз -Х4) = 1
(Хз Х4) + (-Хз -Х4) + (Х4 Х5) + (-Х4 ■ -Х5) = 1
(X4 X5) + (-X4 -X5) + (X Xb) + (-X5 ■ -Xb) = 1
(X5 Xb) + (-X5 -Xb) + (Xb X7) + (-Xb ■ -X7) = 1
(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 ■ -X8) = 1
(X7 X8) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1
(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 0
Ņemiet vērā, ka vienādojumu sistēmu var pārrakstīt šādi:
(X = X2) + (X2 = X3) = 1 (X2 = X3) + (X3 = X4) = 1
(Xs = X) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X = Xb) + (Xb = X7) = 1 (Xb = X7) + (X7 = X8) = 1 (X7 = X8) + (X8 = X9) = 1 (X8 = X 9) + (X = X10) = 0
18. uzdevums ir līdzīgs 17. uzdevumam, tomēr pēdējais vienādojums noved pie tā, ka, sākot no septītā līmeņa, risinājumu skaits nepalielinās. Rezultātā F(10) = Fl(10) + Fo(10) = Fl(7) + Fo(7) = 21 + 21 = 42.
19. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, uzdevums b)
(X = X2) + (X = X10) = 1 (X = X3) + (X2 = X10) = 1 (X3 = X4) + (X = X10) = 1 (X = X5) + (X = X10) = 1 (X = Xb) + (X5 = X10) = 1 (Xb = X7) + (Xb = X10) = 1 (X7 = X) + (X = X10) = 1 (X8 = X9) + (X = X10) = 1 (X9 = X10) + (X9 = X10) = 1 (X = X10) = 0
- - - -*- - - -*-O
Rīsi. 1b. 19. uzdevums
Lēmumu koki F1(N) un F0(N) iegūšanai ir parādīti attēlā. 1b. Tomēr vienādojumu (X9 = X10) = 1 nevar izpildīt. Tāpēc vienādojumu sistēmai nav risinājumu.
20. uzdevums. Jāatrod atrisinājumu skaits vienādojumu sistēmai (, 7. uzdevums)
(X ^ X2) + (X ^ Xs) = 1 (X2 ^ Xs) + (X2 * X4) = 1 (Xs ^ X4) + (Xs ^ X5) = 1 (X ^ X5) + (X4 ^ Xb) = 1 (X5 ^ Xb) + (X5 ^ X7) = 1 (Xb ^ X7) + (Xb ^ X8) = 1
(X7 ^ Xs) + (X7 ^ X9) = 1 (Xs ^ X9) + (Xs ^ X10) = 1
17. attēlā parādīts lēmumu koks no “1”.
Rīsi. 17. 20. uzdevums Att. 18. 20.uzdevums
Desmit līmeņu vietā mēs aprobežojāmies ar pieciem, jo uzdevums ir līdzīgs 17. uzdevumam. Taču no “0” koks izskatīsies savādāk (18. att.).
Ņemiet vērā, ka F0(N) = Fx(N+1) - 1. Tad Fx(10) = 89 un F0(10) = Fx(11) - 1 = 144 - 1. Kopā, F(10) = F1 ( 10) + F0(10) = 89 + 143 = 232.
Noslēgumā mēs piedāvājam BASIC VBA programmu, ar kuras palīdzību jūs varat atrisināt loģisko vienādojumu sistēmas. Programma var būt nepieciešama, veidojot jaunas vienādojumu sistēmas. 19. attēlā parādīta programma, kas izmantota, lai atrisinātu vienādojumu sistēmu no 7. uzdevuma.
Programmā, kas parādīta attēlā. 19, masīvs m un mainīgais c satur mainīgo vērtības, kas apmierina 7. uzdevuma vienādojumu sistēmu. Programma rada atbildi 68. Programma izmanto faktu, ka dažādu vērtību kopu skaits n loģiskie mainīgie ir 2n. Lai iegūtu visas kopas, jums ir jāveido cilpa no 0 līdz 2n-1. Katrā solī cilpas mainīgais tiek pārveidots par bināro sistēmu, rezultāts tiek ierakstīts m masīvā un pēc tam tiek pārbaudīti nosacījumi no vienādojumu sistēmas. Lai atrisinātu citu vienādojumu sistēmu, pietiek ar masīva dimensijas m mainīšanu, mainīgā lieluma vg vērtības maiņu (vienādu ar dimensiju) un testa nosacījumu maiņu.
Dim m(S) kā vesels skaitlis, k kā vesels skaitlis, j. Kā vesels skaitlis. _ j Kā vesels skaitlis. N Kā vesels skaitlis, vg kā vesels skaitlis Dim ar As String vg=S j-0
No 1 līdz 2 ■""■ vg "Cilpa caur ^ no 1 līdz 2n. kur n=,.g Ja k = 1 uz vg
N = ).- 1: Binārais e pr e c put e n nesākas no nulles k= 1
Do "^Tiils N > 0 "Tulkošanas e binārā sistēma m(k) = N Mod 2 K = N ■ 2 k=k+ ! Cilpa
Ifim(l) O m(2) Vai m(l)0- ni(3)) Un_ "vienādojuma nosacījumi (m(2) c= "" "Mainīgais c katrā solī saturēs sistēmas risinājumu Ja k= 1 Tad vg с = с - Foimat(m(k)j Nākamais k j-j-1 Beigas Ja Nākamais I. Ms^Eox i "Risinājumu skaits VvVvVlVvVvv- -1 i Rīsi. 19. Programma 7. uzdevumam 1. Krilovs S.S. LIETOŠANA 2014. Informātika. Tematiskie testa uzdevumi / S.S. Krilovs, D.M. Ušakovs. - M.: Izdevniecība "Eksāmens". - 245 s. 2. K.Yu vietne. Poļakova. Piekļuves režīms: http://kpolyakov.namd.-ru/download/inf-2011-14.pdf 3. Uzņēmuma “1C” metodiskais sertificēts kurss “Sagatavošanās vienotajam valsts eksāmenam datorzinātnēs. Modulis 1". - M.: Izdevniecība "1C". - 218 lpp. 4. Sekmīgi nokārtot vienoto valsts eksāmenu datorzinātnēs. Piekļuves režīms: http://infoegehelp.ru/index.php?Itemid=77&id=103&option=com_con- Kā atrisināt dažus uzdevumus datorzinātņu eksāmena A un B sadaļā Nodarbība #3. Loģika. Loģiskās funkcijas. Vienādojumu risināšana Liela daļa vienotā valsts eksāmena uzdevumu ir veltīti priekšlikuma loģikai. Lai atrisinātu lielāko daļu no tiem, pietiek zināt propozicionālās loģikas pamatlikumus, zināšanas par viena un divu mainīgo loģisko funkciju patiesuma tabulām. Es došu propozicionālās loģikas pamatlikumus. Loģisko funkciju attēlojums Jebkuru n mainīgo loģisko funkciju - F(x 1, x 2, ... x n) var norādīt ar patiesības tabulu. Šādā tabulā ir 2n mainīgo kopas, katrai no kurām ir norādīta šīs kopas funkcijas vērtība. Šī metode ir laba, ja mainīgo lielumu skaits ir salīdzinoši mazs. Jau n > 5 attēlojums kļūst slikti redzams. Vēl viens veids ir definēt funkciju pēc kādas formulas, izmantojot zināmas diezgan vienkāršas funkcijas. Funkciju sistēmu (f 1, f 2, ... f k) sauc par pilnīgu, ja jebkuru loģisku funkciju var izteikt ar formulu, kurā ir tikai funkcijas f i. Funkciju sistēma (¬, ˄, ˅) ir pabeigta. 9. un 10. likumi ir piemēri, kas parāda, kā implikācija un identitāte tiek izteikta ar noliegumu, konjunkciju un disjunkciju. Faktiski divu funkciju sistēma – noliegums un konjunkcija vai noliegums un disjunkcija – arī ir pilnīga. No De Morgana likumiem izriet idejas, kas ļauj izteikt konjunkciju ar noliegumu un disjunkciju un attiecīgi izteikt disjunkciju ar noliegumu un konjunkciju: (a ˅ b) ≡ ¬(¬a ˄ ¬b) Paradoksāli, bet sistēma, kas sastāv tikai no vienas funkcijas, ir pabeigta. Ir divas bināras funkcijas - antikonjunkcija un antidisjunkcija, ko sauc par Pīrsa bultiņu un Šēfera gājienu, kas attēlo dobu sistēmu. Programmēšanas valodu pamatfunkcijas parasti ietver identitāti, noliegšanu, konjunkciju un disjunkciju. Vienotā valsts eksāmena problēmās līdztekus šīm funkcijām bieži tiek atrasta nozīme. Apskatīsim dažas vienkāršas problēmas, kas saistītas ar loģiskām funkcijām. 15. uzdevums: Ir dots patiesības tabulas fragments. Kura no trim dotajām funkcijām atbilst šim fragmentam? Funkcijas numurs 3. Lai atrisinātu problēmu, ir jāzina pamatfunkciju patiesības tabulas un jāatceras darbību prioritātes. Atgādināšu, ka konjunkcijai (loģiskajai reizināšanai) ir augstāka prioritāte un tā tiek izpildīta agrāk nekā disjunkcijai (loģiskā saskaitīšana). Veicot aprēķinus, var viegli pamanīt, ka funkcijām ar skaitļiem 1 un 2 trešajā kopā ir vērtība 1 un šī iemesla dēļ tās neatbilst fragmentam. 16. uzdevums: Kurš no dotajiem skaitļiem atbilst nosacījumam: (cipari, sākot no nozīmīgākā cipara, ir dilstošā secībā) → (skaitlis - pāra) ˄ (zems cipars - pāra) ˄ (augstais cipars - nepāra) Ja ir vairāki šādi skaitļi, norādiet lielāko. Nosacījumu apmierina cipars 4. Pirmie divi skaitļi neatbilst nosacījumam, jo zemākais cipars ir nepāra. Nosacījumu savienojums ir nepatiess, ja viens no savienojuma nosacījumiem ir nepatiess. Trešajam skaitlim nav izpildīts nosacījums par augstāko ciparu. Ceturtajam numuram ir izpildīti nosacījumi, kas izvirzīti skaitļa mazajam un augstajam ciparam. Arī saikļa pirmais termins ir patiess, jo implikācija ir patiesa, ja tās premisa ir nepatiesa, kā tas ir šajā gadījumā. 17. problēma: divi liecinieki sniedza šādas liecības: Pirmais liecinieks: ja A ir vainīgs, tad B ir vēl vairāk vainīgs, un C ir nevainīgs. Otrais liecinieks: Divi ir vainīgi. Un viens no atlikušajiem noteikti ir vainīgs un vainīgs, bet es nevaru pateikt, kurš tieši. Kādus secinājumus par A, B un C vainu var izdarīt no liecībām? Atbilde: No liecības izriet, ka A un B ir vainīgi, bet C ir nevainīgs. Risinājums: Protams, atbildi var sniegt, balstoties uz veselo saprātu. Bet paskatīsimies, kā to var izdarīt stingri un formāli. Pirmā lieta, kas jādara, ir formalizēt paziņojumus. Ieviesīsim trīs loģiskos mainīgos - A, B un C, katram no kuriem ir vērtība true (1), ja vainīgs ir attiecīgais aizdomās turamais. Tad pirmā liecinieka liecība tiek sniegta pēc formulas: A → (B ˄ ¬C) Otrā liecinieka liecība tiek sniegta pēc formulas: A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C)) Tiek pieņemts, ka abu liecinieku liecības ir patiesas un atspoguļo atbilstošo formulu savienojumu. Izveidosim patiesības tabulu šiem lasījumiem: Kopsavilkuma pierādījumi ir patiesi tikai vienā gadījumā, kas noved pie skaidras atbildes - A un B ir vainīgi, un C ir nevainīgs. No šīs tabulas analīzes arī izriet, ka otrā liecinieka liecībai ir informatīvāka nozīme. No viņa liecības patiesuma izriet tikai divi iespējamie varianti - A un B ir vainīgi, un C ir nevainīgi, vai A un C ir vainīgi, un B ir nevainīgi. Pirmā liecinieka liecība ir mazāk informatīva - ir 5 dažādi varianti, kas atbilst viņa liecībām. Kopā abu liecinieku liecības sniedz skaidru atbildi par aizdomās turamo vainu. Loģiskie vienādojumi un vienādojumu sistēmas Pieņemsim, ka F(x 1, x 2, …x n) ir n mainīgo loģiskā funkcija. Loģiskais vienādojums izskatās šādi: F(x 1, x 2, … x n) = C, Konstantei C ir vērtība 1 vai 0. Loģiskam vienādojumam var būt no 0 līdz 2 n dažādu risinājumu. Ja C ir vienāds ar 1, tad risinājumi ir visas tās mainīgo kopas no patiesības tabulas, kurās funkcija F iegūst vērtību true (1). Atlikušās kopas ir vienādojuma atrisinājumi ar C vienādu ar nulli. Jūs vienmēr varat ņemt vērā tikai formas vienādojumus: F(x 1 , x 2 , …x n) = 1 Patiešām, dosim vienādojumu: F(x 1, x 2, … x n) = 0 Šajā gadījumā mēs varam pāriet uz līdzvērtīgu vienādojumu: ¬F(x 1 , x 2 , …x n) = 1 Apsveriet k loģisko vienādojumu sistēmu: F1 (x 1, x 2, …x n) = 1 F2 (x 1, x 2, …x n) = 1 F k (x 1 , x 2 , …x n) = 1 Sistēmas risinājums ir mainīgo lielumu kopa, uz kuras ir izpildīti visi sistēmas vienādojumi. Runājot par loģiskajām funkcijām, lai iegūtu loģisko vienādojumu sistēmas risinājumu, jāatrod kopa, uz kuras ir patiesa loģiskā funkcija Ф, kas attēlo sākotnējo funkciju F konjunkciju: Ф = F 1 ˄ F 2 ˄ … F k Ja mainīgo skaits ir mazs, piemēram, mazāks par 5, tad nav grūti izveidot patiesības tabulu funkcijai Ф, kas ļauj pateikt, cik sistēmai ir risinājumu un kādas ir kopas, kas dod risinājumus. Dažos Vienotā valsts pārbaudījuma uzdevumos par loģisko vienādojumu sistēmas risinājumu meklēšanu mainīgo skaits sasniedz 10. Tad patiesības tabulas izveidošana kļūst par gandrīz neatrisināmu uzdevumu. Problēmas risināšanai nepieciešama cita pieeja. Patvaļīgai vienādojumu sistēmai nav citas vispārīgas metodes, izņemot uzskaitīšanu, kas ļautu atrisināt šādas problēmas. Eksāmenā piedāvātajās problēmās risinājums parasti balstās uz vienādojumu sistēmas specifikas ņemšanu vērā. Es atkārtoju, ka, izņemot visu mainīgo lielumu kopas opciju izmēģināšanu, nav vispārēja veida, kā problēmu atrisināt. Risinājums jābūvē, balstoties uz sistēmas specifiku. Bieži vien ir lietderīgi veikt vienādojumu sistēmas iepriekšēju vienkāršošanu, izmantojot zināmus loģikas likumus. Vēl viens noderīgs paņēmiens šīs problēmas risināšanai ir šāds. Mūs neinteresē visas kopas, bet tikai tās, kurās funkcijai Ф ir vērtība 1. Tā vietā, lai izveidotu pilnīgu patiesības tabulu, mēs izveidosim tās analogu - bināro lēmumu koku. Katrs šī koka zars atbilst vienam atrisinājumam un norāda kopu, uz kuras funkcijai Ф ir vērtība 1. Zaru skaits lēmumu kokā sakrīt ar vienādojumu sistēmas atrisinājumu skaitu. Es paskaidrošu, kas ir binārais lēmumu koks un kā tas tiek veidots, izmantojot vairāku problēmu piemērus. 18. problēma Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas apmierina divu vienādojumu sistēmu? Atbilde: Sistēmai ir 36 dažādi risinājumi. Risinājums: vienādojumu sistēma ietver divus vienādojumus. Atradīsim atrisinājumu skaitu pirmajam vienādojumam atkarībā no 5 mainīgajiem - x 1, x 2, ...x 5. Pirmo vienādojumu savukārt var uzskatīt par 5 vienādojumu sistēmu. Kā parādīts, vienādojumu sistēma faktiski attēlo loģisko funkciju savienojumu. Patiess ir arī apgrieztais apgalvojums - nosacījumu konjunkciju var uzskatīt par vienādojumu sistēmu. Izveidosim lēmumu koku implikācijai (x1→ x2), savienojuma pirmajam loceklim, ko var uzskatīt par pirmo vienādojumu. Lūk, kā izskatās šī koka grafiskais attēlojums: Koks sastāv no diviem līmeņiem atbilstoši mainīgo skaitam vienādojumā. Pirmais līmenis apraksta pirmo mainīgo X 1 . Divi šī līmeņa atzari atspoguļo šī mainīgā iespējamās vērtības - 1 un 0. Otrajā līmenī koka zari atspoguļo tikai tās iespējamās mainīgā X 2 vērtības, kurām vienādojumā ir patiesa vērtība. Tā kā vienādojums definē implikāciju, zaram, uz kura X 1 ir 1, ir nepieciešams, lai X 2 šajā zarā būtu 1. Zars, uz kura X 1 ir 0, ģenerē divus zarus ar X 2 vērtībām 0 un 1 Konstruētais koks definē trīs risinājumi, uz kuriem implikācija X 1 → X 2 iegūst vērtību 1. Katrā zarā tiek izrakstīta atbilstošā mainīgo vērtību kopa, kas dod vienādojuma atrisinājumu. Šīs kopas ir: ((1, 1), (0, 1), (0, 0)) Turpināsim lēmumu koka veidošanu, pievienojot šādu vienādojumu ar sekojošu implikāciju X 2 → X 3 . Mūsu vienādojumu sistēmas specifika ir tāda, ka katrā jaunajā sistēmas vienādojumā tiek izmantots viens mainīgais no iepriekšējā vienādojuma, pievienojot vienu jaunu mainīgo. Tā kā mainīgajam X 2 jau ir vērtības kokā, tad visos zaros, kur mainīgajam X 2 ir vērtība 1, arī mainīgajam X 3 būs vērtība 1. Šādiem zariem koka konstrukcija turpinās nākamais līmenis, bet neparādās jauni zari. Vienīgais zars, kurā mainīgajam X 2 ir vērtība 0, iedos atzarojumu divās atzaros, kur mainīgais X 3 iegūs vērtības 0 un 1. Tādējādi katra jauna vienādojuma pievienošana, ņemot vērā tā specifiku, pievieno vienu. risinājums. Sākotnējais pirmais vienādojums: (x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1 Mūsu sistēmas otrais vienādojums ir līdzīgs pirmajam: (y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1 Vienīgā atšķirība ir tā, ka vienādojumā izmantoti mainīgie Y. Arī šim vienādojumam ir 6 risinājumi. Tā kā katru mainīgo X i risinājumu var apvienot ar katru mainīgo Y j risinājumu, kopējais risinājumu skaits ir 36. Ņemiet vērā, ka konstruētais lēmumu koks dod ne tikai risinājumu skaitu (atbilstoši zaru skaitam), bet arī pašus risinājumus, kas uzrakstīti uz katra koka zara. 19. problēma Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem? (x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1 Šis uzdevums ir iepriekšējā uzdevuma modifikācija. Atšķirība ir tāda, ka tiek pievienots vēl viens vienādojums, kas attiecas uz mainīgajiem X un Y. No vienādojuma X 1 → Y 1 izriet, ka, ja X 1 ir vērtība 1 (viens šāds risinājums pastāv), tad arī Y 1 ir vērtība 1. Tādējādi ir viena kopa, kurā X 1 un Y 1 ir vērtības 1. Ja X 1 ir vienāds ar 0, Y 1 var būt jebkura vērtība, gan 0, gan 1. Tāpēc katra kopa ar X 1, kas vienāda ar 0, un šādas kopas ir 5, atbilst visām 6 kopām ar Y mainīgajiem. Tāpēc kopējais risinājumu skaits ir 31 . 20. problēma
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1 Risinājums: atceroties pamata ekvivalences, mēs rakstām vienādojumu šādi: (X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1 Ietekmju cikliskā ķēde nozīmē, ka mainīgie ir identiski, tāpēc mūsu vienādojums ir līdzvērtīgs vienādojumam: X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1 Šim vienādojumam ir divi risinājumi, ja visi X i ir 1 vai 0. 21. problēma
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1 Risinājums: Tāpat kā 20. uzdevumā, mēs pārejam no cikliskām sekām uz identitātēm, pārrakstot vienādojumu šādā formā: (X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1 Izveidosim lēmumu koku šim vienādojumam: 22. problēma Cik atrisinājumu ir šādai vienādojumu sistēmai? ((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0 ((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0 ((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0 ((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0 Atbilde: 64 Risinājums: pāriesim no 10 mainīgajiem uz 5 mainīgajiem, ieviešot šādas mainīgo izmaiņas: Y 1 = (X 1 ≡ X 2); Y 2 \u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10); Tad pirmais vienādojums būs šāds: (Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0 Vienādojumu var vienkāršot, ierakstot to šādi: (Y 1 ≡ Y 2) = 0 Pārejot uz tradicionālo formu, mēs rakstām sistēmu pēc formas vienkāršošanas: ¬(Y 1 ≡ Y 2) = 1 ¬(Y 2 ≡ Y 3) = 1 ¬(Y 3 ≡ Y 4) = 1 ¬(Y 4 ≡ Y 5) = 1 Šīs sistēmas lēmumu koks ir vienkāršs un sastāv no diviem zariem ar mainīgām mainīgajām vērtībām: Kā redzat, katrai vienādojumu sistēmas risināšanas problēmai ir nepieciešama sava pieeja. Izplatīts paņēmiens ir veikt līdzvērtīgas transformācijas, lai vienkāršotu vienādojumus. Izplatīta metode ir lēmumu koku konstruēšana. Izmantotā pieeja daļēji atgādina patiesības tabulas izveidošanu ar īpatnību, ka tiek konstruētas ne visas iespējamo mainīgo vērtību kopas, bet tikai tās, kurām funkcijai ir vērtība 1 (true). Bieži vien piedāvātajās problēmās nav nepieciešams izveidot pilnīgu lēmumu koku, jo jau sākotnējā posmā ir iespējams noteikt jaunu zaru parādīšanās modeli katrā nākamajā līmenī, kā tas tika darīts, piemēram, 18. problēmā. . Kopumā problēmas, kas saistītas ar risinājumu meklēšanu loģisko vienādojumu sistēmai, ir labi matemātiski vingrinājumi. Ja problēmu ir grūti atrisināt manuāli, tad risinājumu var uzticēt datoram, uzrakstot atbilstošu programmu vienādojumu un vienādojumu sistēmu risināšanai. Uzrakstīt šādu programmu nav grūti. Šāda programma viegli tiks galā ar visiem Vienotajā valsts eksāmenā piedāvātajiem uzdevumiem. Savādi, bet uzdevums atrast risinājumus loģisko vienādojumu sistēmām datoram ir sarežģīts, un izrādās, ka datoram ir savas robežas. Dators var diezgan viegli tikt galā ar problēmām, kurās mainīgo lielumu skaits ir 20-30, bet tas sāks ilgi domāt par lielāka izmēra problēmām. Fakts ir tāds, ka funkcija 2 n, kas nosaka kopu skaitu, ir eksponenciāls, kas strauji pieaug, palielinoties n. Tik ātri, ka parasts personālais dators nevar tikt galā ar uzdevumu, kuram dienā ir 40 mainīgie. Programma C# valodā loģisko vienādojumu risināšanai Loģisko vienādojumu risināšanas programmas rakstīšana ir noderīga daudzu iemeslu dēļ, kaut vai tāpēc, ka varat to izmantot, lai pārbaudītu sava vienotā valsts eksāmena pārbaudes uzdevumu risinājuma pareizību. Vēl viens iemesls ir tas, ka šāda programma ir lielisks programmēšanas uzdevuma piemērs, kas atbilst C kategorijas uzdevumu prasībām vienotajā valsts eksāmenā. Programmas izveides ideja ir vienkārša - tās pamatā ir pilnīga visu iespējamo mainīgo vērtību kopu meklēšana. Tā kā konkrētam loģiskam vienādojumam vai vienādojumu sistēmai ir zināms mainīgo lielumu skaits n, tad zināms arī kopu skaits - 2 n, kuras ir jāsakārto. Izmantojot C# valodas pamatfunkcijas – noliegumu, disjunkciju, konjunkciju un identitāti, nav grūti uzrakstīt programmu, kas noteiktai mainīgo kopai aprēķina loģiskam vienādojumam vai vienādojumu sistēmai atbilstošās loģiskās funkcijas vērtību. . Šādā programmā jums ir jāizveido cilpa, pamatojoties uz kopu skaitu, cilpas pamattekstā, izmantojot kopas numuru, jāveido pati kopa, jāaprēķina šīs kopas funkcijas vērtība un, ja šī vērtība ir 1, tad kopa dod vienādojuma atrisinājumu. Vienīgās grūtības, kas rodas, ieviešot programmu, ir saistītas ar uzdevumu pašam ģenerēt mainīgo vērtību kopu, pamatojoties uz iestatīto numuru. Šīs problēmas skaistums ir tāds, ka šis šķietami sarežģītais uzdevums faktiski ir saistīts ar vienkāršu problēmu, kas jau ir radusies daudzas reizes. Patiešām, pietiek saprast, ka mainīgo vērtību kopa, kas atbilst skaitlim i, kas sastāv no nullēm un vieniniekiem, ir skaitļa i binārais attēlojums. Tātad sarežģītais uzdevums iegūt mainīgo vērtību kopu pēc iestatītā skaitļa tiek samazināts līdz pazīstamajam uzdevumam pārvērst skaitli binārā. Šādi izskatās funkcija C#, kas atrisina mūsu problēmu: /// /// programma risinājumu skaita skaitīšanai /// loģiskais vienādojums (vienādojumu sistēma) /// ///
/// loģiskā funkcija — metode, /// kuras parakstu norāda DF delegāts /// /// mainīgo lielumu skaits /// statisks int. Atrisiniet vienādojumus (DF jautri, int n) bool set = new bool[n]; int m = (int)Math.Pow(2, n); //komplektu skaits int p = 0, q = 0, k = 0; //Pabeigt meklēšanu pēc kopu skaita for (int i = 0; i< m; i++) //Nākamās kopas veidošana - komplekts, //norāda skaitļa i binārais attēlojums for (int j = 0; j< n; j++) k = (int)Math.Pow(2, j); //Aprēķināt funkcijas vērtību komplektā Lai saprastu programmu, ceru, ka programmas idejas skaidrojumi un komentāri tās tekstā ir pietiekami. Es pievērsīšos tikai dotās funkcijas nosaukuma izskaidrošanai. Funkcijai SolveEquations ir divi ievades parametri. Funkcijas parametrs norāda loģisku funkciju, kas atbilst atrisināmajam vienādojumam vai vienādojumu sistēmai. Parametrs n norāda jautrības funkcijas mainīgo skaitu. Rezultātā funkcija SolveEquations atgriež loģiskās funkcijas risinājumu skaitu, tas ir, to kopu skaitu, kurās funkcija novērtē kā patiesu. Skolēniem parasti ir gadījumi, kad kādai funkcijai F(x) ir ievades parametrs x, kas ir aritmētiskā, virknes vai loģiskā tipa mainīgais. Mūsu gadījumā tiek izmantots jaudīgāks dizains. Funkcija SolveEquations attiecas uz augstākas kārtas funkcijām - F(f) tipa funkcijām, kuru parametri var būt ne tikai vienkārši mainīgie, bet arī funkcijas. Funkciju klase, ko var nodot kā parametru funkcijai SolveEquations, ir norādīta šādi: delegate bool DF(bool vars); Šai klasei pieder visas funkcijas, kuras kā parametrs tiek nodotas loģisko mainīgo vērtību kopai, ko nosaka vars masīvs. Rezultāts ir Būla vērtība, kas attēlo šīs kopas funkcijas vērtību. Visbeidzot, šeit ir programma, kas izmanto SolveEquations funkciju, lai atrisinātu vairākas loģisko vienādojumu sistēmas. Funkcija SolveEquations ir daļa no šādas ProgramCommon klases: klases ProgrammCommon delegate bool DF(bool vars); statiskā tukšums Galvenā (stīgu args) Console.WriteLine("Funkcija un risinājumi - " + Atrisiniet vienādojumus (Jautri, 2)); Console.WriteLine("Funkcijai ir 51 risinājums - " + Atrisiniet vienādojumus (Fun51, 5)); Console.WriteLine("Funkcijai ir 53 risinājumi - " + Atrisiniet vienādojumus (Fun53, 10)); statisks bool FunAnd(bool vars) atgriezties vars && vars; statiskā bool Fun51 (bool vars) f = f && (!vars || vars); f = f && (!vars || vars); f = f && (!vars || vars); f = f && (!vars || vars); f = f && (!vars || vars); statiskā bool Fun53 (bool vars) f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && (!((vars == vars) || (vars == vars))); Lūk, kā izskatās šīs programmas risinājuma rezultāti: 10 uzdevumi patstāvīgam darbam Kurai no trim funkcijām šis fragments atbilst: Atbildes uz problēmām: Šajā materiālā ir iekļauta prezentācija, kurā ir izklāstītas loģisko vienādojumu risināšanas metodes un loģisko vienādojumu sistēmas Vienotā valsts eksāmena datorzinātnēs uzdevumā B15 (Nr. 23, 2015). Zināms, ka šis uzdevums ir viens no grūtākajiem Vienotā valsts pārbaudījuma uzdevumiem. Prezentācija var būt noderīga, pasniedzot nodarbības par tēmu “Loģika” specializētajās nodarbībās, kā arī gatavojoties vienotajam valsts eksāmenam. Lai izmantotu prezentāciju priekšskatījumus, izveidojiet Google kontu un piesakieties tajā: https://accounts.google.com B15 uzdevuma atrisinājums (loģisko vienādojumu sistēmas) Višņevska M.P., MAOU “Ģimnāzija Nr.3” 2013.gada 18.novembris, Saratova B15 uzdevums ir viens no grūtākajiem Vienotajā valsts eksāmenā datorzinībās!!! Tiek pārbaudītas šādas prasmes: konvertēt izteiksmes, kas satur loģiskos mainīgos; aprakstiet dabiskajā valodā loģisko mainīgo vērtību kopu, kurai ir patiesa dotā loģisko mainīgo kopa; saskaitīt bināro kopu skaitu, kas atbilst dotajiem nosacījumiem. Grūtākais ir tāpēc, ka... nav formālu noteikumu, kā to izdarīt, tas prasa minējumus. Bez kā nevar iztikt! Bez kā nevar iztikt! Konvenciju konjunkcija: A /\ B , A B , AB , А &B, A un B disjunkcija: A \ / B , A + B , A | B , A vai B noliegums: A , A, nevis A ekvivalence: A B, A B, A B ekskluzīvs “vai”: A B , A xor B Mainīgo aizstāšanas metode Cik dažādu loģisko mainīgo x1, x2, ..., x9, x10 vērtību kopu pastāv, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5) ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Atbildē nav jānorāda visas dažādās kopas x1, x2, …, x9, x10, kurām šī vienlīdzības sistēma ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits (2012. gada demonstrācijas versija) Risinājums 1. solis. Vienkāršojiet, mainot mainīgos t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 Pēc vienkāršošanas: (t1 \/ t2) /\/¬t1 t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Apsveriet vienu no vienādojumiem: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Acīmredzot tas =1 tikai tad, ja viens no mainīgajiem ir 0 un otrs ir 1 . Izmantosim formulu, lai izteiktu XOR darbību, izmantojot konjunkciju un disjunkciju: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 2. darbība. Sistēmas analīze .Līdz. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), tad katra tk vērtība atbilst diviem vērtību pāriem x2k-1 un x2k, piemēram: tk =0 atbilst diviem pāriem - (0 ,1) un (1, 0) , un tk =1 – pāri (0,0) un (1,1). 3. darbība. Risinājumu skaita skaitīšana. Katram t ir 2 atrisinājumi, ts skaits ir 5. Tādējādi. mainīgajiem t ir 2 5 = 32 atrisinājumi. Bet katram t atbilst atrisinājumu pāris x, t.i. sākotnējā sistēmā ir 2*32 = 64 risinājumi. Atbilde: 64 Daļas risinājumu likvidēšanas metode Cik dažādas loģisko mainīgo vērtību kopas ir x1, x2, ..., x5, y1,y2,..., y5, kas atbilst visiem zemāk uzskaitītajiem nosacījumiem: (x1 → x2 )∧(x2→x3)∧(x3→x4 )∧(x4→x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 =1. Atbildē nav jāuzskaita visas dažādās kopas x1, x2, ..., x5, y 1 , y2, ... , y5, kurām šī vienādību sistēma ir spēkā. Atbildē jānorāda šādu komplektu skaits. Risinājums. 1. darbība. Vienādojumu secīgs risinājums x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Pirmais vienādojums ir vairāku implikācijas operāciju konjunkcija, kas vienāda ar 1, t.i. katra no sekām ir patiesa. Implikācija ir nepatiesa tikai vienā gadījumā, kad 1 0, visos pārējos gadījumos (0 0, 0 1, 1 1) darbība atgriež 1. Rakstīsim to tabulas formā: 1. darbība. Vienādojumu secīgs risinājums T.o. Tika iegūti 6 risinājumu komplekti x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Spriežot līdzīgi, mēs nonākam pie secinājuma, ka y1, y2, y3, y4, y5 ir tāda pati risinājumu kopa. Jo šie vienādojumi ir neatkarīgi, t.i. tiem nav kopīgu mainīgo, tad šīs vienādojumu sistēmas risinājums (neņemot vērā trešo vienādojumu) būs 6 * 6 = 36 pāri “X” un “Y”. Aplūkosim trešo vienādojumu: y5→ x5 =1 Atrisinājums ir pāri: 0 0 0 1 1 1 Pāris nav risinājums: 1 0 Salīdzināsim iegūtos risinājumus, kur y5 =1, x5=0 neder. tādu pāru ir 5. Sistēmas atrisinājumu skaits: 36-5= 31. Atbilde: 31 Bija nepieciešama kombinatorika!!! Dinamiskās programmēšanas metode Cik dažādu risinājumu ir loģiskajam vienādojumam x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kur x 1, x 2, …, x 6 ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās mainīgo vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājuma solis 1. Nosacījuma analīze Pa kreisi vienādojumā implikācijas operācijas ir rakstītas secīgi, prioritāte ir vienāda. Pārrakstīt: (((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Katrs nākamais mainīgais ir atkarīgs nevis no iepriekšējā, bet gan no iepriekšējās implikācijas rezultāta! 2. darbība. Modeļa atklāšana Apskatīsim pirmo implikāciju X 1 → X 2. Patiesības tabula: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 No viena 0 mēs saņēmām 2 vienības, bet no 1 mēs saņēmām vienu 0 un vienu 1. Tikai viens 0 un trīs 1, tas ir pirmās darbības rezultāts. 2. darbība. Parauga atklāšana Savienojot x 3 ar pirmās darbības rezultātu, iegūstam: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 No diviem 0 - divi 1, no katra 1 (ir 3) pa vienam 0 un 1 (3 + 3) Solis 3. Formulas atvasināšana T.o. jūs varat izveidot formulas nullju skaita N i un vieninieku skaita E i aprēķināšanai vienādojumam ar i mainīgajiem: , 4. solis. Tabulas aizpildīšana Aizpildīsim tabulu no kreisās puses uz labo, ja i = 6, aprēķinot nulles un vieniniekus, izmantojot iepriekš minētās formulas; tabulā parādīts, kā tiek veidota nākamā kolonna no iepriekšējās: mainīgo skaits 1 2 3 4 5 6 Nuļļu skaits N i 1 1 3 5 11 21 Vieninieku skaits E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Atbilde: 43 Metode, izmantojot loģisko izteiksmju vienkāršojumus Cik dažādu risinājumu ir vienādojumam ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1, kur J, K, L, M, N ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās J, K, L, M un N vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājums Ņemiet vērā, ka J → K = ¬ J K Ieviesīsim mainīgo izmaiņu: J → K=A, M N L =B Pārrakstīsim vienādojumu, ņemot vērā izmaiņas: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Acīmredzot A B vienādām A un B vērtībām 6. Apsveriet pēdējo implikāciju M → J = 1 Tas ir iespējams, ja: M = J = 0 M = 0, J = 1 M = J = 1 Risinājums Jo A B, tad Kad M=J=0 iegūstam 1 + K=0. Nav risinājumu. Ja M=0, J=1 iegūstam 0 + K=0, K=0, un N un L ir jebkuri, 4 risinājumi: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1 10. risinājums. Kad M=J=1 iegūstam 0+K=1 *N * L, jeb K=N*L, 4 risinājumi: 11. Kopā ir 4+4=8 risinājumi Atbilde: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1 Informācijas avoti: O.B. Bogomolova, D.Ju. Usenkovs. B15: jauni uzdevumi un jauni risinājumi // Informātika, Nr. 6, 2012, lpp. 35 – 39. K.Yu. Poļakovs. Loģiskie vienādojumi // Informātika, Nr. 14, 2011, lpp. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektroniskais resurss]. http://kpolyakov.narod.ru/school/ege.htm, [Elektroniskais resurss]. Loģisko vienādojumu sistēmu risināšana, mainot mainīgos Mainīgo aizvietošanas metode tiek izmantota, ja daži mainīgie ir iekļauti vienādojumos tikai noteiktas izteiksmes veidā, un nekas cits. Tad šo izteiksmi var apzīmēt ar jaunu mainīgo. 1. piemērs. Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, x6, x7, x8 vērtību kopu ir, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem? (x1 → x2) → (x3 → x4) = 1 (x3 → x4) → (x5 → x6) = 1 (x5 → x6) → (x7 → x8) = 1 Atbildē nav jāuzskaita visas dažādās mainīgo x1, x2, x3, x4, x5, x6, x7, x8 vērtību kopas, kurām šī vienādību sistēma ir izpildīta. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājums: (x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4. Tad mēs varam uzrakstīt sistēmu viena vienādojuma formā: (y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Savienojums ir 1 (patiess), kad katrs operands iegūst vērtību 1. Tas ir katrai ietekmei ir jābūt patiesai, un tas attiecas uz visām vērtībām, izņemot (1 → 0). Tie. mainīgo y1, y2, y3, y4 vērtību tabulā viens nedrīkst būt pa kreisi no nulles: Tie. nosacījumi ir izpildīti 5 komplektiem y1-y4. Jo y1 = x1 → x2, tad vērtība y1 = 0 tiek sasniegta vienā kopā x1, x2: (1, 0), un vērtība y1 = 1 tiek sasniegta trīs kopās x1, x2: (0,0) , ( 0,1), (1,1). Līdzīgi y2, y3, y4. Tā kā katra kopa (x1,x2) mainīgajam y1 ir apvienota ar katru kopu (x3,x4) mainīgajam y2 un tā tālāk, mainīgo x kopu skaits tiek reizināts: Komplektu skaits uz x1…x8 Saskaitīsim kopu skaitu: 1 + 3 + 9 + 27 + 81 = 121. Atbilde: 121 2. piemērs. Cik dažādu Būla mainīgo x1, x2, ... x9, y1, y2, ... y9 vērtību kopu ir, kas atbilst visiem tālāk norādītajiem nosacījumiem? (¬ (x1 ≡ y1)) ≡ (x2 ≡ y2) (¬ (x2 ≡ y2)) ≡ (x3 ≡ y3) (¬ (x8 ≡ y8)) ≡ (x9 ≡ y9) Atbildot nav vajadzības uzskaitiet visas dažādās mainīgo x1, x2, ... x9, y1, y2, ... y9 vērtību kopas, saskaņā ar kurām tiek izpildīta dotā vienādību sistēma. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājums: Mainīsim mainīgos: (x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9 Sistēmu var uzrakstīt kā vienu vienādojumu: (¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9) Ekvivalence ir patiesa tikai tad, ja abi operandi ir vienādi. Šim vienādojumam ir divas risinājumu kopas: Jo zi = (xi ≡ yi), tad vērtība zi = 0 atbilst divām kopām (xi,yi): (0,1) un (1,0), un vērtība zi = 1 atbilst divām kopām (xi,yi). ): (0 ,0) un (1,1). Tad pirmā kopa z1, z2,…, z9 atbilst 2 9 kopām (x1,y1), (x2,y2),…, (x9,y9). Tas pats skaitlis atbilst otrajai kopai z1, z2,…, z9. Tad kopā ir 2 9 +2 9 = 1024 komplekti. Atbilde: 1024 Loģisko vienādojumu sistēmu risināšana pēc rekursijas vizuālas definīcijas. Šo metodi izmanto, ja vienādojumu sistēma ir pietiekami vienkārša un kopu skaita palielināšanas secība, pievienojot mainīgos, ir acīmredzama. 3. piemērs. Cik dažādu risinājumu ir vienādojumu sistēmai? ¬x9 ∨ x10 = 1, kur x1, x2, … x10 ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās vērtību kopas x1, x2, ... x10, kurām attiecas dotā vienādību sistēma. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājums: Atrisināsim pirmo vienādojumu. Disjunkcija ir vienāda ar 1, ja vismaz viens no tās operandiem ir vienāds ar 1. Tas ir risinājumi ir komplekti: Ja x1 = 0, ir divas x2 vērtības (0 un 1), un x1 = 1 ir tikai viena x2 vērtība (1), lai kopa (x1, x2) būtu vienādojuma risinājums. Kopā ir 3 komplekti. Pievienosim mainīgo x3 un apsvērsim otro vienādojumu. Tas ir līdzīgs pirmajam, kas nozīmē, ka x2=0 ir divas x3 vērtības (0 un 1), bet x2=1 ir tikai viena x3 (1) vērtība, lai kopa ( x2,x3) ir vienādojuma risinājums. Kopā ir 4 komplekti. Ir viegli redzēt, ka, pievienojot citu mainīgo, tiek pievienota viena kopa. Tie. rekursīvā formula (i+1) mainīgo kopu skaitam: N i +1 = N i + 1. Tad desmit mainīgajiem iegūstam 11 kopas. Atbilde: 11 Dažādu veidu loģisko vienādojumu sistēmu risināšana 4. piemērs. Cik dažādas loģisko mainīgo vērtību kopas ir x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem ? (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 Atbildot nav vajadzības uzskaitiet visas mainīgo x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 dažādās vērtību kopas, kurām šī vienādību sistēma ir izpildīta. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājums: Ņemiet vērā, ka trīs sistēmas vienādojumi dažādās neatkarīgās mainīgo kopās ir vienādi. Apskatīsim pirmo vienādojumu. Saiklis ir patiess (vienāds ar 1) tikai tad, ja visi tā operandi ir patiesi (vienāds ar 1). Ietekme ir 1 uz visiem kortežiem, izņemot (1,0). Tas nozīmē, ka pirmā vienādojuma risinājums būs šādas kopas x1, x2, x3, x4, kurās 1 neatrodas pa kreisi no 0 (5 kopas): Līdzīgi otrā un trešā vienādojuma risinājumi būs absolūti vienādas kopas y1,…,y4 un z1,…, z4. Tagad analizēsim sistēmas ceturto vienādojumu: x 4 ∧ y 4 ∧ z 4 = 0. Atrisinājums būs visas kopas x4, y4, z4, kurās vismaz viens no mainīgajiem ir vienāds ar 0. Tie. ja x4 = 0 ir piemērotas visas iespējamās kopas (y4, z4), un x4 = 1 ir piemērotas kopas (y4, z4), kurās ir vismaz viena nulle: (0, 0), (0,1) ), (1, 0). Komplektu skaits Kopējais komplektu skaits ir 25 + 4*9 = 25 + 36 = 61. Atbilde: 61 Loģisko vienādojumu sistēmu risināšana, konstruējot atkārtotas formulas Atkārtotu formulu konstruēšanas metode tiek izmantota, risinot sarežģītas sistēmas, kurās kopu skaita palielināšanas secība nav acīmredzama un koka konstruēšana nav iespējama apjomu dēļ. 5. piemērs. Cik dažādu loģisko mainīgo x1, x2, ... x7, y1, y2, ... y7 vērtību kopu ir, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem? (x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1 (x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1 (x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1 Atbildē nav jāuzskaita visas dažādās mainīgo x1, x2, ..., x7, y1, y2, ..., y7 vērtību kopas, kurām šī vienādību sistēma ir izpildīta. Kā atbilde jums jānorāda šādu komplektu skaits. Risinājums: Ņemiet vērā, ka pirmie seši sistēmas vienādojumi ir identiski un atšķiras tikai mainīgo kopā. Apskatīsim pirmo vienādojumu. Tās risinājums būs šādas mainīgo kopas: Apzīmēsim: korešu skaits (0,0) mainīgajiem (x1,y1) līdz A 1, virkņu skaits (0,1) mainīgajiem (x1,y1) līdz B 1, korešu skaits (1,0) mainīgajiem (x1,y1) līdz C 1, korešu skaits (1,1) uz mainīgajiem (x1,y1) līdz D 1 . virkņu skaits (0,0) uz mainīgajiem (x2,y2) līdz A2, korešu skaits (0,1) mainīgajiem (x2,y2) līdz B 2, korešu skaits (1,0) uz mainīgajiem (x2,y2) līdz C 2, korešu skaits (1,1) uz mainīgajiem (x2,y2) līdz D 2 . No lēmumu koka mēs to redzam A 1 = 0, B 1 = 1, C 1 = 1, D 1 = 1. Ņemiet vērā, ka kopa (0,0) uz mainīgajiem (x2,y2) tiek iegūta no kopām (0,1), (1,0) un (1,1) uz mainīgajiem (x1,y1). Tie. A 2 = B 1 + C 1 + D 1. Kopa (0,1) uz mainīgajiem (x2,y2) tiek iegūta no kopām (0,1), (1,0) un (1,1) uz mainīgajiem (x1,y1). Tie. B 2 = B 1 + C 1 + D 1. Līdzīgi argumentējot, mēs atzīmējam, ka C 2 =B 1 + C 1 + D 1. D2 = D1. Tādējādi mēs iegūstam atkārtotas formulas: 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 Taisām galdu Komplektu skaits Pēdējo vienādojumu (x7 ∨ y7) = 1 apmierina visas kopas, izņemot tās, kurās x7=0 un y7=0. Mūsu tabulā šādu komplektu skaits ir A 7. Tad kopējais kopu skaits ir B 7 + C 7 + D 7 = 127+127+1 = 255 Atbilde: 255 Loģisko vienādojumu sistēmu risināšanas metodes
Kirgizova E.V., Ņemkova A.E.
Lesosibirskas pedagoģiskais institūts -
Sibīrijas federālās universitātes filiāle, Krievija
Spēja konsekventi domāt, pārliecinoši argumentēt, izvirzīt hipotēzes un atspēkot negatīvus secinājumus nerodas pati par sevi, šo prasmi attīsta loģikas zinātne. Loģika ir zinātne, kas pēta metodes dažu apgalvojumu patiesuma vai nepatiesuma noteikšanai, pamatojoties uz citu apgalvojumu patiesumu vai nepatiesību. Šīs zinātnes pamatu apgūšana nav iespējama bez loģisku problēmu risināšanas. Prasmju attīstības pārbaude, lai pielietotu savas zināšanas jaunā situācijā, tiek veikta caur piespēli. Jo īpaši tā ir spēja atrisināt loģiskās problēmas. Uzdevumi B15 vienotajā valsts eksāmenā ir paaugstinātas sarežģītības uzdevumi, jo tie satur loģisko vienādojumu sistēmas. Ir dažādi veidi, kā atrisināt loģisko vienādojumu sistēmas. Tas ir reducēšana uz vienu vienādojumu, patiesības tabulas konstruēšana, sadalīšana, vienādojumu secīgs risinājums utt. Uzdevums:Atrisiniet loģisko vienādojumu sistēmu: Apsvērsim samazināšanas metode līdz vienam vienādojumam
. Šī metode ietver loģisko vienādojumu pārveidošanu tā, lai to labās puses būtu vienādas ar patiesības vērtību (tas ir, 1). Lai to izdarītu, izmantojiet loģiskās noliegšanas darbību. Tad, ja vienādojumos ir sarežģītas loģiskās darbības, mēs tās aizstājam ar pamata operācijām: “UN”, “OR”, “NOT”. Nākamais solis ir apvienot vienādojumus vienā, kas ir ekvivalents sistēmai, izmantojot loģisko darbību “UN”. Pēc tam jums jāpārveido iegūtais vienādojums, pamatojoties uz loģiskās algebras likumiem, un jāiegūst konkrēts sistēmas risinājums. 1. risinājums:Lietojiet inversiju abām pirmā vienādojuma pusēm: Iedomāsimies nozīmi, izmantojot pamata darbības “OR” un “NOT”: Tā kā vienādojumu kreisās puses ir vienādas ar 1, mēs varam tos apvienot, izmantojot operāciju “UN”, vienā vienādojumā, kas ir līdzvērtīgs sākotnējai sistēmai: Mēs atveram pirmo iekavu saskaņā ar De Morgana likumu un pārveidojam iegūto rezultātu: Iegūtajam vienādojumam ir viens risinājums: A= 0, B = 0 un C = 1. Nākamā metode ir veidojot patiesības tabulas
. Tā kā loģiskajiem lielumiem ir tikai divas vērtības, varat vienkārši izskatīt visas iespējas un atrast starp tām tos, kuriem ir izpildīta noteiktā vienādojumu sistēma. Tas ir, mēs izveidojam vienu kopīgu patiesības tabulu visiem sistēmas vienādojumiem un atrodam līniju ar nepieciešamajām vērtībām. 2. risinājums:Izveidosim patiesības tabulu sistēmai: 0
0
1
1
0
1
Rinda, kurai ir izpildīti uzdevuma nosacījumi, ir izcelta treknrakstā. Tātad A =0, B =0 un C =1. veids sadalīšanās
.
Ideja ir fiksēt viena mainīgā vērtību (iestatīt to vienādu ar 0 vai 1) un tādējādi vienkāršot vienādojumus. Pēc tam varat labot otrā mainīgā vērtību utt. 3. risinājums:Ļaujiet A = 0, tad: No pirmā vienādojuma mēs iegūstam B =0, un no otrā – C=1. Sistēmas risinājums: A = 0, B = 0 un C = 1. Varat arī izmantot metodi vienādojumu secīgs risinājums
, katrā solī pievienojot apskatāmajai kopai vienu mainīgo. Lai to izdarītu, vienādojumus nepieciešams pārveidot tā, lai mainīgie tiktu ievadīti alfabētiskā secībā. Tālāk mēs izveidojam lēmumu koku, secīgi pievienojot tam mainīgos. Pirmais sistēmas vienādojums ir atkarīgs tikai no A un B, bet otrais vienādojums no A un C. Mainīgajam A var būt 2 vērtības 0 un 1: Tādējādi mēs ieguvām sistēmas risinājumu: A = 0, B = 0 un C = 1. Vienotajā valsts eksāmenā datorzinātnēs ļoti bieži ir nepieciešams noteikt loģisko vienādojumu sistēmas atrisinājumu skaitu, neatrodot pašus risinājumus, tam ir arī noteiktas metodes. Galvenais veids, kā atrast risinājumu skaitu loģisko vienādojumu sistēmai, ir mainīgo lielumu aizstāšana. Pirmkārt, jums pēc iespējas jāvienkāršo katrs vienādojums, pamatojoties uz loģiskās algebras likumiem, un pēc tam vienādojumu sarežģītās daļas jāaizstāj ar jauniem mainīgajiem un jānosaka jaunās sistēmas risinājumu skaits. Pēc tam atgriezieties pie nomaiņas un nosakiet tam risinājumu skaitu. Uzdevums:Cik atrisinājumu ir vienādojumam ( A → B ) + (C → D ) = 1? Kur A, B, C, D ir loģiskie mainīgie. Risinājums:Ieviesīsim jaunus mainīgos: X = A → B un Y = C → D . Ņemot vērā jaunos mainīgos, vienādojums tiks uzrakstīts šādi: X + Y = 1. Disjunkcija ir patiesa trīs gadījumos: (0;1), (1;0) un (1;1), savukārt X un Y ir norāde, tas ir, tā ir patiesa trīs gadījumos un nepatiesa vienā. Tāpēc gadījums (0;1) atbildīs trīs iespējamām parametru kombinācijām. Gadījums (1;1) – atbildīs deviņām iespējamām sākotnējā vienādojuma parametru kombinācijām. Tas nozīmē, ka šī vienādojuma iespējamie risinājumi ir 3+9=15. Nākamais veids, kā noteikt risinājumu skaitu loģisko vienādojumu sistēmai, ir binārais koks. Apskatīsim šo metodi ar piemēru. Uzdevums:Cik dažādu risinājumu ir loģisko vienādojumu sistēmai: Dotā vienādojumu sistēma ir līdzvērtīga vienādojumam: (
x 1
→
x 2
)*(
x 2
→
x 3
)*…*(
x m -1
→
x m) = 1.
Izliksimies tāx 1
ir taisnība, tad no pirmā vienādojuma mēs to iegūstamx 2
arī taisnība, no otrā -x 3
=1 un tā tālāk līdz x m= 1. Tātad kopa (1; 1; …; 1) no m vienības ir sistēmas risinājums. Ļaujiet tai tagadx 1
=0, tad no pirmā vienādojuma mums irx 2
=0 vai x 2
=1.
Kad x 2
taisnība, mēs iegūstam, ka arī pārējie mainīgie ir patiesi, tas ir, kopa (0; 1; ...; 1) ir sistēmas risinājums. Plkstx 2
=0 mēs to sapratām x 3
=0 vai x 3
=, un tā tālāk. Turpinot pie pēdējā mainīgā, mēs atklājam, ka vienādojuma risinājumi ir šādas mainīgo kopas ( m +1 risinājums, katrā risinājumā m mainīgās vērtības): (1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Šo pieeju labi ilustrē bināra koka izveide. Iespējamo risinājumu skaits ir konstruētā koka dažādu zaru skaits. Ir viegli redzēt, ka tā ir m +1. Mainīgie lielumi Koks Risinājumu skaits x 1 x 2 x 3 Ja rodas grūtības argumentācijā un lēmumu koka veidošanā, risinājumu var meklēt, izmantojot patiesības tabulas, vienam vai diviem vienādojumiem. Mēs pārrakstām vienādojumu sistēmu šādā formā: Un izveidosim patiesības tabulu atsevišķi vienam vienādojumam: x 1 x 2 (x 1 → x 2) Izveidosim patiesības tabulu diviem vienādojumiem: x 1 x 2 x 3 x 1 → x 2 x 2 → x 3 (x 1 → x 2) * (x 2 → x 3) Tālāk var redzēt, ka viens vienādojums ir patiess šādos trīs gadījumos: (0; 0), (0; 1), (1; 1). Divu vienādojumu sistēma ir patiesa četros gadījumos (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Šajā gadījumā uzreiz ir skaidrs, ka ir risinājums, kas sastāv tikai no nullēm un vairāk m risinājumi, kuros tiek pievienota viena vienība, sākot no pēdējās pozīcijas, līdz tiek aizpildītas visas iespējamās vietas. Var pieņemt, ka vispārējam risinājumam būs tāda pati forma, taču, lai šāda pieeja kļūtu par risinājumu, ir nepieciešams pierādījums, ka pieņēmums ir pareizs. Apkopojot visu iepriekš minēto, es vēlos vērst jūsu uzmanību uz to, ka ne visas apspriestās metodes ir universālas. Risinot katru loģisko vienādojumu sistēmu, jāņem vērā tās pazīmes, uz kuru pamata jāizvēlas risināšanas metode. Literatūra: 1.
Loģiskās problēmas / O.B. Bogomolovs – 2. izd. – M.: BINOM. Zināšanu laboratorija, 2006. – 271 lpp.: ill. 2.
Poļakovs K.Ju. Loģisko vienādojumu sistēmas / Izglītības un metodiskais laikraksts informātikas skolotājiem: Informātika 2011.g. Nr.14.
a ˅ b ≡ b ˅ a
a^b ≡ b^a
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
¬(¬a) ≡ a
a ^ ¬а ≡ nepatiess
a ˅ ¬а ≡ taisnība
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ patiess ≡ a
a ˄ nepatiess ≡ nepatiess
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
a → b ≡ ¬a ˅ b
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)x1
x2
X 3
x4
F
1
1
0
0
1
0
1
1
1
1
1
0
0
1
0
A
B
C
F 1
F 2
F 1˄ F 2
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
0
0
ir 6 risinājumi. Lūk, kā izskatās šī vienādojuma pilns lēmumu koks:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1
Atgriežoties pie sākotnējiem X mainīgajiem, ņemiet vērā, ka katra Y mainīgā vērtība atbilst 2 mainīgo X vērtībām, tāpēc katrs Y mainīgā lieluma risinājums ģenerē 2 5 risinājumus mainīgajos X. Divi zari ģenerē 2 * 2 5 risinājumus. , tātad kopējais risinājumu skaits ir 64.
x1
x2
X 3
x4
F
1
0
0
1
1
0
1
1
1
1
1
0
1
0
0
Kuri no šiem teikumiem ir pareizi izveidoti:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
(a → b) → c = 0
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1
(((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
P ˄ (M 1 ˅ M 2)
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))Lejupielādēt:
Priekšskatījums:
Slaidu paraksti:
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
Komplekti
Simbols.
Formula
i=1
i=2
i=3
i=4
i=5
i=6
i=7
(0,0)
A i
Ai+1 =Bi +Ci +Di
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
No pirmā vienādojuma izriet, ka 
, tad, kad A = 0 un mēs iegūstam B = 0, un A = 1 mums ir B = 1. Tātad pirmajam vienādojumam ir divi risinājumi attiecībā uz mainīgajiem A un B.
Attēlosim otro vienādojumu, no kura katrai opcijai nosakām C vērtības. Ja A =1, implikācija nevar būt nepatiesa, tas ir, koka otrajam zaram nav risinājuma. Plkst A= 0
mēs iegūstam vienīgo risinājumu C= 1
:
