 Thema: Wie funktioniert primitive Rekursion? |
|
|
Meine Frage:
Guten Tag zusammen,
ich bin Informatikstudent und beschäftige mich derzeit mit derBerechenbarkeit. Ein Thema dieser Berechenbarkeit ist die primitive Rekursion. Dabei hab ich aber ein paar Probleme.
Ich möchte eine Funktion min(y,x) = {1. y, falls y <= x oder 2. x, sonst} (Funktion hat logischerweise 2 Fälle) in primitiv rekursiver Schreibweise darstellen und weiß nicht so recht wie ich das machen soll.
Könnte mir da jemand helfen?
Meine Ideen:
Die primitive Rekursion ist wie folgt induktiv definiert:
Basisfunktionen:
1. Konstante Funktionen sind Prim-Rek.
2. Alle Projektionen sind Prim-Rek.
3. Die Nachfolgerfunktion ist Prim-Rek.
Abschlusseigenschaften:
4. Komposition
5. Primitive Rekursion
Ich soll zeigen das die min-Funktion primitiv-rekursiv ist, also versucht man diese primitiv-rekursiv darzustellen oder man gibt ein LOOP-Programm an. Die Klasse der LOOP-Programme ist ja identisch zu der Klasse der primitiv-rekursiven Funktionen. Aber ein LOOP-Programm ist in dieser Aufgabe nicht erwünscht. Nur ein Beweis über einen primitiv-rekursiven Ausdruck und da hakt es halt bei mir 
|
|
| Thema: Kompaktheitssatz |
|
|
Meine Frage:
Hi Leute,
lerne gerade TI Logik und hänge ein wenig bei den Beweisen mit dem Kompaktheissatz/Endlichkeitssatz. Die Definition des Satzes besagt, dass wenn man eine Formelmenge F mit unendlich vielen Formeln (F1, F2, ...) besitzt und diese erfüllbar ist, so ist auch jede endliche Teilmenge von F erfüllbar. Bitte korrigiere mich jemand wenn ich hier Mist geschrieben habe! Ich lerne noch und will mich verbessern..
Zur Übung habe ich eine Übungsaufgabe, die das Verständnis von Beweisen mit dem Kompaktheitssatz fördern soll (denke ich mal):
Angenommen,????AL. Zeige, dass gilt: Wenn ? erfüllbar ist, dann ist auch ? erfüllbar.
Wäre cool, wenn mir da jemand helfen könnte :-)
Meine Ideen:
Wie gehe ich da genau vor? Gibt es da irgendwie ein Schema, dass man immer anwenden kann? "Hin- und Rückrichtungs-Beweise" habe ich schon zig gesehen, aber bekomme keinen so wirklich aufs Papier...
|
|
|
