Prädikatenlogik

bolingo · Newbie Anmeldungsdatum: 12.05.2008 Beiträge: 1

Hallo Leute

Ich habe angefangen zu studieren und zwar 1erste Semester Informatik und möchte ein paar Übungen lösen.
Könnte mir Jemanden erklären wie Prädikatenlogik funktioniert?
Ich danke Euch im voraus.

Aufgabe 1: Prädikatenlogik
Überführen Sie folgende Aussagen in die Schreibweise der Prädikatenlogik:
a) Klaus und Lars sind Studenten
b) Klaus und Lars sind Freunde
c) Jeder Mensch hat irgend eine Aufgabe
d) Alle Menschen haben eine gemeinsame Aufgabe
e) Anna liebt Peter
f) Niemand liebt Logik
g) Alle Studierenden lieben Logik
h) Jeder Hund mag einen Knochen
i) Anna sieht einen Bär und Paul sieht ihn auch (Hinweis: Den gleichen Bär!)
j) Anna sieht einen Bär und Paul sieht auch einen
Nutzen Sie dabei ausschließlich Prädikate der Form ist_irgendetwas(x) oder
hat_irgendetwas(x) für „...ist...“-Aussagen oder „...hat...“-Aussagen, Prädikate der Form
sind_irgendetwas(x,y) für Aussagen der Form „...sind...“ und Prädikate der Form
tutirgendetwas(x,y) für Beziehungen wie z.B. „a sieht b“ oder „a liebt b“.

Aufgabe 2: Prädikatenlogik
a) Formulieren Sie die folgenden umgangssprachlichen Sätze mit Hilfe der
Prädikatenlogik:
1. Alle grünen Drachen und rosa Drachen sind glücklich
2. Alle grünen Drachen sind glücklich und optimistisch
3. Alle Drachen sind grün oder rosa
(Nutzen Sie die Prädikate sind_grün() und sind_rosa())
4. Grüne Drachen sind biestig, aber nicht aggressiv
(Nutzen Sie die Prädikate sind_biestig() und sind_aggressiv())
5. Es gibt keinen Drachen, der nicht eine Seeschlange liebt
6. Alle Drachen, die bissig und biestig sind, sind frech.
7. Einige Drachen, die biestig und frech sind, lieben alle rosa Seeschlangen
8. Einige singende Drachen sind biestig.
b) Formulieren Sie a)5. und a)8. mit Hilfe des All-Quantors statt des Existenz-Quantors!
c) Formulieren Sie a)2, a)3, a)6. mit Hilfe des Existenz-Quantors statt des All-Quantors!
d) Formulieren Sie a)7. unter ausschließlicher Verwendung von Existenz-Quantoren!

Aufgabe 3: Prädikatenlogik
Gegeben seien folgende Prädikate
- V(x): x ist ein Vogel
- D(x): x ist ein Drache
- T(x): x ist ein Tier
- f(x): x kann fliegen
- s(x): x kann Feuer spucken
- g(x): x ist glücklich
- l(x,y): x wird von y geliebt
1. Drücken Sie folgende Feststellung in Prädikatenlogik aus:
- Alle Tiere, die fliegen können und keine Drachen sind, werden von einigen
Vögeln geliebt.
- Jeder Vogel ist glücklich, wenn ein von ihm geliebtes fliegendes Tier kein
Feuer spuckt.
2. Formulieren Sie folgenden Ausdruck umgangssprachlich:
∃x∀y: ( (T(x) ∧ f(x) ∧ s(x) ∧ l(x,y)) ⇒ D(y) )

Aufgabe 4: Prädikatenlogik
Sei a=Anna, b=Bodo, f=Thomas, A=bewundert, D=verachtet. Übersetzen Sie folgende
prädikatenlogische Ausdrücke in deutsche Sätze:
a. A(b,f)
b. A(b,f) ∧ (D(f,b)
c. ∃x: A(x,x)
d. ¬∀x: D(x,f)
e. ∀x Sad

A(x,f)⇒D(x,x))
f. ¬∃x∀y:A(y,x)
g. ∀x∀y(A(x,y) ⇒¬D(x,y))

Aufgabe 5: Prädikatenlogik
Betrachten Sie folgende verbale Aussage:
Der größte gemeinsame Teiler von zwei positiven Zahlen kleiner 6 ist die 1 oder das
Minimum der beiden Zahlen.
a) Überführen Sie die Aussage in einen Prädikatenlogischen Ausdruck
b) Zeigen Sie ob die Aussage wahr ist oder falsch ist.
c) Überprüfen Sie die Aussage nochmals, nachdem Sie „kleiner 6“ durch
„kleiner-gleich 6“ ersetzt haben.
Aufgabe 6: Prädikatenlogik
Welche der folgenden Ausdrücke sind äquivalent?
a) ∀x(∀y:p(x,y)) ≡ ∀y(∀x:p(x,y))
b) ∀x : (mensch(x) ⇒ ∃y:(mensch(y) ∧ liebt(x,y)))
≡ ∃x: (mensch(x) ∧ ∀y : (mensch(y) ⇒ liebt(y,x)))

murekursion · Full Member Anmeldungsdatum: 10.03.2008 Beiträge: 220

Niemand wird hier deine Hausaufgaben machen.

Hinweise zur Aufgabenstellung:
Bei Aufgabe 1 und 2 musst du dir Praedikate definieren, um die dort beschriebenen Aussagen in der Syntax eder Praedikatenlogik darstellen zu koennen.
Aufgabe 3 ist genauso wie Aufgabe 1 und 2, nur dass die zu verwendenen Praedikate schon vorgegeben sind.

4) und 5) sollten klar sein.

Nachdem du also die Aufgabenstellung verstanden hast, teile uns mit, was du konkret nicht verstehst.

Tolotos · Full Member Anmeldungsdatum: 20.01.2007 Beiträge: 307

smoother · Senior Member Anmeldungsdatum: 05.09.2006 Beiträge: 506 Wohnort: Hannover

d.e.m.p. · Senior Member Anmeldungsdatum: 10.04.2007 Beiträge: 1034

Gut, ich probiers mal hier, die Philosophen können mir grad nicht helfen (vielleicht wegen der schlechten Erreichbarkeit.)

Das bedeutet nicht, dass ich hier etwas doppelt poste, nein, ein brandneues Beispiel aus der Prädikatenlogik, an dem ich mich versucht habe.
Bitte zögert nicht, mich auf Fehler hinzuweisen. Ich glaube, es gibt welche, denn der nächste Beweis scheint mir wieder reichlich kurz und einfach geraten zu sein.

Nun mit Definitionen, die substituieren können/sollen.
(Allerdings weiß ich auch hier nicht, wie das formal an der Seite korrekt notiert wird)

Df1: Exy <-> Mxy & Myx
Df2: Gxy <-> Mxy & ~Myx

1 AxAyAz(Gxy&Gyz -> Gxz)___ A
2 Gab&Gbc _________________ A
3 Gab&Gbc -> Gac __________ 1 A out
4 Gac _____________________ 2,3 -> out
5 Mab & ~Mca ______________ 4 Df2 <>
6 ~Mca ____________________ 5 & out
7 | Eac ___________________ H (oder PA)
8 | Mac & Mca _____________ 7 Df1 <>
9 | Mca ___________________ 8 & out
10| Mca & ~Mca ____________ 6,9 & in
11 ~Eac ___________________ 7-10 ~ in
12 ~Eac & ~ Mca ___________ 6,11 & in

A steht für den All-, E für den Existenzquantor.

Danke für eventuelle Mühen!

Annihilator · Verfasst am: 24 Jun 2009 - 22:51:47 Titel:

Zur Darstellung von Formeln: Siehe meine Signatur.
Zu deinem Post: Was ist denn die Aufgabe? Was machst du da?

d.e.m.p. · Senior Member Anmeldungsdatum: 10.04.2007 Beiträge: 1034

Ich habe die zwei Annahmen 1,2 und "beweise" zeile Zwölf, also ~Eac & ~Mca. Ich dachte, das macht ihr Informatiker auch? Sad

Zwei Definitionen habe ich erstellt (Teil der Aufgabe), ohne die ich zwischen den Prädikatskonstanten G, E und M ja keine Verbindung hätte. (klingt wirr, aber der Teil stimmt)

Annihilator · Verfasst am: 25 Jun 2009 - 00:15:06 Titel:

Formeln auf Allgemeingültigkeit prüfen, tun viele - auch Informatiker. Ich denke, dass Problem ist, dass du davon ausgehst, dass die Notation, welche du verwendest, universell ist, also in der Form überall verwendet wird; dem ist nicht so. Ich kann daher nur raten, was Prädikat-Symbole, was Variablen, was Quantoren und was Junktoren sind. Mein Versuch einer "Übersetzung" in LaTeX (direkt lesbar mit erwähntem Plugin):

[; F_1 = \left( E(x, y) \leftrightarrow \left( M(x, y) \wedge M(y, x) \right) \right) ;]
[; F_2 = \left( G(x, y) \leftrightarrow \left( M(x, y) \wedge \neg M(y, x) \right) \right) ;]

