Ausagenlogische Formel gesucht < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe 1 | Gesucht ist eine Funktion f : [mm] \IN \to [/mm] {1,...,k}, so dass für alle {i,j} [mm] \in [/mm] M gilt: f(i) [mm] \not= [/mm] f(j).
Sei M = {{1,2},{1,3},{2,3},{3,4},{3,5},{4,5}}.
a) Geben Sie die kleinste Anzahl k an. |
| Aufgabe 2 | | b) Geben Sie eine Formel [mm] \mu^{!}_{i} [/mm] an, die ausdrückt, dass i genau einem k zugeordnet werden kann. |
| Aufgabe 3 | | c) Geben Sie eine Formel [mm] \mu^{\#}_{i,j} [/mm] an, die ausdrückt, dass i und j genau dem selben k zugeordnet ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo, zu obiger Aufgabe brauche ich vermutlich nur einen kleinen Denkanstoß, denn ich finde einfach keinen Lösungsansatz.
Aufgabenteil a) habe ich schon gelöst, indem ich einen Graphen mit jeweils einem Knoten für jedes i gemacht habe und die Kanten wie in M beschrieben eingefügt habe. Daraus sieht man, dass k minimal 3 sein muss. So gibt es nur die beiden Fälle, dass entweder [mm] k_{1}= [/mm] {1,4}, [mm] k_{2}= [/mm] {2,5}, [mm] k_{3}= [/mm] {3} oder eben [mm] k_{1}= [/mm] {1,5}, [mm] k_{2}= [/mm] {2,4}, [mm] k_{3}= [/mm] {3} sein muss.
Wie ich jetzt jedoch das ganze in einer aussagenlogischen Formel in b) und c) schreiben soll, will mir nicht klar werden. Evtl. kann mich ja jemand in die richtige Richtung schupsen. ;)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:22 Do 24.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
