Sisteme de ecuații logice. Logici. Funcții logice. Rezolvarea ecuațiilor

Scopul serviciului. Calculatorul online este conceput pentru construirea unui tabel de adevăr pentru o expresie logică.
Tabel de adevăr – un tabel care conține toate combinațiile posibile de variabile de intrare și valorile lor de ieșire corespunzătoare.
Tabelul de adevăr conține 2n rânduri, unde n este numărul de variabile de intrare și n+m sunt coloane, unde m sunt variabile de ieșire.

Instrucțiuni. Când introduceți de la tastatură, utilizați următoarele convenții:

Expresie booleană:

Derivarea tabelelor intermediare pentru tabelul de adevăr
Construcția SKNF
Construcția SDNF
Construcția polinomului Zhegalkin
Construcția hărții Veitch-Karnaugh
Minimizarea unei funcții booleene

De exemplu, expresia logică abc+ab~c+a~bc trebuie introdusă astfel: a*b*c+a*b=c+a=b*c
Pentru a introduce date sub forma unei diagrame logice, utilizați acest serviciu.

Reguli pentru introducerea unei funcții logice

1. În loc de simbolul v (disjuncție, SAU), utilizați semnul +.
2. Nu este nevoie să specificați o desemnare a funcției înainte de o funcție logică. De exemplu, în loc de F(x,y)=(x|y)=(x^y) trebuie să introduceți pur și simplu (x|y)=(x^y) .
3. Suma maximă variabile este egală cu 10.

Proiectarea și analiza circuitelor logice computerizate se realizează folosind o ramură specială a matematicii - algebra logică. În algebra logicii se pot distinge trei funcții logice principale: „NU” (negație), „ȘI” (conjuncție), „SAU” (disjuncție).
Pentru a crea orice dispozitiv logic, este necesar să se determine dependența fiecăreia dintre variabilele de ieșire de variabilele de intrare existente; această dependență se numește funcție de comutare sau funcție de algebră logică.
O funcție de algebră logică se numește complet definită dacă sunt date toate cele 2n dintre valorile sale, unde n este numărul de variabile de ieșire.
Dacă nu toate valorile sunt definite, funcția se numește parțial definită.
Un dispozitiv este numit logic dacă starea lui este descrisă folosind o funcție de algebră logică.
Următoarele metode sunt utilizate pentru a reprezenta o funcție algebrică logică:
În formă algebrică, puteți construi un circuit al unui dispozitiv logic folosind elemente logice.


Figura 1 - Diagrama dispozitivului logic

Toate operațiile algebrei logicii sunt definite tabele de adevăr valorile. Tabelul de adevăr determină rezultatul unei operații pentru oricine este posibil x valorile logice ale afirmațiilor originale. Numărul de opțiuni care reflectă rezultatul aplicării operațiilor va depinde de numărul de instrucțiuni din expresia logică. Dacă numărul de afirmații dintr-o expresie logică este N, atunci tabelul de adevăr va conține 2 N rânduri, deoarece există 2 N combinații diferite de valori posibile ale argumentului.

Operațiunea NOT - negație logică (inversie)

O operație logică NU se aplică unui singur argument, care poate fi o expresie logică simplă sau complexă. Rezultatul operației NU este următorul:

• dacă expresia originală este adevărată, atunci rezultatul negației sale va fi fals;
• dacă expresia originală este falsă, atunci rezultatul negației sale va fi adevărat.

Următoarele convenții NU sunt acceptate pentru operația de negație:
nu A, Â, nu A, ¬A, !A
Rezultatul operației de negație NU este determinat de următorul tabel de adevăr:

A	nu A
0	1
1	0

Rezultatul operației de negație este adevărat atunci când afirmația inițială este falsă și invers.

Operație SAU - adunare logică (disjuncție, unire)

Operația logic OR îndeplinește funcția de a combina două instrucțiuni, care pot fi fie o expresie logică simplă, fie o expresie logică complexă. Declarațiile care sunt punctele de plecare pentru o operație logică se numesc argumente. Rezultatul operației SAU este o expresie care va fi adevărată dacă și numai dacă cel puțin una dintre expresiile originale este adevărată.
Denumiri utilizate: A sau B, A V B, A sau B, A||B.
Rezultatul operației OR este determinat de următorul tabel de adevăr:
Rezultatul operației SAU este adevărat atunci când A este adevărat, sau B este adevărat sau ambele A și B sunt adevărate și false când argumentele A și B sunt false.

Operația ȘI - înmulțire logică (conjuncție)

Operația logică AND îndeplinește funcția de intersecție a două afirmații (argumente), care poate fi fie o expresie logică simplă, fie o expresie logică complexă. Rezultatul operației AND este o expresie care va fi adevărată dacă și numai dacă ambele expresii originale sunt adevărate.
Denumirile utilizate: A și B, A Λ B, A și B, A și B.
Rezultatul operației AND este determinat de următorul tabel de adevăr:

A	B	A și B
0	0	0
0	1	0
1	0	0
1	1	1

Rezultatul operației AND este adevărat dacă și numai dacă afirmațiile A și B sunt ambele adevărate și false în toate celelalte cazuri.

Operațiunea „IF-THEN” - consecință logică (implicație)

Această operație conectează două expresii logice simple, dintre care prima este o condiție, iar a doua este o consecință a acestei condiții.
Denumiri folosite:
dacă A, atunci B; A implică B; dacă A atunci B; A→B.
Tabelul de adevăr:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Rezultatul operației de implicare este fals numai dacă premisa A este adevărată și concluzia B (consecința) este falsă.

Operația „A dacă și numai dacă B” (echivalență, echivalență)

Denumirea utilizată: A ↔ B, A ~ B.
Tabelul de adevăr:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operația „Adăugare modulo 2” (XOR, exclusiv sau, disjuncție strictă)

Notația folosită: A XOR B, A ⊕ B.
Tabelul de adevăr:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Rezultatul operației de echivalență este adevărat numai dacă A și B sunt ambele adevărate sau false în același timp.

Prioritatea operațiilor logice

• Acțiuni între paranteze
• Inversiunea
• Conjuncție (&)
• Disjuncție (V), SAU exclusiv (XOR), suma modulo 2
• Implicație (→)
• Echivalență (↔)

Forma normală disjunctivă perfectă

Forma normală disjunctivă perfectă a unei formule(SDNF) este o formulă echivalentă, care este o disjuncție a conjuncțiilor elementare și are următoarele proprietăți:

1. Fiecare termen logic al formulei conține toate variabilele incluse în funcția F(x 1,x 2,...x n).
2. Toți termenii logici ai formulei sunt diferiți.
3. Niciun termen logic nu conține o variabilă și negația acesteia.
4. Niciun termen logic dintr-o formulă nu conține aceeași variabilă de două ori.

SDNF poate fi obținut fie folosind tabele de adevăr, fie folosind transformări echivalente.
Pentru fiecare funcție, SDNF și SCNF sunt definite în mod unic până la permutare.

Forma normală conjunctivă perfectă

Forma normală conjunctivă perfectă a unei formule (SCNF) Aceasta este o formulă echivalentă cu aceasta, care este o conjuncție de disjuncții elementare și satisface proprietățile:

1. Toate disjuncțiile elementare conțin toate variabilele incluse în funcția F(x 1 ,x 2 ,...x n).
2. Toate disjuncțiile elementare sunt diferite.
3. Fiecare disjuncție elementară conține o variabilă o dată.
4. Nici o singură disjuncție elementară nu conține o variabilă și negația ei.

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

Lecția #3. Logici. 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?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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 bun 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:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

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 decurg doar două lucruri: opțiuni posibile- A și B sunt vinovați, iar C este nevinovat, sau A și C sunt vinovați și B este nevinovat. Depoziția primului martor este mai puțin informativă - sunt 5 diverse opțiuni, corespunzător 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ăr variabilele ecuației. 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 , atunci numărul total Există 36 de soluții.

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. Asa de sarcină dificilă obținerea unui set de valori variabile după un număr stabilit se rezumă la binecunoscuta problemă a conversiei unui număr în sistemul binar.

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

///

/// program de numărare a numărului de soluții

/// ecuație logică (sistem de ecuații)

///

///

/// 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 urmare, 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, folosim mai mult design 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:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

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 variabila logică P i să ia valoarea 1 când este la i-a aruncare monedele ies din cap. 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)

Acest material conține o prezentare care prezintă metode de rezolvare a ecuațiilor logice și a sistemelor de ecuații logice în sarcina B15 (Nr. 23, 2015) a Examenului Unificat de Stat în informatică. Se știe că această sarcină este una dintre cele mai dificile dintre sarcinile de examinare unificată de stat. Prezentarea poate fi utilă atunci când predați lecții pe tema „Logică” în clase de specialitate, precum și atunci când vă pregătiți pentru Examenul de stat unificat.

Descarca:

Previzualizare:

Pentru a utiliza previzualizările prezentării, creați un cont Google și conectați-vă la el: https://accounts.google.com

Subtitrările diapozitivelor:

Rezolvarea sarcinii B15 (sisteme de ecuații logice) Vishnevskaya M.P., MAOU „Gymnasium No. 3” 18 noiembrie 2013, Saratov

Sarcina B15 este una dintre cele mai dificile din examenul de stat unificat în informatică!!! Sunt testate următoarele abilități: convertirea expresiilor care conțin variabile logice; descrieți în limbaj natural setul de valori ale variabilelor logice pentru care un anumit set de variabile logice este adevărat; numărați numărul de mulțimi binare care îndeplinesc condițiile date. Cel mai dificil lucru este pentru că... nu există reguli formale cu privire la modul de a face acest lucru, necesită presupuneri.

De ce nu te poți descurca fără!

De ce nu te poți descurca fără!

Conjuncție simboluri: A /\ B , A  B , AB , A &B, A și B disjuncție: A \ / B , A + B , A | B , A sau B negație:  A , A, nu A echivalență: A  B, A  B, A  B exclusiv „sau”: A  B , A xor B

Metoda de înlocuire a variabilelor Câte seturi diferite de valori ale variabilelor logice x1, x2, ..., x9, x10 există care îndeplinesc toate condițiile enumerate mai jos: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ ​​(¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ ​​​​(¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ​​​​(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ ​​​​(¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Răspunsul nu trebuie să enumere toate seturile diferite x1, x2, …, x9, x10 pentru care acest sistem de egalităţi este valabil. Ca răspuns, trebuie să indicați numărul de astfel de seturi (versiunea demo 2012)

Soluție Pasul 1. Simplificați prin modificarea variabilelor t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 După simplificare: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Luați în considerare una dintre ecuațiile: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Evident, este =1 numai dacă una dintre variabile este 0 și cealaltă este 1 . Să folosim formula pentru a exprima operația XOR prin conjuncție și disjuncție: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Pasul 2. Analiza sistemului ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .La. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), atunci fiecare valoare a lui tk corespunde la două perechi de valori x2k-1 și x2k, de exemplu: tk =0 corespunde la două perechi - (0 ,1) și (1, 0) și tk =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 ts este 5. Astfel. pentru variabilele t există 2 5 = 32 soluții. Dar pentru fiecare t îi corespunde o pereche de soluții x, adică. sistemul original are 2*32 = 64 solutii. Raspuns: 64

Metoda de eliminare a unei părți a soluțiilor Câte seturi diferite de valori ale variabilelor logice x1, x2, ..., x5, y1, y2,..., 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; y5→ x5 =1. Răspunsul nu trebuie să enumere toate mulțimile diferite x1, x2, ..., x5, y 1 , y2, ... , y5 pentru care acest sistem de egalități este valabil. Răspunsul trebuie să indice numărul de astfel de seturi.

Soluţie. Pasul 1. Soluție secvențială 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 este conjuncţia mai multor operaţii de implicare, egale cu 1, adică. fiecare dintre implicații este adevărată. Implicația este falsă doar într-un caz, când 1  0, în toate celelalte cazuri (0  0, 0  1, 1  1) operația returnează 1. Să scriem asta sub formă de tabel:

Pasul 1. Rezolvarea secvenţială a ecuaţiilor T.o. S-au obținut 6 seturi de soluții pentru x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Raționând în mod similar, ajungem la concluzia că pentru y1, y2, y3, y4, y5 există același set de soluții. Deoarece aceste ecuații sunt independente, adică nu au variabile comune, atunci soluția acestui sistem de ecuații (fără a lua în considerare a treia ecuație) va fi 6 * 6 = 36 de perechi de „X” și „Y”. Luați în considerare a treia ecuație: y5→ x5 =1 Soluția este perechile: 0 0 0 1 1 1 Perechea nu este o soluție: 1 0

Să comparăm soluțiile obținute.Unde y5 =1, x5=0 nu este potrivit. există 5 astfel de perechi.Numărul de soluții ale sistemului: 36-5= 31. Raspuns: Era nevoie de 31 de combinatorice!!!

Metoda de programare dinamică Câte soluții diferite are ecuația logică x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, unde x 1, x 2, …, x 6 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 cantitățile de astfel de seturi.

Soluția Pasul 1. Analiza condiției În stânga în ecuație se scriu secvențial operațiile de implicare, prioritatea fiind aceeași. Să rescriem: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Fiecare variabilă ulterioară depinde nu de cea anterioară, ci de rezultatul implicației anterioare!

Pasul 2. Dezvăluirea tiparului Să luăm în considerare prima implicație, X 1 → X 2. Tabelul de adevăr: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Din unul 0 avem 2 unități, iar din 1 avem un 0 și unul 1. Există doar un 0 și trei 1, acesta este rezultatul primei operații.

Pasul 2. Dezvăluirea unui model Conectând x 3 la rezultatul primei operații, obținem: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Din doi 0 – doi 1, din fiecare 1 (sunt 3) unul 0 și unul 1 (3+3)

Pasul 3. Derivarea formulei T.o. puteți crea formule pentru calcularea numărului de zerouri N i și a numărului de unități E i pentru o ecuație cu i variabile: ,

Pasul 4. Completarea tabelului Să completăm tabelul de la stânga la dreapta pentru i = 6, calculând numărul de zerouri și unu folosind formulele de mai sus; tabelul arată cum se construiește următoarea coloană din cea anterioară: numărul de variabile 1 2 3 4 5 6 Numărul de zerouri N i 1 1 3 5 11 21 Numărul de unități E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Răspuns: 43

Metodă folosind simplificări ale expresiilor logice Câte soluții diferite are ecuația ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 unde J, K, L, M, N sunt variabile logice? Răspunsul nu trebuie să enumere toate seturile diferite de valori ale lui J, K, L, M și N pentru care această egalitate este valabilă. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluție Rețineți că J → K = ¬ J  K Să introducem o modificare de variabile: J → K=A, M  N  L =B Să rescriem ecuația ținând cont de modificarea: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Evident, A  B pentru aceleași valori ale lui A și B 6. Luați în considerare ultima implicație M → J =1 Acest lucru este posibil dacă: M= J=0 M=0, J=1 M=J=1

Soluție Pentru că A  B, atunci când M=J=0 obținem 1 + K=0. Fara solutii. Când M=0, J=1 obținem 0 + K=0, K=0, iar N și L sunt oricare, 4 soluții: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Soluția 10. Când M=J=1 obținem 0+K=1 *N * L, sau K=N*L, 4 soluții: 11. Total are 4+4=8 soluții Răspuns: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Surse de informare: O.B. Bogomolova, D.Yu. Usenkov. B15: sarcini noi și soluții noi // Informatică, nr. 6, 2012, p. 35 – 39. K.Yu. Poliakov. Ecuații logice // Informatică, Nr. 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [Resursa electronică]. http://kpolyakov.narod.ru/school/ege.htm, [Resursa electronică].

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?

Tema lecției: Rezolvarea ecuațiilor logice

Educational - studierea metodelor de rezolvare a ecuațiilor logice, dezvoltarea abilităților de rezolvare a ecuațiilor logice și construirea unei expresii logice folosind un tabel de adevăr;

Dezvoltare - să creeze condiții pentru dezvoltarea interesului cognitiv al elevilor, să promoveze dezvoltarea memoriei, a atenției, gandire logica;

Educational : promovează capacitatea de a asculta opiniile altora, cultivarea voinței și perseverenței pentru a obține rezultatele finale.

Tip de lecție: lecție combinată

Echipament: computer, proiector multimedia, prezentare 6.

În timpul orelor

Repetarea și actualizarea cunoștințelor de bază. Examinare teme pentru acasă(10 minute)

În lecțiile anterioare, ne-am familiarizat cu legile de bază ale algebrei logice și am învățat să folosim aceste legi pentru a simplifica expresiile logice.

Să ne verificăm temele despre simplificarea expresiilor logice:

1. Care dintre următoarele cuvinte satisface condiția logică:

(prima literă consoană → a doua literă consoană)٨ (vocala ultima literă → vocala penultima literă)? Dacă există mai multe astfel de cuvinte, indicați cel mai mic dintre ele.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Să introducem următoarea notație:

A – prima literă consoană

B – consoana a doua litera

S – vocala ultimei litere

D – penultima literă vocală

Să facem o expresie:

Să facem un tabel:

2. Indicați ce expresie logică este echivalentă cu expresia

Să simplificăm înregistrarea expresiei originale și a opțiunilor propuse:

3. Având în vedere un fragment din tabelul de adevăr al expresiei F:

Care expresie se potrivește cu F?

Să determinăm valorile acestor expresii pentru valorile specificate ale argumentelor:

Introducere în tema lecției, prezentare de material nou (30 minute)

Continuăm să studiem elementele de bază ale logicii, iar subiectul lecției noastre de astăzi este „Rezolvarea ecuațiilor logice”. După ce ați studiat acest subiect, veți învăța modalitățile de bază de rezolvare a ecuațiilor logice, veți dobândi abilitățile de a rezolva aceste ecuații folosind limbajul algebrei logice și abilitatea de a compune o expresie logică folosind un tabel de adevăr.

1. Rezolvați o ecuație logică

(¬K M) → (¬L M N) =0

Scrieți răspunsul ca un șir de patru caractere: valorile variabilelor K, L, M și N (în această ordine). Deci, de exemplu, linia 1101 corespunde faptului că K=1, L=1, M=0, N=1.

Soluţie:

Să transformăm expresia(¬K  M) → (¬L  M  N)

O expresie este falsă atunci când ambii termeni sunt falși. Al doilea termen este egal cu 0 dacă M =0, N =0, L =1. În primul termen K = 0, deoarece M = 0, și
.

Raspuns: 0100

2. Câte soluții are ecuația (indicați doar numărul din răspunsul dvs.)?

Soluție: transformați expresia

(A +B)*(C +D)=1

A +B =1 și C +D =1

Metoda 2: întocmirea unui tabel de adevăr

3 căi: construcția unui SDNF - o formă normală disjunctivă perfectă pentru o funcție - o disjuncție a conjuncțiilor elementare regulate complete.

Să transformăm expresia originală, să deschidem parantezele pentru a obține disjuncția conjuncțiilor:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Să suplimentăm conjuncțiile pentru a completa conjuncțiile (produsul tuturor argumentelor), deschidem parantezele:

Să luăm în considerare aceleași conjuncții:

Ca rezultat, obținem un SDNF care conține 9 conjuncții. Prin urmare, tabelul de adevăr pentru această funcție are valoarea 1 în 9 rânduri de 2 4 = 16 seturi de valori variabile.

3. Câte soluții are ecuația (indicați doar numărul din răspunsul dvs.)?

Să simplificăm expresia:

,

3 căi: construcția SDNF

Să luăm în considerare aceleași conjuncții:

Ca rezultat, obținem un SDNF care conține 5 conjuncții. Prin urmare, tabelul de adevăr pentru această funcție are valoarea 1 pe 5 rânduri de 2 4 = 16 seturi de valori variabile.

Construirea unei expresii logice folosind un tabel de adevăr:

pentru fiecare rând al tabelului de adevăr care conține 1, compunem un produs de argumente, iar variabilele egale cu 0 sunt incluse în produs cu negație, iar variabilele egale cu 1 sunt incluse fără negație. Expresia dorită F va fi compusă din suma produselor rezultate. Apoi, dacă este posibil, această expresie ar trebui simplificată.

Exemplu: este dat un tabel de adevăr al unei expresii. Construiți o expresie logică.

Soluţie:

3. Tema pentru acasă (5 minute)

Rezolvați ecuația:

Câte soluții are ecuația (indicați doar numărul din răspunsul dvs.)?

Folosind un tabel de adevăr dat, construiți o expresie logică și

simplifica-l.