Hallo. Da nicht jeder zum Tutorium "darf" mache ich mal einen thread auf, vielleicht ist ja jemand so nett und beantwortet hier ab un an Fragen.

Meine erste Frage ist wohl sehr simpel, aber ich komme irgendwie nicht drauf:

Aufgabenstellung: Geben sie alle möglichen Resolventen von F an.
Ich weiss wie man diese bestimmt, aber woher weiss ich wann bzw ob ich wirklich fertig bin und nicht doch irgendwie eine vergessen habe?

Du musst alle Literale mit allen durchzuprobieren und schauen, ob die du schon hast. Man kann sich ja die Literale durchnummerieren und sich dann da jeweils kleine Zahlen dran schreiben, womit man es schon probiert hat, falls dir da der Überblick fehlt.

Etwas einfacher kann es werden, wenn man sich auf N- oder P-Resolution beschränkt, dort hat man in der Regel weniger Möglichkeiten zu resolvieren, bleibt jedoch das gleiche Ergebnis, was die Widerlegbarkeit angeht.

Bei der aussagenlogischen Resolution handelt es sich um ein NP-vollständiges Problem, das wird also ganz unlustig, wenn du viele Literale hast.

/edit (zum vorigen)
Meinte natürlich Klauseln. Sollte mehr schlafen -.-

/nocheinedit
Bei den Klauseln natürlich auch aufpassen, dass du alle Literale erwischt, also bei der Durchnummerierung auch aufschreiben, welches Literal man nun eigentlich genommen hat. Bei {nA, nB} und {A, B} beispielsweise bekommst du ja zwei Resolventen: {nA, A} und {nB, B}.

Ich schreib nochmal in Ruhe später was, wenn ich wieder richtig fit bin.

Habe ein Problem bei der Prädikatenlogik. Und zwar verstehe ich die ganze Variablen-Umbenennungsgeschichte nicht, wenn ich eine Formel F in die Pränexform bringen soll.

Wie darf ich denn da etwas umbenennen? Für mich sieht es in den Beispielen immer nach "frei Schnauze" aus, aber ich kann doch nicht einfach umbenennen wie ich lustig bin, das verändert doch sicherlich die Semantik der Formel????

Wäre riesig, wenn das jemand erklären könnte (auch wenn ich nicht daran glaube :( )

So, mal etwas ausführlicher an einem Beispiel (die Frage, wann man keine weiteren Resolventen mehr hat):
{{A}, {¬C}, {¬A, B}, {¬A, D}, {¬A, ¬D, C}} soll auf Erfüllbarkeit geprüft werden.

Als erstes einfach mal alle Klauseln durchnummerieren:
{{A}_1, {¬C}_2, {¬A, B}_3, {¬A, D}_4, {¬A, ¬D, C}_5}
Nun systematisch durchgehen:
1) Erste Klausel mit allen anderen Klauseln literalweise vergleichen und schauen, was sich resolvieren lässt. Dieses dann resolvieren und den Resolventen auch wieder Nummern geben. Dann mit der zweiten Klausel etc.

Mal ganz kleinschrittig:
Erster Schritt:
1 Klausel:
- 2. Klausel: gibt nichts
- 3. Klausel: A -> {B}_6  (wenn noch weitere Literale außer A gingen würden, dann z.B. auch noch {B}_7, halt alle Literale da einmal durchgehen)
- 4. Klausel: A -> {D}_7
- 5. Klausel: A -> {¬D, C}_8
2. Klausel:
- 1. Klausel bereits erledigt
- 3. Klausel: gibt nichts
- 4. Klausel: gibt nichts
- 5. Klausel: C -> {¬A, ¬D}_9
3. Klausel:
- Klauseln 1 und 2 bereits erledigt
- 4. Klausel: gibt nichts
- 5. Klausel: gibt nichts
4. Klausel
- Klauseln 1-3 hat man bereits erledigt
- 5. Klausel: D -> {¬A, C}_10
5. Klausel:
- Wurde bereits mit allen verglichen

