Boolean algebra. algebra av logik. Delar av matematisk logik

I dagens värld är vi allt mer med hjälp av olika maskiner och prylar. Och inte bara när det är nödvändigt att tillämpa bokstavligen övermänsklig styrka: flytta lasten för att höja den till höjden, gräva långt och djupt dike, etc. Cars dag samla robotar är mat tillagas Multivarki och elementära aritmetiska beräkningar producerar räknare ... Allt oftare hör vi frasen "Boolean algebra". Kanske är det dags att förstå betydelsen av mänskliga varelser i skapandet av robotar och maskiner förmågan att lösa inte bara matematiskt, men också logiska problem.

logik

I den grekiska logik - ett ordnat tankesystem som skapar förhållandet mellan de givna villkoren och låter dig dra slutsatser baserade på antaganden och uppskattningar. Ofta frågar vi varandra: "Det är logiskt att" Svaret bekräftar våra antaganden eller kritiserar tankegång. Men processen slutar inte där: vi fortsätter att prata.

Ibland antal villkor (input) är så stor, och förhållandet mellan dem är så förvirrande och komplex att den mänskliga hjärnan inte kan "smälta" alla på en gång. Du kan behöva mer än en månad (vecka, år) för att förstå vad som händer. Men det moderna livet inte ger oss dessa tidsintervaller för att fatta beslut. Och vi tillgripa hjälp av datorer. Och det är här som det finns en algebra och logik, med sina lagar och egenskaper. Efter nedladdning alla de ursprungliga uppgifterna, tillåter vi att datorn känner igen alla relationer, för att eliminera motsägelser och att finna en tillfredsställande lösning.

Matematik och logik

Kända Gotfrid Vilgelm Leybnits formulerade begreppet "matematisk logik", vilka uppgifter var lätta att förstå bara en liten krets av forskare. Av särskilt intresse är den riktning inte orsakar och till mitten av XIX-talet av matematisk logik känd av få.

Det stora intresset för det vetenskapliga samfundet har orsakat en tvist där engelsmannen Dzhordzh Bul deklarerat sin avsikt att etablera en gren av matematiken, att inte ha någon som helst praktisk användning. Som vi vet från historien, vid denna tid aktivt utveckla industriell produktion har vi utvecklat alla typer av hjälpmaskiner, har t. E. Alla vetenskapliga upptäckter hade en praktisk inriktning.

Framöver säger vi att en Boolean algebra - den mest använda i världen i dag en del av matematiken. Så din argument Buhl förlorade.

Dzhordzh Bul

Personlighet författaren förtjänar särskild uppmärksamhet. Även med tanke på att under de senaste människor växte upp framför oss, fortfarande det bör noteras att under de 16 år av John. Buhl visade på byskolan, och till 20 år öppnade sin egen skola i Lincoln. Matematiker perfekt behärskar fem främmande språk, och på sin fritid, läste verk Newton och Lagrange. Och allt detta - på en vanlig arbetare son!

1839, Buhl skickade sina första vetenskapliga artiklar i Cambridge Mathematical Journal. Forskare vände 24 år gammal. Boole arbete är så intresserade medlemmar i Royal Society, 1844 han fick en medalj för hans bidrag till utvecklingen av matematisk analys. Några publicerade artiklar i vilka delar av matematisk logik, matematik tillåts de unga att ta tjänsten som professor i College of Cork County beskrevs. Minns att i mycket Boole utbildning var det inte.

idé

I princip är Boolean algebra mycket enkel. Det finns påståenden (logiska uttryck) som från synvinkel matematik, bara kan definieras i två ord: "true" eller "false". Till exempel träd i vårblomningen - sanningen, på sommaren det snöar - en lögn. Skönheten i matematik är att det inte är absolut nödvändigt att använda enbart siffror. För algebra domar riktigt passar några uttalanden med unik betydelse.

Således kan algebra av logik användas bokstavligen överallt: i schemaläggning och skriva instruktioner, analys av motstridiga uppgifter om händelserna och fastställandet av den följd av åtgärder. Det viktigaste - att inse att det inte spelar någon roll hur vi bestämmer sanningen eller falskheten i uttalanden. Från dessa "hur" och "varför" du behöver för att ignorera. Det viktiga är bara ett konstaterande: sanningen är en lögn.

