Combinatorics and Logic Quiz

A relation R on a set A is symmetric if whenever aRb then bRa. In simpler terms, if (a, b) is in the relation, then (b, a) must also be in the relation.

A relation R on a set A is antisymmetric if whenever aRb and bRa then a = b. If two elements are related both ways, they must be the same element.

A relation R on a set A is transitive if whenever aRb and bRc, then aRc. In simpler terms, if (a, b) and (b, c) are in the relation, then (a, c) must also be in the relation.

A relation is reflexive if every element is related to itself. In other words, (a, a) is in the relation for every element 'a' in the set.

The smallest relation, R', that has a set of properties P, is called the P-closure of relation R.

A statement in the form "If p, then q." It asserts that if the first part (p) is true, the second part (q) must also be true.

A statement in the form "p if and only if q." It asserts that p and q have the same truth value.

A statement that asserts that a set of propositions (premises) leads to a conclusion.

An argument where the conclusion is true whenever all the premises are true.

An argument where the conclusion may not be true even if the premises are true.

A specific argument for a conditional statement. It states that if both 'p' and 'p → q' are true, then 'q' must also be true.

A statement or expression equivalent to another, meaning they have the same truth value in all cases.

A method or technique for proving the validity of an argument by examining all possible truth values of its components.

A way to arrange a set of objects in a specific order. For example, the letters ABCD can be arranged as ABCD, ACBD, BACD, etc.

The number of permutations of n objects taken r at a time. It represents the number of ways to choose and arrange r objects out of n.

A sequence of numbers where each number is the sum of the two numbers above it. It's a visual representation of binomial coefficients.

The coefficients that appear in the expansion of a binomial raised to a power (a + b)^n. They show how many ways you can choose r objects out of n.

The number of ways to choose r objects out of n without regard to order. It's represented by (nCr).

A theorem that states how to expand a binomial raised to a power (a + b)^n. It uses binomial coefficients to determine each term in the expansion.

A combination where the order of the objects is important. For example, choosing a password where the order of letters matters.

A combination where the order of the objects doesn't matter. For example, choosing a team where the order of members doesn't matter.

A matrix representation of a graph where each entry indicates whether two vertices are connected (1 for connected, 0 for not connected).

A representation of a graph where each vertex points to its neighbors using linked lists. This is especially efficient for graphs with many vertices and few connections.

A graph where the number of edges is proportional to the square of the number of vertices. Many connections.

A graph where the number of edges is proportional to the number of vertices or a smaller power of it. Few connections.

A graph where each edge has a value associated with it, representing a weight or cost.

A graph where multiple edges can exist between the same pair of vertices.

The process of adding or removing vertices in a graph.

The representation of a graph in memory using a data structure like an adjacency matrix or linked lists.

A traversal algorithm that explores a graph by going as deep as possible along each branch before backtracking.

A data structure used in DFS to keep track of possible paths. It acts like a stack of unfinished paths, allowing the algorithm to backtrack and explore other branches.

A field that stores the current processing state of a vertex in DFS. It helps prevent revisiting the same vertex multiple times.

A spanning tree formed by the edges traversed during a DFS. It shows the paths explored by the algorithm.

A traversal algorithm that explores a graph level by level, starting from the root.

A data structure used in BFS to keep track of vertices that are waiting to be processed.

A spanning tree formed by the edges traversed during a BFS. It shows the paths explored by the algorithm, prioritizing vertices closer to the starting vertex.

A field used in BFS to mark the current state of a vertex, preventing revisiting.

A subgraph of a directed graph G is a graph H(V', E') where V' is a subset of vertices in G, and E' is a subset of edges in G. The edges in E' must connect vertices in V'.

A subgraph of a directed graph G that includes all edges in G whose endpoints are in a subset of vertices V' is called the subgraph generated by V'.

The outdegree of a vertex in a directed graph is the number of edges leaving that vertex.

The indegree of a vertex in a directed graph is the number of edges entering that vertex.

A vertex with zero indegree, meaning no edges point towards it, is called a source.

A vertex with zero outdegree, meaning no edges leave it, is called a sink.

A directed path in a graph is a sequence of alternating vertices and edges, where each edge starts at the previous vertex and ends at the current vertex.

Similar to undirected graphs, a cycle in a directed graph is a path where the first and last vertices are the same, and all other vertices are distinct.