Tema lekcije: "Sustavi logičkih jednadžbi." Rješavanje logičkih jednadžbi u matematici

Metode rješavanja sustava logičkih jednadžbi

Možete riješiti sustav logičkih jednadžbi, na primjer, pomoću tablice istinitosti (ako broj varijabli nije prevelik) ili pomoću stabla odlučivanja, nakon što ste prethodno pojednostavili svaku jednadžbu.

1. Metoda zamjene varijable.

Uvođenje novih varijabli omogućuje vam da pojednostavite sustav jednadžbi, smanjujući broj nepoznanica.Nove varijable moraju biti neovisne jedna o drugoj. Nakon rješavanja pojednostavljenog sustava moramo se vratiti na izvorne varijable.

Razmotrimo primjenu ove metode na konkretnom primjeru.

Primjer.

((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

Riješenje:

Uvedimo nove varijable: A=(X1≡ X2); B=(X3 ≡ X4); S=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Pažnja! Svaka od varijabli x1, x2, ..., x10 mora biti uključena samo u jednu od novih varijabli A, B, C, D, E, tj. nove varijable su neovisne jedna o drugoj).

Tada će sustav jednadžbi izgledati ovako:

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

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

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

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

Izgradimo stablo odlučivanja za rezultirajući sustav:

Razmotrimo jednadžbu A=0, tj. (X1≡ X2)=0. Ima 2 korijena:

Iz iste tablice se vidi da jednadžba A=1 također ima 2 korijena. Posložimo broj korijena na stablu odlučivanja:

Da biste pronašli broj rješenja jedne grane, morate pomnožiti broj rješenja na svakoj razini. Lijeva grana ima 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 rješenja; desna grana također ima 32 rješenja. Oni. cijeli sustav ima 32+32=64 rješenja.

Odgovor: 64.

2. Metoda rasuđivanja.

Teškoća rješavanja sustava logičkih jednadžbi leži u glomaznosti potpunog stabla odlučivanja. Metoda razmišljanja omogućuje vam da ne izgradite cijelo stablo, već da shvatite koliko će grana imati. Pogledajmo ovu metodu na konkretnim primjerima.

Primjer 1. Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 postoji koji zadovoljavaju sve dolje navedene uvjete?

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

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

x1\/y1 =1

Odgovor ne mora navesti sve različite skupove vrijednosti varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 za koje je ovaj sustav jednakosti zadovoljen. Kao odgovor morate navesti broj takvih skupova.

Riješenje :

Prva i druga jednadžba sadrže nezavisne varijable koje su povezane trećim uvjetom. Izgradimo stablo rješenja za prvu i drugu jednadžbu.

Za predstavljanje stabla rješenja za sustav prve i druge jednadžbe, svaka grana prvog stabla mora se nastaviti sa stablom za varijable na . Ovako konstruirano stablo imat će 36 grana. Neke od tih grana ne zadovoljavaju treću jednadžbu sustava. Označimo broj grana stabla na prvom stablu"y" , koji zadovoljavaju treću jednadžbu:

Objasnimo: da bi se zadovoljio treći uvjet, kada je x1=0 mora postojati y1=1, tj. sve grane stabla"X" , gdje se x1=0 može nastaviti sa samo jednom granom stabla"y" . I to samo za jednu granu stabla"X" (desno) sve grane stabla odgovaraju"y". Dakle, kompletno stablo cijelog sustava sadrži 11 grana. Svaka grana predstavlja jedno rješenje izvornog sustava jednadžbi. To znači da cijeli sustav ima 11 rješenja.

Odgovor: 11.

Primjer 2. Koliko različitih rješenja ima sustav jednadžbi?

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

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

………………

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

(X1 ≡ X10) = 0

gdje su x1, x2, …, x10 logičke varijable? Odgovor ne mora navesti sve različite skupove vrijednosti varijabli za koje ova jednakost vrijedi. Kao odgovor morate navesti broj takvih skupova.

Riješenje : Pojednostavimo sustav. Napravimo tablicu istinitosti za dio prve jednadžbe:

Obratite pozornost na zadnji stupac, on odgovara rezultatu akcije X1 ≡ X10.

Nakon pojednostavljenja dobivamo:

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

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

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

……

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

(X1 ≡ X10) = 0

Razmotrimo posljednju jednadžbu:(X1 ≡ X10) = 0, tj. x1 ne bi trebao koincidirati s x10. Da bi prva jednadžba bila jednaka 1, jednakost mora biti istinita(X1 ≡ X2)=1, tj. x1 mora odgovarati x2.

Izgradimo stablo rješenja za prvu jednadžbu:

Razmotrimo drugu jednadžbu: za x10=1 i za x2=0 zagradamora biti jednak 1 (tj. x2 se poklapa s x3); za x10=0 i za x2=1 zagrada(X2 ≡ X10)=0, što znači zagrada (X2 ≡ X3) treba biti jednak 1 (tj. x2 se podudara s x3):

Razmišljajući na ovaj način, gradimo stablo odlučivanja za sve jednadžbe:

Dakle, sustav jednadžbi ima samo 2 rješenja.

Odgovor: 2.

Primjer 3.

Koliko ima različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 koji zadovoljavaju sve dolje navedene uvjete?

(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

Riješenje:

Izgradimo stablo rješenja za 1. jednadžbu:

Razmotrimo drugu jednadžbu:

• Kada je x1=0 : druga i treća zagrada bit će jednake 0; da prva zagrada bude jednaka 1, y1=1, z1=1 (tj. u ovom slučaju - 1 rješenje)
• Kada je x1=1 : prva zagrada će biti jednaka 0; drugi ili treća zagrada mora biti jednaka 1; druga zagrada će biti jednaka 1 kada je y1=0 i z1=1; treća zagrada će biti jednaka 1 kada je y1=1 i z1=0 (tj. u ovom slučaju - 2 rješenja).

Slično za preostale jednadžbe. Zabilježimo rezultirajući broj rješenja za svaki čvor stabla:

Da biste saznali broj rješenja za svaku granu, pomnožite dobivene brojeve posebno za svaku granu (slijeva na desno).

1 grana: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 rješenje

Grana 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 rješenja

3. grana: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 rješenja

4. grana: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 rješenja

5. grana: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 rješenja

Zbrojimo dobivene brojeve: ukupno je 31 rješenje.

Odgovor: 31.

3. Prirodni porast broja korijena

U nekim sustavima, broj korijena sljedeće jednadžbe ovisi o broju korijena prethodne jednadžbe.

Primjer 1. Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 postoji koji zadovoljavaju sve dolje navedene uvjete?

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

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

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

Pojednostavimo prva jednadžba:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Tada će sustav imati oblik:

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

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

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

itd.

Svaka sljedeća jednadžba ima 2 korijena više od prethodne.

4 jednadžba ima 12 korijena;

Jednadžba 5 ima 14 korijena

Jednadžba 8 ima 20 korijena.

Odgovor: 20 korijena.

Ponekad broj korijena raste prema Fibonaccijevom zakonu.

Rješavanje sustava logičkih jednadžbi zahtijeva kreativan pristup.

Kako riješiti neke zadatke u dijelovima A i B ispita iz informatike

Lekcija #3. Logike. Logičke funkcije. Rješavanje jednadžbi

Velik broj zadataka Jedinstvenog državnog ispita posvećen je propozicijskoj logici. Za rješavanje većine njih dovoljno je poznavanje osnovnih zakona iskazne logike, poznavanje tablica istinitosti logičkih funkcija jedne i dvije varijable. Dat ću osnovne zakone propozicijske logike.

1. Komutativnost disjunkcije i konjunkcije:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distributivni zakon o disjunkciji i konjunkciji:
   a ˅ (b^s) ≡ (a ˅ b) ^(a ˅ s)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negacija negacije:
   ¬(¬a) ≡ a
4. Dosljednost:
   a ^ ¬a ≡ lažno
5. Ekskluzivno treće:
   a ˅ ¬a ≡ istinito
6. De Morganovi zakoni:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Pojednostavljenje:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ točno ≡ a
   a ˄ lažno ≡ lažno
8. Apsorpcija:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Zamjena implikacije
   a → b ≡ ¬a ˅ b
10. Zamjena identiteta
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Predstavljanje logičkih funkcija

Bilo koja logička funkcija od n varijabli - F(x 1, x 2, ... x n) može se specificirati tablicom istine. Takva tablica sadrži 2n skupova varijabli, za svaki od njih je navedena vrijednost funkcije na tom skupu. Ova metoda je dobra kada je broj varijabli relativno mali. Već za n > 5 prikaz postaje slabo vidljiv.

Drugi način je definirati funkciju nekom formulom koristeći poznate prilično jednostavne funkcije. Sustav funkcija (f 1, f 2, ... f k) naziva se potpunim ako se bilo koja logička funkcija može izraziti formulom koja sadrži samo funkcije f i.

Sustav funkcija (¬, ˄, ˅) je dovršen. Zakoni 9 i 10 primjeri su koji pokazuju kako se implikacija i identitet izražavaju kroz negaciju, konjunkciju i disjunkciju.

Zapravo, sustav dviju funkcija – negacije i konjunkcije ili negacije i disjunkcije – također je potpun. Iz De Morganovih zakona slijede ideje koje omogućuju izražavanje konjunkcije kroz negaciju i disjunkciju i, sukladno tome, izražavanje disjunkcije kroz negaciju i konjunkciju:

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

Paradoksalno, sustav koji se sastoji od samo jedne funkcije je potpun. Postoje dvije binarne funkcije - antikonjunkcija i antidisjunkcija, nazvane Peirceova strelica i Schaefferov potez, koje predstavljaju šuplji sustav.

Osnovne funkcije programskih jezika obično uključuju identitet, negaciju, konjunkciju i disjunkciju. U problemima Jedinstvenog državnog ispita, uz ove funkcije, često se nalazi implikacija.

Pogledajmo nekoliko jednostavnih problema koji uključuju logičke funkcije.

Problem 15:

Dan je fragment tablice istinitosti. Koja od tri navedene funkcije odgovara ovom fragmentu?

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)

Funkcija broj 3.

Da biste riješili problem, morate znati tablice istinitosti osnovnih funkcija i zapamtiti prioritete operacija. Dopustite mi da vas podsjetim da konjunkcija (logičko množenje) ima veći prioritet i izvršava se prije od disjunkcije (logičko zbrajanje). Tijekom izračuna lako je primijetiti da funkcije s brojevima 1 i 2 u trećem skupu imaju vrijednost 1 i zbog toga ne odgovaraju fragmentu.

Problem 16:

Koji od datih brojeva zadovoljava uvjet:

(znamenke, počevši od najznačajnije znamenke, idu silaznim redoslijedom) → (broj - paran) ˄ (niža znamenka - paran) ˄ (viša znamenka - neparan)

Ako postoji više takvih brojeva, navedite najveći.

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

Uvjet je zadovoljen kod broja 4.

Prva dva broja ne zadovoljavaju uvjet iz razloga što je najniža znamenka neparna. Konjunkcija uvjeta je lažna ako je jedan od članova konjunkcije lažan. Za treći broj nije ispunjen uvjet za najvišu znamenku. Za četvrti broj ispunjeni su uvjeti za nižu i visoku znamenku broja. Prvi član konjunkcije je također istinit, budući da je implikacija istinita ako je njena premisa lažna, što je ovdje slučaj.

Problem 17: Dva svjedoka dala su sljedeći iskaz:

Prvi svjedok: Ako je A kriv, onda je B još više kriv, a C je nevin.

Drugi svjedok: Dvojica su kriva. A od preostalih jedan je sigurno kriv i dužan, ali ne mogu reći tko točno.

Kakvi se zaključci o krivnji A, B i C mogu izvući iz iskaza?

Odgovor: Iz iskaza proizilazi da su A i B krivi, a C nevin.

Rješenje: Naravno, odgovor se može dati na temelju zdravog razuma. Ali pogledajmo kako se to može učiniti striktno i formalno.

Prvo što treba učiniti je formalizirati izjave. Uvedimo tri logičke varijable - A, B i C, od kojih svaka ima vrijednost true (1) ako je odgovarajući osumnjičenik kriv. Tada se iskaz prvog svjedoka daje formulom:

A → (B ˄ ¬C)

Iskaz drugog svjedoka daje se formulom:

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

Iskazi obaju svjedoka pretpostavljaju se istinitima i predstavljaju spoj odgovarajućih formula.

Napravimo tablicu istinitosti za ova očitanja:

Sažeti dokazi su istiniti samo u jednom slučaju, što dovodi do jasnog odgovora - A i B su krivi, a C je nevin.

Iz analize ove tablice također proizlazi da je iskaz drugog svjedoka informativniji. Iz istinitosti njegova svjedočenja proizlaze samo dvije moguće opcije - A i B su krivi, a C je nevin ili A i C su krivi, a B je nevin. Iskaz prvog svjedoka je manje informativan - postoji 5 različitih opcija koje odgovaraju njegovom iskazu. Zajedno, iskazi oba svjedoka daju jasan odgovor o krivnji osumnjičenih.

Logičke jednadžbe i sustavi jednadžbi

Neka je F(x 1, x 2, …x n) logička funkcija od n varijabli. Logička jednadžba izgleda ovako:

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

Konstanta C ima vrijednost 1 ili 0.

Logička jednadžba može imati od 0 do 2 n različitih rješenja. Ako je C jednak 1, tada su rješenja svi oni skupovi varijabli iz tablice istinitosti za koje funkcija F ima vrijednost true (1). Preostali skupovi su rješenja jednadžbe s C jednakim nuli. Uvijek možete razmatrati samo jednadžbe oblika:

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

Doista, neka je dana jednadžba:

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

U ovom slučaju možemo prijeći na ekvivalentnu jednadžbu:

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

Razmotrimo sustav od k logičkih jednadžbi:

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

Rješenje sustava je skup varijabli na kojem su zadovoljene sve jednadžbe sustava. Što se tiče logičkih funkcija, da bi se dobilo rješenje sustava logičkih jednadžbi, treba pronaći skup na kojem je istinita logička funkcija F, koja predstavlja konjunkciju izvornih funkcija F:

F = F 1 ˄ F 2 ˄ … F k

Ako je broj varijabli mali, npr. manji od 5, tada nije teško konstruirati tablicu istinitosti za funkciju F, koja nam omogućuje da kažemo koliko rješenja ima sustav i koji su skupovi koji daju rješenja.

U nekim USE problemima pronalaženja rješenja sustava logičkih jednadžbi broj varijabli doseže 10. Tada konstruiranje tablice istinitosti postaje gotovo nemoguć zadatak. Rješavanje problema zahtijeva drugačiji pristup. Za proizvoljan sustav jednadžbi ne postoji opća metoda osim nabrajanja koja omogućuje rješavanje takvih problema.

U zadacima predloženim na ispitu rješavanje se obično temelji na uzimanju u obzir specifičnosti sustava jednadžbi. Ponavljam, osim isprobavanja svih opcija za skup varijabli, ne postoji opći način rješavanja problema. Rješenje se mora graditi na temelju specifičnosti sustava. Često je korisno izvesti preliminarno pojednostavljenje sustava jednadžbi korištenjem poznatih zakona logike. Još jedna korisna tehnika za rješavanje ovog problema je sljedeća. Ne zanimaju nas svi skupovi, već samo oni na kojima funkcija F ima vrijednost 1. Umjesto da gradimo potpunu tablicu istinitosti, izgradit ćemo njen analog - binarno stablo odlučivanja. Svaka grana ovog stabla odgovara jednom rješenju i zadaje skup na kojem funkcija F ima vrijednost 1. Broj grana u stablu odlučivanja podudara se s brojem rješenja sustava jednadžbi.

Objasnit ću što je binarno stablo odlučivanja i kako se gradi koristeći primjere nekoliko problema.

Problem 18

Koliko postoji različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 koji zadovoljavaju sustav dviju jednadžbi?

Odgovor: Sustav ima 36 različitih rješenja.

Rješenje: Sustav jednadžbi uključuje dvije jednadžbe. Nađimo broj rješenja za prvu jednadžbu, ovisno o 5 varijabli - x 1, x 2, ...x 5. Prva se jednadžba može pak smatrati sustavom od 5 jednadžbi. Kao što je pokazano, sustav jednadžbi zapravo predstavlja konjunkciju logičkih funkcija. Vrijedi i obrnuto: konjunkcija uvjeta može se smatrati sustavom jednadžbi.

Izgradimo stablo odlučivanja za implikaciju (x1→ x2) - prvi član konjunkcije, koji se može smatrati prvom jednadžbom. Ovako izgleda grafički prikaz ovog stabla:

Stablo se sastoji od dvije razine prema broju varijabli u jednadžbi. Prva razina opisuje prvu varijablu X 1 . Dvije grane ove razine odražavaju moguće vrijednosti ove varijable - 1 i 0. Na drugoj razini, grane stabla odražavaju samo one moguće vrijednosti varijable X 2 za koje je jednadžba istinita. Budući da jednadžba navodi implikaciju, grana na kojoj X 1 ima vrijednost 1 zahtijeva da na toj grani X 2 ima vrijednost 1. Grana na kojoj X 1 ima vrijednost 0 proizvodi dvije grane s vrijednostima X 2 jednako 0 i 1. Konstruirano stablo definira tri rješenja, na kojima implikacija X 1 → X 2 poprima vrijednost 1. Na svakoj grani ispisuje se odgovarajući skup varijabilnih vrijednosti, dajući rješenje jednadžbe.

Ovi skupovi su: ((1, 1), (0, 1), (0, 0))

Nastavimo graditi stablo odlučivanja dodavanjem sljedeće jednadžbe, sljedeće implikacije X 2 → X 3 . Specifičnost našeg sustava jednadžbi je u tome što svaka nova jednadžba sustava koristi jednu varijablu iz prethodne jednadžbe, dodajući jednu novu varijablu. Budući da varijabla X 2 već ima vrijednosti u stablu, tada će na svim granama gdje varijabla X 2 ima vrijednost 1, varijabla X 3 također imati vrijednost 1. Za takve grane, konstrukcija stabla nastavlja na sljedeću razinu, ali se nove grane ne pojavljuju. Pojedinačna grana gdje varijabla X 2 ima vrijednost 0 će se granati u dvije grane gdje će varijabla X 3 dobiti vrijednosti 0 i 1. Dakle, svaki dodatak nove jednadžbe, s obzirom na njezine specifičnosti, dodaje jedno rješenje. Izvorna prva jednadžba:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
ima 6 rješenja. Evo kako izgleda kompletno stablo odlučivanja za ovu jednadžbu:

Druga jednadžba našeg sustava slična je prvoj:

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

Jedina razlika je u tome što jednadžba koristi varijable Y. Ova jednadžba također ima 6 rješenja. Budući da se svako rješenje za varijable X i može kombinirati sa svakim rješenjem za varijable Y j, ukupan broj rješenja je 36.

Napominjemo da konstruirano stablo odlučivanja ne daje samo broj rješenja (prema broju grana), već i sama rješenja zapisana na svakoj grani stabla.

Problem 19

Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 postoji koji zadovoljavaju sve dolje navedene uvjete?

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

Ovaj zadatak je modifikacija prethodnog zadatka. Razlika je u tome što se dodaje još jedna jednadžba koja povezuje varijable X i Y.

Iz jednadžbe X 1 → Y 1 slijedi da kada X 1 ima vrijednost 1 (postoji jedno takvo rješenje), tada Y 1 također ima vrijednost 1. Dakle, postoji jedan skup na kojem X 1 i Y 1 imaju vrijednosti ​​1. Kada je X 1 jednak 0, Y 1 može imati bilo koju vrijednost, i 0 i 1. Prema tome, svaki skup s X 1 jednakim 0, a postoji 5 takvih skupova, odgovara svih 6 skupova s ​​Y varijablama. Dakle, ukupan broj rješenja je 31 .

Problem 20

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

Rješenje: Sjećajući se osnovnih ekvivalencija, svoju jednadžbu pišemo kao:

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

Ciklički lanac implikacija znači da su varijable identične, pa je naša jednadžba ekvivalentna jednadžbi:

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

Ova jednadžba ima dva rješenja kada su svi X i 1 ili 0.

Problem 21

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

Rješenje: Baš kao u problemu 20, prelazimo s cikličkih implikacija na identitete, prepisujući jednadžbu u obliku:

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

Izgradimo stablo odlučivanja za ovu jednadžbu:

Problem 22

Koliko rješenja ima sljedeći sustav jednadžbi?

((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

Odgovor: 64

Rješenje: Prijeđimo s 10 varijabli na 5 varijabli uvođenjem sljedeće izmjene varijabli:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Tada će prva jednadžba imati oblik:

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

Jednadžba se može pojednostaviti tako da se zapiše kao:

(Y 1 ≡ Y 2) = 0

Prelazeći na tradicionalni oblik, zapisujemo sustav nakon pojednostavljenja u obliku:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Stablo odlučivanja za ovaj sustav je jednostavno i sastoji se od dvije grane s izmjeničnim vrijednostima varijabli:

Vraćajući se na izvorne X varijable, imajte na umu da za svaku vrijednost u Y varijabli postoje 2 vrijednosti u X varijablama, tako da svako rješenje u Y varijablama generira 2 5 rješenja u X varijablama. Dvije grane generiraju 2 * 2 5 rješenja, tako da je ukupan broj rješenja 64.

Kao što vidite, svaki problem rješavanja sustava jednadžbi zahtijeva vlastiti pristup. Uobičajena tehnika je izvođenje ekvivalentnih transformacija za pojednostavljenje jednadžbi. Uobičajena tehnika je konstruiranje stabala odlučivanja. Pristup koji se koristi djelomično podsjeća na konstruiranje tablice istine s tom posebnošću da nisu konstruirani svi skupovi mogućih vrijednosti varijabli, već samo oni na kojima funkcija ima vrijednost 1 (true). Često u predloženim problemima nema potrebe za izgradnjom potpunog stabla odlučivanja, budući da je već u početnoj fazi moguće uspostaviti obrazac pojavljivanja novih grana na svakoj sljedećoj razini, kao što je učinjeno, na primjer, u problemu 18 .

Općenito, problemi koji uključuju pronalaženje rješenja sustava logičkih jednadžbi dobre su matematičke vježbe.

Ako je problem teško riješiti ručno, tada rješenje možete povjeriti računalu tako da napišete odgovarajući program za rješavanje jednadžbi i sustava jednadžbi.

Nije teško napisati takav program. Takav program lako će se nositi sa svim zadacima ponuđenim na Jedinstvenom državnom ispitu.

Čudno je da je zadatak pronalaženja rješenja sustava logičkih jednadžbi težak za računalo, a ispada da računalo ima svoje granice. Računalo se vrlo lako može nositi s problemima gdje je broj varijabli 20-30, ali će početi dugo razmišljati o problemima veće veličine. Činjenica je da je funkcija 2 n, koja određuje broj skupova, eksponencijal koji brzo raste kako n raste. Toliko brzo da se obično osobno računalo ne može nositi sa zadatkom koji ima 40 varijabli u danu.

Program u C# jeziku za rješavanje logičkih jednadžbi

Pisanje programa za rješavanje logičkih jednadžbi korisno je iz mnogo razloga, barem zato što ga možete koristiti za provjeru točnosti vlastitog rješenja zadataka testa Jedinstvenog državnog ispita. Drugi razlog je taj što je takav program izvrstan primjer programskog zadatka koji udovoljava zahtjevima za zadatke kategorije C na Jedinstvenom državnom ispitu.

Ideja izgradnje programa je jednostavna - temelji se na potpunom pretraživanju svih mogućih skupova varijabilnih vrijednosti. Kako je za zadanu logičku jednadžbu ili sustav jednadžbi poznat broj varijabli n, onda je poznat i broj skupova - 2 n koje treba razvrstati. Pomoću osnovnih funkcija jezika C# - negacije, disjunkcije, konjunkcije i identiteta, nije teško napisati program koji za zadani skup varijabli izračunava vrijednost logičke funkcije koja odgovara logičkoj jednadžbi ili sustavu jednadžbi. .

U takvom programu trebate izgraditi petlju na temelju broja skupova, u tijelu petlje, koristeći broj skupa, formirati sam skup, izračunati vrijednost funkcije na tom skupu, i ako ovo vrijednost je 1, tada skup daje rješenje jednadžbe.

Jedina poteškoća koja se javlja pri implementaciji programa odnosi se na zadatak generiranja skupa vrijednosti varijable na temelju zadanog broja. Ljepota ovog problema je u tome što se ovaj naizgled težak zadatak zapravo svodi na jednostavan problem koji se već mnogo puta pojavio. Doista, dovoljno je razumjeti da skup vrijednosti varijable koji odgovara broju i, koji se sastoji od nula i jedinica, predstavlja binarnu reprezentaciju broja i. Dakle, složeni zadatak dobivanja skupa varijabilnih vrijednosti prema postavljenom broju svodi se na poznati zadatak pretvaranja broja u binarni.

Ovako izgleda funkcija u C# koja rješava naš problem:

///

///

/// logička funkcija - metoda,

/// čiji potpis specificira delegat DF-a

///

/// broj varijabli

/// broj rješenja

static int SolveEquations(DF fun, int n)

bool set = novi bool[n];

int m = (int)Math.Pow(2, n); //broj skupova

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

//Dovrši pretragu prema broju skupova

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

//Formiranje sljedećeg skupa - set,

//određeno binarnom reprezentacijom broja i

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

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

//Izračunaj vrijednost funkcije na skupu

Za razumijevanje programa nadam se da su objašnjenja ideje programa i komentari u njegovom tekstu dovoljni. Usredotočit ću se samo na objašnjenje naziva dane funkcije. Funkcija SolveEquations ima dva ulazna parametra. Fun parametar specificira logičku funkciju koja odgovara jednadžbi ili sustavu jednadžbi koji se rješava. Parametar n određuje broj zabavnih varijabli. Kao rezultat, funkcija SolveEquations vraća broj rješenja logičke funkcije, odnosno broj onih skupova na kojima funkcija daje vrijednost true.

Za školarce je uobičajeno da neka funkcija F(x) ima ulazni parametar x koji je varijabla aritmetičkog, string ili logičkog tipa. U našem slučaju koristi se snažniji dizajn. Funkcija SolveEquations odnosi se na funkcije višeg reda - funkcije tipa F(f), čiji parametri mogu biti ne samo jednostavne varijable, već i funkcije.

Klasa funkcija koje se mogu proslijediti kao parametar funkciji SolveEquations navedena je na sljedeći način:

delegat bool DF(bool vars);

Ova klasa posjeduje sve funkcije koje se prosljeđuju kao parametar skupa vrijednosti logičkih varijabli navedenih u nizu vars. Rezultat je Booleova vrijednost koja predstavlja vrijednost funkcije na ovom skupu.

Konačno, ovdje je program koji koristi funkciju SolveEquations za rješavanje nekoliko sustava logičkih jednadžbi. Funkcija SolveEquations dio je klase ProgramCommon ispod:

klasa ProgramCommon

delegat bool DF(bool vars);

static void Main(string args)

Console.WriteLine("I funkcije - " +

Riješite jednadžbe(FunAnd, 2));

Console.WriteLine("Funkcija ima 51 rješenje - " +

Riješi jednadžbe(Zabava51, 5));

Console.WriteLine("Funkcija ima 53 rješenja - " +

Riješite jednadžbe (Zabava53, 10));

statički bool FunAnd(bool vars)

return vars && vars;

statički bool Fun51(bool vars)

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

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

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

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

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

statički 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)));

