Modelle fuer Formelmengen

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Modelle fuer Formelmengen
Hi zusammen,

kennt jemand ein Verfahren, wie man Modelle fuer Formelmengen schnell
finden kann?
Wie habt ihr die Aufgabe von der Klasur Herbst 2004 I-5 c) geloest?
Was fuer eine Rolle spielen da die Konstanten a und b? Muss man die bei der Erstellung eines Modells auch beruecksichtigen?

Danke


Zu einem Modell braucht man erstma eine Struktur. Diese besteht aus
einer Trägermenge dem so genannten Universum zu dem auch die Konstanten gehören müssen. Dann braucht man eine Menge von Funktionen die auf dem Universum definiert sind und eine Menge von Prädikaten.
Eine Struktur ist ein Modell für eine prädikatenlogische Formel wenn die Formel für diese Struktur wahr ist. Bsb.

Formel F = ∀x P(x,f(y))

Struktur die ein Modell für F darstellt

Universum U = N
Menge der Funktionen {f(x) = x}
Menge der Prädikate {P(x,y) := x ≤ y}

aber die Struktur

U = N
f(x) = x
P(x,y) := x < y

ist kein Modell für F denn P(x,y) gilt nicht für alle x Bsp. 1 < 0 ist falsch


2 Kommentare:

  1. Was heißt

???

  1. Im letzten Bsp sollte es 1<1 ist falsch heißen, um Konsistenz mit F zu wahren.

Beisbiel.

Das fraenkische Wort fuer Beispiel.


es sollte Bsp. heissen habe mich vertippt.


hätte aber ne anderes dilema. für nen vergleichsbasierten sortieralgorithmus mit listenlänge 2n. d.h. die anzahl der blätter im binärbaum ist (2n)!. frage ist wie verhält sich die anzahl der blätter für
n-> ∞? man soll für n! Strilings formel verwenden.


Die Aufgabe macht so keinen Sinn. Die Anzahl der Blätter geht nämlich für n ->∞ auch ohne Stirling gegen ∞.


Klausuraufgabe H04 III-1

Wie verhält sich die anzahl der blätter asymptotisch für n->∞ in abhängigkeit von der listenlänge n. wobei listenlänge ist m + n und m = n also ist die listenlänge 2n.


Sie verhält sich 2n über n.
das muss man umformen mit der Stirlingformel.

2n über n = (2n)! / (n! * (2n - n)!) =
= ((2n/e)^2n * √4πn) / ((n/e)^n * √2πn * (n/e)^n * √2πn) = … = 4^n / √πn

Gruss Chris


wie kommt man drauf. ich meine von den 2n auf 2n über n?


Da kommt man so drauf. Die listen n und m sind ja schon sortiert. Die Ergebnisliste is dann n+m lang. Und jetzt kannst du dir die Ergebnisliste als ein regal mit n+m fächern vorstellen. auf die du n elemente verteilen musst. Dafür gibt´s ( n+m über n )-Möglichkeiten. Is n=m, kannst dann sagen (2n über n )- Möglichkeiten. Der Rest wurde ja schon gezeigt.