View Full Version : [Frage] 8.1
so hab wider einmal nicht einschlafen können...
und was macht man da am besten? thinf1 natürlich!
hier meine lösungen für 8.1a und 8.1b.
übrigens: bei 8.1 sieht man mit 2 scharfen blicken, dass die formel unerfüllbar ist (wenn man sich ein bischen mit dem zeug auskennt).
hab das einmal dazunotiert, aber da ja der beweis mittels sequentialkalkül erbracht werden muss, is das eh für die katz!
also:
8.1a:
http://www.itcorner.net/informatik_forum/thinf1/8.1a.gif
8.1b:
http://www.itcorner.net/informatik_forum/thinf1/8.1b.gif
p.s.: kann mir einmal jemand erklären wie man größere bilder (bezieht sich auf abmessungen, nicht auf speicher) ins forum direkt stellen kann? und wer is eigentlich auf die idee gekommen, dass die abmessungen im querformat sind? und einmal im ernst: wenn ich die bilder mit 800x600 einscannen würde, könnt keiner meine sauklaue lesen!
noch viel spaß!
koe
jamironico
19-05-2004, 14:23
Also die ableitungen schauen genau so aus wie meine, aber ich glaube dass die Modelle in b falsch sind. bei einem modell muss ja ein wahr oder t raus kommen, und das machen sie nicht wenn du false fuer A rein gibst. Meine modelle schauen wie folgt aus....
Modell 1: I(A) = t, I(B) = t/f, I(C) = t/f
Modell 2: I(A) = t, I(B) = t, I(C) = t/f
ich hoffe das stimmt so.
seid ihr euch da sicher?
sollte man nicht am anfang das sequentialzeichen links von der formel hinsetzen?
und damit mit der oder-rechts formel beginnen?
ja mann soll ja die unerfüllbarkeit zeigen und net die gültigkeit!
nautiLus
21-05-2004, 19:31
Hallo,
ich dachte, wenn bei dem Sequentialkalkül nur Axiome herauskommen, dann ist die Formel gültig? Wieso ist das bei a) nicht so?
Hab ich was überlesen?
ciao Nauti
naja es kommt ganz auf den anfang an!
wenn das 'gedrehte T' vor der formel steht und es kommen nur axiome raus, dann is die formel gültig!
wenn man mit dem T am ende beginnt und es ergeben sich nur axiome, dann is die formel unerfüllbar!
nautiLus
21-05-2004, 19:47
Ahhsoo ist das ... jetzt versteh ich :) Danke!
Weiß wer, wo das im alten Skriptum zum Nachlesen ist?
Ciao,
nauti
ChristofNeutron
22-05-2004, 12:00
oder im neuen???
Ich hab das nirgends gefunden :(
Veronika
22-05-2004, 14:14
oder im neuen???
Ich hab das nirgends gefunden :(
Auf Seite 76 3.34:
Als Randfälle erhalten wir: F |- 0 gilt genau dann, wenn F unerfüllbar ist, und 0 |- G gilt genau dann, wenn G gültig ist. Das ist es glaub ich.
alter Post wegen blödheit gelöscht...
neue Frage :-) also beim 1.b, Wenn du da auf "kein Axiom stößt, mußt du da nicht beim rechten Teil weiter machen ob nicht vielleicht doch noch wo ein Axiom rauskommt? weil da geht es ja darum ob es nicht doch erfüllbar ist, oder?
nop!
es geht ja darum die unerfüllbarkeit zu beweisen/widerlegen!
und um sie zu widerlegen genügt ein modell, das man bekommt, wenn man einen endausdruck erhält, der kein axiom ist!
Sorry. My mistake!
Also ich habe abgeleitet mit dem Sequentialzeichen links, d.h. wenn der Ableitungsversuch scheitert, d.h. am Ende eines Astes steht kein Axiom, ...
Also ist der Sequent unerfüllbar, was man mit einigem Nachdenken auch leicht feststellen kann, denn aufgrund der Verknüpfungen kommt bei jeder Interpretation f raus.
naja es kommt ganz auf den anfang an!
wenn das 'gedrehte T' vor der formel steht und es kommen nur axiome raus, dann is die formel gültig!
wenn man mit dem T am ende beginnt und es ergeben sich nur axiome, dann is die formel unerfüllbar!
ja woher weiß ich, wann das verkehrte T links oder rechts von der Formel steht?
Also ich habe abgeleitet mit dem Sequentialzeichen links, d.h. wenn der Ableitungsversuch scheitert, d.h. am Ende eines Astes steht kein Axiom, ist der Sequent (des is de Ausgangs"formel") überhaupt nicht ableitbar (Skript 81 oben).
Damit kannst du aber nur die Gültigkeit beweisen und nicht die Unerfüllbarkeit. Du hast also nur gezeigt, dass die Formel nicht für alle Belegungen gilt, für den Unerfüllbarkeitsbeweis musst du aber zeigen, dass es keine Belegungen geben kann und das macht man mit Sequentialpfeil RECHTS, was soviel heißt wie "Formel ist ungültig" und diese Aussage beweist du dann, indem du sie auf Axiome zurückführst.
Oder anders gesagt. Aus der Widerlegung von "Formel gültig" folgt NICHT "Formel ungültig"
Mit "nicht ableitbar" im Skriptum ist denk ich gemeint, dass man die Formel nicht beweisen kann, weil sie nicht für alle Belegungen gilt und nicht das sie unerfüllbar ist.
ja woher weiß ich, wann das verkehrte T links oder rechts von der Formel steht?
links, wenn du Gültigkeit(1) beweisen willst oder ein Gegenmodell (Widerlegbarkeit)(2) finden willst.
rechts, wenn du Unerfüllbarkeit(1) zeigen willst oder ein Modell (Erfüllbarkeit)(2) suchst.
Für (1) brauchst du jeweils nur Axiome, für (2) reicht ein Anti-Axiom.
Hab mich schon gefragt warum ich bei 8.1.b nicht weiter komme, aber da habt ihr sicher recht!
Aber find ich dass irgendwo auch im Skript "verständlich" beschrieben :confused:
Sorry für meinen falschen Schluss und Danke für den Hinweis :thumb:
ein_stein2000
23-05-2004, 13:22
das a) hab ich gelöst, das war jo leicht ... beim b) hänge ich jedoch .. habs abgeleitet und komme auch auf 2 anti-axiome ... aber was muss i jetzt machen? - was sind das für "modelle"? wofür brauch i das? wo steht das im skriptum :confused: ?!?!?
ich hab bei b) zum Schluss 4 Anti Axiome, glaub da passt was ned :shinner:
Freilandei
23-05-2004, 15:24
wie kommt man bei b) nun von den "Antiaxiomen" auf die Modelle??
nautiLus
23-05-2004, 15:37
Naja , da das links äußerste Antiaxiom |-A,A ist, ist das Gegenmodell
I(A) = f. Man setzt alles was vorkommt false also nur A. Der Rest kann true oder false sein: I(B) = t/f, I(C) = t/f
Genauso beim 2. von links: |-A,B => I(A) = f, I(B) = f, I(C) = t/f.
Alle anderen sind Axiome... stimmt das?
Und zwar: C|-A, B|-A,B und B|-A,A
mfG Nauti
beim b) hänge ich jedoch .. habs abgeleitet und komme auch auf 2 anti-axiome Ich komme auch auf zwei Anti-Axiome |-A,A und |-A,B ........mehr brauchen wir nicht :)
=> Formel ist nicht unerfüllbar
wie kommt man bei b) nun von den "Antiaxiomen" auf die Modelle??
Die Variablen links von |- werden auf t gesetzt, jene rechts davon auf f
zB. A,B|- C
I(A)=t
I(B)=t
I(C)=f
ich hoffe, alles stimt
Alle anderen sind Axiome... stimmt das?
Und zwar: C|-A, B|-A,B und B,!A|-AAxiome müssen links und recht von |- mindestens eine gemeinsame Variable haben
C|-A ist meiner Meinung nach kein Axiom
nautiLus
23-05-2004, 15:57
Axiome müssen links und recht von |- mindestens eine gemeinsame Variable haben
C|-A ist meiner Meinung nach kein Axiom
Hm, ok.. Danke.
Wenn ich endlich mal die Definition eines Axioms (altes Sktiptum) finden würde, hätte ich das gewusst :-)
Also insgesamt 3 Antiaxiome, und 2 Axiome.
Das Gegenmodell zum 3. Antiaxiom wäre dann I(A) = f, I(C) = f und I(B) = t/f
Stimmt das jetzt endlich? :engel:
edit: hmm laut kambo #21 doch:
C|-A => I(C) = t und I(A) = f, I(B) = t/f
Sollte passen?
ein_stein2000
23-05-2004, 16:02
Ich komme auch auf zwei Anti-Axiome |-A,A und |-A,B ........mehr brauchen wir nicht :)
=> Formel ist nicht unerfüllbar
Die Variablen links von |- werden auf t gesetzt, jene rechts davon auf f
zB. A,B|- C
I(A)=t
I(B)=t
I(C)=f
ich hoffe, alles stimt
DANKE für dein erklärung, aber WO steht das? kannst mir seite im skriptum sagen, i hab das wirklich net gefunden ....
also wir haben dann ja folgende 2 nicht-axiome:
|- A,A und |- A,B
das würde also ergeben:
leere menge |- I(A)=f ... und ... leere menge |- I(A)=f, I(B)=f
und die anderen variablen kann man dann auf dont-care setzen, also so wäre die komplettlösung dann:
leere menge |- I(A)=f, I(B)=X, I(C)=X
und
leere menge |- I(A)=f, I(B)=f, I(C)=X
ist das nun so richtig?
nautiLus
23-05-2004, 16:04
Schaut vernünftig aus!
Nauti
... glaub jetzt hammas :)
DANKE für dein erklärung, aber WO steht das? kannst mir seite im skriptum sagen, i hab das wirklich net gefunden.... Ich habe aber altes Skriptum (Juni 2002). Seite 76, gleich vor dem Thema "Eigenschaften des Sequentialkalküls", das direkt vor dem Abschnitt "Ein Hilbert-Typ Kalkül für die Aussagenlogik" steht.....
also wir haben dann ja folgende 2 nicht-axiome:
|- A,A und |- A,B
:
:
und die anderen variablen kann man dann auf dont-care setzen, also so wäre die komplettlösung dann:
leere menge |- I(A)=f, I(B)=X, I(C)=X
und
leere menge |- I(A)=f, I(B)=f, I(C)=X
ist das nun so richtig?
Ja. Meine Lösung sieht gleich aus:
Modell 1: I(A)=f , I(B)=t/f, I(C)=f/t
Modell 2: I(A)=f , I(B)=f , I(C)=f/t
Die Formel "enthält" noch zwei andere Anti-Axiome (C|-A und B|-A,A) und ein Axiom B|-A,B
was genau ist nun ein Axiom?
was genau ist nun ein Axiom?ok, nochmal...
Axiome müssen links und recht von |- mindestens eine gemeinsame Variable haben
dh:
C|-A kein Axiom
C,B |- A,D,E kein Axiom
|-A,B kein Axiom
A|- A,B Axiom
B,C|-B,C,D Axiom
klar?
nautiLus
23-05-2004, 16:41
Eine Eigenschaft is mal, dass eine Variable links und eine Variable rechts vom |- gleich sein muss.
edit: war wer schneller :D
Die restlichen Gegenmodelle wären dann noch folgende:
C|-A =>
I(C) = t
I(A) = f
I(B) = t/f
und
B|-A,A =>
I(B) = t
I(A) = f
I(C) = t/f
Ciao nauti
Reicht es denn wenn wir nur
Modell 1: I(A)=f , I(B)=t/f, I(C)=f/t
Modell 2: I(A)=f , I(B)=f , I(C)=f/t
haben, oder "muessen" wir auch noch die restlichen 2 dazugeben ? :rolleyes:
C|-A => I(C) = t , I(A) = f , I(B) = t/f
und
B|-A,A => I(B) = t , I(A) = f , I(C) = t/f
Reicht es denn wenn wir nur
Modell 1: I(A)=f , I(B)=t/f, I(C)=f/t
Modell 2: I(A)=f , I(B)=f , I(C)=f/t Ja!http://hades.gothic.at/iforum/images/smilies/thumb.gif
ist jetzt 8.1a unerfüllbar, weil ich Axiome erhalte? Brauch ich da keine Modelle?
ist jetzt 8.1a unerfüllbar, weil ich Axiome erhalte? Genau!
Brauch ich da keine Modelle? Modelle muss man angeben falls die Formel "nicht unerfüllbar" ist
bei b) hab ich 4 Anti Axiome, nämlich |-A,A ; |-B,A; C|-A ; B|-A,A und ein Axiom B|-A,B.
und diese Formel ist jetzt nicht unerfüllbar, weil um die Unerfüllbarkeit zu erzielen müsste ich nur Axiome haben, hab ich aber nicht.
Und da ich mehrere Anti Axiome habe, brauche ich nun Modelle, oder?
Und diese Modelle finde ich, indem ich mir die Axiome und Anti Axiome hernehme und sag:
Alles was rechts vom |- ist wird zu FALSE, und links davon zu TRUE.
Hab ich das soweit richtig verstanden?
bei b) hab ich 4 Anti Axiome, nämlich |-A,A ; |-B,A; C|-A ; B|-A,A und ein Axiom B|-A,B. habe auch so
und diese Formel ist jetzt nicht unerfüllbar, weil um die Unerfüllbarkeit zu erzielen müsste ich nur Axiome haben, hab ich aber nicht. Genau!
Und da ich mehrere Anti Axiome habe, brauche ich nun Modelle, oder? Ja!
Und diese Modelle finde ich, indem ich mir die Axiome und Anti Axiome hernehme und sag: Um modelle zu finden, nimmt man nur Anti-Axiome!
Alles was rechts vom |- ist wird zu FALSE, und links davon zu TRUE. Ja!
sunflower
23-05-2004, 23:07
ok, ich hab den ausdruck in der angabe ohne implikationszeichen gegeben, was entscheidet darüber ob das implikationszeichen am anfang vor oder nach den ausdruck gesetzt wird?
danke würd unheimlich weiterhelfen, weil der rest ist dann schon klar
ein_stein2000
23-05-2004, 23:12
@sunflower
links, wenn du Gültigkeit(1) beweisen willst oder ein Gegenmodell (Widerlegbarkeit)(2) finden willst.
rechts, wenn du Unerfüllbarkeit(1) zeigen willst oder ein Modell (Erfüllbarkeit)(2) suchst.
Für (1) brauchst du jeweils nur Axiome, für (2) reicht ein Anti-Axiom.siehe thread-anfang ...
sunflower
23-05-2004, 23:35
@sunflower
siehe thread-anfang ...
ok danke, hab ich scheinbar übersehen
Variable
25-05-2004, 22:43
habe auch so
Genau!
Ja!
Um modelle zu finden, nimmt man nur Anti-Axiome!
Ja! warum nimmt man nur Anti-Axiome ?
und warum wird alles rechts zu false und links zu true ?
gitbs da ne enstprechende Stelle im skript ?
edit: ja gibts, schon gefunden s142 auf dern Folien
Superwinki
25-05-2004, 23:40
Wenn ich die Erfüllbarkeit beweisen oder wiederlegen möchte reicht es bereits EIN Antiaxiom zu finden.
Da man recht schnell im a) Teil auf D |- B,A kommt wurde bereits eines gefunden. Ein Gegenbeispiel genügt.
Bei der Lösung wurde zumindest in der vorherigen Posts immer auf D vergessen. Ich würd zumindest hinschreiben, dass es beliebig gewählt werden kann, solltet ihr über eine andere Ableitung zu einem Antiaxiom gekommen sein!
D=t, A=f, B=f, C=beliebig
der b) Teil ist eigentlich recht simpel:
|- negation(((......)
erster Schritt: negation rechts
(((.......) |-
zweiter Schritt: impliziert links
Im rechten Teilbaum erhält man so A |-
Dies ist ein Antiaxiom --> Gegenmodell: A=t, B,C=beliebig
Oder seht ihr das anders?
IceBreaker
26-05-2004, 00:06
okay.. jetzt bin ich wieder out of the track.. stimmt die lösung vom koe oder nicht? reicht es wenn man im a bsp, die formel bis auf die axiome ableitet?
und wieso im b bsp nach der 3ten zeile alles bis auf A,A & B wegfällt?
Danke
mfg
ICE
Superwinki
26-05-2004, 01:24
@icebreaker
Die Lösung sollte stimmen. Das was dort anders gemacht wird, ist das Ableitungszeichen auf die rechte Seite der Formel zu setzen (also von einer Unlösbarkeit auszugehen), dies führt nur zu Axiomen in den Blättern, daher ist die Annahme der Unerfüllbarkeit bestätigt.
Wenn du das Ableitungszeichen auf die linke Seite setzt, bedeutet dies, dass du von einer Lösbarkeit ausgehst, ein Antiaxiom in einem Blatt reicht aus, um dies zu wiederlegen.
In der Angabe will man vermutlich diese Tatsache herausstreichen, es ist aber schlampig formuliert, was es einem ermöglicht, dies über Annahme der Erfüllbarkeit sehr viel schneller (s. obiges Post) zu lösen. Die Unerfüllbarkeit zu beweisen kannst du auf beide Arten (also entweder von der Unerfüllbarkeit ausgehen und nur Axiome in den Blättern haben oder von der Erfüllbarkeit ausgehen und mindestens ein Antiaxiom finden). Was du annehmen sollst steht nämlich nicht auf dem Zettel, also das WIE was das beweisen angeht, steht dir bei genauem Lesen offen (auch wenn die UE-Leitung vermutlich dies nicht beabsichtigt hat...).
Hoffe ich hab dich jetzt nicht noch mehr verwirrt...
IceBreaker
26-05-2004, 02:46
@superwinki...
nein.. ganz und gar nicht... du hast es gut formuliert und jetzt kenne ich mich um 60% mehr aus als vorher... bin dir sehr dankbar dafür...
mfg
ICE
PS: für die restlichen 40% darf ich mit beim koe und den anderen postern bedanken ;)
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.