Šta je logička jednačina. Metode rješavanja sistema logičkih jednačina

Metode rješavanja sistema logičke jednačine

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 se ovaj sistem jednaki 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 odlučivanja 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.

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

Lekcija #3. Logika. Logičke funkcije. Rješavanje jednačina

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

1. Komutativnost disjunkcije i konjunkcije:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distributivno pravo vezano za disjunkciju i konjunkciju:
   a ˅ (b^s) ≡ (a ˅ b) ^(a ˅ s)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negacija negacije:
   ¬(¬a) ≡ a
4. dosljednost:
   a ^ ¬a ≡ netačno
5. Ekskluzivno treće:
   a ˅ ¬a ≡ tačno
6. De Morganovi zakoni:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Pojednostavljenje:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ istina ≡ a
   a ˄ false ≡ false
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 biti specificirana tablicom istinitosti. Takva tabela sadrži 2n skupova varijabli, za svaku od kojih je specificirana vrijednost funkcije na ovom skupu. Ova metoda je dobra kada je broj varijabli relativno mali. Već za n > 5 reprezentacija postaje slabo vidljiva.

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

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

Zapravo, sistem od dvije funkcije – negacije i konjunkcije ili negacije i disjunkcije – također je potpun. Iz De Morganovih zakona slijede ideje koje omogućavaju izražavanje konjunkcije kroz negaciju i disjunkciju i, shodno tome, izražavanje disjunkcije kroz negaciju i konjunkciju:

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

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

Osnovne funkcije programskih jezika obično uključuju identitet, negaciju, konjunkciju i disjunkciju. IN Problemi objedinjenog državnog ispita Zajedno s ovim funkcijama često se nalazi implikacija.

Pogledajmo nekoliko jednostavni zadaci vezano za logičke funkcije.

Problem 15:

Dat je fragment tabele istine. Koja od tri date funkcije odgovara ovom fragmentu?

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

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funkcija broj 3.

Da biste riješili problem, morate znati tablice istinitosti osnovnih funkcija i zapamtiti prioritete operacija. Da vas podsjetim da konjunkcija (logičko množenje) ima veći prioritet i da se izvršava ranije od disjunkcije (logičko sabiranje). Prilikom izračunavanja lako je uočiti da funkcije sa brojevima 1 i 2 u trećem skupu imaju vrijednost 1 i iz tog razloga ne odgovaraju fragmentu.

Problem 16:

Koji od datih brojeva zadovoljava uslov:

(cifre, počevši od najznačajnije cifre, su u opadajućem redoslijedu) → (broj - paran) ˄ (mala cifra - paran) ˄ (visoka cifra - neparan)

Ako postoji nekoliko takvih brojeva, navedite najveći.

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

Uslov je zadovoljen brojem 4.

Prva dva broja ne zadovoljavaju uslov iz razloga što je najniža cifra neparna. Konjunkcija uslova je netačna ako je jedan od uslova konjunkcije netačan. Za treći broj nije ispunjen uslov za najvišu cifru. Za četvrti broj ispunjeni su uslovi koji se postavljaju za niske i visoke cifre broja. Prvi član konjunkcije je takođe tačan, jer je implikacija tačna ako je njena premisa netačna, što je ovde slučaj.

Problem 17: Dva svjedoka su dala 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 jedan od preostalih je svakako kriv i kriv, ali ne mogu reći ko tačno.

Koji se zaključci o krivici A, B i C mogu izvući iz svjedočenja?

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

Rješenje: Naravno, odgovor se može dati na osnovu zdrav razum. Ali pogledajmo kako se to može učiniti strogo i formalno.

Prva stvar koju treba učiniti je formalizirati izjave. Hajde da uvedemo tri logičke varijable - A, B i C, od kojih svaka ima vrijednost true (1) ako je odgovarajući osumnjičeni kriv. Tada se iskaz prvog svjedoka daje formulom:

A → (B ˄ ¬C)

Iskaz drugog svjedoka je dat formulom:

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

Pretpostavlja se da je iskaz oba svjedoka istinit i predstavlja spoj odgovarajućih formula.

Hajde da napravimo tabelu istinitosti za ova čitanja:

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

Sumarni 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 tabele takođe proizilazi da je iskaz drugog svjedoka informativniji. Iz istinitosti njegovog svjedočenja proizilaze samo dvije stvari: 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 krivici osumnjičenih.

Logičke jednačine i sistemi jednačina

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

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

Konstanta C ima vrijednost 1 ili 0.

Logička jednačina može imati od 0 do 2 n 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:

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

Zaista, neka je data jednačina:

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

U ovom slučaju možemo ići na ekvivalentnu jednačinu:

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

Razmotrimo sistem od k logičkih jednačina:

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

F = F 1 ˄ F 2 ˄ … F k

Ako je broj varijabli mali, na primjer, manji od 5, onda nije teško konstruirati tabelu istinitosti za funkciju F, 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 F 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 u zavisnosti od 5 varijabli - x 1, x 2, ...x 5. 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. I obrnuto: konjunkcija uslova se može smatrati sistemom jednačina.

