 Boolische Funktionen darstellbar als "+" und " * " |
Gast
unregistriert
 |
|
| Boolische Funktionen darstellbar als "+" und " * " |
     |
Hallo,
hab mal eine Frage:
wir haben letztens Boolische Schaltalgebra durchgenommen und da bin ich auf ein Satz gestoßen, den ich so wirklich gar nicht verstehe.
Er lautet wie folgt:
"Jede n-stellige Boolesche Funktion ist allein darstellbar durch die 2-
stelligen Booleschen Funktionen „+“ und „ · “ sowie die 1-stellige
Boolesche Funktion „¯ “.
Anders ausgedrückt: {+, ·, ¯ } ist funktional vollständig"
Was bedeutet das??
Ich kann damit so wirklich gar nichts anfangen...
Dass eine Boolische Funktion als Summe ihrer einschlägigen Minterme darstellbar ist das hab ich noch verstanden und dass dies eine DNF ist auch. Aber der Satz hier....
Kann mir das hier jemand vielleicht erklären was das genau bedeutet?
Am besten anhand einer Veranschaulichung.
Und bitte erklärt mir was genau eine 2-Stellige Funktion "+" und " · “ ist, sowie die 1-stellige Boolesche Funktion „¯ “ und ganz wichtig: wie die aussieht.
Ich wäre sehr dankbar für eure Erklärungen.
mfG
|
|
05.02.2016 20:43 |
|
|
|
|
+ ist ein ODER. * ist ein UND. ¬ ist ein NICHT.
+ und * sind 2stellig, weil sie 2 Opernaden haben (x + y). ¬ ist einstellig, da nur ein Operand (¬x).
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
05.02.2016 20:54 |
|
|
Gast
unregistriert
|
|
Ok Vielen Dank erstmal für die Antwort,
das hab mich schon so ungefähr gedacht, heißt das also dass wenn ein Minterm ist:
x1 ^ x2 ^ ¬x3
und
x4^ ¬x5 ^ x6
(x entnommen aus der Boolischen Funktion f.)
und wenn die beiden als Summe mit "+" also einer Disjunktion " v " (ODER)
(x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6) ---> (das " ^ " ist ein UND)
diese Boolische Funktion f darstellen --> dann ist das die Bedeutung dieses Satzes bzw. das was der Satzt aussagt??
Das ist ja dann nichts anderes als eine andere Form der Sätze:
"Sei f : B^n --> B eine Boolesche Funktion und sei (x1 , x2 ,..., xn ) aus Bn.
Dann heißt das Produkt x1 x2 ...xn der Elemente von (x1 , x2 ,..., xn ) ein
Minterm von f."
und
"Jede Boolesche Funktion ist eindeutig darstellbar als Summe ihrer
einschlägigen Minterme."
und
Die Darstellung einer Booleschen Funktion durch einschlägige Minterme
heißt auch disjunktive Normalform (DNF) einer Booleschen Funktion.
Wenn das so ist, dann hab ich das Ganze verstanden und der Thread wäre erledigt.
Ich bedanke mich für die Antworten.
mfG
|
|
|
05.02.2016 22:05 |
|
|
|
|
"funktional vollständig" heißt einfach, dass du mit UND, ODER, NICHT jede boolshe Funktion darstellen kannst.
Sachen wie NAND, NOR, XOR kannst du aus UND, ODER, NICHT zusammenbauen.
NAND bzw. NOR sind alleine übrigens auch funktional vollständig.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
06.02.2016 08:05 |
|
|
Gast
unregistriert
|
|
Ja schon klar,
aber habe ich das richtig verstanden so wie ich das oben beschrieben habe??
Zitat:
"Ok Vielen Dank erstmal für die Antwort,
das hab mich schon so ungefähr gedacht, heißt das also dass wenn ein Minterm ist:
x1 ^ x2 ^ ¬x3
und
x4^ ¬x5 ^ x6
---> (das " ^ " ist ein UND)
(x entnommen aus der Boolischen Funktion f.)
und wenn die beiden als Summe mit "+" also einer Disjunktion " v " (ODER)
(x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6)
diese Boolische Funktion f darstellen --> dann ist das die Bedeutung dieses Satzes bzw. das was der Satzt aussagt??
Das ist ja dann nichts anderes als eine andere Form der Sätze:
"Sei f : B^n --> B eine Boolesche Funktion und sei (x1 , x2 ,..., xn ) aus Bn.
Dann heißt das Produkt x1 x2 ...xn der Elemente von (x1 , x2 ,..., xn ) ein
Minterm von f."
und
"Jede Boolesche Funktion ist eindeutig darstellbar als Summe ihrer
einschlägigen Minterme."
und
Die Darstellung einer Booleschen Funktion durch einschlägige Minterme
heißt auch disjunktive Normalform (DNF) einer Booleschen Funktion.
Wenn das so ist, dann hab ich das Ganze verstanden und der Thread wäre erledigt.
Ich bedanke mich für die Antworten.
mfG"
|
|
|
06.02.2016 15:50 |
|
|
|
|
| Zitat: |
| (x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6) |
hier hast du eine boolsche Funktion aus Mintermen aufgebaut, soweit richtig.
| Zitat: |
| diese Boolische Funktion f darstellen --> dann ist das die Bedeutung dieses Satzes bzw. das was der Satzt aussagt?? |
Hier kann ich keinen Zusammenhang erkennen. Deshalb habe ich nochmal auf die funktionale Vollständigkeit hingewiesen.
| Zitat: |
Das ist ja dann nichts anderes als eine andere Form der Sätze:
... |
nein. in den folgenden Sätzen wird beschrieben, wie eine boolsche Funktion aus Mintermen aufgebaut wird. Das hast du im ersten Satz nicht.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
06.02.2016 15:59 |
|
|
Gast
unregistriert
|
|
ich meinte eigentlich:
du hast ja selbst gesagt, dass man jede Boolishe Funktion mit UND, ODER, NICHT darstellen kann.
Zitat:
""funktional vollständig" heißt einfach, dass du mit UND, ODER, NICHT jede boolshe Funktion darstellen kannst."
und
dann hast du noch gesagt, dass das hier --> " (x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6)"
eine Darstellung der Boolischen Funktion ist
Zitat:
"(x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6)
hier hast du eine boolsche Funktion aus Mintermen aufgebaut, soweit richtig."
Und somit ist es ja genau das was der erste Satz aussagt:
"Jede n-stellige Boolesche Funktion ist allein darstellbar durch die 2-
stelligen Booleschen Funktionen „+“ und „ · “ sowie die 1-stellige
Boolesche Funktion „¯ “.
Anders ausgedrückt: {+, ·, ¯ } ist funktional vollständig"
Denn du hast noch selbst gesagt:
"+ ist ein ODER. * ist ein UND. ¬ ist ein NICHT.
+ und * sind 2stellig, weil sie 2 Opernaden haben (x + y). ¬ ist einstellig, da nur ein Operand (¬x)."
und da in der Darstellug der Funktion
"(x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6)"
zweistellige UND(s), ein zweistelliges ODER und ein einstelliges NICHT vorkommen ist das halt eben genau das (sry nochmal Zitat) was dieser Satzt aussagt:
"Jede n-stellige Boolesche Funktion ist allein darstellbar durch die 2-
stelligen Booleschen Funktionen „+“ und „ · “ sowie die 1-stellige
Boolesche Funktion „¯ “.
Anders ausgedrückt: {+, ·, ¯ } ist funktional vollständig"
richtig??
Ich wollte damit fragen ob ich das in soweit richtig verstanden habe?
Also ich denke schon.
Vielen Dank
|
|
|
06.02.2016 21:36 |
|
|
|
|
Sei so lieb und kopiere nur die relevanten Teile, ich habe keine Lust mir das alles durchzulesen, um deine Frage zu finden. Und markiere Zitate auch als solche.
| Zitat: |
| Zitat: |
| Zitat: |
| (x1 ^ x2 ^ ¬x3) v (x4 ^ ¬x5 ^ x6) |
hier hast du eine boolsche Funktion aus Mintermen aufgebaut, soweit richtig. |
Und somit ist es ja genau das was der erste Satz aussagt:
| Zitat: |
Jede n-stellige Boolesche Funktion ist allein darstellbar durch die 2-
stelligen Booleschen Funktionen „+“ und „ · “ sowie die 1-stellige
Boolesche Funktion „¯ “.
Anders ausgedrückt: {+, ·, ¯ } ist funktional vollständig" |
|
Eben nicht. Bei der Formel siehst du, dass diese eine Funktion mit UND, ODER, NICHT ausgedrückt weden kann.
Der Satz geht aber noch weiter: jede boolsche Funktion kann mit UND, ODER, NICHT gebaut werden.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
07.02.2016 09:05 |
|
|
Gast
unregistriert
|
|
hmmm schon klar,
im Großen und Ganzen hab ichs aber verstanden
Danke...
mfG
|
|
|
07.02.2016 15:26 |
|
|
|