Naturligtvis programmering av de viktigaste funktionerna i algebra av logik som registreras med lämpliga tecken och symboler. Och lär dem - det innebär att lära sig ett nytt främmande språk. Ingenting är omöjligt.

Grundläggande begrepp och definitioner

Utan att gå in på djupet, tar vi med terminologi. Så förutsätter Boolean algebra:

• uttalanden;
• logiska operationer;
• funktioner och lagar.

Uttalanden - varje jakande uttryck som kan tolkas två värderad. De är skrivna som tal (5> 3) eller formulerade välbekanta ord (elefant - den största däggdjur). I det här fallet "giraffen hals är inte" frasen har också rätt att existera, endast Boolean algebra definiera det som "en lögn."

Alla uppgifter bör vara entydig, men de kan vara grundläggande eller förening. Senaste använda logiska bunt. E. I algebra uttalanden domar förening bildad genom tillsats av elementära logiska operationer.

Boolesk algebra operationer

Vi minns redan att verksamheten i algebra av domar - logiskt. Precis som algebra av siffror med de aritmetiska operationer för att addera, subtrahera, eller jämföra siffror, matematiska logikelement gör det möjligt att göra komplexa uttalanden, att förneka eller att beräkna slutresultatet.

Logiska operationer för formalisering och enkelhet som uttrycks av formeln bekant för oss i aritmetik. Egenskaper för Boolean algebra ekvationer gör det möjligt att spela in och beräkna det okända. Logiska operationer brukar registreras av sanningstabellen. Dess element definierar kolumner och beräkningsoperation, som utförs på dem, och raderna visar resultatet av beräkningarna.

Grundläggande logik handlings

Den vanligaste i Boolesk algebra verksamheten är negation (NOT), och den logiska AND och OR. Så det är möjligt att beskriva praktiskt taget alla steg i algebra domar. Vi studerade i detalj var och en av de tre operationer.

Negationen (ej) appliceras på endast ett element (operand). Därför är funktionen kallas unär negation. För att spela in begreppet "inte en" använder sådana symboler: ¬A, A eller A !. I tabellform det ser ut så här:

Funktionen för förnekande typisk för ett sådant uttalande: om A är sant, då A - är falskt. Till exempel månen kretsar kring jorden - sanningen; Jorden kretsar kring månen - en lögn.

Logisk multiplikation och addition

Logisk OCH-operation kallas en konjunktion. Vad betyder det? För det första, att den kan appliceras på två operander, dvs I - .. binär operation. För det andra är det bara i fallet med sanningen i båda operander (både A och B) är sant och uttrycket själv. Ordspråket "Tålamod och en liten ansträngning" innebär att endast två faktorer kan hjälpa en person att hantera svårigheterna.

symboler används för inspelning: A∧B, A⋅B eller A && B.

Tillsammans liknar multiplikation i aritmetik. Ibland och säga - logisk multiplikation. Om du multiplicerar de delar av raderna i tabellen, får vi ett resultat som liknar logiskt tänkande.

Disjunktion är en logisk ELLER-operation. Det är SANT om åtminstone en av de påståenden är sant (antingen A eller B). Det är skrivet så här: A∨B, A + B eller A || B. sanningstabellen för dessa operationer är:

Disjunktion liknande aritmetisk addition. logisk additionsoperationen endast har en begränsning: en + 1 = 1. Men vi komma ihåg att i ett digitalt format är begränsad till matematisk logik 0 och 1 (där 1 - sanningen, 0 - false). Till exempel påståendet "i museet kan du se ett mästerverk eller hitta ett bra företag" betyder vad du kan se konstverk, och det är möjligt att uppfylla en intressant person. Samtidigt, utesluter inte möjligheten av samtidig uppfyllande av båda händelserna.

Funktioner och lagar

Så vi vet redan vad den logiska operation med hjälp av boolesk algebra. Funktioner beskriva alla egenskaper hos de delar av matematisk logik, och tillåter oss att förenkla komplexa sammansatta uttalanden. Den mest tydliga och enkla verkar avvisande egendom derivatverksamhet. Med derivat förstås XOR, implikation och ekvivalens. Som vi har skrivskyddad med de grundläggande funktionerna, och sedan fastigheten är också bara betrakta dem.