Es ist zu untersuchen, ob die Formel [; \left( \left( F_1 \wedge F_2 \right) \rightarrow \left( \neg E(a, c) \wedge \neg M(c, a) \right) \right) ;] allgemeingültig ist. Mit in und out kann ich gar nichts anfangen.

Die Formel von 1 war: [; (\forall x) (\forall y) (\forall z) \left( \left( G(x, y) \wedge G(y, x) \right) \rightarrow G(x, z) \right) ;]. Sie sagt aus, dass die Relation [; G ;] transitiv ist. Mir ist nur der Zusammenhang zu [; F_1 ;] und [; F_2 ;] nicht klar.

d.e.m.p. · Senior Member Anmeldungsdatum: 10.04.2007 Beiträge: 1034

Nein, hier gehts um was Anderes.

Was ich Df1 und Df2 genannt habe, sind Definitionen, soll heißen, in dem folgenden Beweis kann man den Ausdruck (Exy) für (Mxy & Myx) substituieren.
[;(\forall x)(\forall y)(\forall z);](Gxy & Gyx -> Gxz) und (Gab & Gbc) zu beweisen, dass (~Eac & ~ Mca)

"out" bedeutet dabei, dass ich im 3. Schritt ( nach Zeile 1 und 2, die hinten mit "A" als Annahme oder Assumption gekennzeichnet sind) den Allquantor unter Beachtung der Regeln eliminiere, also eine Erläuterung des Gemachten.

In Zeile 7 führe ich, gekennzeichnet durch eine Linie und "H", eine Hypothese ein, die in Zeile 10 zu einem Widerspruch führt, was mich berechtigt, die Negation der Hypothese anzunehmen (~ in = Negationseinführung)

Meine Frage ist jetzt also, ob jemandem ein Fehler auffällt oder ein unnötiger Umweg.

P.S. Tex kann ich jetzt sehen, cool, nur benutzen wird wohl dauern. Ich kann ja deine Formeln sogar per drag&drop einfügen, sehr geil Smile

edit: doch nicht.

Annihilator · Verfasst am: 25 Jun 2009 - 12:16:18 Titel:

Jeeetzt verstehe ich. Was du da tust, ist eine logische Konsequenz mit Hilfe des so genannte Kalküls des natürlichen Schließens herzuleiten. Anders formuliert: Du hast die Allgemeingültigkeit einer bestimmten Formel bewiesen, nämlich [; \left( \left( F_1 \wedge F_2 \wedge F_3 \wedge F_4 \right) \rightarrow \left( \neg E(a, c) \wedge \neg M(c, a) \right) \right) ;] für

[; F_1 = \left( E(x, y) \leftrightarrow \left( M(x, y) \wedge M(y, x) \right) \right) ;]
[; F_2 = \left( G(x, y) \leftrightarrow \left( M(x, y) \wedge \neg M(y, x) \right) \right) ;]
[; F_3 = (\forall x) (\forall y) (\forall z) \left( \left( G(x, y) \wedge G(y, x) \right) \rightarrow G(x, z) \right) ;]
[; F_4 = \left( G(a, b) \wedge G(b, c) \right) ;]

Der Beweis ist geglückt. Ob man es auch einen schnelleren Weg gibt? Tja, das Kalkül des natürlichen Schließens ist für den Menschen weitaus komfortabler als Resolution. Diese kann der Rechner gut nutzen und würde dir das Ergebnis in Null-Komma-Nix ausspucken. Nur könnte man mit dem Beweis kaum etwas anfangen, da er nicht gerade anschaulisch und außerdem recht lang ist. Ich denke also schon, dass natürliches Schließen der für den Menschen eleganteste Weg ist.

d.e.m.p. · Senior Member Anmeldungsdatum: 10.04.2007 Beiträge: 1034

Okay, du sprichst zwar immernoch 'ne andere Sprache aber wir meinen das Selbe. Laughing

Danke, dass du dich da mal reingedacht hast.
Gruß

mazal · Full Member Anmeldungsdatum: 03.03.2006 Beiträge: 121

humanlike · Newbie Anmeldungsdatum: 20.02.2009 Beiträge: 15

uralter Thread: ich weiß! Aber hat noch jemand Aufgaben und Lösungen zu Prädikatenlogik?
Ich suche spezielle nach Aufgaben der Form:
Formulieren Sie die folgenden umgangssprachlichen Sätze mit Hilfe der
Prädikatenlogik.

Das Web liefert mir Aufgaben, leider nur ohne Lösung, evtl. hat jemand noch was auf seinem Rechner oder auf der Uni-Website.

Vielen Dank!