Evo kako izgledaju rezultati rješenja za ovaj program:

10 zadataka za samostalan rad

1. Koje su od tri funkcije ekvivalentne:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Dan je fragment tablice istine:

Kojoj od tri funkcije odgovara ovaj 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. Žiri se sastoji od tri osobe. Odluka je donesena ako za nju glasuje predsjednik žirija uz potporu najmanje jednog člana žirija. U protivnom se ne donosi odluka. Konstruirajte logičku funkciju koja formalizira proces donošenja odluka.
5. X pobjeđuje Y ako četiri bacanja novčića rezultiraju glavama tri puta. Definirajte logičku funkciju koja opisuje isplatu X.
6. Riječi u rečenici numeriraju se počevši od jedan. Rečenica se smatra ispravno konstruiranom ako su ispunjena sljedeća pravila:
   1. Ako parna riječ završava samoglasnikom, onda sljedeća riječ, ako postoji, mora započeti samoglasnikom.
   2. Ako neparna riječ završava suglasnikom, onda sljedeća riječ, ako postoji, mora započeti suglasnikom i završiti samoglasnikom.
      Koje su od sljedećih rečenica pravilno sastavljene:
   3. Mama je oprala Mašu sapunom.
   4. Lider je uvijek uzor.
   5. Istina je dobra, ali sreća je bolja.
