1 of 16

Matematika Diskrit

Rahmat Hidayat, S.Kom., M.Cs

Muhammad Galih Wonoseto, M.T.

4. Kardinalitas, Relasi, Reflektif, Simetri dan Transitif

2 of 16

Tujuan Pembelajaran

  • Mahasiswa memahami konsep Kardinalitas, Relasi, Reflektif, Simetri, Transitif

3 of 16

Cardinality

  • Definition:

​

If there are exactly n distinct elements in a set S, with n a

nonnegative integer, we say that S is a finite set and the

cardinality of S is n. Notationally, we write

|S| = n

4 of 16

Cardinality II

  •  

5 of 16

Relations

  •  

 

6 of 16

Relations

  • To represent a relation, you can enumerate every element in R.
  • Example:

​

​

​

​

  • You can also represent this relation graphically.

 

7 of 16

Relations�On a Set

  •  

A relation on the set A is a relation from A to A. I.e. a subset of A × A.

8 of 16

Reflexivity

  •  

 

9 of 16

Reflexivity

  •  

10 of 16

Symmetry I

  • Definition

 

11 of 16

Symmetry II

Some things to note:

  • A symmetric relationship is one in which if a is related to b then b must be related to a.
  • An antisymmetric relationship is similar, but such relations hold only when a = b.
  • An antisymmetric relationship is not a reflexive relationship.
  • A relation can be both symmetric and antisymmetric or neither or have one property but not the other!
  • A relation that is not symmetric is not necessarily asymmetric.

12 of 16

Symmetric Relations

  •  

 

13 of 16

Transitivity

  • Definition

 

14 of 16

Transitivity

  • Example

 

Is the relation R = {(a, b), (b, a), (a, a)} transitive?

No since bRa and aRb but bR b.

15 of 16

Transitivity

  • Example

Is the relation

{(a, b) | a is an ancestor of b}

transitive?

Yes, if a is an ancestor of b and b is an ancestor of c then a is also an ancestor of c (who is the youngest here?).

 

16 of 16

Pustaka

  • Christopher M. Bourke
  • Berthe Y. Choueiry