Flashcards
21.2.3 Prädikatenlogik, Semantik
Cards in this deck (35)
- 1Wie wird in der Prädikatenlogik einzelnen Symbolen eine Bedeutung zugeordnet?Durch Interpretationen, welche den Symbolen eine Bedeutung in Form von konkreten Objekten zuordnet.
- 2Was 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. - 3Wie 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) \) - 4Was 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 - 5Ergä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 - 6Nenne 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 - 7Was 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 - 8Für jeden Term : Term \( f(t_1, . . . , t_n) \) ist: \( I(f(t_1, . . . , t_n)) \) = ...?\( I(f)(I(t_1), . . . , I(t_n)) \).
- 9\( I(P(t_1, . . . , t_n)) = \)...?\( I(P) (I(t_1), ... I(t_n)) \)
- 10\( I(P(t_1, . . . , t_n)) = 1 \) , genau dann wenn...?\( (I(t_1), . . . , I(t_n)) \) ∈ I(P)
- 11\( I(t_1 = t_2) = 1, genau dann wenn ...?\( I(t_1) = I (t_2) \)
- 12\( I (\alpha \wedge \beta) = 1 \) genau dann wenn\( I(\alpha) = 1 \)
und
\( I (\beta) =1 \) - 13\( I (\alpha \vee \beta) = 1 \) genau dann wenn\( I(\alpha) = 1 \)
oder
\( I(\beta) =1 \) - 14\( I(\exists x\alpha) = 1 \) genau dann, wenn .. ?wenn es ein \( x_U \epsilon U \) gibt mit:
\( I[x/x_U](\alpha ) = 1 \) - 15\( 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" - 16Wann ist eine Formel "erfüllbar"?Wenn es zu ihr mindestens eine Interpretation = 1 gibt.
- 17Wann ist eine Formel tautologisch?Wenn jede Interpretation
der Formel = 1 ist. - 18Wann ist eine Formel widerspruchsvoll?Wenn jede ihrer Interpretation = 0 ist
- 19Wozu dient der Begriff der "Entscheidbarkeit"?Sollte eine Formel widerspruchsvoll sein, müsste man sonst im worst case unendlich viele
Interpretationen prüfen - 20Wann ist eine beliebige Menge "entscheidbar"?wenn es einen
Algorithmus gibt, der für jedes x angibt, ob x in M liegt oder nicht. - 21Ist die Menge der prädikatenlogischen Formeln entscheidbar?Nein, einen solchen Algorithmus kann es nicht geben.
- 22\( \neg\alpha \) ist tautologisch genau dann wenn.. ?\( \alpha \) widerspruchsvoll,
also nicht erüllbar ist. - 23Ergänze: Der Begriff der semantischen Folgerung in der Prädikatenlogik ist analog zu dem ...dem Begriff in der Aussagenlogik
- 24Wann gilt \( \alpha |= \beta\) in der Prädikatenlogik?Genauso wie in der Aussagenlogik:
Wenn für jede I ( \(\alpha\) = 1 ,
auch \( I (\beta\) =1 gilt. - 25α ∧ ¬β ist, widerspruchsvoll genau dann wenn ..?\(\alpha |= \beta \)
- 26Ergänze: Die logische Äquivalenz zwischen prädikatenlogischen Formeln ist ... ?Genauso definiert wie in der Aussagenlogik
- 27Wann sind zwei prädikatenlogische Formeln äquivalent?Genauso wie in der Aussagenlogik,
wenn alle ihr Interpretationen gleich sind.
Bzw. wenn:
wenn α |= β und β |= α. - 28Was besagt die Äquivalenzregel "Quantorwechsel"?Bei der Negation einer Formel wechseln die Quantoren:
¬(∃xα) ≈ ∀x(¬α)
und ¬(∀xα) ≈ ∃x(¬α) - 29Was 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\). - 30Wann kann man Quantoren zusammenfassen? (Äquivalenzregel: Quantorenzusammenfassung)Wenn sich zwei gleiche Quantoren auf unterschiedliche Formeln beziehen, welche mit \(\wedge\) oder \(\vee\) verknüpft sind.
- 31Womit ist die Äquivalenzregel: Quantorenzusammenfassung vergleichbar?mit dem Distributivgesetz, also "Ausklammern für Quantoren"
- 32Worauf ist bei der Quantorzusammenfassung zu achten?Der Existenzquantor verträgt sich nur mit der Disjunktion und der Allquantor nur mit der Konjunktion.
- 33Was besagt die Äquivalenzregel der "Quantorelimination"?Wenn x keine freie Variable in \( \alpha \) ist, kann der Quantor entfernt werden.
- 34Was besagt die Äquivalenzregel der "Quantifizierung"?Diese erlaubt, einen Quantor in einer Teilformel, die Teil einer Konjunktion oder Disjunktion ist, „nach außen“ zu ziehen.
- 35Warum 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.
Information
- Description
- Mathematik (Grundlagen KE 7) Flashcards on 21.2.3 Prädikatenlogik, Semantik, created by David Bratschke on 04/07/2017.
- Created by
- David Bratschke
- Views
- 24
- Rating