7. Koliko rješenja ima jednadžba:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Navedite sva rješenja jednadžbe:
   (a → b) → c = 0
9. Koliko rješenja ima sljedeći sustav jednadžbi:
   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. Koliko rješenja ima jednadžba:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Odgovori na probleme:

1. Funkcije b i c su ekvivalentne.
2. Fragment odgovara funkciji b.
3. Neka logička varijabla P poprimi vrijednost 1 kada predsjednik žirija glasa “za” odluku. Varijable M 1 i M 2 predstavljaju mišljenja članova žirija. Logička funkcija koja specificira donošenje pozitivne odluke može se napisati na sljedeći način:
   P ˄ (M 1 ˅ M 2)
4. Neka logička varijabla P i poprimi vrijednost 1 kada i-ti novčić padne na glavu. Logička funkcija koja specificira isplatu X može se napisati na sljedeći način:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Rečenica b.
6. Jednadžba ima 3 rješenja: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Upotreba jednadžbi široko je rasprostranjena u našim životima. Koriste se u mnogim izračunima, izgradnji građevina, pa čak i sportu. Čovjek je koristio jednadžbe u davna vremena, a od tada se njihova upotreba samo povećava. U matematici postoje određeni problemi koji se bave iskaznom logikom. Za rješavanje ovakve jednadžbe potrebno je imati određeno znanje: poznavanje zakona logike iskaza, poznavanje tablica istinitosti logičkih funkcija 1 ili 2 varijable, metode za pretvaranje logičkih izraza. Osim toga, potrebno je poznavati sljedeća svojstva logičkih operacija: konjunkciju, disjunkciju, inverziju, implikaciju i ekvivalenciju.

Bilo koja logička funkcija \varijable - \može se specificirati tablicom istine.

Riješimo nekoliko logičkih jednadžbi:

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

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

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

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

Započnimo rješenje s \[X1\] i odredimo koje vrijednosti ova varijabla može poprimiti: 0 i 1. Zatim ćemo razmotriti svaku od gornjih vrijednosti i vidjeti što može biti \[X2.\].

Kao što se vidi iz tablice, naša logička jednadžba ima 11 rješenja.

Gdje mogu riješiti logičku jednadžbu online?

Jednadžbu možete riješiti na našoj web stranici https://site. Besplatni mrežni rješavač omogućit će vam rješavanje mrežnih jednadžbi bilo koje složenosti u nekoliko sekundi. Sve što trebate učiniti je jednostavno unijeti svoje podatke u Solver. Također možete pogledati video upute i naučiti kako riješiti jednadžbu na našoj web stranici. A ako još uvijek imate pitanja, možete ih postaviti u našoj VKontakte grupi http://vk.com/pocketteacher. Pridružite se našoj grupi, uvijek ćemo vam rado pomoći.

Trenutno su sve veći zahtjevi za poboljšanjem kvalitete obrazovanja za školsku djecu. Jedna od najvažnijih novosti u sadržaju matematičkog obrazovanja je uključivanje elemenata matematičke logike u školske programe. To je zbog uloge koju logičko znanje ima u općoj obrazovnoj pripremi suvremenog čovjeka.
Preporučljivo je započeti proučavanje elemenata matematičke logike u 5.–6. razredu ili u 7. razredu, ovisno o sustavu izlaganja u udžbeniku koji se koristi za nastavu. Potrebno vrijeme može se pronaći odbijanjem razmatranja s učenicima pitanja koja nisu uključena u obvezni minimum sadržaja osnovne škole (korijen stupnja n, stupanj s razlomljenim eksponentom, metoda intervala, trigonometrijsko gradivo u kolegiju algebre) , ali su sačuvani u nizu udžbenika i u učiteljskoj praksi.
Ali najčešće se ti dijelovi proučavaju samo u izbornim predmetima.

