Hallo zusammen,

ich war leider nicht bei der letzten FGI1-Vorlesung, habe aber erfahren, dass der Prof die Themen für die Klausur eingegrenzt hat.
Hat das zufällig jemand mitgeschrieben und kann das hier mal posten?
Wäre super!

Danke

Wurde überhaupt nix eingegrenzt!!!

Hat nur im Schnelldurchlauf viele Themen angesprochen, die meiner Meinung nach, aber nicht sooo wichtig sind, wie z.B. Monoid und so….

Also wie immer in FGI: Es kann ALLES drankommen!

Hat jemand schon die von Frank netterweise zur Verfügung gestellte "Probeklausur" bearbeitet? Ich bin gerade dabei, und finde die Aufgaben z.T. ziemlich happig und vor allem zeitaufwändig.

Probeklausur? Wo kann man die bekommen? Habe schon im mincommsy raum nachgesehen …

Probeklausur? Wo kann man die bekommen? Habe schon im mincommsy raum nachgesehen …

Bitteschön :)

zum Jantzen-Teil gibts dann wohl keine Probeklausur, seh ich das richtig?

kann jemand mir die 1.Aufgabe in Probeklausur erklären ?
danke sehr :)

Danke. Im PDF ist die Rede von weiteren Aufgaben. Wo gibt es die?

Sollte Frank Heitmann das hier lesen: vielen Dank für deinen Einsatz!

Danke. Im PDF ist die Rede von weiteren Aufgaben. Wo gibt es die?

Sorry, hier sind sie :)
Das war's dann aber auch an Probeaufgaben.
Weder zum Jantzen-Teil (den finde ich deutlich schwerer) gibt es welche noch gibt es Musterlösungen.

Sollte Frank Heitmann das hier lesen: vielen Dank für deinen Einsatz!

Danke auch von mir, Frank!

kann jemand mir die 1.Aufgabe in Probeklausur erklären ?
danke sehr :)

Ich denke mal bei 1.1 z.B sollst du sagen was F ist wenn G kontingent und (G=>F) Tautologie ist.
Glaube "allgemeingültig" ist hier richtig.

Ich denke mal bei 1.1 z.B sollst du sagen was F ist wenn G kontingent und (G=>F) Tautologie ist.
Glaube "allgemeingültig" ist hier richtig.

Sollte F nicht auch kontingent sein können?

1.1 in Probeklausur:
Es ist bekannt: G ist kontingent (kann also true und false sein) und die Beziehung G => F (wenn G wahr ist, ist auch F wahr) ist gültig.
Es gibt mindestens ein Fall, in dem G wahr ist, also muss es auch mindestens ein Fall geben, in dem F wahr ist. F kann also nicht ungültig sein. Wenn F gültig ist, ist die Beziehung G => F immer korrekt. Wenn F = G gilt, ist die Beziehung auch korrekt, F wäre dann aber auch kontingent.

Also: F kann kontigent und gültig sein.

Hi….

ich hatte heute morgen über den Commsy-Raum folgende Email an alle Teilnehmer verschickt:

—- —- —- —-
Liebe FGI-Studenten,

am Samstag gibt es kurzfristig ein Letzte-Offene-Fragen-Tutorium.

Eine Anmeldung ist nötig, wenn ihr kommen wollt! (Wenn es zu viele
Anmeldungen sind, dann splite ich die Veranstaltung in zwei.)

Das ganze soll stattfinden
am Samstag (24.7)
14-18 Uhr (bei Split wird's 14-17 und 17-20)
in B-201 (Hörsaal auf dem Stellinger Campus)

Zur Anmeldung schickt bitte kurz einen Reply auf diese
Email und nennt dort einfach euren Namen.

Sonnige Grüße,
Frank :)

PS Einige Texte und Aufgaben findet ihr gleich unter
http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/wimis/heitmann/Lehre/FGI10.html

—- —- —- —-

Wenn ihr eine gültige Email im Commsy-Raum angegeben habt oder nicht im Commsy
eingetragen seid, aber zur ersten Klausur angemeldet seid, dann solltet ihr die ge-
kriegt haben. Sonst nun hoffentlich auf diesem Wege ;-)


Zum Automatenteil der Klausur:
Guckt euch mal Aufgaben 7, 8 und 9 in Aufgaben1.pdf an. Bei 9 könnt ihr dann
für die Sprachen, die nicht regulär sind, einen PDA konstruieren und einen Grammatik
angeben. Auch eine TM für die ein oder andere Sprache anzugeben, könnt ihr ver-
suchen. Dann seid ihr was eventuelle Konstruktionsaufgaben angeht gut vorbereitet.

Dann lohnt es sich die Übungszettel noch mal anzuschauen bzw. zu bearbeiten. Die
dortigen Verfahren und Begriffe sollten bekannt sein. (Das gilt natürlich auch für den
Logik-Teil der Klausur!)

Frank

Werden für die Probeklausur und für das Aufgabenblatt Musterlösungen zur Verfügung gestellt?

Für mich wäre das sehr hilfreich, da ich leider nicht zum Tutorium kommen kann.

Ich finde es echt Klasse, dass Übungsaufgaben zur Verfügung gestellt werden!!

Hi…

Musterlösungen dafür schaff ich nicht mehr, ebenso nicht wie
weitere Aufgaben zum zweiten Teil.

Werkel einfach herum und wenn du irgendwo nicht weiter kommst,
dann schreib mir eine Email (heitmann@…) mit einer konkreten Frage
- oder poste eine Frage hier im Forum.

Frank

Ich versuche mal die Aufgabe zwei der Probeklausur zu lösen:

2. Wie kann das Resolutionsverfahren genutzt werden, um zu testen, ob eine gegebene Formel eine Tautologie ist?

Tautologie: NICHT F ist unerfüllbar.

Mein Vorschlag:
1. KNF bilden
2. F negieren
3. Rsolutionsverfahren anwenden
4. Lässt sich die leere Klausel ableiten, so ist NICHT F unerfüllbar und somit Tautologie

Top oder Flop?

Ich bin bisschen aus dem Thema raus. Aber benötigt das das ResVerfahren nicht eine Formel in konjunktiver Form? Dann müsstest du 1 und 2 tauschen.

In der Aufgabenstellung steht nicht ob es sich bei der Formel F um eine bereits in KNF befindlichen Formel handelt. Deshalb erstmal KNF bilden (Voraussetzung für das Resolutionsverfahren).

Bin ich jetzt völlig auf dem falschen Dampfer wenn ich sage dass es egal ist ob ich erst die KNF bilde und dann negiere oder umgekehrt?

Aaaaaah … sorry! Jetzt hab ich verstanden! Mein Fehler

Alternativ kannst du auch erst die DNF bilden und die negieren.

… genau das dachte ich mir auch gerade. Danke für den Hinweis!

btw: wird in der Klausur eigentlich viel Fachwissen zum Thema TI abgefragt? Ich meine, diese ganzen Verfahren zu kennen und anwenden zu können ist das eine, das Vokabular zu kennen das andere …

"TI" = Theoretische Informatik?

Ja.

Wenn du damit den Jantzen-Teil (Automaten, Sprachen, Berechenbarkeit, Komplexität) meinst: Ich hoff's doch, weil's doch eines der schönsten Gebiete in der Informatik ist. Und so viel Vokabular gibt's da nicht.

[…]
PS Einige Texte und Aufgaben findet ihr gleich unter
http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/wimis/heitmann/Lehre/FGI10.html
[…]

Das war in 2004 mal im Netz zu erreichen (passwortgeschützt) :
[attachment=416]

Ich denke "eines der schönsten Gebiete in der Informatik" ist eher subjektiv (:

99,89% der Studierenden wollen FGI1 "einfach nur bestehen"

Der Rest strebt dann eine Mitarbeiterstelle im Ab TGI an …

Kann mir jemand sagen, was bei Aufgabe 1.5 der Probeklausur rauskommt? Ich komme da auf gültig oder kontingent, bin aber nicht ganz sicher.

Gültig soll wohl in dem Zusammenhang "Tautologie" bedeuten. Und das ist ja wohl etwas anderes als kontingent …

Wenn ich die Aufgabenstellung zu 1.5 richtig verstehe, dann soll entschieden werden ob F kontradiktorisch, kontingent oder tautologisch sein muss für den Fall dass jedes Modell für G auch Modell für G => F ist …

G folgt G=>F ist äquivalent zu {G}U{G} folgt F ist äquvalent zu {G} folgt F.

Da man nichts über G weiß, kann F nur gültig sein.

Danke, hab's nun verstanden.

Hi,

ich habe versucht mir 1.5 anhand einer kleinen Tabelle
klar zu machen (chacun à son goût):

G | F | G => F
—————
0 | 1 | 1
—————
0 | 1 | 1
—————
1 | 0 | 0 -> G ist an dieser Stelle erfüllt, aber G => F nicht.
—————
1 | 1 | 1

Deshalb muss F gültig bzw. eine Tautologie sein.

Ist die Argumentation richtig?

Jain

du hast gerade bewiesen, dass F auch kontingent sein kann.

Wo ist der Haken? Also für nicht gegebenes G, ganz allgemein wäre die Lösung: F kann nur gültig sein. So habe ich halt von der Aufgabestellung verstanden.

Sei nun G gegeben, da wollen wir auch nicht beschränken ob G unerfüllbar oder kontingent ist. Dann kann F auch kontingent sein, indem F Nullen nur für Modelle haben, die auch Nullen für G sind.

Falls aber G gegeben und G ist gültig, dann sind wir wieder zurück beim Anfang, dass F nur gültig sein kann.

In deiner Tabelle hast du also ein bestimmtes G gewählt, das zufällig kontingent ist, dann darf F also nur gültig oder kontingent sein. Aber nicht beliebige Kontingenz, F darf nur Nullen haben, bei dem G auch Null hat. (Bemerkung: nicht umgekehrt!!! wo G Nullen hat, zwingt es nicht, dass F auch in der Stelle Null hat.)

Verfeinerung:

F kann tatsächlich auch ungültig sein, falls es keine Modelle gibt, die G erfüllt.

Ich würde gern auch noch ne Frage zum allseits beliebten Pumping lemma stellen :D

L9c ={a^nb^m |∃g∈N:2g=n+m}

soll festgestellt werden, ob das ein regulärer Ausdruck ist. Ich denke mal nicht, aber naja beweisen halt –> Pumping Lemma….

Könnte mir hier jemand bitte auf die Sprünge helfen ?
Wozu brauche ich da eigentlich das g ?
Und wie lautet der Lösungsweg in etwa dazu ?

vielen Dank !

Das g bzw. 2g stellt sicher, dass die Summe n+m eine gerade Zahl ist. Über das Pumping Lemma kannst du ja ein k wählen, so dass v auf jeden Fall ein "a" enthält. Das kannst du dann auf- oder abpumpen, um aus a^n z.B. a^n+1 zu machen, so dass die Bedingung nicht mehr erfüllt ist und die Sprache somit nicht regulär sein kann.

Das g bzw. 2g stellt sicher, dass die Summe n+m eine gerade Zahl ist. Über das Pumping Lemma kannst du ja ein k wählen, so dass v auf jeden Fall ein "a" enthält. Das kannst du dann auf- oder abpumpen, um aus a^n z.B. a^n+1 zu machen, so dass die Bedingung nicht mehr erfüllt ist und die Sprache somit nicht regulär sein kann.

Die Sprache ist aber regulär. Die Sprache enthält ja alle geraden Wörter wo am Anfang a's und danach b's kommen.
Der reguläre Ausdruck
[latex](aa)^*(bb)^* + (aa)^*a(bb)^*b [/latex]
sollte die Sprache beschreiben.
Denn ein Wort aus a's und b's ist genau dann gerade, wenn die Anzahl von a's gerade und die Anzahl von b's gerade ist oder die Anzahl von a's ungerade und auch die Anzahl von b's ungerade ist.

hast jemand die Idee über die Aufgabe 3.2 und 3.3 bei Probeklausur ?
es wäre nett :) wenn du mir erklären könntest

Ich finde für diesen Ausdruck keinen DFA, bzw. nur für die beiden Teilausdrücke kriege ich das hin.

Der Automat sollte der im Anhang sein.

Edit: wäre s0 auch noch Endzustand..

Weiss jemand, ob wir auch Kleene Verfaren lernen müssen? Wir haben es einmal in der Hausaufgabe gemacht, es ist nicht schwehr, aber ziemlich aufwendig von der Zeit her. Gab es schon jemals in alten Klausuren?

Der Automat sollte der im Anhang sein.

Edit: wäre s0 auch noch Endzustand..

Danke :) Sollte s1 nicht auch Endzustand sein?

Versteht einer [latex]$L_{9d}$[/latex]? Ist das nicht einfach [latex]$a^{2g}b^{2g}[/latex] und nicht regulär?

Weiss jemand, ob wir auch Kleene Verfaren lernen müssen? Wir haben es einmal in der Hausaufgabe gemacht, es ist nicht schwehr, aber ziemlich aufwendig von der Zeit her.

Können sollte man es sicherlich, aber aus dem von dir genannten Grund kann ich mir kaum vorstellen, dass es für die Klausur relevant ist.

Sollte s1 nicht auch Endzustand sein?

Nein, ansonsten wäre ja bspw. auch 'a' ein akzeptiertes Wort.

Versteht einer [latex]$L_{9d}$[/latex]? Ist das nicht einfach [latex]$a^{2g}b^{2g}[/latex] und nicht regulär?

Jo.

Weiss jemand, ob wir auch Kleene Verfaren lernen müssen? Wir haben es einmal in der Hausaufgabe gemacht, es ist nicht schwehr, aber ziemlich aufwendig von der Zeit her. Gab es schon jemals in alten Klausuren?

Kam wohl mal dran, es hieß aber 5-10%-ige Warscheinlichkeit oder sowas ;-)
Ich denke wenn man die Rekursionsformel kennt, sollte es ausreichen (es kann ja auch nur die abgefragt werden).

Moin Moin, wenn von euch jemand die Aufgabe 8 gemacht hat von Frank, mit den DFA's wäre es cool wenn jemand die mal hochladen könnte =)

Danköö

muss man 50% von der Gesamtklausur erreichen oder 50% von jedem Teil?

Och nööö… das nimmt total den Sinn solcher Aufgaben!
Der Sinn ist das DU versuchst so einen Automaten zu basteln,
NICHT dass du dir die Lösung dazu anguckst. Wenn du Beispiel-
automaten suchst, dann brauchst du dir doch nur ein x-beliebiges
Buch dazu nehmen (oder im Netz suchen; die englischen Wikipedia
Seiten sind meist nett). Da findest du Automaten in Hülle und Fülle.

Danach kannst du dann versuchen die Aufgaben zu bearbeiten.

Man lernt Automatenkonstruieren genausowenig wie Programmieren
dadurch, dass man sich nur Lösungen anguckt. Man muss das *selbst*
*machen*. Eine gute Herangehensweise ist mit dem Startzustand
anzufangen und sich zu überlegen, was bei jeder Eingabe passiert:
brauch ich einen neuen Zustand (und falls ja, welche Information will
ich mir merken?) oder sollte ich bleiben wo ich bin (weil die Information,
die ich mir da merke, erhalten bleibt oder ich einfach nichts gewonnen
habe)?

Ein gutes Beispiel für diese Vorgehensweise ist ein Automat in dessen
Zuständen ich mir das zuletzt gelesene Symbol merke. Ich fange im
Startzustand z_start an, lese ich nun eine 0 gehe ich in z_0, lese ich
eine 1 in z_1. Im Index des Zustandes merke ich mir also, was das zu-
letzt gelesene Symbol ist. Nun fragt man sich, wo man hingeht, wenn
man in z_0 ist und eine 0 bzw. eine 1 liest und entsprechend für z_1.
Wenn man nun dabei neue Zustände macht (braucht man hier nicht), dann
guckt man wieder was in denen bei allen Eingaben passiert usw.
Dabei entsteht ein vollständiger DFA.
(Randbemerkung: Im obigen Beispiel käme man auch mit nur zwei Zuständen aus.)

Eine andere Herangehensweise ist sich zuerst zu überlegen, welche Informationen
man eigentlich speichern will: Gelesene Symbole, bestimmte Eigenschaften der
gelesenen Symbole (z.B. vielfaches von etwas zu sein oder ähnliches) usw.
Dann danach die Zustände zu konstruieren und sich dann noch die Kantenübergänge
zu überlegen.

In jedem Fall ist zu beachten, dass man nur *endlich viele* Informationen speichern
kann!

Mit dem Wissen im Hinterkopf probier mal jetzt die Aufgaben.

Frank

Ups, mein vorheriges Post bezog sich auf das von Philipp oben.

Zu dem hier:

muss man 50% von der Gesamtklausur erreichen oder 50% von jedem Teil?

50% der Gesamtklausur und einen bestimmten Punkteteil in jedem Teil, ich weiss nicht
mehr genau wie viel. Ich glaube 40%.

Im übrigen: Lern einfach!

Ich hab auch schon so skurrielle Fragen gekriegt wie "Wieviele Multiple-Choice Fragen wird
es geben?" - Was genau kann man mit dem Wissen denn anfangen?!

Wobei ich deine Frage ja noch nachvollziehen kann: In einem Teil sehr gut zu sein und
in dem anderen dann nur sehr wenig zu können, wird aber nicht reichen. Du musst in
beiden Teilen ein gewisses Verständnis zeigen.

Frank

@Frank…

na was denkste denn was ich hier mache?!?!?! Ich will doch nur sehen ob das so einigermaßen hinhaut was ich hier tu, weil ich gerade ein wenig auf dem schlauch stehe… schon klar das lösungen alleine nix bringen, weil man selten den gleichen Automaten 2mal hat… trotzdem danke

edit: hab ja nix davon wenn ich hier einen automaten mache und nicht weiß ob der funktioniert… ich finde zwar das er es tut, aber wissen kann ichs ja schlecht ohne lösung ;)

Hm, ich finds schon ok nach einer Musterlösung zu fragen, damit man seine Ergebnisse auch vergleichen kann. Hat man einen Fehler den man nicht bemerkt hat ist so immerhin der Lerneffekt niedriger.

Ich fand 8.) gar nicht so leicht und hab durch Überlegen z.T. zu lange gebraucht. Da hab ich dann jeweils den NFA entworfen (der selten ein Problem darstellt) und den Potenzautomaten daraus konstruiert. Nur als Tipp, falls man auf herkömmlichen Wege überhaupt nicht weiterkommt bei sowas.

Was ist bei 8 c) eigentlich genau gemeint: Die Sprache bestehend aus allen Wörtern, die eine ungerade Anzahl von Nullen beinhalten?
a) und b) fand ich auch ziemlich tricky, in der Klausur würde ich das aus Zeitgrunden wohl gleich mit Potenzautomatenkonstruktion machen.

Andere Herangehensweise: Was ist das kürzeste Wort der Sprache? Bau erstmal einen Automaten, der genau dieses Wort akzeptiert.
Dieser hat einen Startzustand, einen Endzustand und dazwischen eine Kette von anderen Zuständen.

Dann schaust du bei jedem Zustand, welche Kante (z.B. 0 oder 1) noch fehlt und überlegst ob die überhaupt gebraucht wird und wenn ja, wohin die geht (nie weiter Richtung Endzustand, nur zum selben Zustand oder weiter Richtung Anfangszustand).

Die Methode funktioniert zwar nicht bei allen Aufgaben, aber einige (z. B. 8a,b,c) kann man damit schnell erschlagen.

[attachment=418]

klappt der Automat für 8 b) so?!?! würde mich wundern :D

Als Tipp falls man seinen endlichen Automaten mal "ausprobieren" will: Es gibt dafür Simulatoren (teilweise auch direkt online als Java-Applet oder Flash), mit denen man herumexperimentieren und die Dinger mal durchlaufen lassen kann.

Wie in der Softwaretechnik gilt selbstverständlich auch hier: Ein paar positive Testfälle beweisen nicht die allgemeine Korrektheit. :)

@Philipp: Ah, super, du hast schon was gemacht! (Ich wollte nur dem 'Einmal-Draufgucken-und-gleich-
sagen-ne-das-kann-ich-nicht-und-nach-Musterlösung-fragen' vorbeugen. Das bringt halt einfach echt
nur dann was, wenn man selbst was macht.) Dann poste doch einfach mal deine Lösungen und dann
kann man sagen, was richtig ist und was nicht. Das ist auch darum viel besser, weil es ja oft mehrere
Lösungen gibt und nur weil deine dann anders aussieht als die Musterlösung, muss sie ja nicht falsch
sein! Lerneffekt würde nur dann einsetzen, wenn du deine Fehler auch verstehen kannst! Und wenn
man nur sieht, dass es in der Musterlösung anders aussieht, hilft das ja nicht. (Darum kriegt man seine
Übungszettel ja auch mit Kommentaren versehen korrigiert zurück.)

Aeeehhh, also kurz: Poste mal, was du gemacht hast!

Frank

@Philipp: Ah, super, du hast schon was gemacht! (Ich wollte nur dem 'Einmal-Draufgucken-und-gleich-
sagen-ne-das-kann-ich-nicht-und-nach-Musterlösung-fragen' vorbeugen. Das bringt halt einfach echt
nur dann was, wenn man selbst was macht.) Dann poste doch einfach mal deine Lösungen und dann
kann man sagen, was richtig ist und was nicht. Das ist auch darum viel besser, weil es ja oft mehrere
Lösungen gibt und nur weil deine dann anders aussieht als die Musterlösung, muss sie ja nicht falsch
sein! Lerneffekt würde nur dann einsetzen, wenn du deine Fehler auch verstehen kannst! Und wenn
man nur sieht, dass es in der Musterlösung anders aussieht, hilft das ja nicht. (Darum kriegt man seine
Übungszettel ja auch mit Kommentaren versehen korrigiert zurück.)

Aeeehhh, also kurz: Poste mal, was du gemacht hast!

Frank

siehe oben ^^

Endzustand fehlt. Wenn q3 Endzustand ist, wird z. B. 0100 akzeptiert?

@Philipp: Der Anfang sieht gut aus. Das Hauptproblem ist die 1-Schleife bei q_2. Wenn du das so
lässt, dann kommst du auch mit so Sachen wie 01111110 klar, das will man ja nicht. Ganz zum
Schluss bei q_3 ist auch noch was nicht gut, aber das merkst du dann vielleicht, wenn du das
korrigiert hast.

Ein Tipp: Das Wort steht da zwar als v010u, aber man kann das für den DFA so machen (und
das klappt bei dir am Anfang auch sehr gut), dass man versucht das *erste Auftreten* von 010
zu ermitteln. Hat man das, ist's egal was danach kommt, hat man's nicht, muss man ggf. wieder
zum Start zurück.

Ansonsten fehlen noch Endzustände und der Startzustand (q_0 vermutlich).

Frank

Endzustand fehlt. Wenn q3 Endzustand ist, wird z. B. 0100 akzeptiert?

oh ja hab ich vergessen, soltle q3 sein! öhm wieso 0100 ? hm, naja wie gesagt steh ich mmoment fett auf dem schlauch…

@Philipp
Die 1-Kante von q2 und die 0-Kante von q3 sind nicht richtig, ansonsten sieht es gut aus.

mit [latex]w = v010u,~ v = \epsilon,~ u=0[/latex] ergibt sich w = 0100.

hm… ich bin hier die ganze zeit nur am rumtesten… das die beiden kanten falsch sind seh ich jetzt auch… und ich hab versucht die anders zu legen. Also z.B. q2-> 1 ->q0 oder q2 -> 1 -> q1… aber es erschliesst sich mir iwie nicht, weil ich immer ein wort finde was akzeptiert wird aber nicht akzeptieren werden darf… seh wohl den wald vor lauter bäumen nicht ^^

Nicht nur wild testen. Denken. Wo ist das Problem? Die 1-Kante bei q_2 zunächst. Die ist doof.
Bisher konntest du führende 1en lesen, wenn dann die 0 kam hast du vermutet, dass jetzt die
erhoffte 010 beginnt. Gehst also in q_1 um zu sagen, ok die 0 hab ich. Wenn hier weitere 0en
kommen, weisst du immer nur weiterhin, dass die zuletztgelesene die erste von 010 sein kann,
bleibst also in q_1. Wenn die 1 kommt, weisst du, du hast jetzt (möglicherweise) das 01 vom
ersten auftreten von 010 gelesen. Wenn jetzt eine 0 kommt wäre alles toll. Kommt aber die
eins, dann war das doch nicht die 01 von der ersten 010, sondern halt nur irgendwie 011 oder
so. Wo gehst du jetzt mit der 1 wieder hin? Wo hast du dir sozusagen gemerkt, dass du noch
nichts weisst, dass 010 noch nicht da war und du auch die erste 0 davon also nicht gesehen haben
kannst.

Frank

Hier ist meine version von 8b) :P
Ich finde auch das vergleich mit Programmieren ist auch ziemlich schlecht, da beim Porgrammieren sieht man ja ob das funktioniert oder nicht, wenn man das nicht erkennt, lernt man unwissend was falsches. Also sind Musterlösungen(oder irgend welches feedback) sind für das lernen genau so wichtig wie die Aufgaben selbst.

Ist es bei Aufgabe 6.1.b (von Aufgaben1.pdf) tatsächlich so, dass der Markierungsalgorithmus gar nicht angewendet werden kann? Nach zweimaliger Anwendung des Distributivgesetzes auf den Term in eckigen Klammern bekomme ich nämlich u.a. eine Klausel mit zwei positiven Literalen.

hm… wenn ich also von q2 in den startzustand q0 wechsel sollte ich ja wieder in dem stand sein, dass ich noch kein 010 bekommen habe… (also: q2->1->q0) … ja? ^^… (ich muss dazu sagen, dass ich in der zeit hier noch ein paar andere DFAs gemacht habe und die wirklich gut funktioniert haben, aber der hier ist bei mir ein derber brainfuck^^) und dann müssen wir ja noch u reinbekommen. Reicht dafür eine schleife mit 0,1 an q3?

Schon mal ein riesen Dankeschön =)

edit: seh ich das richtig, dass meine Version jetzt genauso aussieht wie die von konst(danke)? :D:D:D …. ^^

[…] beim Porgrammieren sieht man ja ob das funktioniert oder nicht

Sechs. Setzen. ;-)

Nein, ernsthaft. Beim Programmieren "siehst" du auch nicht einfach so, ob was funktioniert
oder nicht. Du siehst vielleicht, dass bei bestimmten Eingaben etc. dein Programm sich so
verhält, wie du's erwartest, aber das ist noch weit, weit ab davon, dass das Programm
"funktioniert" (= korrekt arbeitet - und zwar *immer*).

Oder wie meinst du, dass Bugs in Software kommen? Weil jemand die da absichtlich einbaut?
Bestimmt auch mal ;-) aber i.A. ja, weil eben nicht so einfach zu sehen ist, ob ein Programm
das tut, was es tun soll.

Was wir können ist mechanisch sagen, ob der *Syntax* eines Programmes stimmt. Wir sind
aber noch weit davon entfernt, etwas ähnliches auch über die *Semantik* sagen zu können.
(Thema: Softwareverifikation, sehr spannend)

Das Halteproblem macht in dem Zusammenhang auch eine wichtige Aussage, nämlich, dass
es nicht möglich ist, soetwas allgemein algorithmisch zu lösen. — Das, um nochmal dem Thread
entsprechend etwas klausurrelevantes einzustreuen ;-)

Frank

PS Und, ja, ich streite nicht ab, dass Musterlösungen auch einen Lerneffekt haben. Die Frage
ist, wie man mit solchen Musterlösungen umgeht. Meine Argumentation war lediglich, dass es
genügend Beispiele (= Lösungen) zu Automaten im Netz und in den Büchern gibt. Das ist dann
natürlich nicht *genau die* Sprache, die ihr jetzt da auf dem Aufgabenzetteln habt und also
auch nicht *genau die* Lösung, aber so wird es in der Klausur ja auch nicht sein.
Zudem könnt ihr auch versuchen zu *beweisen*, dass euer Automat die Sprache akzeptiert.
Bei der Argumentation (im Beweis) fällt einem dann oft auch auf, was noch nicht klappt.

@Philipp: Super! Zu der Schleife an q_3: Wenn du erstmalig in q_3 landest, weisst du ja jetzt, dass du
bisher ein Wort gelesen hast, in dem einmal 010 (gerade zuletzt) die Zeichenkette 010 auftratt. Was
jetzt kommt ist egal. Daher jetzt die 0,1 Schleife an q_3.
(Man beachte übrigens, dass die Menge der Wörter, die einen von q_0 nach q_3 bringen und dann
nicht weiter (also Wörter w der Art q_0 — w —> q_3 und auf dem Weg von q_0 nach q_3 tritt
q_3 nicht auf) nicht gleich ist mit der Menge der Wörter v010 mit v \in {0,1}^*. Der Automat
ist nämlich so konstruiert, dass er, wenn er erstmalig in q_3 auftritt genau *einmal* 010 gelesen
hat und dies ist das Ende des Wortes. Trotzdem akzeptiert der Automat die gegebene Sprache,
denn wenn schon in dem v der Sprachbeschreibung eine 010 auftritt, dann könnte man das Wort
anders in v'010w' zerlegen und ist dann nach v'010 in q_3 und liest dort den Rest.)

Frank

Naja, was lange währt…. :D

Danke =)

@henning: Das sieht zunächst so aus, du kannst aber Idempotenz- und Absorptions-
Regeln anwenden und gelangst dann doch zu einer Hornformel (siehe Skript Folie 4[7]).

(Die Aufgabe ist etwas unglücklich gestellt; da fehlt bestimmt irgendwo ein \nicht, so
dass der Algorithmus dann sofort anwendbar gewesen wäre, aber egal, so geht's
trotzdem.)

Frank

Wie sinnig… es ist ein Smilie geworden :-)
Ich meinte eben Folie 7 aus Kapitel 4 (im Skript des ersten Teils).

Frank

Was ist bei 8 c) eigentlich genau gemeint: Die Sprache bestehend aus allen Wörtern, die eine ungerade Anzahl von Nullen beinhalten?

ich stelle mir gerade eine aehnliche frage zur notation bei aufgabe 9 e: anzahl der a's = anzahl der b's?

@konst: Eben übersehen. Sieht auch gut aus.

Frank

@henning: Das sieht zunächst so aus, du kannst aber Idempotenz- und Absorptions-
Regeln anwenden und gelangst dann doch zu einer Hornformel (siehe Skript Folie 4[7]).

Danke! Idempotenz hatte ich schon angewandt, aber die Absportionsmöglichkeit nicht gesehen - jetzt lüppt's!

Kennt ihr die Notation nicht? Wenn M eine Menge ist, ist |M| die Anzahl der Elemente in M.
Wenn w ein Wort ist, ist |w| die Länge des Wortes. Wenn x ein Symbol ist, dass in einem
Wort w auftreten könnte (soll heissen: wenn w \in \Sigma^* ist und x \in Sigma), dann
ist mit |w|_x die Anzahl der x in w gemeint.

Beispiel: w = 000110, |w| = 6, |w|_0 = 4, |w|_1 = 2, |w|_2 = 0.

Das geht auch mit längeren Wort, wobei man da ein wenig aufpassen muss. Hier ist das bei
9f mit ab bzw. ba gemacht und da sollte das keine Probleme geben. Probleme gibt es bei
sowas wie |aaaa|_aa, denn wie oft tritt aa in aaaa auf? Zweimal oder Dreimal? Das müsste
man dann definieren wie man das meint. Ich glaube man definiert das so, dass es dreimal
drin ist, weil man sagt so oft wie man einen (eindeutigen, neuen) Anfangsbuchstaben finden
kann, ab dem das Teilwort startet.

Aber erstmal reicht es die Notationen |w| und |w|_x für einzelne Symbole x zu kennen.

Frank :)

@Frank

Vielen Dank, so hatte ich mir das auch gedacht, aber es ist beruhigend, dass von kundiger Seite noch mal erklärt und bestätigt zu bekommen.

Ich brauch mal Hilfe bei der Probeklausur Aufgabe 4.1:
Prüfen sie ob folgende Klauselmenge erfüllbar ist.

Mir ist das Vorgehen nicht ganz klar. Meiner Meinung nach ist die Resolution ja ein Verfahren um auf Unerfüllbarkeit zu testen, Erfüllbarkeit ist dann ja nicht automatisch gegeben wenn ich die leere Menge nicht ableiten kann, oder? Die gesamte Formel zu negieren, würde doch dazu führen, dass ich teste ob die Formel eine Tautologie ist.

Irgendwie kom ich da grad nicht weiter.

Meiner Meinung nach ist die Resolution ja ein Verfahren um auf Unerfüllbarkeit zu testen, Erfüllbarkeit ist dann ja nicht automatisch gegeben wenn ich die leere Menge nicht ableiten kann, oder?

hm… ich würde sagen, dass der Algorithmus, wie er auch im Skript steht, eine Formel als erfüllbar bezeichnet wenn die leere klausel nicht ableitbar ist. ohne gewähr natürlich

Genau, Resolution ist ein Verfahren um Unerfüllbarkeit zu testen. Die Aussage ist folgende:

Eine aussagenlogische Formel ist unerfüllbar genau dann, wenn die leere Klausel ableitbar ist.

Beachte das "genau dann, wenn", d.h. die Aussage ist

WENN eine aussagenlogische Formel unerfüllbar ist, DANN ist die leere Klausel ableitbar.
und
WENN die leere Klausel ableitbar ist, DANN ist die aussagenlogische Formel unerfüllbar.

Was weiss man nun, wenn die leere Klausel *nicht* ableitbar ist? (Man aber - und dies geht nur in
der Aussagenlogik - alle Resolventen gebildet hat.)

Frank

Meiner Meinung nach ist die Resolution ja ein Verfahren um auf Unerfüllbarkeit zu testen, Erfüllbarkeit ist dann ja nicht automatisch gegeben wenn ich die leere Menge nicht ableiten kann, oder?

Ist die leere Klausel denn in diesem Fall ableitbar?

Meiner Meinung nach ist die Resolution ja ein Verfahren um auf Unerfüllbarkeit zu testen, Erfüllbarkeit ist dann ja nicht automatisch gegeben wenn ich die leere Menge nicht ableiten kann, oder?

Ist die leere Klausel denn in diesem Fall ableitbar?

bei mir schon :D

bei mir schon :D

Bei mir auch. ;)

dito. [24]

WENN eine aussagenlogische Formel unerfüllbar ist, DANN ist die leere Klausel ableitbar.
und
WENN die leere Klausel ableitbar ist, DANN ist die aussagenlogische Formel unerfüllbar.

Was weiss man nun, wenn die leere Klausel *nicht* ableitbar ist? (Man aber - und dies geht nur in
der Aussagenlogik - alle Resolventen gebildet hat.)

Dann kann sie ja nicht mehr unerfüllbar sein (DANN == 0 -> WENN != 0)?

Manchmal sieht man aber auch schon vor der Resolution, dass eine Formel erfüllbar ist. Dann ist es gar nicht nötig, mühsam alle Resolventen zu bilden, sondern man kann sich auf 0 P-/N-Resolventenbildungen stützen.
Das mit "Zur Übung zu beweisen" (haha) in Kapitel 8, 29 sollte man sich mal durchgelesen haben imo.

Hat z.B. jede Klausel mind. ein negatives Literal, ist sie erfüllbar. Denn P-Resolution liefert dann genau 0 Resolventen (es gibt ja keine Klauseln mit nur-positiven Literalen). Und P/N-Resolution ist w-vollständig bzw. liefert dann die leere Klausel, wenn sie die "normale" Resolution auch liefert. Somit spart man sich in manchen Fällen viel Schreiberei [25]

Genau! Und nicht unerfüllbar bedeutet, dass die Formel erfüllbar ist. Sie könnte
vielleicht sogar eine Tautologie sein, das weiss man so noch nicht, man weiss
erstmal nur, dass sie erfüllbar ist.

In der PL klappt das leider nicht mehr, weil man da i.A. ja nicht mehr alle Resolventen
bilden kann, also nicht weiss, ob die leere Klausel nicht ableitbar ist, oder man es nur
noch nicht geschaft hat.

Die Aussagen zur P- und N-Resolutionen sind gut. Das ist gut, dass zu wissen, damit
kann man sich oft sehr viel arbeit sparen (auch wenn man z.B. erstmal P- bzw. N-
Resolution macht, da man damit ja den Raum der möglichen Resolventen ordentlich
einschränkt; ggf. kann man dann aber, wenn man das Ergebnis "sieht", davon ab-
weichen).

Frank

Frage zu Probeklausur Aufgabe 6.3… besser gesagt ist es richtig was ich gemacht habe? ^^

[/forall y] [/forall u] [ [/not] (P (e,y) [/and] Q (f(y), k(u)) [/or] ( P(u, k(u)) [/or] Q (k(u), f(y))]

wobei ich:
x durch e ersetzt habe
z durch f(y)
v durch k(u)

Fast richtig.

Du hast v durch k(u) ersetzt, oder? Aber weder k(y) noch k(u) ist richtig.

Guck dir nochmal Folien 10-21 und 10-22 an. (Vorallem das dritte Beispiel
bei 10-22).

Frank

ja k(u)…

muss ich ein zweistelliges funktionssymbol einführen? Wegen der 2 Allquantoren?

so:

[/forall y] [/forall u] [ [/not] (P (e,y) [/and] Q (f(y), k(y, u)) [/or] ( P(u, k(y, u)) [/or] Q (k(y, u), f(y))]

also v durch k(y, u) ersetzen. ist der rest sonst okay ?

Jip. So ist gut.

Frank

Abgesehen davon, dass du an einer Stelle noch k(u) hast stehen lassen ;-)

Eine Anmerkung noch: Warum hast du die Implikation aufgelöst? Das wäre nicht
nötig gewesen und so wie es jetzt ist, ist es weder KNF noch DNF (falls du das
beabsichtig haben solltest).

Frank

öh, gute frage :D dachte erst das wäre cool ^^… ja weiss ich jetzt selber net so genau warum ich das gemacht hab, wahrscheilich aus gewohnheit :D aber gut das sonst alles richtig ist =) danke =)

Ich wollt nur darauf hinaus, dass es ja auch noch die "KNF" in der Prädikatenlogik gibt,
also die "Klauselnormalform". Dort müsstest du die Matrix (der Formelteil hinter den Quantoren)
dann aber auf KNF (= Konjunktive Normalform) bringen.

Aber danach war hier zumindest gar nicht gefragt.

Frank

okay =) wollte ich nicht machen zumindest nicht bewusst… bei Prädikatenlogik bin ich mir im allgemeinen sehr unsicher… hoffe mein wissen reicht für die Klausur ^^

Und toll, dass Du uns aufgaben bereitgestellt hast, damit man nicht immer die selben macht!

Weiss jemand, ob wir auch Kleene Verfaren lernen müssen? Wir haben es einmal in der Hausaufgabe gemacht, es ist nicht schwehr, aber ziemlich aufwendig von der Zeit her. Gab es schon jemals in alten Klausuren?

1. Frage: Ja (=verstehen lernen sollten)
2. Frage: Nein

Ich hab da auch nochmal ne ganz dumme Frage.
Kann ich bei der Resolution auch mehrere Aussagensymbole in einem Schritt resolvieren?
Also z.B. [latex]$\{\neg A, B, C}}, \{A, \neg B , D\}$[/latex] zu [latex]$\{C, D\}$[/latex]

*NEIN* !

x-mal erwähnt (mit x > 10 ;) ) und immer, immer, immer wieder passiert das doch!

Ihr wisst doch auch alle das 1 > 0 ist! Beim Resolvieren IMMER NUR EIN PAAR

IMMER NUR EINS
IMMER NUR EINS
IMMER, IMMER, IMMER NUR EINS
!!!


Ernsthaft: Immer nur eins. Ein Beispiel, warum das sonst keinen Sinn macht ist
das folgende:

{A, B} {-A, -B}

da könntest du sonst in einem Schritt zur leeren Klausel kommen. Das würde aber
bedeuten, dass die Formel
(A oder B) AND (nicht A oder nicht B)
unerfüllbar ist (das ist die Formel die durch obige Klauselmenge "codiert" wird), was
sie nicht ist. Z.b. mit "A = 1" und "B = 0" nicht.

Frank

PS IMMER NUR EINS, bitte, bitte, bitteeeeeee…… ;-)

Danke, hatte ich mir auch schon so gedacht. Aber die Hoffnung auf eine billige Lösung gibts ja immer :)

@Marc: Pro Schritt immer nur ein Paar resolvieren, zwei oder mehrere gleichzeitig geht in die Hose.
z.B. kannst du folgendes NICHT resolvieren: { {A,B} , {¬A,¬B} }
Was auch nicht stimmen könnte, denn würde das gehen, wäre es unerfüllbar. Aber diese Formelmenge ist durchaus erfüllbar.



Ich habe noch eine Frage zur Unifikation: Damit eine Formel unifizierbar ist, müssen ja alle Elemente der Menge die gleiche Funktion mit der gleichen Stelligkeit sein. Reicht das alleine aus?
Ich glaube eigentlich nicht, weil z.B. L = {P(a), P(b)} nicht unifizierbar ist, wenn a und b Konstanten sind. Frage schon selbst richtig beantwortet?

Jip :)

Frank

Unifikation:

Variablen durch Konstanten ersetzen
Variablen durch Formeln ersetzen

Das sollte ja beides gehen. Darf man auch Funktionen durch Variablen ersetzen? [2]

Es werden nur Variablen durch etwas ersetzt. Guckt euch den Algorithmus im Skript
an (Folie 11-26), da steht ganz genau, was ihr tun dürft und was nicht! (Variablen
durch Formeln geht nicht, nur durch andere Terme (also Konstanten, Variablen oder
Funktionen) - und auch da in einem Fall nicht!)

Frank

Danke nochmal für die Antworten auf die sehr kurzfristigen Fragen, Frank. :)

Gern geschehen. Jetzt muss ich aber auch los, ist gerade 18 Uhr geworden.

Vielleicht kann ich heute am späten Abend nochmal reinschauen. Sonst wünsch
ich euch allen schon mal viel Erfolg bei der Klausur!

Bis morgen!

Frank :)

Moin !

Könnte mir bitte noch kurz jemand auf die Sprünge helfen wie ich eine Biimplikation in einer prädikatenlogischen Formel auflöse ?
Ich finde da grade keine Antwort zu….läuft das wie bei einer Biimplikation im Rahmen der Aussagenlogik ?

Danke und allen viel Erfolg Morgen !

A <=> B ist genau so wie A => B und B =>A, man kann das umformen zu (A & B) | (not A & not B)

Wird es auch für den zweiten Klausurtermin ein Paniktutorium geben?

Gute Nachricht: Ja
Schlechte Nachricht: Jetzt gerade [25]

http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS10/FGI1-Support/#repetitorium

War das Tutorium vor der letzten Klausur nicht "unabhängig" vom Repetitorium?

Kann mir jemand weiterhelfen und sagen was der Unterschied zwischen Grad und Tiefe einer Formel ist?!

Grad: Anzahl der Knoten
Tiefe: Maximale Anzahl der Kanten von der Wurzel bis zu einem Blatt

Grad lässt sich auch anschaulich gut als "Zahl der Junktoren in einer Formel" bezeichnen.

Moin, könnte jemand mir die Aufgabe 5 in Probeklausur erklären ? Es wäre schön . Danke .

[IMG]http://farm3.anhso.net/upload/20101003/04/o/anhso-045337_Bildschirmfoto_2010-10-02_um_23.53.25.jpg[/IMG]

Folie 10, S. 5

P(x, y) – Mensch x hat Geschlecht y (wir nehmen mal an, dass sich jedem Menschen genau ein Geschlecht zuordnen lässt)

F sagt dann aus, dass jeder Mensch ein Geschlecht hat.
G sagt aus, dass es ein Geschlecht gibt, das jeder Mensch hat.

Die Aufgabe solltet ihr dazu benutzen den *formalen* Umgang mit der prädikatenlogischen
Semantik zu üben. Darum ist in der Aufgabe auch explizit nach einer Struktur gefragt! (Die
Begründung bestünde dann darin den Wahrheitswert der Formeln bzgl. dieser Struktur zu
ermitteln. Da sollte dann einmal 1 und einmal 0 rauskommen.)

Es ist hier also nötig eine Struktur anzugeben und dann diese dazu zu benutzen für beide
Formeln den Wahrheitswert zu ermitteln. Guckt euch dazu nochmal die Aufgaben 6.5 und
6.6 von den diesjährigen Aufgabenzetteln an.

Zum finden einer geeigneten Struktur hilft einem ein intuitives Herangehen wie Wulf das
demonstriert hat. Da kann man aber auch sehen, wie schnell man mit seiner Intution in
die Irre laufen kann (und darum sollte man seine Intution mit dem "Formalapparat" dann
auch überprüfen!). Das Problem bei Wulfs Beispiel ist nämlich, dass er sowohl Menschen
als auch Geschlechter braucht. Das Universum müsste also beides enthalten. Wenn man dann
P aber so definiert, wie von Wulf beabsichtigt, dann werden z.B. die Tupel (m,m) und (m,w)
(m steht für männlich, w für weiblich) nicht in I(P) enthalten sein - und dann wird die Struktur
weder F noch G zu wahr auswerten, ist also keine geeignete Struktur, um zu zeigen, dass
die Formeln nicht äquivalent sind.

Also zusammengefasst: Guckt euch nochmal 6.5 und 6.6 an und dann probiert das so (formal)
zu machen wie dort.

Fröhliche Grüße,
Frank :)

Hallo. Ich verstehe folgende Frage in der Probeklausur  (Aufgabe 2) nicht, aber würde es gerne vestehen:

"Wofür ist im Allgemeinen die Bedingung, dass die Formeln keine Aussagensymbole
gemein haben, nötig? Was kann sonst passieren?"

Kann mir jemand helfen? Vielen Dank im Voraus :)

lg Eric

In der Aufgabenstellung ist gegeben, dass die Formeln F, G, usw. keine Aussagensymbole
gemein haben. Unter dieser Bedingung (!) soll man angeben ob die dann folgenden Aussagen
gelten oder nicht.

Die Frage ist dann, ob die Aussagen auch immer gelten, wenn man die Bedingung, dass F,
G, usw. keine Aussagensymbole gemein haben, fallen lässt? (Mit "im Allgemeinen" ist hier
gemeint, ob man sich sonst Sachen vorstellen kann (ähnliche Fragen), bei denen das eine
Rolle spielt.) Die Frage ist also, ob es Aussagen gibt, die nur dann richtig sind, wenn man
nutzt, dass F, G, usw. keine Aussagesymbole gemein haben. (Man probiere z.B. mal eine
Tautologie zu konstruieren, die nur dann eine ist, wenn F und G keine Aussagensymbole
gemein haben, dann aber keine mehr ist, wenn F und G Aussagensymbole gemein haben
können.)

Frank :)

Ich habe eine Aufgabe , es war L8 = {w € {0,1}*| v € {0,1}* : w = 0v10} und konstruiert man für jede der folgenden Sprachen einen DFA, der die Sprache akzeptiert.
               0                          1                           0
(q0) ————-> (q1) ————–> (q2) <=======> ((q3))
                              0                           1          1                0

Ist es richtig ? wenn es nicht richtig ist, bitte erklär mir, wie ich wieder richtig schreiben kann. Danke

Problem bei Wulfs Beispiel

Das kommt davon, wenn man sich seit Jahren nicht mit Prädikatenlogik beschäftigt hat… Wie wäre dann KindVon(a, b) = a ist Kind von b?

Ist es richtig ?

