Morgan lagar

Morgan-ögonen är regler för inferens som används i propositionell logik, som visar vad som är resultatet av att neka en disjunktion och en kombination av propositioner eller propositionella variabler. Dessa lagar definierades av matematikern Augustus De Morgan.

Morgans lagar är ett mycket användbart verktyg för att visa giltigheten av en matematisk resonemang. Senare generaliserades de inom konceptet uppsättningar av matematiker George Boole.

Denna generalisering gjord av Boole motsvarar helt Morgans ursprungliga lagar, men den är utvecklad speciellt för uppsättningar snarare än för propositioner. Denna generalisering kallas också Morgans lagar.

Granskning av propositionell logik

Innan vi tittar på vad Morgans lagar är specifikt och hur de används, är det lämpligt att komma ihåg några grundläggande begrepp i propositionell logik. (För mer information se artikeln om propositionell logik).

Inom matematisk (eller propositionell) logik är en inferens en slutsats som emitteras från en uppsättning lokaler eller hypoteser. Denna slutsats, tillsammans med ovannämnda lokaler, ger upphov till det som kallas matematisk resonemang.

Denna resonemang måste kunna demonstreras eller nekas; det vill säga att inte alla slutsatser eller slutsatser i en matematisk resonemang är giltiga.

vanföreställning

En falsk inferens som emitteras från vissa antaganden som antas vara sann är känd som en felaktighet. Felaktigheter har egenheten av att vara argument som verkar korrekta, men matematiskt är de inte.

Propositional logic har ansvaret för att utveckla och tillhandahålla metoder genom vilken man utan tvekan kan validera eller motbevisa en matematisk resonemang det vill säga en giltig slutsats från lokaler. Dessa metoder kallas inferensregler, varav Morgans lagar är en del.

satser

De väsentliga delarna i propositionell logik är propositioner. Förslag är uttalanden om vilken man kan säga om de är giltiga eller inte, men att de inte kan vara sanna eller falska samtidigt. Det borde inte finnas någon tvetydighet i denna fråga.

Precis som siffror kan kombineras genom addition, subtraktion, multiplicering och delning, kan propositionerna manövreras med hjälp av den kända kopplings- eller konnektorns logiska: negation (, "no"), disjunction (V, "O"), konjunktion (Ʌ, "och"), villkorlig (→, "om ..., då ...") och biconditional (↔, "yes, and only if").

För att arbeta mer generellt, istället för att överväga specifika propositioner, betraktar vi propositionsvariabler som representerar några förslag, och brukar betecknas med små bokstäver p, q, r, s, etc.

En propositionell formel är en kombination av propositionella variabler genom några av de logiska bindningarna. Med andra ord är det en sammansättning av propositionella variabler. De betecknas vanligen med grekiska bokstäver.

Det sägs att en propositionell formel logiskt innebär en annan när den senare är sant varje gång den första är sant. Detta betecknas av:

När den logiska implikationen mellan två propositionella formler är ömsesidig - det vill säga när den föregående implikationen är giltig även i motsatt riktning - sägs formlerna vara logiskt ekvivalenta, och den betecknas av

Logisk ekvivalens är en slags jämlikhet mellan propositionella formler och låter en ersättas av den andra vid behov.

Morgan lagar

Morgans lagar består av två logiska ekvivalenser mellan två propositionella former, nämligen:

Dessa lagar tillåter att skilja negationen av en disjunction eller conjunction, som negationer av de involverade variablerna.

Den första kan läsas enligt följande: Negationen av en disjunktion är lika med konjunktionen av negationerna. Och den andra läser så här: Negationen av en konjunktion är negationen av negationerna.

Med andra ord, för att neka disjunktionen av två propositionella variabler motsvarar konjunktionen av negativen hos båda variablerna. På samma sätt, för att neka konjunktionen av två propositionella variabler är ekvivalent med disjunktionen av negativen hos båda variablerna.

Som tidigare nämnts bidrar substitutionen av denna logiska likvärdighet till att visa viktiga resultat tillsammans med de andra befintliga reglerna. Med dessa kan du förenkla många propositionella formler, så att de är mer användbara att arbeta med.

Följande är ett exempel på ett matematiskt bevis med hjälp av regler om inferens, bland dessa Morgans lagar. Specifikt visas att formeln:

motsvarar:

Den senare är enklare att förstå och utveckla.

show

Det är värt att nämna att validiteten av Morgans lagar kan demonstreras matematiskt. Ett sätt är att jämföra dina sanningstabeller.

uppsättningar

Samma regler om inferens och begreppen logik som tillämpas på propositioner, kan också utvecklas med tanke på uppsättningar. Detta är vad som kallas boolesalgebra, efter matematiker George Boole.

För att differentiera fallen är det nödvändigt att ändra notationen och överföra till uppsättningar, alla begrepp som redan har sett av propositionell logik.

En uppsättning är en samling objekt. Satserna betecknas med bokstäverna A, B, C, X, ... och elementen i en uppsättning anges med små bokstäver a, b, c, x, etc. När ett element a hör till en uppsättning X, betecknas det av:

När det inte hör till X är notationen:

Sättet att representera uppsättningarna är att placera sina element inuti nycklarna. Till exempel representeras uppsättningen naturliga siffror av:

Satser kan också representeras utan att skriva en explicit lista över deras element. De kan uttryckas i formuläret {:}. De två punkterna läses "så att". En variabel som representerar elementet i uppsättningen placeras till vänster om de två punkterna och egenskapen eller tillståndet som de uppfyller placeras på höger sida. Detta är:

Till exempel kan uppsättningen heltal större än -4 uttryckas som:

Eller motsvarande, och förkortas, som:

På liknande sätt representerar följande uttryck de uppsättningar av jämn och udda tal:

Union, korsning och komplement till uppsättningar

Därefter kommer vi att se analogerna i det logiska bindemedlet vid uppsättningar, vilka ingår i de grundläggande operationerna mellan uppsättningar.

Union och korsning

Facket och skärningspunkten för uppsättningar definieras respektive på följande sätt:

Tänk på följande:

Då måste du:

komplement

Komplementet till en uppsättning bildas av de element som inte hör till den uppsättningen (av samma typ som originalet representerar). Komplementet till en uppsättning A, betecknas av:

Till exempel, inom de naturliga siffrorna, är komplementet till uppsättningen jämnt antal det för udda tal och vice versa.

För att bestämma komplementet på en uppsättning måste det tydligt vara från början allmänt eller huvuduppsättningen av element som beaktas. Till exempel är det inte lika att överväga komplementet till en uppsättning på de naturliga siffrorna som på de rationella.

Följande tabell visar förhållandet eller analogi som existerar mellan operationerna på tidigare definierade uppsättningar och de anslutande i propositionell logik: