Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Math 1 > Unit 6 > Flashcards

Unit 6 Flashcards

1
Q

A binary relation is a way of expressing a blank between two sets

A

relationship

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Mathematically, a blankbetween two sets A and B is a subset R of A x B. The term binary refers to the fact that the relation is a subset of the Cartesian product of two sets.

A

binary relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

For a ∈ A and b ∈ B, the fact that (a, b) ∈ R is denoted by blank.

A

aRb

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In an blank of a relation R on sets A and B, the elements of A are listed on the left, the elements of B are listed on the right, and there is an arrow from a ∈ A to b ∈ B if aRb.

A

arrow diagram

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

A blank of relation R between A and B is a rectangular array of numbers with |A| rows and |B| columns. Each row corresponds to an element of A and each column corresponds to an element of B. For a ∈ A and b ∈ B, there is a 1 in row a, column b, if aRb. Otherwise, there is a 0.

A

matrix representation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

It is possible to have a relation between two sets A and B in which A = B. A binary relation on a set A is a subset of A x A. The set A is called the blank of the binary relation.

A

domain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

An arrow diagram for a relation R on a finite set A requires only one copy of the elements of A. There is an arrow from a to b if blank.

A

aRb

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

An element that is related to itself is indicated by an arrow called a blank

A

self-loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

The relation R is blank if for every x ∈ A, xRx.

A

reflexive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

The relation R is blank if for every x ∈ A, it is not true that xRx.

A

anti-reflexive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

The relation R is blank if for every x,y, z ∈ A, xRy and yRz imply that xRz.

A

transitive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

The relation R is blank if for every x,y ∈ A, xRy implies that yRx.

A

symmetric

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

The relation R is blank if for every x,y ∈ A, xRy and yRx imply that x = y.

A

anti-symmetric

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Each of the properties of a binary relation is stated as a blank. Therefore in order to establish that relation has a property, the condition must be shown to be true for all the elements in the domain.

A

universal condition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

A blank (or digraph, for short) consists of a pair (V, E).

A

directed graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

V is a set of blank, and E, a set of directed blank, is a subset of V × V.

A

vertices
edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

An individual element of V is called a blank. A blank is typically pictured as a dot or a circle labeled with the name of the vertex.

A

vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

An blank (u, v) ∈ E, is pictured as an arrow going from the vertex labeled u to the vertex labeled v.

A

edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

The vertex u is the tail of the edge (u, v) and vertex v is the head. If the head and the tail of an edge are the same vertex, the edge is called a blank.

A

self-loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

The blank of a vertex is the number of edges pointing into it.

A

in-degree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

The blank of a vertex is the number of edges pointing out of it.

A

out-degree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

A blank from v0 to vl in a directed graph G is a sequence of alternating vertices and edges that starts and ends with a vertex.

A

walk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

The blank of a walk is l, the number of edges in the walk.

A

length

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

An blank is a walk in which the first and last vertices are not the same.

A

open walk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

A blank is a walk in which the first and last vertices are the same.

A

closed walk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

A blank is an open walk in which no edge occurs more than once.

A

trail

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

A blank is a closed walk in which no edge occurs more than once.

A

circuit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

A blank is a trail in which no vertex occurs more than once.

A

path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

A blank is a circuit of length at least 1 in which no vertex occurs more than once, except the first and last vertices which are the same.

A

cycle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

<a, c, d, a>
is a blank because the only repeated vertices are the first and the last, a.

A

cycle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

The circuit <a, c, a, d, a>
is blank because the vertex a appears in the middle of the circuit as well as at the beginning and the end.

A

not a cycle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

The circuit <b, c, d, c, b>
is also blank because the vertex c is repeated in the middle of the circuit.

A

not a cycle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

A blank is a link between two sets and is a collection of ordered pairs that contains one object from each of the given set. The arrow diagram for a binary relation is a directed graph.

A

relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

The blank of binary relations is a concept of forming a new relation from two given relations.

A

composition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

The composition of two relations, B and W, on set Y is denoted blank
.

A

W o B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

The ordering of a composition is to apply the output of the blank function as the input to the blank function.

A

second
first

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Let G be a directed graph. Let u and v be any two vertices in G. There is an edge from u to v in Gk if and only if there is a walk of length k from u to v in G is what theorem

A

The Graph Power Theorem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

The relation R+ is called the blank and is the smallest relation that is both transitive and includes all the pairs from R. In other words, any relation that contains all the pairs from R and is transitive must include all the pairs in R+.

A

transitive closure of R

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

If G is a directed graph, then G+ is called the blank. The animation below shows how the graph G+(with 4 vertices) is determined from the graphs G1 through G4.

A

transitive closure of G

40
Q

If there are three elements x, y, z ∈ A such that (x, y) ∈ R, (y, z) ∈ R and (x, z) ∉ R, then add blank.

A

(x, z) to R

41
Q

To find the blank start with the pairs in R and add pairs until you cannot add any more pairs.

A

transitive closure of relation R,

42
Q

According to the blank, given a directed graph, G and any two vertices in G (u and v) then there is an edge from u to v in Gk if and only if there is a walk of length k from u to v in G.

A

graph power theorem

43
Q

In a directed graph, the number of lengths of walks from one vertex to another is the blank.

A

graph power

44
Q

blank is the number of times (length of walks) a relation is composed with itself. For example, if it takes 2 walks to get from a to c, by a to b and b to c, then it is graph power 2. When a relation is composed with itself, then the resulting relation must contain pairs from the original G with a walk length of 2 in order to be valid. If the same relation is composed yet again - a third time - the resulting relation would contain only pairs whose walks in G are length 3. This pattern continues. The number of times (length of walks) a relation is composed with itself is known as the power of the relation.

A

Powers of relations

45
Q

If you create the union of all Gk , then the resulting relation from the union is the blank that is transitive and contains all the pairs from G. This is referred to as the transitive closure of G and is denoted as G+ .

A

smallest relation

46
Q

An n × m blank over a set S is an array of elements from S with n rows and m columns.

A

matrix

47
Q

Each element in a blank is called an entry.

A

matrix

48
Q

A matrix is called a blank if the number of rows is equal to the number of columns.

A

square matrix

49
Q

A directed graph G with n vertices can be represented by an n × n matrix over the set {0, 1} called the blank for G. If matrix A is the adjacency matrix for a graph G, then Ai,j = 1 if there is an edge from vertex i to vertex j in G. Otherwise, Ai,j = 0.

A

adjacency matrix

50
Q

If mathematical operations, such as addition and multiplication, are defined on a set S, then matrix addition and multiplication can be defined for matrices over the set S. A blank is a matrix whose entries are from the set {0, 1}.

A

Boolean matrix

51
Q

Each entry of the matrix A × B is computed by taking the dot product of a row of A and a column of B. If A and B are n × n matrices, the blank of row i of A and column j of B is the sum of the product of each entry in row i from A with the corresponding entry in column j from B

A

dot product

52
Q

If A and B are n × n matrices over the integers, then the blank of A and B, denoted AB or A·B, is another n × n matrix such that (AB)i,j is the result of taking the dot product of row i of matrix A and column j of matrix B.

A

matrix product

53
Q

Matrix multiplication is associative, meaning that if A, B, and C are all n × n matrices, then A(BC) = (AB)C. However, matrix multiplication is not commutative because there are matrices A and B for which AB ≠ BA. The kth blank A is the product of k copies of A:

A

power of a matrix

54
Q

f G is a directed graph, then the kth power of G (Gk) represents walks of length k in G. There is an edge from vertex v to vertex w in Gk if and only if there is a walk of length exactly k from v to w in G. Matrix multiplication provides a systematic way of computing Gk. What is it?

A

Take the adjacency matrix A for graph G.
Compute Ak by repeated matrix multiplication.
The matrix Ak is the adjacency matrix for graph Gk. There is a walk of length k in G from vertex v to vertex w if and only if the entry in row v, column w in Ak is 1.

55
Q

The sum of two matrices A and B is well defined if A and B have the same number of rows and the same number of columns. If A and B are two m × n matrices, then the blank of A and B, denoted A + B, is also an m × n matrix such that (A + B)i,j = Ai,j + Bi,j for all 1 ≤ i ≤ m and 1 ≤ j ≤ n.

A

matrix sum

56
Q

A relation R on a set A is a blank if it is reflexive, transitive, and anti-symmetric.

A

partial order

57
Q

The domain along with a partial order defined on it is denoted (A, ⪯) and is called a blank

A

partially ordered set or poset.

58
Q

The pair (N, ⪯) satisfies the conditions for a partial order how

A

x evenly divides itself (reflexive)
If x evenly divides y and y evenly divides x, then x = y (anti-symmetric)
If x evenly divides y and y evenly divides z, then x evenly divides z (transitive)

59
Q

Two elements of a partially ordered set, x and y, are said to be blank if x ⪯ y or y ⪯ x.

A

comparable

60
Q

A partial order is a total order if every two elements in the domain are blank. The partial order (Z, ≤) is an example of a total order.

A

comparable

61
Q

An element x is a blank element if there is no y ≠ x such that y ⪯ x.

A

minimal

62
Q

An element x is a blank element if there is no y ≠ x such that x ⪯ y.

A

maximal

63
Q

A blank, named after the 20th century German mathematician Helmut Hasse, is a useful way to depict a partial order on a finite set. Each element is represented by a labeled point.The idea is to show precedence relationships by placing elements that are greater than others towards the top of the diagram. Some precedence relationships are depicted with lines between elements, but only enough to make the relationship between elements clear. Otherwise, the goal is to not clutter the diagram with unnecessary edges.

A

Hasse diagram

64
Q

The rules for placement and for connecting segments in a Hasse diagram are what

A

For any x and y such that x ≠ y:

If x ⪯ y, then make x appear lower in the diagram than y.
If x ⪯ y and there is no z such that x ⪯ z and z ⪯ y, then draw a segment connecting x and y.

65
Q

A blank acts similar to the ≤ operator on the elements of its domain

A

partial order

66
Q

A blank acts similar to the < operator on the elements of its domain

A

strict order

67
Q

A relation R is a blank if R is transitive and anti-reflexive. The notation a ≺ b is used to express aRb and is read “a is less than b”. The difference between the ≺ and the < symbols is the slight curve in the ≺ symbol. The domain along with the strict order defined on it is called a strictly ordered set and is denoted by (A, ≺).

A

strict order

68
Q

The arrow diagram for a strict order is basically an arrow diagram for a partial order without the blank

A

self loops

69
Q

The definitions for a partial order carry over in a natural way to strict orders. Two elements, x and y, are said to be blank if x ≺ y or y ≺ x.

A

comparable

70
Q

A strict order is a blank if every pair of elements is comparable.

A

total order

71
Q

An element x is a blank if there is no y such that y ≺ x. An element x is a blank if there is no y such that x ≺ y.

A

minimal element
maximal element

72
Q

Strict orders are blank

A

anti-symmetric

73
Q

Relations with strict order have the transitive and anti-symmetry properties, but they are not blank.

A

reflexive

74
Q

The symbol used to show a blank relation is ≺. The domain is denoted by (A, ≺).

A

strict order

75
Q

The definitions for strict order are very similar to partial order relations. The main difference is the blank (or equality) being removed for strict order.

A

reflexive

76
Q

A blank (or DAG for short) is a directed graph that has no positive length cycles.

A

directed acyclic graph

77
Q

DAGs are particularly useful for representing blank relationships.

A

precedence

78
Q

Let G be a directed graph. G has no positive length cycles if and only if G+ is a blankj.

A

strict order

79
Q

If a DAG G is transitive, then G+ = G. Thus, the theorem above implies that a directed graph G is a strict order if and only if G is blank and blank.

A

acyclic and transitive

80
Q

A blank for a DAG is an ordering of the vertices that is consistent with the edges in the graph.

A

topological sort

81
Q

A relation R is an blank if R is reflexive, symmetric, and transitive.

A

equivalence relation

82
Q

If a relation R is an equivalence relation, the notation blank is used to express aRb. Blank is read “a is equivalent to b”.

A

a~b

83
Q

If A is the domain of an equivalence relation and a ∈ A, then [a] is defined to be the set of all x ∈ A such that a~x. The set [a] is called an blank

A

equivalence class.

84
Q

what is the Structure of equivalence relations.

A

Consider an equivalence relation on a set A. Let x,y ∈ A:

If x~y then [x] = [y]
If it is not the case that x~y, then [x] ∩ [y] = ∅

85
Q

A blank of a set A is a set of non-empty subsets of A that are pairwise disjoint and whose union is A.

A

partition

86
Q

Equivalence classes are intimately related to blank and, in fact, define each other. An equivalence relation between equivalence classes defines a blank. Likewise, a blank defines an equivalence relation between equivalence classes.

A

partitions

87
Q

A set of sets is blank if the intersection of any pair of the sets is empty.

A

pairwise disjoint

88
Q

Pairwise disjoint sets have no blank of any of the sets.

A

intersection

89
Q

An equivalence relation has what three properties: blank, blank, and blank. An equivalence relation, R, is denoted as a ~ b for aRb.

A

symmetry, reflexive, and transitive.

90
Q

An equivalence relation is easy to spot when shown as a directed graph: each vertex has a blank.

A

self- loop

91
Q

An blank is denoted by [a] and is defined to be the set of all x ∈ A such that a ~ x, given A is the domain of an equivalence relation and a is also an element of A. The example of the set of natural numbers, which all have the same remainder when divided by 3, would have classes of [0], [1], and [2].

A

equivalence class

92
Q

According to the structure of equivalence relations theorem, two equivalence classes are either blank or blank

A

identical or completely different (disjoint).

93
Q

The set of all distinct equivalence classes of set A is called a blank of the set A. The “distinct” qualification just means a class is only included once if there are two equal equivalence classes.

A

partition

94
Q

The blank chooses n-tuples from a relational database that satisfy particular conditions on their attributes.

A

selection operation

95
Q

The blank takes a subset of the attributes and deletes all the other attributes in each of the n-tuples.

A

projection operation

96
Q

A blank is an attribute (or set of attributes) which provides a unique identity for each n-tuple in the database.

A

key

Discrete Math 1 (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions