Dva jednaka protivnika igraju šah. Ekvivalentne jednačine i jednačine-posljedice. Ekvivalentne transformacije. Pojednostavljenje formula

Odjeljak 2. Logička ekvivalencija formula. Normalni oblici za formule propozicione algebre

Odnos ekvivalencije

Koristeći tablice istinitosti, moguće je ustanoviti na kojim skupovima istinitih vrijednosti ulaznih varijabli formula će poprimiti istinitu ili lažnu vrijednost (kao i iskaz s odgovarajućom logičkom strukturom), koje će formule biti tautologije ili kontradikcije , kao i utvrditi da li su dvije date formule ekvivalentan.

U logici kažu da su dvije rečenice ekvivalentne ako su obje istinite ili netačne u isto vrijeme. Riječ "istovremeno" u ovoj frazi je dvosmislena. Dakle, za rečenice "Sutra će biti utorak" i "Jučer je bila nedelja" ova reč ima doslovno značenje: u ponedeljak su obe tačne, a u ostatku nedelje - obe su netačne. za jednadžbe" x = 2" i " 2x = 4"" Istovremeno "znači" na istim vrijednostima varijable ". Prognoze "Sutra će padati kiša" i "Nije tačno da sutra neće padati" istovremeno će se potvrditi (ispostaviti se istinitim) ili ne potvrditi (ispostaviti se lažnim). U suštini, ovo je jedna te ista prognoza, izražena u dva različita oblika, koja se može predstaviti formulama X i . Ove formule istovremeno uzimaju vrijednost "true" ili vrijednost "false". Za provjeru dovoljno je sastaviti tabelu istinitosti:

X
1	0	1
0	1	0

Vidimo da su vrijednosti istine u prvoj i posljednjoj koloni iste. Prirodno je smatrati da su takve formule, kao i rečenice koje im odgovaraju, ekvivalentne.

Formule F 1 i F 2 nazivaju se ekvivalentnim ako je njihov ekvivalent tautologija.

Ekvivalencija dvije formule se piše na sljedeći način: (čitaj: formula F 1 je ekvivalentna formuli F 2).

Postoje tri načina da se proveri da li su formule ekvivalentne: 1) sastavite njihovu ekvivalentnost i koristite tabelu istinitosti da proverite da li to nije tautologija; 2) za svaku formulu sastaviti tabelu istinitosti i uporediti konačne rezultate; ako je u završnim kolonama sa istim skupovima vrijednosti varijabli istinite vrijednosti obje formule će biti jednake, tada su formule ekvivalentne; 3) korištenjem ekvivalentnih transformacija.

Primjer 2.1: Saznajte da li su formule ekvivalentne: 1),; 2),.

1) Koristićemo prvi metod za određivanje ekvivalencije, odnosno saznaćemo da li je ekvivalentnost formula i tautologija.

Hajde da sastavimo ekvivalent formula:. Rezultirajuća formula sadrži dvije različite varijable ( A i V) i 6 operacija: 1); 2); 3); 4) ; 5) ; 6). To znači da će odgovarajuća tabela istine imati 5 redova i 8 stupaca:

A	V
1	1	0	0	0	1	0	1
1	0	0	1	1	0	1	1
0	1	1	0	1	0	1	1
0	0	1	1	1	0	1	1

Iz završne kolone tabele istinitosti može se vidjeti da je sastavljena ekvivalentnost tautologija i, prema tome,.

2) Da bismo saznali da li su formule ekvivalentne i da li su ekvivalentne, koristimo drugu metodu, odnosno sastavljamo tabelu istinitosti za svaku od formula i upoređujemo konačne kolone. ( Komentar... Da bi se drugi metod efikasno koristio, potrebno je da sve sastavljene tabele istinitosti počnu na isti način, tj. skupovi vrijednosti varijabli bili su isti u odgovarajućim redovima .)

Formula ima dvije različite varijable i 2 operacije, što znači da odgovarajuća tabela istinitosti ima 5 redaka i 4 stupca:

A	V
1	1	1	0
1	0	0	1
0	1	1	0
0	0	1	0

Formula ima dvije različite varijable i 3 operacije, što znači da odgovarajuća tabela istinitosti ima 5 redova i 5 stupaca:

A	V
1	1	0	0	1
1	0	0	1	1
0	1	1	0	0
0	0	1	1	1

Upoređujući završne stupce kompajliranih tablica istinitosti (pošto tabele počinju na isti način, možemo zanemariti skupove vrijednosti varijabli), vidimo da se ne poklapaju i stoga formule nisu ekvivalentne ().

Izraz nije formula (pošto se simbol "" ne odnosi ni na jednu logičku operaciju). Izražava stav između formula (kao i jednakost između brojeva, paralelizam između pravih, itd.).

Važi teorema o svojstvima relacije ekvivalencije:

Teorema 2.1. Odnos ekvivalencije između formula propozicionalne algebre:

1) refleksivno:;

2) simetrično: ako, onda;

3) tranzitivno: ako i, onda.

Zakoni logike

Često se nazivaju ekvivalentnosti formula u propozicionoj logici zakonima logike... Nabrojimo najvažnije od njih:

1. - zakon identiteta.

2.- zakon isključene trećine

3. - zakon kontradikcije

4. - disjunkcija sa nulom

5. - konjunkcija sa nulom

6. - disjunkcija sa jedinicom

7. - spoj s jednim

8. - zakon dvostruke negacije

9. - komutativnost konjunkcije

10. - komutativnost disjunkcije

11. - asocijativnost veznika

12. - asocijativnost disjunkcije

13. - distributivnost veznika

14. - distributivna disjunkcija

15.- zakoni idempotencije

16. ; - zakoni apsorpcije

17. ; - de Morganovi zakoni

18. - zakon koji izražava implikaciju kroz disjunkciju

19. - zakon kontrapozicije

20.- zakoni koji izražavaju ekvivalenciju kroz druge logičke operacije

Zakoni logike se koriste za pojednostavljenje složenih formula i za dokazivanje da su formule podjednako istinite ili netačne.

Ekvivalentne transformacije. Pojednostavljenje formula

Ako se ista formula svugdje zamijeni u ekvivalentnim formulama umjesto neke promjenljive, tada će se i novodobivene formule ispostaviti da su ekvivalentne u skladu s pravilom zamjene. Na ovaj način, iz svake ekvivalencije, može se dobiti onoliko novih ekvivalencija.

Primjer 1: Ako u de Morganovom zakonu umjesto X zamjena, i umjesto Y zamjenu, dobijamo novu ekvivalentnost. Valjanost dobijene ekvivalencije lako je provjeriti korištenjem tablice istinitosti.

Ako je bilo koja formula koja je dio formule F, zamijenjen formulom koja je ekvivalentna formuli, tada će se rezultirajuća formula pokazati ekvivalentnom formuli F.

Zatim se za formulu iz primjera 2 mogu napraviti sljedeće promjene:

- zakon dvostruke negacije;

- de Morganov zakon;

- zakon dvostruke negacije;

- zakon asocijativnosti;

- zakon idempotencije.

Svojstvom tranzitivnosti relacije ekvivalencije možemo to tvrditi .

Zamjena jedne formule drugom, njoj ekvivalentnom, naziva se ekvivalentna konverzija formule.

Ispod pojednostavljenje formule koje ne sadrže znakove implikacije i ekvivalencije razumiju ekvivalentnu transformaciju koja vodi do formule koja ne sadrži negacije neelementarnih formula (posebno dvostruke negacije) ili sadrži u zbiru manje znakova konjunkcije i disjunkcije od izvorne .

Primjer 2.2: Hajde da pojednostavimo formulu .

U prvom koraku primijenili smo zakon koji transformiše implikaciju u disjunkciju. U drugom koraku primijenili smo komutativni zakon. U trećem koraku primijenili smo zakon idempotencije. Četvrti je de Morganov zakon. A na petom - zakon dvostruke negacije.

Napomena 1... Ako je određena formula tautologija, tada je i svaka formula koja joj je ekvivalentna također tautologija.

Dakle, ekvivalentne transformacije se također mogu koristiti za dokazivanje identične istinitosti određenih formula. Da bi se to postiglo, ova formula se mora svesti ekvivalentnim transformacijama na jednu od formula, koje su tautologije.

Napomena 2... Neke tautologije i ekvivalencije su kombinovane u parovima (zakon kontradikcije i zakon alternativnih, komutativnih, asocijativnih zakona, itd.). U tim prepiskama tzv princip dualnosti .

Zovu se dvije formule koje ne sadrže znakove implikacije i ekvivalencije ambivalentan ako se svaki od njih može dobiti od drugog zamjenom znakova, odnosno sa.

Princip dualnosti glasi sljedeće:

Teorema 2.2: Ako su dvije formule koje ne sadrže znakove implikacije i ekvivalencije ekvivalentne, tada su i njihove dualne formule ekvivalentne.

Normalni oblici

Normalna forma Je sintaktički nedvosmislen način pisanja formule koja implementira datu funkciju.

Iskorištavanje poznatim zakonima logike, svaka formula se može transformisati u ekvivalentnu formulu oblika , gdje i svaki je ili varijabla, ili negacija varijable, ili konjunkcija varijabli ili njihove negacije. Drugim riječima, bilo koja formula se može svesti na ekvivalentnu formulu jednostavnog standardnog oblika, koja će biti disjunkcija elemenata, od kojih je svaki konjunkcija zasebnih različitih logičkih varijabli, bilo s negativnim predznakom ili bez njega.

Primjer 2.3: U velikim formulama ili za višestruke transformacije, uobičajeno je da se izostavi znak veznika (po analogiji sa znakom množenja):. Vidimo da je nakon izvršenih transformacija formula disjunkcija triju veznika.

Ovaj oblik se zove disjunktivni normalni oblik (DNF). Poziva se poseban element DNF-a elementarna konjunkcija ili sastavne jedinice.

Slično, bilo koja formula se može svesti na ekvivalentnu formulu, koja će biti konjunkcija elemenata, od kojih će svaki biti disjunkcija logičkih varijabli sa ili bez negativnih predznaka. To jest, svaka formula se može svesti na ekvivalentnu formulu oblika , gdje i svaki je ili varijabla, ili negacija varijable, ili disjunkcija varijabli ili njihove negacije. Ovaj oblik se zove konjunktivni normalni oblik (CNF).

Primjer 2.4:

Zaseban element CNF-a se zove elementarna disjunkcija ili sastavni dio nule.

Očigledno, svaka formula ima beskonačno mnogo DNF-ova i CNF-ova.

Primjer 2.5: Nađimo nekoliko DNF-ova za formulu .

Savršene normalne forme

SDNF (savršeni DNF) je DNF u kojem svaka elementarna konjunkcija sadrži sve elementarne iskaze, ili njihove negacije jednom, elementarne konjunkcije se ne ponavljaju.

SKNF (savršeni CNF) je CNF u kojem svaka elementarna disjunkcija sadrži sve elementarne iskaze, ili njihove negacije jednom, elementarne disjunkcije se ne ponavljaju.

Primjer 2.6: 1) - SDNF

2) 1 - SKNF

Hajde da formulišemo karakteristični znaci SDNF (SKNF).

1) Svi članovi disjunkcije (veznika) su različiti;

2) Svi članovi svake konjunkcije (dizjunkcije) su različiti;

3) Nijedna konjunkcija (disjunkcija) ne sadrži i promenljivu i njenu negaciju;

4) Svaka konjunkcija (disjunkcija) sadrži sve varijable uključene u originalnu formulu.

Kao što vidimo, karakteristične osobine (ali ne i forme!) zadovoljavaju definiciju dualnosti, stoga je dovoljno da se pozabavite jednim oblikom da biste naučili kako da primite oba.

Iz DNF (CNF), koristeći ekvivalentne transformacije, lako se može dobiti SDNF (SKNF). S obzirom da su pravila za dobijanje savršenih normalnih oblika takođe dualna, detaljno ćemo analizirati pravilo za dobijanje SDNF-a i sami formulisati pravilo za dobijanje SKNF-a koristeći definiciju dualnosti.

Opšte pravilo reducirajući formulu na SDNF koristeći ekvivalentne transformacije:

Da bi se dala formula F, što nije identično lažno, za SDNF, dovoljno je:

1) dovesti je u neki DNF;

2) ukloniti članove disjunkcije koja sadrži promenljivu zajedno sa njenom negacijom (ako postoji);

3) ukloniti sve identične članove disjunkcije osim jednog (ako ih ima);

4) ukloniti sve identične članove svakog veznika osim jednog (ako ih ima);

5) ako bilo koji veznik ne sadrži promenljivu iz redova varijabli uključenih u prvobitnu formulu, dodati pojam ovoj konjunkciji i primeniti odgovarajući distributivni zakon;

6) ako rezultirajuća disjunkcija sadrži iste termine, koristite Recept 3.

Rezultirajuća formula je SDNF ove formule.

Primjer 2.7: Nađimo SDNF i SKNF za formulu .

Budući da je DNF za ovu formulu već pronađen (vidi primjer 2.5), počećemo s dobivanjem SDNF-a:

2) u rezultujućoj disjunkciji nema varijabli sa njihovim negacijama;

3) u disjunkciju nema identičnih članova;

4) ne postoje identične varijable ni u jednoj konjunkciji;

5) prva elementarna konjunkcija sadrži sve varijable uključene u originalnu formulu, a druga elementarna konjunkcija nema varijablu z, pa dodajmo mu člana i primijenimo distributivni zakon:;

6) lako je uočiti da su se u disjunkciji pojavili identični termini, pa jedan uklanjamo (recept 3);

3) uklonite jednu od istih disjunkcija: ;

4) u preostalim klauzulama nema identičnih članova;

5) nijedna od elementarnih disjunkcija ne sadrži sve varijable uključene u originalnu formulu, stoga svaku od njih dopunjavamo konjunkcijom:;

6) u nastaloj konjunkciji nema identičnih disjunkcija, stoga je pronađeni konjunktivni oblik savršen.

Budući da u agregatu SKNF i SDNF formule F 8 članova, oni su najvjerovatnije pronađeni ispravno.

Svaka izvršna (osporiva) formula ima jedan SDNF i jedan jedinstveni SKNF. Tautologija nema SKNF, a kontradikcija nema SDNF.

Definicija. Dvije jednačine f 1 (x) = g 1 (x) i f 2 (x) = g 2 (x) nazivaju se ekvivalentnim ako se skupovi njihovih korijena poklapaju.

Na primjer, jednadžbe x 2 - 9 = 0 i (2 X + 6)(X- 3) = 0 su ekvivalentni, jer oba imaju brojeve 3 i -3 kao svoje korijene. Jednačine (3 X + 1)-2 = x 2- + 1 i x 2+ 1 = 0, pošto oba nemaju korijena, tj. njihovi skupovi korijena se poklapaju.

Definicija. Zamjena jednačine ekvivalentnom jednačinom naziva se ekvivalentna transformacija.

Hajde sada da saznamo koje transformacije omogućavaju dobijanje ekvivalentnih jednačina.

Teorema 1. Neka jednačina f (x) i g (x) dato na setu i h(x) je izraz definiran na istom skupu. Zatim jednačine f (x) = g (x)(1) i f (x) + h(x) =g (x) + h(x) (2) su ekvivalentni.

Dokaz. Označimo sa T 1 - skup rješenja jednadžbe (1) i kroz T 2 - skup rješenja jednačine (2). Tada će jednačine (1) i (2) biti ekvivalentne ako T 1 = T 2. Da bismo se u to uvjerili, potrebno je pokazati da bilo koji korijen od T 1 je korijen jednadžbe (2) i, obrnuto, bilo koji korijen od T 2 je korijen jednačine (1).

Neka broj a je korijen jednačine (1). Onda a? T 1, a kada se zameni u jednačinu (1) pretvara je u pravu numeričku jednakost f (a) = g (a) i izraz h (x) pretvara u numerički izraz h(a), što ima smisla na setu X. Dodajte objema stranama istinske jednakosti f (a) = g (a) numerički izraz h(a). Dobijamo, prema svojstvima pravih numeričkih jednakosti, pravu brojčanu jednakost f (a) + h(a) =g (a) + h(a), što označava da je broj a je korijen jednačine (2).

Dakle, dokazano je da je svaki korijen jednačine (1) ujedno i korijen jednačine (2), tj. T 1 With T 2.

Pusti sada a - korijen jednačine (2). Onda a? T 2 a kada se zameni u jednačinu (2) pretvara je u pravu numeričku jednakost f (a) + h(a) =g (a) + h(a). Dodajte na obje strane ove jednakosti numerički izraz - h(a), Dobijamo pravu brojčanu jednakost f (x) = g (x),što ukazuje da je broj a - korijen jednačine (1).

Dakle, dokazano je da je svaki korijen jednačine (2) ujedno i korijen jednačine (1), tj. T 2 With T 1.

Jer T 1 With T 2 i T 2 With T 1, onda po definiciji jednakih skupova T 1= T 2, što znači da su jednačine (1) i (2) ekvivalentne.

Ova teorema se može formulirati drugačije: ako na obje strane jednačine sa domenom X dodamo isti izraz sa promenljivom, definisanom na istom skupu, onda dobijamo novu jednačinu ekvivalentnu datoj.

Ova teorema implicira sljedeće posljedice, koje se koriste za rješavanje jednačina:

1. Ako se jedan ili drugi broj doda na obje strane jednačine, onda ćemo dobiti jednačinu koja je ekvivalentna datoj.

2. Ako se bilo koji pojam (numerički izraz ili izraz s promjenljivom) prenese iz jednog dijela jednačine u drugi, mijenjajući predznak pojma u suprotan, tada dobijamo jednačinu koja je ekvivalentna ovoj.

Teorema 2. Neka jednačina f (x) = g (x) dat na setu X i h (x) - izraz koji je definiran na istom skupu i ne nestaje ni za jednu vrijednost X mnoštva X. Zatim jednačine f (x) = g (x) i f (x) h(x) =g (x) h(x) su ekvivalentni.

Dokaz ove teoreme je sličan dokazu teoreme 1.

Teorema 2 može se formulisati drugačije: ako su obje strane jednadžbe sa domenom X pomnožimo sa istim izrazom, koji je definiran na istom skupu i na njemu ne nestaje, onda dobijamo novu jednačinu ekvivalentnu datoj.

Iz ove teoreme slijedi sljedeći zaključak: ako se obje strane jednačine pomnože (ili podijele) sa istim brojem različitim od nule, onda dobijamo jednačinu koja je ekvivalentna datoj.

Rješavanje jednadžbi u jednoj varijabli

Hajde da riješimo jednačinu 1- x/3 = x/6, x ? R i opravdati sve transformacije koje ćemo izvršiti u procesu rješenja.

Transformacije	Obrazloženje za konverziju
1. Dovedemo izraze s lijeve i desne strane jednačine na zajednički nazivnik: (6-2 X)/ 6 = X/6	Provedena je identična transformacija izraza na lijevoj strani jednačine.
2. Odbacite zajednički imenilac: 6-2 X = X	Množenjem obe strane jednačine sa 6 (Teorema 2), dobijamo jednačinu koja je ekvivalentna datoj.
3. Prenesite izraz -2x na desna strana jednadžbe sa suprotnim predznakom: 6 = X+2X.	Koristili smo korolar iz teoreme 1 i dobili jednačinu koja je ekvivalentna prethodnoj, a samim tim i datoj.
4. Dajemo slične članove na desnoj strani jednačine: 6 = 3 X.	Izvršili su identičnu transformaciju izraza.
5. Podijelite obje strane jednačine sa 3: X = 2.	Iskoristili smo korolar iz teoreme 2, dobili jednačinu ekvivalentnu prethodnoj, a samim tim i datoj.

Budući da su sve transformacije koje smo izvršili prilikom rješavanja ove jednačine bile ekvivalentne, može se tvrditi da je 2 korijen ove jednačine.

Ako u procesu rješavanja jednadžbe nisu ispunjeni uvjeti teorema 1 i 2, može doći do gubitka korijena ili se mogu pojaviti strani korijeni. Stoga je važno, prilikom transformacije jednačine da bi se dobila jednostavnija, osigurati da one vode do jednačine ekvivalentne ovoj.

Razmotrimo, na primjer, jednačinu x (x - 1) = 2x, x? R... Podijelimo oba dijela na X, dobijamo jednačinu X - 1 = 2, odakle X= 3, to jest, ova jednačina ima jedan korijen - broj 3. Ali da li je to istina? Lako je vidjeti da ako u datoj jednačini umjesto varijable X zamijeniti 0, pretvorit će se u pravu numeričku jednakost 0 · (0 - 1) = 2 · 0. To znači da je 0 korijen ove jednadžbe, koju smo izgubili pri izvođenju transformacija. Hajde da ih analiziramo. Prvo što smo uradili je da podelimo obe strane jednačine na X, one. pomnoženo izrazom x ali na X= Oh, nema smisla. Posljedično, nismo ispunili uvjet iz teoreme 2, što je dovelo do gubitka korijena.

Da bismo bili sigurni da se skup korijena ove jednadžbe sastoji od dva broja 0 i 3, dajemo još jedno rješenje. Pomjeri izraz 2 X s desna na lijevo: x (x- 1) - 2x = 0. Izvodimo na lijevoj strani jednadžbe izvan zagrada X i dati slične članove: x (x - 3) = 0. Proizvod dva faktora jednak je nuli ako i samo ako je barem jedan od njih jednak nuli, dakle x= 0 ili X- 3 = 0. Otuda dobijamo da su koreni ove jednadžbe 0 i 3.

U osnovnom kursu matematike teorijske osnove rješavanje jednačina je odnos između komponenti i ishoda radnji. Na primjer, rješavanje jednadžbe ( X 9): 24 = 3 opravdano je na sljedeći način. Pošto je nepoznata u dividendi, da bi se našla dividenda, djelitelj se mora pomnožiti s količnikom: X 9 = 24 3, ili X 9 = 72.

Da biste pronašli nepoznati faktor, morate proizvod podijeliti sa poznatim faktorom: x = 72: 9, ili x = 8, dakle, korijen ove jednadžbe je broj 8.

Vježbe

1 ... Odredite koji od sljedećih unosa su jednadžbe s jednom promjenjivom:

a) ( X-3) 5 = 12 X; d) 3 + (12-7) 5 = 16;

b) ( X-3) 5 = 12; e) ( X-3) y =12X;

v) ( X-3) 17 + 12; e) x 2 - 2x + 5 = 0.

2. Jednačina 2 X 4 + 4X 2 -6 = 0 dato na setu prirodni brojevi... Objasnite zašto je broj 1 korijen ove jednadžbe, ali 2 i -1 nisu njeni korijeni.

3. U jednačini ( X+ ...)(2X + 5) - (X - 3)(2X+ 1) = 20 jedan broj se briše i zamjenjuje tačkama. Pronađite izbrisani broj ako znate da je korijen ove jednadžbe broj 2.

4. Formulirajte uslove pod kojima:

a) broj 5 je korijen jednačine f (x) = g (x);

b) broj 7 nije korijen jednačine f (x) = g (x).

5. Saznajte koji od sljedećih parova jednadžbi su ekvivalentni na skupu realnih brojeva:

a) 3 + 7 X= -4 i 2 (3 + 7L X) = -8;

6)3 + 7X= -4 i 6 + 7 X = -1;

c) 3 + 7 X= -4 i l X + 2 = 0.

6. Formulirajte svojstva relacije ekvivalencije jednačina. Koje se koriste u procesu rješavanja jednadžbe?

7. Riješite jednačine (sve su date na skupu realnih brojeva) i opravdajte sve transformacije izvršene u procesu njihovog pojednostavljivanja:

a) (7 x+4)/2 – x = (3x-5)/2;

b) x –(3x-2)/5 = 3 – (2x-5)/3;

u 2- X)2-X (X + 1,5) = 4.

8. Student je riješio jednačinu 5 X + 15 = 3 X+ 9 kako slijedi: izvadio sam broj 5 na lijevoj strani i 3 na desnoj strani, dobio sam jednačinu 5 (x+ 3) = 3(X+ 3), a zatim podijelite oba dijela u izraz X+ 3. Dobio je jednakost 5 = 3 i zaključio da ova jednačina nema korijena. Da li je student u pravu?

9. Riješite jednačinu 2 / (2- x) - ½ = 4 / ((2- x)x); X? R... Je li broj 2 korijen ove jednadžbe?

10. Riješite jednadžbe koristeći odnos između komponenti i rezultata akcije:

a) ( X+ 70) 4 = 328; c) (85 X + 765): 170 = 98;

b) 560: ( X+ 9) - 56; G) ( X - 13581):709 = 306.

11. Riješite probleme koristeći aritmetičke i algebarske metode:

a) Prva polica ima 16 knjiga više od druge. Ako uklonite 3 knjige sa svake police, tada će na prvoj polici biti jedan i pol puta više knjiga nego na drugoj. Koliko knjiga ima na svakoj polici?

b) Biciklista je put od kampa do stanice, koja je 26 km, prešao za 1 sat i 10 minuta. Prvih 40 minuta ovog vremena vozio je istom brzinom, a ostatak vremena - brzinom od 3 km / h manjom. Pronađite brzinu bicikliste na prvom dijelu staze.

Definicija. Dvije formule algebre logike A i B su pozvani ekvivalent, ako uzimaju iste logičke vrijednosti na bilo kojem skupu vrijednosti uključenih u formule elementarnih iskaza.

Ekvivalentnost formula će biti označena znakom i notacijom A V znači da su formule A i B su ekvivalentni.

Na primjer, formule su ekvivalentne:

Formula A se zove identično istinito (ili tautologija) ako uzima vrijednost 1 za sve vrijednosti varijabli uključenih u njega.

Na primjer, formule , .

Formula A pozvao identično lažno, ako uzima vrijednost 0 za sve vrijednosti varijabli uključenih u njega.

Na primjer, formula je identično netačna.

Jasno je da je relacija ekvivalencije refleksivna, simetrična i tranzitivna.

Postoji sljedeća veza između pojmova ekvivalencije i ekvivalencije: ako su formule A i V su ekvivalentni, onda formula A V- tautologija, i obrnuto, ako je formula A V- tautologija, zatim formule A i V su ekvivalentni.

Najvažnije ekvivalencije algebre logike mogu se podijeliti u tri grupe.

1. Osnovne ekvivalencije:

Dokažimo jedan od zakona apsorpcije. Razmotrite formulu . Ako u ovoj formuli a= 1 tada, očigledno, i dok je konjunkcija dva istinita iskaza. Sada neka formula A x = 0. Ali tada će, po definiciji, operacija veznika biti lažna i konjunkcija . Dakle, u svim slučajevima, vrijednosti formule A odgovaraju vrijednostima a, i zbog toga A x.

2. Ekvivalenata koji izražavaju neke logičke operacije kroz druge:

Jasno je da se ekvivalentnosti 5 i 6 dobijaju iz ekvivalentnosti 3 i 4, ako uzmemo negative iz oba dijela potonjeg i koristimo zakon uklanjanja dvostrukih negativa. Dakle, prve četiri ekvivalentnosti trebaju dokaz. Dokažimo dva od njih: prvi i treći.

Budući da sa istim logičkim vrijednostima X i at formule,, su tačne, zatim konjunkcija . Stoga, u ovom slučaju, oba dijela ekvivalencije imaju iste prave vrijednosti.

Pusti sada X i at imaju različita logička značenja. Tada će ekvivalencija i jedna od dvije implikacije ili biti netačna. U isto vrijeme

bit će lažna i konjunkcija ... Dakle, u ovom slučaju, oba dijela ekvivalencije imaju iste logičke vrijednosti.

Razmotrite ekvivalentnost 3. Ako X i at uzeti prave vrijednosti u isto vrijeme, tada će konjunkcija biti istinita x & y i lažna negacija konjunkcije. Istovremeno, i i i biće lažni, a samim tim i disjunkcija .

Pustite sada barem jednu od varijabli X ili at poprima vrijednost false. Tada će konjunkcija biti lažna x & y i njegovo istinsko poricanje. U isto vrijeme, negacija barem jedne od varijabli bit će istinita, pa će stoga i disjunkcija također biti istinita .

Stoga, u svim slučajevima, oba dijela ekvivalencije 3 imaju iste logičke vrijednosti.

Slično se dokazuju ekvivalentnosti 2 i 4.

Iz ekvivalencija ove grupe slijedi da se bilo koja formula algebre logike može zamijeniti ekvivalentnom formulom koja sadrži samo dvije logičke operacije: konjunkciju i negaciju ili disjunkciju i negaciju.

Dalje isključivanje logičkih operacija je nemoguće. Dakle, ako koristimo samo konjunkciju, onda već takvu formulu kao negaciju X ne može se izraziti pomoću operacije veznika.

Međutim, postoje operacije pomoću kojih se može izraziti bilo koja od pet logičkih operacija koje koristimo. Takva operacija je, na primjer, Schaeffer Stroke operacija. Ova operacija je označena simbolom x | y a određen je sljedećom tablicom istinitosti:

x	y	x \| y

Očigledno, postoje ekvivalentnosti:

2) x & y (x | y) | (x | y).

Iz ove dvije ekvivalencije slijedi da se bilo koja formula algebre logike može zamijeniti ekvivalentnom formulom koja sadrži samo operaciju "Schaefferov potez".

Zapiši to.

Operacija se može unijeti na sličan način .

3. Ekvivalencije koje izražavaju osnovne zakone algebre logike:

1. x & y y & x - komutativnost konjunkcije.

2. x at y X- komutativna disjunkcija.

3. x & (y & z) (x & y) & z- asocijativnost veznika.

4. X(y z ) (X y) z-asocijativnost disjunkcije.

5. x & (y z) (x & y) (x & z)- distributivnost veznika u odnosu na disjunkciju.

6. X (y & z) (X y) & (x z ) - distributivnost disjunkcije u odnosu na konjunkciju.

Dokažimo posljednji od navedenih zakona. Ako X= 1, zatim formule X (y & z), X y, x z . Ali onda konjunkcija (X y) & (x z ). Dakle, za X= 1 oba dijela ekvivalencije 6 uzimaju iste logičke vrijednosti (tačno).

Pusti sada x = 0. Onda X (y & z) y & z, x at at i x z z , a samim tim i veznik X (y & z) y & z... Dakle, ovdje su obje strane ekvivalencije 6 ekvivalentne istoj formuli y & z, i stoga uzimaju iste logičke vrijednosti.

§ 5. Ekvivalentne transformacije formula

Koristeći ekvivalencije grupa I, II i III, moguće je zamijeniti dio formule ili formule ekvivalentnom formulom. Takve transformacije formula se nazivaju ekvivalentan.

Ekvivalentne transformacije se koriste za dokazivanje ekvivalencija, za dovođenje formula u dati oblik, za pojednostavljenje formula.

Formula A smatra se jednostavnijim od ekvivalentne formule V, ako sadrži manje slova, ima manje logičkih operacija. U ovom slučaju, operacije ekvivalencije i implikacije obično se zamjenjuju operacijama disjunkcije i konjunkcije, a negacija se naziva elementarnim iskazima. Pogledajmo neke primjere.

1. Dokažite ekvivalentnost .

Koristeći ekvivalencije grupa I, II i III

2. Pojednostavite formulu .

Zapišimo lanac ekvivalentnih formula:

3. Dokazati identitet formule

Zapišimo lanac ekvivalentnih formula:

Booleova algebra

Ekvivalencije grupe III ukazuju na to da algebra logike ima komutativne i asocijativne zakone u odnosu na operacije konjunkcije i disjunkcije i distributivni zakon konjunkcije u odnosu na disjunkciju; isti zakoni se također primjenjuju u algebri brojeva. Stoga se nad formulama algebre logike mogu izvršiti iste transformacije koje se provode u algebri brojeva (otvorene zagrade, stavljanje u zagrade, ostavljajući zajednički faktor izvan zagrada).

Ali u algebri logike, moguće su i druge transformacije zasnovane na korištenju ekvivalencija:

Ova karakteristika omogućava da se dođe do dalekosežnih generalizacija.

Razmotrite neprazan skup M elementi bilo koje prirode ( x, y, z, ...} , u kojoj je definirana relacija "=" (jednako) i tri operacije: "+" (sabiranje), "" (množenje) i "-" (negacija), poštujući sljedeće aksiome:

Komutativni zakoni:

1a. x + y = y + x, 1b. X y = y X.

Asocijativni zakoni:

2a. x + (y + z)= (x + y) + z, 2b. X (u z) = (x y) z.

Distributivni zakoni:

3a. (x + y) z = (x z ) + (g G) 3b. (x y) + z = (x + z) (y + z).

Zakoni idempotencije:

4a. x + x = x, 4b. X x = x.

Zakon dvostruke negacije:

De Morganovi zakoni:

6a. , 6b . .

Zakoni apsorpcije:

7a. x + (y X)= X, 7b. X (y + x) = x.

Toliko M pozvao Bulova algebra.

Ako je ispod glavnih elemenata x, y, z, ... znači iskaze, operacijama "+", "", "-" disjunkcija, konjunkcija, negacija, respektivno, a znak jednakosti se smatra znakom ekvivalencije, tada, kako slijedi iz ekvivalencije grupa I, II i III , svi aksiomi Bulove algebre su zadovoljeni.

U onim slučajevima kada je za određeni sistem aksioma moguće odabrati određene objekte i specifične odnose između njih tako da su svi aksiomi zadovoljeni, kažu da je pronađeno interpretacija(ili model) ovaj sistem aksioma.

Dakle, Bulova algebra je interpretacija Bulove algebre. Booleova algebra ima i druga tumačenja. Na primjer, ako je ispod glavnih elemenata x, y, z, ... mnoštvo M da označavamo skupove, pod operacijama "+", "", "-" unija, presek, sabiranje, respektivno, i pod znakom jednakosti - znak jednakosti skupova, onda dolazimo do algebre skupova. Lako je provjeriti da u algebri skupova vrijede svi aksiomi Bulove algebre.

Među različitim tumačenjima Bulove algebre, postoje i tumačenja tehničke prirode. O jednom od njih će biti riječi u nastavku. Kao što će biti prikazano, ona igra važnu ulogu u modernoj automatizaciji.

Funkcije Bulove algebre

Kao što je već napomenuto, značenje formule algebre logike u potpunosti ovisi o vrijednostima iskaza uključenih u ovu formulu. Prema tome, formula algebre logike je funkcija elementarnih iskaza uključenih u nju.

Na primjer, formula je funkcija

tri varijable f (x, y, z). Karakteristika ove funkcije je činjenica da njeni argumenti imaju jednu od dvije vrijednosti: nulu ili jedan, a funkcija također uzima jednu od dvije vrijednosti: nulu ili jedan.

Definicija. Funkcija Booleove algebre ha varijable (ili Boolean funkcija) poziva se funkcija od m varijabli, gdje svaka varijabla uzima dvije vrijednosti: 0 i 1, a funkcija može uzeti samo jednu od dvije vrijednosti: 0 ili 1.

Jasno je da su identično istinite i identično lažne formule algebre logike konstantne funkcije, a dvije ekvivalentne formule izražavaju istu funkciju.

Hajde da saznamo koliki je broj funkcija od n varijabli. Očigledno, svaka funkcija algebre logike (kao i formula algebre logike) može se specificirati pomoću tablice istinitosti, koja će sadržavati 2 n reda. Dakle, svaka funkcija od n varijabli uzima 2 n vrijednosti koje se sastoje od nula i jedinica. Dakle, funkcija od n varijabli je u potpunosti određena skupom vrijednosti nula i jedinica dužine 2 n. (Ukupan broj skupova koji se sastoje od nula i jedinica dužine 2 n je jednak. Dakle, broj različitih funkcije Bulove algebre P varijable je jednaka.

Konkretno, postoje četiri različite funkcije jedne varijable i šesnaest različitih funkcija dvije varijable. Napišimo sve funkcije algebre logike jedinice i dvije varijable.

Razmotrimo tablicu istinitosti za različite funkcije jedne varijable. Očigledno izgleda ovako:

x	f 1 (x)	f 2 (x)	f 3 (x)	f 3 (x)
1

Iz ove tabele sledi da će dve funkcije jedne varijable biti konstantne: f 1 (x) = 1, f 4 (x) = 0, i f 2 (x) X, i f 3 (x) .

Tabela istinitosti za sve moguće funkcije dvije varijable je:

f i = f i (x, y)

f 1

f 2

f 3

f 4

f 5

f 6

f 7

f 8

f 9

f 10

f 11

f 12

f 13

f 14

f 15

f 16

Jasno je da se analitički izrazi za ove funkcije mogu napisati na sljedeći način.

Otvorena lekcija iz matematike "Bernoulijeva šema. Rješavanje zadataka prema Bernulijevoj i Laplaceovoj shemi"

Didaktika: sticanje vještina i sposobnosti za rad sa Bernoullijevom šemom za izračunavanje vjerovatnoća.

Razvijanje: razvijanje vještina primjene znanja u praksi, formiranje i razvoj funkcionalnog mišljenja učenika, razvijanje sposobnosti poređenja, analize i sinteze, vještina rada u paru, proširenje stručnog rječnika.

Kako možete igrati ovu igru:

Obrazovni: podsticanje interesa za predmet kroz praktičnu primjenu teorije, postizanje svjesne asimilacije nastavnog materijala učenika, formiranje sposobnosti za timski rad, pravilnu upotrebu kompjuterski pojmovi, interesovanje za nauku, poštovanje buduće profesije.

Naučni karakter znanja: B

Vrsta lekcije: kombinovani čas:

konsolidacija gradiva položenog u prethodnim časovima;
tematska, informaciono-problemska tehnologija;
generalizacija i konsolidacija gradiva proučavanog u ovoj lekciji.

Način izvođenja nastave: eksplanatorno - ilustrativna, problematična.

Kontrola znanja: frontalni pregled, rješavanje problema, prezentacija.

Materijalno-tehnička opremljenost časa. kompjuter, multimedijalni projektor.

Metodička podrška: referentni materijali, prezentacija na temu časa, ukrštenica.

Tokom nastave

1. Organizacioni momenat: 5 min.

(pozdrav, spremnost grupe za čas).

2. Testiranje znanja:

Provjeri pitanja frontalno na slajdovima: 10 min.

definicije odjeljka "Teorija vjerovatnoće"
glavni koncept sekcije "Teorija vjerovatnoće"
koje događaje proučava "Teorija vjerovatnoće"?
karakteristika slučajnog događaja
klasična definicija vjerovatnoća

Rezimirajući. 5 minuta.

3. Rješavanje zadataka u redovima: 5 min.

Problem 1. Bačena je kocka. Kolika je vjerovatnoća da će se oboriti par i manje od 5 bodova?

Problem 2. U kutiji se nalazi devet identičnih radio cijevi, od kojih su tri bile u upotrebi. U toku radnog dana, predradnik je morao da uzme dve radio cevi da popravi opremu. Koja je vjerovatnoća da su obje uzete lampe bile u upotrebi?

Zadatak 3. U tri sale kina prikazuju se tri različita filma. Verovatnoća da na blagajni 1. sale ima ulaznica za određeni sat je 0,3, na blagajni 2. sale - 0,2, a na blagajni 3. sale - 0,4. Kolika je vjerovatnoća da je u datom satu moguće kupiti kartu za barem jedan film?

4. Provjera načina rješavanja zadataka na tabli. Dodatak 1,5 min.

5. Zaključak o rješavanju problema:

Vjerovatnoća nastanka događaja je ista za svaki zadatak: m i n - konst

6. Postavljanje ciljeva kroz zadatak: 5 min.

Zadatak. Dva ekvivalentna šahista igraju šah. Kolika je vjerovatnoća pobjede u dvije od četiri utakmice?

Kolika je vjerovatnoća pobjede u tri od šest gema (remi se ne uzimaju u obzir)?

Pitanje. Razmislite i navedite po čemu se pitanja ovog zadatka razlikuju od pitanja prethodnih zadataka?

Rasuđivanje, upoređivanje da se dobije odgovor: u pitanjima m i n se razlikuju.

7. Tema lekcije:

Proračun vjerovatnoće pojave događaja k puta iz n eksperimenata sa p-konst.

Ako se provode testovi u kojima vjerovatnoća pojave događaja A u svakom testu ne zavisi od ishoda drugih testova, onda se takvi testovi nazivaju nezavisni od događaja A. Testovi u svakom od kojih je vjerovatnoća pojave događaja isto.

Bernulijeva formula. Vjerovatnoća da je u n nezavisnih ispitivanja, u svakom od kojih je vjerovatnoća pojave događaja p (0

ili Dodatak 2 Bernulijeva formula, gdje su k, n mali brojevi gdje je q = 1-p

Rešenje: igraju ekvivalentni šahisti, pa je verovatnoća pobede p = 1/2; stoga je vjerovatnoća gubitka q također 1/2. Budući da je u svim partijama vjerovatnoća pobjede konstantna i nije bitno kojim će redoslijedom igre biti dobijene, primjenjiva je Bernoullijeva formula. 5 minuta

Nađimo vjerovatnoću da će dvije od četiri utakmice biti dobijene:

Nađimo vjerovatnoću da će tri utakmice od šest biti dobijene:

Budući da je P4 (2)> P6 (3), veća je vjerovatnoća da će pobijediti dvije utakmice od četiri nego tri od šest.

8. Zadatak.

Nađite vjerovatnoću da će se događaj A dogoditi tačno 70 puta u 243 testa ako je vjerovatnoća da se ovaj događaj dogodi u svakom testu 0,25.

k = 70, n = 243 Otuda su k i n veliki brojevi. To znači da je teško računati koristeći Bernoullijevu formulu. Za takve slučajeve primjenjuje se lokalna Laplaceova formula:

Dodatak 3 za pozitivne vrijednosti x dat je u Dodatku 4; za negativne vrijednosti x koristite istu tablicu i =.