Booles algebra. Algebra av logik. Element av matematisk logik

I den moderna världen använder vi alltmeren mängd olika maskiner och gadgets. 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

På grekiska är logikenett ordnat tänkande system som skapar relationer mellan givna förhållanden och gör det möjligt för oss att göra slutsatser utifrån antaganden och antaganden. Ofta frågar vi varandra: "Är det logiskt?" Svaret svarar på våra antaganden eller kritiserar tankegången. Men processen stoppar inte: vi fortsätter att förklara.

Ibland är antalet villkor (inledande) såbra, och relationerna mellan dem är så förvirrande och komplexa att människans hjärna inte kan "smälta" allt på en gång. Det kan ta mer än en månad (en vecka, ett år) för att förstå vad som händer. Men det moderna livet ger oss inte sådana tidsintervaller för beslutsfattandet. Och vi tillgriper till hjälp av datorer. Och det här är logikens algebra med sina lagar och egenskaper. Efter att ha laddat ner alla initialdata tillåter vi datorn att känna igen alla relationer, eliminera motsättningar och hitta en tillfredsställande lösning.

Matematik och logik

Den mest berömda Gottfried Wilhelm Leibnizformulerade begreppet "matematisk logik", vars uppgifter endast var tillgängliga för en smal cirkel av forskare. Ett speciellt intresse i denna riktning orsakade inte, och till mitten av XIX-talet visste få om matematisk logik.

Stort intresse för vetenskapligaen tvist i vilken engelsmannen George Buhl meddelade sin avsikt att skapa en del av matematik som absolut inte hade någon praktisk tillämpning. Som vi kommer ihåg från historien utvecklades industriproduktionen aktivt, alla typer av hjälpmaskiner och maskiner utvecklades, det vill säga alla vetenskapliga upptäckter hade en praktisk inriktning.

Se framåt, vi säger att booles algebra är den mest använda delen av matematik i den moderna världen. Så förlorade tvisten hans Boule.

George Boule

Författarens mycket personlighet förtjänar en separatuppmä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. Matematikern behärskar helt och hållet fem främmande språk, och i sin fritid läste han av verk av Newton och Lagrange. Och allt handlar om en enkel arbetares son!

1839 skickade Boule först sin vetenskapligaarbeta i Cambridge matematiska tidskrift. Vetenskapsmannen var 24 år gammal. Boole arbetar så intresserade medlemmar av Royal Scientific Society som år 1844 fick han en medalj för sitt bidrag till utvecklingen av matematisk analys. Flera andra publicerade verk, i vilka element av matematisk logik beskrevs, tillät den unga matematiker att ta ställning som professor vid Cork County College. Minns att han själv inte var utbildad.

idé

I princip är den booleska algebra mycket enkel. Det finns uttalanden (logiska uttryck), som ur matematikens synvinkel endast kan definieras av två ord: "sanning" eller "lögn". Till exempel, på våren blommar träden - sanningen, på sommaren snöar det - ligger. All charm i denna matematik är att det inte finns något strikt behov att bara använda siffror. Eventuella propositioner med entydig mening är perfekt lämpade för propositionernas algebra.

Således kan logikkens algebra varaanvänds bokstavligen överallt: i schemaläggnings- och skrivinstruktioner, analysera motstridiga uppgifter om händelser och bestämma handlingssekvensen. Det viktigaste är att förstå att det inte spelar någon roll hur vi bestämde sanning eller falskhet i ett uttalande. Från dessa "hur" och "varför" bör abstraheras. Det enda som betyder något är faktabladet: true-false.

Visst är funktioner viktig för programmeringalgebra av logik, som är skrivna med lämpliga tecken och symboler. Och för att lära sig betyder det att behärska ett nytt främmande språk. Ingenting är omöjligt.

Grundläggande begrepp och definitioner

Utan att gå in i djupet förstår vi terminologin. Så antar boolesalgebra närvaron av:

• uttalanden;
• logiska operationer
• funktioner och lagar.

Uttalanden - alla bekräftande uttryck,vilket inte kan tolkas dubbelvärderat. De är skrivna i form av siffror (5> 3) eller formulerade med de vanliga orden (elefanten är det största däggdjuret). I det här fallet har frasen "giraffen inte en nacke" också rätt att existera, bara den booleska algebraen definierar den som en "lögn".

Alla uttalanden måste vara tydligakaraktär, men de kan vara elementära och sammansatta. Den senare använder logiska anslutningar. Det vill säga i de propositionella algebraföreningarna bildas uttalanden genom att lägga elementära element genom logiska operationer.

Operationer av booles algebra

Vi minns redan att verksamheten i propositionernas algebra -logiskt. Precis som algebra av siffror använder aritmetiska operationer för att lägga till, subtrahera eller jämföra siffror, gör elementen i matematisk logik det möjligt att komponera komplexa uttalanden, förneka eller beräkna slutresultatet.

Logiska operationer för formalisering och enkelhetskrivs ned av formlerna sedvanliga för oss i aritmetik. Egenskaperna hos den booleska algebra gör det möjligt att skriva ekvationer och beräkna okända. Logiska operationer skrivs vanligtvis med hjälp av en sanningstabell. Dess kolumner definierar beräkningselementen och den operation som utförs på dem, och raderna visar resultatet av beräkningarna.

Grundläggande logiska handlingar

Den vanligaste i boolesalgebraOperationerna är negation (NOT) och logiska AND och OR. Så du kan beskriva nästan alla handlingar i algebra av domar. Vi kommer att studera i detalj var och en av de tre operationerna.

Negation (inte) gäller endast enelement (operand). Därför kallas negationsoperationen unary. Att skriva begreppet "inte A" använder sådana symboler: ¬A, A¯¯¯ eller! A. I tabellform ser det ut så här:

För negationsfunktionen är följande uttalande typiskt: om A är sant, är A falskt. Månen kretsar till exempel runt jorden - sanningen; Jorden kretsar runt månen - en lögn.

Logisk multiplikation och addition

En logisk OCH kallas en conjunction operation. Vad betyder detta? För det första att det kan tillämpas på två operander, det vill säga jag är en binär operation. För det andra är det bara i fallet med sanningen av båda operanderna (och A, och B) själva uttrycket sant. Ordspråket "Tålamod och arbete kommer peretrut" förutsätter att endast två faktorer kommer att hjälpa en person att klara svårigheterna.

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

Konjunktion är analog med multiplikation i aritmetik. Ibland säger de så - logisk multiplikation. Om vi ​​multiplicerar tabellelementen med rader får vi ett resultat som liknar det logiska tänkandet.

Disjunktion kallas den logiska OR-operationen. Det tar på sig ett sanningsvärde när minst en av deklarationerna är sanna (eller A eller B). Det är skrivet så här: A∨B, A + B eller A || B. Sanningstabeller för dessa operationer är:

Disjunktion är som ett aritmetiskt tillägg. Funktionen av logisk tillsats har endast en begränsning: 1 + 1 = 1. Men vi kommer ihåg att i det digitala formatet är matematisk logik begränsad till 0 och 1 (där 1 är sant, 0 är falskt). Till exempel kan påståendet "i museet du se ett mästerverk eller träffa en intressant samtalare" innebära att du kan se konstverk och du kan bekanta dig med en intressant person. Samtidigt utesluts inte möjligheten att samtidigt genomföra båda händelserna.

Funktioner och lagar

Så, vi vet redan vilka logiska operationeranvänder en booles algebra. Funktioner beskriver alla egenskaper hos element i matematisk logik och låter dig förenkla komplexa sammansatta arbetsförhållanden. Det mest begripliga och enkla är att överge derivatverksamhet. Derivat är exklusiva ELLER, implikation och ekvivalens. Eftersom vi bara har bekantat oss med de grundläggande operationerna kommer vi bara att överväga egenskaperna hos dem.

associativitet betyder att i uppfattningar som "och A, och B och B" spelar uppräkningen av operander inte någon roll. Formeln är detta:

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

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

Som vi ser är detta märkligt, inte bara för konjugationer, men även disjunktioner.

kommutativitet argumenterar för att resultatet av en konjunktion eller disjunction inte beror på vilket element som beaktades i början:

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

distributivity låter dig öppna parentes i komplexa logiska uttryck. Reglerna liknar upplysningen av parentes när man multiplicerar och lägger till i algebra:

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

Egenskaper hos enheten och noll, som kan vara en av operandema, är också analog med algebraisk multiplikation med noll eller en och tillägg till en:

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

idempotent berättar att om tvålika operanda, visar resultatet av operationen sig vara analogt, då är det möjligt att "kasta ut" de extra operanderna som komplicerar förloppsförloppet. Både konjunktionen och disjunktionen är idempotenta operationer.

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

upptag tillåter oss också att förenkla ekvationer. 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 verksamheten

Operationssekvensen är viktigvärde. Egentligen, som för algebra, finns det en prioritet i funktioner som använder booles algebra. Formlerna kan förenklas endast om betydelsen av verksamheten följs. Ranking från den mest betydelsefulla till mindre får vi följande sekvens:

1. Denial.

2. Konjunktion.

3. Disjunktion exklusive OR.

4. Implikation, ekvivalens.

Som vi ser har inte bara avslag och konjunktioner lika prioriteringar. Och prioriteringen av disjunktionen och den exklusiva ELLER är lika, liksom prioriteringarna för implikation och likvärdighet.

Implikation och ekvivalensfunktioner

Som vi redan har sagt, utöver de grundläggande logiska operationerna använder matematisk logik och teorin om algoritmer derivat. Den vanligast använda implikationen och ekvivalensen.

Implikation eller logiskt följd ärett uttalande där en åtgärd är ett villkor, och en annan är en följd av att den uppfylls. Med andra ord, denna mening med företeelserna "om ... då". "Du gillar att rida, älska och släde att bära." Det är för att åka skridskor är det nödvändigt att dra åt släden till kullen. Om det inte finns någon önskan att lämna berget, behöver du inte bära slädar. Det är skrivet så här: A → B eller A⇒B.

Ekvivalens förutsätter att den resulterandeÅtgärden uppträder endast när båda operanderna är sanna. Till exempel är natten ersatt av dagen då (och endast då), när solen stiger från horisonten. På matematiska logikens språk skrivs detta uttalande som: A≡B, A≡B, A == B.

Andra lagar i Boolean algebra

Domen algebra utvecklas, och mångaintresserade forskare formulerade nya lagar. De mest kända är postulaten till den skotska matematikern O. de Morgan. Han märkte och definierade sådana egenskaper som nära negation, addition och dubbel negation.

Nära Negation föreslår att det inte finns en enda negation före konsolen: inte (A eller B) = inte A eller INTE B.

När operanden negeras, oavsett dess betydelse, Dessutom:

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

Och slutligen, dubbel negation kompenserar sig själv. dvs Före operand försvinner negationen, eller bara en kvarstår.

Hur man löser test

Matematisk logik innebär förenklingav de givna ekvationerna. Precis som i algebra är det först nödvändigt att göra villkoret så enkelt som möjligt (bli av med komplicerade introduktioner och operationer med dem) och fortsätt sedan för att hitta rätt svar.

Vad kan vi göra för att förenkla saker? Konvertera alla avledda operationer till enkla. Öppna sedan alla parenteser (eller vice versa, gör bort parentes för att förkorta detta element). Nästa steg är att tillämpa egenskaperna hos boolesalgebra i praktiken (absorption, egenskaper av noll och enheter etc.).

I slutändan måste ekvationen bestå avMinsta antal okända, förenade med enkla operationer. Det är lättast att leta efter en lösning om man uppnår ett stort antal nära negationer. Då kommer svaret att dyka upp som om i sig själv.