semantische Äquivalenz |
| 08.01.2007, 15:57 | steffi110 | Auf diesen Beitrag antworten » | ||||
| semantische Äquivalenz und zwar soll ich die Menge der Booleschen Terme über n Variablen betrachten und angeben wieviele äquivalenzklassen bezöglich der semantischen Äquivalenz existieren. Naja so ein Boolescher Term kann ja nur wahr oder falsch sein. Deshalb gibt es doch nur zwei klassen oder?? |
||||||
| 08.01.2007, 20:28 | steffi110 | Auf diesen Beitrag antworten » | ||||
jemand ein tip, vorschlag, ne anregung? |
||||||
| 08.01.2007, 23:43 | Abakus | Auf diesen Beitrag antworten » | ||||
Ich muss erstmal rückfragen: was verstehst du unter semantisch äquivalent (Definition) ? Grüße Abakus 
|
||||||
| 09.01.2007, 10:39 | steffi110 | Auf diesen Beitrag antworten » | ||||
naja sementisch äquivalent sind doch zwei boolesche terme A und B, wenn alle Interpretationen von A und B (also die Belegeungen) gleich sind. z.b.: (A und B) sem. Äq. (B und A) oder? |
||||||
| 09.01.2007, 12:55 | Abakus | Auf diesen Beitrag antworten » | ||||
OK, zwei boolesche Terme sind also semantisch äquivalent, wenn sie für alle Belegungen jeweils das selbe Ergebnis liefern. Demnach gibt es bei n Variablen mehr als nur 2 Klassen, zwei boolesche Terme gehören ja schon dann einer anderen Klasse an, wenn sie für mindestens eine Belegung ein unterschiedliches Ergebnis liefern. Wieviele Belegungen gibt es bei n booleschen Variablen und wieviele mögliche boolesche Funktionen auf diesen Belegungen gibt es demnach ? Das ist hier die Frage dann. Grüße Abakus
|
||||||
| 09.01.2007, 16:00 | steffi110 | Auf diesen Beitrag antworten » | ||||
na wenn ein term min. aus einer variable besteht gibts maximal n terme, als o n klassen...aber ein term kann doch auch aus mehreren variablen bestehn...hmmmm |
||||||
| Anzeige | ||||||
|
|
||||||
| 09.01.2007, 17:35 | Abakus | Auf diesen Beitrag antworten » | ||||
Das meine ich nicht. Meine Frage ist, wieviele boolesche Funktionen mit n Variablen gibt es ? Gemeint sind solche Funktionen: Diese Funktionen kannst du als Repräsentanten für deine Klassen nehmen, denke ich. Grüße Abakus
|
||||||
| 09.01.2007, 18:19 | steffi110 | Auf diesen Beitrag antworten » | ||||
ich versteh glaube nur bahnhof eine boolesche Funktion mit n parametern (Variablen) liefert als ergebniss 0 oder 1, soooo wieviel boolesche funktionen gibt es mit n Variablen??? na unendlich viele |
||||||
| 09.01.2007, 18:56 | Abakus | Auf diesen Beitrag antworten » | ||||
Wenn du eine Variable hast, gibt es zB 4 Funktionen, siehe die folgenden Möglichkeiten: 0 -> 0 0 1 1 1 -> 0 1 0 1 Wenn du zwei Variablen hast, gibt es bereits 16 Möglichkeiten, die du ähnlich aufzählen kannst. Grüße Abakus
EDIT: Text |
||||||
| 09.01.2007, 19:16 | steffi110 | Auf diesen Beitrag antworten » | ||||
sorry ich kann dir nicht folgen. wenn ich eine Variable habe, dann gibts doch nur zwei funktionen 0 und 1, hööö? |
||||||
| 09.01.2007, 19:24 | Abakus | Auf diesen Beitrag antworten » | ||||
Also: 1. f(0) = f(1) = 0, 2. f(0) = 0, f(1) = 1, 3. f(0) = 1, f(1) = 0, 4. f(0) = f(1) = 1. Das sind 4 verschiedene Funktionen, obwohl der Wertebereich nur aus 2 Elementen besteht. Funktionen sind bereits dann verschieden, wenn sie ein Element verschieden abbilden. Grüße Abakus
|
||||||
| 09.01.2007, 19:34 | steffi110 | Auf diesen Beitrag antworten » | ||||
? wie sieht denn die funktion aus? einmal ist f(0)=1, dann ist f(0) wieder 0 das geht doch garnich..oder bin ich jetzt komplett bekloppt? |
||||||
| 09.01.2007, 19:42 | Abakus | Auf diesen Beitrag antworten » | ||||
Das ist nicht eine, sondern es sind 4 Funktionen. Der Einfachheit sind alle 4 mit f bezeichnet. Grüße Abakus
|
||||||
| 09.01.2007, 20:02 | steffi110 | Auf diesen Beitrag antworten » | ||||
also es geht ja um terme.. bei einer Variable, nennen wir sie mal a ergeben sich vier verschiedene funktionen.. a kann den wert 0 oder 1 haben jetzt setzt ich a ein, aber in welche funktionen?? wie kommst du auf die ergebnisse was die funktionen ausspucken?? |
||||||
| 10.01.2007, 00:02 | Abakus | Auf diesen Beitrag antworten » | ||||
Aus einem booleschen Term kannst du eine boolesche Funktion machen, zB: du hast den Term: daraus wird die Funktion: Wenn du wissen willst, was die Funktion "ausspuckt", kannst du eine Wertetabelle erstellen. Hier siehst du relativ leicht, dass f(1, 1, 1) = f(1, 0, 0) = 1 ist und alle anderen Kombinationen 0 ergeben. Ein ähnliches Beispiel: Hier ist zusätzlich noch g(0, 1, 1) = 1, d.h. der Term hier ist vom obigem Term semantisch verschieden. Grüße Abakus
|
||||||
| 10.01.2007, 01:29 | steffi110 | Auf diesen Beitrag antworten » | ||||
also sind das nur beispiele und völlig unverbindlich. aber ich glaub wir sind total vom eigentlich thema abgeschweift... was sind die ÄKlassen...ich bin total verwirrt jetzt |
||||||
| 10.01.2007, 18:25 | Abakus | Auf diesen Beitrag antworten » | ||||
Siehe hier: Äquivalenzrelation. Zu dem Thema ergibt die Boardsuche ebenfalls zahlreiche Threads. Grüße Abakus
|
||||||
| 10.01.2007, 18:54 | steffi110 | Auf diesen Beitrag antworten » | ||||
ja also ich weiss eine äquivalenzrelation ist (wenn eine funktion reflexiv, semetrisch und transitiv ist, was das bedeutet weiss ich auch). äquivelnzeklassen ist mehr auch soweit klar... ich weiss aber nicht wie ich das mit der aufgabe kombiniern soll.. |
||||||
| 10.01.2007, 20:41 | Abakus | Auf diesen Beitrag antworten » | ||||
Auf der Menge der booleschen Terme ist eine Äquivalenzrelation wie folgt definiert: Das kannst du nachprüfen, dass es eine Äquivalenzrelation ist. Über mögliche Repräsentanten der Klassen habe ich vorher schon was gesagt (boolesche Funktionen usw.). Grüße Abakus
|
||||||
| 10.01.2007, 20:56 | Steffi110 | Auf diesen Beitrag antworten » | ||||
hmm ich versteh einfach nicht, wie genau so ein boolescher term aussieht bzw. wie eine menge davon aussieht und wo da n variablen drinstecken solln |
||||||
| 10.01.2007, 21:11 | Abakus | Auf diesen Beitrag antworten » | ||||
Einige Beispiele stehen ja schon im Thread für solche Terme. Und ihr werdet das ja definiert haben, was ihr darunter versteht. Grob gesagt, kannst du n Variablen mit den Verknüpfungen "NOT", "AND", und "OR" beliebig umfangreich verknüpfen. Jede solche Verknüpfung ist ein boolescher Term. Grüße Abakus
|
||||||
| 10.01.2007, 21:18 | steffi110 | Auf diesen Beitrag antworten » | ||||
ja und wenn ich die beliebigen verknüpfungen mit n Variablen aufschreiben dann hab ich EIN Term mit n-1 Verknüpfungen, das ist doch richtig oder? Jetzt ist immer die rede von der Menge der Terme, also sind es doch mehrere Terme, in denen insgesamt n Variablen vorkommen oder in jedem Term der Menge von Termen kommen n Variablen vor??? |
||||||
| 10.01.2007, 22:54 | Abakus | Auf diesen Beitrag antworten » | ||||
Nein, die Variablen können durchaus mehrfach vorkommen.
In mehreren Termen kommen n Variablen vor, ja. Es können aber auch weniger Variablen vorkommen, in dem Fall hat zB eine Variable keinen Einfluß auf das Ergebnis: Hier kommt die dritte Variable zB nicht vor. Als Regeln für die Bildung von Termen kannst du dir vorstellen: [1] sind Terme [2] wenn S und T Terme sind, so auch [3] wenn R ein Term ist, so auch Mittels dieser 3 Regeln können alle booleschen Terme aus höchstens n Variablen gebildet werden. Grüße Abakus
|
||||||
| 10.01.2007, 23:10 | steffi110 | Auf diesen Beitrag antworten » | ||||
soo okay, das wäre die menge der booleschen terme über n Variablen.. ich werf einfach mal meine vermutung in den raum, wird sicher falsch sein, aber bevor ich mich um kopf un kragen schreiben
gibt es 2^n Ä.Klassen? |
||||||
| 10.01.2007, 23:27 | Abakus | Auf diesen Beitrag antworten » | ||||
2^n wären zu wenig, wie du an diesem Beispielen siehst. Aber es gibt 2^n-viele Belegungen der n Variablen. Grüße Abakus
|
||||||
| 10.01.2007, 23:32 | steffi110 | Auf diesen Beitrag antworten » | ||||
okay dann 4^n aber erklären könnt ichs nich wirklich... |
||||||
| 10.01.2007, 23:36 | Abakus | Auf diesen Beitrag antworten » | ||||
Mit Raten kommst du nicht weit. Du musst schon überlegen, welche Möglichkeiten es gibt und wie du die zählst. Einen Anhaltspunkt hast du: die 2^n - vielen Belegungen. Grüße Abakus
|
||||||
| 10.01.2007, 23:39 | steffi110 | Auf diesen Beitrag antworten » | ||||
kannst du ein paar beispiele für ä.klassen geben? du mich noch mehr in die richtige richtung schubsen? |
||||||
| 11.01.2007, 00:05 | Abakus | Auf diesen Beitrag antworten » | ||||
Überleg mal, wieviele boolesche Funktionen es gibt. Jede dieser Funktionen repräsentiert eine Äquivalenzklasse. Du hast 2^n mögliche Belegungen einer solchen Funktion, für jede einzelne Belegung gibt es als Funktionswert 2 Möglichkeiten (0 und 1). Wieviele solche Funktionen gibt es nun ? Grüße Abakus
|
||||||
| 11.01.2007, 00:09 | steffi110 | Auf diesen Beitrag antworten » | ||||
2^2*n ? |
||||||
| 11.01.2007, 00:11 | steffi110 | Auf diesen Beitrag antworten » | ||||
richtig is aber glaube 2^2^n |
||||||
| 11.01.2007, 00:14 | Abakus | Auf diesen Beitrag antworten » | ||||
Ja, das passt 
.Da du für jede Belegung 2 Möglichkeiten hast und es 2^n Belegungen gibt, kommst du insgesamt auf 2^(2^n)-viele Funktionen. Grüße Abakus
|
||||||
| 11.01.2007, 00:20 | steffi110 | Auf diesen Beitrag antworten » | ||||
ooh man das war echt ein harter weg
jetzt soll ich noch zeigen das alle klassen gleichmächtig sind: gleichmächtig bedeutet doch, das jede klasse die gleiche anzahl an elementen hat oder? |
||||||
| 11.01.2007, 00:35 | Abakus | Auf diesen Beitrag antworten » | ||||
Ja, das bedeutet es. Da es nach meiner Definition oben unendlich viele verschiedene Terme gibt (die können ja beliebig verlängert werden), solltest du hier zunächst eure Definition von Booleschen Termen abklären (ggf. lautet die anders). Grüße Abakus
|
||||||
| 11.01.2007, 00:44 | Steffi110 | Auf diesen Beitrag antworten » | ||||
Die Menge der Booleschen Formeln (Booleschen Terme) der Aussagenlogik über der Variablenmenge V und der Aussagenmenge A ist induktiv definiert: 1. Jedes a element A und jedes v element V sind Boolescher Term. 2. Wenn t Boolescher Term ist, so ist auch (nicht t) Boolescher Term. 3. Wenn t1 und t2 Boolesche Terme sind, so sind es auch die Konjunktion (t1 oder t2) und die Disjunktion (t1 und t2). 4. (Minimalitätsprinzip) Nur Konstrukte, die sich durch endlich oftes Anwenden der Regeln (1),(2) bzw. (3) erzeugen lassen, sind Boolesche Terme. also genauso wie deine definition...hätte mal früher nachgucken solln.. |
||||||
| 11.01.2007, 13:42 | Abakus | Auf diesen Beitrag antworten » | ||||
Du kannst dir überlegen, dass die Menge der Booleschen Terme mit höchstens n Variablen abzählbar ist und dass ebenfalls jede Äquivalenzklasse abzählbar ist. Damit wäre auch das gezeigt. Grüße Abakus
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
