Boolsk algebra. algebra af logik. Elementer af matematisk logik

I dagens verden er vi i stigende grad ved hjælp af forskellige maskiner og gadgets. Og ikke kun, når det er nødvendigt at anvende bogstaveligt overmenneskelig styrke: flytte lasten for at hæve det til højden, grave lang og dyb grøft mv biler i dag indsamle robotter, er mad tilberedt Multivarki og elementære aritmetiske beregninger producere regnemaskiner ... Oftere og oftere hører vi udtrykket "boolsk algebra". Måske er tiden inde til at forstå betydningen af mennesket i skabelsen af robotter og maskiner evnen til at løse ikke kun matematisk, men også logiske problemer.

logik

I den græske logik - et ordnet system af tanker, der skaber sammenhængen mellem de givne betingelser og giver dig mulighed for at drage slutninger baseret på forudsætninger og skøn. Ganske ofte, vi spørger hinanden: "Det er logisk at" Svaret bekræfter vores antagelser eller kritiserer tankegang. Men processen stopper ikke der: vi fortsætter med at tale.

Undertiden række betingelser (input) er så stor, og forholdet mellem dem er så forvirrende og kompleks, at den menneskelige hjerne er ikke i stand til at "fordøje" på én gang. Du skal muligvis mere end en måned (uge, år) for forståelsen af, hvad der sker. Men moderne liv giver os ikke disse tidsintervaller til at træffe beslutninger. Og vi ty til hjælp fra computere. Og det er her, at der er en algebra og logik, med dens love og egenskaber. Efter at have downloadet alle de oprindelige data, vi så computeren kan genkende alle relationer, for at eliminere modsætninger og at finde en tilfredsstillende løsning.

Matematik og logik

Berømte Gotfrid Vilgelm Leybnits formulerede begrebet "matematisk logik", hvilke opgaver var nemme at forstå kun en lille kreds af forskere. Af særlig interesse er den retning forårsagede ikke, og til midten af det XIX århundrede af matematisk logik kendt af få.

Den store interesse for det videnskabelige samfund har forårsaget en tvist, hvor englænderen Dzhordzh Bul erklæret sin hensigt om at etablere en gren af matematikken, der ikke har absolut ingen praktisk brug. Som vi ved fra historien, på dette tidspunkt aktivt at udvikle industriel produktion, vi udviklet alle former for hjælpeansatte maskiner, har t. E. Alle videnskabelige opdagelser havde en praktisk orientering.

Fremadrettet siger vi, at en boolsk algebra - den mest anvendte i verden i dag en del af matematik. Så din argumentation Buhl tabt.

Dzhordzh Bul

Den personlighed af forfatteren fortjener særlig opmærksomhed. Selv i betragtning af, at der i de sidste mennesker voksede op foran os, der stadig skal det bemærkes, at i de 16 år af John. Buhl underviste ved landsbyen skole, og til 20 år åbnede sin egen skole i Lincoln. Matematiker perfekt mestrer fem fremmedsprog, og i sin fritid, læste værker af Newton og Lagrange. Og alt dette - på en almindelig arbejdstagers søn!

I 1839, Buhl sendte sine første videnskabelige artikler i Cambridge Matematisk Journal. Forsker vendte 24 år. Boole arbejde er så interesserede medlemmer af Royal Society, i 1844, han har modtaget en medalje for sit bidrag til udviklingen af matematisk analyse. Et par offentliggjort papirer, hvor de elementer af matematisk logik, matematik tilladt de unge til at tage en stilling som professor i kollegiet af Cork blev beskrevet. Husk på, at i det Boole uddannelse var ikke.

idé

I princippet boolsk algebra er meget enkel. Der er udsagn (logiske udtryk), at fra synspunkt matematik, kun kan defineres i to ord: "true" eller "false". Eksempelvis træer i forårsopblomstringen - sandheden, i sommeren det sne - en løgn. Skønheden i matematik er, at det ikke er strengt nødvendigt at bruge kun tal. For algebra domme helt passer erklæringer med enestående betydning.

Således kan den algebra af logik bruges bogstaveligt talt overalt: i planlægningen og skrivning instruktion, analyse af modstridende oplysninger om de begivenheder og bestemmelse af rækkefølgen af handlinger. Det vigtigste - at indse, at det ikke betyder noget, hvordan vi bestemme sandheden eller falskheden af udsagn. Fra disse "hvordan" og "hvorfor" du har brug for at ignorere. Det afgørende er kun en konstatering af fakta: sandheden er en løgn.

Selvfølgelig programmere de vigtigste funktioner i algebra af logik, som er optaget med passende tegn og symboler. Og lære dem - det vil sige at lære et nyt fremmedsprog. Intet er umuligt.

Grundlæggende begreber og definitioner

Uden at gå i dybden, vi beskæftiger os med terminologi. Så boolsk algebra forudsætter:

• udsagn;
• logiske operationer;
• funktioner og love.

Udtalelser - enhver bekræftende udtryk, der kan fortolkes med to værdier. De er skrevet som tal (5> 3) eller formuleret velkendte ord (elefant - den største pattedyr). I dette tilfælde er udtrykket "giraffen hals er ikke" også har en ret til at eksistere, kun boolsk algebra definere det som "en løgn."

Alle udsagn skal være entydige, men de kan være grundlæggende eller sammensatte. Nylig brug logisk bundt. E. I algebra udsagn domme forbindelse dannet ved tilsætning af elementære logiske operationer.

Boolske algebra operationer

Vi har allerede huske, at operationerne i algebra af retsafgørelser - logisk. Ligesom algebra tal, der bruger de aritmetiske operationer for at tilføje, trække fra, eller sammenligne tal, matematiske logiske elementer gør det muligt at foretage komplekse udsagn, at benægte eller til at beregne det endelige resultat.

Logic aktiviteter for formalisering og enkelhed udtrykkes ved formlen, velkendt for os i aritmetik. Egenskaber af Boolske algebra ligninger gør det muligt at optage og beregne det ukendte. Logiske operationer er normalt registreres af sandheden bordet. Dens elementer definerer søjler og computing operation, der udføres på dem, og rækkerne viser resultatet af beregningerne.

Grundlæggende logik handling

Den mest almindelige i de booleske algebra operationer er negation (NOT), og den logiske AND og OR. Så det er muligt at beskrive stort set alle trin i algebra domme. Vi studerede i detaljer hver af de tre operationer.

Negationen (ikke) påføres kun et element (operand). Derfor er operationen kaldes en unary negation. For at optage begrebet "ikke en" anvender sådanne symboler: ¬A, A eller A !. I tabelform ser det sådan ud:

Funktionen af benægtelse typisk for en sådan erklæring: hvis A er sand, så A - er falsk. For eksempel, månen kredser rundt om Jorden - sandheden; Jorden drejer rundt om månen - en løgn.

Logiske multiplikation og addition

Logisk og kaldes en forbindelse. Hvad betyder det? For det første, at det kan anvendes på to operander, dvs. I - .. Binary drift. For det andet er det kun i tilfælde af sandheden i begge operander (både A og B) er sande og selve udtrykket. Det ordsprog, "Tålmodighed og en lille indsats" indebærer, at kun to faktorer kan hjælpe en person at klare vanskelighederne.

symboler bruges til optagelse: A∧B, A⋅B eller A && B.

Konjunktion ligner multiplikation i matematik. Nogle gange og sige - logisk multiplikation. Hvis du ganger elementerne i rækkerne i tabellen, får vi et resultat svarende til logisk tænkning.

Disjunktion er en logisk OR operation. Det er SAND, hvis mindst en af de udsagn er sandt (enten A eller B). Det er skrevet sådan her: A∨B, A + B eller A || B. sandheden tabellen for disse operationer, er:

Disjunktion lignende aritmetiske tilsætning. logisk tilføjelse drift har kun én begrænsning: 1 + 1 = 1. Men vi huske, at i et digitalt format er begrænset til matematisk logik 0 og 1 (hvor 1 - sandheden, 0 - falsk). For eksempel sætningen "i museet kan du se et mesterværk eller finde en god virksomhed" betyder hvad du kan se kunstværker, og det er muligt at møde en interessant person. På samme tid, ikke udelukke muligheden for opfyldt samtidig begge begivenheder.

Funktioner og love

Så vi ved allerede, hvad den logiske operation ved hjælp boolsk algebra. Funktioner beskrive alle de egenskaber af de elementer af matematisk logik, og give os mulighed for at forenkle komplekse sammensatte sætninger. Den mest klare og enkle synes afvisning egenskab af derivattransaktioner. Med derivater forstås XOR, implikation og ækvivalens. Som vi har læst kun med de grundlæggende funktioner, og derefter ejendommen er også kun overveje dem.

Associativitet betyder, at i de udsagn som "både A og B, og B 'sekvens liste over de operander er ligegyldigt. Formlen skrives 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 entydigt til sammen men en disjunktion.

Kommutativitet hævder, at resultatet af den sammen eller disjunktion ikke afhænger af hvilket element blev anset fra starten:

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

Distributivitet tillader afsløre parentes i komplekse logiske udtryk. Regler er magen til åbningen parentes i multiplikation og addition i algebra:

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

Unit egenskaber og bunden, som kan være en af operanderne er også lignende den algebraiske multiplikation med nul eller et, og tilsætning af en enhed:

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

Idempotent fortæller os, at hvis relativt to lige operander resultatet af operationen er den samme, kan du "smide" de overskydende komplicere ræsonnement operander. Og konjunktionen og disjunktion operationer er idempotent.

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

Erhvervelse giver os også mulighed for at forenkle ligningen. Absorption, at når ekspressionen påføres den ene operand, er en anden operation med det samme element af resultatet operand absorberende operation.

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

sekvens af operationer

Rækkefølgen af operationer er af stor betydning. Faktisk, som for algebra, der er en prioriteret funktion, der bruger en boolsk algebra. Formler kan forenkles kun underlagt betydningen af operationerne. Ranking af de mest betydningsfulde for ubetydelig, får vi den følgende sekvens:

1. Benægtelse.

2. Konjunktion.

3. disjunktion, XOR.

4. Implikationen, ækvivalens.

Som du kan se, er det kun negation af sammen og ikke har lige så højt. En prioritet for disjunktion og XOR er ens, samt prioriteterne for implicit og ækvivalens.

Funktioner af implikation og ækvivalens

Som vi har sagt, ud over de grundlæggende logiske operationer, matematisk logik og teori af algoritmer ved hjælp af derivater. Det er oftest den implikation og ækvivalens.

Implikationen eller logisk konsekvens - dette udsagn, hvor en handling er en tilstand, og den anden - resultatet af dens gennemførelse. Med andre ord, dette forslag med påskud af "hvis ... så". "Efter middagen kommer opgør." E. For kørsel, der skal strammes på slæden bakke. Hvis der ikke er noget ønske om at bevæge sig ned fra bjerget, og derefter trække slæden er ikke nødvendig. Er skrevet så: A → B eller A⇒B.

Ligestilling betyder, at nettoeffekten forekommer kun, når begge operander er sande. For eksempel natten viger for dagen derefter (og kun da), når solen står op over horisonten. På det sprog, matematisk logik af denne erklæring er skrevet som A≡B, A⇔B, A == B.

Andre love boolsk algebra

Algebra dom udvikler sig, og mange interesserede forskere til at formulere nye love. Den mest berømte betragtes postulerer skotske matematiker O. De Morgan. Han lagde mærke til og gav en definition af sådanne egenskaber som tæt negation, addition og dobbelt negativ.

Luk benægtelse tyder på, at før parentesen er ingen tvivl: ikke (A eller B) = ikke A eller B. IKKE

Når operand nægtes, uanset dens værdi, siger om tilføjelse:

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

Og endelig, den dobbelte negation selv kompenserer. dvs. før enten operand negation forsvinder eller bliver kun én.

Hvordan man løser test

Logik indebærer forenkling forudbestemte ligninger. Ligesom i Lie algebra, er det nødvendigt at maksimalt lette første betingelse (for at slippe af komplicerede input operationer, og med dem), og derefter begynde at lede efter et korrekt svar.

Hvad skal man gøre for at forenkle? Konverter alle derivaterne i en simpel operation. Så afdække alle beslagene (eller omvendt, for at gøre beslagene til at reducere dette element). Det næste skridt bør være at bruge boolske algebra egenskaber i praksis (absorptionsegenskaber nul og én, og t.).

I sidste ende bør ligningen bestå af et minimalt antal ubekendte, kombineret med enkle operationer. Den nemmeste måde at finde en løsning, hvis du laver en lang række tætte negativer. Så svaret vil poppe op, som om sig selv.