ggT in Prädikatenlogik

[Hardwaretoaster]

Gegegeben sei:
P(x,y), x teilt y, beides natürliche Zahlen
Mit diesem Prädikat den ggT definieren.
E als Existenzquantor
UND als Konjunktion
- als Negation

Mein Ansatz:
Ex(P(x,y) UND P(x,z)) UND -Ew(P(w,y) UND P(w,z) UND (w>x))

Ist das komplett? Gibt's da Verfahren, mit denen ich prüfen kann, ob es komplett ist?

[MadMax@]

Die Prädikatenlogik ist nicht entscheidbar also gibts kein Verfahren um das zu überprüfen.

[Hardwaretoaster]

Ja, nur Aussagen sind entscheidbar. Nur wenn ich eine Prädikatenlogische Formel aufstelle, muss ich ja irgendwie rausfinden, ob ich das, was ich da mache richtig mache?

[Trap]

Ich versteh deine Formel nicht. Die ist doch immer wahr, oder? "true" wäre eine einfachere Version die Formel hinzuschreiben.

[Hardwaretoaster]

Immer wahr? Aber nur in der Menge der reelllen Zahlen, oder, es sind aber nur natürliche zugelassen.
Ich probiere es mal in Worten:
Es gibt ein x das y und z teilt (ganzzahlig) und kein w das y und z teilt und größer ist als x.

Desshalb frage ich ja, ob es passt;)

[Trap]

Ich kenne die Aufgabenstellung nicht, aber so wie du die Formel geschrieben hast ergibt sich das Ergebnis von ggT(y,z) aus der Belegung der gebundenen Variable x und die Formel ist immer wahr, da ggT(y,z) für alle y, z definiert ist.

Man kann die Formel stattdessen auch mit ungebundenem x schreiben, so dass sie nur wahr ist, wenn x=ggT(y,z) gilt.

Herausfinden ob die Formel vollständig ist könnte man eventuell mit einem Induktionsbeweis.

[Hardwaretoaster]

Ich kenne die Aufgabenstellung nicht, aber so wie du die Formel geschrieben hast ergibt sich das Ergebnis von ggT(y,z) aus der Belegung der gebundenen Variable x und die Formel ist immer wahr, da ggT(y,z) für alle y, z definiert ist.

Man kann die Formel stattdessen auch mit ungebundenem x schreiben, so dass sie nur wahr ist, wenn x=ggT(y,z) gilt.

Herausfinden ob die Formel vollständig ist könnte man eventuell mit einem Induktionsbeweis.

Jetzt steige ich aus, ich soll doch den ggT Definieren.

Mal die Aufgabenstellung wörtlich, vielleicht reden wir auch aneinader vorbei:

"P(x,y) bedeutet: x teilt y, wobei x und y natürliche Zahlen sind. Definieren Sie mit Hilfe der Prädikatenlogik
a) Primzahl (rauskommen soll Ax(P(x,y) -> x=1 v x=y) )
b) den größten gemeinsamen Teiler zweier Zahlen"

[Trap]

Die Aufgabe ist für mich nicht klar. ggT ist eine Funktion die 2 natürliche Zahlen auf eine 3. natürliche Zahl abbildet. Eine Formel kann das nicht, die ergibt wahr oder falsch, aber keine natürliche Zahl.

[Hardwaretoaster]

Also wenn ich das richtig verstehe (so ist's ja auch bei der Primzahl), soll whr zurückgegeben werden, wenn x ggt von y,z, sonst falsch.

[Hardwaretoaster]

Vielleicht darf ich x wirklich nicht binden:
Ayz(P(x,y) UND P(x,z) UND -Ew(P(w,y) UND P(w,z) UND (w>x)))

So vielleicht? Aber so richtig durchsteigen tu ich in dem Thema nicht...

[Trap]

Dann muss x in der Formel frei sein.

Für eine Korrektheitsbeweis deiner Formel müsstest du in einem größeren Logiksystem das auch ggT enthält zeigen:
A.xyz(Prädikatenlogik(formel(x,y,z)=true) <=> x=ggT(y,z))

Vielleicht darf ich x wirklich nicht binden:
Ayz(P(x,y) UND P(x,z) UND -Ew(P(w,y) UND P(w,z) UND (w>x)))
Ich würde x,y und z ungebunden lassen, ob x ggT von y und z ist hängt doch von allen 3 ab. So wie du es jetzt formuliert hast, sagt die Formel ob x ggt von allen möglichen y und z ist. Das ist sicher falsch, kein x ist ggT von allen y und z.

[Novox]

Die Aufgabe ist für mich nicht klar. ggT ist eine Funktion die 2 natürliche Zahlen auf eine 3. natürliche Zahl abbildet. Eine Formel kann das nicht, die ergibt wahr oder falsch, aber keine natürliche Zahl.

Das Prädikat lautet: "x ist GGT von y" "x ist GGT von y UND z". Das ist eine Aussage mit den Variablen x, y und z - also ein Prädikat - und keine Funktion oder Abbildung.


Mein Ansatz:
Ex(P(x,y) UND P(x,z)) UND -Ew(P(w,y) UND P(w,z) UND (w>x))

Ist das komplett?

Hm, zwei Allquantoren fehlen auf jeden Fall: ∀z∀y∃x(...

[Hardwaretoaster]

Das Prädikat lautet: "x ist GGT von y" "x ist GGT von y UND z". Das ist eine Aussage mit den Variablen x, y und z - also ein Prädikat - und keine Funktion oder Abbildung.



Hm, zwei Allquantoren fehlen auf jeden Fall: ∀z∀y∃x(...

Also ∀z∀y∃x((P(x,y) UND P(x,z)) UND -∃w(P(w,y) UND P(w,z) UND (w>x)) ?

[Gast]

Also ∀z∀y∃x((P(x,y) UND P(x,z)) UND -∃w(P(w,y) UND P(w,z) UND (w>x)) ?
Hattet ihr schon das Lamda-Kalkül?
Falls ja, ersetze die beide All-Quantoren durch Lamdas.
Ansonsten könnte man z und y durch ungebundene Variablen ersetzen.
Momentan testest du, ob es für alle z und alle y ein ggT existiert, was immer wahr sein sollte.

[Hardwaretoaster]

Lamda-Kalkül sagt mir noch nicht.

Ungebunden, also die beiden Allquantoren doch wieder weg? (so wie am Anfang)

[Novox]

Lamda-Kalkül sagt mir noch nicht.

Ungebunden, also die beiden Allquantoren doch wieder weg? (so wie am Anfang)

Lambda-Kalkül brauchst Du hier überhaupt nicht. Die Allquantoren hingegen auf jeden Fall, sonst ist y und z undefiniert.

[Trap]

Die Allquantoren hingegen auf jeden Fall, sonst ist y und z undefiniert.
Nein, sie sind dann nicht undefiniert, sondern frei.

[Hardwaretoaster]

Nein, sie sind dann nicht undefiniert, sondern frei.
Ja, so würde ich es wohl auch verstehen, also ich wähle zB y =12 z=18
dann wäre durch den Existenzquantor für x gegeben [...] ggt(5, 12, 18) v ggt(6, 12, 18) v ggt(7,12,18) v [..]

Also FALSCH v WAHR v FALSCH

Oder bin ich da auf dem falschen Dampfer?

[Gast]

Lamda-Kalkül sagt mir noch nicht.
Ok. Das wäre imo eine saubere Lösung gewesen-
Das mit den beideren Allquantoren weglassen war ein Brainfart wegen OPS5... egal.
Für nun das Prädikat GGT richtig zu definieren würde ich aus der Erinnerung raus das so machen:
∀z∀y∀x(GGT(x,y,z) <=> ((P(x,y) UND P(x,z)) UND -∃w(P(w,y) UND P(w,z) UND (w>x))

D.h. das GGT wertet genau dann zu wahr aus, wenn der rechte Teil erfüllt ist.

[ethrandil]

∀z∀y∀x(GGT(x,y,z) <=> ((P(x,y) UND P(x,z)) UND -∃w(P(w,y) UND P(w,z) UND (w>x))
Das sieht auch in meinen Augen richtig aus :-)

[Hardwaretoaster]

Das sieht auch in meinen Augen richtig aus :-)

Bei den drei Allquantoren habe ich noch meine verständnisschwierigkeiten: warum brauche ich die alle?
Bei dem Primzahlbsp ist die Zahl, die getestet werden soll ja auch frei

[ethrandil]

Ich würde mich jetzt einfach mal auf den heiklen Standpunkt stellen, die Aufgabenstellung zu den Primzahlen wurde mit der Musterantwort nicht ganz gelöst.
Man kann in der Prädikatenlogik nicht ohne weiteres Zahlen definieren, sondern nur Formeln über Aussagen und Prädikate aufstellen.

Sehen wir uns das Primzahlbeispiel einfach mal an: "Ax(P(x,y) -> x=1 v x=y)"
Hier wird implizit davon ausgegangen, dass y gewisser Weise als konkret gebundene Variable in die Formel eingesetzt wird. Das ist aber implizit ausgedrückt und nicht in Prädikatenlogik!
Richtiger wäre auch hier die Variante ein Prädikat aufzustellen und es dann in der Prädikatenlogik zu beschreiben: "Ay(PRIM( y) <=> Ax(P(x,y) -> x=1 v x=y))"
Das heißt nichts weiter als das was vorher implizit gemeint war: Jede Zahl y ist Prim (genauer: erfüllt das Prädikat PRIM), wenn 'Ax(P(x,y) -> x=1 v x=y)' wahr ist.

Und ebenso ist es auch mit der Antwort auf die GGT-Aufgabe. Dein erster Beitrag war absolut richtig, wenn man sich auf diese lasche Schreibweise deiner Dozenten einlassen will. Aber generell ist es nicht ganz korrekt in Prädikatenlogik ausgedrückt.

- eth

EDIT:
Ex(P(x,y) UND P(x,z)) UND -Ew(P(w,y) UND P(w,z) UND (w>x))
du hast irgendwie die Variablen komisch benannt und nicht ganz richtig geklammert. Ich würde sagen, wenn ggt(x,y) = z, dann Ez( P(z,x) UND P(z,y) UND -Ew( P(w,x) UND P(w,y) UND (w>z) ) )

[Gast]

Bei den drei Allquantoren habe ich noch meine verständnisschwierigkeiten: warum brauche ich die alle?
Einfach ausgedrückt: Es wird eine Wahrheitstabelle gebaut für alle möglichen Variablenbelegungen. Indem man nun sagt, dass das Prädikat für jede Variablenbelegung exakt das selbe Ergebnis wie der rechte Teil besitzt, kann man es definieren.
(Es gibt irgendein Satz, dass 2 Funktionen identisch sind, wenn sie für jede Variablenbelegung das gleiche Ergebnis liefern.)
Bei dem Primzahlbsp ist die Zahl, die getestet werden soll ja auch frei
Das ist nur in Ordnung, wenn das Ergebnis nicht ein definiertes Prädikat sein soll, sonder nur ein Teilausdruck, den man irgendwo einfügen kann. Normalerweise nutzt man für solche Definitionen Lambda-Ausdrücke, damit auch alle Variablen eindeutig gebunden werden. Dort werden im Prinzip die Argumente des Prädikats als Variablen durch ein vorangestelltes Lambda gebunden. Da ihr das noch nicht hattet, also muss man ein anderes Konstrukt bemühen um keine freie Variablen zu haben.

Wenn ihr freie Variablen benutzen dürft, lass einfach "∀z∀y∃x" weg, da dies alle "Eingabevariablen" sind.

[Hardwaretoaster]

Einfach ausgedrückt: Es wird eine Wahrheitstabelle gebaut für alle möglichen Variablenbelegungen. Indem man nun sagt, dass das Prädikat für jede Variablenbelegung exakt das selbe Ergebnis wie der rechte Teil besitzt, kann man es definieren.
(Es gibt irgendein Satz, dass 2 Funktionen identisch sind, wenn sie für jede Variablenbelegung das gleiche Ergebnis liefern.)

Das ist nur in Ordnung, wenn das Ergebnis nicht ein definiertes Prädikat sein soll, sonder nur ein Teilausdruck, den man irgendwo einfügen kann. Normalerweise nutzt man für solche Definitionen Lambda-Ausdrücke, damit auch alle Variablen eindeutig gebunden werden. Dort werden im Prinzip die Argumente des Prädikats als Variablen durch ein vorangestelltes Lambda gebunden. Da ihr das noch nicht hattet, also muss man ein anderes Konstrukt bemühen um keine freie Variablen zu haben.

Wenn ihr freie Variablen benutzen dürft, lass einfach "∀z∀y∃x" weg, da dies alle "Eingabevariablen" sind.

Gut, danke.
Werde dann morgen mal meinen Dozent wegen Schreibweise löchern.
Die Aufgabe stammt übrigens aus "Einführung in die Mathematik für Informatiker" von Dörfler und Pescek, wie ich eben festestellen musste...
Kap 5 Aufg9c)
Naja, wenigstens habe ich vorher ordentlich drüber nachgedacht...
Die dort vorgeschlagene Lösung geht über "alle w sind kleiner als x anstatt kein w ist größer", sollte aber äquivalent sein,w enn ich richtig denke.

@ethrandil Ok, der Klammerunsgfehler ist mir unterlaufen, dadurch binde ich einmal und einmal nicht, was nicht geht, werde ich in meinen Aufzeichnungen gleich mal anpassen...

[Novox]

Nein, sie sind dann nicht undefiniert, sondern frei.
Ja, das stimmt; mein Fehler.

[Gast]

Formal gesehen geht aus der Aufgabenstellung nicht hervor, dass du das binaere Praedikat "x > w" verwenden darfst;
die genau Bezeichnungs ist, wenn ich mich recht erinner, FO( N, P),
FO steht dabei fuer First-Order (Praedikatenlogik 1.Stufe),
mit dem Universum N (Natuerliche Zahlen) und dem einzigen Praedikat P.

Die Definition fuer den ggT benoetigt allerdings auch keine Ordnungsrelation;
formal ist der ggT definiert durch:

1) der ggT(x,y) ist ein Teiler von x und von y
2) jeder andere Teiler w von x und y teilt auch den ggT(x,y)

Ergibt dann

F := E g. [ P(g,x) /\ P(g,y) /\ A w.[ (P(w,x) /\ P(w,y)) -> P(w,g) ] ].

Implizit ist ja durch die Aufgabenstellung dann fuer jede Struktur A bereits
das Universum U^A als die natuerlichen Zahlen definiert,
das Praedikat P^A wird stets als { ( u, k \cdot v ) | u,v,k natuerliche Zahlen } interpretiert.

Eine Struktur A fuer F muss dann nur noch x,y,g interpretieren/belegen, z.B.
x^A = 3, y^A = 42;
daraus wird ein Model fuer g^A = 3 ( A(F) = 1), eine Struktur, aber kein Model, fuer g^A = 7 (A(F) = 0).

MaW, eine Struktur A fuer F ist ein Tripel von natuerlichen Zahlen (x^A,y^A, z^A), wobei A ein Model genau dann ist, falls g = ggT(x,y).

[Hardwaretoaster]

Formal gesehen geht aus der Aufgabenstellung nicht hervor, dass du das binaere Praedikat "x > w" verwenden darfst;
die genau Bezeichnungs ist, wenn ich mich recht erinner, FO( N, P),
FO steht dabei fuer First-Order (Praedikatenlogik 1.Stufe),
mit dem Universum N (Natuerliche Zahlen) und dem einzigen Praedikat P.

Die Definition fuer den ggT benoetigt allerdings auch keine Ordnungsrelation;
formal ist der ggT definiert durch:

1) der ggT(x,y) ist ein Teiler von x und von y
2) jeder andere Teiler w von x und y teilt auch den ggT(x,y)

Ergibt dann

F := E g. [ P(g,x) /\ P(g,y) /\ A w.[ (P(w,x) /\ P(w,y)) -> P(w,g) ] ].

Implizit ist ja durch die Aufgabenstellung dann fuer jede Struktur A bereits
das Universum U^A als die natuerlichen Zahlen definiert,
das Praedikat P^A wird stets als { ( u, k \cdot v ) | u,v,k natuerliche Zahlen } interpretiert.

Eine Struktur A fuer F muss dann nur noch x,y,g interpretieren/belegen, z.B.
x^A = 3, y^A = 42;
daraus wird ein Model fuer g^A = 3 ( A(F) = 1), eine Struktur, aber kein Model, fuer g^A = 7 (A(F) = 0).

MaW, eine Struktur A fuer F ist ein Tripel von natuerlichen Zahlen (x^A,y^A, z^A), wobei A ein Model genau dann ist, falls g = ggT(x,y).

Ich versthe nur Bahnhof ;(
Das muss doch nicht so umständlich sein, oder?

[Gast]

Kommt immer auf den Tutor an ;P

Aber so kompliziert erscheint das nur das erste Semester, bis man sich dann auf die Pruefung vorbereitet und langsam Uebung bekommt im Umgang mit den ganzen Definitionen.

Ich wollte einfach nur drauf hinweisen, dass je nach Vorlesung es sein koennte,
dass du dein ( w > x ) nicht verwenden darfst, weshalb du es durch
eben mit Hilfe von P(,) umschreiben musst.

Der zweite Teil war ein -- offensichtlich gescheiterter Versuch xD --
die Semantik von solchen Formeln (also Wahrheitswert unter Strukturen/Modelen) zu verdeuchtlichen; ueblicherweise macht das naemlich am Anfang doch groessere Probleme -- sorry, wenn das eher verwirrend/entmutigend gewirkt haben sollte.

[Gast]

Nachtrag:

Wegen dem Unterschied "Praedikatenlogik 1. Stufe" und "Theorie" (ich hoff, es ist der richtige Begriff):

* eine rein praedikatenlogische Formel, z.B.

F = A x E y S(x,y) /\ E u A v - S(v,u)

( "-" Negation, "A" Allquantor, "E" Ex-Quantor, /\ = UND, \/ = ODER)

hat zunaechst keinen Wahrheitswert, da die Formel allein
nicht definiert, wo a) die Variablen x,y leben sollen,
b) nicht klar ist, wie S definiert ist.

Hierfuer benoetigt man formal eine "passende Struktur A".

So eine Struktur besteht im Fall von der Formel F also
zum einen aus dem "Universum U^A", in welchem x und y leben,
und zum anderen sagt A uns, was S bedeuten soll,
es definiert also S^A als eine Teilmenge von U^A x U^A.

Unter einer Struktur ergibt sich dann der Wahrheitswert der Formel,
meist durch A(F) abgekuerzt.

Nehmen wir z.B. die Struktur A definiert durch
U^A = { 0,1,2, .... } (natuerliche Zahlen)
S^A = { (i,i+1) | i = 0,1,2, .... } (Nachfolgerrelation)

Dann gilt A(F) = 1:
- A x E y S(x,y) ist stets wahr, da fuer jedes x in U^A man y = x+1 waehlen kann.
- E u A v - S(v,u) ist stehts wahr, da u = 0 kein Nachfolger einer anderen
natuerlichen Zahl ist.

Die Struktur B mit U^B = { ..., -2, -1, 0, 1, 2, .... } (ganze Zahlen)
mit S^B = { (i,i+1) | i = ...., -2,-1,0,1,2, .... } (Nachfolgerrelation wieder)
ist hingegen kein Model (also A(F) = 0), da jetzt jede Zahl Nachfolger einer
anderen Zahl ist.

* Jetzt kann man sich aber auch auf den Standpunkt stellen, dass
stets U^A die natuerlichen Zahlen sein sollen und S^A stets die
Nachfolgerrelation ueber den natuerlichen Zahlen sein soll -- so wie in
Struktur A eben.
Dann muss eine Struktur hoechstens noch freie aka ungebundene Variablen
interpretieren/belegen, damit sich der Wahrheitswert der Formel ergibt.

Man laesst dann allerdings nur noch Formeln zu, die sich aus den
fixierten Praedikaten- (und ggf. Funktions)symbolen bilden lassen;
man ist dann daran interessiert, was sich alles beweisen laesst,
wenn man einzig das Universum und die Definition von S
als gegeben annimmt.

Man laesst hoechstens noch Abkuerzungen fuer bereits abgeleitete
Formeln zu, z.B.

N = A v - S(v,u)

Um sich zu merken, dass u frei in N ist, schreibt man vllt
auch N(u).

Eine Struktur A zu N(u) muss dann nur noch den Wert von u definieren,
da wir ja das Universum und S bereits fixiert haben.

Z.B. waere u^A = 2 eine passende Struktur, mit A(N) = 0;
waehrend fuer u^A = 0 wieder A(N) = 1 folgen wuerde.

Die Formel N(u) ist also genau dann wahr, wenn u also 0 interpretiert wird;
m.a.W. N(u) definiert explizit die 0.

Damit koennen wir auch z.B. explizit die 1 als Formel einfuehren, durch
Eins(v) = E u . ( N(u) /\ S(u,v) ).

Eins(v) ist jetzt genau dann wahr, wenn wir v als 1 interpretieren.

Haetten wir z.B. S nicht als Nachfolgerrelation definiert, sondern als Gleichheitsrelation, dann haetten wir niemals Formeln schreiben koennen,
die explizit gewisse Werte aus den natuerlichen Zahlen definieren.

Du kannst z.B. auch versuchen, eine Formel Kleiner(x,y) mit zwei
freien Variablen nur unter Verwendung von S und Quantoren/aussagenlogischen Verknuepfungen zu schreiben,
so dass A(Kleiner) = 1 genau dann, wenn x^A < y^A --
wenn ich jetzt nicht ganz daneben lieg, sollte das allerdings nicht gehen,
mir zumindest wuerde gerade nur eine unendliche Formel
S(x,y) \/ E u. (S(x,u) /\ S(u,y) ) \/ E u1 E u2 . (S(x,u1) /\ S(u1,u2) /\ S(u2,y) ) \/ ...
einfallen, die allerdings -- da unendlich -- nicht mehr praedikatenlogisch waere.

Was hat das ganze jetzt mit dem (w > x) zu tun? Man kann sich eben
auf den Standpunkt stellen, dass in der Aufgabenstellung nur
das Universum (die natuerlichen Zahlen) und das Praedikat P(,) gegeben
sind, und die Relation (w > x) hoechstens dann verwendet werden darf,
wenn sie denn mittels P durch eine entsprechende Formel geschrieben
werden kann -- was allerdings nicht gehen sollte, da "x teilt y" nur eine
partielle Ordnung ist, " x kleiner y" jedoch linear/total ist.


Ich hoffe, das ist jetzt weniger verwirrend.

[Hardwaretoaster]

Ok, dem ersten posting kann ich folgen, diese Ausdrücke der Form (W>v) dürfen wir direkt verweden.

Das zwete vertseh ich noch nicht vollständig, aber dazu muss ich wohl auch noch ein paar Stunden Vorlesung mehr hören...