21.2.3 Prädikatenlogik, Semantik

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.

Next up

21.2.3 Prädikatenlogik, Semantik

Description

Resource summary

Similar

	Created by David Bratschke over 7 years ago