Zum Inhalt springen

Formelsammlung Mathematik: Logik

Aus Wikibooks
Formelsammlung Mathematik

Aussagenlogik

[Bearbeiten]

Boolesche Algebra

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

Distributivgesetze:

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]

Vorlagen für KV-Diagramme

[Bearbeiten]

KV-Diagramm-Vorlage mit vier Feldern KV-Diagramm-Vorlage mit acht Feldern
KV-Diagramm-Vorlage mit 16 Feldern

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):

Verallgemeinerte Distributivgesetze:

Verallgemeinerte Idempotenzgesetze:

Äquivalenzen:

Implikationen:

Endliche Mengen

[Bearbeiten]

Sei .

Beschränkte Quantifizierung

[Bearbeiten]

Quantifizierung über Produktmengen

[Bearbeiten]

Analog gilt

usw.

Alternative Darstellung

[Bearbeiten]

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

Substitution

[Bearbeiten]

Sei eine Injektion. Es gilt:

Ist eine bijektive Selbstabbildung auf , so gilt speziell:

Eindeutigkeit

[Bearbeiten]

Quantor für eindeutige Existenz: