Boolen algebra. Logiikan algebra. Matemaattisen logiikan elementit

Sisällysluettelo:

Boolen algebra. Logiikan algebra. Matemaattisen logiikan elementit
Boolen algebra. Logiikan algebra. Matemaattisen logiikan elementit
Anonim

Nykyajan maailmassa käytämme yhä enemmän erilaisia autoja ja laitteita. Eikä vain silloin, kun on tarpeen käyttää kirjaimellisesti epäinhimillistä voimaa: siirtää kuormaa, nostaa se korkealle, kaivaa pitkä ja syvä oja jne. Nykyään autot kootaan robottien avulla, ruokaa valmistetaan monikeittiöillä, ja alkeelliset aritmeettiset laskelmat ovat laskimien suorittamana. Yhä useammin kuulemme ilmaisun "Boolen algebra". Ehkä on aika ymmärtää ihmisen rooli robottien luomisessa ja koneiden kyky ratkaista paitsi matemaattisia myös loogisia ongelmia.

Logiikka

Käännettynä kreikasta logiikka on järjestynyt ajattelujärjestelmä, joka luo suhteita annettujen olosuhteiden välille ja antaa sinun tehdä johtopäätöksiä premissien ja oletusten perusteella. Usein kysymme toisiltamme: "Onko se loogista?" Saatu vastaus vahvistaa olettamuksemme tai arvostelee ajatuskulkua. Mutta prosessi ei pysähdy: jatkamme järkeilyä.

Joskus olosuhteiden määrä (johdanto) on niin suuri, ja niiden väliset suhteet ovat niin monimutkaisia ja monimutkaisia, että ihmisaivot eivät pysty "sulattamaan" kaikkea kerralla. Voi kestää yli kuukauden (viikko, vuosi) ymmärtää, mitä tapahtuu. Muttanykyelämä ei anna meille sellaisia aikavälejä päätösten tekemiseen. Ja turvaudumme tietokoneiden apuun. Ja tässä ilmestyy logiikan algebra, jolla on omat lakinsa ja ominaisuudet. Lataamalla kaikki alkutiedot, annamme tietokoneen tunnistaa kaikki suhteet, poistaa ristiriidat ja löytää tyydyttävän ratkaisun.

Kuva
Kuva

Matematiikka ja logiikka

Kuuluisa Gottfried Wilhelm Leibniz muotoili "matemaattisen logiikan" käsitteen, jonka ongelmat olivat ymmärrettävissä vain kapealle tiedemiehelle. Tämä suunta ei herättänyt erityistä kiinnostusta, ja 1800-luvun puoliväliin asti vain harvat tiesivät matemaattisesta logiikasta.

Suuri kiinnostus tiedeyhteisöä kohtaan aiheutti kiistan, jossa englantilainen George Boole ilmoitti aikovansa luoda matematiikan haara, jolla ei ole minkäänlaista käytännön sovellusta. Kuten historiasta muistamme, teollisuustuotanto kehittyi tuolloin aktiivisesti, kaikenlaisia apukoneita ja työstökoneita kehitettiin, eli kaikilla tieteellisillä löydöillä oli käytännön painopiste.

Eteenpäin katsottuna oletetaan, että Boolen algebra on nykymaailman eniten käytetty osa matematiikkaa. Joten Bull menetti väitteensä.

George Buhl

Kirjoittajan persoonallisuus ansaitsee erityistä huomiota. Vaikka otetaan huomioon, että ihmiset kasvoivat ennen meitä, on silti mahdotonta olla huomaamatta, että J. Buhl opetti 16-vuotiaana kyläkoulussa ja 20-vuotiaana hän avasi oman koulun Lincolniin. Matemaatikko puhui sujuvasti viittä vierasta kieltä, ja vapaa-ajallaan hän luki teoksiaNewton ja Lagrange. Ja kaikki tämä on yksinkertaisen työntekijän pojasta!

Kuva
Kuva

Vuonna 1839 Boole lähetti ensimmäisen kerran tieteelliset artikkelinsa Cambridge Mathematical Journaliin. Tiedemies on 24-vuotias. Boolen työ kiinnosti Royal Societyn jäseniä niin paljon, että hän sai vuonna 1844 mitalin panoksestaan matemaattisen analyysin kehittämiseen. Useat julkaistut teokset, joissa kuvattiin matemaattisen logiikan elementtejä, antoivat nuorelle matemaatikolle mahdollisuuden ottaa professorin virkaan College of Corkissa. Muista, että Buhlilla itsellään ei ollut koulutusta.

Idea

Periaatteessa Boolen algebra on hyvin yksinkertainen. On väitteitä (loogisia ilmaisuja), jotka matematiikan näkökulmasta voidaan määritellä vain kahdella sanalla: "tosi" tai "epätosi". Esimerkiksi keväällä puut kukkivat - totta, kesällä sataa lunta - valhe. Tämän matematiikan kauneus on, että ei ole tiukkaa tarvetta käyttää vain numeroita. Kaikki lausunnot, joilla on yksiselitteinen merkitys, sopivat hyvin tuomion algebraan.

Siten logiikan algebraa voidaan käyttää kirjaimellisesti kaikkialla: ohjeiden ajoittamisessa ja kirjoittamisessa, tapahtumien ristiriitaisen tiedon analysoinnissa ja toimintojen järjestyksen määrittämisessä. Tärkeintä on ymmärtää, että on täysin yhdentekevää, miten määritämme väitteen totuuden tai valheellisuuden. Nämä "miten" ja "miksi" on otettava pois. Vain tosiasian toteamuksella on merkitystä: tosi-epätosi.

Tietenkin ohjelmoinnissa tärkeitä ovat logiikan algebran funktiot, jotka vastaavatmerkkejä ja symboleja. Ja niiden oppiminen tarkoittaa uuden vieraan kielen hallintaa. Mikään ei ole mahdotonta.

Peruskäsitteet ja määritelmät

Syvyyteen menemättä, käsitellään terminologiaa. Joten Boolen algebra olettaa:

  • lausunnot;
  • loogiset toiminnot;
  • funktiot ja lait.

Lausunnat ovat myönteisiä ilmaisuja, joita ei voida tulkita moniselitteisesti. Ne on kirjoitettu numeroina (5 > 3) tai muotoiltu tutuin sanoin (norsu on suurin nisäkäs). Samalla ilmauksella "kirahvilla ei ole kaulaa" on myös oikeus olla olemassa, vain Boolen algebra määrittelee sen "vääräksi".

Kaikkien lauseiden on oltava yksiselitteisiä, mutta ne voivat olla alkeellisia ja yhdistelmiä. Jälkimmäiset käyttävät loogisia yhteyksiä. Toisin sanoen tuomioalgebrassa yhdistetyt lauseet muodostetaan lisäämällä peruslauseita loogisten operaatioiden avulla.

Kuva
Kuva

Boolen algebran operaatiot

Muistamme jo, että operaatiot tuomioalgebrassa ovat loogisia. Aivan kuten lukualgebra käyttää aritmetiikkaa lukujen lisäämiseen, vähentämiseen tai vertailuun, matemaattisen logiikan elementit antavat sinun tehdä monimutkaisia väitteitä, kumota tai laskea lopputuloksen.

Loogiset operaatiot formalisointiin ja yksinkertaisuuteen kirjoitetaan meille aritmetiikassa tutuilla kaavoilla. Boolen algebran ominaisuudet mahdollistavat yhtälöiden kirjoittamisen ja tuntemattomien laskemisen. Loogiset operaatiot kirjoitetaan yleensä totuustaulukon avulla. Sen sarakkeetmääritä laskennan elementit ja niille suoritettava toiminto, ja viivat näyttävät laskennan tuloksen.

Loogiset perustoiminnot

Boolen algebran yleisimmät operaatiot ovat negaatio (EI) ja looginen AND ja OR. Lähes kaikki tuomioalgebran toimet voidaan kuvata tällä tavalla. Tutkitaan kutakin kolmea operaatiota yksityiskohtaisemmin.

Negaatio (ei) koskee vain yhtä elementtiä (operandi). Siksi negatiivista operaatiota kutsutaan unaariseksi. Kirjoita "ei A"-käsite käyttämällä seuraavia symboleja: ¬A, A¯¯¯ tai !A. Taulukkomuodossa se näyttää tältä:

Kuva
Kuva

Negataatiofunktiolle on ominaista seuraava lause: jos A on tosi, niin B on epätosi. Esimerkiksi Kuu pyörii Maan ympäri - totta; Maa pyörii kuun ympäri - väärin.

Looginen kerto- ja yhteenlasku

Loogista AND-toimintoa kutsutaan konjunktiooperaatioksi. Mitä se tarkoittaa? Ensinnäkin, että sitä voidaan soveltaa kahteen operandiin, eli Ja on binääritoiminto. Toiseksi, että vain molempien operandien (sekä A että B) totuuden tapauksessa lauseke itse on tosi. Sananlasku "Kärsivällisyys ja työ jauhaa kaiken" viittaa siihen, että vain molemmat tekijät auttavat ihmistä selviytymään vaikeuksista.

Kirjoituksessa käytetyt symbolit: A∧B, A⋅B tai A&&B.

Konjunktio on samanlainen kuin kertolasku aritmetiikassa. Joskus he sanovat, että - looginen kertolasku. Jos kerromme taulukon elementit riviltä, saamme loogista päättelyä vastaavan tuloksen.

Disjunction on looginen TAI-operaatio. Se vaatii totuuden arvonkun ainakin yksi väitteistä on tosi (joko A tai B). Se kirjoitetaan näin: A∨B, A+B tai A||B. Näiden operaatioiden totuustaulukot ovat:

Kuva
Kuva

Disjunktio on kuin aritmeettinen yhteenlasku. Loogisella summausoperaatiolla on vain yksi rajoitus: 1+1=1. Mutta muistamme, että digitaalisessa muodossa matemaattinen logiikka on rajoitettu arvoihin 0 ja 1 (jossa 1 on tosi, 0 on epätosi). Esimerkiksi lause "museossa voit nähdä mestariteoksen tai tavata mielenkiintoisen keskustelukumppanin" tarkoittaa, että voit nähdä taideteoksia tai voit tavata mielenkiintoisen henkilön. Samanaikaisesti ei ole poissuljettua mahdollisuutta, että molemmat tapahtumat tapahtuvat samanaikaisesti.

Toiminnot ja lait

Joten, tiedämme jo mitä loogisia operaatioita Boolen algebra käyttää. Funktiot kuvaavat kaikkia matemaattisen logiikan elementtien ominaisuuksia ja mahdollistavat monimutkaisten ongelmien yhdistelmäehtojen yksinkertaistamisen. Ymmärrettävin ja yksinkertaisin ominaisuus näyttää olevan johdettujen operaatioiden hylkääminen. Johdannaiset ovat yksinomainen TAI, implikaatio ja ekvivalenssi. Koska olemme tutkineet vain perusoperaatioita, huomioimme myös vain niiden ominaisuudet.

Assosiatiivisuus tarkoittaa, että lauseissa, kuten "ja A, ja B ja C", operandien järjestyksellä ei ole väliä. Kaava on kirjoitettu näin:

(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.

Kuten näet, tämä ei ole ominaista vain konjunktiolle vaan myös disjunktiolle.

Kuva
Kuva

Kommutatiivisuus sanoo, että tuloskonjunktio tai disjunktio ei riipu siitä, mikä elementti katsottiin ensin:

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

Hajauttaminen mahdollistaa sulkeiden laajentamisen monimutkaisissa loogisissa lausekkeissa. Säännöt ovat samanlaiset kuin avaussulkeissa kerto- ja yhteenlaskennassa algebrassa:

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

Yksien ja nollan ominaisuudet, jotka voivat olla yksi operandeista, ovat myös samanlaisia kuin algebrallinen kertominen nollalla tai yhdellä ja yhteenlasku yhdellä:

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

Idempotenssi kertoo meille, että jos operaation tulos osoittautuu kahden samanlaisen operandin suhteen samanlaiseksi, voimme "heittää pois" ylimääräiset operandit, jotka vaikeuttavat päättelyn kulkua. Sekä konjunktio että disjunktio ovat idempotentteja operaatioita.

B∧B=B; B∨B=B.

Absorptio mahdollistaa myös yhtälöiden yksinkertaistamisen. Absorptio sanoo, että kun yhtä operandia käyttävään lausekkeeseen sovelletaan toista operaatiota samalla elementillä, tuloksena on absorboivan operaation operandi.

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

Toimintojakso

Toimintojaksolla ei ole vähäistä merkitystä. Itse asiassa, kuten algebrassa, Boolen algebrassa on prioriteetti funktiot. Kaavoja voidaan yksinkertaistaa vain, jos toimintojen merkitys huomioidaan. Luokittelu merkittävimmästä pienimpään, saamme seuraavan järjestyksen:

1. Kieltäminen.

2. Konjunktio.

3. Disjunktio, eksklusiivinenTAI.

4. Implikaatio, vastaavuus.

Kuten näet, vain negaatiolla ja konjunktiolla ei ole yhtäläistä etusijaa. Ja disjunktion ja XOR:n prioriteetit ovat samat, samoin kuin implikoinnin ja ekvivalenssin prioriteetit.

implikaatio- ja ekvivalenssifunktiot

Kuten olemme jo todenneet, loogisten perusoperaatioiden lisäksi matemaattinen logiikka ja algoritmien teoria käyttävät derivaattoja. Yleisimmin käytettyjä ovat implikaatio ja ekvivalenssi.

Implikaatio tai looginen seuraus on lause, jossa yksi toiminta on ehto ja toinen on seuraus sen toteutuksesta. Toisin sanoen tämä on lause, jossa on prepositiot "jos … sitten." "Jos pidät ratsastamisesta, rakasta kelkkojen kantamista." Eli hiihtoa varten sinun on kiristettävä kelkka mäkeä ylös. Jos ei halua liikkua alas vuorelta, sinun ei tarvitse kantaa kelkkaa. Se kirjoitetaan näin: A→B tai A⇒B.

Ekvivalenssi olettaa, että tuloksena oleva toiminta tapahtuu vain, kun molemmat operandit ovat tosi. Esimerkiksi yö muuttuu päiväksi, kun (ja vain kun) aurinko nousee horisontin yli. Matemaattisen logiikan kielellä tämä lause kirjoitetaan seuraavasti: A≡B, A⇔B, A==B.

Muut Boolen algebran lait

Tuomioiden algebra kehittyy, ja monet kiinnostuneet tiedemiehet ovat muotoilleet uusia lakeja. Skotlantilaisen matemaatikon O. de Morganin postulaatteja pidetään tunnetuimpina. Hän huomasi ja määritteli sellaiset ominaisuudet kuin läheinen negaatio, komplementti ja kaksoisnegatio.

Sulje negaatio tarkoittaa, että sulkujen edessä ei ole kieltämistä:ei (A tai B)=ei A tai EI B.

Kun operandi negoidaan sen arvosta riippumatta, puhutaan komplementista:

B∧¬B=0; B∨¬B=1.

Ja lopuksi kaksoisnegatio kompensoi itsensä. Nuo. joko negaatio katoaa ennen operandia tai vain yksi jää jäljelle.

Kuinka ratkaista testejä

Matemaattinen logiikka edellyttää annettujen yhtälöiden yksinkertaistamista. Aivan kuten algebrassa, sinun on ensin tehtävä ehdosta mahdollisimman helppo (päästä eroon monimutkaisista syötteistä ja operaatioista niillä) ja sitten alkaa etsiä oikeaa vastausta.

Mitä voidaan tehdä yksinkertaistamiseksi? Muunna kaikki johdetut operaatiot yksinkertaisiksi. Avaa sitten kaikki kiinnikkeet (tai päinvastoin, ota se pois suluista lyhentääksesi tätä elementtiä). Seuraava askel pitäisi olla Boolen algebran ominaisuuksien soveltaminen käytännössä (absorptio, nollan ja ykkösen ominaisuudet jne.).

Kuva
Kuva

Viime kädessä yhtälön tulisi koostua vähimmäismäärästä tuntemattomia yhdistettynä yksinkertaisiin operaatioihin. Helpoin tapa löytää ratkaisu on saavuttaa suuri määrä läheisiä negatiivisia. Sitten vastaus ponnahtaa esiin kuin itsestään.

Suositeltava: