View Full Version : [Frage] 9.1
a) erfüllbar und widerlegbar
b) gültig in S
c) gültig in L
Mr. Bringer
28-05-2004, 12:57
kannst du vielleicht an hand des 9.1 a) erklären wie des funtkioniert....
war nicht in der Vorlesung und übers skriptum kommich nicht ganz drauf was da gemeint ist
thx
Hier meine Rechenschritte zum 9.1 a)
Mr. Bringer
28-05-2004, 14:32
stimmt es dass es egal ist welche seite ich in diesem fall zuerst bearbeite
MPL(I,...)impliziertMPL(I,...)
du hast zuerst mir der linken seite begonnen
???
Mr. Bringer
28-05-2004, 14:43
habs nachgerechnet keine fehler entdeckt
9.1 a)
für x=1 --> 1 impliziert 1
für x=0 --> 0 impliziert 0
9.2 b)
y=egal --> immer 1
soweit so gut
:thumb:
a) erfüllbar und widerlegbar
b) gültig in S
c) gültig in L Warum ist c) gültig?
Meiner Meinung nach wird die rechte Formel eq?(first(x),build(false,nil)) immer f sein => t/f AND f = f => Formel F ist unerfüllbar
Erdös-Index 97
29-05-2004, 17:56
bin auch für unerfüllbar, der erste ausdruck ist nur wahr wenn x = () , und das macht den zweiten falsch.
eine frage zu dem thema: wie beweist man eigentlich allgemeine gültigkeit bzw was wäre ein beispiel dafür?
warum braucht man beim 1.a die rechte hälfte(recht neben dem für alle quantor) nicht weiter zerlegen wie auf der linekn??
hm...also 9.1 a) ist mir klar aber kann mir bitte wer erklären wie man b) macht? weil bei mir kommt da unerfüllbar raus...also irgendwo mach ich da wohl einen gewaltigen fehler...
lg
bei a) kommt bei euch allen erfüllbar und widerlegbar raus.
ein beispiel für erfüllbar ist mir klar zB I(x)=1. da hätten wir dann t impliziert t womit es erfüllbar ist.
aber kann mir wer ein beispiel für widerlegbarkeit nennen?
alleine nach dem impliziert ein f stehen zu haben recht IMHO nicht, das impliziert-prädikat ist doch nur dann widerlegbar wenn wir eine belegung finden die davor t stehen hat und dahinter f? oder seh ich da was falsch?
meines erachtens müsste die formel doch für jede belegung erfüllbar sein. also gültig und erfüllbar in N.
FlatAlex
02-06-2004, 14:47
hmmmm also die rechte Seite der Implikation ist imho immer false, weil da steht der Allquantor, und ((x=2) or (0 < x)) fuer alle x ist nicht gegeben, da brauchen wir nur ein Gegenbeispiel, x=0, und die rechte Seite ist widerlegt; dadurch dass es fuer alle x gelten muss, insbesondere fuer x=0, ist die rechte Seite sogar unerfuellbar, weil sie unabhaengig von unserem speziellen I(x) ist. Jetzt haengts nur mehr von der linken Seite ab, fuer x!=1 ist der linke Teil false und die Implikation und damit die formel TRUE, fuer x=1 ist die linke Seite true und die Formel wird FALSE
HHIILLFFFEEE....kann mir bitte irgendwer sagen wie man b) und c) löst :confused: ????
ich komm da immer auf ein anderes ergebnis...bzw. auf gar keines...
ich hoffe, das hilft dir etwas
vielen, vielen dank :) ...jetzt versteh ichs ich hab das anfangs falsch gemacht!
MarvinTheRobot
02-06-2004, 19:09
ich hoffe, das hilft dir etwasund das reicht? weil genauso hab ichs auch aber dann kam auf einmal dieses komische Mpl auf..... bei 9.5. muss ma ja auch mit dem mist arbeiten.... wozu?
ähm wegen a)
wtf is < is das das selbe wie "nicht"?
Ich habe da noch eine frage zu 9.1 b)
Ich hoffe, dass ich mich mit der fragen nicht blamiere aber warum ist (istleer?(push0(y)) immer false?
lg
major
warum ist (istleer?(push0(y)) immer falseistleer?(push0(y))
istleer? ist TRUE, falls (....) leer ist !
push0 fügt eine 0 ein, dh (....) enthält zumindest eine 0 (bzw.noch etwas) => (....) ist nie leer => Formel ist immer false!
Also beim 9.1a) muss man offenbar beachten, dass man zwei verschiedene Environments hat, I und I', oder? I(x) und I'(x) dürfen sich ja in der Variablenbelegung (im Wert der Variablen) unterscheiden, also muss man doch für das Modell und das Gegenbeispiel beide Environments angeben?
Ich mein das so:
Modell: I(x)=0, I'(x)=0, da entsteht ein f impliziert f => Formel ist t
Gegenbeispiel: I(x)=1, I'(x)=0, da entsteht t impliziert f => Formel ist f
Wobei ich mir jetzt nicht ganz sicher bin, ist ob das überhaupt so geht, in einer Formel zwei Environments "anzuwenden", bzw dadurch verschiedene Variablenwerte zu haben. Aber anders stimmt das Ganze einfach nicht glaub ich.
Siehe eben Definition 4.2 und MPL6 auf Seite 100, offenbar gilt nicht für alle I' dass I'~I ist, oder? Wie fließt das in die ganze Sache ein? Wie spezifizier ich das formal? Bin etwas auf der Leitung bei dem Beispiel...
Tja und bei 9.1c) frage ich mich, warum der Ausdruck
eq?(first(x), rest(x))
(Unterstreichungen dazudenken) nur bei der leeren Liste () zu t evaluiert? Könnte nicht zb I(x)=(i1,i2) sein, mit i1=i2? Das ergäbe doch ebenfalls t? Oder funktioniert das nicht bei Listen? Vielleicht weil Listenelemente nicht gleich sein dürfen, also paarweise verschieden sein müssen oder so?
Aber falls man das darf, könnte man dann, mit einer Belegung I(x)=(i1,i2) und i1=i2=false die Formel zumindest erfüllbar machen?
Der Teil links vom AND würde zu t evaluieren, der rechte Teil ebenfalls: first(x) ergibt false, build(false,nil) ergibt ebenfalls false, und eq?(false,false) wäre dann t, nichtwahr?
Wahrscheinlich eitle Hirnwixerei, kann mir nicht vorstellen, dass das noch keinem aufgefallen wäre, hätte ich da Recht :) Trotzdem wüsste ich gern wo ich hier falsch liege, falls ich falsch liege.
hallo!
Die Formel
(Ex) [eq?(first(x), rest(x)) AND eq?(first(x), build( false, ( ) ))]
ist TRUE für x= ((false)) da
linke seite:
first( ((false)) ) = (false)
rest( ((false)) )) = (false)
=> eq? ((false) , (false) ) = TRUE
rechte Seite
first( ((false)) ) = (false)
build( false, ( ) ) = (false)
=> eq? ((false) , (false) ) = TRUE
=> formel ist gültig (wegen Ex)
maitscha
03-06-2004, 18:18
Und wenn man für x = ((true)) einsetzt? Dann ist sie doch widerlegbar, oder?
ahhh...
liegt dass an MPL7.. wenn es für ein I' true ist dass es dann für alle I true ist?
Also, da die "Existenzquantorbedingung" (Ex) für die ganze Formel gilt, heißt das, die Formel ist gültig, wenn man (mindestens) EIN I(x) findet, für das die Formel zu t evaluiert. So hats uns heute der Tutor erklärt, und das ergibt auch Sinn.
Wenn du eine Belegung I(x) findest, die die Formel zu f evaluieren lässt, so ist das zwar schön für dich, trifft aber keine Aussage oder so in Bezug auf die Formel, weil ja der Existenzquantor davor steht, quasi eine Bedingung vorgibt (zumindest hab ich das so verstanden und interpretiere das so)
Wenn du es schaffst, die Formel für ALLE Belegungen I(x) zu f evaluieren zu lassen, dann ist die Formel unerfüllbar. Aber sonst reicht eine Belegung aus, in der die Formel zu t wird, und du hast schon gewonnen.
Die Formel
(Ex) [eq?(first(x), rest(x)) Ù eq?(first(x), build( false, ( ) ))] ist TRUE für x= ((false)) da ...[blah]
nö, sie ist imho true für( (false), (false) ) und zwar:
linke seite: first liefert dann (false) und rest ebenfalls
rechte seite: das first liefert wieder (false), das build erzeugt (false)
clemensp
04-06-2004, 22:11
frage:
warum liefert bei euch first (x) false?
x ist ja entweder true oder false
also ein atom oda ?
und laut skript S.56 liefert first(l) ( ) wenn l ein Atom ist hm
oda versteh i da was a bissi falsch ^^
bei a) ...
meines erachtens müsste die formel doch für jede belegung erfüllbar sein. also gültig und erfüllbar in N.volle Zustimmung! Ich finde für alle 3 gültig und erfüllbar (beim c weil der Existenzquantor davor steht und es dadurch reicht, dass eines true ist, was da wäre (false, false))
Mein einziges Problem ist jetzt, ist eines davon vielleicht sogar eine Tautologie? Hab den Begriff in diesem Kontext nicht ganz verstanden, wenn ichs net in diesem Thread anders gelesen hätt hätt ich alle Tautologien genannt, kann mir wer vielleicht erklären, was eine Tautologie in diesem Fall sein soll? Aus dem Skriptum werd ich in diesem Punkt auch nicht ganz schlau.
lG,
Murmel
nochwas zu b)
laut tutor haben wir hier eine tautologie. warum?
ganz einfach, weil wir die einzelnen teile der formeln ersetzen können, zB durch A und B.
tun wir das - ich hab > für "impliziert" genommen - sieht das ganze so aus:
A > ( B > A )
jaaaa und das eben is eine tautologie weil es in jedem datentyp mit jeder beliebigen zuordnung von prädikaten, funktionen und konstanten zu den entsprechenden symbolen.
:engel:
Also ich komme auf folgendes:
(a) widerlegbar (weil false nur für I(x) = 1 und I'(x) = 0, während für true mehrere Möglichkeiten zum Einsetzen bestehen, für "erfüllbar" sollte es jedoch ebenfalls nur eine einzige geben)
(b) Tautologie (wegen A > (B > A)) >...impliziert
(c) gültig (wegen MPL7)
Meiner Meinung nach sollte a) gültig sein.
Begründung:
1) betrachte Ausdruck links von der Implikation:
((0<x) and (x=1)) ... nur true für I(x)=1, sonst false
2) betrachte Ausdruck rechts von der Implikation:
(für jedes x aus N gilt: (x=2) or (0<x)) ... true für I(x)!=0 bzw false für I(x)=0
3) daher erhält man für F mit:
a) I(x)=0: false impliziert false
b) I(x)=1: true impliziert true
c) I(x)>1: false impliziert true
a), b), c) entsprechen dem geforderten Verhalten der Implikation (nur false, wenn true impliziert false). Daher ist F gültig!
Wer ist anderer Meinung?
nö, sie ist imho true für( (false), (false) ) und zwar:
linke seite: first liefert dann (false) und rest ebenfalls
rechte seite: das first liefert wieder (false), das build erzeugt (false)
edit: ich glaub, es müsste nur ( (false) false) sein so wie im post von templar
rest( (false) ) ergibt ja meines erachtens nur ()
Zusammenfassend (Übung war am 3.6.):
a) ist erfüllbar und widerlegbar (es gibt Environments sowohl für F=t und F=f, wenn ich das nicht falsch verstanden hab)
b) gültig in S und auch allgemein gültig (Tautologie)
c) gültig wegen MPL7 (der Existenzquantor)
Bei a) ist noch wichtig zu beachten, dass die Variable x auf der linken Seite der Implikation und die Variable x auf der rechten Seite der Implikation NICHT die gleichen sind! Dadurch, dass der Allquantor vor dem Block auf der rechten Seite steht ist das quasi eine "Überladung" der Variablen bzw vergleichbar (in einem 'echten' Programm) mit einer lokalen Variable (x), als Parameter für eine Funktion, die den gleichen Namen hat wie eine global definierte Variable x. Haben also von der Belegung her nichts miteinander zu tun!
Man könnte (und sollte vielleicht) die Variable auf der rechten Seite umbenennen um sich leichter zu tun, dann wird das Ergebnis auch klarer.
hallo!
Die Formel
(Ex) [eq?(first(x), rest(x)) AND eq?(first(x), build( false, ( ) ))]
ist TRUE für x= ((false)) da
linke seite:
first( ((false)) ) = (false)
rest( ((false)) )) = (false)
=> eq? ((false) , (false) ) = TRUE
Wieso ist rest( ((false)) ) = (false)?
Müsste es nicht gleich () sein, so stehts nämlich imho im Skriptum. Die Liste enthält ja nur ein Element, oder, und deshalb geht das so nicht, außer ich hab irgendwo einen Denkfehler.
Ich hab folgende Speicherbelegung gefunden:
I'(x)=( ( false ) false )
Sollte eigentlich stimmen, da first und rest jeweils (false) liefern, oder?
Und noch was: Steht eigentlich irgendwo, dass nil wirklich das Gleiche wie () ist?
Wieso ist rest( ((false)) ) = (false)?
Müsste es nicht gleich () sein, so stehts nämlich imho im Skriptum. Die Liste enthält ja nur ein Element, oder, und deshalb geht das so nicht, außer ich hab irgendwo einen Denkfehler.
Ich hab folgende Speicherbelegung gefunden:
I'(x)=( ( false ) false )
Sollte eigentlich stimmen, da first und rest jeweils (false) liefern, oder?
ja, würde ich auch sagen
Und noch was: Steht eigentlich irgendwo, dass nil wirklich das Gleiche wie () ist?
ja, Seite 56: "Einer Konvention folgend verwenden wir nil an Stelle von () als zugehöriges Symbol"
ein_stein2000
05-06-2004, 19:20
kann mir wer bitte erklären, wie man auf wiederlegbar bei a) kommt? i hab mir oben die 2 erklärungen durchgelesn aber i verstehs afoch nit ...
Ich versuchs mal: Man sollte damit anfangen, die Variable x auf der rechten Seite der Implikation umzubenennen, da vor dem rechten Block der Allquantor steht. Die Belegung der Variable im rechten Block hat daher nichts mit der Belegung der Variablen im linken Block zu tun, darf also umbenannt werden. Das hat der Tutor gesagt, und auch gemeint, dass das im Skriptum überhaupt nicht rüberkommt, nur in den Semantikfunktionen impliziert gesagt wird. Oder so.
Nach ein paar Schritten des Regelanwendens sieht die Formel dann hoffentlich so aus (Unterstreichungen dazudenken, wo nötig):
((MT(I,0)<MT(I,x)) && (MT(I,x)=MT(I,1))) impliziert (Ay)((MT(I,y)=MT(I,2)) || (MT(I,0) < MT(i,y)))
Und wenn man da schaut, dann erkennt man denke ich, dass du es für den Block auf der rechten Seite der Implikation nicht schaffst, für alle Environments die Formel t werden zu lassen.
Das ist das, was MPL6 aussagt, zusammen mit der Definition 4.2. MPL6 sagt: Für MPL(I, (Av) F) gilt: wenn du es schaffst, die Formel MPL(I',F) für alle möglichen Environments I', die sich nur durch den Wert der Variablen v unterscheiden, wahr werden zu lassen, dann ist die Formel F=t. Das geht aber nicht, denn für I'(y)=0 evaluiert der rechte Block zu f.
Der linke Block ist easy. Er wird nur t für eine Belegung I(x)=1, sonst f.
Du hast also im einen Fall dein Gegenbeispiel:
(t impliziert f)=f, für I(x)=1 und I(y)=0 (oder I'(y), bin nicht sicher wie man das anschreiben muss)
und im anderen Fall dein Modell:
(f impliziert f)=t, für zB I(x)=0 und I(y)=0.
Und damit ergibt sich erfüllbar und widerlegbar. Hoffe ich hab mich nicht vertan in der Erklärung, bitte nicht schlagen ihr da draußen, die ihr besser bescheid wisst :)
kann mir jemand sagen, was bei c) nun endgültig rauskommt?
stimmt das von kambo jetzt?
Bei b.) und c.), kann man da eher intuitiv argumentieren wie im pdf von KAMBO oder muss man da auch immer das ganze Ersetzungs-Zeugs dazuschreiben, wenn ja hätt ich eine Frage:
bei 9.1b)
da hat man ja irgendwo in der Rechnung mal
Mpl(I,istleer?(push0(y))) uns muss ja dann MPL1 darauf anwenden.
Beginnt man in diesem Fall beim istleer?(..) oder mit dem push0(..) oder
macht man das irgendwie gleichzeitig?
Oder lieg ich da komplett falsch?
kann mir jemand sagen, was bei c) nun endgültig rauskommt? Formel ist gültig! Das ist 100% sicher
stimmt das von kambo jetzt? Das stimmt leider nicht! Ich glaub, die Lösung von Templar ist korrekt dh.
I(x) = ( (false) false )
Variable
06-06-2004, 17:06
hallo !
ich hab folgendes Gegenbeispiel bzw Modell
für a.)
x= 1 (linke Seite)
x = 2 (rechte Seite)
das wiederum eingesetzt ergibt t impliziert t = t ....ist also ein Modell
dann
x= 1 (linke Seite)
x!=2 (rechte Seite) also zumbeispiel 3 für x
ergibt hier : t impliziert f = f also ein Gegenbeispiel
nun 2.Fragen die ich mir stelle:
1.) Stimmen mein Aussagen ? hats nochwer so ....?
2.) ich hab auch , nach lesen des threads , angenommen das x links und x rechts nicht gleich ist ..... sonst würd nicht erfüllbar, bzw wiederlegbar rauskommen ....aber.....jetzt kommts......WARUM ist das hier so ?
weiß das jemand .....ich vermute mal es hängt vom Allquantor ab ....aber sicher weiß ichs nicht .... help pls http://hades.gothic.at/iforum/images/smilies/biggrin.gif
edit : links und rechts beziehn sich auf links von der Implikation bzw rechts von der Implikation ....;)
Die Lösung von Templar stimmt SICHER! (--> hatte letzte Woche schon Übung)
lg, qn
reicht es bei c) einfach die lösung anzugeben? Gibt es denn keine einzelnen Rechenschritte?
ein_stein2000
06-06-2004, 22:26
Ich versuchs mal: Man sollte damit anfangen, die Variable x auf der rechten Seite der Implikation umzubenennen, da vor dem rechten Block der Allquantor steht. Die Belegung der Variable im rechten Block hat daher nichts mit der Belegung der Variablen im linken Block zu tun, darf also umbenannt werden. Das hat der Tutor gesagt, und auch gemeint, dass das im Skriptum überhaupt nicht rüberkommt, nur in den Semantikfunktionen impliziert gesagt wird. Oder so.
Nach ein paar Schritten des Regelanwendens sieht die Formel dann hoffentlich so aus (Unterstreichungen dazudenken, wo nötig):
((MT(I,0)<MT(I,x)) && (MT(I,x)=MT(I,1))) impliziert (Ay)((MT(I,y)=MT(I,2)) || (MT(I,0) < MT(i,y)))
Und wenn man da schaut, dann erkennt man denke ich, dass du es für den Block auf der rechten Seite der Implikation nicht schaffst, für alle Environments die Formel t werden zu lassen.
Das ist das, was MPL6 aussagt, zusammen mit der Definition 4.2. MPL6 sagt: Für MPL(I, (Av) F) gilt: wenn du es schaffst, die Formel MPL(I',F) für alle möglichen Environments I', die sich nur durch den Wert der Variablen v unterscheiden, wahr werden zu lassen, dann ist die Formel F=t. Das geht aber nicht, denn für I'(y)=0 evaluiert der rechte Block zu f.
Der linke Block ist easy. Er wird nur t für eine Belegung I(x)=1, sonst f.
Du hast also im einen Fall dein Gegenbeispiel:
(t impliziert f)=f, für I(x)=1 und I(y)=0 (oder I'(y), bin nicht sicher wie man das anschreiben muss)
und im anderen Fall dein Modell:
(f impliziert f)=t, für zB I(x)=0 und I(y)=0.
Und damit ergibt sich erfüllbar und widerlegbar. Hoffe ich hab mich nicht vertan in der Erklärung, bitte nicht schlagen ihr da draußen, die ihr besser bescheid wisst :)
dank i glaub i habs kapiert (so einigermaßen)
ad a)
ich kapier das nicht, wenn ihr sagt, ihr widerlegt das mit I'(x) = 0 und daraus folgt "false". in der angabe steht doch im prinzip das so:
"...impliziert für alle x, dass x=2, oder x>0 ist" dann kann ich doch gar nicht das widerlegen mit I'(x) = 0, weil es ja über null sein muss, nicht? :confused: :(
Frage an die, die 9.Übung schon abgegeben haben.
Bei 9.1a)b)c)
muss man da vollständig nach den semantischen Regeln auflösen, oder reicht
eine gute Erklärung wie die von kambo oder daff???
Frag mich das auch manchmal, warum bei einigen Beispielen streng nach den Auflösungskriterien vorgegangen werden muss, bei anderen aber nicht. Bei b) und c) hats auf jeden Fall gereicht, das ganze rein überlegungsmäßig aufzulösen, bei a) wollte er die Rechenschritte. Keine Ahnung warum.
@owaye: Glaub nicht, dass das so stimmt wie du sagst (sofern ich dich richtig verstanden hab). Werte doch einfach die Formel G=(Ay)(MT(I,y)=MT(I,2)) || (MT(I,0) < MT(i,y)) aus (und es ist eigentlich egal wie man die Variablen nennt), du siehst, dass du ein I'(y) finden kannst, für das G falsch wird, und sobald es mindestens eine solche Belegung I'(y) gibt, evaluiert die Formel zu false, aufgrund des Allquantors davor. Klar gibt es noch eine Million Belegungen, für die die Formel G=t ist, aber das ist egal, G ist immer f durch die Allquantorbedingung.
Für das was du sagst "x=2 oder x>0" werden ja beide Teile (links und rechts vom Oder) falsch sobald du x=0 setzt. Da steht dann "0=2 oder 0>0" und das ist doch sicher insgesamt falsch, weil 0 ist nicht gleich 2 und 0 ist auch nicht größer als 0. f oder f ergibt f.
Oder meinst du, dass 0 nicht im Datentyp der natürlichen Zahlen ist? Ist es nämlich schon, hier zumindest.
hallo !
ich hab folgendes Gegenbeispiel bzw Modell für a.)
x= 1 (linke Seite)
x = 2 (rechte Seite)
das wiederum eingesetzt ergibt t impliziert t = t ....ist also ein Modell
dann
x= 1 (linke Seite)
x!=2 (rechte Seite) also zumbeispiel 3 für x
ergibt hier : t impliziert f = f also ein Gegenbeispiel
nun 2.Fragen die ich mir stelle:
1.) Stimmen mein Aussagen ? hats nochwer so ....?
2.) ich hab auch , nach lesen des threads , angenommen das x links und x rechts nicht gleich ist ..... sonst würd nicht erfüllbar, bzw wiederlegbar rauskommen ....aber.....jetzt kommts......WARUM ist das hier so ?
weiß das jemand .....ich vermute mal es hängt vom Allquantor ab ....aber sicher weiß ichs nicht .... help pls
Stimmt nicht ganz, weil erstens passt den Gegenbeispiel nicht (eine Formel "3=2 oder 3>0" aka "f oder t" evaluiert trotzdem zu true) und zweitens, wie gesagt, der Allquantor vor dem Block rechts von der Implikation (nennen wir ihn G) bewirkt, dass G zu f evaluiert, denn du kannst eine Belegung finden (und es muss nur mindestens eine gefunden werden), für die G=(f oder f)=f gilt, und diese Belegung ist einfach I(x)=0 bzw im richtigen Kontext muss es I'(x)=0 heißen. Die Formel G gilt einfach nicht für alle x (bzw y).
Im Prinzip ist das ja recht simpel, ist immer noch realtiv einfache Aussagenlogik, oder? Soll heißen: Wenn die Bedingung "gilt für alle" verletzt wird, dann kann die Formel, die dieser Bedingung unterliegt, nie gültig sein (sondern wird falsch, laut MPL6).
ahjo stimmt, thx. ich fürchte ich hab die angabe nicht verstanden.
http://hades.gothic.at/iforum/images/smilies/shinner.gifhttp://hades.gothic.at/iforum/images/smilies/engel2.gifhttp://hades.gothic.at/iforum/images/smilies/disturbed.gif
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.