Grundlagen der Logik in der Informatik - Cheatsheet

Syntax und Semantik der Aussagenlogik

Definition:

Syntax und Semantik der Aussagenlogik: Syntax beschreibt die formale Struktur von Aussagen, Semantik legt die Bedeutung fest.

Details:

• Syntax: Grundelemente – Aussagenvariablen (z.B. \( p, q, r \)), Junktoren (z.B. \( eg, \land, \lor, \rightarrow, \leftrightarrow \)), Klammern zur Strukturierung.
• Formeln: durch rekursive Definition aus Aussagenvariablen und Junktoren gebildet.
• Semantik: Interpretation Funktion \( I \), die jeder Aussagenvariable einen Wahrheitswert \( \{wahr, falsch\} \) zuordnet.
• Wahrheitstabellen: zur Bestimmung des Wahrheitswerts komplexer Aussagen.
• Wahrheitswert einer Formel unter einer Interpretation I bestimmen.
• Modelle: Interpretation, in der eine Formel wahr wird.
• Erfüllbarkeit: Existenz mindestens einer Interpretation, sodass die Formel wahr.
• Gültigkeit: Formel in allen möglichen Interpretationen wahr.

Wahrheitstabellen und logische Äquivalenz

Definition:

Werkzeuge zur Analyse und zum Vergleich von logischen Aussagen in der Informatik.

Details:

• Wahrheitstabelle: zeigt alle möglichen Wahrheitswerte einer logischen Aussage.
• Reihen: jede mögliche Kombination von Wahrheitswerten für alle beteiligten Variablen.
• Spalten: enthalten die Wahrheitswerte der Teilaussagen und der gesamten logischen Aussage.
• Logische Äquivalenz: zwei Aussagen sind logisch äquivalent, wenn sie in allen Fällen denselben Wahrheitswert haben.
• Notation: Aussagen \(A\) und \(B\) sind äquivalent: \[A \equiv B\]
• Nützlichkeit: hilft bei der Vereinfachung logischer Ausdrücke und Validierung logischer Argumente.

Aussagenlogische Formeln und Normalformen

Definition:

Aussagenlogische Formeln und Normalformen sind zentrale Konzepte der Aussagenlogik, die strukturelle Eigenschaften und Vereinfachungen logischer Ausdrücke betreffen.

Details:

• Aussagenlogische Formel: Logischer Ausdruck aus Variablen, Junktoren (z.B. \(\land\), \(\lor\), \(eg\)) und Klammern
• Normalformen: Standardisierte Formen logischer Formeln, z.B. KNF, DNF
• Konjunktive Normalform (KNF): Formel als Konjunktion von Disjunktionen \(\bigwedge (\bigvee p_i)\)
• Disjunktive Normalform (DNF): Formel als Disjunktion von Konjunktionen \(\bigvee (\bigwedge p_i)\)
• Transformation: Jede Formel ist äquivalent umwandelbar in KNF/DNF

Quantoren in der Prädikatenlogik

Definition:

Quantoren beschreiben die Menge der Elemente, für die eine Aussage gilt.

Details:

• Allquantor \(\forall\): Aussage gilt für alle Elemente.
• Existenzquantor \(\exists\): Aussage gilt für mindestens ein Element.
• Bindet eine Variable im Prädikatenausdruck.
• Beispiel: \[\forall x \, P(x)\] - P gilt für alle x.
• Beispiel: \[\exists y \, Q(y)\] - Q gilt für mindestens ein y.

Freie und gebundene Variablen

Definition:

Unterscheide zwischen Variablen, die innerhalb eines Ausdrucks durch Quantoren gebunden sind, und solchen, die frei bleiben.

Details:

• Freie Variable: Nicht durch Quantor gebunden, z.B. in \( \forall x (P(y) \rightarrow Q(x, z)) \) sind \( y \) und \( z \) frei.
• Gebundene Variable: Durch Quantor gebunden, z.B. in \( \forall x (P(x) \rightarrow Q(x, y)) \) ist \( x \) gebunden.
• Gültigkeitsbereich eines Quantors: Der Bereich im Ausdruck, in dem die gebundene Variable gilt.

Formalisierung von Argumenten und Beweisen

Definition:

Definition/Erklärung von Argumenten und Beweisen auf formale Regeln und Syntax herunterbrechen; Ziel ist es, deren Korrektheit eindeutig nachzuweisen.

Details:

• Mathematische Logik als Grundlage
• Verwendung formaler Systeme wie Prädikatenlogik
• Beweise als Sequenzen von logischen Schritten
• Verifikation durch Beweisregeln und Axiome
• Verwendung von Schlussregeln: Modus Ponens, Kettenschluss, etc.
• Unterscheidung von syntaktischer und semantischer Korrektheit
• Hilfsmittel: Wahrheitstabellen, Formalkalküle
• Satz von Gödel: Unvollständigkeit jedem formalen System innewohnend

Induktive Beweise und mathematische Induktion

Definition:

Induktive Beweise nutzen das Prinzip der vollständigen Induktion, um Aussagen für alle natürlichen Zahlen n zu beweisen. Sie bestehen aus zwei Hauptschritten: dem Induktionsanfang und dem Induktionsschritt.

Details:

• Induktionsanfang: Basisfall prüfen, z.B. für n=0 oder n=1.
• Induktionsschritt: Annahme, dass Aussage für n=k gilt (Induktionsannahme), und Beweis, dass daraus die Gültigkeit für n=k+1 folgt.
• Formel: Sei P(n) eine Aussage. Zu beweisen: P(n) für alle natürlichen Zahlen n.
• Schritt 1: Beweise P(0) oder P(1).
• Schritt 2: Zeige: Aus P(k) folgt P(k+1).
• Daraus folgt: P(n) gilt für alle natürlichen Zahlen n.