Noskin Andrej Nikolajevič,
IT-učitelj
najviša kvalifikaciona kategorija,
Kandidat vojnih nauka, vanredni profesor
GBOU Licej br. 1575, Moskva

Optimizovana metoda mapiranja za rešavanje problema 23 sa Jedinstvenog državnog ispita KIM iz računarstva i IKT

Jedan od najtežih zadataka na Jedinstvenom državnom ispitu KIM je zadatak 23, u kojem morate pronaći broj različitih skupova vrijednosti logičkih varijabli koji zadovoljavaju navedeni uvjet.
Ovaj zadatak je možda najteži zadatak KIM Jedinstvenog državnog ispita iz računarstva i IKT. Po pravilu, najviše 5% ispitanika se s tim nosi (1).
Tako mali procenat učenika koji su završili ovaj zadatak objašnjava se sledećim:
- učenici mogu pobrkati (zaboraviti) znakove logičkih operacija;
- matematičke greške u procesu izvođenja proračuna;
- greške u zaključivanju pri traženju rješenja;
- greške u procesu pojednostavljivanja logičkih izraza;
- nastavnici preporučuju rješavanje ovaj zadatak, nakon što je sav posao obavljen, pošto je vjerovatnoća pretpostavke
greške su veoma velike, a "težina" zadatka je samo jedna primarna tačka.
Osim toga, neki nastavnici i sami imaju poteškoća u rješavanju ove vrste problema i stoga pokušavaju riješiti jednostavnije probleme s djecom.
Situaciju komplikuje i to što u ovom bloku postoji veliki broj raznih zadataka i nemoguće je odabrati šablonsko rješenje.
Kako bi ispravila ovu situaciju, pedagoška zajednica finalizira dvije glavne metode za rješavanje problema ovog tipa: rješavanje korištenjem lanaca bitova (2) i metodom mapiranja (3).
Potreba za doradom (optimizacijom) ovih metoda je zbog činjenice da se zadaci stalno mijenjaju kako po strukturi tako i po broju varijabli (samo jedna vrsta varijabli X, dvije vrste varijabli X i Y, tri vrste: X, Y , Z).
Teškoću savladavanja ovih metoda za rješavanje problema potvrđuje činjenica da je na web stranici K.Yu. Poljakova postoji 38 analiza ove vrste problema (4). Neke analize pružaju više od jedne vrste rješenja za problem.
U poslednje vreme na KIM Jedinstvenom državnom ispitu iz računarstva postoje problemi sa dve vrste varijabli X i Y.
Optimizirao sam metod prikaza i ohrabrujem svoje učenike da koriste poboljšani metod.
Ovo daje rezultate. Procenat mojih učenika koji se nose sa ovim zadatkom varira do 43% onih koji prolaze. U pravilu svake godine od 25 do 33 osobe iz svih 11. razreda polažu Jedinstveni državni ispit iz informatike.
Prije pojave problema sa dvije vrste varijabli, učenici su vrlo uspješno koristili metodu mapiranja, ali nakon pojave Y u logičkom izrazu počela sam primjećivati ​​da se odgovori djece više ne poklapaju sa testovima. Ispostavilo se da im nije sasvim jasno kako da kreiraju tabelu preslikavanja sa novim tipom varijable. Tada mi je pala na pamet misao da zbog pogodnosti, cijeli izraz treba svesti na jednu vrstu varijable, kako je zgodno za djecu.
Ovu tehniku ​​ću iznijeti detaljnije. Radi praktičnosti, razmotrit ću ga na primjeru sistema logičkih izraza datih u (4).
Koliko različitih rješenja ima sistem logičkih jednačina?

(x 1 ^ y 1)=(¬x 2 V ¬ y 2 )
(x 2 ^ y 2)= (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5) = (¬ x 6 V ¬ y 6 )

Gdjex 1 , …, x 6 , y 1 , …, y 6 , - 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:
1. Iz analize sistema logičkih jednačina vidimo da postoji 6 varijabli X i 6 varijabli U. Budući da bilo koja od ovih varijabli može imati samo dvije vrijednosti (0 i 1), te varijable zamjenjujemo sa 12 varijabli istog tipa, na primjer Z.
2. Sada prepišimo sistem novim varijablama istog tipa. Poteškoća zadatka će biti pažljivo bilježenje prilikom zamjene varijabli.

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

3. Napravimo tabelu u kojoj ćemo proći kroz sve opcije z 1 , z 2 , z 3 , z 4 , pošto postoje četiri varijable u prvoj logičkoj jednačini, tabela će imati 16 redova (16=2 4); uklonite takve vrijednosti iz tabele z 4 , za koju prva jednadžba nema rješenja (precrtani brojevi).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Analizirajući tabelu, gradimo pravilo za prikaz parova varijabli (na primjer, par Z 1 Z 2 =00 odgovara par Z 3 Z 4 = 11) .

5. Popunite tabelu tako što ćete izračunati broj parova varijabli za koje sistem ima rješenje.

6. Zbrojite sve rezultate: 9 + 9 + 9 + 27 = 54
7. Odgovor: 54.
Navedena optimizovana metodologija za rešavanje zadatka 23 sa Jedinstvenog državnog ispita KIM omogućila je studentima da povrate samopouzdanje i uspešno reše ovu vrstu problema.

književnost:

1. FIPI. Smjernice za nastavnike, pripremljeno na osnovu analize tipične greške polaznici Jedinstvenog državnog ispita 2015. iz INFORMACIJE i IKT. Način pristupa: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. K.Yu. Polyakov, M.A. Roitberg.Sistemi logičkih jednadžbi: rješenje pomoću nizova bitova. Informatički časopis, br. 12, 2014, str. 4-12. Izdavačka kuća"Prvi septembar", Moskva.
3. E.A. Mironchik, Način prikaza.Časopis Informatika, br. 10, 2013, str. 18-26. Izdavačka kuća "Prvi septembar", Moskva.

Rješavanje sistema logičkih jednačina promjenom varijabli

Metoda zamjene varijabli koristi se ako su neke varijable uključene u jednačine samo u obliku određenog izraza, i ništa drugo. Tada se ovaj izraz može označiti novom varijablom.

Primjer 1.

Koliko ima različitih skupova vrijednosti logičkih varijabli x1, x2, x3, x4, x5, x6, x7, x8 koji zadovoljavaju sve dolje navedene uslove?

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

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

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

U odgovoru nije potrebno navesti sve različite skupove vrijednosti varijabli x1, x2, x3, x4, x5, x6, x7, x8, za koje je ovaj sistem jednakosti zadovoljen. Kao odgovor, potrebno je navesti broj takvih setova.

Rješenje:

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

Tada možemo napisati sistem u obliku jedne jednačine:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunkcija je 1 (tačno) kada svaki operand ima vrijednost 1. To je svaka od implikacija mora biti tačna, a to vrijedi za sve vrijednosti osim (1 → 0). One. u tabeli vrijednosti varijabli y1, y2, y3, y4, jedna ne smije biti lijevo od nule:

One. uslovi su zadovoljeni za 5 setova y1-y4.

Jer y1 = x1 → x2, tada se vrijednost y1 = 0 postiže na jednom skupu x1, x2: (1, 0), a vrijednost y1 = 1 – na tri skupa x1, x2: (0,0) , (0 ,1), (1.1). Isto tako za y2, y3, y4.

Pošto je svaki skup (x1,x2) za varijablu y1 kombinovan sa svakim skupom (x3,x4) za varijablu y2, itd., množe se brojevi skupova varijabli x:

				Broj setova po x1…x8

Zbrojimo broj skupova: 1 + 3 + 9 + 27 + 81 = 121.

odgovor: 121

Primjer 2.

Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, ... x9, y1, y2, ... y9 postoji koji zadovoljavaju sve dolje navedene uslove?

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

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

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

Kao odgovor nema potrebe navesti sve različite skupove vrijednosti varijabli x1, x2, ... x9, y1, y2, ... y9 za koje ovaj sistem jednaki Kao odgovor, potrebno je navesti broj takvih setova.

Rješenje:

Napravimo promjenu varijabli:

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

Sistem se može napisati kao jedna jednačina:

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

Ekvivalencija je istinita samo ako su oba operanda jednaka. Postoje dva skupa rješenja ove jednačine:

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

Jer zi = (xi ≡ yi), tada vrijednost zi = 0 odgovara dva skupa (xi,yi): (0,1) i (1,0), a vrijednost zi = 1 odgovara dva skupa (xi,yi ): (0 ,0) i (1,1).

Tada prvi skup z1, z2,…, z9 odgovara 2 9 skupova (x1,y1), (x2,y2),…, (x9,y9).

Isti broj odgovara drugom skupu z1, z2,…, z9. Tada ima ukupno 2 9 +2 9 = 1024 seta.

odgovor: 1024

Rješavanje sistema logičkih jednačina metodom vizualnog određivanja rekurzije.

Ova metoda se koristi ako je sistem jednačina prilično jednostavan i redoslijed povećanja broja skupova pri dodavanju varijabli očigledan.

Primjer 3.

Koliko različitih rješenja ima sistem jednačina?

¬x9 ∨ x10 = 1,

gdje su x1, x2, … x10 logičke varijable?

U odgovoru nije potrebno navesti sve različite skupove vrijednosti x1, x2, ... x10 za koje je ovaj sistem jednakosti zadovoljen. Kao odgovor, potrebno je navesti broj takvih setova.

Rješenje:

Rešimo prvu jednačinu. Disjunkcija je jednaka 1 ako je barem jedan njen operand jednak 1. To jest rješenja su skupovi:

Za x1=0 postoje dvije vrijednosti x2 (0 i 1), a za x1=1 postoji samo jedna vrijednost x2 (1), tako da je skup (x1,x2) rješenje jednadžbe . Ima ukupno 3 seta.

Dodajmo varijablu x3 i razmotrimo drugu jednačinu. Slično je prvom, što znači da za x2=0 postoje dvije vrijednosti x3 (0 i 1), a za x2=1 postoji samo jedna vrijednost x3 (1), tako da je skup (x2 ,x3) je rješenje jednadžbe. Ukupno ima 4 seta.

Lako je vidjeti da se pri dodavanju druge varijable dodaje jedan skup. One. rekurzivna formula za broj skupova (i+1) varijabli:

N i +1 = N i + 1. Tada za deset varijabli dobijamo 11 skupova.

odgovor: 11

Rješavanje sistema logičkih jednačina različitih tipova

Primjer 4.

Koliko različitih skupova vrijednosti logičkih varijabli x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 postoji koji zadovoljavaju sve dolje navedene uslove ?

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

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

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

x 4 ∧ y 4 ∧ z 4 = 0

Kao odgovor nema potrebe Navedite sve različite skupove vrijednosti varijabli x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 za koje je ovaj sistem jednakosti zadovoljen.

Kao odgovor, potrebno je navesti broj takvih setova.

Rješenje:

Imajte na umu da su tri jednačine sistema iste na različitim nezavisnim skupovima varijabli.

Pogledajmo prvu jednačinu. Konjunkcija je istinita (jednaka 1) samo ako su svi njeni operandi tačni (jednaki 1). Implikacija je 1 za sve tuple osim (1,0). To znači da će rješenje prve jednadžbe biti sljedeći skupovi x1, x2, x3, x4, u kojima se 1 ne pojavljuje lijevo od 0 (5 skupova):

Slično, rješenja druge i treće jednačine će biti apsolutno isti skupovi y1,…,y4 i z1,…, z4.

Sada analizirajmo četvrtu jednačinu sistema: x 4 ∧ y 4 ∧ z 4 = 0. Rješenje će biti svi skupovi x4, y4, z4 u kojima je barem jedna od varijabli jednaka 0.

One. za x4 = 0 su pogodni svi mogući skupovi (y4, z4), a za x4 = 1 su prikladni skupovi (y4, z4) u kojima postoji barem jedna nula: (0, 0), (0,1 ) , (1, 0).

				Broj setova

Ukupan broj setova je 25 + 4*9 = 25 + 36 = 61.

odgovor: 61

Rješavanje sistema logičkih jednačina konstruiranjem rekurentnih formula

Metoda konstruisanja rekurentnih formula koristi se pri rješavanju složenih sistema u kojima redoslijed povećanja broja skupova nije očigledan, a konstrukcija stabla je nemoguća zbog volumena.

Primjer 5.

Koliko različitih skupova vrijednosti logičkih varijabli x1, x2, ... x7, y1, y2, ... y7 postoji koji zadovoljavaju sve dolje navedene uslove?

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

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

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

U odgovoru nije potrebno navesti sve različite skupove vrijednosti varijabli x1, x2, ..., x7, y1, y2, ..., y7 za koje je ovaj sistem jednakosti zadovoljen. Kao odgovor, potrebno je navesti broj takvih setova.

Rješenje:

Imajte na umu da je prvih šest jednačina sistema identično i da se razlikuju samo po skupu varijabli. Pogledajmo prvu jednačinu. Njegovo rješenje će biti sljedeći skupovi varijabli:

Označimo:

broj skupova (0,0) na varijablama (x1,y1) do A 1,

broj skupova (0,1) na varijablama (x1,y1) do B 1,

broj skupova (1,0) na varijablama (x1,y1) do C 1,

broj skupova (1,1) na varijablama (x1,y1) do D 1 .

broj skupova (0,0) na varijablama (x2,y2) do A 2 ,

broj skupova (0,1) na varijablama (x2,y2) do B 2,

broj skupova (1,0) na varijablama (x2,y2) do C 2,

broj skupova (1,1) na varijablama (x2,y2) do D 2 .

Iz stabla odlučivanja vidimo to

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Imajte na umu da se skup (0,0) na varijablama (x2,y2) dobija iz skupova (0,1), (1,0) i (1,1) na varijablama (x1,y1). One. A 2 =B 1 +C 1 +D 1.

Skup (0,1) na varijablama (x2,y2) dobija se iz skupova (0,1), (1,0) i (1,1) na varijablama (x1,y1). One. B 2 =B 1 +C 1 +D 1.

Slično argumentirajući, primjećujemo da je C 2 =B 1 +C 1 +D 1. D2 = D1.

Tako dobijamo rekurentne formule:

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

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

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

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

Hajde da napravimo sto

Setovi	Oznaka.	Formula	Broj setova
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Posljednju jednačinu (x7 ∨ y7) = 1 zadovoljavaju svi skupovi osim onih u kojima je x7=0 i y7=0. U našoj tabeli broj takvih setova je A 7.

Tada je ukupan broj setova B 7 + C 7 + D 7 = 127+127+1 = 255

odgovor: 255

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 mišljenja, izgradnje hipoteza i pobijanja negativnih zaključaka ne dolazi sama od sebe; 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, ovo 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 je zadovoljen dati sistem jednačina. 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 fiksirati vrijednost jedne od varijabli (postaviti je na 0 ili 1) i na taj način pojednostaviti 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šenje. 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 ne pronađu sama rješenja, 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 novo promenljiva jednačina biće napisan u obliku: 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. Pogledajmo ovu metodu koristeći 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.

Krajem godine se pokazalo da je samo jedna od tri pretpostavke tačna. Koje su divizije ostvarile dobit na kraju godine?

Rješenje. Zapišimo pretpostavke iz uslova problema u formu logičke izjave: „Profitabilnost divizije B nije neophodan uslov za dobijanje

dobit po odjeljku A ":F 1 (A, B, C) = A → B

“Ostvarivanje profita od najmanje jednog odjeljenja B i C nije dovoljno da divizija A ostvari profit”: F 2 (A, B, C) = (B + C) → A

“Divizije A i B neće ostvariti profit u isto vrijeme”: F 3 (A, B, C) = A B

Iz uslova se zna da je samo jedna od tri pretpostavke tačna. To znači da moramo pronaći koji od sljedeća tri logička izraza nije identično lažan:

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Shodno tome, na kraju godine druga pretpostavka se ispostavila kao tačna, a prva i treća su bile netačne.

									A=0
	F1 F2 F3 = A B C= 1
									ako i samo ako je B = 0.
									C=1

Dakle, divizija C će dobiti profit, ali divizije A i B neće dobiti profit.

Rješavanje logičkih jednačina

U tekstovima državnog centraliziranog testiranja nalazi se zadatak (A8), koji traži da se pronađe korijen logičke jednačine. Pogledajmo načine rješavanja takvih zadataka koristeći primjer.

Pronađite korijen logičke jednačine: (A + B)(X AB) = B + X → A.

Prvo rješenje je da se napravi tabela istinitosti. Napravimo tablice istinitosti za desnu i lijevu stranu jednadžbe i vidimo na kojem X se poklapaju vrijednosti u posljednjim stupcima ovih tablica.

F1 (A, B, X) = (A+ B)(X AB)

					A+B	(A+ B)(X AB)	F 1 (A,B,X)

F2 (A, B, X) = B+ X→ A

			X → A							F 2 (A,B,X)
					X → A			X → A

Usporedimo rezultirajuće tablice istinitosti i odaberemo one redove u kojima se poklapaju vrijednosti F 1 (A, B, X) i F 2 (A, B, X).

			F 1 (A,B,X)	F 2 (A,B,X)

Prepišimo samo odabrane redove, ostavljajući samo kolone argumenata. Pogledajmo varijablu X kao funkciju A i B.

Očigledno, X = B → A.

Drugo rješenje je zamijeniti znak jednakosti u jednačini ekvivalentnim predznakom, a zatim pojednostaviti rezultirajuću logičku jednačinu.

Da bismo olakšali daljnji rad, najprije pojednostavimo desnu i lijevu stranu logičke jednadžbe i pronađemo njihove negacije:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Zamijenimo znak jednakosti u našoj logičkoj jednadžbi znakom ekvivalencije:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

Hajde da preuredimo logičke termine ovog izraza, uzimajući faktore X i X iz zagrada.

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

Označimo onda T = A B

X T+ X T= X↔ T.

Dakle, da bi logička jednačina imala rješenje: X = A B = B + A = B → A.

Kompjuterski logički elementi. Izrada funkcionalnih dijagrama

Razvojem računarske tehnologije pokazalo se da je matematička logika usko povezana sa pitanjima dizajna i programiranja kompjuterska tehnologija. Algebra logike je u početku našla široku primjenu u razvoju relejni kontakt sheme Prvo fundamentalno istraživanje, koji je skrenuo pažnju inženjera koji se bave kompjuterskim dizajnom na mogućnost analize električnih kola pomoću Bulove algebre, članak Amerikanca Claudea Shanona "Simbolička analiza relejnih kola" objavljen je u decembru 1938. godine. Nakon ovog članka, kompjuterski dizajn nije mogao biti urađen bez upotrebe Booleove algebre.

Logički element je kolo koje implementira logičke operacije disjunkcije, konjunkcije i inverzije. Hajde da razmotrimo implementaciju logičkih elemenata kroz električna relejno-kontaktna kola, koja su vam poznata iz školskog kursa fizike.

Serijsko povezivanje kontakata

Paralelno povezivanje kontakata

Sastavimo tabelu zavisnosti stanja kola od svih mogućih stanja kontakata. Uvedemo sljedeće oznake: 1 – kontakt je zatvoren, u kolu postoji struja; 0 – kontakt je otvoren, nema struje u kolu.

		Stanje strujnog kola	Stanje kola sa paralelom
		serijska veza	veza

Kao što se može vidjeti, kolo sa serijskom vezom odgovara logička operacija konjunkcija, jer se struja u kolu pojavljuje samo kada su kontakti A i B zatvoreni istovremeno. Kolo s paralelnom vezom odgovara logičkoj operaciji disjunkcije, budući da u kolu nema struje samo u trenutku kada su oba kontakta otvorena.

Logički rad inverzije se provodi kroz kontaktni krug elektromagnetnog releja, čiji je princip proučavan u školski kurs fizike. Kontakt x je otvoren kada je x zatvoren i obrnuto.

Upotreba relejnih kontaktnih elemenata za konstruisanje logičkih kola računara nije opravdana zbog niske pouzdanosti, velikih dimenzija, velike potrošnje energije i niskih performansi. Pojava elektronskih uređaja (vakuma i poluprovodnika) stvorila je mogućnost konstruisanja logičkih elemenata sa brzinama od 1 milion prekidača u sekundi i više. Poluvodički logički elementi rade u prekidačkom režimu slično kao elektromagnetni relej. Celokupna teorija predstavljena za kontaktna kola prenosi se na poluvodičke elemente. Logičke elemente na poluvodičima karakterizira ne stanje kontakata, već prisutnost signala na ulazu i izlazu.

Razmotrimo logičke elemente koji implementiraju osnovne logičke operacije:

Inverter - implementira operaciju negacije ili inverzije. U

inverter ima jedan ulaz i jedan izlaz. Pojavljuje se izlazni signal

kada ga nema na ulazu, i obrnuto.

konjuktor -

X1 X2 ... Xn

implementira operaciju veze.

Kod konjunkora

jedan izlaz i najmanje dva ulaza. Signal uključen

pojavljuje se u izlazu ako i samo ako

svi ulazi su signalizirani.

X2 + ... Xn

Disjunktor - implementira operaciju disjunkcije. U

disjunktor ima jedan izlaz i najmanje dva

Izlazni signal se ne pojavljuje ako i samo ako

kada se signali ne dovode na sve ulaze.

	Build	funkcionalan
F(X, Y, Z) = X(Y+ Z)
			X+Z

dijagram koji odgovara funkciji:

&F(X, Y, Z)

Rješavanje problema pomoću konjunktivne normale

I disjunktivno-normalno forme

IN Logički problemi često sadrže standardne probleme u kojima trebate napisati funkciju koja implementira lestvičasti dijagram, pojednostaviti ga i konstruisati tabelu istinitosti za ovu funkciju. Kako riješiti inverzni problem? S obzirom na proizvoljnu tablicu istinitosti, potrebno je izgraditi funkcionalni ili relejni dijagram. Danas ćemo se pozabaviti ovim pitanjem.

Bilo koja funkcija logičke algebre može biti predstavljena kombinacijom tri operacije: konjunkcija, disjunkcija i inverzija. Hajde da shvatimo kako se to radi. Da bismo to učinili, zapišimo nekoliko definicija.

Minterm je funkcija formirana konjunkcijom određenog broja varijabli ili njihovih negacija. Minterm uzima vrijednost 1 za jedini od svih mogućih skupova

argumente, a vrijednost je 0 za sve ostale. Primjer: x 1 x 2 x 3 x 4 .

Maxterm je funkcija formirana disjunkcijom određenog broja varijabli ili njihovih negacija. Maxterm uzima vrijednost 0 u jednom od mogućih skupova i 1 u svim ostalim.

Primjer: x 1 + x 2 + x 3.

Funkcija u disjunktivni normalni oblik(DNF) je logičan zbir minterms.

Primjer: x 1x 2+ x 1x 2+ x 1x 2x 3.

Konjunktivna normalna forma(CNF) je logičan proizvod elementarnih disjunkcija (maxterms).

Primjer: (x 1+ x 2+ x 3) (x 1+ x 2) .

Savršena disjunktivna normalna forma se naziva DNF, u kojem su sve varijable ili njihove negacije prisutne.

Primjer: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Savršena konjunktivna normalna forma se naziva CNF, u svakom maksimalnom terminu u kojem su prisutne sve varijable ili njihove negacije.

Primjer: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Pisanje logičke funkcije iz tablice

Bilo koji logička funkcija može se izraziti kao SDNF ili SCNF. Kao primjer, razmotrite funkciju f prikazanu u tabeli.

			f(x1, x2, x3)

Funkcije G0, G1, G4, G5, G7 su mintermi (vidi definiciju). Svaka od ovih funkcija je proizvod tri varijable ili njihove inverze i uzima vrijednost 1 samo u jednoj situaciji. Može se vidjeti da je za dobivanje 1 u vrijednosti funkcije f potreban jedan minterm. Prema tome, broj minterma koji čine SDNF ove funkcije jednak je broju jedinica u vrijednosti funkcije: f= G0+G1+G4+G5+G7. Dakle, SDNF ima oblik:

f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.

Slično, možete izgraditi SKNF. Broj faktora jednak je broju nula u vrijednostima funkcije:

f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

Dakle, svaka logička funkcija data u obliku tabele može se napisati kao formula.

Algoritam za konstruisanje SDNF-a koristeći tabelu istinitosti

Tabela istinitosti neke funkcije je data. Da biste napravili SDNF, morate izvršiti sljedeći niz koraka:

1. Odaberite sve redove tablice u kojima funkcija ima vrijednost 1.

2. Za svaki takav red dodijelite konjunkciju svih argumenata ili njihove inverzije (minterm). U ovom slučaju, argument koji ima vrijednost 0 je uključen u minterm sa negacijom, a vrijednost 1 je uključena bez negacije.

3. Konačno, formiramo disjunkciju svih dobijenih minterma. Broj minterma mora odgovarati broju jedinica logičke funkcije.

Algoritam za konstruisanje SCNF-a koristeći tabelu istinitosti

Dana je tabela istinitosti neke funkcije. Da biste izgradili SKNF, morate izvršiti sljedeći niz koraka:

1. Odaberite sve redove tablice u kojima funkcija ima vrijednost 0.

2. Za svaki takav red dodijelite disjunkciju svih argumenata ili njihove inverzije (maxterm). U ovom slučaju, argument koji ima vrijednost 1 je uključen u maxterm sa negacijom, a vrijednost 1 je uključena bez negacije.

3. Konačno, formiramo konjunkciju svih dobijenih maxtermsa. Broj maksimalnih termina mora odgovarati broju nula logičke funkcije.

Ako se slažemo između dva oblika (SDNF ili SKNF), dajemo prednost onom koji sadrži manje slova, tada je SDNF poželjniji ako ima manje jedinica među vrijednostima funkcije tablice istine, a SCNF je poželjniji ako ima manje nula.

Primjer. Dana je tabela istinitosti logičke funkcije tri varijable. Konstruirajte logičku formulu koja implementira ovu funkciju.

			F(A, B, C)

Odaberimo one redove u ovoj tablici istinitosti u kojima je vrijednost funkcije 0.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Provjerimo izvedenu funkciju kreiranjem tabele istinitosti.

Upoređujući početnu i konačnu tablicu istinitosti, možemo zaključiti da je logička funkcija ispravno konstruirana.

Rješavanje problema

1. Tri nastavnika biraju zadatke za olimpijadu. Postoji nekoliko zadataka koje možete izabrati. Za svaki zadatak svaki nastavnik iznosi svoje mišljenje: lak (0) ili težak (1) zadatak. Zadatak se uključuje u olimpijski zadatak ako ga najmanje dva nastavnika ocjenjuju kao težak, ali ako ga sva tri nastavnika smatraju teškim, onda se takav zadatak ne uvrštava u olimpijski zadatak kao pretežak. Napravite logički dijagram uređaja koji će dati 1 ako je zadatak uključen u olimpijski zadatak i 0 ako nije uključen.

Napravimo tabelu istinitosti za željenu funkciju. Imamo tri ulazne varijable (tri nastavnika). Stoga će tražena funkcija biti funkcija tri varijable.

Analizirajući stanje problema, dobijamo sledeću tabelu istinitosti:

Gradimo SDNF. F(A, B, C) = ABC+ ABC+ ABC

Sada gradimo logički dijagram ove funkcije.

B&1F(A,B,C)

2. City Olympics osnovni kurs informatika, 2007.Napravite dijagram električnog kola za ulaz u trokatnu kuću tako da prekidač na bilo kojem spratu može uključiti ili isključiti svjetla u cijeloj kući.

Dakle, imamo tri prekidača koje moramo koristiti za uključivanje i isključivanje svjetla. Svaki prekidač ima dva stanja: gore (0) i dole (1). Pretpostavimo da ako su sva tri prekidača u položaju 0, svjetla na ulazu su isključena. Zatim, kada pomerite bilo koji od tri prekidača u položaj 1, svetlo na ulazu bi trebalo da se upali. Očigledno, kada pomerite bilo koji drugi prekidač u položaj 1, svjetlo na ulazu će se ugasiti. Ako se treći prekidač prebaci u položaj 1, upalit će se svjetlo na ulazu. Pravimo tabelu istine.

Tada je F(A, B, C) = ABC+ ABC+ ABC+ ABC.

	3. Promijenite stanje			vrijednosti logičke funkcije			F(A, B, C) = C→		A+B
	promjena argumenata B i C u isto vrijeme jednaka je:
		A → (B C)						(B C) → A
					A(B C)
	4) (B C) → A				A → (B C)

Bilješka. Da biste uspješno riješili ovaj problem, zapamtite sljedeće logičke formule:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

Zadata nam je logička funkcija tri varijable F 1 (A, B, C) = C → A + B = C + A B.

Promjenimo varijable B i C istovremeno: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Napravimo tablice istinitosti za ove dvije funkcije:

Analizirajmo rezultirajuću tabelu. Od osam redova tabele, samo u dva (2. i 3.) funkcija ne menja svoju vrednost. Primijetite da u ovim redovima varijabla A ne mijenja svoju vrijednost, ali varijable B i C to čine.

Mi gradimo SKNF funkcije koristeći ove linije:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (B C) → A

Dakle, željeni odgovor je 4.

4. Uvjet za promjenu vrijednosti logičke funkcije F (A, B, C) = C + AB dok se istovremeno mijenjaju argumenti A i B jednako je:

1) C+ (A B)

C+(A B)

TAKSI)

4) C(A B)

C → (A B)

F 1 (A,B,C)=

C+AB

F 2 (A ,B ,C )= F 1 (

C )= A

Pravimo tabelu istine.

Analizirajmo rezultirajuću tabelu. Od osam redova tabele, samo u dva (1. i 7.) funkcija menja svoju vrednost. Imajte na umu da u ovim redovima varijabla C ne mijenja svoju vrijednost, ali varijable A i B mijenjaju.

Mi gradimo SDNF funkcije koristeći ove linije:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Dakle, traženi odgovor je 2.

Reference

1. Shapiro S.I. Rješavanje logičkih i zadaci igranja (logičke i psihološke studije). – M.: Radio i veze, 1984. – 152 str.

2. Šolomov L.A. Osnove teorije diskretnih logičkih i računarskih uređaja. – M.: Nauka. Ch. ed. fizički - mat. lit., 1980. - 400 str.

3. Pukhalsky G.I., Novoseltseva T.Ya. Projektovanje diskretnih uređaja na integrisanim kolima: Priručnik. – M.: Radio i komunikacije, 1990.