Boolesche Algebra

06.01.2005, 15:20

Moeki

Boolesche Algebra

Zitat:

Zeigen Sie, dass die Menge B aller Abbildungen $\begin{eqnarray*} f : \{0, 1\} ^2 \rightarrow \{0, 1\} \end{eqnarray*}$ mit den folgenden Verknüpfungen eine Boolesche Algebra ist:

$\begin{eqnarray*} (f \vee g)(x, y) := max \{ f(x, y), g(x, y) \}, \end{eqnarray*}$

$\begin{eqnarray*} (f \wedge g)(x, y) := min \{ f(x, y), g(x, y) \}, \end{eqnarray*}$

$\begin{eqnarray*} ( \neg f)(x, y) := 1, wenn f(x, y) = 0, \end{eqnarray*}$

$\begin{eqnarray*} ( \neg f)(x, y) := 0, wenn f(x, y) = 1, \end{eqnarray*}$

$\begin{eqnarray*} n(x, y) \equiv 0, e(x, y) \equiv 1. \end{eqnarray*}$

Ich muss also folgende Gesetze beweise.

1) Kommutativgesetz
2) Assoziativgesetz
3) Distriputivgesetz
4) idempotente Gesetze
5) Absorptions- bzw. Verschmelzungsgesetz
6) $\begin{eqnarray*} x \wedge \neg x = 0 ; x \vee \neg x = 1 \end{eqnarray*}$

Das haben wir in der Übung für $\begin{eqnarray*} f: \{ 0,1 \} \rightarrow \{ 0,1 \} \end{eqnarray*}$ gemacht.

Als Input kann man 0 und 1 nehmen, die vier Output Kombinationen sind $\begin{eqnarray*} f_1= 0 0; f_2 = 1 0; f_3 = 0 1; f_4 = 1 1 \end{eqnarray*}$

$\begin{eqnarray*} F_1 = \{ f_1 , f_2 , f_3 , f_4 \} \end{eqnarray*}$

Was ist jetzt der Unterschied zwischen $\begin{eqnarray*} f: \{ 0,1 \} \rightarrow \{ 0,1 \} \end{eqnarray*}$ und $\begin{eqnarray*} f : \{0, 1\} ^2 \rightarrow \{0, 1\} \end{eqnarray*}$ und was ist der genaue Zusammenhang zwischen der Menge der Abbildungen und den oben stehenden Verknüpfungen einer Boolesche Algebra (diesen habe ich nämlich nicht verstanden) ?

Danke für eure Hilfe.

06.01.2005, 21:45

quizzmaster

Auf diesen Beitrag antworten »

Bei der Boolschen Algebra gibts nur 0 und 1 also falsch und wahr.

zur 6) wenn x 1 ist dann gilt: $\begin{eqnarray*} 1(wahr) \wedge \neg 1(wahr) = 0 \end{eqnarray*}$ das entspricht wahr und nicht wahr (also falsch) = falsch

genauso gehts mit 0

zum zweiten Teil: $\begin{eqnarray*} 1(wahr) \vee \neg 1(wahr) = 1 \end{eqnarray*}$ entspricht: wahr oder nicht wahr (falsch) = wahr

genauso mit 0

aus oder wird immer wahr wenn einer der beiden ausdrücke (links oder rechts) wahr ist.

aus und wird immer wahr, wenn beide ausdrücke wahr sind.

07.01.2005, 13:50

Moeki

Auf diesen Beitrag antworten »

Das ist mir ja klar. Aber den Unterschied zwischen $\begin{eqnarray*} f: \{ 0,1 \} \rightarrow \{ 0,1 \} \end{eqnarray*}$ und $\begin{eqnarray*} f : \{0, 1\} ^2 \rightarrow \{0, 1\} \end{eqnarray*}$ verstehe ich nicht. Bzw. was ich da nun anders machen muss.

08.01.2005, 00:54

The_Lion

Auf diesen Beitrag antworten »

für B^n --> B^m gibt es $\begin{eqnarray*} (2^{m})^{2^{n}} \end{eqnarray*}$ verschiedene Outputs, also Funktionen $\begin{eqnarray*} f_i \end{eqnarray*}$ .

Bei deinem ersten Beispiel hast du z.B. B^1 --> B^1 , also B--> B

Du hast $\begin{eqnarray*} (2^{m})^{2^{n}} \end{eqnarray*}$ , also hier $\begin{eqnarray*} (2^{1})^{2^{1}} \end{eqnarray*}$ = $\begin{eqnarray*} (2^{2}= 4 \end{eqnarray*}$ verschiedene Outputs, Funktionen, die raus kommen. wie du bereits gesagt hast, sind dies.
f: 00, f_2 : 01, f_3 : 10 und f_4: 11

Bei B^2 --> B hast du 2^n (hier 2^2 = 4 inputs.)

das bedeutet, du hast nach der formel oben nun 16 funktionen, die rauskommen.

eine tabelle wäre die hier:
x y f1 f2 . . . . f_16
0 0
0 1
1 0
1 1

hier sind die beiden Inputs x und y. Um alle Kombinationen von Nullen und einsen zu erhalten, zählst du einfach binär durch, also 00, 01, 10 11 in diesem Falle.

ich kann dir ein Buch empfehlen wenn du möchtest. Augenzwinkern

09.01.2005, 22:11

Tovok7

Auf diesen Beitrag antworten »

Also mein Problem bei der Sache ist ja das Distributivgesetz zu beweisen.
Ich fange z.B. hier an: $\begin{eqnarray*} (f\wedge(g \vee h)) (x,y) = min\lbrace f(x, y), max\lbrace g(x,y), h(x,y) \rbrace \rbrace \end{eqnarray*}$

und forme das in das hier um: $\begin{eqnarray*} ((f \wedge g) \vee (f \wedge h)) (x,y) = max\lbrace min\lbrace f(x,y), g(x,y)\rbrace , min\lbrace f(x,y), h(x,y)\rbrace \rbrace \end{eqnarray*}$

Die Frage ist nur, wie mache ich das? Eine Fallunterscheidung fuer jeweils alle 6 Faelle fuer beide Gleichungen?

10.01.2005, 18:12

Moeki

Auf diesen Beitrag antworten »

Zitat:

Original von The_Lion

ich kann dir ein Buch empfehlen wenn du möchtest. Augenzwinkern

Sofern es mir bei der Lösung dieser Aufgabe weiterhilft, wäre ich dir sehr verbunden Augenzwinkern

11.01.2005, 17:30

Tovok7

Auf diesen Beitrag antworten »

Ich glaube, es lohnt sich nicht extra fuer das Loesen einer Uebungs-Aufgabe ein Buch anzuschaffen.
Hat denn niemand eine Ahnung, wie das Distributivgesetz hier bewiesen werden kann?

Neue Frage »

Antworten »

Boolesche Algebra

Verwandte Themen