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.
Übung 11
Wenn man beim Aufstellen der Polynomordnung auf etwas wie
4x + 2 >_A 2x + 1kommt, stimmt ja die Gleichung für alle nicht-negativen x.
Kann man sicher sein, dass x nicht-negativ ist?
Im Skript steht, dass P_f € N[X1, … Xm] (siehe erster Übungsfolieinsatz, Folie 11). Ist das die Antwort?
Fast. Folie 11 ist schonmal gut, aber der Punkt ist die Menge A, die eine Teilmenge der natürlichen Zahlen ist. Die können nicht negativ werden, daraus ergibt sich die Einschränkung für x. Eventuell musst du A sogar weiter beschränken, weil nicht alle natürlichen Zahlen klappen.
Danke Hasenichts.
Habt ihr bei Teilaufgabe 2 auch nur ein kritisches Paar gefunden?
ne, ich hab mehr als 1
Muss man bei der Suche nach kritischen Paaren den rechten Teil eines Terms unifizieren, oder kann man auch den linken unifizieren (und entsprechend den rechten Teil “stehen lassen”)?
@BreakFast : Soweit ich verstanden habe, nimmt man für l1 bzw. l2 nur linke Teile. Rechte Teile zu nehmen wäre Unsinn bei der definition, dass
l_1 ->_0 r_1 bzw.
l_2 ->_0 r_2Habe auch eine Frage: was ist mit “Wenn wir mit der Reduktion bei einem Term beginnen, der eine wohlgeformte Formel repräsentiert, was wird die Normalform des Term reprasentieren?”.
Was ist eine wohlgeformte Formel? Die Wikipedia definition hilft mir nicht wirklich.
hat wer nen kleinen Hinweis zur 11.3? Ich hab nichtmal ansatzweise ne Idee, wo das hingehen soll. Meine erste Idee waren irgendwelche Normalformen der Prädikatenlogik erster Stufe, aber da hab ich nix passendes gefunden…
Sieht ein wenig nach einer Shannon-NormalformZerlegung aus. Kam in GTI vor, um alles mit NANDs darzustellen.
Edit: Alles Murks… noch nicht mal die NAND-Zerlegung haut hin.
“Logische Äquivalenz” hört sich nennenswert an.
Ich verstehe schon bei Aufgabe 11. 1.) nicht wie man (x v y) als Polynom schreiben kann ? Soll man sich da einfach iwas ausdenken ? zb P_v(x,y) = x ?
Ja, im Prinzip muss man sich für jede Funktion in Σ ein streng monotones Polynom ausdenken. Die genaue Definition kannst du auf Folie 11 des ersten Übungsfoliensatzes nachlesen.
Bei Übung 6 hatten wir z.B. diese zwei Zeilen eines TES:
x + S(y) →° S( x + y )Außerdem war als Hinweis gegen, dass P_S(x) := x + 1 sei.
Das Polynom, das auf der linken Seite steht, muss größer sein als das rechte.
P_(x + S(y) ) >A P_( S(X + Y) )Das kann man einfach umschreiben zu
P_+ (x, S(Y) ) >A P_S ( X + Y)Jetzt setzen wir das Polynom x + 1 für P_S ein.
P_+ (x, y + 1) >A P_+ (X, Y) + 1Jetzt müssen wir uns ein Polynom für P_+ überlegen. Sei P_+(x, y) := x + y
Dann können wir weiter einsetzen.
(x + (y + 1) ) >A (x + y) + 1Offensichtlich ist die linke Seite nicht größer als die rechte Seite. Wir müssen wohl ein anderes Polynom für P_+ wählen. Sei P_+ (x, y) := x + 2y
Wieder eingesetzt:
x + 2( y + 1 ) >A (x + 2y) + 1
x + 2y + 2 >A x + 2y + 1Wunderbar, die Ungleichung ist erfüllt.
So macht man jetzt weiter, bis für jede Operation ein Polynom gefunden ist.
Ergebnis:
danke, dann denk ich mir mal ein paar aus 