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

Übungsblatt 5

Abgabe in der 6. Semesterwoche

5.1 Gegeben sei eine Menge M = ( 0, 1/2, 1 ), ihre Elemente seien natürlich geordnet und es seien 3 Operationen definiert: a Ú b := max (a,b), a Ù b := min (a,b), ¬ a := 1-a, für a,b aus M.
Ist dann M mit diesen Verknüpfungen ein Verband? Ist es eine Boolesche Algebra?

5.2 Man leite b aus den folgenden Prämissen ab:

  1. x Ù y Ù z
  2. a ® b
  3. w ® a
  4. c Ú x
  5. z ® w

    5.3 Die Abbildung f: P({1,2,3,4} ® N0 sei durch f(S) = åx Î S x gegeben. Wir definieren eine Relation R auf P({1,2,3,4} durch (S,T) Î R falls f(S) = f(T) ist. Zeigen Sie, daß das eine Äquivalenzrelation ist und bestimmen Sie die Äquivalenzklassen.

    5.4 (optional) R sei eine Relation auf einer Menge M. M' sei die Menge der starken Komponenten. Wir definieren eine Relation R¢ Í M' ×M' auf M' durch (A,B) Î R¢ Û $a Î A $b Î B: (a,b) Î R, die Kondensation von R.
    Zeigen Sie, daß die starken Komponenten bzgl. R' alle einelementig sind. Zeigen Sie auch daß die Kondensation der transitiven Hülle (R*)¢ gleich der transitiven Hülle der Kondensation (R¢)* ist.

    zu Blatt 6
    April 2000