Predmet:“Sustavi logičkih jednadžbi” (10. razred)

Ciljevi lekcije:

• upoznavanje učenika s pojmom sustava logičkih jednadžbi, proučavanje različitih metoda za njihovo rješavanje, ponavljanje metoda za rješavanje algebarskih sustava i skalarnog produkta vektora;
• razvoj matematičkog mišljenja i logičkog govora učenika, mašte, sposobnosti analize i primjene znanja u nepoznatoj situaciji;
• njegovanje interesa za predmet, marljivost i pozornost.

Oprema: ploča, kreda, bilježnice, olovke, olovke, mreže za rješavanje sustava s tri i četiri nepoznanice.

TIJEKOM NASTAVE

I. Organizacijski trenutak

II. Poruka o temi lekcije

Zapiši naziv teme u svoju bilježnicu.

– Na prošlom smo satu učili logičke operacije. Danas nastavljamo proučavati logičke jednadžbe i učimo kako rješavati sustave takvih jednadžbi. Treba odmah napomenuti da se sustavi logičkih jednadžbi rješavaju malo drugačije od algebarskih. Ili bolje rečeno, na druge načine.

III. Obnavljanje znanja

– Što znači riješiti sustav s dvije varijable?
Rješavanje sustava s dvije varijable znači pronaći sve parove (x, y) koji zadovoljavaju svaku od zadanih jednadžbi ili dokazati da ne postoji rješenje.
Koje načine rješavanja sustava znate?

