Formel mit k Belegungen < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:52 Mo 14.10.2013 | | Autor: | Haeger |
| Aufgabe | | Sei n groß, k [mm] \le 2^n. [/mm] Geben Sie eine Formel in den Variablen [mm] p_1,...,p_n [/mm] an, die von genau k Belegungen erfüllt wird. Versuchen Sie eine möglichst kleine Formel zu finden (mit etwa O(n) Symbolen) |
Ahoi, ich hoffe ihr könnt mir hier weiter helfen.
ich habe bis jetzt versucht eine konstruktion aufgrund der binär darstellung von k zu entwickeln welche mir auch genau die k belegungen liefert. Allerdings bewege ich mic hier in einem bereich von [mm] O(n^2)
[/mm]
Hat hier jemand einen neuen kreativen Ansatz?
Vielen Dank schonmal im voraus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo Haeger, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Du bist einer Lösung näher als Du denkst.
> Sei n groß, k [mm]\le 2^n.[/mm] Geben Sie eine Formel in den
> Variablen [mm]p_1,...,p_n[/mm] an, die von genau k Belegungen
> erfüllt wird. Versuchen Sie eine möglichst kleine Formel
> zu finden (mit etwa O(n) Symbolen)
> Ahoi, ich hoffe ihr könnt mir hier weiter helfen.
> ich habe bis jetzt versucht eine konstruktion aufgrund der
> binär darstellung von k zu entwickeln
Sehr gute Idee.
> welche mir auch
> genau die k belegungen liefert.
Hier weist das kleine Wort "die" auf eine Denkblockade hin. Die Aufgabe gibt nicht vor, dass die k Belegungen beliebig gewählt sind! Es genügt eine Formel, die in genau k Fällen wahr ist, egal welche k Fälle das sind. Das darf die Formel also sogar festlegen.
> Allerdings bewege ich mic
> hier in einem bereich von [mm]O(n^2)[/mm]
Ja, kleiner wird es bei einem vorgegebenen "Set" auch nicht werden können.
> Hat hier jemand einen neuen kreativen Ansatz?
> Vielen Dank schonmal im voraus
Wo Du doch schon bei den Binärzahlen warst...
Kommst Du selbst drauf?
Grüße
reverend
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:53 Mo 14.10.2013 | | Autor: | Haeger |
Danke schon mal für deine schnelle antwort.
der teil mit den k belegungen war leider schlecht formuliert. mir ist schon klar, dass es reicht eine formel zu finden die für k beliebige belegungen erfüllt ist.
ich bräuchte eher einen kleinen tipp für die eine elegante bildungsvorschrift für eine solche formel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:13 Mo 14.10.2013 | | Autor: | tobit09 |
Hallo Haeger und herzlich !
Nachdem ich nun etwa vier Stunden an der Aufgabe rumprobiert habe, habe ich eine Möglichkeit gefunden, die mit einer Formel der Länge von Größenordnung O(n) auskommt.
Gekommen bin ich darauf wie gesagt durch Rumprobieren mit $k=0$ bis $k=8$. Der Nachweis, dass meine Lösung es tut, ist jedoch deutlich einfacher als das Finden dieser Lösung.
Zu gegebenem k und n basteln wir uns die gesuchte Formel [mm] $F_{n,k}$ [/mm] wie folgt:
Falls $k=0$, wählen wir einfach irgendeine immer falsche Formel wie z.B.
[mm] $F_{n,k}:=p_1\wedge\neg p_1$.
[/mm]
Diese leistet im Fall $k=0$ offensichtlich das Gewünschte.
Sei nun [mm] $k\ge [/mm] 1$. Dann ist [mm] $0\le k-1\le 2^n-1$ [/mm] und wir können die Zahl $k-1$ binär darstellen durch [mm] $a_{n-1}a_{n-2}\ldots a_1a_0$ [/mm] für gewisse [mm] $a_0,\ldots,a_{n-1}\in\{0,1\}$. [/mm] Es gilt also
[mm] $k-1=\summe_{i=0}^{n-1}a_i2^i$.
[/mm]
Nun definieren wir für [mm] $a\in\{0,1\}$ [/mm] den Junktor [mm] $\overline{a}$ [/mm] durch
[mm] $\overline{a}:=\begin{cases}\wedge,&\text{falls }a=0\\\vee,&\text{falls }a=1\end{cases}$.
[/mm]
Sei $T$ irgendeine immer erfüllte Formel, z.B. [mm] $T:=p_1\vee\neg p_1$.
[/mm]
Dann sei [mm] $F_{n,k}$ [/mm] definiert durch
[mm] $F_{n,k}:=(\ldots((((T)\,\overline{a_0}\,p_1)\,\overline{a_1}\,p_2)\,\overline{a_2}\,p_3)\,\overline{a_3}\,\ldots\,\overline{a_{n-2}}\,p_{n-1})\,\overline{a_{n-1}}\,p_n$.
[/mm]
Zeige nun per Induktion nach $n$, dass für alle [mm] $1\le k\le 2^n$ [/mm] diese Formel [mm] $F_{n,k}$ [/mm] genau von $k$ Belegungen erfüllt wird.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 16.10.2013 | | Autor: | Haeger |
Super, vielen dank für eure schnellen antworten und dass ihr euch soviel zeit genommen habt.
lg haeger
|
|
|
|
