104080 UE11

Aus WinfWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

1 11. SW/DMG-UE 19.01.06
- 1.1 Beispiele
2 Lösungen

[bearbeiten]

11. SW/DMG-UE 19.01.06

Wie schreibe ich mathematische Ausdrücke ins wiki

[bearbeiten]

Beispiele

123, 139, 142, 146, 147, 148a, 148b, 151, 152

[bearbeiten]

Lösungen

[bearbeiten]

Bsp. 123

Für jeden schlichten ungerichteten Graphen  bezeichne 
der Grad jedes Knoten  der maximale
Knotengrad im Graphen.
Man beweise, dass die Ungleichung



für jeden schlichten ungerichteten Graphen G gilt. (Hinweis: Skizzieren
Sie einen Algorithmus, der als Eingabe einen beliebigen Graphen G erhält,
und als Ausgabe ein Färbung von G mit höchstens  liefert; er-
klären Sie, warum dieser Algorithmus funktioniert.)

[bearbeiten]

Bsp. 139

Betrachten Sie das folgende Netzwerk mit Fluss f:

(a) Bestimmen Sie den Wert von f.
(b) Finden Sie einen zunehmenden Weg für f,
    und bestimmen Sie den erhöhten Fluss.
(c) Bestimmen Sie einen Schnitt mit minimaler Kapazität.
(d) Geben Sie einen maximalen Fluss an.

Flüsse in Netzwerken (Seminararbeit)

(a) Wert von f: 11

(b) P0/q -> P2 -> P4 -> P6/s, erhöhter Fluss (+ 1): 12

(c) S* = 12 = max. Fluss (Skriptum S. 41 oben: es gilt der Satz vom max. Fluss und min. Schnitt W(F*) = $ψ(S * )$ ) Möglicher Schnitt geht durch die Kanten q->P1,P2->P4,P5->P6

(d) max. Fluss: 12

[bearbeiten]

Bsp. 142

Wie kann man beim Kruskal-Algorithmus im Schritt (3) (siehe Vorlesung)
überprufen, dass der entstehende Graph kreislos ist?

[bearbeiten]

Bsp. 146

Man bestimme für folgende Klauselmenge  $F K$  die Mengen  für

Siehe auch Resolution bei Wikipedia

Ammerkung: lt. Skriptum ist $\underline R^0 \big( F_K \big)$ die Klauselmenge $F K$ selbst.

$\underline R^0 = \big\{ \big\{ A, \lnot B, C \big\}, \big\{ B, C \big\}, \big\{ \lnot A, C, \big\}, \big\{ \lnot C \big\}\big\}$

$\underline R^1:$

$Resolventen: R_1 = \big\{ A, C \big\}, R_2 = \big\{ \lnot B, C \big\}, R_3 = \big\{ A, \lnot B \big\}, R_4 = \big\{ B \big\}, R_5 = \big\{ \lnot A \big\}$

$\underline R^1 = \big\{ \big\{A, \lnot B, C \big\}, \big\{ B, C \big\}, \big\{ \lnot A, C \big\}, \big\{ \lnot C \big\}, \big\{ A, C \big\}, \big\{ \lnot B, C \big\}, \big\{ A, \lnot B \big\}, \big\{ B \big\}, \big\{ \lnot A \big\} \big\}$

$\underline R^2:$

$Resolventen: R_1 = \big\{ A, C \big\}, R_2 = \big\{ \lnot B, C \big\}, R_3 = \big\{ A, \lnot B \big\},$

$R_4 = \big\{ A, C \big\}, R_5 = \big\{ \lnot B, C \big\}, R_6 = \big\{ B \big\}, R_7 = \big\{ C \big\}, R_8 = \big\{ A, C \big\}, R_9 = \big\{ \lnot A \big\},$

$R_{10} = \big\{ C \big\}, R_{11} = \big\{ \lnot B, C \big\}, R_{12} = \big\{ A \big\}, R_{13} = \big\{ \lnot B \big\}, R_{14} = \big\{ C \big\},$

$R_{15} = \big\{ C \big\}, R_{16 }= \big\{ A \big\}, R_{17} = \big\{ \lnot B \big\}$

$\underline R^2 = \big\{ \big\{A, \lnot B, C \big\}, \big\{ B, C \big\}, \big\{ \lnot A, C \big\}, \big\{ A, C \big\}, \big\{ \lnot B, C \big\}, \big\{ A, \lnot B \big\}, \big\{ A \big\}, \big\{ \lnot A \big\}, \big\{ B \big\}, \big\{ \lnot B \big\}, \big\{ C \big\}, \big\{ \lnot C \big\} \big\}$

[bearbeiten]

Bsp. 147

Man zeige mit der Resolutionsmethode, dass



eine Tautologie ist.

Hinweis: Zeigen Sie, dass die Negation dieser Formel unerfüllbar ist,
indem Sie die Negation der Formel in Klauselform umwandeln und durch
Resolution die leere Klausel herleiten.

Tautologie: eine Aussage, die immer wahr ist, also z.B. 
Siehe auch Resolution bei Wikipedia

Negation: $( B \lor C \lor \lnot D) \land ( B \lor D ) \land ( \lnot C \lor \lnot D ) \land ( \lnot B)$

$F_K = \big\{ \big\{ B, C, \lnot D \big\}, \big\{ B, D \big\}, \big\{ \lnot C, \lnot D \big\}, \big\{ \lnot B \big\} \big\}$

$Resolventen: R_1 = \big\{ B, C \big\}, R_2 = \big\{ B, \lnot D \big\}, R_3 = \big\{ C, \lnot D \big\}, R_4 = \big\{ B, \lnot C \big\}, R_5 = \big\{ D \big\}$

$\underline R^1 = \big\{ \big\{ B, C, \lnot D \big\}, \big\{ B, D \big\}, \big\{ \lnot C, \lnot D \big\}, \big\{ B, C \big\}, \big\{ B, \lnot D \big\}, \big\{ C, \lnot D \big\}, \big\{ B, \lnot C \big\}, \big\{ \lnot B \big\}, \big\{ D \big\} \big\}$

$Resolventen: R_1 = \big\{ B, C \big\}, R_2 = \big\{ B, \lnot D \big\}, R_3 = \big\{ B, \lnot D \big\}, R_4 = \big\{ C, \lnot D \big\}, R_5 = \big\{ B, C \big\}$

$R_6 = \big\{ B, \lnot C \big\}, R_7 = \big\{ B \big\}, R_8 = \big\{ B, C \big\}, R_9 = \big\{ D \big\}, R_10 = \big\{ B, \lnot D \big\}, R_11 = \big\{ \lnot D \big\}, R_12 = \big\{ \lnot C \big\}$

$R_13 = \big\{ B \big\}, R_14 = \big\{ C \big\}, R_15 = \big\{ \lnot D \big\}, R_16 = \big\{ B \big\}, R_17 = \big\{ B, \lnot D \big\}, R_18 = \big\{ C \big\}, R_19 = \big\{ \lnot C \big\}$

$\underline R^2 = \big\{ \big\{ B, C, \lnot D \big\}, \big\{ B, D \big\}, \big\{ \lnot C, \lnot D \big\}, \big\{ B, C \big\}, \big\{ B, \lnot D \big\}, \big\{ C, \lnot D \big\}, \big\{ B, \lnot C \big\},$ $\big\{ \lnot B \big\}, \big\{ D \big\}, \big\{ B \big\}, \big\{ \lnot D \big\}, \big\{ \lnot C \big\}, \big\{ C \big\} \big\}$

$Resolventen: R_1 = \big\{ B, C \big\}, R_2 = \big\{ B, \lnot D \big\}, R_3 = \big\{ B, \lnot D \big\}, R_4 = \big\{ C, \lnot D \big\}, R_5 = \big\{ B, C \big\},$

$R_6 = \big\{ B, \lnot D \big\}, R_7 = \big\{ B, \lnot C \big\}, R_8 = \big\{ B \big\}, R_9 = \big\{ B, C \big\}, R_10 = \big\{ D \big\}, R_11 = \big\{ B \big\}, R_12 = \big\{ B, \lnot D \big\}$

$R_13 = \big\{ \lnot D \big\}, R_14 = \big\{ \lnot C \big\}, R_15 = \big\{ \lnot D \big\}, R_16 = \big\{ B \big\}, R_17 = \big\{ C \big\}, R_18 = \big\{ B \big\}, R_19 = \big\{ \lnot D \big\},$

$R_20 = \big\{ B \big\}, R_21 = \big\{ B, \lnot D \big\}, R_22 = \big\{ C \big\}, R_23 = \big\{ \lnot D \big\}, R_24 = \big\{ \lnot C \big\}, R_25 = \big\{ B \big\},$ $R_26 = \big\{ \big\}, R_27 = \big\{ \big\}, R_28 = \big\{ \big\}$

$\underline R^3 = \big\{ \big\{ B, C, \lnot D \big\}, \big\{ B, D \big\}, \big\{ \lnot C, \lnot D \big\}, \big\{ B, C \big\}, \big\{ B, \lnot D \big\}, \big\{ C, \lnot D \big\},$ $\big\{ B, \lnot C \big\}, \big\{ \lnot B \big\}, \big\{ D \big\}, \big\{ B \big\}, \big\{ \lnot D \big\}, \big\{ \lnot C \big\}, \big\{ C \big\}, \big\{ \big\} \big\}$

[bearbeiten]

Bsp. 148a

Ist die Formel



unter jeder Belegung wahr? Ist ihre Negation erfüllbar?

Hinweis dazu: $\exists y \forall x ...$ und $\forall x \exists y...$ bedeutet nicht das Gleiche.
Die erste Formel bedeutet "es gibt ein (fixes) y, sodass für alle x gilt: ... ; die zweite Formel bedeutet: "für jedes x gilt, dass es ein (eventuell von x abhängiges) y gibt, sodass ..."

Zum Beispiel ist die Formel

$\exists y \forall x (x < y)$

in den natürlichen Zahlen falsch, weil es eben keine natürliche Zahl y gibt, die größer als alle natürlichen Zahlen x ist.

Sehr wohl aber gibt es zu jeder natürlichen Zahl x eine größere natürliche Zahl y (zum Beispiel x+1), also ist die Formel

$\forall x \exists y (x < y)$

in den natürlichen Zahlen wahr.

Die Negation von F ist äquivalent zur Formel

$(\exists y \forall x R (x, y)) \wedge \lnot (\forall x \exists y R(x, y))$

Nach Bereinigen erhält man die Pränexform

$\exists y \exists u \forall x\forall v ( R (x, y)) \wedge \lnot R(u,v))$

Die $\exists$ werden durch Konstante a, b ersetzt, damit erhält man

$\forall x\forall v ( R (x, a)) \wedge \lnot R(b,v)).$

In Klausenform

{ R(x,a) }, { -R(b,v) }

Einsetzen von x=b und v=a liefert

{ R(b,a) }, { -R(b,a) }

daraus mit Resolution die leere Menge.

Damit ist die Negation der Formel niemals wahr (die Formel ist also unerfüllbar), die ursprüngliche Formel ist Tautologie.

[bearbeiten]

Bsp. 148b

Ist die Formel



unter jeder Belegung wahr? Ist ihre Negation erfüllbar?

unter jeder belegung wahr: nein // negation erfüllbar: ja

[bearbeiten]

Bsp. 151

Sei .
Finden Sie eine bereinigte Formel , die zu F äquivalent ist.

Bereinigte Normalform bei Wikipedia

wenn ichs richtig verstanden habe (gebundene werden ersetzt):

$\bar F = \forall u R(u, y) \lor \forall v \lnot S (x, v)$

[bearbeiten]

Bsp. 152

Sei 

Ist F bereinigt? Wenn ja, dann finden Sie eine äquivalente Formel 
in Pränexform. (Wenn nein, dann finden Sie zuerst eine äquivalente
bereinigte Formel , dann eine äquivalente Pränexformel .)

Bereinigte Normalform bei Wikipedia