I dagens värld använder vi allt oftare en mängd olika bilar och prylar. Och inte bara när det är nödvändigt att applicera bokstavligen omänsklig styrka: flytta lasten, lyft den till en höjd, gräv en lång och djup dike, etc. Bilar idag monteras av robotar, mat tillagas av multicookers och elementära aritmetiska beräkningar är utförs av miniräknare. Allt oftare hör vi uttrycket "boolesk algebra". Det kanske är dags att förstå människans roll när det gäller att skapa robotar och maskinernas förmåga att lösa inte bara matematiska, utan även logiska problem.
Logic
Översatt från grekiska är logik ett ordnat tänkande som skapar samband mellan givna förutsättningar och låter dig dra slutsatser utifrån premisser och antaganden. Ganska ofta frågar vi varandra: "Är det logiskt?" Det mottagna svaret bekräftar våra antaganden eller kritiserar tankebanorna. Men processen stannar inte: vi fortsätter att resonera.
Ibland är antalet tillstånd (inledande) så stort, och relationerna mellan dem är så invecklade och komplexa att den mänskliga hjärnan inte kan "smälta" allt på en gång. Det kan ta mer än en månad (vecka, år) att förstå vad som händer. MenDet moderna livet ger oss inte sådana tidsintervaller för att fatta beslut. Och vi tar till hjälp av datorer. Och det är här logikens algebra dyker upp, med sina egna lagar och egenskaper. Genom att ladda ner all initial data låter vi datorn känna igen alla samband, eliminera motsägelser och hitta en tillfredsställande lösning.
Math and Logic
Den berömde Gottfried Wilhelm Leibniz formulerade begreppet "matematisk logik", vars problem endast var förståeliga för en snäv krets av vetenskapsmän. Denna riktning väckte inget särskilt intresse och fram till mitten av 1800-talet var det få som kände till matematisk logik.
Stort intresse för det vetenskapliga samfundet orsakade en tvist där engelsmannen George Boole tillkännagav sin avsikt att skapa en gren av matematiken som absolut inte har någon praktisk tillämpning. Som vi minns från historien utvecklades industriproduktionen aktivt på den tiden, alla typer av hjälpmaskiner och verktygsmaskiner utvecklades, det vill säga alla vetenskapliga upptäckter hade ett praktiskt fokus.
När vi ser framåt, låt oss säga att boolesk algebra är den mest använda delen av matematiken i den moderna världen. Så Bull förlorade sitt argument.
George Buhl
Själva författarens personlighet förtjänar särskild uppmärksamhet. Även med tanke på att människor förr växte upp före oss, är det fortfarande omöjligt att inte notera att J. Buhl vid 16 års ålder undervisade på en byskola och vid 20 års ålder öppnade han sin egen skola i Lincoln. Matematikern kunde fem främmande språk flytande och på fritiden läste han verkNewton och Lagrange. Och allt detta handlar om sonen till en enkel arbetare!
1839 skickade Boole först in sina vetenskapliga artiklar till Cambridge Mathematical Journal. Forskaren är 24 år gammal. Booles arbete så intresserade medlemmar av Royal Society att han 1844 fick en medalj för sitt bidrag till utvecklingen av matematisk analys. Flera fler publicerade verk, som beskrev elementen i matematisk logik, gjorde det möjligt för den unge matematikern att ta tjänsten som professor vid Cork County College. Kom ihåg att Buhl själv inte hade någon utbildning.
Idea
I princip är boolesk algebra väldigt enkel. Det finns påståenden (logiska uttryck) som ur matematikens synvinkel endast kan definieras med två ord: "sant" eller "falskt". Till exempel, på våren blommar träden - sant, på sommaren snöar det - en lögn. Det fina med den här matematiken är att det inte finns något strikt behov av att bara använda siffror. Alla påståenden med en entydig innebörd är mycket lämpliga för bedömningarnas algebra.
Därmed kan logikens algebra användas bokstavligen överallt: vid schemaläggning och skrivning av instruktioner, analys av motstridig information om händelser och bestämning av sekvensen av åtgärder. Det viktigaste är att förstå att det är helt oviktigt hur vi avgör sanningen eller falskheten i påståendet. Dessa "hur" och "varför" måste abstraheras bort. Endast påståendet om fakta spelar roll: sant-falskt.
Naturligtvis, för programmering är funktionerna i logikens algebra viktiga, som skrivs av motsvarandetecken och symboler. Och att lära sig dem innebär att behärska ett nytt främmande språk. Ingenting är omöjligt.
Grundläggande begrepp och definitioner
Utan att gå in på djupet, låt oss ta itu med terminologin. Så den booleska algebra antar:
- statements;
- logiska operationer;
- funktioner och lagar.
Uttalanden är alla bekräftande uttryck som inte kan tolkas tvetydigt. De är skrivna som siffror (5 > 3) eller formulerade i bekanta ord (elefant är det största däggdjuret). Samtidigt har frasen "giraffen har ingen hals" också rätt att existera, bara boolesk algebra kommer att definiera den som "falsk."
Alla påståenden måste vara entydiga, men de kan vara elementära och sammansatta. De senare använder logiska kopplingar. Det vill säga, i bedömningarnas algebra bildas sammansatta satser genom att lägga till elementära satser med hjälp av logiska operationer.
boolesk algebraoperationer
Vi minns redan att operationer i bedömningarnas algebra är logiska. Precis som talalgebra använder aritmetik för att addera, subtrahera eller jämföra tal, tillåter element i matematisk logik dig att göra komplexa påståenden, negera eller beräkna slutresultatet.
Logiska operationer för formalisering och enkelhet skrivs av formler som vi känner till i aritmetik. Egenskaperna för boolesk 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 kolumnerdefiniera elementen i beräkningen och operationen som utförs på dem, och linjerna visar resultatet av beräkningen.
Grundläggande logiska åtgärder
De vanligaste operationerna i boolesk algebra är negation (NOT) och logisk AND och OR. Nästan alla handlingar i bedömningarnas algebra kan beskrivas på detta sätt. Låt oss studera var och en av de tre operationerna mer i detalj.
Negation (inte) gäller endast ett element (operand). Därför kallas negationsoperationen unär. För att skriva begreppet "inte A" använd följande symboler: ¬A, A¯¯¯ eller !A. I tabellform ser det ut så här:
Negationsfunktionen kännetecknas av följande påstående: om A är sant så är B falskt. Till exempel, månen kretsar runt jorden - sant; Jorden kretsar runt månen - falskt.
Logisk multiplikation och addition
Den logiska AND kallas konjunktionsoperationen. Vad betyder det? För det första att den kan appliceras på två operander, dvs och är en binär operation. För det andra, att endast i fallet med sanningen av båda operanderna (både A och B) är själva uttrycket sant. Ordspråket "Tålamod och arbete kommer att mala allt" antyder att bara båda faktorerna hjälper en person att hantera svårigheter.
Symboler som används för att skriva: A∧B, A⋅B eller A&&B.
Konjunktion liknar multiplikation i aritmetik. Ibland säger de det - logisk multiplikation. Om vi multiplicerar elementen i tabellen rad för rad får vi ett resultat som liknar logiskt resonemang.
Disjunktion är en logisk ELLER-operation. Det tar sanningens värdenär minst ett av påståendena är sant (antingen A eller B). Det skrivs så här: A∨B, A+B eller A||B. Sanningstabellerna för dessa operationer är:
Disjunktion är som aritmetisk addition. Den logiska additionsoperationen har bara en begränsning: 1+1=1. Men vi kommer ihåg att i digit alt format är matematisk logik begränsad till 0 och 1 (där 1 är sant, 0 är falskt). Till exempel betyder uttalandet "på ett museum kan du se ett mästerverk eller träffa en intressant samtalspartner" att du kan se konstverk, eller så kan du träffa en intressant person. Samtidigt utesluts inte möjligheten att båda händelserna inträffar samtidigt.
Funktioner och lagar
Så vi vet redan vilka logiska operationer boolesk algebra använder. Funktioner beskriver alla egenskaper hos element i matematisk logik och låter dig förenkla komplexa sammansatta problemförhållanden. Den mest förståeliga och enkla egenskapen tycks vara förkastandet av härledda operationer. Derivat är exklusiva OR, implikation och ekvivalens. Eftersom vi endast har studerat de grundläggande funktionerna kommer vi också att överväga egenskaperna endast för dem.
Associativitet betyder att i uttalanden som "och A, och B och C," spelar ordningen på operanderna ingen roll. Formeln är skriven så här:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Som du kan se är detta inte bara karaktäristiskt för konjunktion, utan också för disjunktion.
Kommutativitet anger att resultatetkonjunktion eller disjunktion beror inte på vilket element som ansågs först:
A∧B=B∧A; A∨B=B∨A.
Distributivitet tillåter utökade parenteser i komplexa logiska uttryck. Reglerna liknar öppnande parenteser i multiplikation och addition i algebra:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Egenskaperna för ett och noll, som kan vara en av operanderna, liknar också algebraisk multiplikation med noll eller ett och addition med ett:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotens säger oss att om resultatet av en operation visar sig vara likartat med avseende på två lika operander, då kan vi "kasta bort" de extra operanderna som komplicerar resonemangets gång. Både konjunktion och disjunktion är idempotenta operationer.
B∧B=B; B∨B=B.
Absorption tillåter oss också att förenkla ekvationer. Absorption anger att när en annan operation med samma element tillämpas på ett uttryck med en operand, blir resultatet operanden från den absorberande operationen.
A∧B∨B=B; (A∨B)∧B=B.
Operationssekvens
Operationssekvensen är av ingen liten betydelse. Egentligen, som för algebra, finns det en prioritet för funktioner som den booleska algebra använder. Formler kan förenklas endast om betydelsen av operationerna observeras. Rangordnas från den mest betydande till den minsta får vi följande sekvens:
1. Förnekelse.
2. Konjunktion.
3. Disjunktion, exklusivELLER.
4. Implikation, ekvivalens.
Som du kan se är det bara negation och konjunktion som inte har samma företräde. Och prioriteringen av disjunktion och XOR är lika, liksom prioriteringarna för implikation och ekvivalens.
Implikation och ekvivalensfunktioner
Som vi redan har sagt, förutom de grundläggande logiska operationerna, använder matematisk logik och teorin om algoritmer derivator. De vanligaste är implikation och ekvivalens.
Implikation, eller logisk konsekvens, är ett uttalande där en handling är ett villkor och den andra är en konsekvens av dess genomförande. Detta är med andra ord en mening med prepositioner "om … då." "Om du gillar att åka, älska att bära slädar." Det vill säga att för skidåkning måste du spänna släden uppför backen. Om det inte finns någon lust att flytta nerför berget, behöver du inte bära släden. Det är skrivet så här: A→B eller A⇒B.
Ekvivalens förutsätter att den resulterande åtgärden endast inträffar när båda operanderna är sanna. Till exempel förvandlas natt till dag när (och bara när) solen går upp över horisonten. På matematisk logiks språk skrivs detta påstående på följande sätt: A≡B, A⇔B, A==B.
Andra lagar för boolesk algebra
Bedömningarnas algebra utvecklas, och många intresserade vetenskapsmän har formulerat nya lagar. Den skotske matematikern O. de Morgans postulat anses vara de mest kända. Han lade märke till och definierade sådana egenskaper som nära negation, komplement och dubbel negation.
Close negation betyder att det inte finns någon negation före parentesen:inte (A eller B)=inte A eller INTE B.
När en operand förnekas, oavsett dess värde, talar man om ett komplement:
B∧¬B=0; B∨¬B=1.
Och slutligen, den dubbla negationen kompenserar sig själv. De där. antingen försvinner negationen före operanden, eller så finns bara en kvar.
Hur man löser tester
Matematisk logik innebär förenkling av givna ekvationer. Precis som i algebra måste du först göra villkoret så enkelt som möjligt (bli av med komplexa inmatningar och operationer med dem), och sedan börja leta efter rätt svar.
Vad kan göras för att förenkla? Konvertera alla härledda operationer till enkla. Öppna sedan alla konsoler (eller tvärtom, ta ut den ur konsolerna för att förkorta detta element). Nästa steg bör vara att tillämpa egenskaperna hos boolesk algebra i praktiken (absorption, egenskaperna noll och ett, etc.).
I slutändan bör ekvationen bestå av det minsta antalet okända kombinerat med enkla operationer. Det enklaste sättet att hitta en lösning är att uppnå ett stort antal nära negativa. Då dyker svaret upp som av sig självt.
