Not logged in. · Lost password · Register

BTL
Member since Oct 2012
310 posts
Subject: Übung 11
Wenn man beim Aufstellen der Polynomordnung auf etwas wie
4x + 2 >_A 2x + 1
kommt, 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?
Hasenichts
Member since Apr 2012
554 posts
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.
BTL
Member since Oct 2012
310 posts
Danke Hasenichts.

Habt ihr bei Teilaufgabe 2 auch nur ein kritisches Paar gefunden?
Hasenichts
Member since Apr 2012
554 posts
ne, ich hab mehr als 1
BreakFast
Avatar
Member since Oct 2012
396 posts
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")?
Nichrome
Member since Mar 2014
37 posts
@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_2

Habe 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.
Hasenichts
Member since Apr 2012
554 posts
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...
phi
Member since Nov 2010
79 posts
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.
This post was edited 3 times, last on 2014-05-05, 04:28 by phi.
zy70ht
Member since May 2013
15 posts
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 ?
BTL
Member since Oct 2012
310 posts
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) + 1

Jetzt 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) + 1
Offensichtlich 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 + 1

Wunderbar, die Ungleichung ist erfüllt.
So macht man jetzt weiter, bis für jede Operation ein Polynom gefunden ist.

Ergebnis:
Quote by Übungsfolien:
Terminierung eines TES R mittels Polynomordnung > A zeigen:
1. Sicherstellen, dass A eine polynomielle Interpretation ist, und
2. zeigen, dass für jede Regel l →° r des TES gilt: l >A r .
This post was edited 3 times, last on 2014-05-08, 21:11 by BTL.
zy70ht
Member since May 2013
15 posts
danke, dann denk ich mir mal ein paar aus ;)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen