100% tevredenheidsgarantie Direct beschikbaar na je betaling Lees online óf als PDF Geen vaste maandelijkse kosten
logo-home
Eerder door jou gezocht
Eerder door jou gezocht
logo
Discrete Structures (2IT80) Summary 2019 €3,99
In winkelwagen
Snel navigeren naar
Voorbeeld
  2.  
  3. Technische Universiteit Eindhoven (TUE)
  4.  
  5. Discrete Structures 2IT80 (2IT80)

Samenvatting

Discrete Structures (2IT80) Summary 2019
 3 keer verkocht

EN: Discrete Structures (2IT80) is a course given at Eindhoven University of Technology. It is a mandatory course for Bachelor Computer Science and Engineering students. The course is given in the second quartile of the first year. It goes more in depth about the content from Logic and Set Theory (...

[Meer zien]

Voorbeeld 2 van de 11  pagina's

Document informatie

  • Ja
  • 28 mei 2020
  • 11
  • 2019/2020
  • Samenvatting

Onderwerpen

Gekoppeld boek

book image

Titel boek:

Auteur(s):

  • Uitgave:
  • ISBN:
  • Druk:

Geschreven voor

Alle documenten voor dit vak (1)

Verkoper

avatar-seller
IsabelRutten

Ontvangen beoordelingen

Beschikbare oefenvragen

Discrete Structures - Everything that I learned by heart

Oefenvragen 51 Oefenvragen
€2,99 1 verkocht
Oefenvragen 51 Oefenvragen
€2,99 1 verkocht

Enkele voorbeelden uit deze set oefenvragen

1.

What does the term \"reflexive\" mean?

Antwoord: A relation R on a set A is reflexive if for all x in A, xRx holds.

2.

What does the term \"irreflexive\" mean?

Antwoord: A relation R on a set A is irreflexive if for all x in A, xRx does not hold.

3.

What does the term \"symmetric\" mean?

Antwoord: A relation R on a set A is symmetric if for all x and y in A, xRy implies yRx holds.

4.

What does the term \"antisymmetric\" mean?

Antwoord: A relation R on a set A is antisymmetric if for all x and y in A, (xRy and yRx) implies that x = y holds.

5.

What does the term \"transative\" mean?

Antwoord: A relation R on a set A is transative if for all x, y and z in A, (xRy and yRz) implies that xRz holds.

6.

What is an equivalence relation?

Antwoord: An equivalence relation is a relation that is reflexive, symmetric and transative.

7.

What is an ordering relation?

Antwoord: An ordering relation is a relation that is reflexive, antisymmetric and transative.

8.

What is a partially ordered set?

Antwoord: A partially ordered set (poset) is a pair of a set and ordering relation (X, R) with X as the set and R as the ordering relation and is denoted as ≤.

9.

What is a total ordering?

Antwoord: A total ordering is a partially ordered set (poset) in which any two elements are comparable. Each partial ordering can be extended to a linear ordering.

10.

What is an embedding?

Antwoord: An embedding is a mapping f: X -> X\' of (X, ≤) into (X\', ≤\') if the following holds: - f is injective - f(x) ≤\' f(y) if and only if x ≤ y

Voorbeeld van de inhoud

Introduction to Discrete Structures Summary 2019
Check the summary of Logic and Set Theory for the pre-knowledge of this subject.
Note: the first paragraph repeats what has been taught in Logic and Set Theory but this has also has been
included in the first week of this course hence the repetition. Also: on the left the lecture number is shown.

1 There are several proving techniques. Direct proof is the most basic approach: logically combine
definitions and theorems (forward reasoning) and simplify the goal (backwards reasoning) until the proof is
finished. For proof by case distinction each possible configurations is distinguished for a certain situation
and it is proven that the statement holds for each separately; this is useful when there is a small number of
configurations. An integer n is a perfect square if there exists another integer k such that k2 = n. Proof by
contradiction is done by assuming the negation, showing that this is impossible and ensuring that the
assumption is the only thing that could be wrong; this is useful when the negation has a ‘there exists’
quantifier. The theorem called the pigeonhole principle states that if n items are put into m containers and
n > m, then there must exist a container that contains more than one item. This is a version of proof by
contradiction. For proof by induction you prove one (or more) simple base cases explicitly and then prove
that if the claim holds for k, then it also holds for k + 1. This is useful if you need to prove infinitely many
cases. For proving the step case (k holds implies that k + 1 also holds) the value of k can be restricted in
the inductive hypothesis (e.g. Step: Assume k ≥ 1. IH: 1 ≤ k’ ≤ k).

2 Elements (x) are part of sets (X), so x ∈ X. Know the following definitions: - |X| is the size of set X
- X ⊆ Y if x ∈ X implies x ∈ Y – X = Y if X ⊆ Y and Y ⊆ X – X ∪ Y = {z | z ∈ X or z ∈ Y}
– X ∩ Y = {z | z ∈ X and z ∈ Y} – X\Y is setminus
– P(X) is the powerset – capital versions of ∪ and ∩ to take union/intersection of multiple set.
Associativity means that for any three sets A, B, C it is (A ∪ B) ∪ C = A ∪ (B ∪ C). Distributivity means
that for any three sets X, Y, Z we have X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z) and X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪
Z). De Morgan Laws mean that for any sets X, A, B it is X \ (A ∪ B) = (X \ A) ∩ (X \ B) and X \ (A ∩ B) =
(X \ A) ∪ (X \ B). For two sets X and Y, we define their Cartesian product X × Y as X × Y = {(x, y) | x ∈ X,
y ∈ Y} and is thus the set of all ordered pairs with the first element in X and the second element in Y. A
function (or mapping/map) from set X to set Y is a set of ordered pairs (x, y) with x ∈ X and y ∈ Y (so f ⊆
(X × Y)) with the property that for each x ∈ X there is exactly one pair in f whose first component is x. In this
situation, a function f: X → Y, X is the domain of f and Y is the range of f. If (x, y) ∈ f, we write f(x) = y. We
say f maps x to y and y (so f(x)) is the image of x (under f). Functions can be represented by their graph:
an (x, y)-diagram. Let there be the functions f: X → Y and g: Y → Z which gives the composition of the
functions h: X → Z via h(x) = g(f(x)) (= (g ○ f)(x) = g ○ f) for each x ∈ X. The composition of functions is
associative but not commutative. A function f: X → Y is called injective if x ≠ y implies f(x) ≠ f(y), surjective
if for every y ∈ Y there exists an x ∈ X with f(x) = y and bijective if f is injective and surjective. An important
property that allows us to solve counting problems (e.g. knowing |Y| by making a bijection with an easy |X|)
is that if f: X → Y is a bijection, then |X| = |Y|. The properties of functions are as follows: Let f: X → Y and
g: Y → Z be functions. Then: - if f, g are injective then g ○ f is also injective – if f, g are surjective then g ○ f
is also surjective – if f, g are bijective then g ○ f is also a bijection – for any function f: X → Y there exists a
set Z, an injective function h: Z → Y and a surjective function g: X → Z such that f = h ○ g.
The inverse function of f (denoted as f -1) is the function g: Y → X (g(y) = x) with the bijection f: X → Y. A
relation between two sets X and Y is a subset R ⊆ X × Y of the Cartesian product. If X = Y then there is a
relation on X: R ⊆ X × X. For (x, y) ∈ R we say that x and y are related and we write xRy. Every function is
a relation but not every relation is a function. Relations can be illustrated using diagrams, arrows (for (x, y)
∈ R), loops (for x = y) and adjacency matrices. Let X, Y, Z be sets, let R ⊆ X × Y and S ⊆ Y × Z. The
concatenation of R and S is the following relation T ⊆ X × Z: for x ∈ X and z ∈ Z: xTz if and only if there
exists a y ∈ Y with xRy and ySz (thus T = R ○ S). Warning: the relation corresponding to the function g ○ f
is F ○ G. The properties of relations are as follows: A relation R on a set X is reflexive if xRx for all x ∈ X,
irreflexive if there is no x ∈ X with xRx, symmetric if xRy implies yRx for all x, y ∈ X, antisymmetric if xRy
and yRx implies x = y and transative if xRy and yRz implies xRz for all x, y, z ∈ X. For a relation R the
inverse relation R-1 is defined by R-1 = {(y, x) : (x, y) ∈ R}. For a set X the symbol Δx denotes the diagonal
relation (on X): Δx = {(x, x) : x ∈ X} which is also the smallest reflexive relation on X.

1
by Isabel Rutten

, Introduction to Discrete Structures Summary 2019
The characterization of properties is the following proposition: a relation R on a set X is:
- reflexive if and only if Δx ⊆ R – irreflexive if and only if R ∩ Δx = ∅ – symmetric if and only if R = R-1
– antisymmetric if and only if R ∩ R-1 ⊆ Δx – transative if and only if R ○ R ⊆ R.
When we call two objects equivalent (≡) we consider them as equal. A relation R on a set X is an
equivalence relation (≡) if it is reflexive, symmetric and transative. For an equivalence relation R on X
and an element x ∈ X, let R[x] = {y ∈ x : xRy} be the equivalence class of x. Theorem: For every
equivalence relation R on a set X it holds that: - R[x] = ∅ for all x ∈ X – for any two elements x, y ∈ X either
R[x] = R[y] or R[x] ∩ R[y] = ∅ – an equivalence relation is uniquely determined by its equivalence classes.
Note: from here on are the new subjects explained.

3 An ordering relation on a set X is a reflexive, antisymmetric, transative relation on X. A partially ordered
set (poset) is a pair (X,R) where X is a set and R is an ordering relation on X. We often use notation ≤ and
≼. Given an ordering ≼, we can derive the following relations:
- strict inequality: ≺ as a ≺ b if and only if a ≼ b and a =/ b
– inverse ordering: ≽ as a ≽ b if and only if b ≼ a
Proposition: If R is an ordering on a set X and Y ⊆ X, then R ∩ (Y × Y) is an ordering
on Y. In total orderings, also called linear orderings, any two elements are
comparable: for any two elements x and y either x ≼ y or y ≼ x. Examples of partial
orderings are Δx, divisors, inclusion of subsets and domination orderings. Orderings
can be represented using diagrams but not the arrows and loops. Let (X, ≼) be a poset.
An element x ∈ X is an immediate predecessor of element y ∈ X if x ≺ y and there is
no t ∈ X with x ≺ t ≺ y; this is written as x ⊲ y. Theorem: Let (X, ≼) be a finite poset
and let ⊲ be the corresponding “immediate predecessor” relation. Then for any x, y ∈ X, Fig. 1: Example of
x ≺ y holds if and only if there is a chain of elements x1, x2, …, xk ∈ X such that x ⊲ x1 ⊲ Hasse Diagram: the
… ⊲ xk ⊲ y (possibly k = 0, i.e., x … y). From right to left (⇐), this statement is easily divisibility relation
proven. However, from left to right (⇒) we need induction and transitivity. A Hasse
diagram (see fig. 1) consists of points and segments (arrows without arrow heads) and can be used to
draw the “immediate predecessor” relation. Every linear ordering is also a (partial) ordering but not every
(partial) ordering is a linear ordering (e.g. divisibility in N). Let (X, ≼) be an ordered set. An element a ∈ X is
called a minimal element of (X, ≼) if there is no x ∈ X such that x ≺ a. A maximal element a is defined
analogously (there is no x ≻ a). Theorem: Every finite (so not infinite!) partially
ordered set (X, ≼), with |X| ≥ 1, has at least one minimal element. This can be
proven by checking for every element or by contradiction over distance between
elements. Theorem: Let (X, ≼) be a finite partially ordered set. Then there exists
a linear ordering ≤ of X such that x ≼ y implies x ≺ y. In other words: each partial
ordering can be extended to a linear ordering. This can be proven by induction
on n = |X|. Let (X, ≼) be an ordered set. An element a ∈ X is called a smallest Fig. 2: An embedding
element of (X, ≼) if for every x ∈ X we have x ≼ a. A largest element is
defined analogously (x ≽ a). Note: smallest ≠ minimal and largest ≠
maximal! Let (X, ≼) and (X’, ≼’) be ordered sets. A mapping f: X → X’ is
called an embedding of (X, ≼) into (X’, ≼’) (see fig. 2) if the following
conditions hold: - f is injective – f(x) ≼’ f(y) is and only if x ≼ y.
If an embedding is surjective (and thus bijective), then it is an
isomorphism. Theorem: For every ordered set (X, ≼) there exists an embedding into the ordered Fig. 3: Bn
set (2x, ⊆). This is proven by checking the two conditions of an embedding. The ordered sets (2x,
⊆) contain a copy of every ordered set. For X = {1, 2, …, n} the set (2x, ⊆) is often denoted by Bn (see fig.
3). Let P = (X, ≼) be a poset. Elements x, y are called comparable if either x ≼ y or y ≼ x. Elements x, y
with neither x ≼ y nor y ≼ x are called incomparable. A set A ⊆ X is called a chain in P if every two of its
elements are comparable (in P). We use 𝜔(P) = max{|A| : A chain in P} to denote the maximum size of a
chain in P. A set A ⊆ X is called independent in P if any two of its elements are incomparable.
Independent sets are also called antichains. The set of all minimal elements in P is independent.
2
by Isabel Rutten

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper IsabelRutten. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €3,99. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 69052 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis
€3,99  3x  verkocht
  • (0)
In winkelwagen
Toegevoegd