Links und Funktionen
Sprachumschaltung

Navigationspfad


Inhaltsbereich

Lösung 11

Plain Text icon loesung11.txt — Plain Text, 1 KB (1855 bytes)

Dateiinhalt

Musterloesung Blatt 11
----------------------

H-22:

1. unerfuellbar. 
Damit die Formel wahr wird, muss -x = 1, also x=0 sein,
da -x als Klausel vorkommt.
Wegen der Klausel (x v y) muss dann aber y=1 sein.
Wegen der Klausel (-y v -z) muss dann z=0 sein.
Dann ist aber die Klausel (x v -y v z) falsch. 

2. erfuellbar, aber keine Tautologie.
Jede Bewertung mit x=0 erfuellt die Formel, 
da dann -(x ^ y) wahr wird, also die ganze 
Disjunktion falsch. 
Andererseits macht die Bewertung
 x=1, y=1, z=0, w=0 
die Formel falsch. 

3. Tautologie
Damit die Formel falsch wird, muss --w falsch sein, also w=0. 
Wegen der Teilformel (-y ^ -w) muss dann y=1 sein, 
dann ist aber (-y v x) falsch, also -(-y v x) wahr. 
Also kann die Formel nicht falsch werden.


H-23:

Fuer jedes Konnektiv fuehren wir eine Variable vi ein, 
die die Teilformel mit dem so nummerierten Zeichen  
als aeusserstes Konnektiv repraesentiert:

( -x ^ ( -y v z ) ) v ( x ^ -z )
  1  2   3  4       5     6 7

D.h. v5 repraesentiert die ganze Formel, und 
v4 die Teilformel (-x v z ) .
Die Formel E(F) setzt sich zusammen aus den 
folgenden Klauseln mit der jeweiligen Bedeutung:


Klausel(n)					%% Bedeutung

v5 								%% F gilt
^ (-v5 v v2 v v6) ^ (-v2 v v5) ^ (-v6 v v5)	%% v5 = v2 v v6 
^ (-v2 v v1 ) ^ (-v2 v v4) ^ (-v1 v -v4 v v2)   %% v2 = v1 ^ v4 
^ (-v1 v -x ) ^ (v1 v x)			%% v1 = -x
^ (-v4 v v3 v z) ^ (-v3 v v4) ^ (-z v v4)	%% v4 = v3 v z 
^ (-v3 v -y ) ^ (v3 v y)			%% v3 = -y 
^ (-v6 v x ) ^ (-v6 v v7) ^ (-x v -v7 v v6)     %% v6 = x ^ v7
^ (-v7 v -z ) ^ (v7 v z)		      	%% v7 = -z

(Leicht vereinfachte Version gegenueber der in der Vorlesung,
die mit weniger Variablen auskommt. Hier werden die Variablen
direkt eingesetzt, statt noch Hilfsvariablen fuer die 
Teilformeln, die nur Variablen sind, einzufuehren.)

Artikelaktionen


Funktionsleiste