Napravimo stablo odlučivanja za implikaciju (x1→ x2) - 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 X 1 . 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 X 2 za koje je jednačina istinita. Budući da jednačina specificira 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 sa vrijednostima X 2 jednako 0 i 1 Konstruirano stablo definiše tri rješenja, na kojima implikacija X 1 → X 2 poprima vrijednost 1. Na svakoj grani je ispisan odgovarajući skup varijabilnih vrijednosti, što daje rješenje jednačine.

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

Nastavimo graditi stablo odlučivanja dodavanjem sljedeće jednačine, sljedeće implikacije X 2 → X 3 . 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 X 2 već ima vrijednosti u stablu, onda ć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ći nivo, ali se nove grane ne pojavljuju. Jedna grana u kojoj varijabla X 2 ima vrijednost 0 granaće se u dvije grane gdje će varijabla X 3 dobiti vrijednosti 0 i 1. Dakle, svaki dodatak nove jednadžbe, s obzirom na njene specifičnosti, dodaje jedno rješenje. Prvobitna prva jednačina:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
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:

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

Jedina razlika je u tome što jednačina koristi varijable Y. Ova jednačina također ima 6 rješenja. Pošto 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.

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?

(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 jednačina koja povezuje varijable X i Y.

Iz jednačine X 1 → Y 1 slijedi da kada X 1 ima vrijednost 1 (jedno takvo rješenje postoji), onda 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. Dakle, svaki skup sa X 1 jednak 0, a postoji 5 takvih skupova, odgovara svih 6 skupova sa 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: Prisjećajući se osnovnih ekvivalencija, zapisujemo našu jednačinu kao:

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

Ciklični lanac implikacija znači da su varijable identične, tako da 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 ili 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 zadatku 20, prelazimo s cikličkih implikacija na identitete, prepisujemo jednačinu u obliku:

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

Napravimo stablo odlučivanja za ovu jednačinu:

Problem 22

Koliko rješenja ima sljedeći sistem jednačina?

((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: Pređimo sa 10 varijabli na 5 varijabli uvođenjem sljedeće promjene 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 jednačina poprimiti oblik:

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

Jednačina se može pojednostaviti pisanjem na sledeći način:

(Y 1 ≡ Y 2) = 0

Prelazimo na tradicionalnom obliku, pišemo sistem 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 sistem je jednostavno i sastoji se od dvije grane sa naizmjeničnim vrijednostima varijabli:

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

Kao što vidite, svaki problem rješavanja sistema jednačina zahtijeva vlastiti pristup. Uobičajena tehnika je izvođenje ekvivalentnih transformacija radi pojednostavljenja jednačina. Uobičajena tehnika je izgradnja stabala odluka. Korišteni pristup djelomično podsjeća na konstruiranje tablice istinitosti s posebnošću da se ne konstruiraju svi skupovi mogućih vrijednosti varijabli, već samo oni na kojima funkcija uzima vrijednost 1 (true). Često u predloženim problemima nema potrebe da se gradi kompletno stablo odlučivanja, jer već početna faza moguće je uspostaviti obrazac pojavljivanja novih grana na svakom sljedećem nivou, kao što je učinjeno, na primjer, u zadatku 18.

Generalno, problemi koji uključuju pronalaženje rješenja za sistem logičkih jednačina su dobre matematičke vježbe.

Ako je problem teško riješiti ručno, onda rješenje možete povjeriti računaru tako što ćete napisati odgovarajući program za rješavanje jednačina i sistema jednačina.

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

Čudno je da je zadatak pronalaženja rješenja sistema logičkih jednačina težak za kompjuter, a ispostavilo se da kompjuter ima svoja ograničenja. Računar se prilično lako nosi sa 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 specificira broj skupova, eksponencijalna koja brzo raste kako n raste. Toliko brzo da običan personalni računar ne može da se nosi sa zadatkom koji ima 40 varijabli u jednom danu.

Program na jeziku C# za rješavanje logičkih jednačina

Pisanje programa za rješavanje logičkih jednadžbi korisno je iz mnogo razloga, makar samo zato što ga možete koristiti za provjeru ispravnosti vlastitog rješenja za ispitne probleme objedinjenog državnog ispita. Drugi razlog je taj što je takav program odličan primjer zadatka programiranja koji ispunjava zahtjeve za zadatke kategorije C na Jedinstvenom državnom ispitu.

Ideja izgradnje programa je jednostavna - zasniva se na potpunom pretraživanju svih mogućih skupova varijabilnih vrijednosti. Pošto je za datu logičku jednačinu ili sistem jednačina poznat broj varijabli n, tada je poznat i broj skupova - 2 n koje treba razvrstati. Koristeći osnovne funkcije jezika C# - negaciju, disjunkciju, konjunkciju i identitet, nije teško napisati program koji za dati skup varijabli izračunava vrijednost logičke funkcije koja odgovara logičkoj jednadžbi ili sistemu jednačina .

U takvom programu morate izgraditi petlju na osnovu broja skupova, u tijelu petlje, koristeći broj skupa, formirati sam skup, izračunati vrijednost funkcije na ovom skupu, i ako je ovo vrijednost je 1, tada skup daje rješenje jednačine.

Jedina poteškoća koja se javlja prilikom implementacije programa odnosi se na zadatak generiranja samog skupa vrijednosti varijabli na osnovu broja skupa. Ljepota ovog problema je u tome što se ovaj naizgled težak zadatak zapravo svodi na jednostavan problem koji se već mnogo puta javljao. Zaista, dovoljno je razumjeti da skup vrijednosti varijabli koje odgovaraju broju i, koji se sastoji od nula i jedinica, predstavlja binarni prikaz broja i. Dakle težak zadatak dobijanje skupa varijabilnih vrijednosti po skupu broja svodi se na dobro poznati problem pretvaranja broja u binarni sistem.

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

///

/// program za brojanje rješenja

/// logička jednadžba (sistem jednadžbi)

///

///

/// logička funkcija - metoda,

/// čiji potpis specificira DF delegat

///

/// broj varijabli

/// broj rješenja

static int SolveEquations (DF zabava, int n)

bool set = novi bool[n];

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

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

//Završi pretragu po broju skupova

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

//Formacija sljedeći set- set

//specificirano binarnim prikazom 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 dovoljna. Fokusiraću se samo na objašnjenje naslova date funkcije. Funkcija SolveEquations ima dva ulazna parametra. Fun parametar specificira logičku funkciju koja odgovara jednadžbi ili sistemu jednačina koje se rješavaju. Parametar n specificira broj funkcijske varijable zabava. Kao rezultat, funkcija SolveEquations vraća broj rješenja logičke funkcije, odnosno broj onih skupova na kojima funkcija procjenjuje istinito.

Uobičajeno je za školarce kada 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 pripada funkcijama višeg reda– funkcije tipa F(f), čiji parametri mogu biti ne samo jednostavne varijable, već i funkcije.

Klasa funkcija koja se može proslijediti kao parametar funkciji SolveEquations specificirana je na sljedeći način:

delegate bool DF(bool vars);

Ova klasa posjeduje sve funkcije koje se prosljeđuju kao parametar skup vrijednosti logičkih varijabli specificiranih nizom vars. Rezultat je Boolean vrijednost koja predstavlja vrijednost funkcije na ovom skupu.

Konačno, evo programa koji koristi funkciju SolveEquations za rješavanje nekoliko sistema logičkih jednačina. Funkcija SolveEquations je dio klase ProgramCommon u nastavku:

class ProgramCommon

delegate bool DF(bool vars);

static void Main (args niza)

Console.WriteLine("I funkcije - " +

SolveEquations(FunAnd, 2));

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

SolveEquations(Fun51, 5));

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

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return 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)));

Evo kako izgledaju rezultati rješenja za ovaj program:

10 zadataka za samostalan rad

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

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

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 doneta ako za nju glasa predsednik žirija, uz podršku najmanje jednog od članova žirija. U suprotnom, odluka se ne donosi. Konstruirajte logičku funkciju koja formalizira proces donošenja odluka.
5. X pobjeđuje Y ako četiri bacanja novčića rezultiraju tri puta glavom. Definirajte logičku funkciju koja opisuje isplatu X.
6. Riječi u rečenici se numeriraju počevši od jedan. Smatra se da je rečenica ispravno izgrađena ako su ispunjena sljedeća pravila:
   1. Ako se parna riječ završava samoglasnikom, onda sljedeća riječ, ako postoji, mora početi samoglasnikom.
   2. Ako se neparna riječ završava suglasnikom, onda sljedeća riječ, ako postoji, mora početi sa suglasnikom i završiti samoglasnikom.
      Koje od sljedećih rečenica su ispravno konstruirane:
   3. Mama je oprala Mašu sapunom.
   4. Vođa je uvek model.
   5. Istina je dobra, ali sreća je bolja.
7. Koliko rješenja ima jednačina:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Navedite sva rješenja jednačine:
   (a → b) → c = 0
9. Koliko rješenja ima sljedeći sistem jednačina:
   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 jednačina:
    ((((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 uzme 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 uzme vrijednost 1 kada i-to bacanje novčića 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. Kazna b.
6. Jednačina ima 3 rješenja: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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 da gradimo kompletnu tablicu istinitosti, izgradićemo njen 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 izgleda grafički prikaz ovog stabla

Stablo se sastoji od dva nivoa prema broju varijabli u jednačini. 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 će imati i 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 (postoji jedno takvo rješenje), 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?

Tema lekcije: Rješavanje logičkih jednačina

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. Dakle, 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.

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. Da biste riješili ovakvu jednačinu, potrebno je imati određeno znanje: poznavanje zakona propozicionalne 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.