Associativitet innebär att i uttalanden som "både A och B, och B-sekvensen notering av operander spelar ingen roll. Formeln skrivs på följande sätt:

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

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

Som ni ser är detta inte unikt för samverkan men en disjunktion.

Kommutativitet hävdar att resultatet av samverkan eller disjunktion inte beror på vilket objekt ansågs från början:

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

Distributivity gör avslöja parentes i komplexa logiska uttryck. Regler liknar öppningen parentes i multiplikation och tillägg i algebra:

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

Enhetsegenskaper och repa, som kan vara en av operanderna är också liknande den algebraiska multiplikation med noll eller ett, och tillsats av en enhet:

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

Idempotent berättar att om relativt två lika operander resultatet av operationen är densamma, kan du "kasta" överskottet komplicera resonemang operander. Och konjunktionen och disjunktion verksamhet är idempotent.

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

Förvärv gör det också möjligt för oss att förenkla ekvationen. Absorption anges att när uttrycket appliceras på en operand, är en annan operation med samma element av resultatet operanden absorberande operationen.

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

sekvens av operationer

Sekvensen av operationer är av stor betydelse. Egentligen som för algebra, det är en prioriterad funktion som använder en Boolesk algebra. Formler kan förenklas endast under förutsättning att betydelsen av verksamheten. Rankning av störst betydelse för försumbar, får vi följande ordning:

1. Denial.

2. Conjunction.

3. disjunktion, XOR.

4. implikation, ekvivalens.

Som ni kan se, bara en negation av konjunktionen och inte har samma prioritet. En prioritering för disjunktion och XOR är lika, liksom prioriteringar implikation och ekvivalens.

Funktioner av implikation och ekvivalens

Som vi har sagt, utöver de grundläggande logiska operationer, matematisk logik och teori av algoritmer med användning av derivat. Det är oftast innebörden och likvärdighet.

Innebörden eller logisk konsekvens - detta uttalande, i vilket en åtgärd är ett tillstånd, och den andra - resultatet av dess genomförande. Med andra ord, det här förslaget med att "om ... sedan" förevändning. "Efter middagen kommer räkenskapen." E. För körning dras åt på släden backen. Om det inte finns någon önskan att gå ned från berget, och sedan dra släden är inte nödvändigt. Skrivs så: A → B eller A⇒B.

Likvärdighet innebär att nettoeffekten sker endast när båda operander är sanna. Till exempel ger natten väg till dag då (och bara då), när solen går upp över horisonten. I språket av matematiska logiken i detta uttalande är skriven som A≡B, A⇔B, A == B.

Andra lagar Boolean algebra

Algebra dom utvecklar och många intresserade forskare att formulera nya lagar. Den mest kända anses postulerar skotsk matematiker O. De Morgan. Han märkt och gav en definition av sådana egenskaper som nära negation, addition och dubbel negativ.

Nära förnekande antyder att innan parentes är inte att förneka: inte (A eller B) = ej A eller B. INTE

När operanden nekas, oavsett dess värde, säger om tillägg:

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

Och slutligen, den dubbla negation själv kompenserar. dvs innan någon operand negation försvinner eller återstår bara en.

Hur man löser tester

Logik förutförenklingsförutbestämda ekvationer. Precis som i liealgebra, är det nödvändigt att maximalt underlätta första villkoret (att bli av med komplicerade inmatningsoperationer, och med dem) och sedan börja leta efter ett korrekt svar.

Vad göra för att förenkla? Konvertera alla derivaten i en enkel operation. avslöja sedan alla konsoler (eller vice versa, för att göra fästena för att minska detta element). Nästa steg bör vara att använda booleska algebra egenskaper i praktiken (absorptionsegenskaper noll och ett, och t.).

I slutändan bör ekvationen bestå av ett minimalt antal okända, i kombination med enkla handgrepp. Det enklaste sättet att leta efter en lösning, om du gör ett stort antal nära negativ. Då svaret kommer att dyka upp som om av sig själv.