Dies ist eine Formelsammlung zum mathematischen Teilgebiet der Logik Inhaltsverzeichnis 1 Aussagenlogik 1 1 Verknupfungen zweier Aussagen 1 2 Logische Grundgesetze 1 3 Schlussregeln 2 Pradikatenlogik 2 1 Quantoren 2 2 Pranexform 3 Minimale Schlussregeln 3 1 Quasiordnung 3 2 Konjunktion 3 3 Disjunktion 3 4 Heyting Implikation und Negation 3 5 Ko Heyting Implikation und Negation 3 6 Beziehung zwischen den Negationen 3 7 QuantorenAussagenlogik BearbeitenLogische Werte wahr true 1 falsch false 0Erweiterte Logik unbestimmt Don t Care XAussagen konnen durch logische Operatoren auch Junktoren genannt verknupft werden Die ublichen Junktoren sind Name Symbol sprachliche Umschreibung Operation DefinitionNegator displaystyle neg nbsp nicht Negation Die Negation eines logischen Werts ist genau dann wahr wenn der Wert falsch ist Konjunktor displaystyle land nbsp und Konjunktion Die Konjunktion von zwei Werten ist genau dann wahr wenn beide Werte wahr sind Disjunktor displaystyle lor nbsp oder Disjunktion Die Disjunktion von zwei Werten ist genau dann wahr wenn mindestens ein Wert wahr ist Um die Symbole des Konjunktors und des Disjunktors leicht auseinanderhalten zu konnen gibt es die Eselsbrucke mit den drei O Oder ist Oben Offen Alternativ merkt man sich And Englisch fur und sowie vel Latein fur oder Verknupfungen zweier Aussagen Bearbeiten Name sprachliche Umschreibung Darstellung Wahrheitstabelle Logik gatterdurch Negator Konjunktor und Disjunktor durch andere Junktoren A 1 A 0B 1 B 0 B 1 B 0Konjunktion A und B A B displaystyle A land B nbsp B A displaystyle neg B implies neg A nbsp 1 0 0 0 ANDExklusion kontrarer Gegensatz nicht zugleich A und B A B A B displaystyle neg A land B iff neg A lor neg B nbsp A B A B B A displaystyle A mid B iff A implies neg B iff B implies neg A nbsp 0 1 1 1 NANDDisjunktion A oder B oder beide A B displaystyle A lor B nbsp A B B A displaystyle neg A implies B iff neg B implies A nbsp 1 1 1 0 ORNihilition Rejektion weder A noch B A B A B displaystyle neg A lor B iff neg A land neg B nbsp 0 0 0 1 NORKontravalenz kontradiktorischer Gegensatz entweder A oder B A B A B A B A B displaystyle A land neg B lor neg A land B iff A lor B land neg A lor neg B nbsp A B A B displaystyle A veebar B iff neg A iff B nbsp 0 1 1 0 XORBikonditional Bisubjunktion materiale Aquivalenz nur wenn A dann B genau dann B wenn A A B A B A B A B displaystyle A land B lor neg A land neg B iff A lor neg B land neg A lor B nbsp A B A B B A displaystyle A iff B iff A implies B land B implies A nbsp 1 0 0 1 XNORKonditional Subjunktion materiale Implikation Implikation wenn A dann B A B displaystyle neg A lor B nbsp A B B A displaystyle A implies B iff neg B implies neg A nbsp 1 0 1 1Replikation wenn B dann A B A displaystyle neg B lor A nbsp B A A B displaystyle B implies A iff neg A implies neg B nbsp 1 1 0 1Inhibition Postsektion A und nicht B A B displaystyle A land neg B nbsp A B displaystyle neg A implies B nbsp 0 1 0 0Prasektion B und nicht A B A displaystyle B land neg A nbsp B A displaystyle neg B implies A nbsp 0 0 1 0Logische Grundgesetze Bearbeiten Gesetz der doppelten Negation x x displaystyle x neg neg x nbsp Kommutativgesetze x y y x displaystyle x land y y land x nbsp x y y x displaystyle x lor y y lor x nbsp Assoziativgesetze x y z x y z displaystyle x land y land z x land y land z nbsp x y z x y z displaystyle x lor y lor z x lor y lor z nbsp Distributivgesetze x y z x y x z displaystyle x land y lor z x land y lor x land z nbsp x y z x y x z displaystyle x lor y land z x lor y land x lor z nbsp Idempotenz x x x displaystyle x land x x nbsp x x x displaystyle x lor x x nbsp Gesetze der Negation Tautologie Kontradiktion x x 1 displaystyle x lor neg x 1 nbsp x x 0 displaystyle x land neg x 0 nbsp Absorptionsgesetze x x y x displaystyle x land x lor y x nbsp x x y x displaystyle x lor x land y x nbsp Neutralitat x 0 x displaystyle x lor 0 x nbsp x 1 x displaystyle x land 1 x nbsp De Morgansche Gesetze x y x y displaystyle neg x land y neg x lor neg y nbsp x y x y displaystyle neg x lor y neg x land neg y nbsp Schlussregeln Bearbeiten Modus ponens a b a b displaystyle a rightarrow b land a rightarrow b nbsp Modus tollens a b b a displaystyle a rightarrow b land neg b rightarrow neg a nbsp Hypothetischer Syllogismus a b b c a c displaystyle a rightarrow b land b rightarrow c rightarrow a rightarrow c nbsp Disjunktiver Syllogismus a b a b displaystyle a lor b land neg a rightarrow b nbsp Pradikatenlogik BearbeitenQuantoren Bearbeiten p ist Platzhalter fur eine pradikatenlogische Aussageform x p x p displaystyle forall x p neg exists x neg p nbsp x p x p displaystyle exists x p neg forall x neg p nbsp x p x p displaystyle neg forall x p exists x neg p nbsp x p x p displaystyle neg exists x p forall x neg p nbsp Pranexform Bearbeiten ϕ displaystyle phi nbsp und ps displaystyle psi nbsp sind im Folgenden Platzhalter fur pradikatenlogische Aussageformen Die Umformungen in Zeilen 1 2 4 und 5 der Tabelle gelten nur wenn x innerhalb von ps displaystyle psi nbsp nicht frei vorkommt d h wenn durch das Verschieben des Quantors keine Variablenbindung entsteht bzw aufgelost wird die zuvor nicht da war bzw da war Die letzte Umformung gilt nur wenn x innerhalb von ϕ displaystyle phi nbsp nicht frei vorkommt d h wenn durch das Verschieben des Quantors keine Variablenbindung entsteht bzw aufgelost wird die zuvor nicht da war bzw da war Unproblematisch ist das wenn die Variablen in den Aussageformen ϕ displaystyle phi nbsp und ps displaystyle psi nbsp jeweils unterschiedlich benannt sind x ϕ ps displaystyle forall x phi land psi nbsp x ϕ ps displaystyle forall x phi land psi nbsp x ϕ ps displaystyle forall x phi lor psi nbsp x ϕ ps displaystyle forall x phi lor psi nbsp x ϕ ps displaystyle exists x phi land psi nbsp x ϕ ps displaystyle exists x phi land psi nbsp x ϕ ps displaystyle exists x phi lor psi nbsp x ϕ ps displaystyle exists x phi lor psi nbsp x ϕ displaystyle lnot exists x phi nbsp x ϕ displaystyle forall x lnot phi nbsp x ϕ displaystyle lnot forall x phi nbsp x ϕ displaystyle exists x lnot phi nbsp x ϕ ps displaystyle forall x phi rightarrow psi nbsp x ϕ ps displaystyle exists x phi rightarrow psi nbsp x ϕ ps displaystyle exists x phi rightarrow psi nbsp x ϕ ps displaystyle forall x phi rightarrow psi nbsp ϕ x ps displaystyle phi rightarrow exists x psi nbsp x ϕ ps displaystyle exists x phi rightarrow psi nbsp ϕ x ps displaystyle phi rightarrow forall x psi nbsp x ϕ ps displaystyle forall x phi rightarrow psi nbsp Minimale Schlussregeln BearbeitenQuasiordnung Bearbeiten displaystyle vdash nbsp ist im Folgenden eine Quasiordnung zwischen Aussagen A A A B B C A C displaystyle begin array c hline A vdash A end array qquad begin array c A vdash B qquad B vdash C hline A vdash C end array nbsp Konjunktion Bearbeiten displaystyle top nbsp und displaystyle land nbsp werden durch folgende Regeln definiert A A B A C A B C displaystyle begin array c hline A vdash top end array qquad begin array c A vdash B qquad A vdash C hline A vdash B land C end array uparrow downarrow nbsp Disjunktion Bearbeiten displaystyle bot nbsp und displaystyle lor nbsp werden durch folgende Regeln definiert A A C B C A B C displaystyle begin array c hline bot vdash A end array qquad begin array c A vdash C qquad B vdash C hline A lor B vdash C end array uparrow downarrow nbsp Heyting Implikation und Negation Bearbeiten displaystyle to nbsp wird durch die RegelA B C A B C displaystyle begin array lcr A land B amp vdash amp C hline A amp vdash amp B to C end array uparrow downarrow nbsp definiert und displaystyle lnot nbsp per A A displaystyle lnot A A to bot nbsp Es gelten A A displaystyle A land lnot A vdash bot nbsp displaystyle lnot top vdash bot nbsp und displaystyle top vdash lnot bot nbsp Ko Heyting Implikation und Negation Bearbeiten Dual zu displaystyle to nbsp und displaystyle lnot nbsp sind displaystyle setminus nbsp und displaystyle sim nbsp A B C A B C displaystyle begin array lcr A setminus B amp vdash amp C hline A amp vdash amp B lor C end array uparrow downarrow nbsp A A displaystyle sim A top setminus A nbsp Es gelten A A displaystyle top vdash A lor sim A nbsp displaystyle sim top vdash bot nbsp und displaystyle top vdash sim bot nbsp Beziehung zwischen den Negationen Bearbeiten Es gilt immer A A displaystyle lnot A vdash sim A nbsp Gilt auch A A displaystyle sim A vdash lnot A nbsp erhalt man klassische Logik Quantoren Bearbeiten Es sei f X Y displaystyle f colon X to Y nbsp eine Abbildung Eine beliebige Aussage A displaystyle A nbsp uber Elemente von Y displaystyle Y nbsp kann per f displaystyle f nbsp in eine Aussage uber X displaystyle X nbsp Elemente transformiert werden Notation A f displaystyle A circ f nbsp f displaystyle circ f nbsp ist ein Funktor Seine rechts und linksadjungierten sind respektive All und Existenzquantor D h A f X B A Y f B C X A f f C Y A displaystyle begin array lcr A circ f amp vdash X amp B hline A amp vdash Y amp forall f B end array uparrow downarrow qquad begin array rcl C amp vdash X amp A circ f hline exists f C amp vdash Y amp A end array uparrow downarrow nbsp Abgerufen von https de wikipedia org w index php title Formelsammlung Logik amp oldid 233041513
