PDA

View Full Version : [Frage] 3.bsp der letzten prüfung

enola
20-10-2002, 13:51
kann mir wer sagen wie man da auf die invariante kommt?
das aufspalten hab ich glaub ich richtig, aber ich kenn mich mit dem erstellen der invariante irgendwie nicht aus. ich komme bei der invariante auf 2x=3y + c, stimmt das soweit? und wie komme ich auf das richtige c?
danke für die hilfe!
enola
20-10-2002, 13:59
stimmt das? ich setzte für y=7 und x=y+1 laut anfangs-schleifenbedingung, dann komm ich auf 2x - 3y = c = -5, weil c nicht neg. werden darf verwende ich die form 2x + c = 3y, also ist c = 5
-z0nk-
20-10-2002, 15:57
versteht den HOARE-KALKÜL auch jemand, oder ist das einfach nur ein in_die_formeln_einsetzen ?

also ich versteh ihn nicht :)

mfg, -z0nk-
Stiller
20-10-2002, 15:58
2x+5 = 3y hab ich auch;
und hab damit die korrektheit beweisen können...
enola
20-10-2002, 16:30
Original geschrieben von Stiller
2x+5 = 3y hab ich auch;
und hab damit die korrektheit beweisen können...

könntest den beweis mit erklärung bitte posten, ich weiß nicht, wie man das für teilformel 2 und 3 macht!
danke!!
patricasso
20-10-2002, 18:15
Ich hab auch das gleiche dafür rausbekommen. Nur hab ich
3y-2x=5 dafür verwendet.

Beweis für die Formeln:
(I): y=7 Teilmenge INV [y+1 <- x]
=> Eingesetzt in die Invariante ist das 3*y - 2*(y+1)
3*7 - 2*8 = 5 WAHR!!

(II) (INV und 3x ungleich 4y) Teilmenge INV [y +2 <- y][x+3 <- x]
=> 3*(x+3) ungleich 4*(y+2) ist also umgeformt 3x-4y ungleich -1 für y=7 und x=8 kommt das Ergebnis raus: 0 ungleich -1 WAHR!!

(III) ((INV und 3x = 4y) Teilmenge y=15)
3y-2x=5 und 3x = 4*15 => 3x=60 => x=20
eingesetzt: 3*15-2*20=5 WAHR!!

womit alles bewiesen wäre :thumb:
enola
20-10-2002, 19:26
das geht ja echt voll einfach! bist du dir sicher, dass man das alles so einsetzt, weil im skript und auf den ue-blättern schaut das irgendwie komplizierter aus, aber wenn deines sicher stimmt, dann vielen dank, dann kenn ich mich jetzt aus!:thumb:
Stiller
20-10-2002, 19:35
@patricasso
(II) hab ich auf Tautologie zurückgeführt, siehe Anhang
enola
20-10-2002, 20:44
Original geschrieben von Stiller
@patricasso
(II) hab ich auf Tautologie zurückgeführt, siehe Anhang

das sagt mir irgendwie gar nix, :confused: könntest du das bitte genauer erklären?
und was genau ist eigentlich eine tautologie?
danke!!
patricasso
20-10-2002, 21:44
Original geschrieben von enola
das geht ja echt voll einfach! bist du dir sicher, dass man das alles so einsetzt, ...

Ich bin mir ziemlich sicher, dass man es einfach so einsetzen kann - anders könnt ichs nämlich nur sehr schwer beweisen.

@Stiller
Hast natürlich recht. Das ist auch eine Tautologie, weil durchs einsetzen ja auf beiden Seiten der gleiche Ausdruck steht. Habs übersehen :D

kurz zur Tautologie ein kleines Beispiel:
(A und B) Teilmenge von A
weil der Ausdruck A in der Menge {A und B} vorkommt => Tautologie!
Stiller
20-10-2002, 21:59
weil der Ausdruck A in der Menge {A und B} vorkommt => Tautologie!
die Mengen sind etwas verwirrend, da es sich ja eigentlich um logische Ausdrücke handelt, stimmen tuts aber trotzdem.

Tautologie = Ausdruck, der für beliebige Wahrheitswerte der Variablen immer gültig ist. z.B: wenn bei einer Implikation
((A \and B)) \implies B
auf beiden Seiten der gleiche Term vorkommt.
verständlich? am Besten selber mit einer Wahrheitstabelle ausprobieren :idea:
-z0nk-
20-10-2002, 23:11
genau ...

eine weitere (noch einsichtigere) Tautologie wäre

A v notA

egal, ob A true oder false ist, es kommt (insgesamt) immer true raus!

t v f = t (für A = t)
f v t = t (für A = f)

mfg, -z0nk-
nexxyz
22-10-2002, 10:15
und wie kommt man auf die invariante?