Wie man sieht, fallen jeweils die Klauseln davor zum Vergleichen weg. Also bei der dritten Klausel braucht man 1 und 2 nicht mehr zu betrachten, bei der vierten 1-3 nicht mehr usw.

Zweiter Schritt:
1. Klausel:
- 1-5 schon erledigt
- 6. Klausel: gibt nichts
- 7. Klausel: gibt nichts
- 8. Klausel: gibt nichts
- 9. Klausel: A -> {¬D}_11
- 10. Klausel: A -> {C}_12
2. Klausel:
- 1-5 schon erledigt
- 6. Klausel: gibt nichts
- 7. Klausel: gibt nichts
- 8. Klausel: C -> {¬D} (bereits vorhanden)
- 9. Klausel: gibt nichts
- 10. Klausel: C -> {¬A}_13
3. Klausel:
[…]
9. Klausel:
- 1-8 bereits erledigt
- 10. Klausel: […]
[…]
10. Klausel:
- wurde bereits mit allen verglichen

Dritter Schritt:
1. Klausel:
- 1-10 bereits erledigt
- 11. Klausel: […]
- 12. Klausel: […]
- 13. Klausel: […]
2. Klausel:
- 1-10 bereits erledigt
- 11. Klausel: […]
- 12. Klausel: […]
- 13. Klausel: […]
[…]
13. Klausel:
- wurde bereits mit allen verglichen

Wenn du dann in einem Schritt keine neuen mehr hinzu bekommst, kannst du dir sicher sein, dass du keine vergessen hast, solange du das in der Form systematisch durchgegangen bist. Ich hoffe mal das Muster ist ersichtlich. Es sieht hier zwar ziemlich viel aus, geht aber relativ schnell, da man sich die, wo man nichts gefunden hat, in der Regel nicht mit aufschreibt.

Zur Prädikatenlogik: Hast du da mal konkret ein Beispiel, wo du es als "frei Schnauze" siehst?

Heh, kaum poste ich die Frage komme ich schon selbst auf die Antwort.
Die Beschreibungen im Skript und beim Schöning mögen exakt und korrekt sein, erklären können sie nur so unheimlich schlecht. Ich finde etwas auch für  Laien verständlich rüberzubringen sollte in akademischen Kreisen einen höheren Stellenwert bekommen, es zeugt mMn nicht minder von Intelligenz als die mathematisch korrekten Aufschriften.

Hier meine Version, vielleicht hilft es ja jemanden(bzw ihr könnt mich korrigieren, falls ich doch kacke gebaut habe):

Es geht bei der Pränexform darum die Quantoren, die in der Formel vorhanden bzw in sie "verwoben" sind ganz nach außen(links) zu befördern. Wie man das erreicht sollte klar sein (Äquivalenszregeln).

Nun kann es passieren, dass ein Quantor in einem Teil der Formel eine Variable bindet, die in einem anderen Teil der Formel frei(ungebunden) vorkommt. Schiebt man diesen Quantor jetzt ganz nach links und erweitert seinen Scopus damit auf die ganze Formel, würde man diese freie Variabel ja plötzlich in eine gebundene verwandeln.

Beispiel (A = Allquantor, E = Existenzquantor)

F = P(f(x),z) UND AxG(g(x),y)

Im ersten Teil der Formel  (P(f(x),z) ) sieht man, dass ein x frei/ungebunden (also ohne Quantor) vorkommt und im zweiten Teil durch den Allquantor (Ax) gebunden wird. Befördert man jetzt diesen Allquantor nach vorne ohne das freie x umzubenennen, bindet man es plötzlich auch zum Allquantor, der eigentlich nur für das zweite x bestimmt ist.

Um das zu verhindert muss man dieses freie x eben umbenennen und zwar in eine Variable, die von keinem anderen Quantor verwendet wird (weil man das Problem ansonsten ja beim nächsten Quantor hätte).

Hoffe das ist richtig und verständlich.

Danke für die Resolventenerklärung! Das hilft.

Hey,
Wie wichtig sind eigentlich korrektheit und vollständigkeit? :|
Die sind doch wichtiger (also in der Aussagenlogik) oder?
Kann das vielleicht nochmal jemand erklären?
Auch wie man das anwendet, weil ich seh nicht so richtig den Sinn darin.
Schieb ich auf jedenfall erstmal auf und lern den Rest, also wenn wer ne gute Erklärung dazu hat, wäre es voll super :)

Korrektheit:
Ein Kalkül ist korrekt, wenn jede durch durch diesen Kalkül als unerfüllbar erkannte Formel
auch wirklich unerfüllbar ist.

Zum Beispiel sagt dir der Resolutionskalkül ja:
Wenn mit meinen Regeln aus einer Formelmenge die leere Menge ableiten kannst, dann ist die Formel unerfüllbar.
Die Korrektheit des Resolutionskalküls sagt dir jetzt, dass diese Behauptung auch stimmt (d.h. du kannst mit dem Resolutionskalkül aus keiner erfüllbaren Formel die leere MEnge ableiten).

Vollständigkeit:
Ein Kalkül ist vollständig, wenn jede unerfüllbare Formel von diesem Kalkül auch als vollständing erkannt wird.

Das heisst z.B. für den Resolutionskalkül (welcher ja vollständig ist), dass du mit ihm aus jeder unerfüllbaren Menge
irgendwie die leere Menge ableiten kannst.


Vollständigkeit und Korrektheit ist also nichts was man direkt anwenden kann, sondern es
sind einfach Eigenschaften von Kalkülen (Rechenregeln).


Ich hoffe ich konnte das ein wenig deutlich machen :)

Viel Erfolg!
Benjamin

Vollständigkeit:
Ein Kalkül ist vollständig, wenn jede unerfüllbare Formel von diesem Kalkül auch als unvollständig erkannt wird.

unerfüllbar war hier sicher gemeint.

Stimmt, "unerfüllbar" wäre natürlich richtig gewesen.
Das ist genau die Art Fehler, die ich wohl nie los werd..

Benjamin

Bah. Wegen dem kack STE Teil ist mein Arbeitsspeicher durchgeglüht und beim FGI Lernen wirft mein Kopf ständig OutOfMemoryExceptions :/ .

Hallo
Hab da auch mal eine Frage zur Resolution. Ich weiß zwar wie lineare, P-Resolution und N-Resolution angewendet werden, aber wo liegen die Vor-/ bzw. Nachteile der einzelnen Resolutionsmöglichkeiten. Geht das ein oder andere schneller? Wenn ja in welchen Fällen?
Was nimmt man am besten, wenn es nicht vorgegeben ist?

Vielen Dank schonmal vorab!

Die Resolutiosfrage würde mich auch interessieren.

Aber eine vllcht etwas simplere Frage; Wie entstehen die Übergänge des Potenzautomaten? Dass die Zustände aus der Potenzmenge der alten Zustände besteht ist mir klar, aber wie verfährt man bei der Setzung und Beschriftung der Pfeile?

Du musst dir darüber klar werden in welchen zuständen du dich befinden kannst!
wenn du einen automaten hast mit den zuständen z_1 z_2 z_3
und den überführungsfunktion
delta(z_1,a)=z_1
delta(z_1,(a,b))=z_2
delta(z_2,b) = z_3

und es wird als erstes ein a eingeben, dann befindest du dich in zustand z_1z_2, da du sowohl in z_1, als auch in z_2 sein kannst! wird dann ein b eingegeben (also gesamtwort bisher: ab) kannst du dich in Zustand z_2 und z_3 befinden, also z_2z_3, aber nicht mehr in z_1, da das b auf jedenfall weg führt von z_1! So musst du den Automaten durchgehen, bis du alle Pfeile hast! Ist nen bisschen übung..

Ergänzung: delta(z_1,(a,b))=z_2… hier soll (a,b) heißen, dass sowohl bei a, als auch bei b der Übergang zu z_2 statt findet! war faul… weiß, dass man das so net schreiben sollte…

Sweet, danke. Ist ja ganz einfach.

Wie ist die Erfahrung der altsemestler kommen gleiche Fragen in den Klausuren vom vorjahr  dran ?

Ja, wenn man erstmal in dem Skript geblickt hat, was der da macht, ist es ganz einfach mit dem Potenzautomat!

Hab auch noch ne nette Frage, sicher ganz einfach:
# ist der Kellerboden!
bei einem Übergang im Kellerautomaten: a,#|# wird dann die # mit der # überschrieben?
andere Beispiele, damit klar wird was ich mein:
a,#|a# (wird # mit a# überschrieben?)
a,a|aa (wieder die gleiche frage ;))

Ich hab nämlich gedacht, ich hätts verstanden, bis ich in Kapitel 16 die Beispielrechnung durchgegangen bin und dort passiert der übergang von z nach z' sehr komisch.

http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe09/05-Pumping-PDA-2.pdf

Folie 12

Ja ist genauso wie du sagst.
a,#|a# = a wird aus der eingabe gelesen, # vom Keller (und gelöscht). Dabei wird a# auf den Keller gelegt (oben drauf, d.h. unten ist # und dadrüber a).

Passt auch mit Folie 12 zusammen.

er müsste doch nach dem übergang nur aa im keller haben, aber in der beispielrechnung hat er aaa im keller… weil er geht ja über durch: a,a|a und hat bis dahin 2 a im keller… er liest das letzte a und schreibt auch wieder nur ein a in den keller… wenn er aber um 1 a erhöhen wollte, müsste er doch 2 a schreiben oder?

auf folie 12 sind 2 beispiele.. das erste ist ohne übergang und da blockiert halt iwann der PDA, weil keine a's mehr im wort sind zum lesen.. da hat er also nur 3 mal die schleife an z simuliert…

die richtige rechnung steht dann bei eine andere rechnung.. und da hat er, wie du auch schon meintest nur 2 A's im keller bei dem übergang

hallo,

was meint ihr, kommt automaten Minimierung in der Klausur dran?

und nochwas:
ich habe immer noch probleme mit dem Pumping Lemma. Und zwar bei der Wahl des Wortes, damit die Fallunterscheidung möglichst glatt verläuft und ich ausserdem trotzdem alles richtig mache. Gibt es da Tricks?

gruß,
Arthur

Noch eine Frage zur Folgerbarkeit:
F |= Kontradiktion
was bedeutet das für F? Meiner Meinung nach ist F nicht zwingend eine Kontradiktion, oder?

Gruß,
Arthur

Doch, F ist dann eine Kontradiktion!
Folgern heißt ja, dass F ein Modell hat, das 1 ist und die Folgerung das gleiche modell hat, dass 1 ist.
Eine Kontradiktion hat nur 0 in der wahrheitstafel. Daher hat eine Folgerung kein Modell, also hat auch F kein Modell!
Eine Folgerung kann mehr modelle von F haben, jedoch nicht weniger!

ah na so macht einiges mehr sinn :D
ich hatte die Beziehung genau andersrum im Kopf. Danke dir

Und schon wieder ich :)
Ich verstehe wie ich Kalküle und Ableitungen verwende. Allerdings ist mir nicht ganz klar wozu das getan wird. Wozu brauche ich eine Ableitung? Mir ist klar, dass es in die Richtung der Resolution geht. Ist das der einzige Zweck? :)

gruß,
Arthur

mit kalkülen kannst du folgbarkeit nachweisen

Meint ihr wir müssen die ganzen Inferenzregeln und Hilbertaxiome auswendig wissen?

unser Übungsgruppenleiter meinte: eher nicht.

also hilbert denk ich eigentl auch nicht.. inferenzregeln vllt schon die wichtigesten.. im tutorium wurde ja gesagt, das habel nix hinten anhängt.. und ohne die inferenzregeln könnten klauseln ja gar nicht dran kommen

und das wäre ja zu schade ;)

Jetzt ist die Frage was "die wichtigsten" denn sind? MP ist klar, was noch?

MP, KL und DS

Sehe ich das richtig, dass ein NFA im Gegensatz zum DFA mehrere Startzustände haben kann? o_O

Warum?

weils ers kann

Sehe ich das richtig, dass ein NFA im Gegensatz zum DFA mehrere Startzustände haben kann? o_O

Warum?

Nehmen wir an, ein NFA könnte nur einen Startzustand x haben, Du würdest aber gerne mehrere Startzustände a, b, c haben. Dann könntest Du ja einfach drei epsilon-Übergänge von x nach a, b, c definieren und hättest damit drei Startzustände simuliert.

Wenn man es also indirekt simulieren kann, warum sollte man es dann nicht auch direkt zulassen?

Das wäre aber doch dann ein eFA!
NFA != eFA

kannst ihn ja ε-frei machen…

Ist er e-frei gemacht (zum NFA) kann die besagte "Simulation" nicht durchgeführt werden da keine Epsilons vorhanden sind!

ich denke er meinte nach der Simulation ;)
erst die Simulation mit den e's und dann e frei machen, dann hat man mehrere Startzustände

Auf welcher Grundlage hätte man dann mehrere Startzustände? Der Verfahren das mir bekannt ist sieht das bei der Umwandlung nicht vor. Da gilt "nur" dass alles, was vom Endzustand mit einem Epsilon erreicht werden kann auch ein Endzustand wird. Was vom Startzustand über ein Epsilon erreicht wird wird nicht ebenfalls zum Startzustand oder irre ich mich?

*Das Verfahren

Sind eigentlich irgendwelche Hilfsmittel zugelassen?

Iversonsches Prädikat:
Warum ist [3*2=6]=1 aber [PI=3,14]=0?
M ist ja nicht definiert! Ist M in dem fall N? Iwie blick ich das Prädikat nicht so ganz :|

Sind eigentlich irgendwelche Hilfsmittel zugelassen?

Neben Brille, Kugelschreiber oder Füller sind keinerlei Hilfsmittel erlaubt!
Insbesondere sind NICHT zugelassen: Bücher, Mitschriften aller Art oder eigenes Schreibpapier!
Mit Bleistift oder Rotstift geschriebene Antworten sind nicht zulässig und werden nicht gewertet! Bitte benutzen Sie also Kugelschreiber oder Tinte.

Aus der Mail die wir zur FGI Klausur bekommen haben.
Gefreut hat mich das mit der Brille (: sonst müsste ich raten was auf dem Zettel steht.

Auf welcher Grundlage hätte man dann mehrere Startzustände? Der Verfahren das mir bekannt ist sieht das bei der Umwandlung nicht vor. Da gilt "nur" dass alles, was vom Endzustand mit einem Epsilon erreicht werden kann auch ein Endzustand wird. Was vom Startzustand über ein Epsilon erreicht wird wird nicht ebenfalls zum Startzustand oder irre ich mich?

Selbstverständlich hat man dann nicht mehrere Startzustände, sondern einen zu einem NFA mit mehreren Startzuständen equivalenten NFA.

Nochmal die Idee:
- Mehrere Startzustände simulieren mit e-Übergängen (-> e-NFA)
- Automat e-frei machen (-> NFA)

Iversonsches Prädikat:
Warum ist [3*2=6]=1 aber [PI=3,14]=0?
M ist ja nicht definiert! Ist M in dem fall N? Iwie blick ich das Prädikat nicht so ganz :|

M? N? Wovon sprichst du? Iverson siehe
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe09/08-TM-LBA-2.pdf (Seite 22).

Pi ist nicht 3,14, also ist [Pi = 3,14] falsch.

Wir werden alle sterben!

-> Wir werden alle sterben!

… und das unabhängig davon, ob man die FGI1-Klausur morgen besteht oder oder nicht. Also locker bleiben!

Nur wer besteht darf weiterleben.

werd die klausur niemals schaffen -.- das rs tut war irgendwie aufschlussreicher für die klausur…

und wer dreht jetzt da bitteschön durch?!…

Nur wer besteht darf weiterleben.

So will es das Gesetz!


@Durchdrehen
Es schreiben definitiv >= 2 Leute, also kein Einzelner der Gedanklich am abnippeln ist.
Mehrere Leute, die gedanklich am abnippeln sind! :D

Sind eigentlich irgendwelche Hilfsmittel zugelassen?

In STiNE steht unter den Nachrichten bei der Veranstaltung dieses:

Liebe Teilnehmer am Modul MODUL IP 8 FORMALE GRUNDLAGEN DER INFORMATIK I (FGI I) - SOSEM 2009, nachfolgend finden Sie einige organisatorische Hinweise zur (Modulabschluss-)Klausur am 27.7.

Die Klausur soll um 9:30 beginnen.
Bitte finden Sie sich daher VON 9:00 BIS 9:15 Uhr am Audimax I ein.
Die Klausur dauert 120 Minuten und wird folglich um 11:30 beendet.

Neben Brille, Kugelschreiber oder Füller sind keinerlei Hilfsmittel erlaubt!
Insbesondere sind NICHT zugelassen: Bücher, Mitschriften aller Art oder eigenes Schreibpapier!
Mit Bleistift oder Rotstift geschriebene Antworten sind nicht zulässig und werden nicht gewertet! Bitte benutzen Sie also Kugelschreiber oder Tinte.

Bringen Sie einen Lichtbildausweis (Personalausweis, Reisepass) sowie einen Studierendenausweis mit. Diese werden im Laufe der Klausur kontrolliert.

Legen sie Ihren Studentenausweis und einen Lichtbildausweis sichtbar auf den Tisch. Handys bleiben während der Klausur ausgeschaltet und das Fotografieren von Klausurbögen ist verboten!

Das Benutzen nicht zugelassener Hilfsmittel (z.B. mitgebrachtes Schreibpapier, Hefte, Zettel, Bücher, Vorlesungsskripte, Folienkopien oder daraus kopierte oder abgeschriebene Teile, wie auch Fotoapparate, elektronische Geräte, Handys, PDAs oder Computer) wird als Täuschungsversuch gewertet und entsprechend geahndet!

RECHTSMITTELBELEHRUNG:
Gegen die Bewertung dieser Prüfungsleistung kann innerhalb eines Monats nach ihrer Bekanntgabe Widerspruch erhoben werden. In diesem Zeitraum kann die Bewertung der Klausur eingesehen werden. Der Widerspruch ist schriftlich oder zur Niederschrift bei der bzw. dem Vorsitzenden des für das Hauptfach zuständigen Prüfungsausschusses einzulegen. Es wird darauf hingewiesen, dass ein erfolgloses Widerspruchsverfahren kostenpflichtig ist.

Muss am  ersten eine  Prüfung in FGI schreiben, habe mich aber voll erkältet, wie mach ich das dann jetzt ?  Ärzliches Gutachten holen und zum Prof schicken?   Gilt die Prüfung dann auch als durchgefallen(zweiter Fehlversuch)?

Muss am  ersten eine  Prüfung in FGI schreiben, habe mich aber voll erkältet, wie mach ich das dann jetzt ?  Ärzliches Gutachten holen und zum Prof schicken?   Gilt die Prüfung dann auch als durchgefallen(zweiter Fehlversuch)?

Sieh hier: https://www.fb18.de/mybb/showthread.php?tid=10750&pid=108008#pid108008