verkettete Äquivalenz < Technische Inform. < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:20 Sa 04.02.2006 | | Autor: | heine789 |
Hallo zusammen.
Habe folgende Frage:
Ich soll den Fkt.-Wert der Funktion g(f,e,d,c,b,a) = a [mm] \gdw [/mm] b [mm] \gdw [/mm] c [mm] \gdw [/mm] d [mm] \gdw [/mm] e [mm] \gdw [/mm] f
an der Stelle 12 u 43 (in oktal angegeben) bestimmen.
[mm] \gdw [/mm] := äquivalent
Die Belegung sind also so aus:
12: 001010
43: 100011
Ich glaube, dass ich mal gehört habe, dass wenn die Anzahl der 0en gerade ist, eine so definierte Funktion den Fkt.-Wert 1 hat.
Demnach hat die Fkt. an der Stelle 12 den Wert 1, und an der Stelle 43 den Wert 0.
Kann mir jemand das bestätigen oder mich berichtigen?
Vielen Dank!
Gruß heine
|
|
| |
|
Hallo heine,
> Ich soll den Fkt.-Wert der Funktion
> [mm]g(f,e,d,c,b,a) = a \gdw b \gdw c \gdw d \gdw e \gdw f[/mm]
> an der Stelle 12 und 43 (in oktal angegeben) bestimmen.
> [mm]\mathrel{\gdw \mathord{:}\mathord{=}} \texttt{"aquivalent}[/mm]
> Die Belegung sieht also so aus:
>
> 12: 001010
> 43: 100011
>
> Ich glaube, dass ich mal gehört habe, dass wenn die Anzahl
> der 0en gerade ist, eine so definierte Funktion den
> Fkt.-Wert 1 hat.
>
> Demnach hat die Fkt. an der Stelle 12 den Wert 1, und an
> der Stelle 43 den Wert 0.
Um das festzustellen, sollte es doch reichen eine Wertetabelle dieser Funktion anzugeben. Zuvor sollte man vielleicht noch die Äquivalenzzeichen "loswerden".
Zwei unterschiedliche Boolesche Werte können nicht äquivalent sein, zwei Gleiche hingegen schon; Also gilt:
[mm]\mathrm{gdw}(a, b) \equiv ab+\bar{a}\bar{b}[/mm]
Damit können wir die obige Funktion anders darstellen:
[mm]g(a,\dotsc,f) = \mathrm{gdw}(a, \mathrm{gdw}(b, \mathrm{gdw}(c, \mathrm{gdw}(d, \mathrm{gdw}(e, f)))))[/mm]
Da das Aufstellen einer Wertetabelle mit immerhin [mm] $2^6 [/mm] = 64$ Belegungen per Hand etwas aufwendig wäre, lassen wir den Computer mal ran.
Folgendes Programm bastelt uns eine [mm]\texttt{{\large\LaTeX}-Wertetabelle}[/mm] für die Funktion:
| 1: |
| | 2: | #include <math.h>
| | 3: | #include<iostream>
| | 4: | #include <fstream>
| | 5: | using namespace std;
| | 6: |
| | 7: | int g(int inpt[], int reclevel = 0)
| | 8: | {
| | 9: | if(reclevel == 4)
| | 10: | return ( (inpt[4] && inpt[5]) || (!inpt[4] && !inpt[5]) );
| | 11: |
| | 12: | return ((inpt[reclevel] && g(inpt, reclevel+1)) ||
| | 13: | (!inpt[reclevel] && !g(inpt, reclevel+1)) );
| | 14: | }
| | 15: |
| | 16: | void schreibeWerte(ofstream& channel)
| | 17: | {
| | 18: | int values[6];
| | 19: |
| | 20: | for(int inptnum = 0; inptnum <= 63; inptnum++)
| | 21: | {
| | 22: | // baue Eingabe fuer g auf ...
| | 23: | int zahl = inptnum;
| | 24: | bool bAnzahlNullenGerade = true;
| | 25: |
| | 26: | for(int n = 0; n <= 5; n++)
| | 27: | {
| | 28: | values[5-n] = zahl % 2;
| | 29: | if(values[5-n] == 0)
| | 30: | bAnzahlNullenGerade = !bAnzahlNullenGerade;
| | 31: | zahl /= 2;
| | 32: | }
| | 33: |
| | 34: | for(int n = 0; n <= 5; n++)
| | 35: | channel << values[n] << " & ";
| | 36: |
| | 37: | // uebergebe Eingabe an g ...
| | 38: | if(bAnzahlNullenGerade)
| | 39: | channel << "\\textcolor{red}{" << g(values) << "}";
| | 40: | else channel << g(values);
| | 41: |
| | 42: | if(inptnum < 63)
| | 43: | channel << "\\\\\\hline" << endl;
| | 44: | }
| | 45: | }
| | 46: |
| | 47: | int main(int argc, char* argv[])
| | 48: | {
| | 49: | ofstream wtab("wertetabelle.txt");
| | 50: |
| | 51: | // "Everything that has a beginning ...
| | 52: | wtab << "\\begin{array}{cccccc|c}" << endl << "a & b & c & d & e & f & g\\\\\\hline"
| | 53: | << endl;
| | 54: |
| | 55: | schreibeWerte(wtab);
| | 56: |
| | 57: | // "... has an end."
| | 58: | wtab << endl << "\\end{array}";
| | 59: |
| | 60: | return 0;
| | 61: | }
|
'schreibeWerte' funktioniert so, daß alle Werte von 0 bis [mm] $2^6-1$ [/mm] durchlaufen werden. Dabei wird dann jeder Wert in den Zeilen 26-32 in eine Binärzahl umgewandelt und die Werte werden in einem Array gespeichert, welcher an g übergeben wird. g ist nach der obigen Formel für Äquivalenz rekursiv realisiert (ebenfalls oben angegeben gdw(...)).
Bei der Konvertierung zur Binärzahl wird überprüft, ob die Anzahl der Nullen in der Binärzahl gerade ist. Dafür wird einfach die Tatsache ausgenutzt, daß sich gerade und ungerade Zahlen immer abwechseln, weshalb man hier nur den Wert einer booleschen Variablen "hin und her zu schalten" braucht. War die Anzahl der Nullen bei einer Eingabe gerade, wird die Ausgabe von g rot dargestellt. Das ist das Wichtigste am Programm (der Rest ist nur Formatierung der Ausgabe.) Und hier ist die Ausgabe des Programms (Kommentar siehe unten  ):
[mm]\begin{array}{cccccc|c}
a & b & c & d & e & f & g\\\hline
0 & 0 & 0 & 0 & 0 & 0 & \textcolor{red}{1}\\\hline
0 & 0 & 0 & 0 & 0 & 1 & 0\\\hline
0 & 0 & 0 & 0 & 1 & 0 & 0\\\hline
0 & 0 & 0 & 0 & 1 & 1 & \textcolor{red}{1}\\\hline
0 & 0 & 0 & 1 & 0 & 0 & 0\\\hline
0 & 0 & 0 & 1 & 0 & 1 & \textcolor{red}{1}\\\hline
0 & 0 & 0 & 1 & 1 & 0 & \textcolor{red}{1}\\\hline
0 & 0 & 0 & 1 & 1 & 1 & 0\\\hline
0 & 0 & 1 & 0 & 0 & 0 & 0\\\hline
0 & 0 & 1 & 0 & 0 & 1 & \textcolor{red}{1}\\\hline
0 & 0 & 1 & 0 & 1 & 0 & \textcolor{red}{1}\\\hline
0 & 0 & 1 & 0 & 1 & 1 & 0\\\hline
0 & 0 & 1 & 1 & 0 & 0 & \textcolor{red}{1}\\\hline
0 & 0 & 1 & 1 & 0 & 1 & 0\\\hline
0 & 0 & 1 & 1 & 1 & 0 & 0\\\hline
0 & 0 & 1 & 1 & 1 & 1 & \textcolor{red}{1}\\\hline
0 & 1 & 0 & 0 & 0 & 0 & 0\\\hline
0 & 1 & 0 & 0 & 0 & 1 & \textcolor{red}{1}\\\hline
0 & 1 & 0 & 0 & 1 & 0 & \textcolor{red}{1}\\\hline
0 & 1 & 0 & 0 & 1 & 1 & 0\\\hline
0 & 1 & 0 & 1 & 0 & 0 & \textcolor{red}{1}\\\hline
0 & 1 & 0 & 1 & 0 & 1 & 0\\\hline
0 & 1 & 0 & 1 & 1 & 0 & 0\\\hline
0 & 1 & 0 & 1 & 1 & 1 & \textcolor{red}{1}\\\hline
0 & 1 & 1 & 0 & 0 & 0 & \textcolor{red}{1}\\\hline
0 & 1 & 1 & 0 & 0 & 1 & 0\\\hline
\end{array}[/mm]
[mm]\begin{array}{cccccc|c}
0 & 1 & 1 & 0 & 1 & 0 & 0\\\hline
0 & 1 & 1 & 0 & 1 & 1 & \textcolor{red}{1}\\\hline
0 & 1 & 1 & 1 & 0 & 0 & 0\\\hline
0 & 1 & 1 & 1 & 0 & 1 & \textcolor{red}{1}\\\hline
0 & 1 & 1 & 1 & 1 & 0 & \textcolor{red}{1}\\\hline
0 & 1 & 1 & 1 & 1 & 1 & 0\\\hline
1 & 0 & 0 & 0 & 0 & 0 & 0\\\hline
1 & 0 & 0 & 0 & 0 & 1 & \textcolor{red}{1}\\\hline
1 & 0 & 0 & 0 & 1 & 0 & \textcolor{red}{1}\\\hline
1 & 0 & 0 & 0 & 1 & 1 & 0\\\hline
1 & 0 & 0 & 1 & 0 & 0 & \textcolor{red}{1}\\\hline
1 & 0 & 0 & 1 & 0 & 1 & 0\\\hline
1 & 0 & 0 & 1 & 1 & 0 & 0\\\hline
1 & 0 & 0 & 1 & 1 & 1 & \textcolor{red}{1}\\\hline
1 & 0 & 1 & 0 & 0 & 0 & \textcolor{red}{1}\\\hline
1 & 0 & 1 & 0 & 0 & 1 & 0\\\hline
1 & 0 & 1 & 0 & 1 & 0 & 0\\\hline
1 & 0 & 1 & 0 & 1 & 1 & \textcolor{red}{1}\\\hline
1 & 0 & 1 & 1 & 0 & 0 & 0\\\hline
1 & 0 & 1 & 1 & 0 & 1 & \textcolor{red}{1}\\\hline
1 & 0 & 1 & 1 & 1 & 0 & \textcolor{red}{1}\\\hline
1 & 0 & 1 & 1 & 1 & 1 & 0\\\hline
1 & 1 & 0 & 0 & 0 & 0 & \textcolor{red}{1}\\\hline
1 & 1 & 0 & 0 & 0 & 1 & 0\\\hline
1 & 1 & 0 & 0 & 1 & 0 & 0\\\hline
1 & 1 & 0 & 0 & 1 & 1 & \textcolor{red}{1}\\\hline
1 & 1 & 0 & 1 & 0 & 0 & 0\\\hline
1 & 1 & 0 & 1 & 0 & 1 & \textcolor{red}{1}\\\hline
1 & 1 & 0 & 1 & 1 & 0 & \textcolor{red}{1}\\\hline
1 & 1 & 0 & 1 & 1 & 1 & 0\\\hline
1 & 1 & 1 & 0 & 0 & 0 & 0\\\hline
1 & 1 & 1 & 0 & 0 & 1 & \textcolor{red}{1}\\\hline
1 & 1 & 1 & 0 & 1 & 0 & \textcolor{red}{1}\\\hline
1 & 1 & 1 & 0 & 1 & 1 & 0\\\hline
1 & 1 & 1 & 1 & 0 & 0 & \textcolor{red}{1}\\\hline
1 & 1 & 1 & 1 & 0 & 1 & 0\\\hline
1 & 1 & 1 & 1 & 1 & 0 & 0\\\hline
1 & 1 & 1 & 1 & 1 & 1 & \textcolor{red}{1}
\end{array}[/mm]
Es fällt auf, daß nur die Einsen rot markiert wurden. Demnach hast Du mit deiner Behauptung recht. Im Nachhinein ist mir auch während der Programmierung klar geworden warum, denn sortiert man alle Ziffern einer Eingabe aufsteigend, so kann man eine gerade Anzahl von Nullen in Paare gleicher Ziffern aufspalten, für die die Äquivalenz gilt. Demnach kann man deine Aussage noch erweitern. Soll g 1 liefern, muß die Anzahl der Nullen und Einsen in der Eingabe gerade sein. Beweis siehe Tabelle, wo ja alle Möglichkeit durchprobiert worden sind.  [mm] $\Box$
[/mm]
Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:58 So 05.02.2006 | | Autor: | heine789 |
Vielen Dank!
Da hast du dir aber eine Menge Arbeit gemacht!
Gruß Alwin
|
|
|
|
