Shannon und Logik < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:19 Mo 07.11.2011 | | Autor: | Deztiny |
| Aufgabe | "Shannon Zerlegung"
In dieser Aufgabe betrachten wir nur solche Formeln, die ausschließlich die Junktoren [mm] \wedge, \vee [/mm] und [mm] \neg [/mm] enthalten. Mit Hilfe von Wahrheitstafeln lässt sich jeder Formel F eine boolsche Funktion [F] : [mm] {0,1}^{n} \to [/mm] {0,1} zuweisen. Die Shannon-Zerlegung zeigt die Umkehrung. Für jede boolsche Funktion f : [mm] {0,1}^{n} \to [/mm] {0,1} gibt es eine Formel F mit f = [F]. Für n = 1 benutzt man dazu die Formeln A1, [mm] \negA1, [/mm] (A1 [mm] \wedge \negA1), [/mm] (A1 [mm] \vee \negA1). [/mm] Für n > 1 existieren nach Induktion Formeln [mm] F_{1}, F_{0}, [/mm] mit [mm] f_{1} [/mm] = [mm] [F_{1}] [/mm] und [mm] f_{0} [/mm] = [mm] [F_{0}] [/mm] wobei [mm] f_{1}(A_{1},...,A_{n-1}):= f(A_{1},...,A_{n-1},1) [/mm] und [mm] f_{0}(A_{1},...,A_{n-1}):= f(A_{1},...,A_{n-1},0).
[/mm]
Wir setzen dann F = [mm] ((A_{n} \wedge F_{1}) \vee (\negA_{n} \wedge F_{0})).
[/mm]
a.) Die folgende Tabelle beschreibt eine boolsche Funktion f. Finden sie mit obigem Verfahren eine Formel F, so dass [F] = f gilt.
A B C | f
0 0 0 | 1
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 1
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1
b.) Beweisen Sie mit HIlfe der oben beschriebenen Zerlegung: Für jede boolsche Funktion f : {0,1} [mm] \to [/mm] {0,1}, gibt es eine Formel F mit [F] = f und |F| [mm] \le 12(2^{n}-1). [/mm] Dabei bezeichne |F| die Anzahl der Symbole "(", ")", [mm] "\neg", "\wedge", "\vee" "A_{i}" [/mm] in F. |
Hi,
ich habe schon lange gegoogelt und versucht mich über Shannon zu informieren, jedoch landet man auf eher technischen Seiten, die dann mit Schaltkreisen zu tun haben (was ja auch logisch ist). Daher bin ich immer noch nicht viel schlauer.
Zu a.)
Wir haben gelernt, wie man aus einer Wahrheitstabelle eine DNF (disjunktive Normalform) oder KNF (konjunktive Normalform) lesen kann, aber das ist (soweit ich verstanden habe) nicht in dieser Aufgabe gefragt.
gefragt ist eine Lösung mit der letzten gegebenen Formel des Bescheibungstextes: " F = [mm] ((A_{n} \wedge F_{1}) \vee (\negA_{n} \wedge F_{0})). [/mm] "
Es wäre nett, wenn mir jemand ansatzweise erklären könnte, wie man aus dieser (oder einer anderen Tabelle) etwa eine Formel F nach "Shannon-Zerlegung" auslesen könnte.
Ist evtl eine Art Shannonsche Normalform gefragt?
mit f = A [mm] \wedge [/mm] ( B [mm] \wedge [/mm] ( 1 [mm] \wedge [/mm] C [mm] \vee [/mm] 0 [mm] \wedge \neg [/mm] C ) [mm] \vee \neg [/mm] B [mm] \wedge [/mm] ( 1 [mm] \wedge [/mm] C [mm] \vee [/mm] 1 [mm] \wedge \neg [/mm] C ) ) [mm] \vee \neg [/mm] A [mm] \wedge [/mm] ( B [mm] \wedge [/mm] ( 1 [mm] \wedge [/mm] C [mm] \vee [/mm] 0 [mm] \negC [/mm] ) [mm] \vee \neg [/mm] B [mm] \wedge [/mm] ( 0 [mm] \wedge [/mm] C [mm] \vee [/mm] 1 [mm] \wedge \negC [/mm] ) )
(das habe ich allerdings auch recherchiert, genaueres dazu weiß ich nicht)
Ein Ansatz zu b.) wäre auch nciht schlecht, da ich da komplett auf dem Schlauch stehe :(
(ich sitze seit 3 Tagen an dieser Aufgabe, und komme nicht viel weiter)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Fr 11.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
