Boolsk algebra. algebra av logikk. Elementer av matematisk logikk

I dagens verden er vi i økende grad bruker en rekke maskiner og gadgets. Og ikke bare når det er nødvendig å bruke bokstavelig talt overmenneskelig styrke: flytte lasten å heve den til høyden, grave lang og dyp grøft, etc. biler i dag samle roboter, maten er tilberedt Multivarki og elementære aritmetiske beregninger produsere kalkulatorer ... Stadig oftere hører vi uttrykket "boolsk algebra". Kanskje tiden er inne til å forstå rollen av mennesker i etableringen av roboter og maskiner evnen til å løse ikke bare matematisk, men også logiske problemer.

logikk

I gresk logikk - en ordnet tankesystem som skaper forholdet mellom de gitte forhold, og gir deg mulighet til å gjøre slutninger basert på forutsetninger og estimater. Ganske ofte, spør vi hverandre: "Det er logisk å" Svaret bekrefter våre antakelser eller kritiserer tankegang. Men prosessen stopper ikke der: vi fortsetter å snakke.

Noen ganger antallet tilstander (input) er så stor, og forholdet mellom dem er så forvirrende og sammensatt at den menneskelige hjerne er ikke i stand til å "fordøye" alt på en gang. Du kan trenge mer enn en måned (uke, år) for forståelsen av hva som skjer. Men moderne liv ikke gir oss disse tidsintervaller for å ta beslutninger. Og vi ty til hjelp av datamaskiner. Og det er her at det er en algebra og logikk, med sine lover og egenskaper. Etter nedlasting alle de opprinnelige dataene, tillater vi at datamaskinen gjenkjenner alle relasjoner, for å eliminere motsetninger og å finne en tilfredsstillende løsning.

Matematikk og logikk

Berømte Gotfrid Vilgelm Leybnits formulert begrepet "matematisk logikk", hvilke oppgaver var enkle å forstå bare en liten sirkel av lærde. Av spesiell interesse er retningen ikke føre til, og til midten av det nittende århundre av matematisk logikk kjent av noen.

Den store interessen i det vitenskapelige samfunnet har forårsaket en tvist der engelsk Dzhordzh Bul erklærte sin intensjon om å etablere en gren av matematikk, ikke har absolutt ingen praktisk bruk. Som vi vet fra historien, på denne tiden aktivt med å utvikle industriell produksjon, utviklet vi alle typer hjelpemaskiner, har t. E. Alle vitenskapelige oppdagelser hadde en praktisk orientering.

Se fremover, sier vi at en boolsk algebra - den mest brukte i verden i dag en del av matematikk. Så ditt argument Buhl tapt.

Dzhordzh Bul

Personligheten til forfatteren fortjener spesiell oppmerksomhet. Selv gitt det faktum at de siste menneskene vokste opp før oss, likevel bør det bemerkes at i de 16 årene av John. Buhl undervist ved landsbyens skole, og til 20 år åpnet sin egen skole i Lincoln. Matematiker perfekt mestret fem fremmedspråk, og på fritiden, var å lese verkene til Newton og Lagrange. Og alt dette - på en vanlig arbeidstaker sønn!

I 1839, Buhl sendte sine første vitenskapelige artikler i Cambridge Mathematical Journal. Forsker slått 24 år. Boole arbeid er så interesserte medlemmer av Royal Society, i 1844 fikk han en medalje for sitt bidrag til utviklingen av matematisk analyse. Noen publiserte artikler der elementene i matematisk logikk, matematikk tillot unge til å ta stillingen som professor i College of Cork fylke ble beskrevet. Husk at i det Boole utdanning var det ikke.

idé

I prinsippet er boolsk algebra svært enkel. Det er uttalelser (logiske uttrykk) at det fra synspunkt av matematikk, kan bare defineres i to ord: "true" eller "false". For eksempel trær i våroppblomstringen - sannheten om sommeren snør det - en løgn. Det fine med matematikk er at det er strengt tatt ikke nødvendig å bruke bare tall. For algebra dommene helt passer noen uttalelser med unik betydning.

Således kan den algebra av logikk benyttes bokstavelig talt overalt: i planlegging og skrive instruksjon, analyse av motstridende informasjon om hendelser og bestemmelse av sekvensen av handlinger. Det viktigste - å innse at det ikke spiller noen rolle hvordan vi bestemme sannhet eller falskhet av uttalelser. Fra disse "hvordan" og "hvorfor" du trenger å ignorere. Det som teller er bare en uttalelse om faktum: sannheten er en løgn.

Selvfølgelig, programmering av de viktigste funksjonene i algebra logikk som er registrert med riktige tegn og symboler. Og lære dem - det innebærer å lære et nytt fremmedspråk. Ingenting er umulig.

Grunnleggende begreper og definisjoner

Uten å gå i dybden, har vi avtale med terminologi. Så, forutsetter boolsk algebra:

• uttalelser;
• logiske operasjoner;
• funksjoner og lover.

Uttalelser - en hvilken som helst bekreftende uttrykk som kan tolkes to-verdsatt. De er skrevet som tall (5> 3) eller formulert kjente ord (elefant - den største pattedyr). I dette tilfellet, uttrykket "sjiraffen halsen er ikke" har også en rett til å eksistere, bare boolsk algebra definere det som "løgn".

Alle uttalelser bør være entydig, men de kan være grunnleggende eller sammensatte. Nyere bruk logisk bunt. E. I algebra uttalelser dommer forbindelse dannet ved tilsetning av elementære logiske operasjoner.

Boolsk algebra operasjoner

Vi husker allerede at operasjonene i algebra av dommer - logisk. Akkurat som algebra av tall ved hjelp av aritmetiske operasjoner for å legge til, trekke fra, eller sammenligne tall, matematiske logiske elementer tillater å lage komplekse uttalelser, å nekte eller å beregne det endelige resultatet.

Logiske operasjoner for formalise og enkelhet kan uttrykkes ved formelen, kjent for oss i aritmetikk. Egenskaper av Boolsk algebra ligninger gjør det mulig å registrere og beregne det ukjente. Logiske operasjoner er vanligvis registrert av sannhet tabellen. Dens elementer definerer søyler og beregningsoperasjon som utføres på dem, og radene viser resultatet av beregningene.

Grunnleggende logikken i aksjon

Den vanligste i Boolsk algebra operasjoner er negasjon (NOT), og den logiske AND og OR. Så det er mulig å beskrive praktisk talt alle trinnene i algebra dommer. Vi studerte i detalj hver av de tre operasjoner.

Den negasjon (ikke) blir tilført bare ett element (operand). Derfor er operasjonen kalles en ensartet negasjon. For å ta opp begrepet "ikke en" bruker slike symboler: ¬A, A eller A !. I tabellform ser det ut som dette:

Funksjonen til fornektelse typisk for en slik uttalelse: hvis A er sann, da A - er falsk. For eksempel, månen roterer rundt jorden - sannheten; Jorden roterer rundt månen - en løgn.

Logisk multiplikasjon og addisjon

Logiske og operasjonen kalles en sammenheng. Hva betyr det? For det første, at det kan brukes på to operander, det vil si, jeg - .. Binary drift. For det andre, er det bare i tilfelle av sannheten i begge operander (både A og B) er sant og uttrykket i seg selv. Ordtaket, "Tålmodighet og en liten innsats" innebærer at bare to faktorer kan hjelpe en person takle vanskelighetene.

symboler er brukt for opptak: A∧B, A⋅B eller A && B.

Sammen er lik multiplikasjon i aritmetikk. Noen ganger og si - logisk multiplikasjon. Hvis du multipliserer elementene i radene i tabellen, vi får et resultat som ligner på logisk tenkning.

Disjunksjon er en logisk ELLER operasjon. Det er SANN hvis minst en av de påstandene gjelder (A eller B). Det er skrevet slik: A∨B, A + B eller A || B. sannhetstabellen for disse operasjonene er:

Motsetninger lignende aritmetisk addisjon. logisk addisjonsoperasjon har bare en begrensning: 1 + 1 = 1. Men vi huske at i et digitalt format er begrenset til matematisk logikk 0 og 1 (hvor 1 - sannheten, 0 - false). For eksempel utsagnet "i museet kan du se et mesterverk eller finne et godt selskap" betyr det at du kan se kunstverk, og det er mulig å møte en interessant person. På samme tid, ikke utelukke muligheten for samtidig oppfyllelse av begge hendelsene.

Funksjoner og lover

Så vi allerede vet hva den logiske operasjonen ved hjelp av boolsk algebra. Funksjoner beskrive alle egenskapene til elementene i matematisk logikk, og tillate oss å forenkle komplekse sammensatte setninger. Den mest klar og enkel synes avvisning egenskap av derivater operasjoner. Med derivater er forstått XOR, implikasjon og ekvivalens. Som vi har lest bare med de grunnleggende operasjoner, og da eiendommen er også bare vurdere dem.

Associativity betyr at i de påstander som "både A og B, og B 'sekvensliste av operandene spiller ingen rolle. Formelen er skrevet som følger:

(A∧B) ∧V = A∧ (B∧V) = A∧B∧V,

(A∨B) ∨V = A∨ (B∨V) = A∨B∨V.

Som du kan se, er dette ikke unikt for konjunksjonen men en disjunksjon.

Commutativity hevder at resultatet av samarbeid eller disjunksjon ikke er avhengig av hvilket element ble ansett i utgangspunktet:

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

Distributivity kan avsløre parentes i komplekse logiske uttrykk. Reglene er lik åpningen parentes i multiplikasjon og addisjon i algebra:

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

Enhet egenskaper og bunnen, som kan være en av operandene er også lik den algebraisk multiplikasjon med null eller en, og tilsetning av en enhet:

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

Idempotency forteller oss at hvis relativt to like operander resultatet av operasjonen er den samme, kan du "kaste" det overskytende komplisert resonnement operander. Og konjunksjonen og disjunksjon operasjoner er idempotent.

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

Oppkjøpet gir oss også muligheten til å forenkle ligningen. Absorpsjon fastslår at når uttrykket anvendes på en operand, blir en annen operasjon med det samme element av resultatet operanden absorberende drift.

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

Sekvensen av operasjoner

Sekvensen av operasjoner er av stor betydning. Faktisk, som for algebra, er det en prioritetsfunksjon som bruker en boolsk algebra. Formler kan forenkles bare lagt betydningen av operasjonene. Rangering av de mest betydningsfulle for å neglisjerbar, får vi den følgende sekvens:

1. Denial.

2. konjunksjon.

3. motsetninger, XOR.

4. Implikasjonen, ekvivalens.

Som du kan se, bare negasjonen av sammenheng og ikke har lik prioritet. En prioritet for disjunksjon og XOR er like, så vel som prioriteringer implikasjon og ekvivalens.

Funksjoner av implikasjon og ekvivalens

Som vi har sagt, i tillegg til de grunnleggende logiske operasjoner, matematisk logikk og teori om algoritmer ved bruk av derivater. Det er oftest implikasjon og ekvivalens.

Implikasjonen eller logisk konsekvens - denne uttalelsen, hvor en handling er en tilstand, og den andre - et resultat av gjennomføringen. Med andre ord, dette forslaget med påskudd om "hvis ... da". "Etter middag kommer oppgjørets time." E. For drift som skal strammes på sleden bakken. Hvis det ikke er noe ønske om å gå ned fra fjellet, og deretter drar sleden er ikke nødvendig. Er skrevet slik: A → B eller A⇒B.

Ekvivalens innebærer at nettoeffekten opptrer bare når begge operander er sanne. For eksempel, natt gir vei til dagen da (og bare da), når solen stiger opp over horisonten. I språket av matematisk logikk for denne uttalelsen er skrevet som A≡B, A⇔B, A == B.

Andre lover i boolsk algebra

Algebra dommen utvikler, og mange interesserte forskere til å formulere nye lover. Den mest kjente er ansett postulerer skotske matematikeren O. De Morgan. Han la merke til og ga en definisjon av slike egenskaper som nær negasjon, tillegg og dobbel negativ.

Lukk fornektelse antyder at før parentes er ikke benektes: ikke (A eller B) = ikke A eller B. IKKE

Når operand nektes, uavhengig av sin verdi, si om tillegg:

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

Og til slutt, dobbel negasjon selv kompenserer. dvs. før enten operand negasjon forsvinner eller forblir bare en.

Hvordan løse testene

Logikk medfører forenkling forutbestemte likninger. Akkurat som i Lie algebra, er det nødvendig å maksimalt forenkle første betingelsen (for å kvitte seg med kompliserte inngangs operasjoner, og med dem), og deretter begynne å lete etter et riktig svar.

Hva gjør du for å forenkle? Konverter alle derivatene i en enkel operasjon. Deretter avdekke alle brakettene (eller vice versa, for å gjøre brakettene for å redusere dette element). Det neste trinnet bør være å bruke Boolsk algebra egenskaper i praksis (absorpsjonsegenskaper null og en, og t.).

Ideelt sett skal ligningen bestå av et minimum antall ukjente, kombinert med enkle operasjoner. Den enkleste måten å se etter en løsning, hvis du gjør et stort antall nære negativer. Så svaret vil dukke opp som om seg selv.