9474826
Description
Flashcards by David Bratschke, updated more than 1 year ago
|
Created by David Bratschke
over 7 years ago
|
|
| Question | Answer |
| Wie wird in der Prädikatenlogik einzelnen Symbolen eine Bedeutung zugeordnet? | Durch Interpretationen, welche den Symbolen eine Bedeutung in Form von konkreten Objekten zuordnet. |
| Was ist ein "Universum", und welches Synonym wird dafür häufig verwendet? | Synonym: Grundbereich Eine Menge von Zahlen oder Elementen, auf die sich die Formeln beziehen. |
| Wie ist die Semantik (Bedeutung) des Gleichheitszeichens "=": \( t_1 = t_2 \) festgelegt? | So, dass jede Interpretation: \( I (t_1 = t_2) \) genau dann wahr ist, wenn die Interpretationen der Terme die gleichen Ergebnisse liefert: \( I(t_1) = I(t_2) \) |
| Was ist eine Signatur \( \Sigma\) ? | einem Tripel (K,F,R) von einer Menge von Konstantensymbolen K, einer Menge von Funktionssymbolen F, einer Menge von Prädikatssymbolen R |
| Ergänze: Wenn \( \alpha \) eine Formel ist, dann besteht die durch \(\alpha\) induzierte Signatur \(\Sigma(\alpha)\) aus ... ? | der Menge der in \(\alpha\) vorkommenden Konstantensymbole, Funktionssymbole, und Prädikatssymbole |
| Nenne die ersten beiden Teile aus der eine zu einer Signatur \(\sigma\) passende Interpretation besteht. | 1. dem Universum U 2. eine Abbildung I, die den verschiedenen Symbolen aus Σ konkrete Objekte zuordnet: - Konstanten zu Konstantensymbolen - Funktionen zu Fkt.symbolen - Relationen zu Prädikatssymbolen |
| Was bedeutet die folgende Schreibweise einer Interpretation: I[x/xU] ? | eine Interpretation, die der Variablen x den Wert x_U zuordnet und die restlichen Zuordnungen unverändert lässt |
| Für jeden Term : Term \( f(t_1, . . . , t_n) \) ist: \( I(f(t_1, . . . , t_n)) \) = ...? | \( I(f)(I(t_1), . . . , I(t_n)) \). |
| \( I(P(t_1, . . . , t_n)) = \)...? | \( I(P) (I(t_1), ... I(t_n)) \) |
| \( I(P(t_1, . . . , t_n)) = 1 \) , genau dann wenn...? | \( (I(t_1), . . . , I(t_n)) \) ∈ I(P) |
| \( I(t_1 = t_2) = 1, genau dann wenn ...? | \( I(t_1) = I (t_2) \) |
| \( I (\alpha \wedge \beta) = 1 \) genau dann wenn | \( I(\alpha) = 1 \) und \( I (\beta) =1 \) |
| \( I (\alpha \vee \beta) = 1 \) genau dann wenn | \( I(\alpha) = 1 \) oder \( I(\beta) =1 \) |
| \( I(\exists x\alpha) = 1 \) genau dann, wenn .. ? | wenn es ein \( x_U \epsilon U \) gibt mit: \( I[x/x_U](\alpha ) = 1 \) |
| \( I(\forall x\alpha) = 1 \) genau dann, wenn .. ? | wenn für jedes \( x_U \epsilon U\) gilt: \( I[x/x_U](\alpha ) = 1 \) "alle Lernkarten sind grün, wenn jede Lernkarte grün ist" |
| Wann ist eine Formel "erfüllbar"? | Wenn es zu ihr mindestens eine Interpretation = 1 gibt. |
| Wann ist eine Formel tautologisch? | Wenn jede Interpretation der Formel = 1 ist. |
| Wann ist eine Formel widerspruchsvoll? | Wenn jede ihrer Interpretation = 0 ist |
| Wozu dient der Begriff der "Entscheidbarkeit"? | Sollte eine Formel widerspruchsvoll sein, müsste man sonst im worst case unendlich viele Interpretationen prüfen |
| Wann ist eine beliebige Menge "entscheidbar"? | wenn es einen Algorithmus gibt, der für jedes x angibt, ob x in M liegt oder nicht. |
| Ist die Menge der prädikatenlogischen Formeln entscheidbar? | Nein, einen solchen Algorithmus kann es nicht geben. |
| \( \neg\alpha \) ist tautologisch genau dann wenn.. ? | \( \alpha \) widerspruchsvoll, also nicht erüllbar ist. |
| Ergänze: Der Begriff der semantischen Folgerung in der Prädikatenlogik ist analog zu dem ... | dem Begriff in der Aussagenlogik |
| Wann gilt \( \alpha |= \beta\) in der Prädikatenlogik? | Genauso wie in der Aussagenlogik: Wenn für jede I ( \(\alpha\) = 1 , auch \( I (\beta\) =1 gilt. |
| α ∧ ¬β ist, widerspruchsvoll genau dann wenn ..? | \(\alpha |= \beta \) |
| Ergänze: Die logische Äquivalenz zwischen prädikatenlogischen Formeln ist ... ? | Genauso definiert wie in der Aussagenlogik |
| Wann sind zwei prädikatenlogische Formeln äquivalent? | Genauso wie in der Aussagenlogik, wenn alle ihr Interpretationen gleich sind. Bzw. wenn: wenn α |= β und β |= α. |
| Was besagt die Äquivalenzregel "Quantorwechsel"? | Bei der Negation einer Formel wechseln die Quantoren: ¬(∃xα) ≈ ∀x(¬α) und ¬(∀xα) ≈ ∃x(¬α) |
| Was besagt die Äquivalenzregel "Quantortausch"? | nebeneinander stehende gleiche Quantoren können vertauscht werden: ∃x∃y\(\alpha\)≈ ∃y∃x\(\alpha\) und ∀x∀y\(\alpha\) ≈ ∀y∀x\(\alpha\). |
| Wann kann man Quantoren zusammenfassen? (Äquivalenzregel: Quantorenzusammenfassung) | Wenn sich zwei gleiche Quantoren auf unterschiedliche Formeln beziehen, welche mit \(\wedge\) oder \(\vee\) verknüpft sind. |
| Womit ist die Äquivalenzregel: Quantorenzusammenfassung vergleichbar? | mit dem Distributivgesetz, also "Ausklammern für Quantoren" |
| Worauf ist bei der Quantorzusammenfassung zu achten? | Der Existenzquantor verträgt sich nur mit der Disjunktion und der Allquantor nur mit der Konjunktion. |
| Was besagt die Äquivalenzregel der "Quantorelimination"? | Wenn x keine freie Variable in \( \alpha \) ist, kann der Quantor entfernt werden. |
| Was besagt die Äquivalenzregel der "Quantifizierung"? | Diese erlaubt, einen Quantor in einer Teilformel, die Teil einer Konjunktion oder Disjunktion ist, „nach außen“ zu ziehen. |
| Warum kommt man in der Prädikatenlogik theoretisch mit nur einem Quantor aus? | Weil man durch die Äquivalenzregel "Quantorwechsel" einen Quantor durch den anderen Quantor ausdrücken kann. |
Want to create your own Flashcards for free with GoConqr? Learn more.