Metode de rezolvare a ecuațiilor logice. Logica în informatică este soluția ecuațiilor. fundamentele logice ale PC-ului. Unde pot rezolva o ecuație logică online

Bugetul municipal instituție educațională

"In medie şcoală cuprinzătoare nr. 18"

districtul urban al orașului Salavat al Republicii Bashkortostan

Sisteme de ecuații logice

în sarcinile examenului de informatică

Secțiunea „Fundamentele algebrei logicii” în USE sarcini este considerată una dintre cele mai dificile și prost rezolvate. Procentul mediu de finalizare a sarcinilor pe acest subiect este cel mai mic și este de 43,2.

Sectiunea de curs	Procentul mediu de finalizare pe grupuri de sarcini
Codarea informațiilor și măsurarea cantității acestora
modelarea informaţiei
Sisteme numerice
Fundamentele algebrei logicii
Algoritmizare si programare
Fundamentele tehnologiilor informației și comunicațiilor

Bazat pe specificația KIM 2018, acest bloc include patru sarcini diferite niveluri dificultăți.

№ sarcini	Verificat elemente de conținut	Nivel de dificultate al sarcinii
	Abilitatea de a construi tabele de adevăr și circuite logice
	Abilitatea de a căuta informații pe Internet
	Cunoașterea conceptelor de bază și a legilor logica matematica
	Abilitatea de a construi și transforma expresii logice

Sarcina 23 este un nivel ridicat de dificultate, prin urmare are cel mai mic procent de finalizare. Dintre absolvenții instruiți (81-100 puncte) 49,8% au finalizat-o, cei pregătiți în medie (61-80 puncte) fac față cu 13,7%, restul de studenți nu realizează această sarcină.

Succesul rezolvării unui sistem de ecuații logice depinde de cunoașterea legilor logicii și de aplicarea precisă a metodelor de rezolvare a sistemului.

Luați în considerare soluția unui sistem de ecuații logice prin metoda cartografierii.

(23.154 Polyakov K.Yu.) Câte soluții diferite are sistemul de ecuații?

((X1  y1 )  (X2  y2 ))  (X1  X2 )  (y1  y2 ) =1

((X2  y2 )  (X3  y3 ))  (X2  X3 )  (y2  y3 ) =1

((X7  y7 )  (X8  y8 ))  (X7  X8 )  (y7  y8 ) =1

Unde X1 , X2 ,…, X8, la1 ,y2 ,…,y8 - Variabile booleene? 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.

Soluţie. Toate ecuațiile incluse în sistem sunt de același tip și patru variabile sunt incluse în fiecare ecuație. Cunoscând x1 și y1, putem găsi toate valorile posibile ale x2 și y2 care satisfac prima ecuație. Argumentând în mod similar, din x2 și y2 cunoscute putem găsi x3, y3 care satisface a doua ecuație. Adică cunoscând perechea (x1 , y1) și determinând valoarea perechii (x2 , y2) , vom găsi perechea (x3 , y3 ), care la rândul ei va duce la perechea (x4 , y4 ) și așadar pe.

Să găsim toate soluțiile primei ecuații. Acest lucru se poate face în două moduri: pentru a construi un tabel de adevăr, prin raționament și aplicarea legilor logicii.

Tabelul de adevăr:

				x 1  y 1	x2  y2	(x 1  y1)  (x 2  y2)	(x 1  x2)	(y 1  y2)	(x 1  x2)  (y 1  y2)

Construirea unui tabel de adevăr este laborioasă și ineficientă în timp, așa că folosim a doua metodă - raționamentul logic. Produsul este 1 dacă și numai dacă fiecare factor este 1.

(X1  y1 )  (X2  y2 ))=1

(X1  X2 ) =1

(y1  y2 ) =1

Luați în considerare prima ecuație. Următorul este egal cu 1, când 0 0, 0 1, 1 1, atunci (x1 y1)=0 la (01), (10), atunci perechea (X2  y2 ) poate fi oricare (00), (01), (10), (11), iar pentru (x1 y1)=1, adică (00) și (11) perechea (x2 y2)=1 ia aceleași valori (00) și (11). Excludem din această soluție acele perechi pentru care a doua și a treia ecuație sunt false, adică x1=1, x2=0, y1=1, y2=0.

(X1 , y1 )	(X2 , y2 )

Numărul total de perechi 1+1+1+22= 25

2) (23,160 Polyakov K.Yu.) Câte soluții diferite are un sistem de ecuații logice

(X 1  (X 2  y 2 ))  (y 1  y 2 ) = 1

(X 2  (X 3  y 3 ))  (y 2  y 3 ) = 1

...

( X 6  ( X 7  y 7 ))  ( y 6  y 7 ) = 1

X 7  y 7 = 1

Soluţie. 1) Ecuațiile sunt de același tip, așa că prin metoda raționamentului vom găsi toate perechile posibile (x1,y1), (x2,y2) ale primei ecuații.

(X1  (X2  y2 ))=1

(y1  y2 ) = 1

Soluția celei de-a doua ecuații sunt perechile (00), (01), (11).

Să găsim soluții la prima ecuație. Dacă x1=0, atunci x2 , y2 - oricare, dacă x1=1, atunci x2 , y2 ia valoarea (11).

Să facem conexiuni între perechi (x1 , y1) și (x2 , y2).

(X1 , y1 )	(X2 , y2 )

Să facem un tabel pentru a calcula numărul de perechi la fiecare etapă.

							0

Ținând cont de soluțiile ultimei ecuații X 7  y 7 = 1, eliminăm perechea (10). Găsim numărul total soluții 1+7+0+34=42

3)(23.180) Câte soluții diferite are sistemul de ecuații logice

(X1  X2 )  (X3  X4 ) = 1

(X3  X4 )  (X5  X6 ) = 1

(X5  X6 )  (X7  X8 ) = 1

(X7  X8 )  (X9  X10 ) = 1

X1  X3  X5  X7  X9 = 1

Soluţie. 1) Ecuațiile sunt de același tip, așa că prin metoda raționamentului vom găsi toate perechile posibile (x1,x2), (x3,x4) ale primei ecuații.

(X1  X2 )  (X3  X4 ) = 1

Excludem din soluție perechile care dau 0 (1 0) în cele ce urmează, acestea sunt perechile (01, 00, 11) și (10).

Compuneți legături între perechi (x1,x2), (x3,x4)

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, după simplificarea fiecărei ecuații.

1. Metoda de modificare a variabilelor.

Introducerea de noi variabile face posibilă simplificarea sistemului de ecuații prin reducerea numărului de necunoscute.Noile variabile trebuie să fie independente unele de altele. După rezolvarea sistemului simplificat, este necesar să revenim la variabilele originale.

Luați în considerare aplicarea acestei metode pe 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: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Atenție! Fiecare dintre variabilele lor x1, x2, …, x10 trebuie inclusă doar într-una dintre noile variabilele 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 al sistemului rezultat:

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

		X1 ≡ X2

Din același tabel se poate observa că ecuația A \u003d 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 pentru o ramură, 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.

Complexitatea rezolvării sistemelor de ecuații logice constă în volumul arborelui decizional complet. Metoda de raționament vă permite să nu construiți întregul copac, dar în același timp să înțelegeți câte ramuri va avea. Să luăm în considerare această metodă pe exemple concrete.

Exemplul 1 Câte seturi diferite de valori ale variabilelor booleene x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care îndeplinesc toate următoarele condiții?

(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 sub care sistemul de egalități dat 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 printr-o a treia condiție. Să construim un arbore de decizie pentru prima și a doua ecuație.

Pentru a reprezenta arborele de decizie al sistemului din prima și a doua ecuație, este necesar să se continue fiecare ramură a primului arbore 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. Notați pe primul copac numărul de ramuri ale copacului"la" , care satisfac a treia ecuație:

Să lămurim: pentru îndeplinirea celei de-a treia condiții la x1=0 trebuie să existe y1=1, adică toate ramurile arborelui"X" , unde x1=0 poate fi continuat cu o singură ramură din arbore"la" . Și doar pentru o ramură a copacului"X" (dreapta) se potrivesc tuturor ramurilor copacului"la". Astfel, arborele complet al întregului sistem conține 11 ramuri. Fiecare ramură reprezintă o soluție a sistemului original de ecuații. Deci î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 booleene? 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 al părții din prima ecuație:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)

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

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, i.e. x1 nu ar trebui să fie același cu x10. Pentru ca prima ecuație să fie egală cu 1, egalitatea trebuie să fie valabilă(X1 ≡ X2)=1, adică x1 trebuie să se potrivească cu x2.

Să construim un arbore de decizie 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 este același cu x3); la x10=0 și la x2=1 paranteză(X2 ≡ X10)=0, deci paranteză (X2 ≡ X3) trebuie să fie egal cu 1 (adică x2 este același cu x3):

