Logo

DISKRETE MATHEMATIK
Dr. E. Prisner, Dr. J. Sustal,
Dr. W. Preuß, S. Fröhlich,
Sommersemester 2000


Übungsblatt 3

Abgabe in der 4. Semesterwoche

3.1 Ist die folgende Formel kontradiktorisch? Ist sie tautologisch?
( ( A B ) A ) ( ( A B ) B )

3.2 a) Zeichnen Sie das Hasse-Diagramm für die Formeln:
(a c),
(a ¬ b),
((a c) (a ¬ b)),
a,
(c ¬ b).
Die Ordnung auf diese fünfelementige Menge wird so eingeführt: für zwei Formeln F, G gilt F G, genau dann wenn F G eine Tautologie ist.

b) (optional) Ist die wie oben definierte Relation für beliebige Formelmengen eine Ordnungsrelation?

3.3 Es seien folgende Formeln gegeben.
(a | a) | (b | b),
(a | a) | a,
(a | b) | (a | b),
wobei das Symbol "|" den Sheffer-Strich, d.h. die NAND-Funktion, bezeichnet.
Bilden Sie Formeln mit den Junktoren , , , , ¬, die zu den gegebenen Formeln äquivalent sind (d.h. für beliebige Belegungen der Variablen dieselben Wahrheitswerte liefern).

3.4 (a) Zeichnen Sie das Hasse-Diagramm der folgenden Relation: R={(a,e),(a,f),(a,l), (b,e),(b,f),(b,o), (c,e),(c,n), (d,c),(d,e),(d,n), (f,e), (g,a),(g,e),(g,f),(g,l), (h,a),(h,e),(h,f),(h,g),(h,l), (i,b),(i,c),(i,d),(i,e),(i,f),(i,m),(i,n),(i,o), (j,c),(j,d),(j,e),(j,m),(j,n), (k,a),(k,e),(k,f),(k,g),(k,h),(k,l), (m,c),(m,d),(m,e),(m,n), (n,e), (o,e),(o,f), (a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h),(i,i),(j,j), (k,k),(l,l),(m,m),(n,n),(o,o),(p,p)} auf der Menge {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}

b) (optional) Zeigen Sie, daß es eine 16-elementige Teilmenge M der Menge N der natürlichen Zahlen gibt, so daß sie, versehen mit der Teilbarkeitsrelation "|", zur geordneten Menge in 3.4a) isomorph ist.


zu Blatt 4
April 2000