• metoda supstitucije
• metoda dodavanja
• način uvođenja novih varijabli,
• grafička metoda.

1. Riješite sustav jednadžbi u nizu.

• Prvi red je dodavanjem;
• Drugi je grafički;
• Treći je metodom supstitucije.

a) Zbrajajući jednadžbu član po član, imamo: 2 x + 10x = 15 + 9;

12x = 24; x= 2, zamjenom ove vrijednosti u drugu jednadžbu, dobivamo: 10 . 2 – 11na= 9, odakle na = 1.

Odgovor:(2;1).

b) Iz prve jednadžbe, iz druge jednadžbe,

A (2;1) je točka presjeka grafova jednadžbi.

(2;1) – rješenje sustava.

c) Zamijenite iz prve jednadžbe u drugu

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

Odgovor: (2;1).

– Što se naziva skalarni produkt vektora?
Skalarni umnožak vektora je broj jednak umnošku duljina tih vektora i kosinusa kuta između njih.
Kako zapisati točkasti umnožak u koordinatnom obliku?

.

IV. Glavna pozornica

Koristeći dvije operacije “disjunkciju” i “konjunkciju”, razmatramo Booleove sustave dviju jednadžbi s dvije nepoznanice:

Pronalaženje varijable u jednoj jednadžbi s jednom logičkom operacijom rezultira višestrukim rješenjima. Kada bi se rješenje sustava izrazilo nekom specifičnom formulom, tada bismo zamjenom početnih podataka (koeficijenata jednadžbe) dobili potpuno određeno rješenje. Na jednostavnom primjeru vidimo polisemičnost rješenja, dakle ili rješenje sustava u općem obliku mora biti izraženo s nekoliko formula ili takve formule ne postoje eksplicitno. Trenutno takve formule još nisu pronađene, pa se sustavi logičkih jednadžbi rješavaju jedinstvenim metodama, s kojima ćemo se danas upoznati u lekciji.
Sustav ovisi o šest parametara a,b,c,d,m,n, od kojih svaka ima dvije vrijednosti 0 ili 1. Dakle, ukupno dobivamo 2 6 = 64 slučaja.
Analitički rezultat može se dobiti logičkim zaključivanjem i prolaskom kroz sva 64 slučaja.

Vježba 1.(jedan učenik radi za pločom).

Riješite sustav ako a = 0, b = 0, c = 0, d = 0, m = 0, n = 0.

.

Odgovor: sustav ima 4 rješenja: (1;1), (0;1), (1;0),(0;0).

Zadatak 2.(samostalno u bilježnicama uz naknadnu provjeru).

Riješite sustav ako a = 1, b = 0, c = 0, d = 0, m = 0, n = 0.

,

Odgovor: sustav ima 2 rješenja: (0;0), (0;1).

Slično, možete riješiti preostala 62 sustava zamjenom umjesto parametara a,b,c,d,m,n redom, vrijednosti su 0 i 1.
Moguće je čak grupirati neke slučajeve u klase kako bi se istaknuli uvjeti za slučajeve u kojima sustav ima jedno rješenje, nekoliko rješenja ili nema rješenja.
U školskom tečaju matematike može se identificirati vrlo ograničen raspon problema koji se mogu riješiti pomoću sustava logičkih jednadžbi.

Zadatak 3.Šest prozirnih čaša s vodom poredano je u dva paralelna reda po tri čaše. Slika prikazuje pogled sprijeda i pogled s desne strane. Kroz prozirne stijenke čaša vidljive su razine vode u svakoj čaši i u svim čašama iza njih. Odredite koliko je vode uliveno u svaku čašu.

Na slici se vidi da su čaše pune ili prazne. Skup čaša koji se nalazi na ovih šest mjesta čini abecedu koja se sastoji od dva elementa.
Označimo praznu čašu s 0, a punu s 1. Tada se skup sastoji od 0 i 1, tj. = (0,1) .
Označimo projekcije na slici brojevima od 1 do 5.
Označimo redove stakala kako slijedi i označimo elemente koji se mogu pojaviti u tim redovima

Prva projekcija pokazuje da u prvom stupcu nema punih čaša, tj. x 11 = 0, x 21 = 0.

Iz pete projekcije jasno je da x 23 = 0, x 22 = 0. Preostale elemente je lako odrediti: x 12 = 1, x 13 = 1.

Analitički se formulacija problema svodi na rješavanje sustava jednadžbi

Imamo sustav jednadžbi u kojem su operacije “+” disjunkcija, “ . ” – veznik.
Iz druge jednadžbe sustava i pravih tablica konjunkcije i disjunkcije dobivamo x 21 + x 22 + x 23 = 0 => x 21 = x 22 = x 23 = 0.
Iz treće jednadžbe => x 11 = 0.
Zamijenimo pronađene vrijednosti nepoznanica u četvrtu i petu jednadžbu sustava:

Svi slobodni i nepoznati članovi imaju vrijednosti 0 ili 1, a jednadžbe zadovoljavaju logičke operacije, tj. dobivamo sustav logičkih jednadžbi.
Dakle, ako problem sadrži dvije vrste naočala, tada se može lako riješiti rješavanjem sustava logičkih jednadžbi. To štedi vrijeme i pruža kraće i jednostavnije rješenje.
Razmotrimo metodu transparentnih tablica (metoda mreže) - analognu grafičku metodu za rješavanje algebarskih sustava, koja vam omogućuje brzo rješavanje sustava jednadžbi koje ne sadrže više od četiri varijable.
Ova se metoda temelji na skalarnom produktu vektora.

Neka je logička funkcija od n varijabli. Logička jednadžba izgleda ovako:

Konstanta C ima vrijednost 1 ili 0.

Logička jednadžba može imati od 0 do različitih rješenja. Ako je C jednak 1, tada su rješenja svi oni skupovi varijabli iz tablice istinitosti za koje funkcija F ima vrijednost true (1). Preostali skupovi su rješenja jednadžbe s C jednakim nuli. Uvijek možete razmatrati samo jednadžbe oblika:

Doista, neka je dana jednadžba:

U ovom slučaju možemo prijeći na ekvivalentnu jednadžbu:

Razmotrimo sustav od k logičkih jednadžbi:

Rješenje sustava je skup varijabli na kojem su zadovoljene sve jednadžbe sustava. Što se tiče logičkih funkcija, da bi se dobilo rješenje sustava logičkih jednadžbi, treba pronaći skup na kojem je istinita logička funkcija F, koja predstavlja konjunkciju izvornih funkcija:

Ako je broj varijabli mali, na primjer manji od 5, tada nije teško konstruirati tablicu istine za funkciju, koja nam omogućuje da kažemo koliko rješenja ima sustav i koji su skupovi koji daju rješenja.

U nekim USE problemima pronalaženja rješenja sustava logičkih jednadžbi broj varijabli doseže 10. Tada konstruiranje tablice istinitosti postaje gotovo nemoguć zadatak. Rješavanje problema zahtijeva drugačiji pristup. Za proizvoljan sustav jednadžbi ne postoji opća metoda osim nabrajanja koja omogućuje rješavanje takvih problema.

U zadacima predloženim na ispitu rješavanje se obično temelji na uzimanju u obzir specifičnosti sustava jednadžbi. Ponavljam, osim isprobavanja svih opcija za skup varijabli, ne postoji opći način rješavanja problema. Rješenje se mora graditi na temelju specifičnosti sustava. Često je korisno izvesti preliminarno pojednostavljenje sustava jednadžbi korištenjem poznatih zakona logike. Još jedna korisna tehnika za rješavanje ovog problema je sljedeća. Ne zanimaju nas svi skupovi, već samo oni na kojima funkcija ima vrijednost 1. Umjesto da gradimo potpunu tablicu istinitosti, izgradit ćemo njen analog - binarno stablo odlučivanja. Svaka grana ovog stabla odgovara jednom rješenju i zadaje skup na kojem funkcija ima vrijednost 1. Broj grana u stablu odlučivanja podudara se s brojem rješenja sustava jednadžbi.

Objasnit ću što je binarno stablo odlučivanja i kako se gradi koristeći primjere nekoliko problema.

Problem 18

Koliko postoji različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 koji zadovoljavaju sustav dviju jednadžbi?

Odgovor: Sustav ima 36 različitih rješenja.

Rješenje: Sustav jednadžbi uključuje dvije jednadžbe. Nađimo broj rješenja za prvu jednadžbu, ovisno o 5 varijabli - . Prva se jednadžba može pak smatrati sustavom od 5 jednadžbi. Kao što je pokazano, sustav jednadžbi zapravo predstavlja konjunkciju logičkih funkcija. Obratna izjava je također istinita - konjunkcija uvjeta može se smatrati sustavom jednadžbi.

Izgradimo stablo odlučivanja za implikaciju () - prvi član konjunkcije, koji se može smatrati prvom jednadžbom. Ovako izgleda grafički prikaz ovog stabla

Stablo se sastoji od dvije razine prema broju varijabli u jednadžbi. Prva razina opisuje prvu varijablu. Dvije grane ove razine odražavaju moguće vrijednosti ove varijable - 1 i 0. Na drugoj razini, grane stabla odražavaju samo one moguće vrijednosti varijable za koje se jednadžba procjenjuje kao istinita. Budući da jednadžba specificira implikaciju, grana koja ima vrijednost 1 zahtijeva da na ovoj grani postoji vrijednost 1. Grana koja ima vrijednost 0 generira dvije grane s vrijednostima jednakim 0 i 1. Konstruirana stablo specificira tri rješenja, od kojih implikacija ima vrijednost 1. Na svakoj grani ispisan je odgovarajući skup vrijednosti varijable, dajući rješenje jednadžbe.

Ovi skupovi su: ((1, 1), (0, 1), (0, 0))

Nastavimo graditi stablo odlučivanja dodavanjem sljedeće jednadžbe, sljedeće implikacije. Specifičnost našeg sustava jednadžbi je u tome što svaka nova jednadžba sustava koristi jednu varijablu iz prethodne jednadžbe, dodajući jednu novu varijablu. Budući da varijabla već ima vrijednosti u stablu, tada će na svim granama gdje varijabla ima vrijednost 1, varijabla također imati vrijednost 1. Za takve grane, konstrukcija stabla nastavlja se na sljedeću razinu, ali se ne pojavljuju nove grane. Jedna grana gdje varijabla ima vrijednost 0 će se granati u dvije grane gdje će varijabla dobiti vrijednosti 0 i 1. Dakle, svaki dodatak nove jednadžbe, s obzirom na njenu specifičnost, dodaje jedno rješenje. Izvorna prva jednadžba:

ima 6 rješenja. Evo kako izgleda kompletno stablo odlučivanja za ovu jednadžbu:

Druga jednadžba našeg sustava slična je prvoj:

Jedina razlika je u tome što jednadžba koristi varijable Y. Ova jednadžba također ima 6 rješenja. Budući da se svako varijabilno rješenje može kombinirati sa svakim varijabilnim rješenjem, ukupan broj rješenja je 36.

Napominjemo da konstruirano stablo odlučivanja ne daje samo broj rješenja (prema broju grana), već i sama rješenja zapisana na svakoj grani stabla.

Problem 19

Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 postoji koji zadovoljavaju sve dolje navedene uvjete?

Ovaj zadatak je modifikacija prethodnog zadatka. Razlika je u tome što se dodaje još jedna jednadžba koja povezuje varijable X i Y.

Iz jednadžbe slijedi da kada ima vrijednost 1 (postoji jedno takvo rješenje), onda ima vrijednost 1. Dakle, postoji jedan skup na kojem i ima vrijednosti 1. Kada je jednako 0, može imaju bilo koju vrijednost, i 0 i i 1. Prema tome, svaki skup s , jednakim 0, a ima 5 takvih skupova, odgovara svih 6 skupova s ​​varijablama Y. Dakle, ukupan broj rješenja je 31.

Problem 20

Rješenje: Sjećajući se osnovnih ekvivalencija, svoju jednadžbu pišemo kao:

Ciklički lanac implikacija znači da su varijable identične, pa je naša jednadžba ekvivalentna jednadžbi:

Ova jednadžba ima dva rješenja kada su sva 1 ili 0.

Problem 21

Koliko rješenja ima jednadžba:

Rješenje: Baš kao u problemu 20, prelazimo s cikličkih implikacija na identitete, prepisujući jednadžbu u obliku:

Izgradimo stablo odlučivanja za ovu jednadžbu:

Problem 22

Koliko rješenja ima sljedeći sustav jednadžbi?