Metoda de rezolvare a sistemelor de ecuații logice. Logică
Lăsați funcția logică de la variabilele N. Ecuația logică este:
Constant C are o valoare de 1 sau 0.
Ecuația logică poate avea de la 0 la diferite soluții. Dacă C este egal cu 1, atunci soluțiile sunt toate seturile de variabile din tabelul adevărului, pe care funcția F ia valoarea adevărului (1). Kiturile rămase sunt soluții ale ecuației la C egal cu zero. Puteți lua în considerare întotdeauna numai ecuațiile formularului:
Într-adevăr, lăsați setul de ecuații:
În acest caz, puteți merge la ecuația echivalentă:
Luați în considerare sistemul de la ecuațiile logice K:
Soluția sistemului este un set de variabile pe care se efectuează toate ecuațiile sistemului. În ceea ce privește funcțiile logice, pentru a obține o soluție a sistemului de ecuații logice, ar trebui să găsiți un set pe care funcția logică F este adevărată reprezentând conjuncția funcțiilor sursă:
Dacă numărul de variabile este mic, de exemplu, mai puțin de 5, nu este dificil să construiți un tabel de adevăr pentru o funcție, ceea ce vă permite să spuneți câte soluții au un sistem și care sunt seturile care dau soluții.
În unele sarcini ale EGE pentru a găsi soluții ale sistemului de ecuații logice, numărul variabilelor atinge o valoare de 10. Apoi construirea unui tabel de adevăr devine o sarcină practic dificilă. Pentru a rezolva problema, este necesară o altă abordare. Pentru un sistem arbitrar de ecuații, nu există altă metodă comună decât bustul care vă permite să rezolvați astfel de sarcini.
În sarcinile propuse la examen, soluția se bazează, de obicei, pe specificul sistemului de ecuații. Repet, pe lângă căutarea tuturor variantelor de set de variabile, nu există o modalitate generală de a rezolva problema. Decizia trebuie construită pe baza specificului sistemului. Este adesea utilă simplificarea preliminară a sistemului de ecuații care utilizează legi logice bine cunoscute. O altă primire utilă a soluționării acestei sarcini este după cum urmează. Nu suntem interesați de toate seturile, ci doar pe cele pe care funcția este importantă pentru 1. În loc să construim o masă de adevăr complet, vom construi analogul - o soluții binare de copac. Fiecare ramură a acestui copac corespunde unei singure soluții și stabilește setul pe care funcționează funcția 1. Numărul de ramuri din copacul de soluții coincide cu numărul de soluții ale sistemului de ecuații.
Ce este un copac binar de decizie și cum este construit, explicați cu privire la exemplele de mai multe sarcini.
Sarcina 18.
Câte seturi diferite de valori ale variabilelor logice X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, care satisfac sistemul a două ecuații?
Răspuns: Sistemul are 36 de soluții diferite.
Soluție: Sistemul de ecuații include două ecuații. Noi găsim numărul de soluții pentru prima ecuație dependentă de 5 variabile. Prima ecuație poate, la rândul său, să ia în considerare ca un sistem de 5 ecuații. După cum se arată, sistemul de ecuații reprezintă de fapt conjuncția funcțiilor logice. Declarația inversă este, de asemenea, adevărată, conjuncția condițiilor poate fi considerată ca un sistem de ecuații.
Construim cochilii de implicare () - primul membru al conjuncției, care poate fi considerat ca prima ecuație. Iată cum arată imaginea grafică a acestui copac
Arborele constă din două nivele după numărul de variabile de ecuații. Primul nivel descrie prima variabilă. Cele două ramuri ale acestui nivel reflectă valorile posibile ale acestei variabile - 1 și 0. La al doilea nivel al ramurii arborelui, numai cele posibile valori variabile reflectă pentru care ecuația ia valoarea adevărului. Deoarece ecuația specifică implicația, sucursala pe care devine 1, necesită ca valoarea 1. sucursala pe care are 0, generează două ramuri cu valori egale cu 0 și 1. Arborele construit stabilește trei soluții Ce implicare are o valoare 1. La fiecare ramură, un set adecvat de valori variabile, care dă soluția la ecuația este descărcat.
Acestea sunt aceste seturi: ((1, 1), (0, 1), (0, 0))
Vom continua să construim un copac de soluții prin adăugarea următoarei ecuații cu următoarea implicare. Specificul sistemului nostru de ecuații sunt că fiecare nouă ecuație a sistemului utilizează o variabilă din ecuația anterioară, adăugând o nouă variabilă. Deoarece variabila are deja valori pe un copac, pe toate ramurile, unde variabila este 1, variabila va avea, de asemenea, o valoare 1. Pentru astfel de ramuri, construcția unui copac continuă la nivelul următor, dar noi ramuri nu apare. Singura ramură în care variabila este 0, va da ramificarea în două ramuri, în care variabila va primi valoarea 0 și 1. Astfel, fiecare adăugare a unei noi ecuații, având în vedere specificitatea acestuia, adaugă o singură soluție. Sursa prima ecuație:
are 6 soluții. Iată cum arată pomul complet al soluțiilor pentru această ecuație:
A doua ecuație a sistemului nostru este similară cu cea de primă:
Singura diferență este că ecuațiile utilizează variabilele y. Această ecuație are, de asemenea, 6 soluții. Deoarece fiecare soluție pentru variabile poate fi combinată cu fiecare soluție pentru variabile, numărul total de soluții este egal cu 36.
Observați, arborele de soluții construite oferă nu numai numărul de soluții (de numărul de ramuri), ci și deciziile înșiși evacuate pe fiecare ramură a copacului.
Sarcina 19.
Câte seturi diferite de valori ale variabilelor logice X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, care satisfac toate condițiile enumerate mai jos?
Această sarcină este o modificare a sarcinii anterioare. Diferența este că se adaugă o altă ecuație care leagă variabilele X și Y.
Rezultă din ecuația că, atunci când are o valoare de 1 (o astfel de soluție există), atunci contează 1. Astfel, există un set pe care valorile 1. la egal cu 0 pot avea orice valoare ca 0 , deci și 1. Prin urmare, fiecare set cu egal cu 0 și astfel de seturi 5 corespunde tuturor 6 seturi cu variabilă y. Prin urmare, numărul total de soluții este egal cu 31.
Sarcina 20.
Soluție: Amintiți-vă de echivalența principală, scrieți ecuația noastră în formularul:
Lanțul ciclic al implicațiilor înseamnă identitatea variabilelor, astfel încât ecuația noastră este echivalentă cu ecuația:
Această ecuație are două soluții atunci când toate sunt egale cu 1 sau 0.
Sarcina 21.
Câte soluții au o ecuație:
Soluție: La fel ca în problema 20, mergem pe implicații ciclice față de identitate, rescriind ecuația sub formă:
Construim copacul de soluții pentru această ecuație:
Sarcina 22.
Câte soluții au următorul sistem de ecuații?
Rezolvarea sistemului de ecuații logice prin înlocuirea variabilelor
Metoda de înlocuire variabilă este utilizată dacă unele variabile sunt incluse în ecuații numai ca o expresie specifică și în nici un caz diferit. Apoi, această expresie poate fi desemnată o nouă variabilă.
Exemplul 1.
Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, x6, x7, x8, care satisfac toate condițiile enumerate mai jos?
(x1 → x2) → (x3 → x4) \u003d 1
(x3 → x4) → (x5 → x6) \u003d 1
(x5 → x6) → (x7 → x8) \u003d 1
Ca răspuns, nu este nevoie să enumerați toate seturile de valori ale variabilelor x1, x2, x3, x4, x5, x6, x7, x8, sub care se efectuează acest sistem de egalități. Ca răspuns, trebuie să specificați numărul de astfel de seturi.
Decizie:
(x1 → x2) \u003d y1; (x3 → x4) \u003d y2; (x5 → x6) \u003d y3; (x7 → x8) \u003d y4.
Apoi puteți scrie sistemul sub forma unei ecuații:
(Y1 → Y2) ∧ (Y2 → Y3) ∧ (Y3 → Y4) \u003d 1. Conjuncția este 1 (adevărat), când fiecare operand acceptă valoarea 1. Acestea. Fiecare dintre implicațiile trebuie să fie adevărată, iar acest lucru se efectuează la toate valorile, cu excepția (1 → 0). Acestea. În tabelul valorilor variabilelor Y1, Y2, Y3, Y4, unitatea nu trebuie să stea la stânga din partea stângă a zeroului:
Acestea. Condițiile sunt efectuate pentru 5 seturi de Y1-Y4.
pentru că y1 \u003d x1 → x2, atunci valoarea y1 \u003d 0 este realizată pe un singur set X1, X2: (1, 0) și valoarea y1 \u003d 1 - pe trei seturi x1, x2: (0,0), (0) , 1), (1,1). Similar cu y2, y3, y4.
Deoarece fiecare set (X1, X2) pentru o variabilă Y1 este combinat cu fiecare set (X3, X4) pentru o variabilă Y2 etc., numărul de seturi de variabile x se înmulțește:
|
Numărul de seturi pe X1 ... X8 |
||||
Mutarea numărului de seturi: 1 + 3 + 9 + 27 + 81 \u003d 121.
Răspuns: 121
Exemplul 2.
Câte seturi diferite de variabile logice x1, x2, ... x9, y1, y2, ... y9, care satisfac toate condițiile enumerate mai jos?
(¬ (x1 ≡ y1) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2) ≡ (x3 ≡ y3)
(¬ (X8 ≡ Y8)) ≡ (X9 ≡ Y9)
In raspuns nu este necesarafișați toate seturile diferite de valori ale variabilelor X1, X2, ... X9, Y1, Y2, ... Y9, sub care se face acest sistem de egalități. Ca răspuns, trebuie să specificați numărul de astfel de seturi.
Decizie:
Vom înlocui variabilele:
(x1 ≡ y1) \u003d z1, (x2 ≡ y2) \u003d z2, .... , (x9 ≡ y9) \u003d z9
Sistemul poate fi scris ca o singură ecuație:
(¬ Z1 ≡ Z2) ∧ (¬ Z2 ≡ Z3) ∧ ... .. (¬ Z8 ≡ Z9)
Echivalența este adevărată numai dacă ambii operanzi sunt egali. Deciziile acestei ecuații vor fi două seturi:
| 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 |
pentru că zi \u003d (xi ≡ yi), atunci valoarea Zi \u003d 0 corespunde a două seturi (xi, yi): (0,1) și (1.0), iar valoarea Zi \u003d 1 este două seturi (xi, yi): (0 0 0 0 ) și (1,1).
Apoi primul set Z1, Z2, ..., Z9 corespunde la 2 9 seturi (x1, y1), (x2, y2), ..., (x9, y9).
Aceeași sumă corespunde celui de-al doilea set Z1, Z2, ..., Z9. Apoi, numai 2 9 +2 9 \u003d 1024 seturi.
Răspuns:1024
Rezolvarea sistemului de ecuații logice prin metoda determinării vizuale a recursiei.
Această metodă este utilizată dacă sistemul de ecuații este destul de simplu și ordinea creșterii numărului de seturi la adăugarea de variabile este evidentă.
Exemplul 3.
Câte soluții diferite au un sistem de ecuații
¬x9 ∨ x10 \u003d 1,
unde X1, X2, ... X10 - Variabile logice?
Ca răspuns, nu este nevoie să enumerați toate seturile de valori X1, X2, ... X10, la care se face acest sistem de egalități. Ca răspuns, trebuie să specificați numărul de astfel de seturi.
Decizie:
Efectuați prima ecuație. Dysiauncția este de 1, dacă cel puțin unul dintre operanții săi este 1. Aceștia. Deciziile sunt kituri:
Pentru X1 \u003d 0, există două valori x2 (0 și 1) și pentru x1 \u003d 1, doar o singură valoare x2 (1), astfel încât setul (X1, X2) este o soluție a ecuației. Total 3 seturi.
Adăugați o variabilă x3 și luați în considerare cea de-a doua ecuație. Este similar cu prima, înseamnă că pentru X2 \u003d 0 există două valori x3 (0 și 1) și pentru x2 \u003d 1, doar o singură valoare x3 (1), astfel încât setul (x2, x3) este o soluție a ecuației. Total 4 seturi.
Este ușor de observat că atunci când adăugați o altă variabilă, se adaugă un set. Acestea. Formula recursivă pentru numărul de seturi pe variabilele (I + 1):
N i +1 \u003d n i + 1. Apoi pentru zece variabile, obținem 11 seturi.
Răspuns: 11
Soluția de sisteme de ecuații logice de diferite tipuri
Exemplul 4.
Câte seturi diferite de valori ale variabilelor logice x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, care satisfac toate condițiile enumerate mai jos?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) \u003d 1
(Y 1 → Y 2) ∧ (Y 2 → Y3) ∧ (Y 3 → Y 4) \u003d 1
(Z 1 → Z2) ∧ (Z2 → Z3) ∧ (Z 3 → Z4) \u003d 1
x 4 ∧ Y 4 ∧ Z 4 \u003d 0
In raspuns nu este necesar Afișați toate seturile diferite de valori ale variabilelor x 1, ..., x 4, y 1, ..., Y4, Z 1, ..., Z4, sub care se face acest sistem de egalități.
Ca răspuns, trebuie să specificați numărul de astfel de seturi.
Decizie:
Rețineți că cele trei ecuații ale sistemului sunt aceleași pe diferite seturi independente de variabile.
Luați în considerare prima ecuație. Conjuncția este adevărată (egală cu 1) numai atunci când toți operanții săi sunt adevărați (egali cu 1). Implicația este 1 pe toate seturile, cu excepția (1.0). Aceasta înseamnă că soluția primei ecuații va fi astfel de kituri x1, x2, x3, x4, în care 1 nu merită stânga 0 (5 seturi):
În mod similar, soluțiile a doua și a treia ecuații vor fi absolut aceleași kituri Y1, ..., Y4 și Z1, ..., Z4.
Acum analizăm a patra ecuație a sistemului: X 4 ∧ Y 4 ∧ Z 4 \u003d 0. Soluția va fi toate kiturile X4, Y4, Z4, în care cel puțin una dintre variabile este 0.
Acestea. Pentru X4 \u003d 0, toate seturile posibile (Y4, Z4) sunt potrivite și pentru X4 \u003d 1, seturile (Y4, Z4) sunt adecvate, în care este prezent cel puțin un zero: (0, 0), (0,1 ), (1, 0).
|
Numărul de seturi |
||||
Numărul total de seturi 25 + 4 * 9 \u003d 25 + 36 \u003d 61.
Răspuns: 61
Soluția de sisteme de ecuații logice prin metoda de construire a formulelor recurente
Metoda de construire a formulelor recurente este utilizată în rezolvarea sistemelor complexe, în care ordinea creșterii numărului de seturi nu este evidentă, iar construcția arborelui este imposibilă datorită volumelor.
Exemplul 5.
Câte seturi diferite de variabile logice x1, x2, ... x7, y1, y2, ... x7, y1, y2, ... Y7, care satisfac toate condițiile enumerate mai jos?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) \u003d 1
(X2 ∨ Y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) \u003d 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) \u003d 1
Răspunsul nu are nevoie să prezinte toate seturile de valori ale variabilelor X1, X2, ..., X7, Y1, Y2, ..., X7, Y1, Y2, ..., Y7, sub care Acest sistem de egalități se face. Ca răspuns, trebuie să specificați numărul de astfel de seturi.
Decizie:
Rețineți că primele șase ecuații de sistem sunt aceleași și diferă numai într-un set de variabile. Luați în considerare prima ecuație. Soluția sa va fi următoarele seturi de variabile:
Denota:
numărul de seturi (0,0) pe variabile (x1, y1) printr-un 1,
numărul de seturi (0,1) pe variabile (x1, y1) prin b 1,
numărul de seturi (1.0) asupra variabilelor (X1, Y1) prin C 1,
numărul de seturi (1.1) asupra variabilelor (X1, Y1) prin D 1.
numărul de seturi (0,0) pe variabile (x2, y2) prin 2,
numărul de seturi (0,1) pe variabile (x2, y2) prin b 2,
numărul de seturi (1.0) pe variabile (X2, Y2) prin C 2,
numărul de seturi (1.1) asupra variabilelor (X2, Y2) prin D 2.
Din soluțiile din lemn, vezi asta
A 1 \u003d 0, B 1 \u003d 1, C 1 \u003d 1, D 1 \u003d 1.
Rețineți că setul (0,0) de pe variabile (x2, y2) este obținut din seturile (0,1), (1,0) și (1,1) pe variabilele (X1, Y1). Acestea. A 2 \u003d B 1 + C 1 + D 1.
Setul (0,1) de pe variabile (x2, y2) este obținut din seturile (0,1), (1,0) și (1,1) pe variabilele (X1, Y1). Acestea. B 2 \u003d B 1 + C 1 + D 1.
În mod similar, argumentând, observăm că cu 2 \u003d B 1 + C 1 + D 1. D 2 \u003d D 1.
Astfel, obținem formule recurente:
A I + 1 \u003d B I + C I + D I
B I + 1 \u003d B I + C I + D i
C I + 1 \u003d B I + C I + D i
D I + 1 \u003d A I + B I + C I + D I
Faceți o masă
| Seturi | Proprii. | Formulă |
Numărul de seturi |
||||||
| i \u003d 1. | i \u003d 2. | i \u003d 3. | i \u003d 4. | i \u003d 5. | i \u003d 6. | i \u003d 7. | |||
| (0,0) | A I. | A I + 1 \u003d B I + C I + D I | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B I. | B I + 1 \u003d B I + C I + D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C I. | C I + 1 \u003d B I + C I + D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D I. | D i + 1 \u003d d i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ultima ecuație (X7 ∨ Y7) \u003d 1 satisface toate trusele, cu excepția celor în care X7 \u003d 0 și Y7 \u003d 0. Tabelul nostru este numărul de astfel de seturi de 7.
Apoi, numărul total de seturi este B 7 + C 7 + D 7 \u003d 127 + 127 + 1 \u003d 255
Răspuns: 255
UDC 004.023.
Semenov Serghei Maksimovich.
Universitatea de Stat din Economie și Serviciul Vladivostok Rusia. Vladivostok.
Pe o metodă de rezolvare a sistemelor de ecuații logice
Se ia în considerare o metodă de determinare a numărului de soluții ale unui sistem de ecuații logice. Metoda se bazează pe construirea de soluții din lemn și determină rapoartele recurente pentru N. Aplicarea metodei dezvoltate oferă o abordare constructivă pentru rezolvarea problemei B15 EGE.
Cuvinte cheie și fraze: Sistem de ecuații logice, soluții din lemn, relații recurente, B15, EGE.
În practică, sistemul ecuațiilor logice este util în dezvoltarea dispozitivelor logice digitale. Una dintre sarcinile EGE asupra informaticii științei este dedicată rezolvării sistemelor de ecuații logice. Din păcate, diverse moduri cunoscute de a rezolva această problemă nu permit să formeze o singură abordare pentru rezolvarea acestei sarcini. Ca urmare, soluția problemei determină dificultăți mari pentru absolvenți. Oferim o modalitate de a rezolva sistemele de ecuații logice, care permite unui absolvent să urmeze un algoritm bine definit. Ideea acestei metode este prezentată în. Am aplicat și am dezvoltat această idee (construirea unei soluții de copac), aproape folosind tabelele de adevăr pentru întregul copac. La rezolvarea diferitelor probleme, sa dovedit că numărul de soluții ale multor sisteme de ecuații logice este supus unor rapoarte recurente, cum ar fi Fibonacci, etc.
Sisteme de ecuații logice. Vom adera la următoarele denumiri: disjuncționare (+), conjuncție (), cu excepția sau (©), implicații (-\u003e ■), echivalență (\u003d), negare (- ■). În figuri, cercul întunecat indică 1, iar cercul de lumină este 0. FL - numărul de soluții la X1, egal cu 1. Numărul de soluții la X1, egal cu 0. N - numărul de variabile din sistemul de ecuații. F (n) \u003d f1 (n) + f0 (n) este numărul total de soluții.
Sarcina 1. Este necesar să găsiți numărul de soluții ale sistemului de ecuații (numărul de testare 2)
Mai întâi presupunem că x1 \u003d 1. Apoi, pentru prima ecuație, valorile lui X2 și XS pot fi orice. Astfel, copacul este construit la al treilea nivel. Apoi, luând în considerare x2 și xs, alegeți x4. După aceea, algoritmul se repetă pentru fiecare triplu de variabile (figura 1). Pornind de la cel de-al patrulea nivel, se poate observa că FL (4) \u003d FL (3) + FL (1), FL (5) \u003d FL (4) + FL (2). Astfel, obținem FL (N) \u003d FL (N-1) + FL (N-3) (1)
Smochin. 1. Sarcina 1.
Din ecuația (1) urmează:
BH (8) \u003d 16 + 7 \u003d 23,
FL (9) \u003d 23 + 11 \u003d 34.
Pentru a construi un copac de la zero, puteți utiliza ramura inferioară din fig. 1. Este ușor de văzut că repetă copacul principal, dar cu o trecere la dreapta la 2, adică
Total, F (9) \u003d FL (9) + FO (9) \u003d 34 + 16 \u003d 50.
La construirea unei soluții de copac, puteți stabili vizual relații recurente pentru a determina numărul de soluții la N.
Principiul inducției matematice citește: Să existe o secvență de declarații FL, F2, FD și lăsați prima declarație corectă. Putem dovedi că fantezia declarației FN urmează credincioșia Fn + L. Apoi toate afirmațiile din această secvență sunt adevărate.
Luați în considerare Fig. 2 pentru sarcina 1.
k2\u003e 3 x5 hb x7
Smochin. 2. Analiza copacului de soluții
Figura 2 prezintă formele având un vârf total (combinații de valori variabile) pentru primele cinci ecuații ale sistemului. În fiecare ecuație sunt implicate trei variabile, astfel încât cifrele sunt compilate din valorile a trei variabile (trei nivele de lemn). Pentru a identifica cifrele, ar fi posibilă introducerea notării. Cu toate acestea, vom continua după cum urmează: Fiecare cifră este pusă în concordanță cu numărul de componente ale cercurilor sale (valori variabile). Apoi obținem următoarele ecuații pentru secvență:
4. 7, 4, 4, 1, 7
5. 7, 4, 4, 1, 7, 7, 4.
Din ecuația 4, se poate observa că cifrele pentru ecuația n constau în figurile ecuației N-1 și cifrele ecuației N-3. Este important ca să nu existe alte cifre și nu pot fi pentru acest tip de ecuații, adică tranziția de la o ecuație la altul este produsă prin creșterea numărului de cifre dintr-un set limitat în conformitate cu regulile strict definite. Acest fapt este de bază pentru a afirma inducția că pentru ecuația n + 1 Un set de cifre va consta din figuri ale ecuației n și figuri ale ecuației N-2.
O altă modalitate de a identifica cifrele este de a determina numărul de valori ale variabilelor la ultimul nivel pentru această ecuație, adică trebuie să treceți de la numărul ecuației la numărul de copac, deoarece trebuie să determinăm Numărul de soluții pentru sistemul de ecuații, apoi pentru copacul construit obținem o secvență: 1, 2, 4, 5, 7, 11, 16. Pentru această secvență, formula este validă: FN \u003d FN - 1 + FN- 3.
În conformitate cu argumentele noastre, această formulă va fi adevărată pentru n + 1, și în inducție și pentru orice N.
Metoda specificată de probă poate fi utilizată pentru orice sisteme de acest tip. În practică, este suficient să se determine raportul recurent pentru nivelul N, deoarece se bazează pe un set limitat de cifre și metode ale transformărilor lor în timpul tranziției de la ecuația corespunzătoare nivelului N la ecuația corespunzătoare n + 1 nivel.
Sarcina 2. Este necesar să găsim numărul de soluții ale sistemului de ecuații (4.16)
(X1 \u003d x2) + (x1 \u003d x3) \u003d 1 (x2 \u003d xs) + (x2 \u003d x4) \u003d 1 (xs \u003d x4) + (xs \u003d x5) \u003d 1 (x4 \u003d x5) + (x4 \u003d x6) \u003d 1 (x5 \u003d x6) + (x5 \u003d x7) \u003d 1
Xi x2 xs\u003e: 1 x5 hb x7
Smochin. 3. Sarcina 2.
Pentru a obține numărul de soluții ale sarcinii 2, a fost posibil să nu construiți complet copacul de soluții (fig.3), deoarece este evident că FL (N) \u003d N. În mod similar, FO (N) \u003d N. Total F (7) \u003d 7 + 7 \u003d paisprezece.
Task 3. Este necesar să găsiți numărul de soluții ale sistemului de ecuații (numărul de testare 1)
(X1 ^ x2) ■ (x2 ^ xs) ■ (xs ^ x4) ■ (x4 ^ x5) \u003d 1
(Yl ^ y2) ■ (U2 ^ yz) ■ (yz ^ y4) ■ (y4 ^ y5) \u003d 1
(Yl ^ x1) ■ (U2 ^ x2) ■ (yz ^ xs) ■ (y4 ^ x4) ■ (y5 ^ x5) \u003d 1
Figura 4 prezintă copacii de soluții pentru x și y și sunt afișate tabelele de adevăr corespunzătoare.
Smochin. 4. Sarcina 3.
Dintre primele două ecuații, deoarece X și Y sunt independenți, rezultă că numărul total de soluții F (5) \u003d 6 * 6 \u003d 36. Pentru a lua în considerare cea de-a treia ecuație, este necesar să se calculeze pentru fiecare variabilă Y, Ce număr de seturi din tabelul X nu satisface ecuația. Implicația yi ^ xi \u003d 0, dacă yi \u003d 1 și xi \u003d 0. Cu alte cuvinte, pentru yl \u003d 1, a treia ecuație nu îndeplinește toate liniile din tabelul x, unde x1 \u003d 0. Numărul de Astfel de corzi sunt 5. pentru Y2 \u003d 1 rânduri - 4, etc. Numărul total de linii care nu satisfac a treia ecuație este egal cu 5 + 4 + 3 + 2 + 1 \u003d 15.
Astfel, numărul total de soluții admise este egal cu 36-15 \u003d 21. Sarcina 4. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (4.17.a)
(X1 \u003d x2) + (x1 \u003d x3) \u003d (x2 \u003d x3) + (x2 \u003d x4) + (x4 \u003d x6) \u003d (x5 \u003d x6) + (x5 \u003d x7) \u003d (Hb \u003d X7) + (hb \u003d x8) \u003d (x5 \u003d x6) \u003d 0
Smochin. 5. Sarcina 4.
Pentru acest exemplu, este dificil să se determine Formula finală F (n), este mai ușor să construim un arbore de soluții până la capăt (sau cel puțin la x6). Figura 5 prezintă copacul de soluții construite. Ca rezultat, obținem F (8) \u003d FL (8) + FO (8) \u003d 5 + 5 \u003d 10.
Sarcina 5. Este necesar să găsim numărul de soluții ale sistemului de ecuații (4.17.b)
(X1 \u003d x2) + (x1 \u003d x3) \u003d 1 (x2 \u003d x3) \u003d 1 (x3 \u003d x4) + (x3 \u003d x5) \u003d 1 (x4 \u003d x5) + (x4 \u003d x6) \u003d 1 (x5 \u003d x6) + (x5 \u003d x7) \u003d 1 (x6 \u003d x8) \u003d 1
Pentru acest exemplu, conform celui anterior, este mai ușor să se construiască o soluționare a copacilor până la capăt (figura 6). Ca rezultat, obținem F (8) \u003d FL (8) + FO (8) \u003d 7 + 7 \u003d 14.
Sarcina 6. Este necesar să găsiți numărul de soluții ale sistemului de ecuații ([!]\u003e 4.17.V)
(X! 8 "x2) + (x2Hz) \u003d 1 (x2fx) + (xs \u003d x4) \u003d 1 (xs8" x4) + (x4 \u003d x5) \u003d 1 (x4 © x5) + (x5 \u003d hb) \u003d 1 (X5FHB) + (HB \u003d X7) \u003d 1 (HB © X7) + (X7 \u003d x8) \u003d 1 Soluțiile arborele este prezentat în fig. 7.
Xi x2 xs x4 x5 x6 x7 x8 xi x2 xs x4 x5 x6 x7 x8
Smochin. 6. Sarcina 5 Fig. 7. Sarcina 6.
Pentru acest sistem de ecuații, nu a fost posibilă construirea unui copac complet de soluții, deoarece deja din a treia-a patra etapă este clar că F1 (N) \u003d N. Este ușor de văzut că FO (N) poate fi obținut de la un copac care începe la al doilea nivel de la zero. Apoi pentru (n) \u003d n. Total, f (8) \u003d fl (8) + FO (8) \u003d 8 + 8 \u003d 16.
Sarcina 7. Trebuie să găsiți numărul de soluții ale sistemului de ecuații
(X4H5) + (X4 © X6) \u003d 1 (x5 © Hb) + (X5 © X7) \u003d 1
Rețineți că dacă X! \u003d X2 \u003d 1, prima ecuație este efectuată la XS \u003d 0. Vom construi mai întâi un copac pentru XL \u003d x2 \u003d 1 (figura 8). Apoi numărul de soluții FL (N) \u003d FLL (N) + FLO (N).
Xi x2 xs x4 x5 x6 x7 x8
Smochin. 8. Sarcina 7.
Din Figura 8, se poate observa că numărul de soluții F11 (N) \u003d F11 (N-1) + F11 (N-2). Cu alte cuvinte, numărul de soluții este descris de numerele Fibonacci. Cea de-a doua ramură a copacului pentru F10 nu poate fi construită, după cum se dovedește din fig. 1, pornind de la al doilea nivel. Apoi F10 (N) \u003d F11 (n + 1). În cele din urmă, obținem acest FLL (8) \u003d 1z și FLL (8) \u003d FLL (9) \u003d 1z + 8 \u003d 21. Apoi FL (8) \u003d FLL (8) + FLL (8) \u003d 1z + 21 \u003d C4.
Pentru a obține F0 (N), nu este de asemenea necesar să se construiască arborele de soluții, deoarece este obținut din fig. 1 pornind de la al treilea nivel. Apoi pentru (n) \u003d FLL (N + 2). De aici obținem acest lucru (8) \u003d FLL (10) \u003d FLL (9) + FLL (8) \u003d 21 + 1z \u003d C4. Astfel, numărul total de soluții F (8) \u003d F1 (8) + F0 (8) \u003d Z4 + Z4 \u003d 68.
Sarcina 8. Este necesar să găsim numărul de soluții ale sistemului de ecuații ([S], sarcina 2)
(X1 + X2) ^ (XS + X4) \u003d 1 (xs + x6) \u003d 1 (x5 + x6) ^ (x7 + x8) \u003d 1 (x7 + x8) ^ (x9 + x10) \u003d 1.
Face o substituție (x1 + x2) \u003d yl, etc. Și obținem sistemul de ecuații:
^ ^ Y2 \u003d 1 y2 ^ yz \u003d 1 yz ^ y4 \u003d 1 y4 ^ y5 \u003d 1
Arborele de soluții și tabelul de adevăr pentru acest sistem coincid exact cu arborele și tabelul prezentat în fig. 4. Având în vedere substituția, menționăm că expresia (X1 + X2) este egală cu una în trei cazuri (cu excepția opțiunii, când ambele variabile sunt zero).
Deoarece variabilele Y sunt independente, atunci pentru primul rând al tabelului adevărului prezentat în fig. 4, numărul de combinații diferite este de 35, pentru a doua linie - 34 etc. Numărul total de combinații diferite este de 35 + 34 + 33 + 32 + 31 + 30 \u003d 364.
Sarcina 9. Este necesar să găsiți numărul de soluții ale sistemului de ecuații (, sarcina 4)
(^ ^) ■ (-x ^ x) ■ № ^ x) ■ (-x ^ kz) \u003d 1 No. ^ y2) ■ (U1 ^ yz) ■ (-g1 ^ y4) ■ (U1 ^ y5) \u003d 1 (-x + y 1) ■ (-x + y5) \u003d 1
Pentru x și y avem următorii copaci de soluții
Smochin. 9. Sarcina 8.
Având în vedere cea de-a treia ecuație, obținem următoarele patru seturi de combinații:
A - C: 4 * 4 \u003d 16 ((- £ 1 + y 1) ■ (-x + y5) \u003d (0 + 1) ■ (0 + 1) \u003d 1) B - C: 4 * 4 \u003d 16 ( (-X + y 1) ■ (-x + y5) \u003d (1 + 1) ■ (1 + 1) \u003d 1) A - D: \u003d 0 (0 + 0) ■ (-x + y5) \u003d 0) B - D: 4 * 4 \u003d 16 (1 + 0) ■ (1 + y5) \u003d 1) total este de 48 de seturi de soluții.
Sarcina 10. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (^ 1 \u003d b) + (xz \u003d x)) ■ \u003d à) + -FZ \u003d x4)) \u003d 1 ((x3 x4) + ( x5 \u003d x6)) ■ (- (x \u003d x) + - (x \u003d x6)) \u003d 1 ((x5 \u003d x6) + ^ 7 \u003d x „)) ■ (- (x \u003d x6) + - (^ 7 \u003d x8)) \u003d 1
((X7 \u003d x8) + (x9 \u003d xlo)) ■ (- ^ 7 \u003d x8) + \u003d xLO)) \u003d 1 Vom înlocui: (xl \u003d b) \u003d yl (xz \u003d x4) \u003d y2
(X5 \u003d x) \u003d yz (x7 \u003d x8) \u003d y4 (x9 \u003d x10) \u003d y5
(Y ^ 2) ■ (- + ^) \u003d 1
(Y2 + YZ) ■ № + TZ) \u003d 1
(Yz + y4) ■ № + ^) \u003d 1
(Y4 + Y5) ■ (^ 4 + ^) \u003d 1
Figura 10 prezintă copacul de soluții
U1 u2 uz u4 u5
Smochin. 10. Sarcina 10.
Sarcina 11. Este necesar să găsim numărul de soluții ale sistemului de ecuații (Exemplul 2)
X1 + x2 \u003d 1 -х2 + xs \u003d 1
Figura 11 prezintă arborele de soluții. Ne-am limitat la cele patru nivele în loc de zece, deoarece este evident că F1 (N) \u003d 1 și F0 (N) \u003d N. atunci P (S) \u003d P1 (S) + BOSI) \u003d 1 + N. în cazul nostru p (10) \u003d 1 + 10 \u003d 11.
Smochin. 11. Sarcina 11.
Sarcina 12. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (, exemplul H)
(X1 \u003d x2) + (x2 \u003d xs) \u003d 1
(X1 \u003d xs) + (xs \u003d x4) (x1 \u003d x4) + (x1 \u003d x5) + (x5 \u003d x6) (x1 \u003d x6) + (x6 \u003d x7) (x1 \u003d x7) + (X7 \u003d x8) (x1 \u003d x) + (x8 \u003d x9) (x1 \u003d x9) + (x9 \u003d x10) (x1 \u003d x10) \u003d 0
Smochin. 12. Sarcina 12.
Prin construirea arborelui de soluții de la „1“ (limita la cinci niveluri), observăm că FL (n) \u003d N. și valorile HN constau din N-1 „0“ valori și o valoare „1 ". Cu toate acestea, ultima ecuație din sistemul nostru interzice valoarea "1" pentru X10. Prin urmare, numărul de soluții FL (10) \u003d 10 - 1. Nu este greu de observat că arborele de soluții de la „0“ va fi simetric (în loc de zerouri va fi de unități). Prin urmare, F0 \u003d 10 - 1. În cele din urmă
F (n) \u003d 2 x 9 \u003d 18.
Sarcina 13. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (, Exemplul 4)
- (x1 \u003d x2) + (xs \u003d x4) \u003d 1
- (xs \u003d x4) + (x5 \u003d x) \u003d 1
- (x \u003d x) + (x7 \u003d x) \u003d 1
- (x7 \u003d x8) + (x9 \u003d x10) \u003d 1
Vom înlocui:
(X1 \u003d x2) \u003d yl
(X5 \u003d x) \u003d yz
(X7 \u003d x8) \u003d y4
(X9 \u003d x10) \u003d y5
Rescriem un sistem de ecuații cu înlocuirea:
Din sarcina 11, se poate observa că F (5) \u003d 5 + 1 \u003d 6. Tabelul Adevărului este prezentat în fig. 13.
U1 u2 uz u4 u5
Smochin. 13. Sarcina 13.
Având în vedere substituția, observăm că expresia ^ \u003d x2) este egală cu una (sau zero) în două cazuri (când valorile variabilelor coincid). Având în vedere independența variabilelor pentru fiecare rând al tabelului, obținem că numărul de seturi de soluții este 25 \u003d 32. Numărul total de seturi de soluții este de 6 * 32 \u003d 192.
Sarcina 14. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (sarcina 1)
((X \u003d x) ■ (xz \u003d x4)) + (x \u003d x)) \u003d 0 ((xz \u003d x4) ■ (x5 \u003d x6)) + (4x3 \u003d x4) ■ - (X \u003d x6)) \u003d 0
(X5 \u003d x) ■ (x7 \u003d x8)) + (- (x \u003d x6) ■ 4x7 \u003d x8)) \u003d 0 ((x7 \u003d x8) ■ (x9 \u003d x ",)) + (- (^ 7 \u003d x8) ■ ^ 9 \u003d xlo)) \u003d 0 Vom înlocui:
Kommersant) \u003d yl (x \u003d ^ 4) \u003d y2
(X5 \u003d x6) \u003d yz ^ 7 \u003d x8) \u003d y4 ^ 9 \u003d xlo) \u003d y5
Rescriem un sistem de ecuații cu înlocuirea:
(UL) + (-U "■ -U2) \u003d 0
(Y2 YZ) + (-U2 ■ -U3) \u003d 0 (U3-U4) + (-U3 ■ -U4) \u003d 0 (U4-U5) + (-U4 ■ -U5) \u003d 0
(U2 \u003d yz) \u003d 0 (UZ \u003d U4) \u003d 0 (U4 \u003d U5) \u003d 0
Figura 14 prezintă copacul de soluții
U1 u2 uz u4 u5
Smochin. 14. Sarcina 14.
Având în vedere substituția, observăm că expresia (X1 \u003d x2) este egală cu una (sau zero) în două cazuri (când valorile variabilelor coincid). Ținând cont de independența variabilelor pentru fiecare copac, obținem că numărul de seturi de soluții este 25 \u003d з2. Numărul total de seturi de soluții este de 64.
Sarcina 15. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (sarcină 2)
(X4 x5) + (-H4 -х5) + (x4 \u003d x) \u003d 1
(X5 x) + (-х -х6) + (x5 \u003d x7) \u003d 1
(X x7) + (-х -х7) + (x \u003d x8) \u003d 1
(X7 x) + (-х7 -х8) + (x7 \u003d x9) \u003d 1
(X8 x9) + (-х -х9) + (x8 \u003d x10) \u003d 1
(X1 \u003d x2) + (x1 \u003d xs) \u003d 1
(X \u003d xs) + (x2 \u003d x4) \u003d 1
(Xs \u003d x4) + (xs \u003d x5) \u003d 1
(X4 \u003d x5) + (x4 \u003d x) \u003d 1
(X5 \u003d x6) + (x5 \u003d x7) \u003d 1
(X \u003d x7) + (x6 \u003d x8) \u003d 1
(X7 \u003d x8) + (x7 \u003d x9) \u003d 1
(X \u003d x9) + (x8 \u003d x10) \u003d 1
Dar acest sistem repetă sistemul de la sarcina 5, numai fără condiția de limitare pentru n \u003d 10. Apoi numărul de soluții este F (N) \u003d F1 (N) + F0 (N) \u003d N + N. la n \u003d 10 Obținem f (n) \u003d 20.
Sarcina 16. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (, sarcina 3)
(X1 x2) + (-х1 -х2) + (x1 \u003d xs) \u003d 1
(X2 xs) + (-m-khz) + (x2 \u003d x4) \u003d 1
(XS X4) + (-KHz -х4) + (XS \u003d x5) \u003d 1
(X4 x5) + (-х -х5) + (x4 \u003d hb) \u003d 1
(X5 Hb) + (-H-CHB) + (x5 \u003d x7) \u003d 1
(HB X7) + (-CHB-X7) + (HB \u003d X8) \u003d 1
(X7 x8) + (-х7 -х8) + (x7 \u003d x9) \u003d 1
(X8 x9) + (-х8 -х9) + (x8 \u003d x10) \u003d 0
Acest sistem de ecuații, ca și în sarcina anterioară, poate fi rescris ca:
(Xi \u003d x2) + (xi \u003d xs) \u003d 1 (x \u003d xs) + (x2 \u003d x) \u003d 1 (xs \u003d x) + (xs \u003d x5) \u003d 1 (x \u003d x5) + (x4 \u003d hb) \u003d 1 (x5 \u003d hb) + (x5 \u003d x7) \u003d 1 (Hb \u003d x7) + (HB \u003d x8) \u003d 1 (x \u003d x8) + (x7 \u003d x9) \u003d 1 (x \u003d x9) + (x8 \u003d Xx) \u003d 0
Din ultima ecuație este ușor să se verifice că după n \u003d 8 numărul de soluții încetează să crească. Apoi f (10) \u003d f (8) \u003d 8 + 8 \u003d 16.
Sarcina 17. Este necesar să găsim numărul de soluții ale sistemului de ecuații (, sarcina 4)
(X1 x2) + (-х1 -х2) + (x2 xs) + (-х2 -khz) \u003d 1
(X2 XS) + (-H2 -KHz) + (XS X) + (-KHz ■ -х4) \u003d 1
(XS X) + (-KHz -х4) + (x4 x5) + (-х4 -х5) \u003d 1
(X4 x) + (-x5) + (x5 Hb) + (-H5-CHB) \u003d 1
(X5 Hb) + (-H-CHB) + (HB X7) + (-CHB ■ -х7) \u003d 1
(HB X7) + (-KHB-X7) + (x7 x8) + (-х7 -х8) \u003d 1
(X7 x) + (-х7 -х8) + (x8 x9) + (-х8 -х9) \u003d 1
(X8 x9) + (-х8 -х9) + (x9 x10) + (-х9 ■ -х10) \u003d 1
Rețineți că sistemul de ecuații poate fi rescris ca:
(X \u003d x2) + (x \u003d xs) \u003d 1 (x \u003d xs) + (x \u003d x) \u003d 1 (xs \u003d x4) + (x4 \u003d x5) \u003d 1 (x \u003d x5) + (x5 \u003d hb) \u003d 1 (x5 \u003d hb) + (Hb \u003d x7) \u003d 1
(Hb \u003d x7) + (x7 \u003d x) \u003d 1 (x7 \u003d x8) + (x8 \u003d x9) \u003d 1 (x9 \u003d x 9) + (x9 \u003d x10) \u003d 1
În figura 15, arborele este construit la nivelul al cincilea și se poate observa că numărul de soluții este descris de numerele Fibonacci, care este, FL (N) \u003d FL (N-1) + FL (N-2 ). Apoi FL (10) \u003d 89. Este ușor de verificat faptul că pentru F0 (N) arborele va fi simetric. Prin urmare, FO (10) \u003d 89. b (10) \u003d P1 (10) + PO (10) \u003d 89 + 89 \u003d 178.
Smochin. 15. Sarcina 17.
Sarcina 18. Este necesar să se găsească numărul de soluții ale sistemului de ecuații (, sarcina 5)
(X1 x2) + (-х1 -х2) + (x2 xs) + (-х2 ■ -khz) \u003d 1
(X2 XS) + (-H -HZ) + (XS X4) + (-KHz -х4) \u003d 1
(XS X4) + (-KHz -х4) + (x4 x5) + (-х4 ■ -х5) \u003d 1
(X4 x5) + (-х4 -х5) + (x Hb) + (-х5 ■ -HB) \u003d 1
(X5 Hb) + (-H5 -HB) + (HB X7) + (-KB ■ -х7) \u003d 1
(HB X7) + (-HB -H7) + (x7 x8) + (-х7 ■ -х8) \u003d 1
(X7 x8) + (-х7 -х8) + (x8 x9) + (-х8 -х9) \u003d 1
(X8 x9) + (-х8 -х9) + (x9 x10) + (-х9 ■ -х10) \u003d 0
Rețineți că sistemul de ecuații poate fi rescris ca:
(X \u003d x2) + (x2 \u003d x3) \u003d 1 (x2 \u003d xs) + (xs \u003d x4) \u003d 1
(Xs \u003d x) + (x4 \u003d x5) \u003d 1 (x \u003d x5) + (x5 \u003d hb) \u003d 1 (x \u003d hb) + (HB \u003d x7) \u003d 1 (Hb \u003d x7) + (X7 \u003d X8) \u003d 1 (x7 \u003d x8) + (x8 \u003d x9) \u003d 1 (x8 \u003d x 9) + (x \u003d x10) \u003d 0
Sarcina 18 este similară cu sarcina 17, cu toate acestea, cea de-a doua ecuație conduce la faptul că, de la nivelul al șaptelea, numărul de soluții nu crește. Ca rezultat, F (10) \u003d FL (10) + FO (10) \u003d FL (7) + FO (7) \u003d 21 + 21 \u003d 42.
Sarcina 19. Este necesar să găsim numărul de soluții ale sistemului de ecuații (, sarcina b)
(X \u003d x2) + (x \u003d x10) \u003d 1 (x \u003d xs) + (x2 \u003d x10) \u003d 1 (xs \u003d x4) + (x \u003d x10) \u003d 1 (x \u003d x5) + (x \u003d x10) \u003d 1 (x \u003d hb) + (x5 \u003d x10) \u003d 1 (Hb \u003d x7) + (Hb \u003d x10) \u003d 1 (x7 \u003d x) + (x \u003d x10) \u003d 1 (x8 \u003d x9) + (x \u003d X10) \u003d 1 (x9 \u003d x10) + (x9 \u003d x10) \u003d 1 (x \u003d x10) \u003d 0
- - - -*- - - -*-despre
Smochin. 1b. Sarcina 19.
Copacii de soluții pentru obținerea F1 (N) și F0 (N) sunt prezentate în fig. 1b. Cu toate acestea, ecuația (X9 \u003d x10) \u003d 1 nu poate fi efectuată. Prin urmare, sistemul de ecuații nu are soluții.
Sarcina 20. Este necesar să găsim numărul de soluții ale sistemului de ecuații (sarcina 7)
(X ^ x2) + (x ^ xz) \u003d 1 (x2 ^ xs) + (x2 * x4) \u003d 1 (xs ^ x4) + (xs ^ x5) \u003d 1 (x ^ x5) + (x4 ^ hb) \u003d 1 (x5 ^ hb) + (x5 ^ x7) \u003d 1 (HB ^ x7) + (HB ^ x8) \u003d 1
(X7 ^ xs) + (x7 ^ x9) \u003d 1 (xs ^ x9) + (xs ^ x10) \u003d 1
Figura 17 prezintă copacul de soluții din "1".
Smochin. 17. Sarcina 20 Fig. 18. Sarcina 20.
În loc de zece nivele, am limitat la cinci, deoarece sarcina este similară cu sarcina 17. Cu toate acestea, de la "0" arborele va arăta diferit (figura 18).
Rețineți că F0 (n) \u003d Fx (n + 1) - 1. FX Apoi , (10) \u003d 89, și F0 (10) \u003d FX (11) - 1 \u003d 144 - 1. Total, F (10) \u003d F1 ( 10) + F0 (10) \u003d 89 + 143 \u003d 232.
În concluzie, oferim un program pe un VBA de bază, cu care puteți rezolva sistemul ecuațiilor logice. Programul poate fi necesar în compilarea noilor sisteme de ecuații. Figura 19 prezintă programul cu care este soluționat sistemul de ecuații din sarcina 7.
În programul prezentat în fig. 19, o matrice M și o variabilă C conțin valori ale variabilelor care satisfac sistemul de ecuații din sarcină 7. Programul oferă răspunsul 68. Programul utilizează faptul că numărul de seturi diferite de valori ale logicii N Variabilele sunt de 2N. Pentru a obține toate seturile, trebuie să efectuați un ciclu de la 0 la 2N-1. Variabila ciclului la fiecare etapă este tradusă în sistemul binar, rezultatul este scris la o matrice M, iar apoi sunt verificate deja condițiile din sistemul de ecuație. Pentru a rezolva un alt sistem de ecuații, este suficient pentru a schimba dimensiunea M matrice M, modificați valoarea variabilei VG (egală cu dimensiunea) și schimbe valabilitatea verificării.
Dim m (s) ca număr întreg, k ca număr întreg, J. Ca număr întreg. _ J ca număr întreg. N ca număr întreg, vg ca număr întreg cu ca șir vg \u003d s j-0
Pentru 1 la 2 ■ "" ■ vg "de ^ de la 1 la 2n. Unde n \u003d, g pentru k \u003d 1 la vg
N \u003d) .- 1: binar e PR C instalat E nnO începe de la zero k \u003d 1
Do "^ tiils n\u003e 0" e binar xuramp m (k) \u003d n mod 2 k \u003d n ■ 2 k \u003d k +! Buclă.
IFIM (L) O m (2) sau m (l) 0-Ni (3)) și "Condiții de ecuație (m (2) c \u003d "" "Variabila din fiecare pas va fi capabilă să conțină soluția sistemului pentru k \u003d 1 acel vg c \u003d C - FOIMAT (M (K) J Următor K J-J-1 Sfârșit Dacă următorul I. MS ^ EX I "Numărul de soluții Vvvvvvvvv- -1 I. Smochin. 19. Programul pentru sarcina 7 1. Aripile S.S. EGE 2014. Informatică. Sarcini tematice / S.S. WIRONS, D.M. Ushakov. - M.: Editura "Examen". - 245 p. 2. Site K.Yu. Polyakova. Modul de acces: http: //kpolyakov.namd.-ru/download/inf-2011-14.pdf 3. Curs certificat metodic al companiei "1c" "Pregătirea pentru examenul în domeniul informaticii. Modulul 1 ". - M.: Editura "1c". - 218 p. 4. de succes pentru a trece ECH pe știința informaticii. Modul de acces: http://infoegehelp.ru/index.php?itemid\u003d77&id\u003d103&option\u003dcom_con- Acest material conține o prezentare în care sunt prezentate metode de rezolvare a ecuațiilor și sistemelor de ecuații logice în sarcina B15 logice (No. 23, 2015) EGE pe informatică. Se știe că această sarcină este una dintre cele mai complexe dintre sarcinile EGE. Prezentarea poate fi utilă în efectuarea lecțiilor pe tema "Logic" în clasele de profil, precum și la pregătirea pentru livrarea utilizării. Pentru a vă bucura de prezentări de previzualizare, creați-vă un cont (cont) Google și conectați-vă la acesta: https://accounts.google.com Soluția sarcinii B15 (Sistem de ecuații logice) Vișnevskaya p.t., Maou "Gymnasia №3" 18 noiembrie 2013, Saratov Sarcina B15 este una dintre cele mai dificile din examenul din informatica !!! Abilitățile sunt verificate: Conversia expresiilor care conțin variabile logice; Pentru a descrie în limba naturală, o multitudine de valori variabile logice în care un anumit set de variabile logice este valabil; Calculați numărul de seturi binare care satisfac condițiile specificate. Cel mai dificil lucru, pentru că Nu există reguli formale cum să o faceți, este necesară o sarcină. Fără ceva nu face! Fără ceva nu face! Conjuncția conexiunii: A / \\ B, A B, AB, A & B, A și B Dysuuncy: A \\ / B, A + B, A | B, și negarea B: A, A, nu o echivalență: A B, A B, A B excluzând "sau": A B, Xor B Metodă pentru înlocuirea variabilelor Câte diferite seturi de variabile logice x1, x2, ..., x9, x10, care îndeplinesc toate condițiile enumerate mai jos: ((x1 ≡ x2) \\ / (x3 ≡ x4)) / \\ (¬ (¬ (¬) x1 ≡ x2) \\ / ¬ (x3 ≡ x4)) \u003d 1 ((x3 ≡ x4) \\ / (x5 ≡ x6)) / \\ (¬ (x3 ≡ x4) \\ / ¬ (x5 ≡ x6)) \u003d 1 ( (x5 ≡ x6) \\ / (x7 ≡ x8)) / \\ (¬ (x5 ≡ x7) \\ / ¬ (x7 ≡ x8)) \u003d 1 ((x7 ≡ x8) \\ / (x9 ≡ x10)) / \\ ( ¬ (x7 ≡ x8) \\ / ¬ (X9 ≡ x10)) \u003d 1 Ca răspuns, nu aveți nevoie pentru a lista toate seturi diferite x1, x2, ..., X9, x10, la care se realizează acest sistem de egalități. Ca răspuns, trebuie să specificați numărul de astfel de seturi (versiunea demo 2012) Soluție Pasul 1. Simplificăm, prin înlocuirea variabilelor T1 \u003d x1 x2 t2 \u003d x3 x4 t3 \u003d x5 x6 t4 \u003d x7 x8 t5 \u003d x9 x10 după simplificare: (t1 / t2) / \\ (¬t1 \\ / ¬ T2) \u003d 1 (t2 \\ / t3) / \\ (¬t2 \\ / ¬ t3) \u003d 1 (t3 \\ / t4) / \\ (¬t3 \\ / ¬ t4) \u003d 1 (t4 \\ / t5) / \\ (¬t4 \\ / ¬ T5) \u003d 1 Să considerăm una din ecuațiile: (T1 \\ / T2) / \\ (¬t1 \\ / ¬ T2) \u003d 1 Evident, \u003d 1 numai în cazul în care una dintre variabilele este 0, și celălalt este 1. Noi folosim formula pentru exprimarea unei operații XOR prin conjuncție și disjuncție: (T1 \\ / T2) / \\ (¬t1 \\ / ¬ T2) \u003d T1 T2 \u003d ¬ (T1 ≡ T2) \u003d 1 ¬ ( T1 ≡ T2) \u003d 1 ¬ (T2 ≡ T3) \u003d 1 ¬ (T3 ≡ T4) \u003d 1 ¬ (T4 ≡ T5) \u003d 1 Pasul 2. Analiza sistemului ¬ (T1 ≡ T2) \u003d 1 ¬ (T2 ≡ T3) \u003d 1 ¬ (T3 ≡ T4) \u003d 1 ¬ (T4 ≡ T5) \u003d 1 T1 T2 T3 T4 T5 0 1 0 1 0 1 0 1 T .la. Tk \u003d x2k-1 ≡ x2k (t1 \u003d x1 x2, ....), fiecare valoare a tk corespunde cu două perechi de valori x2k-1 și x2k, de exemplu: tk \u003d 0 corespund cu două perechi - (0,1) și (1, 0) și Tk \u003d 1 - perechi (0,0) și (1,1). Pasul 3. Numărarea numărului de soluții. Fiecare T are 2 soluții, numărul de t - 5. Deci Pentru variabilele există 2 5 \u003d 32 de soluții. Dar fiecare t corespunde unei perechi de decizii x, adică. Sistemul sursă are 2 * 32 \u003d 64 soluții. Răspuns: 64. Metodă de excludere a unei părți a soluțiilor. Câte seturi diferite de valori ale variabilelor logice X1, X2, ..., X5, Y1, Y2, Y5, care satisfac toate condițiile enumerate mai jos: (x1 → x2 ) ∧ (x2 → x4) ∧ (x3 → x4) ∧ (x4 → x5) \u003d 1; (Y1 → Y2) ∧ (Y2 → Y3) ∧ (Y3 → Y4) ∧ (Y4 → Y5) \u003d 1; Y5 → x5 \u003d 1. Răspunsul nu are nevoie să enumere toate kiturile x1, x2, ..., x5, y 1, y2, ..., y5, în care se efectuează acest sistem de egalități. Ca răspuns, trebuie să specificați numărul de astfel de seturi. Decizie. Pasul 1. Soluția consistentă de ecuații 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 Prima ecuație - Conjuncția mai multor operații de implicare este 1, adică Fiecare dintre implicațiile este adevărată. Implicația falsă este doar într-un caz, când 1 0, în toate celelalte cazuri (0 0, 0 1, 1 1) Funcționare Returnează 1. Scrieți-l sub forma unei mese: Pasul 1. Soluția consistentă a ecuațiilor T.O. Sunt obținute 6 seturi de soluții pentru x1, x2, x3, x4, x5, x3, x4, x5: (00000), (00001), (0011), (0111), (11111). Argumentând în mod similar, ajungem la concluzia că pentru Y1, Y2, Y3, Y4, Y5 există același set de soluții. pentru că Aceste ecuații sunt independente, adică. Ei nu au variabile comune, atunci soluția a acestui sistem de ecuații (excluzând a treia ecuație) va fi de 6 * 6 \u003d 36 de perechi de „Iks“ și „Igarekov“. Luați în considerare cea de-a treia ecuație: Y5 → X5 \u003d 1 Soluția sunt perechi: 0 0 0 1 1 1 nu este o soluție de abur: 1 0 Comparam soluțiile obținute în cazul în care y5 \u003d 1 nu este adecvat x5 \u003d 0. Astfel de perechi 5. Numărul de soluții de sistem: 36-5 \u003d 31. Răspuns: 31 nevoie de un combinatoric! Metoda de programare dinamică Câte soluții diferite are o ecuație logică x 1 → x 2 → x 3 → x 4 → x 5 → x 6 \u003d 1, unde x 1, x 2, ..., x 6 - Variabile logice? Ca răspuns, nu este nevoie să enumerați toate seturile de variabile în care se efectuează această egalitate. Ca răspuns, trebuie să specificați cantitatea de astfel de seturi. Decizia Pasul1. Analiza stării din stânga în ecuația este înregistrată secvențial de operațiunea de implicare, prioritatea este aceeași. Rescriem: (((x 1 → x 2) → x 3) → x 4) → x 5) → x 6 \u003d 1 nb! Fiecare variabilă următoare nu depinde de cea anterioară, ci de rezultatul implicării anterioare! Pasul 2. Detectarea modelelor Luați în considerare prima implicare, x 1 → x 2. Tatac de adevăr: x 1 x 2 x 1 → x 2 0 0 1 0 1 1 1 0 0 1 1 1 de la unul 0 a primit 2 unități și de la 1 primite un 0 și 1. un un singur 0 și trei 1, acesta este rezultatul primei operațiuni. Pasul 2. Detectarea modelelor Prin conectarea rezultatul primei operații X 3, obținem: f (x 1, x 2) x 3 f (x 1, x 2) x 3 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 din două 0 - doi 1, de la fiecare 1 (3 al acestuia) , un 0 și 1 (3 + 3) Pasul 3. ieșirea formulei T.O. Puteți forma formule pentru a calcula numărul de zerouri n i și numărul de unități E I pentru ecuația cu variabilele I:, Pasul 4. Umplerea mesei se umple de la stânga la tabelul drept pentru i \u003d 6, calculând numărul de zerouri și unități conform formulelor de mai sus; Tabelul arată modul în care se construiește următoarea coloană în conformitate cu cea precedentă: Număr de variabile 1 2 3 4 5 6 Numărul de zerouri N I 1 3 5 11 21 Număr de unități E I 1 2 * 1 + 1 \u003d 3 2 * 1 + 3 \u003d 5 11 21 43 Răspuns: 43 Metoda utilizând simplificări ale expresiilor logice Câte soluții diferite au o ecuație ((J → K) → (m n l)) ((m n ) → (¬ J k)) (M → J ) \u003d 1 unde j, k, l, m, n sunt variabile logice? Ca răspuns, nu este nevoie să enumerați toate seturile de valori ale lui J, K, L, M și N, sub care se face această egalitate. Ca răspuns, trebuie să specificați numărul de astfel de seturi. Soluție Notă că J → K \u003d ¬ J K Introducem înlocuirea variabilelor: J → K \u003d A, M N L \u003d în ecuația rescrierii, luând în considerare înlocuirea: (a → b) (b → a) (m → J) \u003d 1 4. (a b) (m → j) \u003d 1 5. este evident că un b cu aceleași valori ale lui a și în 6. Luați în considerare cele mai recente implicație m → J \u003d 1 este posibilă în cazul în care : m \u003d J \u003d 0 m \u003d 0, j \u003d 1 m \u003d j \u003d 1 Soluție pentru că A B, apoi la m \u003d j \u003d 0 ajungem 1 + k \u003d 0. Nu există soluții. Când m \u003d 0, J \u003d 1, primim 0 + k \u003d 0, k \u003d 0, și n și l - oricare, 4 soluții: ¬ J k \u003d m n Lknl 0 0 0 0 0 1 0 1 0 0 1 unul Soluție 10. Cu m \u003d j \u003d 1, obținem 0 + K \u003d 1 * N * L, sau k \u003d n * L, 4 soluții: 11. Are 4 + 4 \u003d 8 soluții Răspuns: 8 knl 0 0 0 0 0 1 0 1 0 1 1 1 Surse de informații: OB Bogomolova, D.Yu. Usekov. B15: Sarcini noi și o nouă soluție // Informatică, nr. 6, 2012, p. 35 - 39. K.YU. Polonezi. Ecuații logice // Informatică, nr. 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [Resurse electronice]. http://kpolyakov.narod.ru/school/ege.htm, [Resurse electronice]. Metode de rezolvare a sistemelor de ecuații logice Este posibil să se rezolve sistemul de ecuații logice, de exemplu, folosind un tabel de adevăr (dacă numărul de variabile nu este prea mare) sau cu arborele de soluții, simplifică anterior fiecare ecuație. 1. Metoda de înlocuire a variabilelor. Introducerea noilor variabile vă permite să simplificați sistemul de ecuații prin reducerea numărului de necunoscuți.Noile variabile trebuie să fie independente una de cealaltă..
După rezolvarea sistemului simplificat, este necesar să revenim din nou la variabilele inițiale. Luați în considerare aplicarea acestei metode pe un exemplu specific. Exemplu. ((X1 ≡ x2) ∧ (x3 ≡ x4) ∨ (¬ (x1 ≡ x2) ∧ ¬ (x3 ≡ x4)) \u003d 0 ((X3 ≡ x4) ∧ (x5 ≡ x6)) ∨ (¬ (x3 ≡ x4) ∧ ¬ (x5 ≡ x6)) \u003d 0 ((X5 ≡ x6) ∧ (x7 ≡ x8)) ∨ (¬ (x5 ≡ x6) ∧ ¬ (x7 ≡ x8)) \u003d 0 ((X7 ≡ x8) ∧ (x9 ≡ x10)) ∨ (¬ (x7 ≡ x8) ∧ ¬ (x9 ≡ x10)) \u003d 0 Decizie: Introducem noi variabile: A \u003d (x1≡ x2); B \u003d (x3 ≡ x4); C \u003d (x5 ≡ x6); D \u003d (x7 ≡ x8); E \u003d (x9 ≡ x10). (ATENȚIE! Fiecare dintre x1 lor variabile, x2, ..., x10 trebuie incluse numai într-una dintre noile variabile A, B, C, D, E, adică noi variabile sunt independente unele de altele). Apoi, sistemul de ecuații va arăta astfel: (A ∧ b) ∨ (¬ ∧ ¬v) \u003d 0 (În ∧ c) ∨ (¬b ∧ ¬c) \u003d 0 (C ∧ D) ∨ (¬c ∧ ¬d) \u003d 0 (D ∧ E) ∨ (¬d ∧ ¬e) \u003d 0 Construim copacul de soluții al sistemului obținut: Luați în considerare ecuația A \u003d 0, adică (X1.≡
X2) \u003d 0. Are 2 rădăcini: X1 ≡ x2. Din același tabel, se poate observa că ecuația A \u003d 1 are de asemenea 2 rădăcini. Selectați numărul de rădăcini pe deciziile copacului: Pentru a găsi numărul de soluții ale unei sucursale, multiplicați numărul de soluții la fiecare nivel. Ramura stângă are 2⋅
2
⋅
2
⋅
2
⋅
2 \u003d 32 soluții; Sucursala corectă are și 32 de soluții. Acestea. Întregul sistem are 32 + 32 \u003d 64 soluții. Răspuns: 64. 2. Metoda de raționament. Complexitatea sistemelor de rezolvare a ecuațiilor logice constă în vractatea copacului total de soluții. Metoda de raționament permite să nu construiască complet tot arborele, ci să înțelegeți cât de mult va avea ramuri. Luați în considerare această metodă pe exemple specifice. Exemplul 1. Câte seturi diferite de valori ale variabilelor logice X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, care satisfac toate condițiile enumerate mai jos? (x1 → x2) / \\ (x2 → x3) / \\ (x3 → x4) / \\ (x4 → x5) \u003d 1 (Y1 → Y2) / \\ (Y3 → Y3) / \\ (Y3 → Y4) / \\ (Y4 → Y5) \u003d 1 x1 \\ / y1 \u003d 1 Răspunsul nu are nevoie să enumere toate seturi de variabile x1, x2, x, x4, x5, y1, y2, x, x, y1, y2, y3, y4, y5, sub care se face acest sistem de egalități. Ca răspuns, trebuie să specificați numărul de astfel de seturi. Decizie: Prima și a doua ecuații conțin variabile independente care sunt asociate cu a treia condiție. Construim un copac de soluții ale primului și al doilea ecuații. Pentru a prezenta o soluții de arbori de la prima și a doua ecuații, fiecare ramură a primului copac ar trebui să fie continuată de un copac pentru variabilew. . Arborele construit în acest mod va conține 36 de ramuri. Unele dintre aceste ramuri nu satisfac cea de-a treia ecuație a sistemului. Notă privind primul copac numărul de ramuri de copac"U" care satisface a treia ecuație: Să explicăm: să efectuăm a treia condiție la x1 \u003d 0 ar trebui să fie u1 \u003d 1, adică toate ramurile copacilor"X" unde x1 \u003d 0 poate fi continuată numai de o singură ramură a lemnului"U" . Și numai pentru o ramură de copac"X" (dreapta) sugerează toate ramurile copacilor"U". Astfel, pomul complet al întregului sistem conține 11 ramuri. Fiecare ramură reprezintă o soluție la sistemul original de ecuații. Deci, întregul sistem are 11 soluții. Răspuns: 11. Exemplul 2. Câte soluții diferite au un sistem de ecuații (X1 ≡ x2) ∨ (x1 ∧ x10) ∨ (¬x1 ∧ ¬ x10) \u003d 1 (X2 ≡ x3) ∨ (x2 ∧ x10) ∨ (¬x2 ∧ ¬ x10) \u003d 1. ………………
(X9 ≡ x10) ∨ (x9 ∧ x10) ∨ (¬x9 ∧ ¬ x10) \u003d 1 (X1 ≡ x10) \u003d 0 unde x1, x2, ..., x10 - variabile logice? Ca răspuns, nu este nevoie să enumerați toate seturile de variabile în care se efectuează această egalitate. Ca răspuns, trebuie să specificați numărul de astfel de seturi. Decizie: Simplificăm sistemul. Construim o masă a adevărului părții primei ecuații: X1 ∧ X10. ¬x1 ∧ ¬ x10 (X1 ∧ x10) ∨ (¬x1 ∧ ¬ x10) Fiți atenți la ultima coloană, coincide cu rezultatul acțiuniiX1 ≡ x10. X1 ≡ X10. După simplificare, obținem: (X1 ≡ x2) ∨ (x1 ≡ x10) \u003d 1 (X2 ≡ x3) ∨ (x2 ≡ x10) \u003d 1 (X3 ≡ x4) ∨ (x3 ≡ x10) \u003d 1 ……
(X9 ≡ x10) ∨ (x9 ≡ x10) \u003d 1 (X1 ≡ x10) \u003d 0 Luați în considerare ultima ecuație:(X1 ≡ x10) \u003d 0, adică x1 nu trebuie să coincidă cu X10. Pentru ca prima ecuație să fie 1, ar trebui efectuată egalitatea.(X1 ≡ x2) \u003d 1, adică x1 trebuie să coincidă cu X2. Construim un copac de soluții ale primei ecuații: Luați în considerare cea de-a doua ecuație: la X10 \u003d 1 și la X2 \u003d 0 consolaar trebui să fie egal cu 1 (adică x2 coincide cu X3); la x10 \u003d 0 și la x2 \u003d 1 consola(X2 ≡ x10) \u003d 0, înseamnă că suportul (x2 ≡ x3) trebuie să fie egală cu 1 (adică x2 coincide cu x3): Susținerea în acest fel, construim copacul de soluții pentru toate ecuațiile: Astfel, sistemul de ecuații are doar 2 soluții. Răspuns: 2. Exemplul 3. Câte seturi diferite de valori ale variabilelor logice X1, X2, X3, X4, Y1, Y2, Y3, Y4, Z1, Z2, Z3, Z4, care satisfac toate condițiile enumerate mai jos? (x1 → x2) / \\ (x2 → x3) / \\ (x3 → x4) \u003d 1 (¬x1 / \\ y1 / \\ z1) \\ / (x1 / \\ ¬ \\ \\ z1) \\ / (x1 / \\ y1 / \\ ¬z1) \u003d 1 (¬x2 / \\ y2 / \\ z2) \\ / \\ / ¬y2 / \\ z2) \\ / (x2 / \\ y2 / ¬z2) \u003d 1 (¬x3 / \\ y3 / \\ z3) \\ / (x3 / ¬y3 / \\ z3) \\ / (x3 / \\ y3 / ¬z3) \u003d 1 (¬x4 / \\ y4 / \\ z4) \\ / (x4 / ¬y4 / \\ z4) \\ / (x4 / \\ y4 / ¬z4) \u003d 1 Decizie: Construim soluțiile copacului ecuației 1: Luați în considerare cea de-a doua ecuație: Similar cu ecuațiile rămase. Observăm numărul rezultat de soluții din fiecare nod de copac: Pentru a afla numărul de soluții pentru fiecare ramură, alternativ numerele obținute separat pentru fiecare ramură (stânga în viață). 1 ramură: 1 ⋅ 1 ⋅ 1 ⋅ 1 \u003d 1 soluție 2 ramură: 1 ⋅ 1 ⋅ 1 ⋅ 2 \u003d 2 soluții 3 Filiala: 1 ⋅ 1 ⋅ 2 ⋅ 2 \u003d 4 soluții 4 Filiala: 1 ⋅ 2 ⋅ 2 ⋅ 2 \u003d 8 soluții 5 Filiala: 2 ⋅ 2 ⋅ 2 ⋅ 2 \u003d 16 soluții Mutarea numerelor obținute: Soluție totală 31. Răspuns: 31. 3. Creșterea patrată a numărului de rădăcini În unele sisteme, numărul de rădăcini ale următoarei ecuații depinde de numărul de rădăcini ale ecuației anterioare. Exemplul 1. Cât de multe seturi de valori ale variabilelor logice x1, x2, x3, x4, x5, x6, x7, X8, X9, x10, diferite, care îndeplinesc toate condițiile enumerate mai jos? ¬ (x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) \u003d 0 ¬ (x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) \u003d 0 ¬ (x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) \u003d 0 Simplificare prima ecuație:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3) \u003d x1 ⊕ x3 \u003d ¬ (x1 x3). Apoi sistemul va lua forma: ¬ (x1 ≡ x2) ∧ ¬ (x1 ≡ x3) \u003d 0 ¬ (x2 ≡ x3) ∧ ¬ (x2 ≡ x4) \u003d 0 ¬ (x8 ≡ x9) ∧ ¬ (x8 ≡ x10) \u003d 0 Etc. Fiecare ecuație următoare are 2 rădăcini mai mult decât cea precedentă. 4 Ecuația are 12 rădăcini; 5 Ecuația are 14 rădăcini 8 Ecuația are 20 rădăcini. Răspuns: 20 rădăcini. Uneori, numărul de rădăcini crește în conformitate cu legea numerelor Fibonacci. Soluția sistemului de ecuații logice necesită o abordare creativă.Descarca:
Previzualizare:
Semnături pentru diapozitive:
