Subiectul lecției: „Sisteme de ecuații logice”. Rezolvarea ecuațiilor logice la matematică

Metode de rezolvare a sistemelor de ecuaţii logice

Puteți rezolva un sistem de ecuații logice, de exemplu, folosind un tabel de adevăr (dacă numărul de variabile nu este prea mare) sau folosind un arbore de decizie, simplificând mai întâi fiecare ecuație.

1. Metoda de înlocuire a variabilei.

Introducerea de noi variabile vă permite să simplificați sistemul de ecuații, reducând numărul de necunoscute.Noile variabile trebuie să fie independente unele de altele. După rezolvarea sistemului simplificat, trebuie să revenim la variabilele inițiale.

Să luăm în considerare aplicarea acestei metode folosind un exemplu specific.

Exemplu.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Soluţie:

Să introducem noi variabile: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Atenție! Fiecare dintre variabilele x1, x2, ..., x10 trebuie inclusă doar în una dintre noile variabile A, B, C, D, E, adică noile variabile sunt independente unele de altele).

Atunci sistemul de ecuații va arăta astfel:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Să construim un arbore de decizie pentru sistemul rezultat:

Se consideră ecuația A=0, adică. (X1≡ X2)=0. Are 2 rădăcini:

Din același tabel se poate observa că ecuația A=1 are și 2 rădăcini. Să aranjam numărul de rădăcini pe arborele de decizie:

Pentru a găsi numărul de soluții ale unei ramuri, trebuie să înmulțiți numărul de soluții la fiecare nivel. Ramura stângă are 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 solutii; ramura dreaptă are și 32 de soluții. Acestea. intregul sistem are 32+32=64 solutii.

Raspuns: 64.

2. Metoda de raționament.

Dificultatea rezolvării sistemelor de ecuații logice constă în greutatea unui arbore decizional complet. Metoda de raționament vă permite să nu construiți întregul copac, ci să înțelegeți câte ramuri va avea. Să ne uităm la această metodă folosind exemple specifice.

Exemplul 1. Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care îndeplinesc toate condițiile enumerate mai jos?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

Răspunsul nu trebuie să enumere toate seturile diferite de valori ale variabilelor x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 pentru care acest sistem de egalități este satisfăcut. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Solutie:

Prima și a doua ecuație conțin variabile independente care sunt legate de a treia condiție. Să construim un arbore de soluții pentru prima și a doua ecuație.

Pentru a reprezenta un arbore de soluții pentru un sistem de prima și a doua ecuație, fiecare ramură a primului arbore trebuie continuată cu un arbore pentru variabile la . Arborele astfel construit va conține 36 de ramuri. Unele dintre aceste ramuri nu satisfac a treia ecuație a sistemului. Să marchem numărul de ramuri ale copacului pe primul copac"y" , care satisfac a treia ecuație:

Să explicăm: pentru a îndeplini a treia condiție, când x1=0 trebuie să existe y1=1, adică toate ramurile arborelui"X" , unde x1=0 poate fi continuat cu o singură ramură din arbore"y" . Și doar pentru o ramură a copacului"X" (dreapta) toate ramurile copacului se potrivesc„y”. Astfel, arborele complet al întregului sistem conține 11 ramuri. Fiecare ramură reprezintă o soluție a sistemului original de ecuații. Aceasta înseamnă că întregul sistem are 11 soluții.

Raspuns: 11.

Exemplul 2. Câte soluții diferite are sistemul de ecuații?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

unde x1, x2, …, x10 sunt variabile logice? Răspunsul nu trebuie să enumere toate seturile diferite de valori variabile pentru care este valabilă această egalitate. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Solutie: Să simplificăm sistemul. Să construim un tabel de adevăr pentru o parte a primei ecuații:

Atenție la ultima coloană, se potrivește cu rezultatul acțiunii X1 ≡ X10.

După simplificare obținem:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Luați în considerare ultima ecuație:(X1 ≡ X10) = 0, adică. x1 nu trebuie să coincidă cu x10. Pentru ca prima ecuație să fie egală cu 1, egalitatea trebuie să fie adevărată(X1 ≡ X2)=1, adică x1 trebuie să se potrivească cu x2.

Să construim un arbore de soluții pentru prima ecuație:

Luați în considerare a doua ecuație: pentru x10=1 și pentru x2=0 parantezatrebuie să fie egal cu 1 (adică x2 coincide cu x3); pentru x10=0 și pentru x2=1 paranteză(X2 ≡ X10)=0, ceea ce înseamnă paranteza (X2 ≡ X3) ar trebui să fie egal cu 1 (adică x2 coincide cu x3):

Raționând în acest fel, construim un arbore de decizie pentru toate ecuațiile:

Astfel, sistemul de ecuații are doar 2 soluții.

Raspuns: 2.

Exemplul 3.

Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 există care îndeplinesc toate condițiile enumerate mai jos?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Soluţie:

Să construim un arbore de soluții pentru prima ecuație:

Luați în considerare a doua ecuație:

• Când x1=0 : a doua și a treia paranteză vor fi egale cu 0; pentru ca prima paranteză să fie egală cu 1, y1=1, z1=1 (adică în acest caz - 1 soluție)
• Când x1=1 : prima paranteză va fi egală cu 0; al doilea sau a treia paranteză trebuie să fie egală cu 1; a doua paranteză va fi egală cu 1 când y1=0 și z1=1; a treia paranteză va fi egală cu 1 când y1=1 și z1=0 (adică în acest caz - 2 soluții).

La fel și pentru celelalte ecuații. Să notăm numărul rezultat de soluții pentru fiecare nod de arbore:

Pentru a afla numărul de soluții pentru fiecare ramură, înmulțiți numerele rezultate separat pentru fiecare ramură (de la stânga la dreapta).

1 ramură: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 soluție

Ramura 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 soluții

A 3-a ramură: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 soluții

Ramura a 4-a: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 soluții

Ramura a 5-a: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 soluții

Să adunăm numerele rezultate: sunt 31 de soluții în total.

Raspuns: 31.

3. Cresterea naturala a numarului de radacini

Î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âte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 există care îndeplinesc toate condițiile enumerate mai jos?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Să simplificăm prima ecuatie:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Apoi sistemul va lua forma:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

etc.

Fiecare ecuație următoare are cu 2 rădăcini mai multe decât cea anterioară.

4 ecuația are 12 rădăcini;

Ecuația 5 are 14 rădăcini

Ecuația 8 are 20 de rădăcini.

Răspuns: 20 de rădăcini.

Uneori, numărul de rădăcini crește conform legii Fibonacci.

Rezolvarea unui sistem de ecuații logice necesită o abordare creativă.

Cum se rezolvă unele probleme din secțiunile A și B ale examenului de informatică

Lecția #3. Logice. Funcții logice. Rezolvarea ecuațiilor

Un număr mare de probleme ale examenului de stat unificat sunt dedicate logicii propoziționale. Pentru a rezolva majoritatea dintre ele, este suficient să cunoașteți legile de bază ale logicii propoziționale, cunoașterea tabelelor de adevăr ale funcțiilor logice ale unei și două variabile. Voi da legile de bază ale logicii propoziționale.

1. Comutativitatea disjuncției și conjuncției:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Legea distributivă privind disjuncția și conjuncția:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negarea negației:
   ¬(¬a) ≡ a
4. Consecvență:
   a ^ ¬а ≡ fals
5. Al treilea exclusiv:
   a ˅ ¬а ≡ adevărat
6. Legile lui De Morgan:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Simplificare:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ adevărat ≡ a
   a ˄ fals ≡ fals
8. Absorbţie:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Înlocuirea implicației
   a → b ≡ ¬a ˅ b
10. Înlocuirea identității
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Reprezentarea funcţiilor logice

Orice funcție logică a n variabile - F(x 1, x 2, ... x n) poate fi specificată printr-un tabel de adevăr. Un astfel de tabel conține 2n seturi de variabile, pentru fiecare dintre acestea fiind specificată valoarea unei funcții din acest set. Această metodă este bună atunci când numărul de variabile este relativ mic. Deja pentru n > 5 reprezentarea devine slab vizibilă.

O altă modalitate este de a defini funcția printr-o formulă folosind funcții cunoscute destul de simple. Un sistem de funcții (f 1, f 2, ... f k) se numește complet dacă orice funcție logică poate fi exprimată printr-o formulă care conține numai funcții f i.

Sistemul de funcții (¬, ˄, ˅) este complet. Legile 9 și 10 sunt exemple care demonstrează modul în care implicația și identitatea sunt exprimate prin negație, conjuncție și disjuncție.

De fapt, un sistem de două funcții – negație și conjuncție sau negație și disjuncție – este de asemenea complet. Din legile lui De Morgan rezultă idei care permit cuiva să exprime o conjuncție prin negație și disjuncție și, în consecință, să exprime o disjuncție prin negație și conjuncție:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

În mod paradoxal, un sistem format dintr-o singură funcție este complet. Există două funcții binare - anticonjuncție și antidisjuncție, numite săgeata Peirce și cursa Schaeffer, reprezentând un sistem gol.

Funcțiile de bază ale limbajelor de programare includ de obicei identitatea, negația, conjuncția și disjuncția. În problemele Unified State Examination, împreună cu aceste funcții, se găsește adesea implicații.

Să ne uităm la câteva probleme simple care implică funcții logice.

Problema 15:

Este dat un fragment din tabelul de adevăr. Care dintre cele trei funcții date corespunde acestui fragment?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funcția numărul 3.

Pentru a rezolva problema, trebuie să cunoașteți tabelele de adevăr ale funcțiilor de bază și să vă amintiți prioritățile operațiunilor. Permiteți-mi să vă reamintesc că conjuncția (înmulțirea logică) are prioritate mai mare și se execută mai devreme decât disjuncția (adunarea logică). În timpul calculelor, este ușor de observat că funcțiile cu numerele 1 și 2 din al treilea set au valoarea 1 și din acest motiv nu corespund fragmentului.

Problema 16:

Care dintre numerele date îndeplinește condiția:

(cifrele, începând de la cea mai semnificativă cifră, sunt în ordine descrescătoare) → (număr - par) ˄ (cifră mică - par) ˄ (cifră mare - impar)

Dacă există mai multe astfel de numere, indicați-l pe cel mai mare.

1. 13579
2. 97531
3. 24678
4. 15386

Condiția este îndeplinită de numărul numărul 4.

Primele două numere nu îndeplinesc condiția pentru motivul că cea mai mică cifră este impară. O conjuncție de condiții este falsă dacă unul dintre termenii conjuncției este fals. Pentru al treilea număr, condiția pentru cea mai mare cifră nu este îndeplinită. Pentru al patrulea număr sunt îndeplinite condițiile impuse cifrelor inferioare și mari ale numărului. Primul termen al conjuncției este și el adevărat, deoarece implicația este adevărată dacă premisa sa este falsă, ceea ce este cazul aici.

Problema 17: Doi martori au depus următoarea mărturie:

Primul martor: Dacă A este vinovat, atunci B este și mai vinovat, iar C este nevinovat.

Al doilea martor: Doi sunt vinovați. Și unul dintre cei rămași este cu siguranță vinovat și vinovat, dar nu pot spune cine exact.

Ce concluzii despre vinovăția lui A, B și C se pot trage din mărturie?

Răspuns: Din mărturie rezultă că A și B sunt vinovați, iar C este nevinovat.

Soluție: Desigur, răspunsul poate fi dat pe baza bunului simț. Dar să vedem cum se poate face acest lucru în mod strict și formal.

Primul lucru de făcut este să oficializați declarațiile. Să introducem trei variabile logice - A, B și C, fiecare având valoarea adevărată (1) dacă suspectul corespunzător este vinovat. Apoi, mărturia primului martor este dată prin formula:

A → (B ˄ ¬C)

Depozitia celui de-al doilea martor este data prin formula:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Depoziţia ambilor martori se presupune a fi adevărată şi reprezintă conjuncţia formulelor corespunzătoare.

Să construim un tabel de adevăr pentru aceste lecturi:

Probele sumare sunt adevărate într-un singur caz, ceea ce duce la un răspuns clar - A și B sunt vinovați, iar C este nevinovat.

Din analiza acestui tabel mai rezultă că depoziţia celui de-al doilea martor este mai informativă. Din adevărul mărturiei sale, urmează doar două opțiuni posibile - A și B sunt vinovați și C este nevinovat, sau A și C sunt vinovați și B este nevinovat. Depoziţia primului martor este mai puţin informativă - există 5 opţiuni diferite care corespund mărturiei sale. Împreună, mărturia ambilor martori oferă un răspuns clar cu privire la vinovăția suspecților.

Ecuații logice și sisteme de ecuații

Fie F(x 1, x 2, …x n) o funcție logică a n variabile. Ecuația logică arată astfel:

F(x 1, x 2, …x n) = C,

Constanta C are valoarea 1 sau 0.

O ecuație logică poate avea de la 0 la 2 n soluții diferite. Dacă C este egal cu 1, atunci soluțiile sunt toate acele seturi de variabile din tabelul de adevăr pentru care funcția F ia valoarea adevărată (1). Mulțimile rămase sunt soluții ale ecuației cu C egal cu zero. Puteți lua în considerare întotdeauna numai ecuații de forma:

F(x 1 , x 2 , …x n) = 1

Într-adevăr, să fie dată ecuația:

F(x 1, x 2, …x n) = 0

În acest caz, putem merge la ecuația echivalentă:

¬F(x 1 , x 2 , …x n) = 1

Considerăm un sistem de k ecuații logice:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1 , x 2 , …x n) = 1

Soluția unui sistem este un set de variabile pe care toate ecuațiile sistemului sunt satisfăcute. În ceea ce privește funcțiile logice, pentru a obține o soluție la un sistem de ecuații logice, ar trebui să găsim o mulțime pe care funcția logică Ф este adevărată, reprezentând conjuncția funcțiilor originale F:

Ф = F 1 ˄ F 2 ˄ … F k

Dacă numărul de variabile este mic, de exemplu, mai mic de 5, atunci nu este dificil să construim un tabel de adevăr pentru funcția Ф, care ne permite să spunem câte soluții are sistemul și care sunt mulțimile care oferă soluții.

În unele probleme USE privind găsirea de soluții la un sistem de ecuații logice, numărul de variabile ajunge la 10. Apoi construirea unui tabel de adevăr devine o sarcină aproape imposibilă. Rezolvarea problemei necesită o abordare diferită. Pentru un sistem arbitrar de ecuații, nu există altă metodă generală decât enumerarea care să permită rezolvarea unor astfel de probleme.

În problemele propuse la examen, soluția se bazează de obicei pe luarea în considerare a specificului sistemului de ecuații. Repet, în afară de a încerca toate opțiunile pentru un set de variabile, nu există o modalitate generală de a rezolva problema. Soluția trebuie construită pe baza specificului sistemului. Este adesea util să se efectueze o simplificare preliminară a unui sistem de ecuații folosind legile logice cunoscute. O altă tehnică utilă pentru rezolvarea acestei probleme este următoarea. Nu ne interesează toate mulțimile, ci doar acelea pe care funcția Ф are valoarea 1. În loc să construim un tabel de adevăr complet, vom construi analogul său - un arbore de decizie binar. Fiecare ramură a acestui arbore corespunde unei soluții și specifică o mulțime pe care funcția Ф are valoarea 1. Numărul de ramuri din arborele de decizie coincide cu numărul de soluții ale sistemului de ecuații.

Voi explica ce este un arbore de decizie binar și cum este construit folosind exemple de mai multe probleme.

Problema 18

Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care satisfac sistemul de două ecuații?

Răspuns: Sistemul are 36 de soluții diferite.

Rezolvare: Sistemul de ecuații include două ecuații. Să găsim numărul de soluții pentru prima ecuație, în funcție de 5 variabile - x 1, x 2, ... x 5. Prima ecuație poate fi considerată la rândul său ca un sistem de 5 ecuații. După cum sa arătat, sistemul de ecuații reprezintă de fapt conjuncția funcțiilor logice. Este adevărat și invers: o conjuncție de condiții poate fi considerată ca un sistem de ecuații.

Să construim un arbore de decizie pentru implicația (x1→ x2) - primul termen al conjuncției, care poate fi considerat ca prima ecuație. Iată cum arată o reprezentare grafică a acestui arbore:

Arborele este format din două niveluri în funcție de numărul de variabile din ecuație. Primul nivel descrie prima variabilă X 1 . Două ramuri ale acestui nivel reflectă valorile posibile ale acestei variabile - 1 și 0. La al doilea nivel, ramurile arborelui reflectă numai acele valori posibile ale variabilei X 2 pentru care ecuația este adevărată. Deoarece ecuația specifică o implicație, o ramură pe care X 1 are valoarea 1 necesită ca pe acea ramură X 2 să aibă valoarea 1. O ramură pe care X 1 are valoarea 0 produce două ramuri cu valorile lui X 2 egal cu 0 și 1 Arborele construit definește trei soluții, pe care implicația X 1 → X 2 ia valoarea 1. Pe fiecare ramură, este scris un set corespunzător de valori variabile, dând o soluție ecuației.

Aceste seturi sunt: ​​((1, 1), (0, 1), (0, 0))

Să continuăm construirea arborelui de decizie adăugând următoarea ecuație, următoarea implicație X 2 → X 3 . Specificul sistemului nostru de ecuații este că fiecare nouă ecuație a sistemului utilizează o variabilă din ecuația anterioară, adăugând o nouă variabilă. Deoarece variabila X 2 are deja valori în arbore, atunci pe toate ramurile în care variabila X 2 are valoarea 1, variabila X 3 va avea și valoarea 1. Pentru astfel de ramuri, construcția arborelui continuă la nivelul următor, dar ramuri noi nu apar. Singura ramură în care variabila X 2 are valoarea 0 se va ramifica în două ramuri unde variabila X 3 va primi valorile 0 și 1. Astfel, fiecare adăugare a unei noi ecuații, având în vedere specificul ei, adaugă o soluție. Prima ecuație originală:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
are 6 solutii. Iată cum arată arborele de decizie complet pentru această ecuație:

A doua ecuație a sistemului nostru este similară cu prima:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Singura diferență este că ecuația folosește variabile Y. Această ecuație are și 6 soluții. Deoarece fiecare soluție pentru variabilele X i poate fi combinată cu fiecare soluție pentru variabilele Y j , numărul total de soluții este 36.

Vă rugăm să rețineți că arborele de decizie construit oferă nu numai numărul de soluții (în funcție de numărul de ramuri), ci și soluțiile în sine scrise pe fiecare ramură a arborelui.

Problema 19

Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care îndeplinesc toate condițiile enumerate mai jos?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

Această sarcină este o modificare a sarcinii anterioare. Diferența este că se adaugă o altă ecuație care leagă variabilele X și Y.

Din ecuația X 1 → Y 1 rezultă că atunci când X 1 are valoarea 1 (există o astfel de soluție), atunci Y 1 are și valoarea 1. Astfel, există o mulțime pe care X 1 și Y 1 au valorile ​​1. Când X 1 egal cu 0, Y 1 poate avea orice valoare, atât 0, cât și 1. Prin urmare, fiecare set cu X 1 egal cu 0 și există 5 astfel de mulțimi, corespunde tuturor celor 6 seturi cu variabile Y. Prin urmare, numărul total de soluții este 31 .

Problema 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Rezolvare: amintindu-ne echivalențele de bază, scriem ecuația noastră ca:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Lanțul ciclic de implicații înseamnă că variabilele sunt identice, deci ecuația noastră este echivalentă cu ecuația:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Această ecuație are două soluții când toți X i sunt fie 1, fie 0.

Problema 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Soluție: La fel ca în problema 20, trecem de la implicațiile ciclice la identități, rescriind ecuația sub forma:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Să construim un arbore de decizie pentru această ecuație:

Problema 22

Câte soluții are următorul sistem de ecuații?

((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 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Raspuns: 64

Soluție: Să trecem de la 10 variabile la 5 variabile introducând următoarea modificare a variabilelor:

Y1 = (X1 ≡ X2); Y2 = (X3 = X4); Y3 = (X5 = X6); Y4 = (X7 = X8); Y5 = (X9 = X10);

Atunci prima ecuație va lua forma:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Ecuația poate fi simplificată scriind-o astfel:

(Y 1 ≡ Y 2) = 0

Trecând la forma tradițională, scriem sistemul după simplificări în forma:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Arborele de decizie pentru acest sistem este simplu și constă din două ramuri cu valori variabile alternative:

Revenind la variabilele X originale, rețineți că pentru fiecare valoare din variabila Y există 2 valori în variabilele X, deci fiecare soluție din variabilele Y generează 2 5 soluții în variabilele X. Cele două ramuri generează 2 * 2 5 soluții, deci numărul total de soluții este 64.

După cum puteți vedea, fiecare problemă de rezolvare a unui sistem de ecuații necesită propria abordare. O tehnică comună este de a efectua transformări echivalente pentru a simplifica ecuațiile. O tehnică comună este construirea arborilor de decizie. Abordarea utilizată amintește parțial de construirea unui tabel de adevăr cu particularitatea că nu sunt construite toate seturile de valori posibile ale variabilelor, ci doar acelea pe care funcția ia valoarea 1 (adevărat). Adesea, în problemele propuse nu este nevoie să se construiască un arbore decizional complet, deoarece deja în stadiul inițial este posibil să se stabilească modelul de apariție a ramurilor noi la fiecare nivel ulterior, așa cum sa făcut, de exemplu, în problema 18. .

În general, problemele care implică găsirea de soluții la un sistem de ecuații logice sunt exerciții matematice bune.

Dacă problema este dificil de rezolvat manual, atunci puteți încredința soluția computerului prin scrierea unui program adecvat pentru rezolvarea ecuațiilor și a sistemelor de ecuații.

Nu este greu să scrii un astfel de program. Un astfel de program va face față cu ușurință tuturor sarcinilor oferite în Examenul de stat unificat.

Destul de ciudat, sarcina de a găsi soluții la sistemele de ecuații logice este dificilă pentru un computer și se dovedește că un computer are limitele sale. Calculatorul poate face față destul de ușor problemelor în care numărul de variabile este de 20-30, dar va începe să se gândească mult timp la probleme de dimensiuni mai mari. Faptul este că funcția 2 n, care specifică numărul de mulțimi, este o exponențială care crește rapid pe măsură ce n crește. Atât de rapid încât un computer personal obișnuit nu poate face față unei sarcini care are 40 de variabile într-o zi.

Program în limbaj C# pentru rezolvarea ecuațiilor logice

Scrierea unui program pentru rezolvarea ecuațiilor logice este utilă din mai multe motive, fie și doar pentru că îl puteți utiliza pentru a verifica corectitudinea propriei soluții la problemele testului Unified State Exam. Un alt motiv este că un astfel de program este un exemplu excelent de sarcină de programare care îndeplinește cerințele pentru sarcinile de categoria C din examenul de stat unificat.

Ideea de a construi un program este simplă - se bazează pe o căutare completă a tuturor seturilor posibile de valori variabile. Deoarece pentru o anumită ecuație logică sau sistem de ecuații, numărul de variabile n este cunoscut, atunci este cunoscut și numărul de mulțimi - 2 n care trebuie sortate. Folosind funcțiile de bază ale limbajului C# - negație, disjuncție, conjuncție și identitate, nu este dificil să scrii un program care, pentru un anumit set de variabile, calculează valoarea funcției logice corespunzătoare unei ecuații logice sau unui sistem de ecuații. .

Într-un astfel de program, trebuie să construiți o buclă bazată pe numărul de seturi, în corpul buclei, folosind numărul setului, să formați setul în sine, să calculați valoarea funcției pe acest set și dacă aceasta valoarea este 1, atunci mulțimea oferă o soluție ecuației.

Singura dificultate care apare la implementarea programului este legată de sarcina de a genera însuși setul de valori variabile pe baza numărului setat. Frumusețea acestei probleme este că această sarcină aparent dificilă se reduce de fapt la o problemă simplă care a apărut deja de multe ori. Într-adevăr, este suficient să înțelegem că setul de valori variabile corespunzătoare numărului i, format din zerouri și unu, reprezintă reprezentarea binară a numărului i. Deci sarcina complexă de a obține un set de valori variabile după un număr stabilit se reduce la sarcina familiară de a converti un număr în binar.

Iată cum arată o funcție în C# care ne rezolvă problema:

///

///

/// funcție logică - metodă,

/// a cărui semnătură este specificată de delegatul DF

///

/// numărul de variabile

/// număr de soluții

static int Rezolva ecuații (DF fun, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); //numar de seturi

int p = 0, q = 0, k = 0;

//Se completează căutarea după numărul de seturi

pentru (int i = 0; i< m; i++)

//Formarea următorului set - set,

//specificat prin reprezentarea binară a numărului i

pentru (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Calculează valoarea funcției pe set

Pentru a înțelege programul, sper că explicațiile ideii programului și comentariile din textul acestuia sunt suficiente. Mă voi concentra doar pe explicarea titlului funcției date. Funcția SolveEquations are doi parametri de intrare. Parametrul fun specifică o funcție logică corespunzătoare ecuației sau sistemului de ecuații care se rezolvă. Parametrul n specifică numărul de variabile distractive. Ca rezultat, funcția SolveEquations returnează numărul de soluții ale funcției logice, adică numărul acelor mulțimi pe care funcția evaluează la adevărat.

Este obișnuit pentru școlari când o funcție F(x) are un parametru de intrare x care este o variabilă de tip aritmetic, șir sau logic. În cazul nostru, se folosește un design mai puternic. Funcția SolveEquations se referă la funcții de ordin superior - funcții de tip F(f), ai căror parametri pot fi nu numai variabile simple, ci și funcții.

Clasa de funcții care poate fi transmisă ca parametru la funcția SolveEquations este specificată după cum urmează:

delegat bool DF(bool vars);

Această clasă deține toate funcțiile care sunt transmise ca parametru un set de valori ale variabilelor logice specificate de matricea vars. Rezultatul este o valoare booleană reprezentând valoarea funcției din acest set.

În cele din urmă, iată un program care utilizează funcția SolveEquations pentru a rezolva mai multe sisteme de ecuații logice. Funcția SolveEquations face parte din clasa ProgramCommon de mai jos:

clasa ProgramCommon

delegat bool DF(bool vars);

static void Main(string args)

Console.WriteLine("Și Funcții - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Funcția are 51 de soluții - " +

RezolvaEcuații(Fun51, 5));

Console.WriteLine("Funcția are 53 de soluții - " +

Rezolvare ecuații(Fun53, 10));

static bool FunAnd(bool vars)

returnează vars && vars;

static bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

static 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)));

Iată cum arată rezultatele soluției pentru acest program:

10 sarcini pentru muncă independentă

1. Care dintre cele trei funcții sunt echivalente:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Este dat un fragment din tabelul de adevăr:

Care dintre cele trei funcții îi corespunde acest fragment:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Juriul este format din trei persoane. Decizia se ia dacă președintele juriului o votează, susținut de cel puțin unul dintre membrii juriului. Altfel, nu se ia nicio decizie. Construiți o funcție logică care formalizează procesul decizional.
5. X câștigă peste Y dacă aruncările de patru monede au ca rezultat de trei ori cap. Definiți o funcție logică care descrie profitul lui X.
6. Cuvintele dintr-o propoziție sunt numerotate începând de la unu. O propoziție este considerată corect construită dacă sunt îndeplinite următoarele reguli:
   1. Dacă un cuvânt par se termină cu o vocală, atunci următorul cuvânt, dacă există, trebuie să înceapă cu o vocală.
   2. Dacă un cuvânt impar se termină cu o consoană, atunci următorul cuvânt, dacă există, trebuie să înceapă cu o consoană și să se termine cu o vocală.
      Care dintre următoarele propoziții sunt corect construite:
   3. Mama a spălat-o pe Masha cu săpun.
   4. Un lider este întotdeauna un model.
   5. Adevărul este bun, dar fericirea este mai bună.
7. Câte soluții are ecuația:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Enumerați toate soluțiile ecuației:
   (a → b) → c = 0
