Noskin Andrei Nikolaevici,
profesor de IT
cea mai înaltă categorie de calificare,
Candidat la științe militare, conferențiar
Liceul GBOU №1575 Moscova
Metodă de cartografiere optimizată pentru rezolvarea problemei 23 din KIM USE în Informatică și TIC
Una dintre cele mai dificile sarcini din KIM USE este sarcina 23, în care trebuie să găsiți numărul de seturi diferite de valori ale variabilelor logice care îndeplinesc condiția specificată.
Această sarcină este poate cea mai mare sarcină dificilă KIM USE în informatică și TIC. De regulă, nu mai mult de 5% dintre examinați îi fac față (1).
Un procent atât de mic de studenți care au finalizat această sarcină se explică prin următoarele:
- elevii pot confunda (uita) semnele operaţiilor logice;
- erori matematice în procesul de efectuare a calculelor;
- erori de raționament la căutarea unei soluții;
- erori în procesul de simplificare a expresiilor logice;
- profesorii recomandă rezolvarea acestei probleme după finalizarea tuturor lucrărilor, deoarece probabilitatea de a face o presupunere
erorile este foarte mare, iar „greutatea” sarcinii este doar un punctaj primar.
În plus, unor profesori înșiși le este greu să rezolve acest tip de probleme și, prin urmare, încearcă să rezolve probleme mai simple cu copiii.
Se complică și situația pe care o există în acest bloc un numar mare de varietate de sarcini și este imposibil să găsiți o soluție șablon.
Pentru a corecta această situație, comunitatea pedagogică finalizează principalele două metode de rezolvare a problemelor de acest tip: soluție șir de biți (2) și metoda de cartografiere (3).
Necesitatea de a rafina (optimiza) aceste metode se datorează faptului că sarcinile sunt în continuă schimbare atât ca structură, cât și ca număr de variabile (doar un tip de variabile X, două tipuri de variabile X și Y, trei tipuri: X, Y , Z).
Complexitatea stăpânirii acestor metode de rezolvare a problemelor este confirmată de faptul că pe site-ul K.Yu. Polyakov, există analize ale acestui tip de probleme în valoare de 38 de bucăți (4). În unele analize, se oferă mai mult de un tip de soluție de problemă.
Timpuri recenteîn KIM USE în informatică există sarcini cu două tipuri de variabile X și Y.
Am optimizat metoda de afișare și sugerez studenților mei să folosească metoda îmbunătățită.
Aceasta dă un rezultat. Procentul studenților mei care termină această sarcină variază până la 43% dintre trecători. De regulă, în fiecare an de la 25 la 33 de persoane din toate clasele a XI-a trec examenul de informatică.
Înainte de apariția sarcinilor cu două tipuri de variabile, metoda afișajului era folosită de elevi cu mare succes, dar după apariția în expresia logică Y am început să observ că răspunsurile copiilor nu mai coincid cu testele. S-a dovedit că nu au înțeles foarte clar cum să creeze un tabel de mapare cu un nou tip de variabilă. Apoi mi-a venit gândul că, pentru comoditate, este necesar să aducem întreaga expresie la un singur tip de variabilă, deoarece este convenabil pentru copii.
Permiteți-mi să descriu această metodă mai detaliat. Pentru comoditate, îl voi lua în considerare folosind exemplul unui sistem de expresii logice dat în (4).
Cum diverse solutii are un sistem de ecuații logice
(x 1 ^ y1)=(¬x 2 V ¬
y 2
)
(x2 ^ y2)= (¬
X 3
V ¬
y 3
)
...
(x5 ^ y 5)
= (¬
X 6
V ¬
y 6
)
Soluţie:
1. Din analiza sistemului de ecuații logice, vedem că sunt 6 variabile Xși 6 variabile La. Deoarece oricare dintre aceste variabile poate lua doar două valori (0 și 1), vom înlocui aceste variabile cu 12 variabile de același tip, de exemplu Z.
2. Acum să rescriem sistemul cu variabile noi de același tip. Complexitatea sarcinii va consta în notarea atentă la schimbarea variabilelor.
(z1 ^ z2)=
(¬z 3V¬
z 4
)
(z3 ^ z4)=
(¬
z 5
V¬
z 6
)
...
(z9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Să construim un tabel în care vom sorta toate opțiunile z 1 , z 2 , z 3 , z 4 , deoarece sunt patru variabile în prima ecuație logică, tabelul va avea 16 rânduri (16=2 4); eliminați astfel de valori din tabel z 4 , pentru care prima ecuație nu are soluție (numerele tăiate).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Analizând tabelul, construim o regulă pentru afișarea perechilor de variabile (de exemplu, o pereche Z 1 Z 2 =00 meciuri pereche Z 3 Z 4 = 11) .
5. Completați tabelul calculând numărul de perechi de variabile pentru care sistemul are o soluție. 
6. Adună toate rezultatele: 9 + 9 + 9 + 27 = 54
7. Raspuns: 54.
Metoda optimizată de mai sus pentru rezolvarea problemei 23 din KIM USE a permis elevilor să-și recapete încrederea și să rezolve cu succes acest tip de problemă.
Literatură:
1. FIPI. Instrucțiuni pentru profesori, pregătit pe baza unei analize a greșelilor tipice ale participanților la USE 2015 în INFORMATICĂ și TIC. Mod de acces: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Polyakov, M.A. Roitberg.Sisteme de ecuații logice: soluție folosind șiruri de biți. Jurnal Informatică, Nr. 12, 2014, p. 4-12. Editura „Primul septembrie”, Moscova.3. E.A. Mironchik, Metoda de afișare. Revistă Informatică, Nr. 10, 2013, p. 18-26. Editura „Primul septembrie”, Moscova.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, unde J, K, L, M, N sunt variabile booleene?
Explicaţie.
Expresia (N ∨ ¬N) este adevărată pentru orice N, deci
J ∧ ¬K ∧ L ∧ ¬M = 0.
Aplicați negația ambelor părți ale ecuației logice și folosiți legea lui De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B. Obținem ¬J ∨ K ∨ ¬L ∨ M = 1.
Suma logică este egală cu 1 dacă cel puțin una dintre afirmațiile sale constitutive este egală cu 1. Prin urmare, orice combinație de variabile logice satisface ecuația rezultată, cu excepția cazului în care toate mărimile incluse în ecuație sunt egale cu 0. Fiecare dintre cele 4 variabile pot fi egale fie cu 1, fie cu 0, deci posibile combinații 2 2 2 2 = 16. Prin urmare, ecuația are 16 −1 = 15 soluții.
Rămâne de menționat că cele 15 soluții găsite corespund oricăreia dintre cele două valori posibile valorile variabilei logice N, deci ecuația originală are 30 de soluții.
Raspuns: 30
Câte soluții diferite are ecuația
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
unde J, K, L, M, N sunt variabile booleene?
Răspunsul nu trebuie să enumere toate seturile diferite de valori J, K, L, M și N pentru care este valabilă această egalitate. Ca răspuns, trebuie să indicați numărul de astfel de seturi.
Explicaţie.
Folosim formulele A → B = ¬A ∨ B și ¬(A ∨ B) = ¬A ∧ ¬B
Luați în considerare prima subformulă:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Luați în considerare a doua subformulă
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Luați în considerare a treia subformulă
1) M → J = 1 deci
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Combina:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 deci 4 soluții.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Combina:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L deci există 4 soluții.
c) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Răspuns: 4 + 4 = 8.
Raspuns: 8
Câte soluții diferite are ecuația
((K ∨ L) → (L ∧ M ∧ N)) = 0
unde K, L, M, N sunt variabile booleene? Răspunsul nu trebuie să enumere toate seturile diferite de valori K, L, M și N pentru care este valabilă această egalitate. Ca răspuns, trebuie să indicați numărul de astfel de seturi.
Explicaţie.
Să rescriem ecuația folosind o notație mai simplă pentru operații:
((K + L) → (L M N)) = 0
1) din tabelul de adevăr al operației de „implicație” (vezi prima problemă) rezultă că această egalitate este adevărată dacă și numai dacă simultan
K + L = 1 și L M N = 0
2) din prima ecuație rezultă că cel puțin una dintre variabile, K sau L, este egală cu 1 (sau ambele împreună); deci luați în considerare trei cazuri
3) dacă K = 1 și L = 0, atunci a doua egalitate este valabilă pentru orice M și N; deoarece există 4 combinații de două variabile booleene (00, 01, 10 și 11), avem 4 soluții diferite
4) dacă K = 1 și L = 1, atunci a doua egalitate este valabilă pentru M · N = 0; sunt 3 astfel de combinatii (00, 01 si 10), mai avem 3 solutii
5) dacă K = 0, atunci neapărat L = 1 (din prima ecuație); în acest caz, a doua egalitate este satisfăcută la М · N = 0; sunt 3 astfel de combinatii (00, 01 si 10), mai avem 3 solutii
6) în total obținem 4 + 3 + 3 = 10 soluții.
Raspuns: 10
Câte soluții diferite are ecuația
(K ∧ L) ∨ (M ∧ N) = 1
Explicaţie.
Expresia este adevărată în trei cazuri când (K ∧ L) și (M ∧ N) sunt 01, 11, respectiv 10.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N sunt 1, iar K și L sunt oricare, cu excepția ambelor 1. Prin urmare, 3 soluții.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 soluție.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 soluții.
Raspuns: 7.
Raspuns: 7
Câte soluții diferite are ecuația
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
unde X, Y, Z, P sunt variabile booleene? Răspunsul nu trebuie să enumere toate seturile diferite de valori pentru care este valabilă această egalitate. Ca răspuns, trebuie să furnizați doar numărul de astfel de seturi.
Explicaţie.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
SAU logic este fals doar într-un caz: când ambele expresii sunt false.
Prin urmare,
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Prin urmare, există o singură soluție a ecuației.
Raspunsul 1
Câte soluții diferite are ecuația
(K ∨ L) ∧ (M ∨ N) = 1
unde K, L, M, N sunt variabile booleene? Răspunsul nu trebuie să enumere toate seturile diferite de valori ale lui K, L, M și N pentru care este valabilă această egalitate. Ca răspuns, trebuie să furnizați doar numărul de astfel de seturi.
Explicaţie.
ȘI logic este adevărat doar într-un caz: când toate expresiile sunt adevărate.
K ∨ L = 1, M ∨ N = 1.
Fiecare dintre ecuații oferă 3 soluții.
Luați în considerare ecuația A ∧ B = 1 dacă atât A cât și B iau valori adevărate în trei cazuri fiecare, atunci, în general, ecuația are 9 soluții.
Prin urmare, răspunsul este 9.
Raspuns: 9
Câte soluții diferite are ecuația
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
unde A, B, C, D sunt variabile booleene?
Răspunsul nu trebuie să enumere toate seturile diferite de valori A, B, C, D pentru care această egalitate este valabilă. Ca răspuns, trebuie să specificați numărul de astfel de seturi.
Explicaţie.
„SAU” logic este adevărat atunci când cel puțin una dintre afirmații este adevărată.
(D ∧ ¬D)= 0 pentru orice D.
Prin urmare,
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, ceea ce ne oferă 3 soluții pentru fiecare D.
(D ∧ ¬ D)=0 pentru orice D, ceea ce ne oferă două soluții (pentru D = 1, D = 0).
Prin urmare: soluții totale 2*3 = 6.
În total 6 soluții.
Raspuns: 6
Câte soluții diferite are ecuația
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
unde K, L, M, N sunt variabile booleene? Răspunsul nu trebuie să enumere toate seturile diferite de valori ale lui K, L, M și N pentru care este valabilă această egalitate. Ca răspuns, trebuie să furnizați doar numărul de astfel de seturi.
Explicaţie.
Aplicați negația ambelor părți ale ecuației:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
SAU logic este adevărat în trei cazuri.
Opțiunea 1.
K ∧ L ∧ M = 1, apoi K, L, M = 1 și ¬L ∧ M ∧ N = 0. Orice N, adică 2 soluții.
Opțiunea 2.
¬L ∧ M ∧ N = 1, apoi N, M = 1; L = 0, K oricare, adică 2 soluții.
Prin urmare, răspunsul este 4.
Raspuns: 4
A, B și C sunt numere întregi pentru care afirmația este adevărată
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Cu ce este B egal dacă A = 45 și C = 43?
Explicaţie.
1) ¬(A = B); (A > B)→(B > C); (B>A)→(C>B);
2) aceste afirmații simple sunt legate prin operația ∧ (ȘI, conjuncție), adică trebuie efectuate simultan;
3) din ¬(А = B)=1 rezultă imediat că А B;
4) să presupunem că A > B, atunci din a doua condiție obținem 1→(B > C)=1; această expresie poate fi adevărată dacă și numai dacă B > C = 1;
5) deci avem A > B > C, numai numarul 44 corespunde acestei conditii;
6) pentru orice eventualitate, verificați varianta A 0 →(B > C)=1;
această expresie este adevărată pentru orice B; acum ne uităm la a treia condiție, obținem
această expresie poate fi adevărată dacă și numai dacă C > B, și aici avem o contradicție, deoarece nu există un astfel de număr B pentru care C > B > A.
Raspuns: 44.
Raspuns: 44
Faceți un tabel de adevăr pentru o funcție logică
X = (A ↔ B) ∨ ¬(A → (B ∨ C))
în care coloana valorilor argumentului A este notația binară a numărului 27, coloana valorilor argumentului B este numărul 77, coloana valorilor argumentului C este numărul 120. Numărul din coloană se scrie de sus în jos de la cea mai semnificativă cifră la cea mai puțin semnificativă (inclusiv setul zero). Convertiți reprezentarea binară rezultată a valorilor funcției X în sistemul numeric zecimal.
Explicaţie.
Scriem ecuația folosind o notație mai simplă pentru operații:
1) aceasta este o expresie cu trei variabile, deci vor exista linii în tabelul de adevăr; prin urmare, notația binară a numerelor prin care sunt construite coloanele tabelului A, B și C trebuie să fie formată din 8 cifre
2) vom traduce numerele 27, 77 și 120 în sistem binar, completând imediat intrarea la 8 caractere cu zerouri la începutul numerelor
3) este puțin probabil să puteți scrie imediat valorile funcției X pentru fiecare combinație, deci este convenabil să adăugați coloane suplimentare la tabel pentru a calcula rezultatele intermediare (vezi tabelul de mai jos)
| DAR | LA | DIN | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) completați coloanele tabelului:
| DAR | LA | DIN | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
valoarea este 1 numai în acele linii în care A = B
valoarea este 1 în acele linii în care fie B, fie C = 1
valoarea este 0 numai în acele rânduri în care A = 1 și B + C = 0
valoarea este inversul coloanei precedente (0 este înlocuit cu 1 și 1 este înlocuit cu 0)
rezultatul X (ultima coloană) este suma logică a celor două coloane și
5) pentru a obține răspunsul, scriem biții din coloana X de sus în jos:
6) traduceți acest număr în sistemul zecimal:
Răspuns: 171
Care este cel mai mare număr întreg X pentru care afirmația (10 (X+1)·(X+2)) este adevărată?
Explicaţie.
O ecuație este o operație de implicare între două relații:
1) Desigur, aici puteți aplica aceeași metodă ca în exemplul 2208, dar în acest caz va trebui să rezolvați ecuații pătratice(nu vreau…);
2) Rețineți că, prin condiție, ne interesează doar numerele întregi, așa că puteți încerca să transformați cumva expresia originală, obținând o declarație echivalentă (valorile exacte ale rădăcinilor nu ne interesează deloc!);
3) Luați în considerare inegalitatea: este evident că poate fi atât un număr pozitiv, cât și unul negativ;
4) Este ușor să verificați dacă afirmația este adevărată pentru toate numerele întregi din domeniu și pentru toate numerele întregi din domeniu (pentru a nu vă confunda, este mai convenabil să folosiți inegalități nestrictive și , în loc de și );
5) Prin urmare, pentru numere întregi, acesta poate fi înlocuit cu o expresie echivalentă
6) regiunea de adevăr a unei expresii este unirea a două intervale infinite;
7) Acum luați în considerare a doua inegalitate: este evident că poate fi și un număr pozitiv și negativ;
8) În regiune, afirmația este adevărată pentru toate numerele întregi, iar în regiune - pentru toate numerele întregi, prin urmare, pentru numerele întregi, poate fi înlocuită cu o expresie echivalentă
9) regiunea de adevăr a expresiei este un interval închis;
10) Expresia dată este adevărată peste tot, cu excepția zonelor în care și ;
11) Rețineți că valoarea nu se mai potrivește, deoarece acolo și , adică implicația dă 0;
12) Când înlocuiți 2, (10 (2+1) · (2+2)), sau 0 → 0 care satisface condiția.
Deci raspunsul este 2.
Raspuns: 2
Care este cel mai mare număr întreg X pentru care afirmația este adevărată?
(50 (X+1) (X+1))?
Explicaţie.
Aplicați transformarea implicației și transformați expresia:
(50 (X+1) (X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Un SAU logic este adevărat atunci când cel puțin o afirmație logică este adevărată. După ce am rezolvat ambele inegalități și ținând cont că vedem că cel mai mare număr întreg pentru care cel puțin unul dintre ele este adevărat este 7 (în figură, o soluție pozitivă a celei de-a doua inegalități este afișată cu galben, iar prima este cu albastru) .
Raspuns: 7
Precizați valorile variabilelor K, L, M, N, pentru care expresia logică
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
fals. Scrieți răspunsul ca șir de 4 caractere: valorile variabilelor K, L, M și N (în această ordine). Deci, de exemplu, linia 1101 corespunde cu K=1, L=1, M=0, N=1.
Explicaţie.
Se dublează sarcina 3584.
Raspuns: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Explicaţie.
Să aplicăm transformarea implicației:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Aplicați negația ambelor părți ale ecuației:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Să transformăm:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Prin urmare, M = 0, N = 0, considerăm acum (¬K ∧ L ∨ M ∧ L):
faptul că M = 0, N = 0 implică că M ∧ L = 0, apoi ¬K ∧ L = 1, adică K = 0, L = 1.
Raspuns: 0100
Precizați valorile variabilelor K, L, M, N, pentru care expresia logică
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
fals. 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 cu K=1, L=1, M=0, N=1.
Explicaţie.
Să scriem ecuația folosind o notație mai simplă a operațiilor (condiția „expresia este falsă” înseamnă că este egală cu zero logic):
1) rezultă din enunțul condiției că expresia trebuie să fie falsă pentru un singur set de variabile
2) din tabelul de adevăr al operației „implicație” rezultă că această expresie este falsă dacă și numai dacă simultan
3) prima egalitate (produsul logic este egal cu 1) este adevărată dacă și numai dacă și ; de aici rezultă (suma logică este egală cu zero), care poate fi numai când ; astfel, am definit deja trei variabile
4) din a doua condiție, , pentru și obținem .
Sarcină duplicată
Raspuns: 1000
Indicați valorile variabilelor logice P, Q, S, T, pentru care expresia logică
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) este falsă.
Scrieți răspunsul ca un șir de patru caractere: valorile variabilelor P, Q, S, T (în această ordine).
Explicaţie.
(1) (Р ∨ ¬Q) = 0
(2) (Q → (S ∨ T)) = 0
(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Aplicați transformarea implicației:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Raspuns: 0100
Precizați valorile variabilelor K, L, M, N, pentru care expresia logică
(K → M) ∨ (L ∧ K) ∨ ¬N
fals. 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 cu K=1, L=1, M=0, N=1.
Explicaţie.
„SAU” logic este fals dacă și numai dacă ambele afirmații sunt false.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Să aplicăm transformarea implicației pentru prima expresie:
¬K ∨ M = 0 => K = 1, M = 0.
Luați în considerare a doua expresie:
(L ∧ K) ∨ ¬N = 0 (vezi rezultatul primei expresii) => L ∨ ¬N = 0 => L = 0, N = 1.
Răspuns: 1001.
Răspuns: 1001
Precizați valorile variabilelor K, L, M, N, pentru care expresia logică
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
Adevărat. 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 cu K=1, L=1, M=0, N=1.
Explicaţie.
„ȘI” logic este adevărat dacă și numai dacă ambele afirmații sunt adevărate.
1) (K → M) = 1 Aplicați transformarea implicației: ¬K ∨ M = 1
2) (K → ¬M) = 1 Aplicați transformarea implicației: ¬K ∨ ¬M = 1
Aceasta înseamnă că K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Raspuns: 0011
Se știe că pentru numerele întregi X, Y și Z afirmația este adevărată
(Z Cu ce este Z egal dacă X=25 și Y=48?
Explicaţie.
Prin înlocuirea numerelor, obținem că Z = 47.
Rețineți că această afirmație complexă constă din trei simple.
1) (Z 2) aceste afirmații simple sunt legate prin operația ∧ (ȘI, conjuncție), adică trebuie efectuate simultan.
3) de la ¬(Z+1 24 și de la ¬(Z+1 47.
4) din (Z Z Răspuns: 47.
Raspuns: 47
A, B și C sunt numere întregi pentru care afirmația este adevărată:
(C Cu ce este C egal dacă A=45 și B=18?
Explicaţie.
„ȘI” logic este adevărat dacă și numai dacă ambele afirmații sunt adevărate.
Înlocuiți valorile numerelor din expresia:
1) (C (C2) ¬(C+1, C ≥ 44.
3) ¬(C+1, C ≥ 17.
Din punctele 2) și 1) rezultă că C
Raspuns: 44
¬(A = B) ∧ ((B A)) ∧ ((A 2C))
Cu ce este A egal dacă C = 8 și B = 18?.
Explicaţie.
„ȘI” logic este adevărat dacă și numai dacă ambele afirmații sunt adevărate.
1) ¬(A \u003d B) \u003d 1, adică A ≠ 18 \u003d 1.
2) ((B A)) Aplicați transformarea implicației: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Aplicați transformarea implicației: (A > 18) ∨ (A > 16) = 1
Din 2) și 3) rezultă că (18 > A) și (A > 16), deoarece în caz contrar apare contradicția A = 17.
Raspuns: 17
A, B și C sunt numere întregi pentru care afirmația este adevărată
¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
Cu ce este B egal dacă A = 45 și C = 18?
Explicaţie.
„ȘI” logic este adevărat numai atunci când toate afirmațiile sunt adevărate.
Poate fi distins diferite căi rezolvarea sistemelor de ecuații logice. Aceasta este o reducere la o singură ecuație, construcția unui tabel de adevăr și descompunere.
O sarcină: Rezolvați un sistem de ecuații logice:
Considera metoda de reducere la o ecuație . Această metodă implică transformarea ecuațiilor logice, astfel încât părțile lor din dreapta să fie egale cu valoarea de adevăr (adică 1). Pentru a face acest lucru, utilizați operația de negație logică. Apoi, dacă există operații logice complexe în ecuații, le înlocuim cu cele de bază: „ȘI”, „SAU”, „NU”. Următorul pas este să combinați ecuațiile într-una singură, echivalentă cu sistemul, folosind operația logică „ȘI”. După aceea, ar trebui să faceți transformări ale ecuației rezultate pe baza legile algebrei logicii și să obțineți solutie specifica sisteme.
Soluția 1: Aplicați inversarea ambelor părți ale primei ecuații:
Să reprezentăm implicația prin operațiile de bază „SAU”, „NU”:
Deoarece părțile stângi ale ecuațiilor sunt egale cu 1, le puteți combina folosind operația „ȘI” într-o singură ecuație care este echivalentă cu sistemul original:
Deschidem prima paranteză conform legii lui de Morgan și transformăm rezultatul:
Ecuația rezultată are o singură soluție: A=0, B=0 și C=1.
Următoarea cale este construirea tabelelor de adevăr . Deoarece valorile logice au doar două valori, puteți pur și simplu să parcurgeți toate opțiunile și să găsiți printre ele pe acelea pentru care sistemul de ecuații dat este satisfăcut. Adică construim unul tabel general adevărul pentru toate ecuațiile sistemului și găsiți linia cu valorile dorite.
Soluția 2: Să facem un tabel de adevăr pentru sistem:
|
0 |
0 |
1 |
1 |
0 |
1 |
Bold este linia pentru care sunt îndeplinite condițiile problemei. Deci A=0, B=0 și C=1.
Cale descompunere . Ideea este de a fixa valoarea uneia dintre variabile (puneți-o egală cu 0 sau 1) și astfel simplificați ecuațiile. Apoi puteți fixa valoarea celei de-a doua variabile și așa mai departe.
Soluția 3: Fie A = 0, atunci:
Din prima ecuație obținem B = 0, iar din a doua - С=1. Soluție de sistem: A = 0, B = 0 și C = 1.
În UTILIZARE în informatică, este foarte adesea necesar să se determine numărul de soluții la un sistem de ecuații logice, fără a găsi soluțiile în sine, există și anumite metode pentru aceasta. Principala modalitate de a găsi numărul de soluții ale unui sistem de ecuații logice estemodificarea variabilelor. În primul rând, este necesar să se simplifice cât mai mult posibil fiecare dintre ecuații pe baza legilor algebrei logicii, apoi să se înlocuiască părțile complexe ale ecuațiilor cu noi variabile și să se determine numărul de soluții ale noului sistem. Apoi reveniți la înlocuire și determinați numărul de soluții pentru aceasta.
O sarcină: Câte soluții are ecuația (A → B ) + (C → D ) = 1? Unde A, B, C, D sunt variabile booleene.
Soluţie: Să introducem noi variabile: X = A → B și Y = C → D . Ținând cont de nou ecuație variabilă se va scrie ca: X + Y = 1.
Disjuncția este adevărată în trei cazuri: (0;1), (1;0) și (1;1), în timp ce X și Y sunt o implicație, adică este adevărată în trei cazuri și falsă într-unul. Prin urmare, cazul (0;1) va corespunde la trei combinații posibile de parametri. Cazul (1;1) - va corespunde la nouă combinații posibile ale parametrilor ecuației inițiale. Deci, în total solutii posibile dată ecuația 3+9=15.
Următorul mod de a determina numărul de soluții ale unui sistem de ecuații logice este − arbore binar. Considera aceasta metoda De exemplu.
O sarcină: Câte soluții diferite are sistemul de ecuații logice:
Sistemul de ecuații dat este echivalent cu ecuația:
(X 1 → X 2 )*(X 2 → X 3 )*…*(x m -1 → x m) = 1.
Să ne prefacem că X 1 este adevărat, atunci din prima ecuație obținem asta X 2 de asemenea adevărat, din a doua - X 3 =1 și așa mai departe până când x m= 1. Aceasta înseamnă că mulțimea (1; 1; …; 1) de m unități este soluția sistemului. Lasă acum X 1 =0, apoi din prima ecuație pe care o avem X 2 =0 sau X 2 =1.
Când X 2 adevărat, obținem că și celelalte variabile sunt adevărate, adică mulțimea (0; 1; ...; 1) este soluția sistemului. La X 2 =0 obținem asta X 3 =0 sau X 3 = și așa mai departe. Continuând la ultima variabilă, obținem că soluțiile ecuației sunt următoarele seturi de variabile (m + 1 soluție, fiecare soluție are m valori de variabile):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Această abordare este bine ilustrată prin construirea unui arbore binar. Numărul de soluții posibile este numărul de ramuri diferite ale arborelui construit. Este ușor de observat că este egal cu m + 1.
|
Lemn |
Numărul de decizii |
|
|
x 1 |
|
|
|
x2 |
||
|
x 3 |
||
|
… |
În caz de dificultăţi în raţionament niyah și construcția dehohote de soluții, puteți căuta o soluție cu folosind tabele de adevăr, pentru una sau două ecuații.
Rescriem sistemul de ecuații sub forma:
Și să facem separat un tabel de adevăr pentru o ecuație:
|
x 1 |
x2 |
(x 1 → x 2) |
Să facem un tabel de adevăr pentru două ecuații:
|
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Modalități de rezolvare a sistemelor de ecuații logice
Kirgizova E.V., Nemkova A.E.
Institutul Pedagogic Lesosibirsk -
filiala a Universității Federale Siberiei, Rusia
Capacitatea de a gândi în mod consecvent, a argumenta în mod concludent, a construi ipoteze, a respinge concluzii negative, nu vine de la sine, această abilitate este dezvoltată de știința logicii. Logica este o știință care studiază metodele de stabilire a adevărului sau falsității unor afirmații pe baza adevărului sau falsității altor enunțuri.
Stăpânirea elementelor de bază ale acestei științe este imposibilă fără rezolvarea problemelor logice. Verificarea formării deprinderilor de a-și aplica cunoștințele într-o situație nouă se realizează prin trecere. În special, este capacitatea de a rezolva sarcini logice. Sarcinile B15 din examen sunt sarcini de complexitate crescută, deoarece conțin sisteme de ecuații logice. Există diferite moduri de a rezolva sisteme de ecuații logice. Aceasta este reducerea la o ecuație, construirea unui tabel de adevăr, descompunerea, soluția secvențială a ecuațiilor etc.
O sarcină:Rezolvați un sistem de ecuații logice:
Considera metoda de reducere la o ecuație . Această metodă implică transformarea ecuațiilor logice, astfel încât părțile lor din dreapta să fie egale cu valoarea de adevăr (adică 1). Pentru a face acest lucru, utilizați operația de negație logică. Apoi, dacă există operații logice complexe în ecuații, le înlocuim cu cele de bază: „ȘI”, „SAU”, „NU”. Următorul pas este să combinați ecuațiile într-una singură, echivalentă cu sistemul, folosind operația logică „ȘI”. După aceea, ar trebui să faceți transformări ale ecuației rezultate pe baza legile algebrei logicii și să obțineți o soluție specifică a sistemului.
Soluția 1:Aplicați inversarea ambelor părți ale primei ecuații:
Să reprezentăm implicația prin operațiile de bază „SAU”, „NU”:
Deoarece părțile stângi ale ecuațiilor sunt egale cu 1, le puteți combina folosind operația „ȘI” într-o singură ecuație care este echivalentă cu sistemul original:
Deschidem prima paranteză conform legii lui de Morgan și transformăm rezultatul:
Ecuația rezultată are o soluție: A= 0, B=0 şi C=1.
Următoarea cale este construirea tabelelor de adevăr . Deoarece valorile logice au doar două valori, puteți pur și simplu să parcurgeți toate opțiunile și să găsiți printre ele pe acelea pentru care sistemul de ecuații dat este satisfăcut. Adică, construim un tabel de adevăr comun pentru toate ecuațiile sistemului și găsim o linie cu valorile dorite.
Soluția 2:Să facem un tabel de adevăr pentru sistem:
|
0 |
0 |
1 |
1 |
0 |
1 |
Bold este linia pentru care sunt îndeplinite condițiile problemei. Deci A =0 , B =0 și C =1 .
Cale descompunere . Ideea este de a fixa valoarea uneia dintre variabile (puneți-o egală cu 0 sau 1) și astfel simplificați ecuațiile. Apoi puteți fixa valoarea celei de-a doua variabile și așa mai departe.
Soluția 3: Lăsa A = 0, atunci:
Din prima ecuație obținem B =0, iar din a doua - С=1. Soluție de sistem: A = 0 , B = 0 și C = 1 .
Puteți folosi și metoda rezolvarea secvențială a ecuațiilor , adăugând o variabilă la setul luat în considerare la fiecare pas. Pentru a face acest lucru, este necesar să transformați ecuațiile în așa fel încât variabilele să fie introduse în ordine alfabetică. Apoi, construim un arbore de decizie, adăugându-i secvențial variabile.
Prima ecuație a sistemului depinde doar de A și B, iar a doua ecuație de A și C. Variabila A poate lua 2 valori 0 și 1:
Din prima ecuaţie rezultă că 
, deci când A = 0 avem B = 0 , iar pentru A = 1 avem B = 1 . Deci, prima ecuație are două soluții în raport cu variabilele A și B .
Tragem a doua ecuație, din care determinăm valorile lui C pentru fiecare opțiune. Pentru A =1, implicația nu poate fi falsă, adică a doua ramură a arborelui nu are soluție. La A= 0
obținem singura soluție C= 1
:
Astfel, am obținut soluția sistemului: A = 0 , B = 0 și C = 1 .
În UTILIZARE în informatică, este foarte adesea necesar să se determine numărul de soluții la un sistem de ecuații logice, fără a găsi soluțiile în sine, există și anumite metode pentru aceasta. Principala modalitate de a găsi numărul de soluții ale unui sistem de ecuații logice este modificarea variabilelor. În primul rând, este necesar să se simplifice cât mai mult posibil fiecare dintre ecuații pe baza legilor algebrei logicii, apoi să se înlocuiască părțile complexe ale ecuațiilor cu noi variabile și să se determine numărul de soluții ale noului sistem. Apoi reveniți la înlocuire și determinați numărul de soluții pentru aceasta.
O sarcină:Câte soluții are ecuația ( A → B ) + (C → D ) = 1? Unde A, B, C, D sunt variabile booleene.
Soluţie:Să introducem noi variabile: X = A → B și Y = C → D . Luând în considerare noile variabile, ecuația poate fi scrisă astfel: X + Y = 1.
Disjuncția este adevărată în trei cazuri: (0;1), (1;0) și (1;1), în timp ce X și Y este o implicație, adică este adevărată în trei cazuri și falsă într-unul. Prin urmare, cazul (0;1) va corespunde la trei combinații posibile de parametri. Cazul (1;1) - va corespunde la nouă combinații posibile ale parametrilor ecuației inițiale. Prin urmare, există 3+9=15 soluții posibile ale acestei ecuații.
Următorul mod de a determina numărul de soluții ale unui sistem de ecuații logice este − arbore binar. Să luăm în considerare această metodă cu un exemplu.
O sarcină:Câte soluții diferite are sistemul de ecuații logice:
Sistemul de ecuații dat este echivalent cu ecuația:
( X 1 → X 2 )*( X 2 → X 3 )*…*( x m -1 → x m) = 1.
Să ne prefacem căX 1 este adevărat, atunci din prima ecuație obținem astaX 2 de asemenea adevărat, din a doua -X 3 =1 și așa mai departe până când x m= 1. De aici și mulțimea (1; 1; …; 1) din m unități este soluția sistemului. Lasă acumX 1 =0, apoi din prima ecuație pe care o avemX 2 =0 sau X 2 =1.
Când X 2 adevărat, obținem că și celelalte variabile sunt adevărate, adică mulțimea (0; 1; ...; 1) este soluția sistemului. LaX 2 =0 obținem asta X 3 =0 sau X 3 = și așa mai departe. Continuând la ultima variabilă, constatăm că soluțiile ecuației sunt următoarele seturi de variabile ( m +1 soluție, în fiecare soluție m valori variabile):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Această abordare este bine ilustrată prin construirea unui arbore binar. Numărul de soluții posibile este numărul de ramuri diferite ale arborelui construit. Este ușor de văzut că este m+1.
|
Variabile |
Lemn |
Numărul de decizii |
|
x 1 |
|
|
|
x2 |
||
|
x 3 |
||
În caz de dificultăți în raționament și construirea unui arbore de decizie, puteți căuta o soluție folosind tabele de adevăr, pentru una sau două ecuații.
Rescriem sistemul de ecuații sub forma:
Și să facem separat un tabel de adevăr pentru o ecuație:
|
x 1 |
x2 |
(x 1 → x 2) |
Să facem un tabel de adevăr pentru două ecuații:
|
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Apoi, puteți vedea că o ecuație este adevărată în următoarele trei cazuri: (0; 0), (0; 1), (1; 1). Sistemul a două ecuații este adevărat în patru cazuri (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). În acest caz, este imediat clar că există o soluție constând doar din zerouri și mai mult m soluții în care se adaugă o unitate, începând de la ultima poziție până la ocuparea tuturor locurilor posibile. Se poate presupune că soluția generală va avea aceeași formă, dar pentru ca o astfel de abordare să devină o soluție este necesară dovada că presupunerea este adevărată.
Rezumând toate cele de mai sus, aș dori să atrag atenția asupra faptului că nu toate metodele luate în considerare sunt universale. La rezolvarea fiecărui sistem de ecuații logice, trebuie luate în considerare caracteristicile acestuia, pe baza cărora ar trebui să fie aleasă metoda de soluție.
Literatură:
1. Sarcini logice / O.B. Bogomolov - ed. a II-a. – M.: BINOM. Laboratorul de cunoștințe, 2006. - 271 p.: ill.
2. Polyakov K.Yu. Sisteme de ecuații logice / Ziar educațional și metodic pentru profesorii de informatică: Informatică Nr. 14, 2011
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. Ecuațiile au fost folosite de om din cele mai vechi timpuri și de atunci utilizarea lor a crescut. În matematică, există anumite sarcini care sunt dedicate logicii propozițiilor. 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 transformare a expresiilor logice. În plus, trebuie să cunoașteți următoarele proprietăți ale operațiilor logice: conjuncții, disjuncții, inversiuni, implicații și echivalențe.
Orice funcție logică din \ variabile - \ poate fi specificată printr-un tabel de adevăr.
Să rezolvăm câteva 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. Apoi, luați în considerare fiecare dintre valorile de mai sus \u200b\u200și vedeți ce \[X2.\] poate fi in acest caz
După cum se vede din tabel, nostru ecuație logică are 11 soluții.
Unde pot rezolva o ecuație logică online?
Puteți rezolva ecuația pe site-ul nostru https: // site-ul. Gratuit rezolvator online vă va permite să rezolvați o ecuație online de orice complexitate în câteva secunde. Tot ce trebuie să faci este să introduci datele în solutor. De asemenea, puteți viziona instrucțiunile video și puteți afla cum să rezolvați ecuația pe site-ul nostru. Și dacă 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.
