9450647
Description
Flashcards by David Bratschke, updated more than 1 year ago
|
Created by David Bratschke
almost 7 years ago
|
|
| Question | Answer |
| Wozu dienen die Normalformen in der Logik? | Fast alle Verfahren, die Formeln auf Erfüllbarkeit prüfen, verlangen dass die Formeln eine bestimmte Form haben. Das sind in der Regel die Normalformen. |
| Nenne die drei Normalformen in der Logik | Die Negationsnormalform (NNF) Die Konjunktionsnormalform (KNF) Die Disjunktionsnormalform (DNF) |
| Was haben alle 3 Normalformen gemeinsam? Bzw. welche Junktoren dürfen in allen drei Normalformen nicht vorkommen? | Implikation \( \to\) und Äquivalenz \( \leftrightarrow \) |
| Was wird verlangt, damit eine Formel in Negationsnormalform vorliegt? | Dass die Formel: 1. keine \( \to \) und \( \leftrightarrow \) enthält 2. \( \neg \) nur direkt vor Atomen sind |
| Durch welche Äquivalenzregeln kann eine Formel in eine Negationsnormalform (NNF) gebracht werden? | Durch die Negationsregel und die Regeln von de Morgan. |
| Wie kann die Formel: \( \alpha_1 \wedge \alpha_2 \wedge ... \wedge \alpha_n \) formal verkürzt dargestellt werden? | Als \( \bigwedge\limits_{i=1}^n \alpha_i\) |
| Wie kann die Formel: \( \alpha_1 \vee \alpha_2 \vee ...\vee \alpha_n \) verkürzt dargestellt werden? | Als: \( \bigvee\limits_{i=1}^{n} \alpha_n \) |
| Wie wird der Ausdruck: \( \bigwedge\limits_{i=1}^{n} \alpha_i \) ausgesprochen? | Als Konjunktion über \( \alpha_1 \) bis \(\alpha_n\) |
| Wann nennt man eine Formel "Klausel"? | wenn sie eine Disjunktion über \(alpha_1\) bis \(\alpha_n\) ist, also von der Form: \( \bigvee\limits_{i=1}^{n} \alpha_i \) |
| Was ist eine positive Klausel? | Eine Klausel die nur aus positiven Literalen besteht. |
| Was ist eine negative Klausel? | Eine Klausel, die nur aus negativen Literalen besteht |
| Wann liegt eine Formel in konjunktiver Normalform vor? | Wenn die Formel eine Konjunktion einer oder mehrerer Klauseln ist. |
| Wie kann eine Formel ohne Implikationen und Äquivalenzen in konjunktive Normalform (KNF) gebracht werden? | indem sie zuerst in NNF gebracht wird und danach sukzessive die Distributivgesetze angewendet werden. |
| Was ist ein Monom? | Eine Formel, die sich nur aus der Konjunktion von Literalen zusammensetzt \( \bigwedge\limits_{i=1}^n \alpha_i \) |
| Was ist eine k-Klausel bzw. ein k-Monom? | Eine Disjunktion (Klausel) bzw. Konjunktion (Monom), die genau k Literale enthält |
| Wann ist eine Formel in disjunktiver Normalform (DNF)? | Wenn sie eine Disjunktion von Monomen ist. |
Want to create your own Flashcards for free with GoConqr? Learn more.