Die Mathe-Redaktion - 18.02.2020 07:21 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 438 Gäste und 2 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Buri Gockel
Strukturen und Algebra » Ringe » Ring der Funktionen von {0,1}^n in einen Ring
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Ring der Funktionen von {0,1}^n in einen Ring
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-13


Hallo Community,
hier vier kurze algebraische Fragen; es sieht nur komplizierter aus, weil ich auch gleich die Hintergründe dazu abgetippt habe:

Sei R ein kommutativer Ring mit Eins und sei $F_{R,n}$ die Menge aller Funktionen von $\{0,1\}^n$ nach R.
Dann ist $F_{R,n}$ selbst wieder ein kommutativer Ring unter punktweiser Addition und Multiplikation von Funktionen. --> 1. Frage: Ist das wieder ein Ring mit Eins?
Insbesondere enthält $F_{R,n}$ die Menge aller Booleschen Funktionen $f: \{0,1\}^n \rightarrow \{0,1\}$ als Teilmenge.

Ein Polynom $P(x_1, \dotsc, x_n)$ mit Koeffizienten in R repräsentiert die Funktion in $F_{R,n}$, die durch $(a_1, \dotsc, a_n) \mapsto P(a_1, \dotsc, a_n)$ gegeben ist.
Ist $a = (a_1, \dotsc, a_n) \in \{0,1\}^n$, dann kann die Funktion $\chi_a: \{0,1\}^n \rightarrow \{0,1\}$, definiert durch $\chi_a(b) = \begin{cases}1, \quad \text{wenn a = b}\\0, \quad \text{sonst}\end{cases}$ durch das Polynom $(\prod\limits_{\{i: a_i = 1\}}x_i)(\prod\limits_{\{i: a_i \neq 1\}} (1-x_i))$ repräsentiert werden.
Ist $f \in F_{R,n}$, dann ist $f = \sum\limits_{a \in \{0,1\}}^n f(a) \chi_a$, also kann jede Funktion in $F_{R,n}$ durch ein Polynom repräsentiert werden.
Da $x_i^2$ und $x_i$ das gleiche Element von $F_{R,n}$ repräsentieren [--> 2. Frage: Wieso repräsentieren sie das gleiche Element, wie sieht man das?], kann jede Funktion durch eine R-lineare Kombination der Monome $X_I = \prod\limits_{i \in I}x_i$, wobei $I \subseteq \{1, \dotsc, n\}$ und $X_{\emptyset}:=1$ repräsentiert werden. --> 3. Frage: Wieso kann deshalb jede Funktion durch eine solche Kombination repräsentiert werden? (Hat jemand vlt. ein konkretes Beispiel dafür, das zum Verständnis beitragen könnte?)

Ist R ein Körper, dann hat $F_{R,n}$ auch die Struktur eines Vektorraumes über R und ist eine R-Algebra der Dimension $2^n$. In diesem Fall bilden die Monome $X_I$ eine Vektorraumbasis. --> 4. Frage: Aus welchen Sätzen o.Ä. folgt das mit dem Vektorraum und der R-Algebra und wie überlegt man sich das mit der Dimension und der Vektorraumbasis?



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2660
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-13


Hallo,

wahrscheinlich können viele deine Fragen besser beantworten als ich.

2020-01-13 16:40 - Newmath2012 im Themenstart schreibt:
1. Frage: Ist $F_{R,n}$ wieder ein Ring mit Eins?
Insbesondere enthält $F_{R,n}$ die Menge aller Booleschen Funktionen \[f\colon \{0,1\}^n \to \{0_R,1_R\}\] als Teilmenge?

Beide Fragen lassen sich mit Ja beantworten.

Wenn du $f\in F_{R,n}$ mit $f(x)=1_R$ für alle $x\in R$ betrachtest, so sollte $f$ das Eins-Element von $F_{R,n}$ sein. Dies solltest du aber auf jeden Fall einmal nachrechnen.
Im Allgemeinen müssen bei einem Ring mit Eins $0_R$ und $1_R$ nicht verschieden sein, so ist $R:=\{0_R\}$ mit $0_R=0_R+0_R$ und $0_R=0_R\cdot 0_R$ auch ein Ring mit Eins. Müssen Booleschen Funktionen zwei verschiedene Funktionswerte annehmen können?


2. Frage: Wieso repräsentieren $x$ und $x^2$ das gleiche Element, wie sieht man das?
Es gilt $1_R^2=1_R$ und $0_R^2=0_R$. Insbesondere folgt $f(x)\cdot f(x)=f(x)$ für alle $f$ mit
\[f\colon \{0,1\}^n \to \{0_R,1_R\}\]

 3. Frage: Wieso kann deshalb jede Funktion durch eine solche Kombination repräsentiert werden? (Hat jemand vlt. ein konkretes Beispiel dafür, das zum Verständnis beitragen könnte?)
Denke dir selbst eins aus :P Immerhin gibt dir der Beweis eine explizite Konstruktion.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-13


Danke für deine Antworten, ochen! :)

1. Wie Boolesche Funktionen genau definiert sind, weiß ich leider auch nicht. Wikipedia zufolge scheint es mir aber schon so zu sein.



2. Das bedeutet aber, dass nur gilt, dass $x$ und $x^2$ das gleiche Element repräsentieren, wenn wir nur Funktionen betrachten, die nach $\{0_R,1_R\}$ abbilden und nicht nach ganz R?



3. An einem nicht trivialen Beispiel bastle ich derzeit noch...



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2660
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-01-13


2020-01-13 18:14 - Newmath2012 in Beitrag No. 2 schreibt:
2. Das bedeutet aber, dass nur gilt, dass $x$ und $x^2$ das gleiche Element repräsentieren, wenn wir nur Funktionen betrachten, die nach $\{0_R,1_R\}$ abbilden und nicht nach ganz R?

Das ist wahr. Mehr wollen wir aber auch gar nicht.



3. An einem nicht trivialen Beispiel bastle ich derzeit noch...

Nimm $R=\mathbb{Z}/3\mathbb{Z}$ und $n=1$, wie viele Funktionen $f\colon \{0,1\}\to R$ gibt es?
Wie viele Polynome $p\in R_{\leq 1}[X]$ gibt es? Damit meine ich univariate Polynome mit einem Grad von höchstens Eins.

Kennst du Elementarfunktionen aus Ana3? Weißt du noch, wie sie als Linearkombinationen von Indikatorfunktionen dargestellt werden konnten?


Wird irgendwo erwähnt, dass $R$ endlich ist?



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-01-19


Zu deinem Beispiel mit $R = \mathbb{Z}/3\mathbb{Z}$:
Ich hätte gedacht, es gibt $2^3$ Funktionen, weil wir 3 Möglichkeiten haben, die Funktionswerte zu den 2 Urbildern zu belegen. Aber wenn ich mir alle aufschreibe, komme ich auf folgende 9 (wobei die erste Spalte angibt, worauf 0 abgebildet wird, und die zweite, worauf 1):
00
01
02
10
20
11
12
21
22
Irgendwie muss es bei den $2^3$ also einen Haken geben...

Was die Polynome betrifft, weiß ich leider nicht genau, was du meinst. Ich würde aber sagen, es sind 0 und 1 Polynome vom Grad 0, x ist ein Polynom vom Grad 1, x + 0 ist ein Polynom vom Grad 1, x + 1 ist ein Polynom vom Grad 1 und x + 0 + 1 ist ein Polynom vom Grad 1. Das wären dann also 6?
Elementare Funktionen sind mir kein Begriff (wobei ich Ana3 aber gehört und abgeschlossen habe). Ich kenne Treppenfunktionen, die aus Indikatorfunktionen aufgebaut werden. Und ich habe den Wikipedia-Artikel zu "elementare Funktionen" gelesen, glaube aber nicht, dass es das ist, was du meinst.



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2660
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-01-20


2020-01-19 18:51 - Newmath2012 in Beitrag No. 4 schreibt:
Zu deinem Beispiel mit $R = \mathbb{Z}/3\mathbb{Z}$:
Ich hätte gedacht, es gibt $2^3$ Funktionen, weil wir 3 Möglichkeiten haben, die Funktionswerte zu den 2 Urbildern zu belegen. Aber wenn ich mir alle aufschreibe, komme ich auf folgende 9 (wobei die erste Spalte angibt, worauf 0 abgebildet wird, und die zweite, worauf 1):
00
01
02
10
20
11
12
21
22
Irgendwie muss es bei den $2^3$ also einen Haken geben...
Neun ist schon richtig. Wir bilden $\{0,1\}$ auf $\mathbb{Z}/3\mathbb{Z}$ ab und nicht umgekehrt. Deshalb haben wir für 0 genau 3 Möglichkeiten einen Funktionswert zu wählen und für 1 genau 3 Möglichkeiten einen Funktionswert zu wählen.
 

Was die Polynome betrifft, weiß ich leider nicht genau, was du meinst. Ich würde aber sagen, es sind 0 und 1 Polynome vom Grad 0,
x ist ein Polynom vom Grad 1, x + 0 ist ein Polynom vom Grad 1,
Das sind doch die selben Polynome :(


 x + 1 ist ein Polynom vom Grad 1 und x + 0 + 1 ist ein Polynom vom Grad 1.
Das sind wieder die gleichen.

Wenn $R=\mathbb{Z}/3\mathbb{Z}$ ist, dann enthält $R_{\leq 1}[X]$ genau die Polynome
\[0,\ 1,\ 2,\ X,\ X+1,\ X+2,\ 2X,\ 2X+1,\ 2X+2.\] Kannst du diese deinen Funktionen $f\colon \{0,1\}\to\mathbb{Z}/3\mathbb{Z}$ zu ordnen?


Elementare Funktionen sind mir kein Begriff (wobei ich Ana3 aber gehört und abgeschlossen habe). Ich kenne Treppenfunktionen, die aus Indikatorfunktionen aufgebaut werden. Und ich habe den Wikipedia-Artikel zu "elementare Funktionen" gelesen, glaube aber nicht, dass es das ist, was du meinst.

Hm, nein, eigentlich meinte ich Funktionen $\mathbb R\to\mathbb R$, die nur endlich viele unterschiedliche Werte aus $\mathbb R$ annehmen. Diese lassen sich als Linearkombinationen von Indikatorfunktionen schreiben. Ganz analog geht das hier auch.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-01-21 16:17


Die Polynome zuzordnen, schaffe ich zwar, glaube ich, aber wie das die urspr. Frage klärt, verstehe ich noch nicht. Der Index bei $R_{\leq 1}$ bedeutet, dass die Variablen nur mit 0 oder 1 belegt werden dürfen, ja? Also:

00: 0
11: 1
22: 2
01: X
12: X+1
20: X+2
02: 2X
10: 2X+1
21: 2X+2



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]