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