Tema lekcije: Rješenje logičke jednačine
edukativni – proučavanje metoda za rješavanje logičkih jednačina, razvijanje vještina rješavanja logičkih jednačina i konstruiranja logičkog izraza pomoću tablice istinitosti;razvojni - stvaraju uslove za razvoj kognitivnog interesovanja učenika, podstiču razvoj pamćenja, pažnje, logičko razmišljanje;
Obrazovni : promovirati sposobnost slušanja mišljenja drugih, negovanje volje i upornosti za postizanje konačnih rezultata.
Vrsta lekcije: kombinovana lekcija
Oprema: kompjuter, multimedijalni projektor, prezentacija 6.
Tokom nastave
Ponavljanje i ažuriranje osnovnih znanja. Ispitivanje zadaća(10 minuta)
U prethodnim lekcijama smo se upoznali sa osnovnim zakonima logičke algebre i naučili da koristimo te zakone za pojednostavljenje logičkih izraza.
Provjerimo našu domaću zadaću o pojednostavljivanju logičkih izraza:
1. Koja od sljedećih riječi zadovoljava logički uslov:
(suglasnik prvog slova→ suglasnik drugog slova)٨ (samoglasnik zadnjeg slova → samoglasnik pretposljednjeg slova)? Ako postoji nekoliko takvih riječi, navedite najmanju od njih.
1) ANA 2) MARIJA 3) OLEG 4) STEPAN
Hajde da uvedemo sljedeću notaciju:
A – suglasnik prvog slova
B – suglasnik drugog slova
S – samoglasnik posljednjeg slova
D – pretposljednje samoglasno slovo
Hajde da napravimo izraz:
Napravimo tabelu:
2. Navedite koji je logički izraz ekvivalentan izrazu
Pojednostavimo snimanje originalnog izraza i predloženih opcija:
3. Dat je fragment tablice istinitosti izraza F:
Koji izraz odgovara F?
Odredimo vrijednosti ovih izraza za navedene vrijednosti argumenata:
Upoznavanje sa temom časa, predstavljanje novog gradiva (30 minuta)
Nastavljamo s učenjem osnova logike, a tema naše današnje lekcije je “Rješavanje logičkih jednačina”. Proučivši ovu temu, naučit ćete osnovne metode rješavanja logičkih jednačina, steći vještine rješavanja ovih jednačina koristeći jezik logičke algebre i sposobnost sastavljanja logičkog izraza pomoću tablice istinitosti.
1. Riješite logičku jednačinu
(¬K M) → (¬L M N) =0
Napišite svoj odgovor kao niz od četiri znaka: vrijednosti varijabli K, L, M i N (tim redoslijedom). Tako, na primjer, red 1101 odgovara činjenici da je K=1, L=1, M=0, N=1.
Rješenje:
Hajde da transformišemo izraz(¬K M) → (¬L M N)
Izraz je netačan kada su oba izraza lažna. Drugi član je jednak 0 ako je M =0, N =0, L =1. U prvom članu K = 0, pošto je M = 0, i 
.
Odgovor: 0100
2. Koliko rješenja ima jednačina (navedite samo broj u svom odgovoru)?
Rješenje: transformirajte izraz
(A +B )*(C +D )=1
A +B =1 i C +D =1
Metoda 2: sastavljanje tabele istinitosti
3 way: konstrukcija SDNF - savršena disjunktivna normalna forma za funkciju - disjunkcija kompletnih regularnih elementarnih konjunkcija.Transformirajmo originalni izraz, otvorimo zagrade da bismo dobili disjunkciju veznika:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Dopunimo veznike u potpune veznike (proizvod svih argumenata), otvorimo zagrade:
Uzmimo u obzir iste veznike:
Kao rezultat, dobijamo SDNF koji sadrži 9 konjunkcija. Prema tome, tabela istinitosti za ovu funkciju ima vrijednost 1 u 9 redova od 2 4 =16 skupova vrijednosti varijabli.
3. Koliko rješenja ima jednačina (navedite samo broj u svom odgovoru)?
Hajde da pojednostavimo izraz:
,
3 way: izgradnja SDNF
Uzmimo u obzir iste veznike:
Kao rezultat, dobijamo SDNF koji sadrži 5 konjunkcija. Dakle, tabela istinitosti za ovu funkciju ima vrijednost 1 na 5 redova od 2 4 =16 skupova vrijednosti varijabli.
Konstruiranje logičkog izraza pomoću tablice istinitosti:
za svaki red tabele istinitosti koji sadrži 1, sastavljamo proizvod argumenata, a varijable jednake 0 su uključene u proizvod sa negacijom, a varijable jednake 1 su uključene bez negacije. Željeni izraz F će biti sastavljen od zbira rezultirajućih proizvoda. Zatim, ako je moguće, ovaj izraz treba pojednostaviti.
Primjer: data je tabela istinitosti izraza. Konstruirajte logički izraz.
Rješenje:3. Domaći (5 minuta)
Riješite jednačinu:
Koliko rješenja ima jednačina (navedite samo broj u svom odgovoru)?
Koristeći datu tablicu istinitosti, konstruirajte logički izraz i
pojednostavite ga.
Metode rješavanja sistema logičkih jednačina
Kirgizova E.V., Nemkova A.E.
Lesosibirski pedagoški institut -
ogranak Sibirskog federalnog univerziteta, Rusija
Sposobnost dosljednog razmišljanja, uvjerljivog rasuđivanja, izgradnje hipoteza i pobijanja negativnih zaključaka ne dolazi sama od sebe; ovu vještinu razvija nauka logike. Logika je nauka koja proučava metode za utvrđivanje istinitosti ili neistinitosti nekih iskaza na osnovu istinitosti ili netačnosti drugih iskaza.
Ovladavanje osnovama ove nauke nemoguće je bez rješavanja logičkih problema. Provjera razvoja vještina primjene znanja u novoj situaciji provodi se polaganjem. Konkretno, to je sposobnost odlučivanja logički problemi. Zadaci B15 na Jedinstvenom državnom ispitu su zadaci povećane složenosti, jer sadrže sisteme logičkih jednačina. Postoje različiti načini za rješavanje sistema logičkih jednačina. To je svođenje na jednu jednačinu, konstrukcija tablice istinitosti, dekompozicija, sekvencijalno rješavanje jednačina, itd.
zadatak:Riješite sistem logičkih jednačina:
Hajde da razmotrimo metoda redukcije na jednu jednačinu . Ova metoda uključuje transformaciju logičkih jednačina tako da njihove desne strane budu jednake istinitoj vrijednosti (tj. 1). Da biste to učinili, koristite operaciju logičke negacije. Zatim, ako jednačine sadrže složene logičke operacije, zamjenjujemo ih osnovnim: “I”, “ILI”, “NE”. Sljedeći korak je kombiniranje jednačina u jednu, ekvivalentnu sistemu, koristeći logičku operaciju “AND”. Nakon toga, trebalo bi transformisati rezultirajuću jednačinu na osnovu zakona logičke algebre i dobiti specifično rješenje za sistem.
Rješenje 1:Primijenite inverziju na obje strane prve jednadžbe:
Zamislimo implikaciju kroz osnovne operacije “ILI” i “NE”:
Pošto su leve strane jednadžbe jednake 1, možemo ih kombinovati pomoću operacije „I“ u jednu jednačinu koja je ekvivalentna originalnom sistemu:
Otvaramo prvu zagradu prema De Morganovom zakonu i transformiramo dobijeni rezultat:
Rezultirajuća jednačina ima jedno rješenje: A= 0, B =0 i C =1.
Sljedeća metoda je konstruisanje tabela istinitosti . Budući da logičke veličine imaju samo dvije vrijednosti, možete jednostavno proći kroz sve opcije i među njima pronaći one za koje ovaj sistem jednačine. Odnosno, gradimo jednu zajedničku tabelu istinitosti za sve jednačine sistema i nalazimo liniju sa traženim vrednostima.
Rješenje 2:Kreirajmo tabelu istinitosti za sistem:
|
0 |
0 |
1 |
1 |
0 |
1 |
Podebljana je linija za koju su ispunjeni uslovi zadatka. Dakle, A =0, B =0 i C =1.
Way raspadanje . Ideja je da se fiksira vrijednost jedne od varijabli (da bude jednaka 0 ili 1) i da se na taj način pojednostave jednačine. Zatim možete popraviti vrijednost druge varijable i tako dalje.
Rješenje 3: Neka A = 0, tada:
Iz prve jednačine dobijamo B =0, a od drugog – C=1. Rješenje sistema: A = 0, B = 0 i C = 1.
Također možete koristiti metodu sekvencijalno rješavanje jednačina , u svakom koraku dodajući jednu varijablu skupu koji se razmatra. Da biste to učinili, potrebno je transformirati jednačine tako da se varijable unose abecednim redom. Zatim gradimo stablo odlučivanja, uzastopno mu dodajući varijable.
Prva jednačina sistema zavisi samo od A i B, a druga od A i C. Varijabla A može imati 2 vrijednosti 0 i 1:
Iz prve jednačine slijedi da 
, Dakle, kada A = 0 i dobijamo B = 0, a za A = 1 imamo B = 1. Dakle, prva jednadžba ima dva rješenja u odnosu na varijable A i B.
Opišimo drugu jednadžbu iz koje određujemo vrijednosti C za svaku opciju. Kada je A =1, implikacija ne može biti netačna, to jest, druga grana stabla nema rješenja. At A= 0
dobijamo jedino rešenje C= 1
:
Tako smo dobili rješenje sistema: A = 0, B = 0 i C = 1.
Na Jedinstvenom državnom ispitu iz informatike vrlo je često potrebno odrediti broj rješenja sistema logičkih jednačina, a da se sama rješenja ne pronađu, a za to postoje i određene metode. Glavni način da se pronađe broj rješenja sistema logičkih jednačina je zamjena varijabli. Prvo, trebate pojednostaviti svaku od jednadžbi što je više moguće na osnovu zakona logičke algebre, a zatim zamijeniti složene dijelove jednadžbi novim varijablama i odrediti broj rješenja novi sistem. Zatim se vratite na zamjenu i odredite broj rješenja za nju.
zadatak:Koliko rješenja ima jednačina ( A → B ) + (C → D ) = 1? Gdje su A, B, C, D logičke varijable.
Rješenje:Hajde da predstavimo nove varijable: X = A → B i Y = C → D . Uzimajući u obzir nove varijable, jednačina će biti napisana kao: X + Y = 1.
Disjunkcija je tačna u tri slučaja: (0;1), (1;0) i (1;1), dok X i Y je implikacija, odnosno tačna je u tri slučaja i lažna u jednom. Stoga će slučaj (0;1) odgovarati trima mogućim kombinacijama parametara. Slučaj (1;1) – odgovaraće devet mogućih kombinacija parametara originalne jednačine. To znači da su ukupna moguća rješenja ove jednačine 3+9=15.
Sljedeći način za određivanje broja rješenja sistema logičkih jednačina je binarno stablo. Hajde da razmotrimo ovu metodu Na primjer.
zadatak:Koliko različitih rješenja ima sistem logičkih jednačina:
Dati sistem jednačina je ekvivalentan jednačini:
( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.
Pretvarajmo se tox 1 – tačno, onda iz prve jednačine dobijamo tox 2 takođe tačno, od drugog -x 3 =1, i tako dalje do x m= 1. Dakle, skup (1; 1; …; 1) od m jedinica je rješenje sistema. Pusti to sadax 1 =0, onda iz prve jednačine koju imamox 2 =0 ili x 2 =1.
Kada x 2 tačno, dobijamo da su i preostale varijable tačne, odnosno da je skup (0; 1; ...; 1) rešenje sistema. Atx 2 =0 dobijamo to x 3 =0 ili x 3 =, i tako dalje. Nastavljajući na posljednju varijablu, nalazimo da su rješenja jednadžbe sljedeći skupovi varijabli ( m +1 rješenje, u svakom rješenju m varijabilne vrijednosti):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Ovaj pristup je dobro ilustrovan konstruisanjem binarnog stabla. Broj mogućih rješenja je broj različitih grana izgrađenog stabla. Lako je vidjeti da je jednaka m +1.
|
Varijable |
Drvo |
Broj rješenja |
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
U slučaju poteškoća u zaključivanju i izgradnji stabla odlučivanja, rješenje možete potražiti koristeći tabele istine, za jednu ili dvije jednačine.
Prepišimo sistem jednačina u obliku:
I napravimo tabelu istinitosti odvojeno za jednu jednačinu:
|
x 1 |
x 2 |
(x 1 → x 2) |
Kreirajmo tabelu istinitosti za dvije jednačine:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Dalje, možete vidjeti da je jedna jednačina istinita u sljedeća tri slučaja: (0; 0), (0; 1), (1; 1). Sistem od dvije jednačine je istinit u četiri slučaja (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). U ovom slučaju, odmah je jasno da postoji rješenje koje se sastoji samo od nula i više m rješenja u kojima se dodaje po jedna jedinica, počevši od posljednje pozicije dok se ne popune sva moguća mjesta. Može se pretpostaviti da zajednička odlukaće imati isti oblik, ali da bi ovaj pristup postao rješenje, potreban je dokaz da je pretpostavka tačna.
Da sumiramo sve gore navedeno, želio bih da vam skrenem pažnju na činjenicu da nisu sve metode o kojima se raspravljalo univerzalne. Prilikom rješavanja svakog sistema logičkih jednačina treba voditi računa o njegovim karakteristikama, na osnovu kojih treba izabrati metodu rješenja.
književnost:
1. Logički problemi / O.B. Bogomolov – 2. izd. – M.: BINOM. Laboratorij znanja, 2006. – 271 str.: ilustr.
2. Polyakov K.Yu. Sistemi logičkih jednačina / Obrazovno-metodički list za nastavnike informatike: Informatika br. 14, 2011.
Metode rješavanja sistema logičkih jednačina
Možete riješiti sistem logičkih jednačina, na primjer, koristeći tablicu istinitosti (ako broj varijabli nije prevelik) ili koristeći stablo odlučivanja, nakon što ste prvo pojednostavili svaku jednačinu.
1. Metoda zamjene varijable.
Uvođenje novih varijabli omogućava vam da pojednostavite sistem jednačina, smanjujući broj nepoznatih.Nove varijable moraju biti nezavisne jedna od druge. Nakon rješavanja pojednostavljenog sistema, moramo se vratiti na originalne 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
Rješenje:
Hajde da uvedemo 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 varijable A, B, C, D, E, tj. nove varijable su nezavisne jedna od druge).
Tada će sistem jednačina izgledati ovako:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Napravimo stablo odlučivanja za rezultirajući sistem:
Razmotrimo jednačinu A=0, tj. (X1≡ X2)=0. Ima 2 korena:
X1 ≡ X2 |
||
Iz iste tabele može se vidjeti da jednačina A=1 također ima 2 korijena. Uredimo broj korijena na stablu odlučivanja:
Da biste pronašli broj rješenja jedne grane, trebate pomnožiti broj rješenja na svakom nivou. Lijeva grana ima 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 rješenja; desna grana takođe ima 32 rješenja. One. cijeli sistem ima 32+32=64 rješenja.
Odgovor: 64.
2. Metoda zaključivanja.
Teškoća rješavanja sistema logičkih jednačina leži u glomaznosti kompletnog stabla odlučivanja. Metoda rasuđivanja vam omogućava da ne izgradite cijelo stablo, već da shvatite koliko će grana imati. Pogledajmo ovu metodu koristeći konkretne primjere.
Primjer 1. Koliko ima različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 koji zadovoljavaju sve dolje navedene uslove?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
U odgovoru nije potrebno navesti sve različite skupove vrijednosti varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 za koje je ovaj sistem jednakosti zadovoljen. Kao odgovor, potrebno je navesti broj takvih setova.
Rješenje:
Prva i druga jednadžba sadrže nezavisne varijable koje su povezane trećim uslovom. Napravimo stablo rješenja prve i druge jednačine.
Da bi se predstavilo stablo rješenja za sistem prve i druge jednačine, svaka grana prvog stabla mora biti nastavljena stablom za varijable at . Ovako konstruirano stablo će sadržavati 36 grana. Neke od ovih grana ne zadovoljavaju treću jednačinu sistema. Označimo broj grana drveta na prvom stablu"y" , koji zadovoljavaju treću jednačinu:
Hajde da objasnimo: da bi se zadovoljio treći uslov, kada je x1=0 mora postojati y1=1, tj. sve grane stabla"X" , gdje se x1=0 može nastaviti sa samo jednom granom od stabla"y" . I to samo za jednu granu drveta"X" (desno) sve grane drveta odgovaraju"y". Dakle, kompletno stablo cijelog sistema sadrži 11 grana. Svaka grana predstavlja jedno rješenje originalnog sistema jednačina. To znači da cijeli sistem ima 11 rješenja.
Odgovor: 11.
Primjer 2. Koliko razna rješenja ima sistem jednačina
(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 vrijedi ova jednakost. Kao odgovor, potrebno je navesti broj takvih setova.
Rješenje: Hajde da pojednostavimo sistem. Napravimo tabelu istinitosti za dio prve jednačine:
X1 ∧ X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Obratite pažnju na posljednju kolonu, ona odgovara rezultatu akcije X1 ≡ X10.
X1 ≡ X10 |
Nakon pojednostavljenja dobijamo:
(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 jednačinu:(X1 ≡ X10) = 0, tj. x1 ne bi trebalo da se podudara sa x10. Da bi prva jednadžba bila jednaka 1, jednakost mora biti tačna(X1 ≡ X2)=1, tj. x1 mora odgovarati x2.
Napravimo stablo rješenja za prvu jednačinu:
Razmotrimo drugu jednačinu: za x10=1 i za x2=0 zagradamora biti jednako 1 (tj. x2 se poklapa sa x3); za x10=0 i za x2=1 zagrada(X2 ≡ X10)=0, što znači zagrada (X2 ≡ X3) treba biti jednako 1 (tj. x2 se poklapa sa x3):
Rezonirajući na ovaj način, gradimo stablo rješenja za sve jednačine:
Dakle, sistem jednačina 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 uslove?
(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
Rješenje:
Napravimo stablo rješenja za prvu jednačinu:
Razmotrimo drugu jednačinu:
- Kada je x1=0 : druga i treća zagrada će biti 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; sekunda 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 i za preostale jednačine. Zabilježimo rezultirajući broj rješenja za svaki čvor stabla:
Da biste saznali broj rješenja za svaku granu, pomnožite rezultirajuće brojeve posebno za svaku granu (s lijeva 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 rezultirajuće brojeve: ima ukupno 31 rješenje.
Odgovor: 31.
3. Prirodni porast broja korijena
U nekim sistemima, broj korena sledeće jednačine zavisi od broja korena prethodne jednačine.
Primjer 1. Koliko ima različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 koji zadovoljavaju sve dolje navedene uslove?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Hajde da pojednostavimo prva jednadžba:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Tada će sistem poprimiti oblik:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
itd.
Svaka sljedeća jednačina ima 2 korijena više od prethodne.
4 jednadžba ima 12 korijena;
Jednačina 5 ima 14 korijena
Jednačina 8 ima 20 korijena.
Odgovor: 20 korijena.
Ponekad broj korijena raste prema Fibonaccijevom zakonu.
Rješavanje sistema logičkih jednačina zahtijeva kreativan pristup.
Upotreba jednačina je široko rasprostranjena u našim životima. Koriste se u mnogim proračunima, izgradnji objekata, pa čak i u sportu. Čovjek je koristio jednačine u drevnim vremenima, a od tada se njihova upotreba samo povećava. U matematici postoje određeni problemi koji se bave propozicionom logikom. Riješiti ove vrste jednadžbi, potrebno je imati određenu količinu znanja: poznavanje zakona propozicione logike, poznavanje tablica istinitosti logičkih funkcija 1 ili 2 varijable, metode za pretvaranje logičkih izraza. Osim toga, morate znati sljedeća svojstva logičke operacije: konjunkcije, disjunkcije, inverzije, implikacije i ekvivalencije.
Bilo koja logička funkcija \varijable - \može biti specificirana tablicom istinitosti.
Riješimo nekoliko logičkih jednačina:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Počnimo rješenje sa \[X1\] i odredimo koje vrijednosti ova varijabla može imati: 0 i 1. Zatim ćemo razmotriti svaku od gore navedenih vrijednosti i vidjeti šta \[X2.\] može biti.
Kao što se može vidjeti iz tabele, naša logička jednačina ima 11 rješenja.
Gdje mogu riješiti logičku jednačinu na mreži?
Jednačinu možete riješiti na našoj web stranici https://site. Besplatni online rješavač će vam omogućiti da riješite online jednadžbe bilo koje složenosti za nekoliko sekundi. Sve što trebate učiniti je jednostavno unijeti svoje podatke u rješavač. Također možete pogledati video upute i naučiti kako riješiti jednadžbu na našoj web stranici. A ako i dalje imate pitanja, možete ih postaviti u našoj VKontakte grupi http://vk.com/pocketteacher. Pridružite se našoj grupi, mi ćemo vam uvijek rado pomoći.
Neka je logička funkcija od n varijabli. Logička jednačina izgleda ovako:
Konstanta C ima vrijednost 1 ili 0.
Logička jednačina može imati od 0 do različitih rješenja. Ako je C jednako 1, tada su rješenja svi oni skupovi varijabli iz tablice istinitosti za koje funkcija F uzima vrijednost true (1). Preostali skupovi su rješenja jednadžbe sa C jednakim nuli. Uvijek možete uzeti u obzir samo jednačine oblika:
Zaista, neka je data jednačina:
U ovom slučaju možemo ići na ekvivalentnu jednačinu:
Razmotrimo sistem od k logičkih jednačina:
Rješenje sistema je skup varijabli na kojima su zadovoljene sve jednačine sistema. U smislu logičkih funkcija, da bi se dobilo rješenje za sistem logičkih jednadžbi, treba pronaći skup na kojem je tačna logička funkcija F, koja predstavlja konjunkciju originalnih funkcija:
Ako je broj varijabli mali, na primjer, manji od 5, onda nije teško konstruirati tabelu istinitosti za funkciju, koja nam omogućava da kažemo koliko rješenja ima sistem i koji su skupovi koji daju rješenja.
U nekim USE problemima o pronalaženju rješenja za sistem logičkih jednačina, broj varijabli dostiže 10. Tada konstruiranje tablice istinitosti postaje gotovo nemoguć zadatak. Rješavanje problema zahtijeva drugačiji pristup. Za proizvoljan sistem jednačina ne postoji opšta metoda osim nabrajanja koja omogućava rešavanje takvih problema.
U zadacima predloženim na ispitu rješenje se obično zasniva na uzimanju u obzir specifičnosti sistema jednačina. Ponavljam, osim isprobavanja svih opcija za skup varijabli, ne postoji opći način rješavanja problema. Rješenje mora biti izgrađeno na osnovu specifičnosti sistema. Često je korisno izvršiti preliminarno pojednostavljenje sistema jednačina koristeći poznate zakone 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 konstruiranja pun sto Istina, izgradićemo njegov analog - binarno stablo odlučivanja. Svaka grana ovog stabla odgovara jednom rješenju i specificira skup na kojem funkcija ima vrijednost 1. Broj grana u stablu odlučivanja poklapa se sa brojem rješenja sistema jednačina.
Objasniću šta je binarno stablo odlučivanja i kako se gradi koristeći primere nekoliko problema.
Problem 18
Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 zadovoljavaju sistem od dvije jednačine?
Odgovor: Sistem ima 36 različitih rješenja.
Rješenje: Sistem jednačina uključuje dvije jednačine. Nađimo broj rješenja za prvu jednačinu, ovisno o 5 varijabli - . Prva jednačina se može posmatrati kao sistem od 5 jednačina. Kao što je pokazano, sistem jednačina zapravo predstavlja konjunkciju logičkih funkcija. Tačna je i obrnuta tvrdnja – konjunkcija uslova se može smatrati sistemom jednačina.
Napravimo stablo odlučivanja za implikaciju () - prvi član konjunkcije, koji se može smatrati prvom jednačinom. Ovako to izgleda grafička slika ovo drvo
Stablo se sastoji od dva nivoa prema broju varijable jednačine. Prvi nivo opisuje prvu varijablu. Dvije grane ovog nivoa odražavaju moguće vrijednosti ove varijable - 1 i 0. Na drugom nivou, grane stabla odražavaju samo one moguće vrijednosti varijable za koje jednačina procjenjuje istinito. Pošto jednačina specificira implikaciju, grana na kojoj ima vrijednost 1 zahtijeva da na ovoj grani postoji vrijednost 1. Grana na kojoj ima vrijednost 0 generiše dvije grane sa vrijednostima jednakim 0 i 1. Konstruirana stablo specificira tri rješenja, od kojih implikacija poprima vrijednost 1. Na svakoj grani se ispisuje odgovarajući skup vrijednosti varijabli, što daje rješenje jednadžbe.
Ovi skupovi su: ((1, 1), (0, 1), (0, 0))
Nastavimo graditi stablo odlučivanja dodavanjem sljedeće jednačine, sljedeće implikacije. Specifičnost našeg sistema jednačina je da svaka nova jednačina sistema koristi jednu varijablu iz prethodne jednačine, dodajući jednu novu varijablu. Pošto varijabla već ima vrijednosti u stablu, onda će na svim granama gdje varijabla ima vrijednost 1, varijabla također imati vrijednost 1. Za takve grane, konstrukcija stabla se nastavlja na sljedeći nivo, ali se nove grane ne pojavljuju. Jedna grana u kojoj varijabla ima vrijednost 0 granaće se 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. Prvobitna prva jednačina:
ima 6 rješenja. Evo kako izgleda kompletno stablo odlučivanja za ovu jednačinu:
Druga jednačina našeg sistema je slična prvoj:
Jedina razlika je u tome što jednačina koristi varijable Y. Ova jednačina također ima 6 rješenja. Pošto se svako varijabilno rješenje može kombinirati sa svakim varijabilnim rješenjem, ukupan broj rješenja je 36.
Imajte na umu da konstruirano stablo odlučivanja daje ne samo broj rješenja (prema broju grana), već i sama rješenja zapisana na svakoj grani stabla.
Problem 19
Koliko ima različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 koji zadovoljavaju sve dolje navedene uslove?
Ovaj zadatak je modifikacija prethodnog zadatka. Razlika je u tome što se dodaje još jedna jednačina koja povezuje varijable X i Y.
Iz jednadžbe slijedi da kada ima vrijednost 1 (jedno takvo rješenje postoji), onda ima vrijednost 1. Dakle, postoji jedan skup na kojem i imaju vrijednosti 1. Kada je jednako 0, može imaju bilo koju vrijednost, i 0 i i 1. Dakle, svaki skup sa , jednak 0, a ima 5 takvih skupova, odgovara svih 6 skupova sa varijablama Y. Dakle, ukupan broj rješenja je 31.
Problem 20
Rješenje: Prisjećajući se osnovnih ekvivalencija, zapisujemo našu jednačinu kao:
Ciklični lanac implikacija znači da su varijable identične, tako da je naša jednadžba ekvivalentna jednadžbi:
Ova jednadžba ima dva rješenja kada su sve 1 ili 0.
Problem 21
Koliko rješenja ima jednačina:
Rješenje: Baš kao u zadatku 20, prelazimo s cikličkih implikacija na identitete, prepisujemo jednačinu u obliku:
Napravimo stablo odlučivanja za ovu jednačinu:
Problem 22
Koliko rješenja ima sljedeći sistem jednačina?
