DTG-1 Flashcards
Fagords betydning
What does Ø (the empty set) represent in discrete mathematics?
It represents a set with no elements, used when no values satisfy the given condition.
What is the union of two sets A and B in discrete mathematics?
The union of A and B, written as
A∪B
A∪B, is a set containing all elements that are in A, in B, or in both.
What is the intersection of two sets
A and B in discrete mathematics?
The intersection of A and B, written as
A∩B
A∩B, is the set of all elements that are in both A and B.
What is the difference between two sets A and B in discrete mathematics?
The difference of A and B, written as A \ B or A - B, is the set of all elements that are in A but not in B.
What is the negation of a statement in discrete mathematics, and how is it represented?
The negation of a statement reverses its truth value. If the statement is true, its negation is false, and if the statement is false, its negation is true. It is represented as ¬P or ∼P.
What does De Morgan’s law say about the negation of a conjunction (P AND Q)?
The negation of a conjunction (P AND Q) is the same as the disjunction of the negations of P and Q. In other words,
¬(P∧Q)≡(¬P)∨(¬Q).
What does De Morgan’s law say about the negation of a disjunction (P OR Q)?
The negation of a disjunction (P OR Q) is the same as the conjunction of the negations of P and Q. In other words,
¬(P∨Q)≡(¬P)∧(¬Q).
What is the result of a conjunction (P AND Q) when one of the parts is false?
The conjunction P and Q is false if either P or Q is false, since both must be true for the conjunction to be true.
What is the result of a disjunction (P OR Q) when both parts are false?
The disjunction P or Q is false only when both P and Q are false.
When is a conjunction (P AND Q) true?
A conjunction P and Q is true only when both P and Q are true.
When is a disjunction (P OR Q) true?
A disjunction P or Q is true if at least one of P or Q is true.
What does the cardinality of a set represent?
The cardinality of a set represents the number of elements in the set, indicating its “size.”
What is the Cartesian product of two sets?
The Cartesian product of two sets, A and B, is the set of all ordered pairs (a, b), where a is an element of A and b is an element of B, written as A × B.
What is an n-tuple in the Cartesian product of sets?
An n-tuple in the Cartesian product is an ordered collection of n elements, where each element comes from a corresponding set in the product. For example, in A₁ × A₂ × … × Aₙ, an n-tuple is (a₁, a₂, …, aₙ) with aᵢ ∈ Aᵢ.
what is a subset?
A subset is a set where every element is also contained in another set.
Is the empty set a subset of every set? Why?
Yes, the empty set is a subset of every set because it has no elements, so it automatically satisfies the subset condition.
How many subsets does a set with 4 elements have?
A set with 4 elements has
2^4=16 subsets.
What is a powerset?
A powerset is the set of all subsets of a given set, including the empty set and the set itself.
If a set A has 3 elements, how many elements does its powerset have?
The powerset of a set with 3 elements has
2^3=8 subsets.
What is the relationship between a set and its powerset in terms of cardinality?
If a set has n elements, the cardinality of its powerset is
2^n, because each element of the set can either be included in or excluded from a subset.
What is a relation?
A relation is a set of ordered pairs, where each element from one set is associated with an element from another set (or the same set).
What is a reflexive relation?
A relation is reflexive if every element in the set is related to itself, meaning for all a in the set, the pair (a, a) is in the relation.
What is a transitive relation?
A relation is transitive if whenever (a, b) and (b, c) are in the relation, the pair (a, c) must also be in the relation.
What is a symmetric relation?
A symmetric relation is a relation where if one element is related to another, the second element is also related to the first. For example, if a is related to b, then b is related to a.
What is an antisymmetric relation?
An antisymmetric relation is a relation where if one element is related to another and the second element is also related to the first, then the two elements must be the same. For example, if a is related to b and b is related to a, then a must equal b.
What does a relation represented as a graph consist of, and how can it be used to determine properties such as reflexivity, symmetry, and transitivity?
A relation represented as a graph consists of a set of vertices (elements of the set) and directed edges (ordered pairs in the relation). Reflexivity is checked by verifying that every vertex has a self-loop. Symmetry is determined by checking if every directed edge (x, y) is paired with its reverse (y, x). Transitivity is verified if, whenever there are edges (x, y) and (y, z), there is also an edge (x, z).
What are the three properties that define a partial order on a set?
A partial order on a set is a relation that is:
Reflexive: Every element is related to itself (a ≤ a).
Antisymmetric: If a ≤ b and b ≤ a, then a = b.
Transitive: If a ≤ b and b ≤ c, then a ≤ c.
What is the difference between a partial order and a total (or linear) order?
A partial order allows some pairs of elements to be incomparable (neither a ≤ b nor b ≤ a).
A total order requires that every pair of elements is comparable (for all a, b in the set, either a ≤ b or b ≤ a).
What is an example of a partial order in a real-world scenario?
An example of a partial order is the subset relation (⊆) on the power set of a set. For any subsets A, B, and C:
Reflexive: A ⊆ A.
Antisymmetric: If A ⊆ B and B ⊆ A, then A = B.
Transitive: If A ⊆ B and B ⊆ C, then A ⊆ C.
What is lexicographic order?
Lexicographic order is like dictionary order: compare the first elements of sequences, then the next, until a difference is found or the sequences end.
What is an equivalence relation?
An equivalence relation is a relation that is reflexive, symmetric, and transitive.
What does reflexive mean in an equivalence relation?
Reflexive means every element is related to itself:
a∼a.
What is a partition of a set, and how does it divide a set into disjoint subsets?
A partition of a set is a way of dividing the set into non-empty, disjoint subsets such that every element of the original set is included in exactly one subset. The subsets must be mutually exclusive and cover the entire set.
What is an equivalence class, and how is it related to an equivalence relation?
An equivalence class is a subset of a set, where all elements in the class are considered equivalent under a given equivalence relation. If a relation is an equivalence relation, it satisfies three properties: reflexivity, symmetry, and transitivity. The equivalence class of an element includes all elements that are related to it by the equivalence relation.
What does it mean for two integers to be congruent modulo n, and how is it related to their remainders when divided by n?
Two integers a and b are congruent modulo n (written as a ≡ b (mod n)) if their difference a - b is divisible by n. This means a and b leave the same remainder when divided by n.
Can you give an example of equivalence classes from something like “people born in the same year”?
This could be people born in q1, q2, q3 and q4: reflexivity: A person is always born in the same quarter as themselves.Symmetry: If person a is born in the same quarter as person b, then b is also born in the same quarter as a.Transitivity: If a is born in the same quarter as b, and b is born in the same quarter as c, thenaa is also born in the same quarter as c.
What are the congruence classes modulo 6, and what integers belong to each class?
The congruence classes modulo 6 are based on the remainder when dividing integers by 6. The classes are:
Class 0 modulo 6: Numbers like …, -12, -6, 0, 6, 12, 18, …
Class 1 modulo 6: Numbers like …, -11, -5, 1, 7, 13, 19, …
Class 2 modulo 6: Numbers like …, -10, -4, 2, 8, 14, 20, …
Class 3 modulo 6: Numbers like …, -9, -3, 3, 9, 15, 21, …
Class 4 modulo 6: Numbers like …, -8, -2, 4, 10, 16, 22, …
Class 5 modulo 6: Numbers like …, -7, -1, 5, 11, 17, 23, …
Each class contains integers that leave the same remainder when divided by 6.