Dein Automat ist leider kaum zu lesen, kannst du das nicht grafisch machen?
Wenn du vier Zustände q0..q3 hast (die reichen hier tatsächlich), muss der Automat wieder in den Zustand q1 springen können; ansonsten kannst du nicht sicherstellen, dass 01 am Ende steht.
Lösungsstrategie, die manchmal (aber nicht immer!) funktioniert: erstmal einen Automaten für das minimale Wort (hier: 010) bauen, dann zusätzliche Kanten einfügen.

Ich habe eine Frage an diese Aufgabe :

[IMG]http://ca4.upanh.com/14.288.18514279.mQB0/bildschirmfoto20101006um005145.png[/IMG]

bitte erklär mir, wie ich diese Aufgabe lösen kann . Vielen Dank

Beweis über Wahrheitstafel? Das sind wirklich absolute Basics.

danke für deine Hilfe . Ich habe schon diese Aufgabe bei Wahrheitstafel erledigt .
Außerdem habe ich noch Frage an diese Aufgabe

[IMG]http://ca4.upanh.com/14.288.18514455.Xev0/bildschirmfoto20101006um015507.png[/IMG]

ich habe nicht verstanden,wie ich mit ',' in dieser Aufgabe umwandeln kann . Bitte hilf mir. Danke ^n :D

Das Komma hat da keine grössere Bedeutung.

Definition der Inferenzregeln und der Korrektheit von Inferenzregeln in
Kapitel 6 (?) nochmal angucken. Dann (weil man's dazu braucht) die
Definition von Folgerbarkeit (Kapitel 5?).

Eine ähnliche Aufgabe war auch bei den diesjährigen Übungszetteln dran.
Da also auch einfach nochmal gucken.

Frank :)

Hallo Leute,
ich hoffe, es ist noch nicht zu spät für folgende Frage:

Woher weiß ich, ob ich bei der Skolemisierung eine Skolemkonstanste oder eine Skolemfunktion einsetze?

Danke
Gruß
Daniel

danke für deine Hilfe . Ich habe schon diese Aufgabe bei Wahrheitstafel erledigt .
Außerdem habe ich noch Frage an diese Aufgabe

[IMG]http://ca4.upanh.com/14.288.18514455.Xev0/bildschirmfoto20101006um015507.png[/IMG]

ich habe nicht verstanden,wie ich mit ',' in dieser Aufgabe umwandeln kann . Bitte hilf mir. Danke ^n :D

Ich würde auch gerne zu diesem Thema wissen, ob es nicht einfach ausreicht zu zeigen, dass bei der Wahrheitstafel bei allen Formelmengen eine 1 herauskommt, sodass die Inferenz dann korrekt ist.

@Daniel
Du ersetzt grundsätzlich immer mit einer Skolemfunktion. Eine Skolemkonstante ist nichts anderes als eine nullstellige Funktion. Die Stelligkeit der Skolemfunktion hängt davon ab, wieviele Allquantoren vor dem zu ersetzenden Existenzquantor stehen.

Ich würde auch gerne zu diesem Thema wissen, ob es nicht einfach ausreicht zu zeigen, dass bei der Wahrheitstafel bei allen Formelmengen eine 1 herauskommt, sodass die Inferenz dann korrekt ist.

Ja, man kann das per Wahrheitstafel machen.

ExAy(…….) x kann durch irgendeine Konstante ersetzt werden, da es nicht von einem Allquantor "abhängig" ist.

ExAyEz(…..) z ist vom Quantor Ay abhängig daher musst du überall wo z auftritt z.B. durch f(y) ersetzen.

danke für deine Hilfe . Ich habe schon diese Aufgabe bei Wahrheitstafel erledigt .
Außerdem habe ich noch Frage an diese Aufgabe

[IMG]http://ca4.upanh.com/14.288.18514455.Xev0/bildschirmfoto20101006um015507.png[/IMG]

ich habe nicht verstanden,wie ich mit ',' in dieser Aufgabe umwandeln kann . Bitte hilf mir. Danke ^n :D

ich habe für Teil 2a versucht , wenn A(A) = 1 und A(B) = A(C) = 1 und dann die Inferzregel ist korrekt . Is es richtige Lösung ?

Ein Belegung A dass Modell für die Prämisse (obere Teil) ist und Konklusion aus der Prämisse folgt, müsste diese Belegung auch Modell für die Konklusion sein (das Untere).

Hey Leute,

wenn ein Kellerautomat ein Wort mit Endzustand akzeptiert, muss das Wort dann am Ende komplett gelesen worden sein oder reicht es, wenn er auf dem Weg einmal den Endzustand durchlaufen hat?

Danke

2a) würde ich sagen A=B=C= 1 ist ein Modell für die Prämisse als auch für die Konklusion.  Somit ist die Regel korrekt.
2b) Es gibt 2 Belegungen die Modelle für die Prämisse sind, jedoch nicht für die Konklusion (A=0,B=1,C=1)(A=1,B=0,C=0) somit denke ich dass man daraus schlussfolgern kann dass die Regel nicht korrekt ist.

Ich denke dass der akzeptierende Zustand erreicht werden muss. Leerer Keller ist nicht zwingend erforderlich… Oder doch?

nein, ich glaube, ihr habt mich falsch verstanden (oder ich habe mich falsch ausgedrückt)

wenn ich zb das wort abbbbbab einlesen möchte und er erreicht, nachdem er abb eingelesen hat, den endzustand, akzeptiert er dann "abbbbbab"?
oder muss er am ende von abbbbbab im endzustand sein, damit er das wort akzeptiert?

2a) würde ich sagen A=B=C= 1 ist ein Modell für die Prämisse als auch für die Konklusion.  Somit ist die Regel korrekt.
2b) Es gibt 2 Belegungen die Modelle für die Prämisse sind, jedoch nicht für die Konklusion (A=0,B=1,C=1)(A=1,B=0,C=0) somit denke ich dass man daraus schlussfolgern kann dass die Regel nicht korrekt ist.

Beides richtig.

Ich denke dass der akzeptierende Zustand erreicht werden muss. Leerer Keller ist nicht zwingend erforderlich…

Stimmt auch.

wenn ich zb das wort abbbbbab einlesen möchte und er erreicht, nachdem er abb eingelesen hat, den endzustand, akzeptiert er dann "abbbbbab"?
oder muss er am ende von abbbbbab im endzustand sein, damit er das wort akzeptiert?

Letzteres.

Kann mir jemand eine Struktur verraten die beweist das diese beiden Formeln nicht äquivalent sind?
[latex] F= \forall x (P(x) \vee Q(x)), G= \forall x P(x) \vee \forall x Q(x) [/latex]

U = natürliche Zahlen
I(P) = ist gerade
I(Q) = ist ungerade

Exakter wäre, wenn ihr hier sowas macht wie

I(P) = {x | x ist gerade}

schliesslich soll das ja eine Menge sein ;-)

Frank :)

Die Klausur war doch heute, oder ?

Kann mal jemand ein wenig was von den Aufgaben ( auch für die Nachwelt ) kundtun ?
Danke !

Hallo zusammen,
wurden die Klausurthemen in der letzten FGI2-Vorlesung etwas eingegrenzt?