Übungsblatt 1 (Mathematische Logik) (Grädel)

Aus Infostudium Wiki

Damit das Wiki keine Schwierigkeiten bekommt, bittet es euch, keine direkten Lösungen zu posten. Bitte erklärt euer Vorgehen bei der Bearbeitung der Aufgaben so, dass es andere verstehen und nachvollziehen können. So kann jeder das Ergebnis bestätigen oder gegebenenfalls auf Fehler hinweisen.

Inhaltsverzeichnis

1 Aufgabe 1
2 Aufgabe 2
- 2.1 a)
  - 2.1.1 Beweis
  - 2.1.2 Was steckt dahinter?
- 2.2 b)
  - 2.2.1 Was steckt dahinter?
3 Aufgabe 3
4 Aufgabe 4

Aufgabe 1

Da man für beide Variablen X und Y die Zustände 0 und 1 durchspielen muss, hilft das Anlegen von Tabellen. Danach mus entschieden werden, ob die Formel eine Tautologie (immer wahr), erfüllbar oder (immer) unerfüllbar ist.

Durch Äquivalenzumformungen kann man die Formeln vereinfachen, dass ein umständliches Ausfüllen von Tabellen nicht mehr nötig ist. Dies geht besonders bei Tautologien gut, da sie sich auf $ψ = 1$ reduzieren lassen.

Die Operationen und deren Ergebnisse findest du unter: http://de.wikipedia.org/wiki/Aussagenlogik

Aufgabe 2

a)

Eine kontigente Formel kann erfüllbar oder nicht erfüllbar sein. Negiert man diese so ändert dies nichts an den Möglichkeiten. Die Lösung sollte damit klar sein :-)

Beweis

Sei $\psi \in AL$ kontigent. Sei $\mathcal{I}$ ein Modell von $ψ$ . $ψ$ kontigent $\Rightarrow \exists$ Interpretation $\mathcal{J}$ mit $[ \psi ]^{\mathcal{J}} = 0$ , dann gilt

1) $[\neg \psi]^{\mathcal{I}} = 1 - [\psi]^{\mathcal{I}} = 1 - 1 = 0 \Rightarrow \neg \psi$ ist keine Tautologie.

2) $[\neg \psi]^{\mathcal{J}} = 1 - [\psi]^{\mathcal{J}} = 1 - 0 = 1 \Rightarrow \neg \psi$ erfüllbar.

Also ist $\neg \psi$ kontigent.

Was steckt dahinter?

Im Prinzip habe ich einfach nur die Eigenschaft einer Formel kontingent zu sein verwendet, also das es eine Interpretation gibt, die ein Modell ist und eine die kein Modell ist. Die weiteren Folgerungen sind aus dem Skript (Kap.1 S.3).

b)

Durch gegebene Definition ist $f$ mit $x \in \{0,1\}$ über die Urbilder vollständig bestimmt. Wenn $g \neq f$ eine andere Funktion wäre, die ebenfalls die selben Bedingungen erfüllt, dann muss $g \equiv f$ sein. Also ist $f$ (bis auf Äquivalenz) eindeutig bestimmt.

$\varphi(X_1,X_2,X_3) := (\overline{X_1} \wedge \overline{X_2} \wedge \overline{X_3}) \vee (\overline{X_1} \wedge X_2 \wedge \overline{X_3}) \vee (X_1 \wedge \overline{X_2} \wedge \overline{X_3}) \vee (X_1 \wedge \overline{X_2} \wedge X_3)$

${f}$ ist funktional vollständig. Es gilt $\neg X \equiv f(X,X,X)$ und $(X \wedge Y) \equiv \neg f(X,Y,X)$ . Vom System ${f}$ kann ein funktional vollständiges System $\{\neg,\wedge\}$ abgeleitet werden, also ist ${f}$ funktional vollständig.

Was steckt dahinter?

Der erste Aufgabenteil hat mir etwas Kopfzerbrechen bereitet. Generell würde man Eindeutigkeit beweisen indem man ein zweiten Objekt gleicher Art (also hier eine weitere Funktion) heranzieht, welche von dem eindeutig bestimmten Objekt verschieden ist, jedoch die selben Schlüsse zulässt. Das führt man dann darauf zurück das beide Objekte gleich sein müssen und schon hat man einen Beweis durch Kontraposition. Naja, hier hat das ganze auf jeden Fall nicht so einfach funktioniert. Mein Tutor meinte, ich könnte es etwas unformaler ausdrücken. Wichtig war dabei, das in der Funktionsdefinition das für alle Zustände des $x$ und die gegebenen Fälle bereits alle $8( = 2 3)$ Urbilder samt Bildern gegeben waren. Da die Funktion also schon in allen Zuständen definiert ist, gibt es auch keinen Punkt wo etwas mehrdeutig werden könnte, also muss es ja schon eindeutig sein. Es bleibt natürlich vorerst noch offen ob man mir das abkauft ^^

Im zweiten Teil habe ich nach der Wahrheitstabelle zur Funktion eine Normalform aufgestellt und somit eine aussagenlogische Formel die passend zur boolschen Funktion ist (siehe Kap 1.2).

Im letzten Teil habe ich ebenfalls versucht mit der Wahrheitstabelle zu arbeiten und ein beliebiges funktional vollständiges System aus ${f}$ zu erzeugen. Zuerst habe ich versucht die Negation und eine UND- bzw. ODER-Verknüpfung zu erzeugen. Ich erinner mich nicht korrekt an die Definition von funktionaler Vollständigkeit, aber ich glaube zumindest, daß ich nicht ohne weiteres die 1 und 0 verwenden kann, falls ich diese nicht zuvor selbst über die Funktion erzeugt habe. Angefangen habe ich mit der Negation, die konnte man schon recht schnell sehen an den beiden rechten vorgegebenen Formeln. Setzt man nämlich in die Funktion dreimal den selben Wert ein, so ist das Ergebnis die Negation des Wahrheitswertes. Wo das geklärt ist kann man also beliebig das $\neg X \equiv f(X,X,X)$ schreiben. Nunja, danach habe ich mir ein paar Wahrheitstabellen aufgestellt für Terme wie $f (X, Y, X)$ (wo also die erste und dritte Abhängige immer gleich ist) und daraus ergab sich eine Tabelle wie beim NICHT-UND (NAND). Also das ganze nochmal negiert und fertig war der Salat.

Zum Thema "eindeutig bestimmt" habe ich nur das finden können: http://www.pms.ifi.lmu.de/publikationen/projektarbeiten/Claudia.Plant_Alije.Ristemi/node6.html Satz 2.1.7

Aufgabe 3

Generell

Es ist ziemlich bescheiden, daß die jeweiligen Aussagenvariablen $X i j$ nur dann definiert sind, falls $i < j$ ist. Das erschwert das ganze etwas. Da der Graph ungerichtet ist und ich auch nicht auf die Reihenfolge der Indizierung achten will, schreibe ich um die korrekte Indizierung zu gewährleisten $X min{i, j}max{i, j}$ .

a)

Sei $V$ die Menge der Knoten, $\psi := \bigvee \limits_{v \in V} \left[ \bigvee \limits_{T \subseteq V, |T|=3, v \not \in T} \left( \bigwedge \limits_{w \in T} X_{\min\{v,w\}\max\{v,w\}} \right) \right]$

Was steckt dahinter?

Edit: Wo findest du eine Definition die sagt, dass der Graph schlaufenfrei ist?

Grüsse

Die Idee ist ganz simpel: Ich formuliere eine Formel, welche mir sagt ob ein Knoten $v \in V$ Kanten zu drei anderen Knoten $w \in T$ hat. Diese Formel steht in den runden Klammern. Allerdings ist nicht wichtig, zu welchen drei Knoten die Kanten gehen, also prüfe ich ob mindestens eine solche Konstellation existiert, indem ich für meinen Knoten $v \in V$ und alle drei-elementigen Teilmengen $T \subset V$ die $v$ nicht enthalten (der Graph ist per Definition Schlaufenfrei) prüfe (Das passiert mit der Disjunktion in den eckigen Klammern.)

b)

$\psi := \bigwedge \limits_{v \in V} \left[ \bigvee \limits_{T \subseteq V, |T|=k} \left( \bigwedge \limits_{w \in T} \delta_{T}(X_{vw}) \right) \right]$ mit Hilfsfunktion $\delta_{T}(X_{ij}) := X_{min(i,\;j),\;max(i,\;j)}$ , falls $i \in T$ und $\delta_{T}(X_{ij}) := \neg X_{min(i,\;j),\;max(i,\;j)}$ sonst.

c)

$\bigvee \limits_{T \subset V, T \neq \emptyset} \left[ \bigwedge \limits_{v \in T} \left( \bigwedge \limits_{w \in V, v \neq w} (\delta(X_{ij})) \leftrightarrow w \not \in T \right) \right]$ mit $δ(X i j)$ wie in b).

Bipartiter Graph Auf dem Wikipedia-Bild sollen die drei Punkte links und die drei Punkte rechts jeweils den Teilgraph symbolisieren. Haben ein bisschen an Farbe gespart. Wie man sieht ist jeder Punkt des einen Graphen mit den Punkten des anderen Graphen auf der anderen Seite verbunden.

Aufgabe 4

$\psi := (A \rightarrow B) \wedge ( C \vee D ) \wedge ( B \oplus E ) \wedge ( D \leftrightarrow E ) \wedge ( C \rightarrow (D \wedge A ))$ , ein Modell von $ψ$ wäre daß $D$ und $E$ die einzigen Gäste sind. Hab mit der Formel einfach ein Szenario durchgespielt angefangen mit $A$ kommt. Als sich dann ein Widerspruch ergabt war klar $A$ kommt also nicht. Dann hab' ich mit $B$ weitergemacht, etc.

Auch hier kann die Wikipedia-Seite helfen. Die Operation (z.B. (Jochen $\rightarrow$ Fabian) ) soll hier jeweils angegeben werden.

Übungsblatt 1 (Mathematische Logik) (Grädel)

Aus Infostudium Wiki

Inhaltsverzeichnis

Aufgabe 1

Aufgabe 2

a)

Beweis

Was steckt dahinter?

b)

Was steckt dahinter?

Aufgabe 3

Generell

a)

Was steckt dahinter?

b)

c)

Aufgabe 4

Ansichten

Meine Werkzeuge

Navigation

Informatik

Mathematik

Anwendungsfächer

Suche

Werkzeuge