Būlio algebra. Logikos algebra. Matematinės logikos elementai

Šiuolaikiniame pasaulyje mes vis dažniau naudojameįvairių mašinų ir dalykėlių. Ir ne tik tada, kai būtina taikyti pažodžiui nežmoniškas jėga: perkelti apkrovą ją pakelti į aukštį, kasti ilgas ir gilus griovys ir tt Automobiliai Šiandien surinkti robotus, maistas yra virti Multivarki ir elementarios aritmetinės skaičiavimai gaminti skaičiuotuvai ... Daugiau ir dažniau girdime frazę "Būlio algebra". Galbūt atėjo laikas suprasti žmonėmis vaidmenį robotų ir mašinų kūrimo gebėjimas spręsti ne tik matematinis, bet ir loginių problemų.

Logika

Graikijoje logika yraužsakyta mąstymo sistema, sukurianti santykius tarp nurodytų sąlygų ir leidžia mums daryti išvadas remiantis prielaidomis ir prielaidomis. Labai dažnai mes prašome vienas kito: "Ar tai logiška?" Atsakymas atitinka mūsų prielaidas arba kritikuoja minties eigą. Tačiau procesas nesibaigia: mes ir toliau džiaugiamės.

Kartais sąlygų (įvadinės) skaičius yra tokspuiku, o tarpusavio tarpusavio ryšiai yra tokie paini ir sudėtingi, kad žmogaus smegenys nebegali "suvirškinti" visko vienu metu. Tai gali užtrukti daugiau nei mėnesį (savaitę, metus), kad suprastumėte, kas vyksta. Bet šiuolaikinis gyvenimas mums nedaro tokių laiko sprendimų priėmimo. Ir mes kreipiamės į kompiuterių pagalbą. Ir čia atsiranda logikos algebra, jo įstatymai ir savybės. Atsisiuntę visus pradinius duomenis, leidžiame kompiuteriui atpažinti visus ryšius, pašalinti prieštaravimus ir rasti priimtiną sprendimą.

Matematika ir logika

Garsiausias Gottfriedas Wilhelmas Leibnizassuformulavo "matematinės logikos" sąvoką, kurios užduotys buvo prieinamos tik siauresniam mokslininkų ratui. Ypatingas susidomėjimas šia kryptimi nesukėlė, o iki XIX a. Vidurio keletą žino apie matematinę logiką.

Didelis susidomėjimas moksluginčas, kuriame angelas George'as Buhlas paskelbė apie savo ketinimą sukurti matematikos skyrių, kurio praktiškai nebuvo jokio praktinio taikymo. Kaip mes prisimename iš istorijos, tuo metu aktyviai vystėsi pramoninė gamyba, buvo sukurtos visos pagalbinės mašinos ir mašinos, ty visi moksliniai atradimai turėjo praktinę orientaciją.

Žvelgiant į ateitį, mes sakome, kad Būlio algebra yra labiausiai naudojama matematikos dalis šiuolaikiniame pasaulyje. Taigi ginčas prarado savo Boule.

George Boule

Pati autoriaus asmenybė nusipelno atskirodėmesio. Net atsižvelgiant į tai, kad praeityje žmonės tapo vyresni nei mes vis dar negalime nepamiršti, kad 16 metų amžiaus J. Bull mokėsi kaimo mokykloje, o 20 metų amžiaus savo mokykloje atidarė Linkolne. Matematikas puikiai įvaldė penkias užsienio kalbas, o jo laisvalaikį skaitė "Newton" ir "Lagrange" darbai. Ir visa tai yra paprasto darbuotojo sūnus!

1839 m. Boule pirmiausia atsiuntė savo mokslinįdirbti Kembridžo matematiniame žurnale. Mokslui buvo 24 metai. Taigi Boole'o darbas buvo toks įdomus Royal Scientific Society nariais, kad 1844 m. Jis gavo medalį už jo indėlį į matematinės analizės kūrimą. Keletas kitų paskelbtų darbų, kuriuose aprašyti matematinės logikos elementai, leido jaunam matematikui užimti Korko apskrities kolegijos profesoriaus postą. Prisiminkite, kad jis pats nebuvo išsilavinęs.

