nicht-äquivalente Formeln < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wieviele paarweise nicht-äquivalente Formeln in den Variablen [mm] p_1, [/mm] ... , [mm] p_n [/mm] gibt es? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
ich weiß nicht wie ich an die aufgabe herangehen soll.
eine formel [mm] \phi [/mm] kann die variablen [mm] p_1, [/mm] ... , [mm] p_n [/mm] enthalten, muss aber nicht alle enthalten... wenn ich zusätzlich die Belegungen der Variablen {0,1} mit einbeziehe, erhalte ich die Anzahl der möglichen Formeln,
sind das n! [mm] \cdot \sum_{k=1}^{n} 2^k [/mm] ?
wenn ich die anzahl der überhaupt möglichen formeln rausgefunden habe, habe ich noch das problem mit der nicht-äquivalenz...
ich bitte um hilfe
ich hab mal die Vorlesung dazu hochgeladen.
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:19 Di 26.05.2009 | | Autor: | jini_9791 |
Wenn ich eine Formel habe, die nur aus einer Variablen bestehen soll, dann habe ich insgesamt n Möglichkeiten mir was auszudenken und alle können doch paarweise verschieden sein, oder? Also mal abgesehen von dem Wert F* [mm] \mapsto [/mm] {0,1} den die Formel dann annimmt, aber danach ist ja nicht gefragt, sondern, wie viele paarweise verschiedene Formeln man finden kann. Wenn ich nun Formeln mit zwei Variablen bilde, dann habe ich doch [mm] \vektor{n \\ 2} [/mm] Möglichkeiten auszuwählen. Also läuft das doch erstmal auf die Potenzmenge hinaus, oder. Also ist das die Summe aller Teilmengen einer n-elementigen Menge, also [mm] 2^n. [/mm] Ist das so? Aber wenn ich eine Formel habe mit [mm] p_1, p_4 [/mm] und [mm] p_5. [/mm] Dann ist ja die Relation dazwischen Wurst, da ich sie ja immer beliebig umformen kann und in gegenseitige Äquvalenzen überführen kann, oder? Stimmt der zweite Schluss? Ich lade mal die Vorlesung hoch.
Auf jedenfall sind das die Aussagenvariablen [mm] p_i. [/mm] Wir hatten, dass man eine Formel bilden kann mit [mm] \phi (p_1, p_2,..., p_n), [/mm] wobei man nicht alle Variablen in [mm] \phi [/mm] verwenden muss, aber eben kann. Nicht äquivalent wäre z.B. [mm] \phi (p_1, p_2, p_3) =p_1 \Rightarrow p_2 [/mm] und [mm] \phi (p_1, p_2, p_3) [/mm] = [mm] p_1 \Rightarrow p_3.
[/mm]
Bitte helft mir!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Do 28.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