9. Câte soluții are următorul sistem de ecuații:
   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
10. Câte soluții are ecuația:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Răspunsuri la probleme:

1. Funcțiile b și c sunt echivalente.
2. Fragmentul corespunde funcției b.
3. Fie ca variabila logică P să ia valoarea 1 atunci când președintele juriului votează „pentru” decizia. Variabilele M 1 și M 2 reprezintă opiniile membrilor juriului. Funcția logică care specifică luarea unei decizii pozitive poate fi scrisă după cum urmează:
   P ˄ (M 1 ˅ M 2)
4. Fie ca variabila logică P i să ia valoarea 1 atunci când a i-a aruncare a monedei aterizează pe capete. Funcția logică care specifică câștigul X poate fi scrisă după cum urmează:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Teza b.
6. Ecuația are 3 soluții: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Utilizarea ecuațiilor este larg răspândită în viața noastră. Ele sunt folosite în multe calcule, construcție de structuri și chiar sport. Omul a folosit ecuații în antichitate, iar de atunci utilizarea lor a crescut. În matematică, există anumite probleme care tratează logica propozițională. Pentru a rezolva acest tip de ecuație, trebuie să aveți o anumită cunoștințe: cunoașterea legilor logicii propoziționale, cunoașterea tabelelor de adevăr ale funcțiilor logice a 1 sau 2 variabile, metode de conversie a expresiilor logice. În plus, trebuie să cunoașteți următoarele proprietăți ale operațiilor logice: conjuncție, disjuncție, inversare, implicație și echivalență.

Orice funcție logică a \variables - \ poate fi specificată printr-un tabel de adevăr.

Să rezolvăm mai multe ecuații logice:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Să începem soluția cu \[X1\] și să stabilim ce valori poate lua această variabilă: 0 și 1. În continuare, vom lua în considerare fiecare dintre valorile de mai sus și vom vedea ce poate fi \[X2.\].

După cum se poate vedea din tabel, ecuația noastră logică are 11 soluții.

Unde pot rezolva o ecuație logică online?

Puteți rezolva ecuația pe site-ul nostru https://site. Rezolvatorul online gratuit vă va permite să rezolvați ecuații online de orice complexitate în câteva secunde. Tot ce trebuie să faceți este să introduceți pur și simplu datele dvs. în soluție. De asemenea, puteți viziona instrucțiuni video și puteți afla cum să rezolvați ecuația pe site-ul nostru. Și dacă mai aveți întrebări, le puteți adresa în grupul nostru VKontakte http://vk.com/pocketteacher. Alăturați-vă grupului nostru, suntem întotdeauna bucuroși să vă ajutăm.

În prezent, cererile sunt în creștere pentru îmbunătățirea calității educației pentru școlari. Una dintre cele mai importante inovații în conținutul educației matematice este includerea elementelor de logică matematică în programele școlare. Acest lucru se datorează rolului jucat de cunoștințele logice în pregătirea educațională generală a omului modern.
Este indicat să începeți studiul elementelor de logică matematică în clasele 5–6, sau în clasa a 7-a, în funcție de sistemul de prezentare în manualul folosit pentru predare. Timpul necesar poate fi găsit prin refuzul de a lua în considerare cu elevii întrebări care nu sunt incluse în conținutul minim obligatoriu al școlii de bază (rădăcina gradului n, gradul cu exponent fracționar, metoda intervalelor, materialul trigonometric la cursul de algebră) , dar sunt păstrate într-o serie de manuale și în practica profesorilor.
Dar cel mai adesea aceste secțiuni sunt studiate numai în cursuri opționale.

Subiect:„Sisteme de ecuații logice” (clasa a X-a)

Obiectivele lecției:

• introducerea elevilor în conceptul de sisteme de ecuații logice, studierea diferitelor metode de rezolvare a acestora, repetarea metodelor de rezolvare a sistemelor algebrice și a produsului scalar al vectorilor;
• dezvoltarea gândirii matematice și a vorbirii logice a elevilor, a imaginației, a capacității de a analiza și de a aplica cunoștințele lor într-o situație nefamiliară;
• cultivarea interesului pentru subiect, diligența și atenția.

Echipament: tablă, cretă, caiete, pixuri, creioane, grile pentru rezolvarea sistemelor cu trei și patru necunoscute.

ÎN CURILE CURĂRILOR

I. Moment organizatoric

II. Mesaj cu subiectul lecției

Scrieți numele subiectului în caiet.

– În ultima lecție am studiat operațiile logice. Astăzi continuăm să studiem ecuațiile logice și să învățăm cum să rezolvăm sisteme de astfel de ecuații. Trebuie remarcat imediat că sistemele de ecuații logice sunt rezolvate puțin diferit față de cele algebrice. Sau mai degrabă, în alte moduri.

III. Actualizarea cunoștințelor

– Ce înseamnă să rezolvi un sistem cu două variabile?
Rezolvarea unui sistem cu două variabile înseamnă găsirea tuturor perechilor (x, y) care satisfac fiecare dintre ecuațiile date sau demonstrarea că nu există o soluție.
Ce moduri cunoașteți pentru a rezolva sistemele?

• metoda de substitutie
• metoda de adăugare
• mod de a introduce noi variabile,
• metoda grafica.

1. Rezolvați un sistem de ecuații în serie.

• Primul rând este prin adunare;
• Al doilea este grafic;
• Al treilea este prin metoda substituției.

a) Adunând ecuația termen cu termen, avem: 2 X + 10X = 15 + 9;

12X = 24; X= 2, înlocuind această valoare în a doua ecuație, obținem: 10 . 2 – 11la= 9, de unde la = 1.

Răspuns:(2;1).

b) Din prima ecuație, din a doua ecuație,

