Discrete Terminology Flashcards
What is the definition of a set in discrete mathematics?
A set is a collection of distinct objects, considered as an object in its own right.
True or False: The empty set is a subset of every set.
True
What does the acronym ‘N’ represent in discrete mathematics?
N represents the set of natural numbers.
Fill in the blank: A __________ is a mathematical statement that can be either true or false.
proposition
What is the definition of a function?
A function is a relation that assigns exactly one output for each input from a specific set.
What does the acronym ‘P’ stand for in the context of propositions?
P stands for a proposition.
What is the difference between a finite set and an infinite set?
A finite set has a limited number of elements, while an infinite set has no limit on the number of elements.
True or False: The intersection of two sets contains all elements from both sets.
False
What is the definition of a relation?
A relation is a set of ordered pairs, typically representing a relationship between elements of two sets.
What does the acronym ‘Z’ represent?
Z represents the set of integers.
What is a bijective function?
A bijective function is a function that is both injective (one-to-one) and surjective (onto).
Fill in the blank: A __________ is a statement that connects two propositions using logical connectors.
compound proposition
What is the principle of mathematical induction?
Mathematical induction is a method of proving statements for all natural numbers.
True or False: A complete graph has an edge between every pair of vertices.
True
What does the acronym ‘GCD’ stand for?
GCD stands for Greatest Common Divisor.
What is the definition of a graph in discrete mathematics?
A graph is a collection of vertices and edges that connect pairs of vertices.
What is the difference between directed and undirected graphs?
In directed graphs, edges have a direction, while in undirected graphs, edges do not have a direction.
Fill in the blank: The __________ of a graph is a subset of its edges that connects all vertices without cycles.
spanning tree
What does the acronym ‘LCM’ represent?
LCM represents Least Common Multiple.
True or False: A path in a graph can visit the same vertex more than once.
False
What is a prime number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
What is a Boolean algebra?
Boolean algebra is a mathematical structure that captures the essentials of logical operations.
Fill in the blank: Two sets A and B are __________ if they have no elements in common.
disjoint
What is the power set of a set?
The power set of a set is the set of all possible subsets of that set, including the empty set and the set itself.
What is the definition of a permutation?
A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement.
What does the acronym ‘RSA’ stand for in cryptography?
RSA stands for Rivest-Shamir-Adleman, which is a public-key cryptosystem.
True or False: In a tree, every pair of vertices is connected by exactly one path.
True
What is a combination?
A combination is a selection of items from a larger set where the order of selection does not matter.
Fill in the blank: The __________ of two sets A and B is the set of elements that are in A or B or in both.
union
What is the definition of an isomorphic graph?
Two graphs are isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves the structure.
What does the acronym ‘DFS’ stand for in graph theory?
DFS stands for Depth-First Search.
True or False: A directed acyclic graph (DAG) contains cycles.
False
What is the definition of an algorithm?
An algorithm is a finite sequence of well-defined instructions to solve a problem or perform a task.
What is the significance of Big O notation?
Big O notation describes the upper bound of the time complexity of an algorithm.
Fill in the blank: The __________ of a function is the set of all possible outputs.
range
What does the acronym ‘NP’ represent in computational theory?
NP stands for Nondeterministic Polynomial time.
