[Theoretische Informatik] Komposition bzw Verknüpfung

nep

Hi,
Ich komme da bei einer Übungsaufgabe irgendwie nicht weiter, bzw weiß nicht was ich machen soll. Hoffe mir kann jemand helfen...

Sei M = {0,1}
a) Zählen sie alle verschiedene Funktionen f: M -> M auf.
Das ist ja noch einfach. Da hab ich dann folgendes:

f1:  0 -> 0
     1 -> 1

f2:  0 -> 1
     1 -> 0

f3:  0 -> 0
     1 -> 0

f4:  0 -> 1
     1 -> 1

Das ist soweit auch richtig (nehme ich doch mal an).

b) Verknüpfung dieser Funktionen sei die Komposition (Hinereinanderausführen). Stellen sie die Verknüpfungstafel auf.

Wie ist das gemeint ? Muss ich da dann sowas wie f1 o f2 o f3 o f4 machen oder wie ? Und was gibt das dann bzw was soll ich in diese Tafel reinschreiben ?

Außerdem wird dann noch als Zusatz gefragt ob die Verknüpfung kommutativ ist, und ob sie ein neutrales Element besitzt ?

fubar

Das [Theoretische Informatik] hat mich zwar eher abgeschreckt, aber ich versuche es trotzdem mal:
a) ist soweit richtig, würde ich sagen
b) mache eine Tabelle mit f1 o f1, f1 o f2, f1 o f3, f1 o f4 usw.
Wenn du die Tabelle fertig hast kannst du die Kommutativität überprüfen, indem du fi o fj mit fj o fi vergleichst. Neutrales Element e wäre e o f = f o e = f. Kann man dann eigentlich alles ablesen ... (Glaube ich zumindest.)

Edit:
$\begin{array}{ccccc} o & f\_1 & f\_2 & f\_3 & f\_4\\ f\_1\\ f\_2\\ f\_3\\ f\_4\end{array}$

nep

Hi, danke schon mal für die Hilfe

Was muss ich denn dann in die Tabelle reinschreiben ? Also angenommen ich mache z.B. f1 o f2: Dann muss ich doch praktisch die Wertemenge von f2 in f1 als Definitionsmenge verwenden, richtig oder ? Aber das gibt ja dann auch wieder die 0 und die 1. D.h. f1 o f2 wäre dasselbe wie f2 o f1. Und was müsste ich dann konkret hinschreiben an dieser Stelle in der Tabelle ? einfach die Zahlen die dabei rauskommen, oder wie ?

fubar

Machs doch so wie oben:

f1 o f1:  0 -> 0 
          1 -> 1

oder du schreibst einfach (kürzer) 
0
1

also jeweils
(fi o fj)(0)
(fi o fj)(1)

Jester

Naja, wenn Du zwei solche solche Funktion verknüpfst, dann kommt doch wieder so eine raus. Das heißt als Ergebnis erhältst Du wieder so ein f_i. Du mußt also nur nachschauen was die Verkettung mit 0 und 1 macht. Dann schaust Du nach welche Deiner Funktionen das ist und die trägst Du dann ein.

MfG Jester

nep

D.h. also dass z.B. f2 o f3 gleich f4 ergibt oder ?
Bei f3 kommt ja nur 0 raus, und das in f2 eingesetzt ergibt nur 1.
Und das ist ja in f4 der Fall, dass nur 1 rauskommt. Ist das richtig so ?

Jester

ja

nep

Ok danke, dann ist alles klar