A (2;1) este punctul de intersecție al graficelor ecuațiilor.

(2;1) – soluția sistemului.

c) Înlocuiți din prima ecuație în a doua

11la = 15 – 4, 11la = 11, la = 1.

Răspuns: (2;1).

– Cum se numește produsul scalar al vectorilor?
Produsul scalar al vectorilor este un număr egal cu produsul dintre lungimile acestor vectori și cosinusul unghiului dintre ei.
Cum se scrie produsul punctual sub formă de coordonate?

.

IV. Scena principală

Folosind două operații „disjuncție” și „conjuncție”, considerăm sisteme booleene de două ecuații cu două necunoscute:

Găsirea unei variabile într-o ecuație cu o operație logică are ca rezultat mai multe soluții. Dacă soluția sistemului ar fi exprimată printr-o formulă specifică, atunci când înlocuim datele inițiale (coeficienții ecuației), am obține o soluție complet definită. Folosind un exemplu simplu, vedem polisemia soluției, prin urmare, fie soluția sistemului într-o formă generală trebuie exprimată prin mai multe formule, fie astfel de formule nu există în mod explicit. În prezent, astfel de formule nu au fost încă găsite, așa că sistemele de ecuații logice sunt rezolvate folosind metode unice, cu care ne vom familiariza astăzi în lecție.
Sistemul depinde de șase parametri A,b,c,d,m,n, fiecare dintre acestea ia două valori 0 sau 1. Prin urmare, în total obținem 2 6 = 64 de cazuri.
Rezultatul analitic poate fi obținut prin raționament logic și parcurgând toate cele 64 de cazuri.

Exercitiul 1.(un elev lucrează la consiliu).

Rezolvați sistemul dacă A = 0, b = 0, c = 0, d = 0, m = 0, n = 0.

.

Răspuns: sistemul are 4 soluții: (1;1), (0;1), (1;0),(0;0).

Sarcina 2.(independent în caiete cu verificare ulterioară).

Rezolvați sistemul dacă A = 1, b = 0, c = 0, d = 0, m = 0, n = 0.

,

Răspuns: sistemul are 2 soluții: (0;0), (0;1).

În mod similar, puteți rezolva restul de 62 de sisteme prin înlocuirea parametrilor A,b,c,d,m,n respectiv, valorile sunt 0 și 1.
Este chiar posibilă gruparea unor cazuri în clase pentru a evidenția condițiile pentru cazurile în care sistemul are o singură soluție, mai multe soluții sau nicio soluție.
Într-un curs de matematică școlar, se poate identifica o gamă foarte limitată de probleme care pot fi rezolvate folosind sisteme de ecuații logice.

Sarcina 3.Șase pahare transparente de apă sunt dispuse în două rânduri paralele a câte trei pahare fiecare. Ilustrația arată vedere frontală și vedere laterală dreaptă. Prin pereții transparenți ai paharelor sunt vizibile nivelurile apei din fiecare pahar și din toate paharele din spatele lor. Determinați câtă apă se toarnă în fiecare pahar.

Imaginea arată că paharele sunt fie pline, fie goale. Setul de ochelari care se găsesc în aceste șase locuri formează un alfabet, care este format din două elemente.
Să notăm un pahar gol cu ​​0 și un pahar plin cu 1. Atunci mulțimea constă din 0 și 1, adică. = (0,1) .
Să numerotăm proiecțiile din figură cu numere de la 1 la 5.
Să numerotăm rândurile de pahare după cum urmează și să indicăm elementele care pot apărea în aceste rânduri

Prima proiecție arată că nu există pahare pline în prima coloană, adică. X 11 = 0, X 21 = 0.

Din a cincea proiecție este clar că X 23 = 0, X 22 = 0. Elementele rămase sunt ușor de determinat: X 12 = 1, X 13 = 1.

Analitic, formularea problemei se reduce la rezolvarea sistemului de ecuații

Avem un sistem de ecuații în care operațiile „+” sunt disjuncție, „ . ” – conjuncție.
Din a doua ecuație a sistemului și adevăratele tabele de conjuncție și disjuncție obținem X 21 + X 22 + X 23 = 0 => X 21 = X 22 = X 23 = 0.
Din a treia ecuație => X 11 = 0.
Să înlocuim valorile găsite ale necunoscutelor în ecuațiile a patra și a cincea ale sistemului:

Toți termenii liberi și necunoscuți iau valorile 0 sau 1, iar ecuațiile satisfac operații logice, adică obţinem un sistem de ecuaţii logice.
Astfel, dacă o problemă conține două tipuri de ochelari, atunci poate fi rezolvată cu ușurință prin rezolvarea unui sistem de ecuații logice. Acest lucru economisește timp și oferă o soluție mai scurtă și mai ușoară.
Să luăm în considerare metoda tabelelor transparente (metoda grilă) - un analog al metodei grafice pentru rezolvarea sistemelor algebrice, care vă permite să rezolvați rapid un sistem de ecuații care conține cel mult patru variabile.
Această metodă se bazează pe produsul scalar al vectorilor.

Fie o funcție logică a n variabile. Ecuația logică arată astfel:

Constanta C are valoarea 1 sau 0.

O ecuație logică poate avea de la 0 la soluții diferite. Dacă C este egal cu 1, atunci soluțiile sunt toate acele seturi de variabile din tabelul de adevăr pentru care funcția F ia valoarea adevărată (1). Mulțimile rămase sunt soluții ale ecuației cu C egal cu zero. Puteți lua în considerare întotdeauna numai ecuații de forma:

Într-adevăr, să fie dată ecuația:

În acest caz, putem merge la ecuația echivalentă:

Considerăm un sistem de k ecuații logice:

Soluția unui sistem este un set de variabile pe care toate ecuațiile sistemului sunt satisfăcute. În ceea ce privește funcțiile logice, pentru a obține o soluție la un sistem de ecuații logice, ar trebui să găsim o mulțime pe care funcția logică Ф este adevărată, reprezentând conjuncția funcțiilor originale:

Dacă numărul de variabile este mic, de exemplu, mai mic de 5, atunci nu este dificil să construim un tabel de adevăr pentru funcție, care ne permite să spunem câte soluții are sistemul și care sunt mulțimile care oferă soluții.

În unele probleme USE privind găsirea de soluții la un sistem de ecuații logice, numărul de variabile ajunge la 10. Apoi construirea unui tabel de adevăr devine o sarcină aproape imposibilă. Rezolvarea problemei necesită o abordare diferită. Pentru un sistem arbitrar de ecuații, nu există altă metodă generală decât enumerarea care să permită rezolvarea unor astfel de probleme.

În problemele propuse la examen, soluția se bazează de obicei pe luarea în considerare a specificului sistemului de ecuații. Repet, în afară de a încerca toate opțiunile pentru un set de variabile, nu există o modalitate generală de a rezolva problema. Soluția trebuie construită pe baza specificului sistemului. Este adesea util să se efectueze o simplificare preliminară a unui sistem de ecuații folosind legile logice cunoscute. O altă tehnică utilă pentru rezolvarea acestei probleme este următoarea. Nu ne interesează toate mulțimile, ci doar acelea pe care funcția are valoarea 1. În loc să construim un tabel de adevăr complet, vom construi analogul său - un arbore de decizie binar. Fiecare ramură a acestui arbore corespunde unei soluții și specifică o mulțime pe care funcția are valoarea 1. Numărul de ramuri din arborele de decizie coincide cu numărul de soluții ale sistemului de ecuații.

Voi explica ce este un arbore de decizie binar și cum este construit folosind exemple de mai multe probleme.

Problema 18

Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care satisfac sistemul de două ecuații?

Răspuns: Sistemul are 36 de soluții diferite.

Rezolvare: Sistemul de ecuații include două ecuații. Să găsim numărul de soluții pentru prima ecuație, în funcție de 5 variabile - . Prima ecuație poate fi considerată la rândul său ca un sistem de 5 ecuații. După cum sa arătat, sistemul de ecuații reprezintă de fapt conjuncția funcțiilor logice. Afirmația inversă este de asemenea adevărată - o conjuncție de condiții poate fi considerată ca un sistem de ecuații.

Să construim un arbore de decizie pentru implicația () - primul termen al conjuncției, care poate fi considerat ca prima ecuație. Așa arată o reprezentare grafică a acestui arbore

Arborele este format din două niveluri în funcție de numărul de variabile din ecuație. Primul nivel descrie prima variabilă. Două ramuri ale acestui nivel reflectă valorile posibile ale acestei variabile - 1 și 0. La al doilea nivel, ramurile arborelui reflectă numai acele valori posibile ale variabilei pentru care ecuația evaluează drept adevărat. Întrucât ecuația specifică o implicație, o ramură pe care are valoarea 1 necesită ca pe această ramură să existe o valoare de 1. O ramură pe care are valoarea 0 generează două ramuri cu valori egale cu 0 și 1. Construcția arborele specifică trei soluții, dintre care implicația ia valoarea 1. Pe fiecare ramură este scris un set corespunzător de valori variabile, dând o soluție ecuației.

Aceste seturi sunt: ​​((1, 1), (0, 1), (0, 0))

Să continuăm construirea arborelui de decizie adăugând următoarea ecuație, următoarea implicație. Specificul sistemului nostru de ecuații este 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 în arbore, atunci pe toate ramurile în care variabila are valoarea 1, variabila va avea și valoarea 1. Pentru astfel de ramuri, construcția arborelui continuă la nivelul următor, dar nu apar ramuri noi. O singură ramură în care o variabilă are valoarea 0 se va ramifica în două ramuri în care variabila va primi valori de 0 și 1. Astfel, fiecare adăugare a unei noi ecuații, dată fiind specificitatea acesteia, adaugă o soluție. Prima ecuație originală:

are 6 solutii. Iată cum arată arborele de decizie complet pentru această ecuație:

A doua ecuație a sistemului nostru este similară cu prima:

Singura diferență este că ecuația folosește variabile Y. Această ecuație are și 6 soluții. Deoarece fiecare soluție variabilă poate fi combinată cu fiecare soluție variabilă, numărul total de soluții este de 36.

Vă rugăm să rețineți că arborele de decizie construit oferă nu numai numărul de soluții (în funcție de numărul de ramuri), ci și soluțiile în sine scrise pe fiecare ramură a arborelui.

Problema 19

Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care îndeplinesc 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.

Din ecuație rezultă că atunci când are valoarea 1 (există o astfel de soluție), atunci are valoarea 1. Astfel, există o mulțime pe care și are valori de 1. Când este egal cu 0, poate au orice valoare, atât 0, cât și 1. Prin urmare, fiecare mulțime cu , egală cu 0 și există 5 astfel de mulțimi, corespunde tuturor celor 6 mulțimi cu variabile Y. Prin urmare, numărul total de soluții este 31.

Problema 20

Rezolvare: amintindu-ne echivalențele de bază, scriem ecuația noastră ca:

Lanțul ciclic de implicații înseamnă că variabilele sunt identice, deci ecuația noastră este echivalentă cu ecuația:

Această ecuație are două soluții când toate sunt fie 1, fie 0.

Problema 21

Câte soluții are ecuația:

Soluție: La fel ca în problema 20, trecem de la implicațiile ciclice la identități, rescriind ecuația sub forma:

Să construim un arbore de decizie pentru această ecuație:

Problema 22

Câte soluții are următorul sistem de ecuații?