Argumentâ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 booleene x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 există care îndeplinesc toate următoarele condiții?

(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 decizie al primei ecuații:

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

• Când x1=0 : a doua și a treia paranteză vor fi 0; pentru ca prima paranteză să fie egală cu 1, trebuie să y1=1 , z1=1 (adică în acest caz - 1 soluție)
• Cu x1=1 : prima paranteză va fi 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 pentru y1=1 și z1=0 (adică în acest caz - 2 soluții).

La fel pentru restul ecuațiilor. Observați numărul de soluții obținute pentru fiecare nod al arborelui:

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

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

2 ramură: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 soluții

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

4 ramură: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 soluții

5 ramură: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 soluții

Să adunăm numerele obținute: în total 31 de soluții.

Raspuns: 31.

3. Creșterea regulată a numărului de rădăcini

În unele sisteme, numărul de rădăcini ale următoarei ecuații depinde de numărul de rădăcini ale ecuației anterioare.

Exemplul 1 Câte seturi diferite de valori ale variabilelor booleene x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 există care îndeplinesc toate următoarele condiții?

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

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

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

Simplifica 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 numerelor Fibonacci.

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

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 de stat unificat în informatică. Se știe că această sarcină este una dintre cele mai dificile dintre sarcinile examenului. Prezentarea poate fi utilă atunci când se desfășoară lecții pe tema „Logică” în clase de specialitate, precum și în pregătirea pentru promovarea examenului.

Descarca:

Previzualizare:

Pentru a utiliza previzualizarea prezentărilor, creați un cont Google (cont) și conectați-vă: https://accounts.google.com

Subtitrările diapozitivelor:

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

Sarcina B15 este una dintre cele mai dificile la examenul de informatică !!! Se verifică abilitățile: de a transforma expresii 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, pentru că nu există reguli formale cu privire la modul de a face acest lucru, este necesară presupunerea.

Ce să nu te faci fără!

Ce să nu te faci fără!

Convenții conjuncție: A /\ B , A  B , AB , А &B, A și B disjuncție: A \ / B , A + B , A | B , A sau B negație:  A , A, nu A echivalent: A  B, A  B, A  B XOR: A  B , A xor B

Metoda de substituție a variabilelor Câte seturi diferite de valori ale variabilelor booleene x1, x2, ..., x9, x10 există care îndeplinesc toate următoarele condiții: ((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 sub care sistemul dat de egalităţi este satisfăcut. 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 . Folosim formula pentru a exprima operația XOR în termeni de 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 .la. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), atunci fiecare valoare 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 sunt perechile (0,0) și (1,1).

Pasul 3. Numărarea numărului de soluții. Fiecare t are 2 soluții, numărul lui t este 5. Astfel pentru variabilele t există 2 5 = 32 de soluții. Dar fiecărui t îi corespunde o pereche de soluții x, adică. sistemul original are 2*32 = 64 solutii. Raspuns: 64

Metoda de eliminare a soluției parțiale Câte seturi diferite de valori ale variabilelor logice x1, x2, …, x5, y1,y2,…, y5 există care îndeplinesc toate următoarele condiții: (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, sub care acest sistem de egalități este satisfăcut. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluţie. Pasul 1. Rezolvarea secvenţială a ecuaţiilor 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 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. Scriem asta sub forma unui tabel:

Pasul 1. Rezolvarea secvenţială a ecuaţiilor Т.о. Se primesc 6 seturi de soluții pentru х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Argumentând în mod similar, concluzionăm că pentru y1, y2, y3, y4, y5 există același set de soluții. pentru că aceste ecuații sunt independente, adică nu există variabile comune în ele, 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 „xes” și „da”. Luați în considerare a treia ecuație: y5→ x5 =1 Perechile sunt soluția: 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 se potrivesc. există 5 astfel de perechi.Numărul de soluții ale sistemului: 36-5= 31. Raspuns: 31 A fost nevoie de combinatorie!!!

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 numărul de astfel de seturi.

Soluția Pasul 1. Analiza condiției În partea stângă a ecuației, operațiile de implicare sunt scrise secvențial, prioritatea este aceeași. Rescrie: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Fiecare variabilă următoare nu depinde de cea anterioară, ci de rezultatul implicației anterioare!

Pasul 2. Dezvăluirea tiparului Luați î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 obținem 2, iar din 1 am primit un 0 și unul 1. Doar unul 0 și trei 1, acesta este rezultatul primei operații.

Pasul 2. Dezvăluind un 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 două 0uri - două 1uri, din fiecare 1 (sunt 3) câte unul 0 și 1 (3 + 3)

Pasul 3. Derivarea formulei puteți face 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ă conform celei precedente: : 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 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.

Soluție Rețineți că J → K = ¬ J  K Introducem o modificare de variabile: J → K=A, M  N  L =B 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 A  B , atunci Cu M=J=0 obținem 1 + K=0. Nu există soluții. Cu M=0, J=1 obținem 0 + K=0, K=0, iar N și L - oricare, 4 soluții: ¬ J  K = M  N  LKNL 0 0 0 0 0 1 0 1 0 0 1 unul

Soluția 10. Cu 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 KNL 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ție nouă // 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ă].

Rezolvarea sistemelor de ecuații logice prin schimbarea variabilelor

Metoda schimbării variabilelor este utilizată dacă unele variabile sunt incluse în ecuații doar sub forma unei expresii specifice și nimic altceva. Apoi această expresie poate fi notată printr-o nouă variabilă.

Exemplul 1

Câte seturi diferite de valori ale variabilelor logice x1, x2, x3, x4, x5, x6, x7, x8 există care îndeplinesc toate următoarele condiții?

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

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

Răspunsul nu trebuie să enumere toate seturile diferite de valori ale variabilelor x1, x2, x3, x4, x5, x6, x7, x8, sub care acest sistem de egalități este satisfăcut. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluţie:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Atunci sistemul poate fi scris ca o singură ecuație:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Conjuncția este 1 (adevărată) când fiecare operand evaluează la 1. Adică, fiecare dintre implicații trebuie să fie adevărată, iar acest lucru este valabil pentru toate valorile, cu excepția (1 → 0). Acestea. în tabelul de valori ale variabilelor y1, y2, y3, y4, unitatea nu trebuie să fie la stânga lui zero:

Acestea. sunt îndeplinite condițiile pentru 5 seturi y1-y4.

pentru că y1 = x1 → x2, atunci valoarea y1 = 0 se realizează pe o singură mulțime x1, x2: (1, 0), iar valoarea y1 = 1 se realizează pe trei mulțimi x1, x2: (0,0) , ( 0,1), (1,1). În mod similar pentru y2, y3, y4.

Deoarece fiecare set (x1,x2) pentru variabila y1 este combinată cu fiecare set (x3,x4) pentru variabila y2 și așa mai departe, numărul de seturi de variabile x este înmulțit:

				Numărul de seturi pe x1...x8

Să adăugăm numărul de seturi: 1 + 3 + 9 + 27 + 81 = 121.

Răspuns: 121

Exemplul 2

Câte seturi diferite de valori ale variabilelor booleene x1, x2, ... x9, y1, y2, ... y9 există care îndeplinesc toate următoarele condiții?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

In raspuns nu este nevoie enumerați toate seturile diferite de valori ale variabilelor x1, x2, ... x9, y1, y2, ... y9, sub care sistemul de egalități dat este satisfăcut. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluţie:

Să facem o schimbare de variabile:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Sistemul poate fi scris ca o singură ecuație:

(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)

Echivalența este adevărată numai dacă ambii operanzi sunt egali. Soluțiile acestei ecuații vor fi două seturi:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

pentru că zi = (xi ≡ yi), atunci valoarea zi = 0 corespunde la două mulțimi (xi,yi): (0,1) și (1,0), iar valoarea zi = 1 corespunde la două mulțimi (xi,yi). ): (0,0) și (1,1).

Atunci primul set z1, z2,…, z9 corespunde cu 2 9 seturi (x1,y1), (x2,y2),…, (x9,y9).

Același număr corespunde celui de-al doilea set z1, z2,…, z9. Apoi există 2 9 +2 9 = 1024 de seturi în total.

Răspuns: 1024

Rezolvarea sistemelor de ecuații logice prin definirea vizuală a recursiunii.

Această metodă este utilizată dacă sistemul de ecuații este suficient de simplu și ordinea creșterii numărului de mulțimi la adăugarea variabilelor este evidentă.

Exemplul 3

Câte soluții diferite are sistemul de ecuații

¬x9 ∨ x10 = 1,

unde x1, x2, ... x10 sunt variabile booleene?

Răspunsul nu trebuie să enumere toate seturile diferite de valori x1, x2, ... x10 pentru care sistemul de egalități dat este valabil. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluţie:

Să rezolvăm prima ecuație. O disjuncție este egală cu 1 dacă cel puțin unul dintre operanzii săi este egal cu 1. Adică, solutiile sunt seturile:

Pentru x1=0 există două valori x2 (0 și 1), iar pentru x1=1 există o singură valoare x2 (1), astfel încât mulțimea (x1,x2) este soluția ecuației. Doar 3 seturi.

Să adăugăm variabila x3 și să considerăm a doua ecuație. Este similar cu primul, ceea ce înseamnă că pentru x2=0 există două valori ale lui x3 (0 și 1), iar pentru x2=1 există o singură valoare a lui x3 (1), astfel încât mulțimea ( x2,x3) este o soluție a ecuației. Sunt 4 seturi in total.

Este ușor de observat că atunci când adăugați o altă variabilă, se adaugă un set. Acestea. formula recursivă pentru numărul de seturi pe variabile (i+1):

N i +1 = N i + 1. Atunci pentru zece variabile obținem 11 mulțimi.

Răspuns: 11

Rezolvarea sistemelor de ecuații logice de diferite tipuri

Exemplul 4

Câte seturi diferite de valori ale variabilelor booleene x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 există care îndeplinesc toate următoarele condiții?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

In raspuns nu este nevoie enumerați toate seturile diferite de valori ale variabilelor x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , sub care sistemul de egalități dat este satisfăcut .

Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluţie:

Rețineți că cele trei ecuații ale sistemului sunt aceleași pe seturi independente diferite de variabile.

Luați în considerare prima ecuație. O conjuncție este adevărată (egale cu 1) numai dacă toți operanzii ei sunt adevărate (egale cu 1). Implicația este 1 pe toate seturile, cu excepția (1,0). Aceasta înseamnă că soluția primei ecuații va fi astfel de mulțimi x1, x2, x3, x4, în care 1 nu este la stânga lui 0 (5 seturi):

În mod similar, soluțiile celei de-a doua și a treia ecuații vor fi exact aceleași mulțimi de y1,…,y4 și z1,…,z4.

Acum să analizăm a patra ecuație a sistemului: x 4 ∧ y 4 ∧ z 4 = 0. Soluția vor fi toate mulțimile x4, y4, z4 în care cel puțin una dintre variabile este egală cu 0.

Acestea. pentru x4 = 0, toate mulțimile posibile (y4, z4) sunt potrivite, iar pentru x4 = 1, se potrivesc mulțimile (y4, z4) care conțin cel puțin un zero: (0, 0), (0,1) , ( 1, 0).

				Numărul de seturi

Numărul total de seturi este 25 + 4*9 = 25 + 36 = 61.

Răspuns: 61

Rezolvarea sistemelor de ecuații logice prin construirea de formule recurente

Pentru rezolvare se folosește metoda de construire a formulelor recurente sisteme complexe, în care ordinea creșterii numărului de seturi nu este evidentă, iar construirea unui arbore este imposibilă din cauza volumelor.

Exemplul 5

Câte seturi diferite de valori ale variabilelor booleene x1, x2, ... x7, y1, y2, ... y7 există care îndeplinesc toate următoarele condiții?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

Răspunsul nu trebuie să enumere toate seturile diferite de valori ale variabilelor x1, x2, ..., x7, y1, y2, ..., y7, sub care este valabil sistemul dat de egalități. Ca răspuns, trebuie să indicați numărul de astfel de seturi.

Soluţie:

Rețineți că primele șase ecuații ale sistemului sunt aceleași și diferă doar în setul de variabile. Luați în considerare prima ecuație. Soluția sa va fi următoarele seturi de variabile:

Denota:

numărul de mulțimi (0,0) pe variabile (x1,y1) până la A 1 ,

numărul de mulțimi (0,1) pe variabile (x1,y1) până la B 1 ,

numărul de seturi (1,0) pe variabile (x1,y1) prin C 1 ,

numărul de seturi (1,1) pe variabile (x1,y1) prin D 1 .

numărul de mulțimi (0,0) pe variabile (x2,y2) până la A 2 ,

numărul de seturi (0,1) pe variabile (x2,y2) prin B 2 ,

numărul de seturi (1,0) pe variabile (x2,y2) prin C 2 ,

numărul de mulțimi (1,1) pe variabile (x2,y2) prin D 2 .

Din arborele de decizie, vedem asta

A1 =0, B1 =1, C1 =1, D1 =1.

Rețineți că tuplul (0,0) pe variabilele (x2,y2) se obține din tuplurile (0,1), (1,0) și (1,1) pe variabilele (x1,y1). Acestea. A 2 \u003d B 1 + C 1 + D 1.

Mulțimea (0,1) pe variabilele (x2,y2) se obține din mulțimile (0,1), (1,0) și (1,1) pe variabilele (x1,y1). Acestea. B 2 \u003d B 1 + C 1 + D 1.

Argumentând în mod similar, observăm că C 2 \u003d B 1 + C 1 + D 1. D2 = D1.

Astfel, obținem formule recursive:

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

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

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

Să facem o masă

seturi	Simbol.	Formulă	Numărul de seturi
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	Ai	Ai+1 =Bi +Ci +Di	0	3	7	15	31	63	127
(0,1)	B i	B i+1 = B i + C i + D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 = B i + C i + D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Ultima ecuație (x7 ∨ y7) = 1 este satisfăcută de toate mulțimile cu excepția celor în care x7=0 și y7=0. În tabelul nostru, numărul de astfel de seturi este A 7 .

Atunci numărul total de seturi este B 7 + C 7 + D 7 = 127+127+1 = 255

Răspuns: 255

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

Lecția numărul 3. Logici. Funcții logice. Rezolvarea ecuațiilor

Un număr mare de sarcini USE sunt dedicate logicii propozițiilor. 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 a conjuncției:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Legea distributivă privind disjuncția și conjuncția:
   a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negație negativă:
   ¬(¬a) ≡ a
4. Consecvență:
   a ^ ¬a ≡ fals
5. Al treilea exclusiv:
   a ˅ ¬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. Schimbarea 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 definită printr-un tabel de adevăr. Un astfel de tabel conține 2 n seturi de variabile, pentru fiecare dintre acestea fiind specificată valoarea funcției de pe acest set. Această metodă este bună atunci când numărul de variabile este relativ mic. Chiar și pentru n > 5, reprezentarea devine slab vizibilă.

O altă modalitate este de a defini funcția printr-o formulă, folosind funcții destul de simple cunoscute. Sistemul 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 ale modului în care implicația și identitatea sunt exprimate prin negație, conjuncție și disjuncție.

De fapt, sistemul a două funcții este de asemenea complet - negație și conjuncție sau negație și disjuncție. Reprezentările decurg din legile lui De Morgan care permit exprimarea unei conjuncții prin negație și disjuncție și, în consecință, exprimarea unei disjuncții 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 lui Pierce și lovitura lui 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 sarcinile examenului, alături de aceste funcții, există adesea o implicație.

Luați în considerare câteva sarcini simple asociate cu funcții logice.

Sarcina 15:

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

x1	x2	x3	x4	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)

Caracteristica numărul 3.

Pentru a rezolva problema, trebuie să cunoașteți tabelele de adevăr ale funcțiilor de bază și să aveți în vedere prioritățile operațiunilor. Permiteți-mi să vă reamintesc că conjuncția (înmulțirea logică) are o prioritate mai mare și se realizează înaintea disjuncției (adunarea logică). La calcul, este ușor de observat că funcțiile cu numerele 1 și 2 de pe al treilea set au valoarea 1 și din acest motiv nu corespund fragmentului.

Sarcina 16:

Care dintre următoarele numere îndeplinește condiția:

(cifrele, începând cu cifra cea mai semnificativă, merg în ordine descrescătoare) → (număr - par) ˄ (cifra cea mai mică - par) ˄ (cifra cea mai 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 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 minore și majore ale numărului. Primul termen al conjuncției este și el adevărat, deoarece o implicație este adevărată dacă premisa ei este falsă, ceea ce este cazul aici.

Problema 17: Doi martori au depus mărturie după cum urmează:

Primul martor: Dacă A este vinovat, atunci B este cu siguranță 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 exact cine.

Ce concluzii despre vinovăția lui A, B și C pot fi trase din probe?

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

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

Primul lucru de făcut este să oficializați declarațiile. Să introducem trei variabile booleene, A, B și C, fiecare dintre acestea fiind 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))

Se presupune că mărturiile ambilor martori sunt adevărate și reprezintă conjuncția formulelor corespunzătoare.

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

A	B	C	F1	F2	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.

De asemenea, din analiza acestui tabel 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 variante diferite care corespund mărturiei sale. Împreună, mărturiile ambilor martori dau un răspuns fără echivoc 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ă este:

F(x 1, x 2, ... x n) \u003d C,

Constanta C are valoarea 1 sau 0.

O ecuație logică poate avea de la 0 la 2n soluții diferite. Dacă C este egal cu 1, atunci soluțiile sunt toate acele seturi de variabile din tabelul de adevăr pe care funcția F ia valoarea adevărată (1). Mulțimile rămase sunt soluții ale ecuației pentru C egale cu zero. Putem considera întotdeauna doar 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, puteți merge la ecuația echivalentă:

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

Luați în considerare un sistem de k ecuații logice:

F 1 (x 1, x 2, ... x n) \u003d 1

F 2 (x 1, x 2, ... x n) \u003d 1

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

Soluția sistemului este un set de variabile pe care sunt satisfăcute toate ecuațiile sistemului. În ceea ce privește funcțiile logice, pentru a obține o soluție a sistemului de ecuații logice, ar trebui să gă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ă construiți un tabel de adevăr pentru funcția Ф, care vă permite să spuneți câte soluții are sistemul și care sunt mulțimile care dau soluții.

În unele sarcini ale examenului de stat unificat privind găsirea de soluții la un sistem de ecuații logice, numărul de variabile ajunge la valoarea de 10. Apoi construirea unui tabel de adevăr devine o sarcină aproape de nerezolvat. Rezolvarea problemei necesită o abordare diferită. Pentru un sistem arbitrar de ecuații, nu există mod general, care este diferit de enumerarea, care permite 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 enumerarea tuturor variantelor unui set de variabile, nu există o modalitate generală de rezolvare a problemei. 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.

Ce este un arbore de decizie binar și cum este construit, voi explica cu exemple de mai multe sarcini.

Problema 18

Câte seturi diferite de valori ale variabilelor booleene x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care satisfac un sistem 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 o conjuncție de funcții logice. Afirmația inversă este de asemenea adevărată - conjuncția condițiilor 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ă reprezentarea 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 ia valoarea adevărată. Deoarece ecuația definește o implicație, ramura pe care X 1 are valoarea 1 necesită ca X 2 să aibă valoarea 1 pe acea ramură. Ramura pe care X 1 are valoarea 0 generează două ramuri cu valorile X 2 egale 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ă se scrie setul corespunzător de valori variabile, care dă soluția 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ă să nivelul următor, dar nu apar ramuri noi. Singura ramură în care variabila X 2 are valoarea 0 va da o ramură în două ramuri, unde variabila X 3 va obține valorile 0 și 1. Astfel, fiecare adăugare a unei noi ecuații, având în vedere specificul ei, adaugă câte una. 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 variabilă X i poate fi combinată cu fiecare soluție variabilă Y j , numărul total de soluții este 36.

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 booleene x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 există care îndeplinesc toate următoarele condiții?

(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 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 mulțimi 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ța 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:

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

Rezolvare: La fel ca în problema 20, trecem de la implicații ciclice la identități prin rescrierea ecuației 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 ≡X4)) = 0

((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0

((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0

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

Raspuns: 64

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

Y1 = (X1 ≡ X2); Y 2 \u003d (X 3 ≡ X 4); Y3 = (X5 = X6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);

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ă fiecare valoare a variabilei Y corespunde la 2 valori ale variabilelor X, astfel încât fiecare soluție din variabilele Y generează 2 5 soluții în variabilele X. Două ramuri generează 2 * 2 5 soluții , deci numărul total de soluții este 64.

După cum puteți vedea, fiecare sarcină pentru rezolvarea unui sistem de ecuații necesită propria sa abordare. Recepție generală este de a efectua transformări echivalente pentru a simplifica ecuațiile. O tehnică comună este construirea arborilor de decizie. Abordarea aplicată seamănă parțial cu construcția 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 este deja în funcțiune stadiul inițial este posibil să se stabilească o regularitate în apariția unor noi ramuri la fiecare nivel următor, așa cum sa făcut, de exemplu, în problema 18.

În general, problemele pentru 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 computerului soluția problemei prin scrierea unui program adecvat pentru rezolvarea ecuațiilor și a sistemelor de ecuații.

Este ușor să scrii un astfel de program. Un astfel de program va face față cu ușurință tuturor sarcinilor oferite în cadrul examenului.

Destul de ciudat, dar sarcina de a găsi soluții la sistemele de ecuații logice este dificilă și pentru un computer, se dovedește că un computer are limitele sale. Computerul poate face față cu ușurință sarcinilor în care numărul de variabile este de 20-30, dar va începe să se gândească mult timp la sarcini mai mari. Ideea este că funcția 2 n care specifică numărul de mulțimi este un exponent care crește rapid cu n. Atât de rapid încât un computer personal normal nu poate face față unei sarcini cu 40 de variabile într-o zi.

Program 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ă poate fi folosit pentru a verifica corectitudinea propriei soluții la problemele testului USE. Un alt motiv este că un astfel de program este un exemplu excelent de problemă de programare care îndeplinește cerințele pentru problemele de categoria C în USE.

Ideea de a construi un program este simplă - se bazează pe o enumerare completă a tuturor seturilor posibile de valori variabile. Deoarece numărul de variabile n este cunoscut pentru o ecuație logică sau un sistem de ecuații dat, 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, este ușor de scris un program care, pentru un anumit set de variabile, calculează valoarea unei funcții logice corespunzătoare unei ecuații logice sau unui sistem de ecuații.

Într-un astfel de program, trebuie să construiți un ciclu după numărul de seturi, în corpul ciclului, după numărul setului, să formați setul în sine, să calculați valoarea funcției pe acest set și dacă această valoare este egal cu 1, atunci mulțimea oferă o soluție ecuației.

Singura dificultate care apare în implementarea programului este legată de sarcina de a forma setul de valori variabile în sine prin numărul setului. Frumusețea acestei sarcini este că această sarcină aparent dificilă, de fapt, se rezumă la o sarcină simplă care a apărut deja în mod repetat. Într-adevăr, este suficient să înțelegem că setul de valori ale variabilelor 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 ale variabilelor prin numărul setului se reduce la binecunoscuta problemă a conversiei unui număr într-un sistem binar.

Așa arată funcția 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 stabilită 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;

//Enumerarea completă după numărul de seturi

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

//Formarea următorului set — set,

//date de 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 despre ideea programului și comentariile din textul acestuia vor fi suficiente. Mă voi opri doar asupra explicației titlului funcției de mai sus. 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 din funcția fun. Ca rezultat, funcția SolveEquations returnează numărul de soluții ale funcției logice, adică numărul de mulțimi pe care funcția evaluează la adevărat.

Pentru școlari, se obișnuiește când pentru o anumită funcție F(x) parametrul de intrare x este o variabilă de tip aritmetic, șir sau boolean. Î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 definită după cum urmează:

delegat bool DF(bool vars);

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

În concluzie, voi oferi un program în care funcția SolveEquations este folosită pentru a rezolva mai multe sisteme de ecuații logice. Funcția SolveEquations face parte din următoarea clasă ProgramCommon:

clasa ProgramCommon

delegat bool DF(bool vars);

static void Main(string args)

Console.WriteLine("Funcție și soluții - " +

SolveEquations(FunAnd, 2));

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

Rezolvare ecuaț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:

x1	x2	x3	x4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Care dintre cele trei funcții corespunde acestui 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 în cazul în care 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 de luare a deciziilor.
5. X câștigă peste Y dacă patru aruncări de monede ies cu capul de trei ori. Definiți o funcție booleană care descrie profitul X.
6. Cuvintele dintr-o propoziție sunt numerotate începând de la unu. O propoziție este considerată bine formată dacă sunt îndeplinite următoarele reguli:
   1. Dacă un cuvânt cu număr par se termină cu o vocală, atunci următorul cuvânt, dacă există, trebuie să înceapă cu o vocală.
   2. Dacă un cuvânt cu numere 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 corecte:
   3. Mama a spălat-o pe Masha cu săpun.
   4. Liderul 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 sarcini:

1. Funcțiile b și c sunt echivalente.
2. Fragmentul corespunde funcției b.
3. Fie ca variabila booleană P să ia valoarea 1 atunci când președintele juriului votează „pentru” decizia. Variabilele M 1 și M 2 reprezintă opinia membrilor juriului. Funcția logică care specifică adoptarea unei decizii pozitive poate fi scrisă astfel:
   P ˄ (M 1 ˅ M 2)
4. Fie ca variabila booleană P i să ia valoarea 1 atunci când aruncarea i-a de monede apare cu capul. Funcția logică care definește 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. Oferta 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)