Formale Sprachen und Logik in der Informatik

Syntax, Semantik und Kalkül.

Atomare Formeln sind grundlegende, nicht weiter zerlegbare Aussagen, während zusammengesetzte Formeln aus mehreren atomaren Formeln gebildet werden.

Aussagenlogik und Prädikatenlogik.

<p>Es bedeutet, dass die Aussage nicht der Realität entspricht, da 4 tatsächlich kleiner als 10 ist.</p> Signup and view all the answers

<p>Durch Regeln, die definieren, welche Bedingungen erfüllt sein müssen, damit eine Formel als wahr oder falsch gilt.</p> Signup and view all the answers

<p>Kalküle dienen dazu, neue wahre Formeln systematisch abzuleiten.</p> Signup and view all the answers

<p>In der formalen Spezifikation, Verifikation von Programmen und in der künstlichen Intelligenz.</p> Signup and view all the answers

<p>Die Aussage ist wahr, weil mindestens eine der Verknüpfungen (10 ist größer als 4) wahr ist.</p> Signup and view all the answers

<p>F G ist wahr, wenn genau eine der beiden Aussagen wahr ist.</p> Signup and view all the answers

<p>Die Implikation F G bedeutet, dass wenn F wahr ist, dann muss auch G wahr sein, sie ist falsch, wenn F wahr und G falsch ist.</p> Signup and view all the answers

<p>F $ G wird als (F !G ) ^ (G !F ) dargestellt, andere verwendete Symbole sind i↵, eq oder F ⌘ G.</p> Signup and view all the answers

<p>Diese Aussage bezieht sich auf eine NAND-Funktion, die wahr ist, es sei denn, beide Bedingungen sind wahr.</p> Signup and view all the answers

<p>Eine andere Bezeichnung ist xor, was eine exklusive Wahl beschreibt, wo nur eine der beiden Aussagen wahr sein kann.</p> Signup and view all the answers

<p>Diese Formel zeigt, dass die Aussagen R, S und H zusammen betrachtet werden, um zu überprüfen, ob sie konsistent sind.</p> Signup and view all the answers

<p>Die Formel ist unerfüllbar, weil es keinen Wahrheitswert existiert, der alle Bedingungen gleichzeitig erfüllt.</p> Signup and view all the answers

<p>Die erste Aussage kann als P !(¬H !C) formuliert werden.</p> Signup and view all the answers

<p>Der Schluss P !C besagt, dass wenn der Geiger das Konzert gibt, dann viele kommen werden.</p> Signup and view all the answers

<p>Die Widerspruchsmethode verwendet einen indirekten Beweis, um zu zeigen, dass die Annahme zu einem Widerspruch führt.</p> Signup and view all the answers

<p>Aussagenlogik ist ein Teilgebiet der Logik, das sich mit der Analyse und Struktur von Aussagen und deren Wahrheitswerten beschäftigt.</p> Signup and view all the answers

<p>Eine Tautologie ist eine logische Aussage, die unabhängig von den Wahrheitswerten ihrer Komponenten immer wahr ist.</p> Signup and view all the answers

<p>Aussagenlogik und Prädikatenlogik.</p> Signup and view all the answers

<p>Die Beziehung {A, B} |= C bedeutet, dass aus den Aussagen A und B logisch die Aussage C folgt.</p> Signup and view all the answers

<p>Das Ergebnis ¬F' wird genutzt, um zu zeigen, dass A ^ B ^ ¬C unerfüllbar ist, was die Tautologie von F' beweist.</p> Signup and view all the answers

<p>Formale Grammatiken definieren die syntaktischen Regeln für die Struktur von Ausdrücken in formalen Sprachen.</p> Signup and view all the answers

<p>Semantik bezieht sich auf die Bedeutung und den Wahrheitsgehalt von logischen Ausdrücken.</p> Signup and view all the answers

<p>Automaten sind mathematische Modelle, die die Verarbeitungs- und Entscheidungsprozesse in der formalen Logik simulieren.</p> Signup and view all the answers

<p>Widerspruchsfreiheit bedeutet, dass in einem System keine Aussagen gleichzeitig wahr und falsch sein können.</p> Signup and view all the answers

<p>Die Gültigkeit bezieht sich darauf, dass aus wahren Prämissen stets wahre Schlussfolgerungen folgen müssen.</p> Signup and view all the answers

<p>Das Buch 'Logik für Informatiker' von Martin Kreuzer und Stefan Kühling.</p> Signup and view all the answers

<p>Die Klauselmenge K(F) wird durch die Einheitsresolution verkleinert, indem Einheitsklauseln hinzugefügt oder entfernt werden.</p> Signup and view all the answers

<p>Eine Hornformel besteht nur aus Hornklauseln, die höchstens ein positives Literal enthalten.</p> Signup and view all the answers

<p>Die leere Klausel zeigt an, dass die Formel unerfüllbar ist.</p> Signup and view all the answers

<p>Wenn eine neue Einheitsklausel hinzukommt, wird erneut die Einheitsresolution angewendet, um die Klauselmenge weiter zu verkleinern.</p> Signup and view all the answers

<p>Die Erfüllbarkeit wird bewiesen, wenn die vereinfachte Klauselmenge ERes(K) durch Einheitsresolution erlangt wird und keine leere Klausel erzeugt wird.</p> Signup and view all the answers

<p>Eine Tatsachenklausel ist eine spezielle Hornklausel, die nur ein positives Literal enthält.</p> Signup and view all the answers

<p>Ein Beispiel für eine Regel wäre (a _ ¬b _ ¬c) ⌘ (b ^ c).</p> Signup and view all the answers

<p>Der wesentliche Unterschied ist, dass Hornklauseln höchstens ein positives Literal enthalten, während allgemeine Klauseln mehrere positive Literale enthalten können.</p> Signup and view all the answers