Idėja

Iš esmės, Būlio algebra yra labai paprasta. Yra teiginiai (loginės išraiškos), kurios, matematikos požiūriu, gali būti apibrėžtos tik dviem žodžiais: "tiesa" arba "melas". Pavyzdžiui, pavasarį žydi medžiai - tiesa, vasarą jis snaigėja - melas. Visas šios matematikos žavesys yra tai, kad nėra griežto reikalavimo naudoti tik numerius. Visi pasiūlymai, turintys vienareikšmę prasmę, puikiai tinka pasiūlymų algebaii.

Taigi, logika gali būti algebrayra vartojamas pažodžiui visur: planuojant ir rašant instrukcijas, analizuojant prieštaringą informaciją apie įvykius ir nustatant veiksmų seką. Svarbiausia yra suprasti, kad nesvarbu, kaip mes nustatėme pareiškimo tiesą ar melagingumą. Iš šių "kaip" ir "kodėl" reikėtų suprasti. Vienintelis dalykas yra faktas: tiesa-klaidinga.

Žinoma, funkcijos yra svarbios programavimuilogikos algebra, kurie parašyti atitinkamais ženklais ir simboliais. Ir išmokti juos reiškia įsisavinti naują užsienio kalbą. Nieko neįmanoma.

Pagrindinės sąvokos ir apibrėžimai

Neįsiliekant į gelmes, mes suprantame terminiją. Taigi, Būlio algebra prisiima tokį buvimą:

• pareiškimai;
• loginės operacijos;
• funkcijos ir įstatymai.

Pareiškimai - bet kokios teigiamos išraiškoskuri negali būti interpretuojama dvigubai. Jie parašyti skaičiais (5> 3) arba suformuluoti įprastu žodžiu (dramblys yra didžiausias žinduolis). Šiuo atveju frazė "žirafa neturi kaklo" taip pat turi teisę egzistuoti, tik loginė algebra ją apibrėžia kaip "melą".

Visi teiginiai turi būti aiškūssimbolis, tačiau jie gali būti pagrindinė arba junginys. Pastarieji naudoja loginius ryšius. E. algebra frazės Teismo sprendimų junginys, sudarytas iš elementarių loginių operacijų be.

Operacijos булевой algebra

Mes jau prisimename, kad operacijos pasiūlymų algeboje -logiškas. Kaip algebra skaičių naudoja aritmetines operacijas pridėti, atimti ar lyginti skaičių, matematinės logikos elementai leidžia sudaryti sudėtingus teiginius, paneigti ar apskaičiuoti galutinį rezultatą.

Logiškos formalizavimo ir paprastumo operacijosyra užrašomi pagal mums įprastas aritmetines formules. Būlio algebra savybės leidžia rašyti lygtis ir apskaičiuoti nežinomus. Loginiai veiksmai paprastai yra parašyti naudojant tiesos lentelę. Jo stulpeliuose apibrėžiami skaičiavimo elementai ir jų vykdoma operacija, o eilutėse rodomas skaičiavimų rezultatas.

Pagrindiniai loginiai veiksmai

Labiausiai paplitusi Būlio algebraoperacijos yra negation (NOT) ir loginis AND ir OR. Taigi jūs galite apibūdinti beveik visus veiksmus sprendimų algeboje. Mes išsamiai išnagrinėsime kiekvieną iš trijų operacijų.

Neigimas (ne) taikomas tik vienamelementas (operandas). Todėl užginčijimo operacija vadinama savaimine. Norėdami parašyti sąvoką "ne A", naudokite tokius simbolius: ¬A, A¯¯¯ arba! A. Lentelės formoje jis atrodo taip:

Neigiamos funkcijos atveju toks teiginys yra tipiškas: jei A yra tiesa, tada A yra klaidinga. Pavyzdžiui, Mėnulis sukasi aplink Žemę - tiesa; Žemė sukasi aplink Mėnulį - melas.

Loginis dauginimas ir papildymas

Loginis AND yra vadinamas jungties operacija. Ką tai reiškia? Pirma, tai gali būti taikoma dviems operandams, tai yra, aš yra dvejetainė operacija. Antra, tai tik abu operandų (ir A, ir B) tiesa yra pati tiesa. Sakinys "Kantrybė ir darbas bus peretruotas" reiškia, kad žmogus sugeba susidoroti su sunkumais tik dviem veiksniais.

Įrašymui naudojami simboliai: A∧B, A · B arba A && B.

Susiejimas yra analogiškas dauginimui aritmetinėje. Kartais jie sako tokį loginį dauginimą. Jei padauginame lentelės elementus eilėmis, gauname rezultatą, panašų į loginį mąstymą.

Disjunction vadinamas logine OR operacija. Tai patvirtina tiesos reikšmę, kai bent vienas teiginys yra teisingas (arba A, arba B). Tai parašyta tokiu būdu: A∨B, A + B arba A || B. Tiesos lentelės šioms operacijoms yra šios:

Disjunkcija yra kaip aritmetinis papildymas. Loginio papildymo operacija turi tik vieną apribojimą: 1 + 1 = 1. Tačiau mes prisimename, kad matematinė logika skaitmenine forma yra ribojama 0 ir 1 (kai 1 yra tiesa, 0 yra klaidinga). Pavyzdžiui, teiginyje "muziejuje galima pamatyti šedevrą ar pasimėgauti įdomiu pašnekovu" reiškia, kad jūs galite pamatyti meno kūrinius ir susipažinti su įdomiu asmeniu. Tuo pačiu metu nepanaikinama galimybė vienu metu įvykdyti abu įvykius.

Funkcijos ir įstatymai

Taigi, mes jau žinome, kokios loginės operacijosnaudoja Būlio algebą. Funkcijos apibūdina visas matematinės logikos elementų savybes ir leidžia jums supaprastinti sudėtingas sudėtines užduočių sąlygas. Labiausiai suprantama ir paprasta yra savybė atsisakyti išvestinių operacijų. Išvestinės finansinės priemonės yra išskirtinės ARBA, POVEIKIS ir lygiavertiškumas. Kadangi mes jau susipažinome su pagrindinėmis operacijomis, mes svarstysime tik jų savybes.

Asociacija reiškia, kad tokiuose teiginiuose kaip "ir A, ir B ir B", operandų skaičiavimas nesvarbus. Formulė yra tokia:

(A∧B) ∧ B = A∧ (B∧В) = A∧B∧В,

(A ∨ B) ∨ B = A∨ (B∨В) = A∨В∨.

Kaip matome, tai būdinga ne tik jungtys, bet ir disjunkcijos.

Komutatyvumas teigia, kad jungties ar disjunkcijos rezultatas nepriklauso nuo to, kuris elementas buvo laikomas pradžioje:

A∧Б = Б∧A; A∨B = B∨A.

Paskirstymas leidžia jums įklijuoti sudėtines logines išraiškas. Taisyklės yra panašios į skliaustų atskleidimą dauginant ir pridedant algebą:

A∧ (B∨В) = A∧В∨A∧В; A∨B∧B = (A∨B) ∧ (A∨B).

Vieneto ypatybės ir nulis, kuris gali būti vienas iš operandų, taip pat yra analogiškas algebriniam dauginimui nuliui arba vienai ir papildomai prie vieno:

A∧0 = 0, A∧1 = A; A∨0 = A, A∨1 = 1.

Idempotencija sako mums, kad jei dulygiaverčiai operandai, operacijos rezultatas pasirodė esantis analogiškas, tada galima "išmesti" papildomus operandus, kurie apsunkina motyvacijos eigą. Tiek jungtis, tiek disjunction yra idempotencinės operacijos.

БББ = Б; БББ = Б.

Absorbcija taip pat leidžia mums supaprastinti lygtis. Absorbcija teigiama, kad kai veiksmas su tuo pačiu operandu yra taikomas išraiška su vienu operandu, rezultatas yra operandas iš sugeriančios operacijos.

A∧B∨B = B; (A∨B) ∧B = B.

Operacijų seka

Operacijų seka yra svarbiprasme. Tiesą sakant, kaip ir algebra, yra funkcijų, naudojančių Būlio algebra, prioritetas. Formulės gali būti supaprastintos tik tuo atveju, jei pastebima operacijų svarba. Reitingas nuo svarbiausių iki mažųjų, mes gauname šią seka:

1. Atsisakymas.

2. Susijungimas.

3. Skirstymas, išskyrus OR.

4. Priežastys, lygiavertiškumas.

Kaip matome, tik neigimas ir junginiai neturi vienodų prioritetų. Ir disjunction ir išskirtinio OR prioritetas yra lygus, taip pat implikacijos ir lygiavertiškumo prioritetai.

Priskyrimo ir lygiavertiškumo funkcijos

Kaip jau minėjome, be pagrindinių loginių operacijų matematinė logika ir algoritmų teorija naudoja išvestines priemones. Dažniausiai naudojamas implikacija ir lygiavertiškumas.

Priežastis ar logiškas sekimas yrateiginys, kuriame vienas veiksmas yra sąlyga, o kitas yra jo įvykdymo pasekmė. Kitaip tariant, šis sakinys su iš anksto "jei ... tada". "Jums patinka važiuoti, mylėti ir važiuoti". Tai reiškia, kad norint čiuožimo reikia nutempti keltuvus į kalną. Jei nėra noro palikti kalną, tuomet nereikia vežti keltuvų. Tai parašyta taip: A → B arba A⇒B.

Ekvivalentiškumas daro prielaidą, kad gautas rezultatasVeiksmas įvyksta tik tuomet, kai abu operandai yra tiesūs. Pavyzdžiui, naktį pakeičia diena (ir tik tada), kai saulė kyla iš horizonto. Matematinės logikos kalba šis teiginys parašomas taip: A≡B, AβB, A == B.

Kiti įstatymai булевой algebra

Judėjimo algebra vystosi, ir daugelissuinteresuoti mokslininkai suformulavo naujus įstatymus. Labiausiai žinomi Škotijos matematikos O. de Morgan postulatai. Jis pastebėjo ir apibrėžė tokias savybes kaip artimas neigimas, papildymas ir dvigubas neigimas.

Uždaryti neigimą leidžia manyti, kad prieš klaviatūrą nėra jokio neginimo: ne (A arba B) = ne A ar ne B.

Kai operandas yra atmestas, nepriklausomai nuo jo reikšmės, papildomai:

Б∧¬Б = 0; Б¬¬б = 1.

Ir galiausiai dvigubas užginčijimas kompensuoja save. Ie. Prieš operandą užginčijimas išnyksta arba lieka tik vienas.

Kaip išspręsti bandymus

Matematinė logika reiškia supaprastinimąiš nurodytų lygčių. Kaip ir algeboje, pirmiausia būtina, kad sąlyga būtų kuo lengviau (atsikratyti sudėtingų įvadų ir operacijų su jais), tada tęsti, kad surastų tinkamą atsakymą.

Ką galime padaryti, kad supaprastintume dalykus? Konvertuokite visas išvestines operacijas į paprastus. Tada atidarykite visus skliaustus (arba atvirkščiai, pateikite skliaustus, kad sutrumpintumėte šį elementą). Kitas žingsnis yra praktikoje pritaikyti Būlio algebra savybes (absorbcija, nulio ir vienetų savybės ir tt).

Galutinėje analizėje lygtį turi sudarytiMinimalus nežinomų skaičių, sujungtas paprastomis operacijomis. Lengviausia ieškoti sprendimo, jei pasiekiamas nemažai artimų prieštaravimų. Tada atsakymas pasirodys kaip pats.