View Full Version : [Frage] Tautologie vs. gültig in Datentyp
Wie kann man Tautologie (allg. Gültigkeit) gegenüber der Gültigkeit nur im Datentyp (Vergleiche 2.Teilprüfung Aufgabe 1.) b); warum ist es nur in L gültig, nicht aber allgemein?) unterscheiden?
maitscha
29-06-2004, 16:09
Du hättest doch nur das aktuellste Post lesen müssen:
http://tigerente.htu.tuwien.ac.at/~iforum/showthread.php?t=20514
tja nur bringt mich das genau null weiter...
ich weiss dass es den unterschied gibt nur wie kann ich beweisen, dass es nur in dem datentyp liegt oder auch allgemein gültig ist
Plantschkuh!
29-06-2004, 17:21
Das ganze ist eine haarige Sache, die erst in ThInf 2 behandelt wird (und dort auch nur die allgemeine Gültigkeit).
Wenn du eine Formel vorliegen hast, von der du weißt, daß sie gültig in deinem Datentyp ist, dann gibt es aber zwei Rezepte, die für die Formeln bei der Prüfung funktionieren sollten:
Die Formel ist allgemein gültig, wenn sie eine Instanz einer aussagenlogisch gültigen Formel ist.
Beispiele dafür wären "atom?(x) oder nicht atom?(x)" als Instanz von "A oder nicht A"; oder sowas wie "(x > 7 und y = 2) impliziert x > 7" als Instanz von "(A und B) impliziert A".
Du versuchst, die Bedeutung der Symbole völlig zu ignorieren und dann zu schauen, ob die Formel noch immer gültig ist.
Es könnte eventuell schwer sein, sich von der Bedeutung zu lösen, daher kann man die Formel umschreiben: Prädikatensymbole in P, Q, ... umbenennen, Funktionssymbole in f, g, ...., Konstantensymbole in a, b, ...
Für das Beispiel 1.b ergibt sich "(P(f(x, a)) und Q(x, a)) impliziert P(x)". Daß das nicht allgemein gültig ist, sollte schon eher einsichtig sein. Wenn nicht, konstruiere ich auf Anfrage ein Gegenbeispiel.
So auf die Schnelle finde ich dazu gar kein positives Beispiel im Skriptum, aber es wäre zum Beispiel etwas wie "(für alle x) x > 7 impliziert 0 > 7"; das ist eine Instanz der prädikatenlogisch allgemein gültigen Formel "(für alle x) P(x, a) impliziert P(b, a)".
Falls jemand in den Übungs- oder alten Prüfungsangaben eine Formel findet, wo diese beiden Rezepte versagen, bitte sagen! Dann können wir uns was neues überlegen :D
hab das theoinf2 skript eh vor mir liegen, aber da steht das auch etwas eh 'schwammig' ;)
aber die 2 rezepte leuchten ein...
Plantschkuh!
01-07-2004, 14:58
Für das Beispiel 1.b ergibt sich "(P(f(x, a)) und Q(x, a)) impliziert P(x)". Daß das nicht allgemein gültig ist, sollte schon eher einsichtig sein. Wenn nicht, konstruiere ich auf Anfrage ein Gegenbeispiel.
Na gut, ich bin gebeten worden, das genauer zu erklären, also probier ich das mal. Die obige Formel ergibt sich aus der Angabe, indem man P für atom?, f für build, a für nil und Q für eq? setzt. Wir wissen nichts über die Bedeutung von P, Q, f und a. Ist die Formel allgemein gültig?
Da wir keinen Kalkül für die Prädikatenlogik gemacht haben, müssen wir uns mit semantischen Überlegungen helfen. Für eine solche Formel heißt das konkret, daß wir verzweifelt versuchen, ein Gegenbeispiel zu konstruieren; also eine Belegung der Prädikaten-, Funktions- und Konstantensymbole sowie der Variablensymbole, unter der die Formel falsch wird.
Schlachtplan: Da es sich hier um eine Implikation handelt, die wir falsifizieren wollen, muß die Konklusion P(x) falsch werden, die Prämissen P(f(x, a)) sowie Q(x, a) hingegen beide wahr.
Ein eher abstraktes Gegenbeispiel: P wird für alle Ergebnisse von f wahr, für andere Objekte aber falsch; Q ist immer wahr. Dann haben sind beide Prämissen wahr, die Konklusion kann aber falsch werden, damit kann die gesamte Formel falsch werden, sie ist also nicht allgemein gültig.
Danke, es wird schon klarer. Also eine Tautologie in L wäre dann: atom(x) v nicht atom(x). Umgeschrieben: P(x) v nicht P(x). Richtig?
mfg Dieli
Wenn du glaubst es geht nicht mehr, von irgendwo ein Lichtlein brennt ;)
Für das Beispiel 1.b ergibt sich "(P(f(x, a)) und Q(x, a)) impliziert P(x)".
Das kann man auch als P(f(x, a)), Q(x, a) |= P(x) anschreiben, dann sieht man sofort, dass dies keine (allgemein) gültige Formel in der Prädikatenlogik ist.
Da in den Ausdrücken, die so zu bearbeiten sind, generell keine quantifizierten Variablen vorkommen (oder besser: wenn in den zu bearbeitenden Ausdrücken keine quantifierten Variablen vorkommen), kann man jedes Atom einfach durch ein nullstelliges Prädikat (z.b. A, B, C, ...) ersetzen und dann schauen, ob eine gültige formel der aussagelogik a.k.a. Tautologie rauskommt. (z.b. hier: A, B |= C). Zwei Atome kriegen dasselbe Literal, wenn sie "genau gleich ausschauen", da (wenn nichts quantifiziert wird) sich z.b. zwei P(x) auf dasselbe x beziehen. Wenn wir was der Form "((für alle x) P(x)) und ((es existiert x) Q(x))" haben, sind die x ja nicht diesselben, aber das führt dann wohl zu weit...
mit dieser Überlegung im Hinterkopf kann man (für die Thinf1 Prüfung zumindest) als Faustregel sagen: wenn Instanz einer aussagelogischen gültigen Formel, dann allgemein gültig...
Danke, es wird schon klarer. Also eine Tautologie in L wäre dann: atom(x) v nicht atom(x). Umgeschrieben: P(x) v nicht P(x). Richtig?
ja, atom(x) oder nicht atom(x) ist allgemein gültig (den Teil mit "in L" tät ich weglassen)...
wenn du es mal nicht sofort siehst (weil vielleicht die Formel komplexer ist oder warum auch immer), kannst du es ja jederzeit mit dem Sequentialkalkül oder Tableauxkalkül probieren, ob die Formel allgemein gültig ist, nachdem du sie in eine Instanz einer aussagelogischen Formel umgewandelt hast, z.b. bei deinem Beispiel
atom(x) oder nicht atom(x) ~~~ A oder not A
dann ins sequentialkalkül damit
A |- A (Axiom)
------------------------------------- not rechts
|- A, not A
atom(x) oder nicht atom(x) ~~~ A oder not A
dann ins sequentialkalkül damit
A |- A (Axiom)
------------------------------------- not rechts
|- A, not A
Passt schon so. Folgendes ist Blödsinn.
Blöde Frage, aber müsste das |-- nicht rechts von den beiden Formeln stehen um Gültigkeit nachzuweisen? Also
A |-- A
------------- ¬-links
A, ¬A |--
Das Ergebnis ist offenbar das gleiche (was bedeutet das dann eigentlich? Eh nix besonderes oder?).
Oder ist das alles Schwachsinn und ich hab den SK nicht verstanden?
Blöde Frage, aber müsste das |-- nicht rechts von den beiden Formeln stehen um Gültigkeit nachzuweisen?
Nein, damit zeigst du Unerfüllbarkeit:
{} |- F --> F gültig
F |- {} --> F unerfüllbar
Links vom Pfeil wird "verundet", rechts "verodert" ;) , der Pfeil entspricht der Implikation. Die leere Disjunktion ist falsch, die leere Konjunktion dagegen true (Seite 133 auf den Folien):
Also |- A,!A heißt soviel wie t(rue) > A v !A, umgekehrt würde es A^!A > f(alse), was natürlich beides stimmt, aber für das Beispiel will man ja ersteres zeigen (obwohl für so triviale Sachen das Sequentialkalkül unnötig ist).
Gottverdammt, schon wieder die Positionen von dem Ableitungszeichen verwechselt. Danke.
zur Erklärung nochmal (sicherheitshalber)
Vorwissen:
leere Disjunktion ~ false
leere Konjunktion ~ true
A, B |= C, D ~ (A und B) impliziert (C oder D)
A, B |= C, D gdw A, B |- C, D
meine ableitung zeigt
true impliziert (A oder nicht A),
was gültig ist, da (A oder nicht A) niemals false werden kann
deine ableitung zeigt
(A und nicht A) impliziert false
was ebenfalls gültig ist, da (A und nicht A) unerfüllbar ist...
Ich hab bei meinen Post auch noch was dazugeschrieben ^^
Jetzt ist mir endlich ein verdammtes Licht aufgegangen glaub ich. Hab zwar weißgottwieoft Abschnitt 3.4, Seite 71/72 sowie Seite 76/77 gelesen, aber hab mir das selbst nie hundertprozentig genau erklären können.
Was aber ist eine leere Disjkunktion bzw leere Konjunktion bzw. warum ist die eine falsch, die andere wahr? Was kann ich mir darunter vorstellen? Sehs zwar im Skriptum und auf den Folien, aber bin wohl grad etwas daneben. Bitte Hilfe, bin kurz davor das Ganze zu verstehen :)
grassi3000
01-07-2004, 19:21
Achja, wo liegt eigentlich der Unterschied zwischen:
|= und |-?
bzw. wann muss ich was verwenden?
Den hab ich nicht so wirklich kapiert?
>wann muss ich was verwenden
|- verwendest du im Sequentialkalkül, |= verwendest du, um eine logische Konsequenz auszudrücken
>wo liegt eigentlich der Unterschied zwischen |= und |-?
wie gck schon gesagt hat, gilt |- genau dann, wenn |= gilt. Der Unterschied ist nur, wo du was anwendest.
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.