U današnjem svijetu sve više koristimo razne automobile i gadgete. I ne samo kada je potrebno primijeniti doslovno neljudsku snagu: premjestiti teret, podići ga u visinu, iskopati dug i dubok rov itd. Automobile danas sastavljaju roboti, hranu pripremaju multicookers, a elementarni aritmetički izračuni su izvode kalkulatori. Sve češće čujemo izraz "Booleova algebra". Možda je vrijeme da shvatimo ulogu čovjeka u stvaranju robota i sposobnost strojeva da rješavaju ne samo matematičke, već i logičke probleme.
Logic
Prevedeno s grčkog, logika je uređeni sustav mišljenja koji stvara odnose između zadanih uvjeta i omogućuje vam izvlačenje zaključaka na temelju premisa i pretpostavki. Često se pitamo jedni druge: "Je li logično?" Dobiveni odgovor potvrđuje naše pretpostavke ili kritizira tok misli. Ali proces ne staje: nastavljamo s rasuđivanjem.
Ponekad je broj uvjeta (uvodnih) tako velik, a odnosi među njima toliko su zamršeni i složeni da ljudski mozak nije u stanju "probaviti" sve odjednom. Može potrajati više od mjesec dana (tjedan, godina) da se shvati što se događa. Alisuvremeni nam život ne daje takve vremenske intervale za donošenje odluka. I pribjegavamo pomoći računalima. I tu se pojavljuje algebra logike, sa svojim vlastitim zakonima i svojstvima. Preuzimanjem svih početnih podataka omogućujemo računalu da prepozna sve odnose, otkloni proturječnosti i pronađe zadovoljavajuće rješenje.
Matematika i logika
Čuveni Gottfried Wilhelm Leibniz formulirao je koncept "matematičke logike", čiji su problemi bili razumljivi samo uskom krugu znanstvenika. Ovaj smjer nije izazvao poseban interes, a sve do sredine 19. stoljeća malo je ljudi znalo za matematičku logiku.
Veliki interes u znanstvenoj zajednici izazvao je spor u kojem je Englez George Boole najavio svoju namjeru da stvori granu matematike koja nema apsolutno nikakvu praktičnu primjenu. Kao što se sjećamo iz povijesti, tada se aktivno razvijala industrijska proizvodnja, razvijale su se sve vrste pomoćnih strojeva i alatnih strojeva, odnosno sva znanstvena otkrića imala su praktičan fokus.
Gledajući unaprijed, recimo da je Booleova algebra najčešće korišteni dio matematike u modernom svijetu. Tako je Bull izgubio argument.
George Buhl
Sama osobnost autora zaslužuje posebnu pažnju. Čak i s obzirom na to da su u prošlosti ljudi odrastali prije nas, ipak je nemoguće ne primijetiti da je J. Buhl sa 16 godina predavao u seoskoj školi, a s 20 je otvorio vlastitu školu u Lincolnu. Matematičar je tečno govorio pet stranih jezika, a u slobodno vrijeme čitao je radoveNewtona i Lagrangea. A sve je to o sinu jednostavnog radnika!
Godine 1839. Boole je prvi put poslao svoje znanstvene radove u Cambridge Mathematical Journal. Znanstvenik ima 24 godine. Booleov rad toliko je zainteresirao članove Kraljevskog društva da je 1844. godine dobio medalju za doprinos razvoju matematičke analize. Još nekoliko objavljenih radova, koji su opisivali elemente matematičke logike, omogućili su mladom matematičaru da preuzme mjesto profesora na Cork County College. Podsjetimo da sam Buhl nije imao obrazovanje.
Ideja
U principu, Booleova algebra je vrlo jednostavna. Postoje iskazi (logički izrazi) koji se, sa stajališta matematike, mogu definirati samo s dvije riječi: “točno” ili “netočno”. Na primjer, u proljeće drveće cvjeta - istina, ljeti pada snijeg - laž. Ljepota ove matematike je u tome što nema stroge potrebe za korištenjem samo brojeva. Bilo koji iskaz s nedvosmislenim značenjem sasvim je prikladan za algebru prosudbi.
Dakle, algebra logike može se koristiti doslovno svugdje: u planiranju i pisanju uputa, analiziranju proturječnih informacija o događajima i određivanju slijeda radnji. Najvažnije je shvatiti da je potpuno nevažno kako utvrđujemo istinitost ili netočnost iskaza. Ove "kako" i "zašto" treba apstrahirati. Važna je samo izjava o činjenicama: istina-netočno.
Naravno, za programiranje su važne funkcije algebre logike, koje su zapisane odgovarajućimznakove i simbole. A naučiti ih znači savladati novi strani jezik. Ništa nije nemoguće.
Osnovni koncepti i definicije
Ne ulazeći u dubinu, pozabavimo se terminologijom. Dakle, Booleova algebra pretpostavlja:
- izjave;
- logičke operacije;
- funkcije i zakoni.
Izjave su svi afirmativni izrazi koji se ne mogu dvosmisleno tumačiti. Napisani su brojevima (5 > 3) ili formulirani poznatim riječima (slon je najveći sisavac). U isto vrijeme, fraza "žirafa nema vrat" također ima pravo na postojanje, samo će je Booleova algebra definirati kao "lažno".
Sve izjave moraju biti nedvosmislene, ali mogu biti elementarne i složene. Potonji koriste logičke veznike. To jest, u algebri prosudbi složeni iskazi se formiraju dodavanjem elementarnih iskaza pomoću logičkih operacija.
Operacije Booleove algebre
Već se sjećamo da su operacije u algebri sudova logične. Baš kao što algebra brojeva koristi aritmetiku za dodavanje, oduzimanje ili uspoređivanje brojeva, elementi matematičke logike omogućuju vam da date složene izjave, negirate ili izračunate konačni rezultat.
Logičke operacije za formalizaciju i jednostavnost napisane su formulama koje su nam poznate u aritmetici. Svojstva Booleove algebre omogućuju pisanje jednadžbi i izračunavanje nepoznanica. Logičke operacije se obično pišu pomoću tablice istinitosti. Njegove kolonedefinirajte elemente izračuna i operaciju koja se nad njima izvodi, a linije pokazuju rezultat izračuna.
Osnovne logičke radnje
Najčešće operacije u Booleovoj algebri su negacija (NE) i logičko I i ILI. Gotovo sve radnje u algebri sudova mogu se opisati na ovaj način. Proučimo svaku od tri operacije detaljnije.
Negacija (ne) primjenjuje se samo na jedan element (operand). Stoga se operacija negacije naziva unarnom. Za pisanje pojma "ne A" koristite sljedeće simbole: ¬A, A¯¯¯ ili !A. U tabličnom obliku to izgleda ovako:
Funkciju negacije karakterizira sljedeća izjava: ako je A istinito, onda je B lažno. Na primjer, Mjesec se okreće oko Zemlje – istina; Zemlja se okreće oko mjeseca - lažno.
logičko množenje i zbrajanje
Logički I naziva se operacija veznika. Što to znači? Prvo, da se može primijeniti na dva operanda, tj. I je binarna operacija. Drugo, da je samo u slučaju istinitosti oba operanda (i A i B) sam izraz istinit. Izreka "Strpljenje i rad će sve samljeti" sugerira da će samo oba faktora pomoći čovjeku da se nosi s poteškoćama.
Simboli koji se koriste za pisanje: A∧B, A⋅B ili A&&B.
Konjunkcija je slična množenju u aritmetici. Ponekad kažu da – logično množenje. Ako pomnožimo elemente tablice red po red, dobit ćemo rezultat sličan logičkom razmišljanju.
Disjunction je logička operacija ILI. Uzima vrijednost istinekada je barem jedna od tvrdnji istinita (A ili B). Piše se ovako: A∨B, A+B ili A||B. Tablice istine za ove operacije su:
Disjunkcija je poput aritmetičkog zbrajanja. Operacija logičkog zbrajanja ima samo jedno ograničenje: 1+1=1. Ali sjećamo se da je u digitalnom formatu matematička logika ograničena na 0 i 1 (gdje je 1 istina, 0 netočno). Na primjer, izjava “u muzeju možete vidjeti remek-djelo ili upoznati zanimljivog sugovornika” znači da možete vidjeti umjetnička djela ili možete upoznati zanimljivu osobu. Istodobno, nije isključena mogućnost da se oba događaja dogode istovremeno.
Funkcije i zakoni
Dakle, već znamo koje logičke operacije koristi Booleova algebra. Funkcije opisuju sva svojstva elemenata matematičke logike i omogućuju vam da pojednostavite složene složene uvjete problema. Čini se da je najrazumljivije i najjednostavnije svojstvo odbacivanje izvedenih operacija. Derivati su isključivo OR, implikacija i ekvivalencija. Budući da smo proučavali samo osnovne operacije, razmotrit ćemo i svojstva samo njih.
Asocijativnost znači da u izjavama poput "i A, i B, i C" redoslijed operanada nije bitan. Formula je napisana ovako:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Kao što možete vidjeti, ovo je karakteristika ne samo konjunkcije, već i disjunkcije.
Komutativnost navodi da je rezultatkonjunkcija ili disjunkcija ne ovise o tome koji je element prvi razmatran:
A∧B=B∧A; A∨B=B∨A.
Distributivnost omogućuje proširenje zagrada u složenim logičkim izrazima. Pravila su slična otvaranju zagrada u množenju i zbrajanju u algebri:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Svojstva jedan i nula, koji mogu biti jedan od operanada, također su slična algebarskom množenju s nulom ili jedinicom i zbrajanju s jedan:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotencija nam govori da ako se, s obzirom na dva jednaka operanda, pokaže da je rezultat operacije sličan, tada možemo "odbaciti" dodatne operande koji kompliciraju tijek razmišljanja. I konjunkcija i disjunkcija su idempotentne operacije.
B∧B=B; B∨B=B.
Apsorpcija nam također omogućuje da pojednostavimo jednadžbe. Apsorpcija navodi da kada se druga operacija s istim elementom primijeni na izraz s jednim operandom, rezultat je operand iz operacije apsorpcije.
A∧B∨B=B; (A∨B)∧B=B.
Slijed operacija
Slijed operacija nije od male važnosti. Zapravo, što se tiče algebre, postoji prioritet funkcija koje koristi Booleova algebra. Formule se mogu pojednostaviti samo ako se promatra značaj operacija. Poredeći od najznačajnijeg do najmanjeg, dobivamo sljedeći niz:
1. Poricanje.
2. Konjukcija.
3. Disjunkcija, isključivaILI.
4. Implikacija, ekvivalencija.
Kao što vidite, samo negacija i konjunkcija nemaju jednak prioritet. I prioritet disjunkcije i XOR su jednaki, kao i prioriteti implikacije i ekvivalencije.
Funkcije implikacije i ekvivalencije
Kao što smo već rekli, osim osnovnih logičkih operacija, matematička logika i teorija algoritama koriste derivate. Najčešće korišteni su implikacija i ekvivalencija.
Implikacija, ili logička posljedica, je izjava u kojoj je jedna radnja uvjet, a druga posljedica njezine implementacije. Drugim riječima, ovo je rečenica s prijedlozima "ako … onda". "Ako volite jahati, volite nositi sanjke." Odnosno, za skijanje morate zategnuti sanjke uz brdo. Ako nema želje za kretanjem niz planinu, onda ne morate nositi sanjke. Piše se ovako: A→B ili A⇒B.
Ekvivalentnost pretpostavlja da se rezultirajuća akcija događa samo kada su oba operanda istinita. Na primjer, noć se pretvara u dan kada (i samo kada) sunce izađe iznad horizonta. Jezikom matematičke logike ova izjava je napisana na sljedeći način: A≡B, A⇔B, A==B.
Drugi zakoni Booleove algebre
Algebra prosudbi se razvija, a mnogi zainteresirani znanstvenici formulirali su nove zakone. Najpoznatijim se smatraju postulati škotskog matematičara O. de Morgana. On je uočio i definirao svojstva kao što su bliska negacija, dopuna i dvostruka negacija.
Zatvorska negacija znači da nema negacije prije zagrade:ne (A ili B)=nije A ili NE B.
Kada je operand negiran, bez obzira na njegovu vrijednost, govori se o komplementu:
B∧¬B=0; B∨¬B=1.
I konačno, dvostruka negacija kompenzira samu sebe. Oni. ili negacija nestaje prije operanda, ili ostaje samo jedan.
Kako riješiti testove
Matematička logika podrazumijeva pojednostavljenje zadanih jednadžbi. Kao i u algebri, prvo morate učiniti uvjet što je moguće lakšim (riješiti se složenih unosa i operacija s njima), a zatim početi tražiti pravi odgovor.
Što se može učiniti da se pojednostavi? Pretvorite sve izvedene operacije u jednostavne. Zatim otvorite sve zagrade (ili obrnuto, izvadite ga iz zagrada da skratite ovaj element). Sljedeći korak trebao bi biti primjena svojstava Booleove algebre u praksi (apsorpcija, svojstva nule i jedan, itd.).
U konačnici, jednadžba bi se trebala sastojati od minimalnog broja nepoznanica kombiniranih jednostavnim operacijama. Najlakši način za pronalaženje rješenja je postizanje velikog broja bliskih negativa. Tada će se odgovor pojaviti kao da sam od sebe.
