Semiringe.... < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:58 Di 16.12.2003 | | Autor: | Gloomer |
Servus.....
ich bräuchte da mal wieder nen bisserl Hilfe...
Ich muss abgeschlossene Semiringe nachweisen, 3 an der Zahl, und bereits nach einem bin ich wieder so verblendet, dass ich keinen Ausweg sehe ;) Beweisführung ist echt nicht mein Ding
Da wäre:
S= ([mm]\mathbb{B}[/mm] , [mm]\vee[/mm] , [mm]\wedge[/mm] , 0, 1)
und noch
S= ([mm]\mathbb{R}[/mm]+ [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{[mm]\infty[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} , inf , +, [mm]\infty[/mm], 0)
Meines Wissens nach muss man doch immer
-Assoziativität
-Kommutativität
-Neutrales Element
-Links/Rechts Distributivität
-Nullteilerfreiheit
nachweisen....
oder fehlt mir da schon was, dann wäre mein erster Ring auch schon falsch :-p
Nachricht bearbeitet (Di 16.12.03 15:03)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:54 Di 16.12.2003 | | Autor: | Marc |
Hallo Gloomer,
habt ihr denn in der Vorlesung Semiringe nicht definiert? Das kann doch gar nicht sein...
Falls du in deinen Aufzeichnungen nichts findest, werde ich es später mal mit dieser Definition versuchen:
Semiring
Den zweiten Ring verstehe ich nicht, was ist denn inf für ein Operator?
Bis später,
Marc
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 16:16 Di 16.12.2003 | | Autor: | Gloomer |
aaalsooooo
inf soll Infimumbildung der Addition in diesm Ring sein....
definiert wurden die Ringe schon, nur höre ich diese vorlesung nicht, wofür ich das brauche und anhand des skriptes bin ein wenig überfragt :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:56 Di 16.12.2003 | | Autor: | Marc |
Hallo Gloomer,
dann versuche ich es mal. Mit dem zweiten Semiring kann ich immer noch nichts anfangen, ich kann das inf nicht einordnen. Ich erwarte dort ein Verknüpfungszeichen, das zwei Elementen eln neues zuordnet. Mmh, vielleicht ist ja hier das infimum der beiden Elemente gemeint... das werde ich gleich mal probieren, zunächst aber zum ersten Ring.
Da ich nirgendwo eine elementare Definition eines Semiringes gefunden habe, stricke ich hier mal eine zusammen (ich orientiere mich da der zuvor zitierten Quelle):
Ein Semiring ist eine Algebra [mm] (A,\cdot,+,0,1)[/mm] über einer Menge [mm]A[/mm],
mit den Konstanten 0 und 1, wenn
a) [mm](A,\cdot,1)[/mm] ein Monoid ist,
b) [mm](A,+,0)[/mm] ein kommutatives Monoid ist,
c) [mm]\cdot[/mm] links und rechts distributiv bzgl. [mm]+[/mm] ist und
d) [mm]0\cdot a = a\cdot 0 = 0[/mm] für alle [mm]a \in A[/mm]
Jetzt noch die Definition eines Monoids:
Eine Menge M mit einer Verküpfung heißt Monoid, wenn
a) Die Verknüpfung assoziativ ist
b) Ein neutrales Element existiert
(Bei kommutativen Monoiden gilt zusätzlich das Kommutativgesetz.)
Ich probiere das mal für [mm] S= (\IB, \vee, \wedge, 0, 1 ) [/mm] (ist das eigentlich das, was man die Boole'sche Algebra nennt? Oder wird hier wert darauf gelegt, dass die Verküpfungen vertauscht sind?)
[mm]\IB[/mm] besteht ja bereits aus den beiden Elementen 0 und 1, also [mm]\IB =\{0,1\}[/mm].
Jetzt ist zu zeigen, dass [mm](\IB,\vee,1)[/mm] ein Monoid ist, also dass
a) das Assoziativgesetz gilt: Nehmen wir uns drei Elemente aus [mm]\IB[/mm] her und überprüfen, ob gilt:
[mm] (a\vee b)\vee c = a\vee (b\vee c) [/mm]
Als Informatiker wirst du wissen, wie man solch eine Gleichung überprüft. Ich würde eine Wahrheitstafel aufstellen, mit folgenden Spalten:
[mm]a,b,c,a\vee b,b\vee c,(a\vee b)\vee c,a\vee(b\vee c)[/mm]
In die ersten drei Spalten trägst du nun die acht Belegungskombinationen von [mm]a,b,c[/mm] ein, und berechnest spalten- und zeilenweise die restlichen Einträge der Tabelle.
b) Die Existenz eines neutralen Elements ist auch schnell überprüft. Falls es eines gibt, wird es [mm]0[/mm] sein. Du mußt nun zeigen, dass [mm]a\vee 0 = 0\vee a = a[/mm] gilt für alle [mm]a\in\IB[/mm], also für a=0 und a=1.
Das machst du auch mit einer Wahrheitstafel.
Weißt du nun, wie es weiter geht? Melde dich einfach, wenn du an einer Stelle nicht weiter kommst.
Zum zweiten Semiring schreibe ich gleich noch was.
Bis gleich,
Marc.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:00 Mi 17.12.2003 | | Autor: | Marc |
Hallo Gloomer,
betrachten wir nun den angeblichen Semiring
[mm] S= (\IR^+\cup\{\infty\}, \inf , +, \infty, 0)[/mm]
Ich verstehe den Operator [mm] \inf [/mm] als Abbildung [mm] \inf: M\times M \to M[/mm], definiert als [mm] (a,b)\mapsto \inf\{a,b\}[/mm]
So ist z.B. [mm]\inf\{1,2\}=1[/mm] oder [mm]\inf\{a,\infty\}=a[/mm] für alle [mm]a\in\IR^+\cup\{\infty\}[/mm].
Jetzt überprüfe dieselben Forderungen an einen Semiring, die du auch in dem ersten Semiring überprüft hast.
Zum Beispiel das Assoziativgesetz für [mm]\inf[/mm]:
[mm]\inf(\inf(a,b),c) \stackrel{?}{=} \inf(a,\inf(b,c))[/mm]
Was meinst du, gilt es, oder gilt es nicht?
Beachte, dass [mm]a,b[/mm] oder [mm]c[/mm] auch den Wert [mm]\infty[/mm] haben kann.
Interessant ist auch das Distributivgesetz. Zunächst das "von links":
[mm]\inf(a,b+c)\stackrel{?}{=}\inf(a,b)+\inf(a,c)[/mm]
Überprüfe das mal für [mm]a=1,b=2,c=3[/mm] und melde dich mit deinen Ergebnissen 
Bei Problemen kannst du dich natürlich auch wieder melden 
Viel Erfolg,
Marc
|
|
|
|
