Formelsammlung Mathematik: Logik

Formelsammlung Mathematik

AussagenlogikBearbeiten

Boolesche AlgebraBearbeiten

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

Distributivgesetze:

  1.  
  2.  

Involution:

 

Zweistellige FunktionenBearbeiten

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 DisjunktionBearbeiten

  1.  
  2.  
  3.  

Vorlagen für KV-DiagrammeBearbeiten

   
 

TautologienBearbeiten

Modus ponens:

 

Modus tollens:

 

Modus tollendo ponens:

 

Modus ponendo tollens:

 

Kontraposition:

 

Beweis durch Widerspruch:

 

Zerlegung einer Äquivalenz:

 

Kettenschluss:

 

Ringschluss:

 
 

Ringschluss, allgemein:

 
 

Regeln zum TableaukalkülBearbeiten

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

SchlussregelnBearbeiten

Modus ponens:

 

MetatheoremeBearbeiten

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 AussagenlogikBearbeiten

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 AussagenlogikBearbeiten

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 AussagenlogikBearbeiten

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ädikatenlogikBearbeiten

RechenregelnBearbeiten

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 MengenBearbeiten

Sei  .

  1.  
  2.  

Beschränkte QuantifizierungBearbeiten

  1.  
  2.  
  3.  

Quantifizierung über ProduktmengenBearbeiten

  1.  
  2.  

Analog gilt

  1.  
  2.  

usw.

Alternative DarstellungBearbeiten

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

  1.  
  2.  

SubstitutionBearbeiten

Sei   eine Injektion. Es gilt:

  1.  
  2.  

Ist   eine bijektive Selbstabbildung auf  , so gilt speziell:

  1.  
  2.  

EindeutigkeitBearbeiten

Quantor für eindeutige Existenz: