Formelsammlung Mathematik: Logik

Formelsammlung Mathematik

Aussagenlogik

Bearbeiten

Boolesche Algebra

Bearbeiten
UND ODER
    Kommutativgesetze
    Assoziativgesetze
    Idempotenzgesetze
    Neutralitätsgesetze
    Extremalgesetze
    Komplementärgesetze
    De Morgansche Gesetze
    Absorptionsgesetze

Distributivgesetze:

  1.  
  2.  

Involution:

 

Zweistellige Funktionen

Bearbeiten
A B Wert
0 0 a
0 1 b
1 0 c
1 1 d
Nr. dcba Fkt. Name
0 0000   Kontradiktion
1 0001  
2 0010  
3 0011  
4 0100  
5 0101  
6 0110   Kontravalenz
7 0111  
8 1000   Konjunktion
9 1001   Äquivalenz
10 1010  
11 1011   Implikation
12 1100  
13 1101  
14 1110   Disjunktion
15 1111   Tautologie

Darstellung mit Negation, Konjunktion und Disjunktion

Bearbeiten
  1.  
  2.  
  3.  

Vorlagen für KV-Diagramme

Bearbeiten

   
 

Tautologien

Bearbeiten

Modus ponens:

 

Modus tollens:

 

Modus tollendo ponens:

 

Modus ponendo tollens:

 

Kontraposition:

 

Beweis durch Widerspruch:

 

Zerlegung einer Äquivalenz:

 

Kettenschluss:

 

Ringschluss:

 
 

Ringschluss, allgemein:

 
 

Regeln zum Tableaukalkül

Bearbeiten
φψ
φ
ψ
¬(φψ)
¬φ ¬ψ
φψ
φ ψ
¬(φψ)
¬φ
¬ψ
φψ
¬φ ψ
¬(φψ)
φ
¬ψ
φψ
φ
ψ
¬φ
¬ψ
¬(φψ)
φ
¬ψ
ψ
¬φ

Schlussregeln

Bearbeiten

Modus ponens:

 

Metatheoreme

Bearbeiten

Sei   eine endliche Menge von Formeln.

Korrektheit der Aussagenlogik.

Es gilt:

 


Vollständigkeit der Aussagenlogik.

Es gilt:

 


Deduktionstheorem (syntaktisch).

Es gilt:

 

Infolge gilt auch:

 


Deduktionstheorem (semantisch).

Es gilt:

 

Infolge gilt auch:

 


Einsetzungsregel.

Sei v eine logische Variable. Ist φ eine tautologische Formel, dann ergibt sich wieder eine tautologische Formel, wenn man jedes Vorkommen von v in φ durch eine Formel ψ ersetzt. Formal:

 

Das gilt auch für die simultane Substitution:

 


Beispiel. Man überzeugt sich z. B. mittels einer Wahrheitstabelle von

 

Unter Anwendung der Einsetzungsregel lassen sich die zwei Variablen simultan gegen Formeln austauschen:

 

Zieht man nun die Vollständigkeit und das Deduktionstheorem heran, ergibt sich der Modus ponens:

 


Syntax der Aussagenlogik

Bearbeiten

Definition. Formale Sprache der Aussagenlogik.

Sei   die Menge der logischen Variablen.

Die Menge der wohlgeformten Formeln ist durch die folgende formale Grammatik definiert:

  1. Bei 0 und 1 handelt es sich um Formeln.
  2. Jede Variable aus V ist eine Formel.
  3. Sind φ und ψ Formeln, dann sind es auch  .

Die Menge der wohlgeformten Formeln ist die formale Sprache der Aussagenlogik.

Bemerkung:

  1. Für die Praxis wird   definiert.
  2. Außerdem können Klammernpaare wie bei Punktrechnung-vor-Strichrechnung weggelassen werden, wobei die Bindungsstärke in absteigender Reihenfolge   ist.
  3. Anstelle von   wird auch   geschrieben.


Formales System der Aussagenlogik

Bearbeiten

Definition. Formales System der Aussagenlogik.

Einzige Schlussregel. Modus ponens:

(MP)  

Axiome.

(A1)  ,
(A2)  ,
(A3)  .

Hierbei ist:

  •   definiert als  ,
  •   definiert als  ,
  •   definiert als  .


Es folgen historische Axiomatisierungen.

Axiome (Rosser, 1953).

(R1)  ,
(R2)  ,
(R3)  .


Axiome (Principia Mathematica, 1910).

(P1)  ,
(P2)  ,
(P3)  ,
(P4)  ,
(P5)  .

Das Axiom (P4) ist redundant.


Semantik der Aussagenlogik

Bearbeiten

Definition. Interpretation.

Eine Interpretation   ist eine Abbildung, die jeder logischen Variablen einen Wahrheitswert zuordnet.

Der Definitionsbereich der Interpretation wird wie folgt auf die Menge der Formeln erweitert:

 ,
 ,
 ,
 ,
 ,
 ,
 .

Die rechte Seite der Zeile wird hierbei jeweils nach ihrer Wahrheitstabelle ausgewertet.


Definition. Modell.

Eine Interpretation   heißt Modell von  , wenn   gilt. Kurz:

 

Sei   eine Menge von Formeln. Eine Interpretation   heißt Modell von M, wenn   ein Modell jeder Formel aus M ist. Kurz:

 


Definition. Modellrelation.

Eine Formelmenge M modelliert eine Formel ψ, wenn jedes Modell von M auch ein Modell von ψ ist. Kurz:

 


Definition. Tautologie.

Eine Formel wird tautologisch (allgemeingültig) genannt, wenn jede Interpretation für sie auch ein Modell ist. Kurz:

 

Eine Formel ist genau dann tautologisch, wenn sie durch die leere Menge modelliert wird:

 


Definition. Erfüllbare Formel.

Eine Formel wird erfüllbar genannt, wenn sie ein Modell besitzt. Kurz:

 


Definition. Unerfüllbare Formel.

Eine Formel wird unerfüllbar genannt, wenn sie kein Modell besitzt. Kurz:

 


Definition. Erfüllbarkeitsäquivalenz.

Zwei Formeln φ und ψ heißen erfüllbarkeitsäquivalent, wenn gilt:

 

Das Modell der ersten Formel braucht dabei nicht mit dem Modell der zweiten Formel übereinzustimmen.

Prädikatenlogik

Bearbeiten

Rechenregeln

Bearbeiten

Verneinung (De Morgansche Gesetze):

  1.  
  2.  

Verallgemeinerte Distributivgesetze:

  1.  
  2.  

Verallgemeinerte Idempotenzgesetze:

  1.  
  2.  

Äquivalenzen:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Implikationen:

  1.  
  2.  
  3.  
  4.  
  5.  

Endliche Mengen

Bearbeiten

Sei  .

  1.  
  2.  

Beschränkte Quantifizierung

Bearbeiten
  1.  
  2.  
  3.  

Quantifizierung über Produktmengen

Bearbeiten
  1.  
  2.  

Analog gilt

  1.  
  2.  

usw.

Alternative Darstellung

Bearbeiten

Sei   und  . Mit   ist die Bildmenge von   bezüglich   gemeint.

  1.  
  2.  

Substitution

Bearbeiten

Sei   eine Injektion. Es gilt:

  1.  
  2.  

Ist   eine bijektive Selbstabbildung auf  , so gilt speziell:

  1.  
  2.  

Eindeutigkeit

Bearbeiten

Quantor für eindeutige Existenz: