matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAussagenlogikFormel mit k Belegungen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Aussagenlogik" - Formel mit k Belegungen
Formel mit k Belegungen < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Formel mit k Belegungen: Konstruktion
Status: (Frage) reagiert/warte auf Reaktion Status 
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

        
Bezug
Formel mit k Belegungen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:48 Mo 14.10.2013
Autor: reverend

Hallo Haeger, [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

Bezug
                
Bezug
Formel mit k Belegungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Formel mit k Belegungen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:13 Mo 14.10.2013
Autor: tobit09

Hallo Haeger und herzlich [willkommenmr]!


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

Bezug
                                
Bezug
Formel mit k Belegungen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]