Šiandieniniame pasaulyje vis dažniau naudojame įvairius automobilius ir prietaisus. Ir ne tik tada, kai reikia panaudoti tiesiogine prasme nežmonišką jėgą: perkelti krovinį, pakelti į aukštį, kasti ilgą ir gilią tranšėją ir pan.. Automobilius šiandien surenka robotai, maistą ruošia multivarkais, o elementarūs aritmetiniai skaičiavimai yra atlieka skaičiuotuvai. Vis dažniau girdime posakį „Bulio algebra“. Galbūt laikas suprasti žmogaus vaidmenį kuriant robotus ir mašinų gebėjimą spręsti ne tik matematines, bet ir logines problemas.
Logika
Išvertus iš graikų kalbos, logika yra sutvarkyta mąstymo sistema, kuri sukuria ryšius tarp nurodytų sąlygų ir leidžia daryti išvadas remiantis prielaidomis ir prielaidomis. Gana dažnai vienas kito klausiame: "Ar tai logiška?" Gautas atsakymas patvirtina mūsų prielaidas arba kritikuoja minčių eigą. Tačiau procesas nesibaigia: mes ir toliau svarstome.
Kartais sąlygų (įžanginių) skaičius yra toks didelis, o santykiai tarp jų tokie įmantrūs ir sudėtingi, kad žmogaus smegenys nepajėgia visko „suvirškinti“iš karto. Norint suprasti, kas vyksta, gali prireikti daugiau nei vieno mėnesio (savaitės, metų). Betšiuolaikinis gyvenimas nesuteikia mums tokių laiko intervalų sprendimams priimti. Ir mes kreipiamės į kompiuterių pagalbą. Ir čia atsiranda logikos algebra su savo dėsniais ir savybėmis. Atsisiuntę visus pradinius duomenis, leidžiame kompiuteriui atpažinti visus ryšius, pašalinti prieštaravimus ir rasti patenkinamą sprendimą.
Matematika ir logika
Žymusis Gottfriedas Wilhelmas Leibnicas suformulavo „matematinės logikos“sąvoką, kurios problemos buvo suprantamos tik siauram mokslininkų ratui. Ši kryptis ypatingo susidomėjimo nesukėlė ir iki XIX amžiaus vidurio mažai kas žinojo apie matematinę logiką.
Didelis susidomėjimas mokslo bendruomene sukėlė ginčą, kurio metu anglas George'as Boole'as paskelbė apie savo ketinimą sukurti matematikos šaką, kuri visiškai neturi praktinio pritaikymo. Kaip prisimename iš istorijos, tuo metu aktyviai vystėsi pramoninė gamyba, buvo kuriamos visokios pagalbinės staklės ir staklės, tai yra, visi mokslo atradimai buvo orientuoti į praktiką.
Žvelgdami į ateitį, tarkime, kad Būlio algebra yra dažniausiai naudojama matematikos dalis šiuolaikiniame pasaulyje. Taigi Bulas prarado savo argumentus.
George'as Buhlas
Pati autoriaus asmenybė nusipelno ypatingo dėmesio. Net turint galvoje, kad anksčiau žmonės augo prieš mus, vis tiek neįmanoma nepastebėti, kad būdamas 16 metų J. Buhlas mokytojavo kaimo mokykloje, o sulaukęs 20 metų Linkolne atidarė savo mokyklą. Matematikas laisvai mokėjo penkias užsienio kalbas, o laisvalaikiu skaitė kūriniusNiutonas ir Lagranžas. Ir visa tai apie paprasto darbininko sūnų!
1839 m. Būlis pirmą kartą pateikė savo mokslinius darbus Kembridžo matematikos žurnalui. Mokslininkui 24 metai. Būlio darbai taip sudomino Karališkosios draugijos narius, kad 1844 m. jis gavo medalį už indėlį plėtojant matematinę analizę. Dar keli publikuoti darbai, kuriuose aprašyti matematinės logikos elementai, leido jaunam matematikui užimti profesoriaus pareigas Korko apygardos koledže. Prisiminkite, kad pats Buhlas neturėjo išsilavinimo.
Idėja
Iš esmės Būlio algebra yra labai paprasta. Yra teiginių (loginių posakių), kuriuos matematikos požiūriu galima apibrėžti tik dviem žodžiais: „teisinga“arba „klaidinga“. Pavyzdžiui, pavasarį medžiai žydi – tiesa, vasarą sninga – melas. Šios matematikos grožis yra tas, kad nėra griežto poreikio naudoti tik skaičius. Bet kokie teiginiai, turintys nedviprasmišką reikšmę, yra gana tinkami sprendimų algebrai.
Taigi, logikos algebra gali būti naudojama pažodžiui visur: planuojant ir rašant instrukcijas, analizuojant prieštaringą informaciją apie įvykius ir nustatant veiksmų seką. Svarbiausia suprasti, kad visiškai nesvarbu, kaip mes nustatome teiginio teisingumą ar klaidingumą. Šiuos „kaip“ir „kodėl“reikia abstrahuoti. Svarbu tik fakto konstatavimas: tiesa-netiesa.
Žinoma, programavimui svarbios logikos algebros funkcijos, kurias rašo atitinkamasženklai ir simboliai. O išmokti juos reiškia išmokti naują užsienio kalbą. Nieko nėra neįmanomo.
Pagrindinės sąvokos ir apibrėžimai
Nesigilinant, nagrinėkime terminologiją. Taigi Būlio algebra daro prielaidą:
- pareiškimai;
- loginės operacijos;
- funkcijos ir dėsniai.
Teiginiai yra bet kokie teigiami posakiai, kurių negalima interpretuoti nevienareikšmiškai. Jie rašomi skaičiais (5 > 3) arba suformuluoti pažįstamais žodžiais (dramblys yra didžiausias žinduolis). Tuo pačiu metu frazė „žirafa neturi kaklo“taip pat turi teisę egzistuoti, tik Būlio algebra ją apibūdins kaip „klaidingą“.
Visi teiginiai turi būti nedviprasmiški, tačiau jie gali būti elementarūs ir sudėtiniai. Pastarieji naudoja loginius ryšius. Tai yra, sprendimų algebroje sudėtiniai teiginiai sudaromi sudedant elementarius teiginius loginėmis operacijomis.
Bulio algebros operacijos
Mes jau prisimename, kad operacijos sprendimų algebroje yra logiškos. Kaip skaičių algebra naudoja aritmetiką skaičiams pridėti, atimti ar palyginti, taip matematinės logikos elementai leidžia daryti sudėtingus teiginius, paneigti arba apskaičiuoti galutinį rezultatą.
Loginės formalizavimo ir paprastumo operacijos užrašomos mums aritmetikoje pažįstamomis formulėmis. Būlio algebros savybės leidžia rašyti lygtis ir apskaičiuoti nežinomuosius. Loginės operacijos dažniausiai rašomos naudojant tiesos lentelę. Jo stulpeliaiapibrėžti skaičiavimo elementus ir su jais atliekamą operaciją, o linijos rodo skaičiavimo rezultatą.
Pagrindiniai loginiai veiksmai
Dažniausios Būlio algebros operacijos yra neigimas (NE) ir loginė AND ir ARBA. Taip galima apibūdinti beveik visus sprendimų algebros veiksmus. Išsamiau išnagrinėkime kiekvieną iš trijų operacijų.
Neigimas (ne) taikomas tik vienam elementui (operandui). Todėl neigimo operacija vadinama unarine. Norėdami parašyti sąvoką „ne A“, naudokite šiuos simbolius: ¬A, A¯¯¯ arba !A. Lentelės pavidalu tai atrodo taip:
Neigimo funkcijai būdingas toks teiginys: jei A teisinga, tai B yra klaidinga. Pavyzdžiui, Mėnulis sukasi aplink Žemę – tiesa; Žemė sukasi aplink mėnulį – klaidinga.
Loginis daugyba ir sudėtis
Loginis AND vadinamas jungties operacija. Ką tai reiškia? Pirma, kad jis gali būti taikomas dviem operandams, ty ir yra dvejetainė operacija. Antra, kad tik abiejų operandų (ir A ir B) tiesos atveju pati išraiška yra teisinga. Patarlė „Viską sumals kantrybė ir darbas“teigia, kad tik abu veiksniai padės žmogui susidoroti su sunkumais.
Rašymui naudojami simboliai: A∧B, A⋅B arba A&&B.
Jungtinys panašus į daugybą aritmetikoje. Kartais taip sako – loginis dauginimas. Jei lentelės elementus padauginsime iš eilutės, gausime rezultatą, panašų į loginį samprotavimą.
Disjunkcija yra loginė ARBA operacija. Tam reikia tiesos vertėskai bent vienas iš teiginių yra teisingas (arba A, arba B). Rašoma taip: A∨B, A+B arba A||B. Šių operacijų tiesos lentelės yra šios:
Disjunkcija yra tarsi aritmetinis sudėjimas. Loginio sudėjimo operacija turi tik vieną apribojimą: 1+1=1. Tačiau mes prisimename, kad skaitmeniniame formate matematinė logika yra apribota iki 0 ir 1 (kur 1 yra tiesa, 0 yra klaidinga). Pavyzdžiui, teiginys „muziejuje gali pamatyti šedevrą arba sutikti įdomų pašnekovą“reiškia, kad galite pamatyti meno kūrinius arba sutikti įdomų žmogų. Tuo pačiu metu neatmetama galimybė, kad abu įvykiai įvyks vienu metu.
Funkcijos ir įstatymai
Taigi, mes jau žinome, kokias logines operacijas naudoja Būlio algebra. Funkcijos apibūdina visas matematinės logikos elementų savybes ir leidžia supaprastinti sudėtingas sudėtines uždavinių sąlygas. Suprantamiausia ir paprasčiausia savybė atrodo išvestinių operacijų atmetimas. Išvestinės priemonės yra išskirtinės ARBA, implikacijos ir lygiavertiškumas. Kadangi išstudijavome tik pagrindines operacijas, atsižvelgsime ir į tik jų savybes.
Asociatyvumas reiškia, kad tokiuose teiginiuose kaip „ir A, ir B, ir C“operandų tvarka nesvarbi. Formulė parašyta taip:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Kaip matote, tai būdinga ne tik konjunkcijai, bet ir disjunkcijai.
Komutatyvumas teigia, kad rezultataskonjunkcija ar disjunkcija nepriklauso nuo to, kuris elementas buvo svarstomas pirmiausia:
A∧B=B∧A; A∨B=B∨A.
Paskirstymas leidžia išplėsti skliaustus sudėtingose loginėse išraiškose. Taisyklės panašios į skliaustų atidarymą dauginant ir sudėjus algebroje:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Vieno ir nulio savybės, kurios gali būti vienas iš operandų, taip pat yra panašios į algebrinį dauginimą iš nulio arba vieneto ir sudėjimą su vienu:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotencija mums sako, kad jei operacijos rezultatas dviejų vienodų operandų atžvilgiu yra panašus, galime „išmesti“papildomus operandus, kurie apsunkina samprotavimo eigą. Tiek konjunkcija, tiek disjunkcija yra idempotentinės operacijos.
B∧B=B; B∨B=B.
Absorbcija taip pat leidžia supaprastinti lygtis. Absorbcija teigia, kad kai reiškiniui su vienu operandu taikoma kita operacija su tuo pačiu elementu, rezultatas yra sugeriančios operacijos operandas.
A∧B∨B=B; (A∨B)∧B=B.
Veiksmų seka
Veiksmų seka yra labai svarbi. Tiesą sakant, kalbant apie algebrą, yra prioritetas funkcijoms, kurias naudoja Būlio algebra. Formulės gali būti supaprastintos tik tada, kai atsižvelgiama į operacijų reikšmę. Reitinguodami nuo reikšmingiausio iki mažiausio, gauname tokią seką:
1. Neigimas.
2. Jungtis.
3. Disjunkcija, išskirtinėARBA.
4. Potekstė, lygiavertiškumas.
Kaip matote, tik neigimas ir jungtukas neturi vienodos pirmenybės. Ir disjunkcijos ir XOR prioritetai yra vienodi, taip pat implikacijos ir lygiavertiškumo prioritetai.
Išreiškimo ir lygiavertiškumo funkcijos
Kaip jau minėjome, be pagrindinių loginių operacijų, matematinė logika ir algoritmų teorija naudoja išvestines. Dažniausiai naudojami implikacijos ir lygiavertiškumas.
Imlikacija arba loginė pasekmė – tai teiginys, kuriame vienas veiksmas yra sąlyga, o kitas – jo įgyvendinimo pasekmė. Kitaip tariant, tai yra sakinys su prielinksniais „jei … tada“. "Jei jums patinka važiuoti, mėgsti neštis roges." Tai yra, norint slidinėti, reikia priveržti roges į kalną. Jei nėra noro leistis nuo kalno, tada nereikia neštis rogių. Rašoma taip: A→B arba A⇒B.
Ekvivalencija daro prielaidą, kad gautas veiksmas įvyksta tik tada, kai abu operandai yra teisingi. Pavyzdžiui, naktis virsta diena, kai (ir tik tada) saulė pakyla virš horizonto. Matematinės logikos kalba šis teiginys parašytas taip: A≡B, A⇔B, A==B.
Kiti Būlio algebros dėsniai
Sprendimų algebra vystosi, ir daugelis suinteresuotų mokslininkų suformulavo naujus įstatymus. Žymiausiais laikomi škotų matematiko O. de Morgano postulatai. Jis pastebėjo ir apibrėžė tokias savybes kaip artimas neigimas, papildymas ir dvigubas neigimas.
Uždaryti neigimą reiškia, kad prieš skliaustelį neigimo nėra:ne (A arba B)=ne A arba NE B.
Kai operandas neigiamas, nepaisant jo vertės, kalbama apie papildymą:
B∧¬B=0; B∨¬B=1.
Ir galiausiai dvigubas neigimas kompensuoja save. Tie. arba neigimas išnyksta prieš operandą, arba lieka tik vienas.
Kaip išspręsti testus
Matematinė logika reiškia pateiktų lygčių supaprastinimą. Kaip ir algebroje, pirmiausia turite padaryti sąlygą kuo paprastesnę (atsikratykite sudėtingų įvesties ir operacijų su jais), o tada pradėkite ieškoti teisingo atsakymo.
Ką galima padaryti norint supaprastinti? Konvertuokite visas išvestas operacijas į paprastas. Tada atidarykite visus skliaustus (arba atvirkščiai, išimkite jį iš skliaustų, kad sutrumpintumėte šį elementą). Kitas žingsnis turėtų būti Būlio algebros savybių pritaikymas praktikoje (absorbcija, nulio ir vieneto savybės ir kt.).
Galų gale lygtį turėtų sudaryti minimalus nežinomųjų skaičius, sujungtas paprastomis operacijomis. Lengviausias būdas rasti sprendimą – pasiekti daug artimų negatyvų. Tada atsakymas pasirodys tarsi savaime.
