Dva jednaka protivnika igraju šah. Ekvivalentne transformacije. Pojednostavljivanje formula. Savršene normalne forme
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. skupovi njihovih korijena se poklapaju.
Definicija. Zamjena jednačine ekvivalentnom jednačinom naziva se ekvivalentna transformacija.
Hajde sada da saznamo koje nam transformacije omogućavaju da dobijemo ekvivalentne jednačine.
Teorema 1. Neka jednačina f(x) i g(x) definisano 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 jednadžbe (2). Tada će jednačine (1) i (2) biti ekvivalentne ako T 1 = T 2. Da biste to potvrdili, 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- 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. Dodajmo 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) i korijen jednačine (2), tj. T 1 With T 2.
Pusti to 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). Dodajmo na obje strane ove jednakosti numerički izraz - h(a), Dobijamo pravu numeričku 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) 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 obje strane jednačine s domenom definicije X dodamo isti izraz sa promenljivom definisanom na istom skupu, onda dobijamo novu jednačinu ekvivalentnu datoj.
Iz ove teoreme slijede posljedice koje se koriste pri rješavanju jednačina:
1. Ako na obje strane jednačine dodamo isti broj, dobićemo jednačinu koja je ekvivalentna datoj.
2. Ako se bilo koji pojam (numerički izraz ili izraz sa promjenljivom) prenese iz jednog dijela jednačine u drugi, mijenjajući predznak člana u suprotan, onda se dobija jednačina ekvivalentna datoj.
Teorema 2. Neka jednačina f(x) = g(x) definisano na setu X I h(x) - izraz koji je definiran na istom skupu i ne nestaje ni za jednu vrijednost X od mnogih 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 obje strane jednačine imaju domen X pomnoženo sa istim izrazom, koji je definisan na istom skupu i na njemu ne nestaje, dobijamo novu jednačinu ekvivalentnu datoj.
Iz ove teoreme slijedi posljedica: Ako se obje strane jednačine pomnože (ili podijele) sa istim brojem koji nije nula, dobićemo 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 a mi ćemo opravdati sve transformacije koje ćemo izvršiti u procesu rješenja.
| Transformacije | Obrazloženje za transformaciju |
| 1. Dovedemo izraze s lijeve i desne strane jednačine na zajednički nazivnik: (6-2 X)/ 6 = X/6 | Izvršili smo identičnu transformaciju izraza na lijevoj strani jednačine. |
| 2. Odbacimo zajednički imenilac: 6-2 X = X | Pomnožili smo obje strane jednačine sa 6 (teorema 2) i dobili jednačinu koja je ekvivalentna ovoj. |
| 3. Prenosimo izraz -2x na desnu stranu jednačine sa suprotnim predznakom: 6 = X+2X. | Koristili smo korolar teoreme 1 i dobili jednačinu koja je ekvivalentna prethodnoj, a samim tim i datoj. |
| 4. Slične članove predstavljamo na desnoj strani jednačine: 6 = 3 X. | Izvršio transformaciju identiteta izraza. |
| 5. Podijelite obje strane jednačine sa 3: X = 2. | Koristili smo korolar iz teoreme 2 i dobili jednačinu ekvivalentnu prethodnoj, a samim tim i ovoj |
Pošto su sve transformacije koje smo izvršili prilikom rješavanja ove jednačine bile ekvivalentne, možemo reći da je 2 korijen ove jednačine.
Ako se u procesu rješavanja jednadžbe ne ispune uvjeti iz 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 datoj.
Razmotrite, na primjer, jednačinu x(x - 1) = 2x, x? R. Podijelimo oba dijela sa X, dobijamo jednačinu X - 1 = 2, odakle X= 3, tj. ova jednačina ima jedan korijen - broj 3. Ali da li je to istina? Lako je vidjeti da ako u ovoj jednačini umjesto varijable X zamjenom 0, pretvara 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 sa X, one. pomnoženo izrazom1/ x, ali u X= Oh, nema smisla. Posljedično, nismo ispunili uvjet iz teoreme 2, što je dovelo do gubitka korijena.
Kako bismo bili sigurni da se skup korijena ove jednadžbe sastoji od dva broja 0 i 3, predstavljamo još jedno rješenje. Pomerimo izraz 2 X s desna na lijevo: x(x- 1) - 2x = 0. Izvadimo to iz zagrada na lijevoj strani jednačine X i dajte slične uslove: 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. Odavde vidimo da su korijeni ove jednadžbe 0 i 3.
Na početnom kursu matematike teorijske osnove rješavanje jednačina je odnos između komponenti i rezultata radnji. Na primjer, rješavanje jednadžbe ( X·9):24 = 3 je opravdano na sljedeći način. Budući da je nepoznata u dividendi, da biste pronašli dividendu, trebate pomnožiti djelitelj 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 u jednoj varijabli:
A) ( X-3) 5 = 12 X; d) 3 + (12-7) 5 = 16;
b) ( X-3) 5 = 12; d) ( 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 definisano na skupu prirodni brojevi. Objasnite zašto je broj 1 korijen ove jednadžbe, ali 2 i -1 nisu njeni korijeni.
3. U jednadžbi ( 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. Odredite koji od sljedećih parova jednačina 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čine. Koje od njih 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. Učenik je riješio jednačinu 5 X + 15 = 3 X+ 9 na sljedeći način: uzeo sam broj 5 iz zagrada na lijevoj strani i broj 3 na desnoj i dobio sam jednačinu 5(x+ 3) = 3(X+ 3), a zatim podijelio obje strane u izraz X+ 3. Dobio sam jednakost 5 = 3 i zaključio da ova jednačina nema korijena. Da li je učenik u pravu?
9. Riješite jednačinu 2/(2- x) – ½ = 4/((2- x)x); X? R. Da li je broj 2 korijen ove jednadžbe?
10. Riješite jednadžbe koristeći odnos između komponenti i rezultata radnji:
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) Na prvoj polici ima 16 knjiga više nego na drugoj. 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 cijelu udaljenost od kampa do stanice, jednaku 26 km, prešao za 1 sat i 10 minuta. Prvih 40 minuta ovog vremena vozio je jednom brzinom, a ostatak vremena 3 km/h manjom. Pronađite brzinu bicikliste na prvom dijelu putovanja.
Odjeljak 2. Logička ekvivalencija formula. Normalni oblici za formule propozicione algebre
Relacija ekvivalencije
Koristeći tablice istinitosti, možete ustanoviti za koje skupove istinitih vrijednosti ulaznih varijabli formula će uzeti tačnu ili lažnu vrijednost (kao i iskaz koji ima odgovarajuću logičku strukturu), koje će formule biti tautologije ili kontradikcije, i također odrediti da li su dvije date formule ekvivalentno.
U logici se kaže da su dvije rečenice ekvivalentne ako su obje istinite ili netačne. Riječ "istovremeno" u ovoj frazi je dvosmislena. Tako, 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 jednačine" x = 2" i " 2x = 4""istovremeno" znači "pri istim vrijednostima varijable." Predviđanja „Sutra će padati kiša“ i „Nije tačno da sutra neće padati kiša“ istovremeno će se potvrditi (ispostaviti se istinitim) ili ne potvrditi (ispostaviti se lažnim). U suštini, ovo je ista prognoza izražena u dva različita oblika, koja se mogu predstaviti formulama X i . Ove formule su i istinite i netačne. Da biste provjerili, dovoljno je napraviti tabelu istinitosti:
| X | ||
| 1 | 0 | 1 |
| 0 | 1 | 0 |
Vidimo da se vrijednosti istine u prvom i posljednjem stupcu poklapaju. Prirodno je smatrati da su takve formule, kao i odgovarajuće rečenice, ekvivalentne.
Za formule F 1 i F 2 se kaže da su ekvivalentne ako je njihov ekvivalent tautologija.
Ekvivalencija dvije formule se piše na sljedeći način: (čitaj: formula F 1 je ekvivalentno formuli F 2).
Postoje tri načina da se proveri da li su formule ekvivalentne: 1) kreirajte njihov ekvivalent i koristite tabelu istinitosti da biste proverili da li je tautologija; 2) za svaku formulu napravite tabelu istinitosti i uporedite konačne rezultate; ako u rezultirajućim stupcima sa istim skupovima vrijednosti varijabli istinite vrijednosti obje formule su jednake, tada su formule ekvivalentne; 3) korištenjem ekvivalentnih transformacija.
Primjer 2.1: Saznajte da li su formule ekvivalentne: 1) , ; 2) , .
1) Upotrijebimo prvi metod za određivanje ekvivalencije, odnosno otkrićemo da li je ekvivalencija formula također tautologija.
Kreirajmo ekvivalentnu formulu: . Rezultirajuća formula sadrži dvije različite varijable ( A I IN) 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 | IN | ||||||
| 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 jasno je da je konstruisana ekvivalencija tautologija i, prema tome, .
2) Da bismo saznali jesu li formule ekvivalentne, koristimo drugu metodu, odnosno sastavljamo tablicu istinitosti za svaku od formula i upoređujemo rezultirajuće stupce. ( Komentar. Da bi se drugi metod efikasno koristio, potrebno je da sve sastavljene tabele istinitosti počinju isto, tj skupovi vrijednosti varijabli bili su isti u odgovarajućim redovima .)
Formula sadrži dvije različite varijable i 2 operacije, što znači da odgovarajuća tablica istinitosti ima 5 redaka i 4 stupca:
| A | IN | ||
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
Formula sadrži dvije različite varijable i 3 operacije, što znači da odgovarajuća tablica istinitosti ima 5 redova i 5 stupaca:
| A | IN | |||
| 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
Upoređujući rezultujuće kolone kompajliranih tabela istinitosti (pošto tabele počinju isto, ne možemo obratiti pažnju na skupove vrijednosti varijabli), vidimo da se ne podudaraju 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) tranzitivan: ako i , onda .
Zakoni logike
Često se nazivaju ekvivalentnosti propozicionih logičkih formula zakonima logike. Navodimo najvažnije od njih:
1. – zakon identiteta.
2. – zakon isključene sredine
3. – zakon protivrečnosti
4. – disjunkcija sa nulom
5. – konjunkcija sa nulom
6. – disjunkcija sa jedinstvom
7. – spoj s jednim
8. – zakon dvostruke negacije
9. – komutativnost konjunkcije
10. – komutativnost disjunkcije
11. – asocijativnost veznika
12. – asocijativnost disjunkcije
13. – distributivnost veznika
14. – distributivnost disjunkcije
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 identične istinitosti ili neistinitosti formula.
Ekvivalentne transformacije. Pojednostavljivanje formula
Ako se svugdje ista formula umjesto neke varijable zamijeni u ekvivalentne formule, tada će se i novodobivene formule pokazati ekvivalentnim u skladu s pravilom zamjene. Na ovaj način, iz svake ekvivalencije može se dobiti onoliko novih ekvivalencija koliko želite.
Primjer 1: Umjesto toga u De Morganovom zakonu X zamjena i umjesto toga Y zamjena, dobijamo novu ekvivalentnost. Valjanost rezultirajuće ekvivalencije može se lako provjeriti korištenjem tablice istinitosti.
Ako je bilo koja formula koja je dio formule F, zamijenite formulom koja je ekvivalentna formuli , tada će rezultirajuća formula biti ekvivalentna formuli F.
Tada se za formulu iz primjera 2 mogu izvršiti sljedeće zamjene:
– zakon dvostruke negacije;
- De Morganov zakon;
– zakon dvostruke negacije;
– zakon asocijativnosti;
– zakon idempotencije.
Svojstvom tranzitivnosti relacije ekvivalencije možemo to reći 
.
Zamjena jedne formule drugom koja je njoj ekvivalentna se zove ekvivalentna transformacija formule.
Ispod pojednostavljenje formule koje ne sadrže znakove implikacije i ekvivalencije shvaćaju se kao ekvivalentna transformacija koja vodi do formule koja ne sadrži negacije neelementarnih formula (posebno dvostrukih negativa) ili sadrži ukupno manji broj znakova konjunkcije i disjunkcije od originalni.
Primjer 2.2: Hajde da pojednostavimo formulu 
.
U prvom koraku primijenili smo zakon koji pretvara implikaciju u disjunkciju. U drugom koraku primijenili smo komutativni zakon. U trećem koraku primijenili smo zakon idempotencije. Četvrti je De Morganov zakon. I peti je 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. Za ovo ovu formulu potrebno je ekvivalentnim transformacijama dovesti do jedne od formula, a to su tautologije.
Napomena 2. Neke tautologije i ekvivalencije se kombinuju u parove (zakon kontradikcije i zakon alternativnih, komutativnih, asocijativnih zakona, itd.). Ove korespondencije otkrivaju tzv princip dualnosti .
Pozivaju se dvije formule koje ne sadrže znakove implikacije i ekvivalencije dual , ako se svaki od njih može dobiti od drugog zamjenom znakova 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.
Koristeći poznate zakone logike, bilo koja formula se može transformirati 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 pojedinačnih različitih logičkih varijabli sa ili bez predznaka negacije.
Primjer 2.3: U velikim formulama ili tokom višestrukih transformacija, 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 pojedinačni DNF element elementarna konjunkcija ili sastavni dio 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 predznaka negacije. 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
(KNF).
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čne karakteristike 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 karakteristike (ali ne i forme!) zadovoljavaju definiciju dualnosti, pa je dovoljno razumjeti jedan oblik da bismo naučili kako dobiti oba.
Iz DNF (CNF) korištenjem ekvivalentnih transformacija lako se može dobiti SDNF (SKNF). Pošto 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 SCNF-a koristeći definiciju dualnosti.
Opšte pravilo dovodeći formulu u SDNF koristeći ekvivalentne transformacije:
Da bi se dala formula F, što nije identično lažno, za SDNF, dovoljno je:
1) dovesti je do neke vrste DNF-a;
2) ukloniti uslove disjunkcije koja sadrži promenljivu zajedno sa njenom negacijom (ako postoji);
3) ukloni sve identične uslove 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 dobijena disjunkcija sadrži identične termine, koristite recept 3.
Rezultirajuća formula je SDNF ove formule.
Primjer 2.7: Nađimo SDNF i SCNF za formulu 
.
Pošto 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 drugoj elementarnoj konjunkciji nedostaje varijabla z, pa dodajmo mu člana i primijenimo distributivni zakon: ;
6) lako je uočiti da su se u disjunkciju pojavili identični termini, pa jedan uklanjamo (recept 3);
3) ukloniti jednu od identičnih disjunkcija: 
;
4) preostale disjunkcije nemaju identične termine;
5) nijedna od elementarnih disjunkcija ne sadrži sve varijable uključene u originalnu formulu, pa hajde da svaku od njih dopunimo konjunkcijom: ;
6) u nastaloj konjunkciji nema identičnih disjunkcija, stoga je pronađeni oblik veznika savršen.
Budući da su u zbiru formule SKNF i SDNF F 8 članova, onda su najvjerovatnije pronađeni ispravno.
Svaka izvodljiva (falsifikabilna) formula ima jedan jedinstveni SDNF i jedan jedinstveni SCNF. Tautologija nema SKNF, ali kontradikcija nema SKNF.
Definicija. Dvije formule logičke algebre A i B su pozvani ekvivalent, ako uzimaju iste logičke vrijednosti na bilo kojem skupu vrijednosti uključenih u formule elementarnih iskaza.
Ekvivalenciju formula ćemo označiti znakom i notacijom A IN 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 su također istinite , .
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 IN su ekvivalentne, onda formula A IN- tautologija, i obrnuto, ako je formula A IN- tautologija, zatim formule A I IN su ekvivalentni.
Najvažnije ekvivalencije algebre logike mogu se podijeliti u tri grupe.
1. Osnovne ekvivalencije:
Hajde da dokažemo jedan od zakona apsorpcije. Razmotrite formulu . Ako u ovoj formuli A= 1 tada, očigledno, a zatim kao konjunkcija dva tačna iskaza. Hajde sada u formulu A x = 0. Ali tada, prema definiciji operacije konjunkcije, konjunkcija će također biti lažna . Dakle, u svim slučajevima vrijednosti formule A odgovaraju vrijednostima A, i zbog toga A x.
2. Ekvivalencije koje izražavaju neke logičke operacije kroz druge:
Jasno je da se ekvivalentnosti 5 i 6 dobijaju iz ekvivalencije 3 i 4, respektivno, ako uzmemo negacije iz oba dijela potonjeg i koristimo zakon uklanjanja dvostrukih negacija. Dakle, prve četiri ekvivalencije trebaju dokaz. Dokažimo dva od njih: prvi i treći.
Pošto sa istim logičkim vrijednostima X I at ako su formule , , , tačne, tada će i konjunkcija biti istinita 
.
Stoga, u ovom slučaju, obje strane ekvivalencije imaju iste prave vrijednosti.
Pusti to sada X I at imaju različite logičke vrijednosti. Tada će ekvivalencija i jedna od dvije implikacije ili biti netačna. U isto vrijeme
konjunkcija će biti lažna . Dakle, u ovom slučaju, obje strane ekvivalencije imaju isto logičko značenje.
Razmotrite ekvivalentnost 3. Ako X I at istovremeno poprimiti prave vrijednosti, tada će konjunkcija biti istinita x&y i lažna negacija veznika. U isto vrijeme, i i biće lažno, i stoga će disjunkcija također biti lažna .
Neka sada barem jedna od varijabli X ili at procjenjuje na false. Tada će konjunkcija biti lažna x&y i njegovu istinsku negaciju. 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, obje strane ekvivalencije 3 uzimaju iste logičke vrijednosti.
Ekvivalencije 2 i 4 se dokazuju na sličan način.
Iz ekvivalencija ove grupe slijedi da se bilo koja formula u algebri logike može zamijeniti ekvivalentnom formulom koja sadrži samo dvije logičke operacije: konjunkciju i negaciju ili disjunkciju i negaciju.
Nije moguće dalje eliminisanje logičkih operacija. Dakle, ako koristimo samo konjunkciju, onda takvu formulu kao negaciju X ne može se izraziti pomoću operatora veznika.
Međutim, postoje operacije kojima se može izraziti bilo koja od pet logičkih operacija koje koristimo. Takva operacija je, na primjer, operacija "Schefferov udar". 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 u algebri logike može zamijeniti ekvivalentnom formulom koja sadrži samo operaciju “Schaeffer stroke”.
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- komutativnost disjunkcije.
3. x&(y&y) (x&y)&z- asocijativnost veznika.
4. X(y z ) (X y) z je asocijativnost disjunkcije.
5. x&(y z) (x&y) (x&z)- distributivnost konjunkcije 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, tada će formule biti tačne X (y& z), X y, x z . Ali tada će i konjunkcija biti istinita (X y)& (x z ). Dakle, kada X= 1, obje strane ekvivalencije 6 uzimaju iste logičke vrijednosti (tačno).
Pusti to 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 ekvivalentnosti grupa I, II i III, dio formule ili formule možete zamijeniti ekvivalentnom formulom. Takve transformacije formula se nazivaju ekvivalentno.
Ekvivalentne transformacije se koriste za dokazivanje ekvivalencija, za dovođenje formula u dati oblik, za pojednostavljenje formula.
Formula A smatra se jednostavnijim od njegove ekvivalentne formule IN, ako sadrži manje slova, manje logičkih operacija. U ovom slučaju, operacije ekvivalencije i implikacije obično se zamjenjuju operacijama disjunkcije i konjunkcije, a negacija se klasificira kao elementarni iskazi. Pogledajmo nekoliko primjera.
1. Dokazati ekvivalenciju 
.
Koristeći ekvivalencije grupa I, II i III
2.
Pojednostavite formulu 
.
Napišimo lanac ekvivalentnih formula:
3. Dokažite identičnu istinitost formule
Napišimo lanac ekvivalentnih formula:
Boolean algebra
Ekvivalencije grupe III ukazuju da algebra logike ima komutativne i asocijativne zakone u vezi sa operacijama konjunkcije i disjunkcije i distributivni zakon konjunkcije u pogledu disjunkcije; isti zakoni važe i u algebri brojeva. Stoga se na formulama algebre logike mogu izvesti iste transformacije koje se provode u algebri brojeva (otvaranje zagrada, stavljanje u zagrade, stavljanje zajedničkog faktora iz zagrada).
Ali u algebri logike moguće su i druge transformacije, zasnovane na korištenju ekvivalencija:
Ova karakteristika nam omogućava da dođemo do dalekosežnih generalizacija.
Razmotrimo neprazan skup M elementi bilo koje prirode ( x,y,z,...} , u kojoj su definirani relacija “=” (jednako) i tri operacije: “+” (sabiranje), “ ” (množenje) i “-” (negacija), podložno sljedećim aksiomima:
Komutativni zakoni:
1a. x + y = y + x, 1b. X y = y X.
Zakoni o udruženjima:
2a. x + (y + z)= (x + y) + z, 2b. X (g 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 Boolean algebra.
Ako je ispod glavnih elemenata x, y, z, ... Ako se na iskaze podrazumijevaju operacije “+”, “ ”, “-” disjunkcija, konjunkcija, negacija, respektivno, a znak jednakosti se smatra znakom ekvivalencije, onda, 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 svi aksiomi budu zadovoljeni, kažu da je pronađeno interpretacija(ili model) ovog sistema aksioma.
To znači da je algebra logike interpretacija Bulove algebre. Boole algebra ima i druga tumačenja. Na primjer, ako je ispod glavnih elemenata x, y, z, ... setovi M mislimo na skupove, pod operacijama “+”, “ ”, “-” unija, presek, sabiranje, respektivno, a pod znakom jednakosti - znak jednakosti skupova, onda dolazimo do algebre skupova. Nije teško provjeriti da su u algebri skupova zadovoljeni svi aksiomi Boole algebre.
Među različitim interpretacijama Bulove algebre, postoje tumačenja tehničke prirode. O jednom od njih će biti riječi u nastavku. Kao što će se pokazati, igra važnu ulogu u modernoj automatizaciji.
Funkcije logičke algebre
Kao što je već napomenuto, značenje formule logičke algebre u potpunosti zavisi od značenja iskaza uključenih u ovu formulu. Stoga je formula algebre logike funkcija elementarnih iskaza uključenih u nju.
Na primjer, formula je funkcija
tri varijable f(x,y,z). Posebnost ove funkcije je činjenica da njeni argumenti uzimaju jednu od dvije vrijednosti: nulu ili jedan, a istovremeno funkcija uzima i jednu od dvije vrijednosti: nulu ili jedan.
Definicija. Funkcija logičke algebre hektara varijabli (ili Boolean funkcija) naziva se funkcija ha 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 identično istinite i identično lažne formule algebre logike predstavljaju konstantne funkcije, i 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 nula i jedinica dužine 2 n je jednak . To znači da je broj različite funkcije algebre logike P varijable su jednake .
Konkretno, postoje četiri različite funkcije jedne varijable i šesnaest različitih funkcija dvije varijable. Zapišimo sve funkcije algebre logike u jednu I dvije varijable.
Razmotrimo tablicu istinitosti za različite funkcije jedne varijable. Očigledno izgleda ovako:
| x | f 1 (x) | f2(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, a f2(x) X, I f 3 (x) .
Tabela istinitosti za sve moguće funkcije dvije varijable ima oblik:
f i = f i (x,y)
| 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 ovih funkcija mogu napisati na sljedeći način.
Omogućava vam prelazak sa jednadžbe koja se rješava na tzv ekvivalentne jednačine I korolarne jednačine, iz čijih rješenja je moguće odrediti rješenje izvorne jednačine. U ovom članku ćemo detaljno analizirati koje se jednadžbe nazivaju ekvivalentne, a koje korolarne jednadžbe, dati odgovarajuće definicije, dati primjere objašnjenja i objasniti kako pronaći korijene jednadžbe koristeći poznate korijene ekvivalentne jednadžbe i posljedične jednačine .
Ekvivalentne jednadžbe, definicije, primjeri
Hajde da definišemo ekvivalentne jednačine.
Definicija
Ekvivalentne jednačine- to su jednačine koje imaju iste korijene ili nemaju korijene.
Definicije koje su iste po značenju, ali se malo razlikuju po formulaciji, date su u raznim udžbenicima matematike, npr.
Definicija
Dvije jednadžbe f(x)=g(x) i r(x)=s(x) nazivaju se ekvivalentno, ako imaju iste korijene (ili, posebno, ako obje jednačine nemaju korijen).
Definicija
Jednačine koje imaju iste korijene nazivaju se ekvivalentne jednačine. Jednačine koje nemaju korijen se također smatraju ekvivalentnim.
Pod istim korijenima podrazumijeva se sljedeće: ako je neki broj korijen jedne od ekvivalentnih jednačina, onda je i korijen bilo koje druge od ovih jednačina, a nijedna od ekvivalentnih jednačina ne može imati korijen koji nije korijen bilo koje druge od njih, ove jednadžbe.
Navedimo primjere ekvivalentnih jednačina. Na primjer, tri jednačine 4 x = 8, 2 x = 4 i x = 2 su ekvivalentne. Zaista, svaki od njih ima jedan korijen 2, tako da su po definiciji ekvivalentni. Drugi primjer: dvije jednačine x·0=0 i 2+x=x+2 su ekvivalentne, skupovi njihovih rješenja se poklapaju: korijen i prve i druge od njih je bilo koji broj. Dve jednačine x=x+5 i x 4 =−1 su takođe primeri ekvivalentnih jednačina; obe nemaju realna rešenja.
Da bismo upotpunili sliku, vrijedi dati primjere nejednakih jednačina. Na primjer, jednačine x=2 i x 2 =4 nisu ekvivalentne, jer druga jednačina ima korijen −2, koji nije korijen prve jednačine. Jednačine i također nisu ekvivalentne, jer su korijeni druge jednačine bilo koji brojevi, a broj nula nije korijen prve jednačine.
Navedena definicija ekvivalentnih jednačina odnosi se i na jednačine sa jednom promenljivom i na jednačine sa velikim brojem varijabli. Međutim, za jednačine sa dva, tri itd. varijabli, riječ “korijeni” u definiciji mora biti zamijenjena riječju “rješenja”. dakle,
Definicija
Ekvivalentne jednačine- to su jednačine koje imaju ista rješenja ili ih nemaju.
Pokažimo primjer ekvivalentnih jednačina sa nekoliko varijabli. x 2 +y 2 +z 2 =0 i 5 x 2 +x 2 y 4 z 8 =0 - evo primjera ekvivalentnih jednačina sa tri varijable x, y i z, obje imaju jedinstveno rješenje (0, 0 , 0) . Ali jednadžbe sa dvije varijable x+y=5 i x·y=1 nisu ekvivalentne, jer je, na primjer, par vrijednosti x=2, y=3 rješenje prve jednačine (kada se ove vrijednosti zamjenjuju u prvu jednačinu dobijamo tačnu jednakost 2+3=5), ali nije rješenje za drugu (prilikom zamjene ovih vrijednosti u drugu jednačinu dobijamo netačnu jednakost 2·3=1).
Jednačine posljedica
Evo definicija korolarnih jednačina iz školskih udžbenika:
Definicija
Ako je svaki korijen jednačine f(x)=g(x) istovremeno i korijen jednačine p(x)=h(x), tada se jednačina p(x)=h(x) naziva posljedica jednačine f(x)=g(x) .
Definicija
Ako su svi korijeni prve jednadžbe korijeni druge jednadžbe, onda se druga jednačina naziva posljedica prva jednačina.
Navedimo nekoliko primjera korolarnih jednačina. Jednačina x 2 =3 2 je posljedica jednačine x−3=0. Zaista, druga jednadžba ima jedan korijen x=3, ovaj korijen je također korijen jednačine x 2 =3 2, dakle, po definiciji, jednačina x 2 =3 2 je posljedica jednačine x−3= 0. Drugi primjer: jednadžba (x−2)·(x−3)·(x−4)=0 je posljedica jednačine 
, pošto su svi korijeni druge jednadžbe (ima ih dva, to su 2 i 3) očito korijeni prve jednačine.
Iz definicije korolarne jednadžbe slijedi da je apsolutno svaka jednačina posljedica bilo koje jednačine koja nema korijen.
Vrijedi navesti nekoliko prilično očiglednih posljedica iz definicije ekvivalentnih jednačina i definicije posljedične jednačine:
- Ako su dvije jednadžbe ekvivalentne, onda je svaka od njih posljedica druge.
- Ako je svaka od dvije jednačine posljedica druge, onda su ove jednačine ekvivalentne.
- Dvije jednadžbe su ekvivalentne ako i samo ako je svaka od njih posljedica druge.
1. Dva jednaka igrača igraju igru u kojoj nema nerešenih rezultata. Kolika je vjerovatnoća da prvi igrač pobijedi: a) jednu od dvije igre? b) dva od četiri? c) tri od šest?
odgovor: A) ; b) ; V)
3. Segment AB odvojeno tačkom WITH u omjeru 2:1. Četiri boda se nasumično bacaju na ovaj segment. Nađite vjerovatnoću da će dva od njih biti lijevo od tačke C, a dva - desno.
odgovor:
4. Nađite vjerovatnoću da će se događaj A dogoditi tačno 70 puta u 243 pokušaja ako je vjerovatnoća da će se ovaj događaj dogoditi u svakom pokušaju 0,25.
odgovor: .
5. Vjerovatnoća da ćete imati dječaka je 0,515. Naći vjerovatnoću da će među 100 novorođenčadi biti jednak broj dječaka i djevojčica.
odgovor: 0,0782
6. Prodavnica je dobila 500 boca u staklenoj ambalaži. Vjerovatnoća da će se bilo koja boca razbiti tokom transporta je 0,003. Nađite vjerovatnoću da će prodavnica primiti razbijene boce: a) tačno dvije; b) manje od dva; c) najmanje dva; d) najmanje jedan.
odgovor: a) 0,22; b) 0,20; c) 0,80; d) 0,95
7. Fabrika automobila proizvodi 80% automobila bez značajnih nedostataka. Kolika je vjerovatnoća da među 600 automobila isporučenih iz fabrike na berzu bude najmanje 500 automobila bez značajnijih kvarova?
odgovor: 0,02.
8. Koliko puta se novčić mora baciti da bi se sa vjerovatnoćom od 0,95 moglo očekivati da će relativna učestalost pojavljivanja grba odstupiti od vjerovatnoće R=0,5 izgled grba sa jednim bacanjem novčića za ne više od 0,02?
Odgovor: n ≥ 2401.
9. Vjerovatnoća da se događaj dogodi u svakom od 100 nezavisnih događaja je konstantna i jednaka str=0,8. Pronađite vjerovatnoću da će se događaj pojaviti: a) najmanje 75 puta i ne više od 90 puta; b) najmanje 75 puta; c) ne više od 74 puta.
odgovor: a B C) .
10. Vjerovatnoća da će se događaj dogoditi u svakom od nezavisnih ispitivanja je 0,2. Nađite kakvo se odstupanje relativne učestalosti pojave događaja od njegove vjerovatnoće može očekivati sa vjerovatnoćom od 0,9128 sa 5000 pokušaja.
odgovor:
11. Koliko puta se novčić mora baciti da bi se sa vjerovatnoćom 0,6 moglo očekivati da će odstupanje relativne učestalosti pojavljivanja grba od vjerovatnoće str=0,5 neće biti više od 0,01 u apsolutnoj vrijednosti.
Odgovor: n = 1764.
12. Vjerovatnoća da će se događaj dogoditi u svakom od 10.000 nezavisnih ispitivanja je 0,75. Pronađite vjerovatnoću da će relativna učestalost pojave događaja odstupiti od njegove vjerovatnoće u apsolutnoj vrijednosti za najviše 0,01.
odgovor: .
13. Vjerovatnoća da će se događaj dogoditi u svakom od nezavisnih ispitivanja je 0,5. Pronađite broj pokušaja n, pri čemu sa vjerovatnoćom od 0,7698 možemo očekivati da će relativna učestalost pojave događaja odstupiti od njegove vjerovatnoće u apsolutnoj vrijednosti za najviše 0,02.
Učitavanje...