Glossary#

Adjacent Vertices#: Two vertices joined by an edge.
Biconditional#: \(A ⇔ B\) is biconditional logical connective which is true when \(p\) and \(q\) are same, i.e. both are false or both are true.
Bijective Function#: A function that is both injective (one-to-one) and surjectie (onto). It pairs every element in the domain with a unique element in the codomain, leaving no elements unmatched in either set, creating a direct one-to-one correspondence.
Binary Tree#: A rooted tree where each vertex has at most 2 children.
Bipartite Graph#: A graph whose vertices can be partitioned into two disjoint sets \(V_1\) and \(V_2\) such that every edge in \(E\) has one endpoint in \(V_1\) and one endpoint in \(V_2\).
Cardinality#: Denoted by \(|S|\), is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is \(\infty\).
Cartesian Product#: The Cartesian product of \(n\) number of sets \(A_1, A_2, ..., A_n\) denoted as \(A_1 \times A_2 \times ... \times A_n\) can be defined as all possible oredered pairs \((x_1, x_2, ..., x_n)\) where \(x_1 \in A, x_2 \in A_2, ..., x_n \in A_n\).
Closed Interval#: The set of all number sbetween two endpoints, including those endpoints. It is denoted by square brackets. \([a, b]\) is all numbers \(x\) such that \(a \leq x \leq b\).
Codomain#: Set of all allowable outputs.
Complement of a Set#: The complement of a set \(A\) (denoted by \(A'\)) is the set of elements which are not in set \(A\). Hence, \(A' = \{ x | x \notin A \}\).
Complete Bipartite Graph#: A bipartite graph whose vertices can be partitioned into two sets \(V_1\) and \(V_2\) and there is an edge for every vertex in \(V_1\) to every vertex in \(V_2\). Where \(|V_1| = m\) and \(|V_2| = n\), the complete bipartite graph is denoted \(K_{m, n}\).
Complete Graph#: A special kind of connected graph; not only must the graph be connected—there must be a path from every vertex to every other vertex—but each path must be of length \(1\).
Complete Inverse Image#: The set of all elements in the domain which are assigned to the codomain by the function.
Composite Function#: A new function created by using the output of one function as the input for another function.
Conjunction#: The conjunction of two propositions \(A\) and \(B\) (written as \(A ∧ B\)) is true if both the propositional variable \(A\) and \(B\) is true.
Connected Vertices#: Two vertices \(u, v\) in a graph if there exists a path from \(u\) to \(v\).
Constant Function#: A specific type of function where every input from the domain maps to the exact same single output in the codomain.
Contingency#: A formula which has both some true and some false values for every value of its propositional variables.
Contradiction#: A formula which is always false for every value of its propositional variables.
Contra-positive Conditional Statement#: The contra-positive of the conditional statement is computed by interchanging the hypothesis and the conclusion of the inverse statement.
Converse Conditional Statement#: The converse of the conditional statement is computed by interchanging the hypothesis and the conclusion.
Cycle Graph#: A graph with exactly one cycle. The cycle graph of order \(n\) is denoted \(C_n\).
Deduction#: A logical process where, starting from a set of premises (assumptions), we find a conclusion that logically follows.
Degree#: The number of edges incident with it. Note that a loop contributes 2 to its degree.
De Morgan’s Laws#: A pair of logical equivalence rules that show how negation interacts with conjunction and disjunction.
Directed Graph#: A pair \((V, E)\) consisting of a non-empty set of vertices \(V\) and a set of directed edges \(E\) with \(E \subseteq V \times V\).
Discrete Mathematics#: The branch of Math studying separate, countable objects rather than smooth, continuous changes.
Disjoint Set#: Two sets \(A\) and \(B\) are called disjoin sets if they do not have even one element in common.
Disjunction#: The disjunction of two propositions \(A\) and \(B\) (written as \(A ∨ B\)) is true if at least any of the propositional variable \(A\) or \(B\) is true.
Domain#: Set of all inputs for a function.
Edge#: A connection or link between two vertices (nodes) in a graph.
Empty Set#: A set that contains no elements. It is denoted by \(\emptyset\). As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.
Endpoint#: A vertex of an edge.
Equal Set#: If two sets contain the same elements, they are said to be equal.
Equivalent Set#: If the cardinalities of two sets are same, they are called equivalent sets.
Existential Quantifier#: States that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol \(∃\).
Finite Set#: A set which contains a definite number of elements.
Full Binary Tree#: A binary tree where every vertex has exactly 2 children or 0 children.
Function#: A rule that assigns each input exactly one output.
Graph#: A pair \((V, E)\) consisting of a non-empty set of vertices \(V\) and a set of edges \(E\).
Graph Coloring#: Some way of labeling or grouping vertices.
Graph Theory#: The study of graphs, which are mathematical structures used to model pairwise relations between objects.
Identity Function#: A special mapping on a set that returns every elemetn exactly as it was given.
Identity Matrix#: A square diagonal matrix with all entries of the main diagonal equal to \(1\). The identity matrix of order \(n\) is denoted \(I_n\).
Image#: The element in the codomain that the domain is mapped to.
Implication#: An implication \(A → B\) is the proposition if \(A\), then \(B\). It is false if \(A\) is true and \(B\) is false. The rest cases are true.
In-Degree#: The number of edges edges which terminate at \(v\). It is denoted \(deg^-(v)\).
Infinite Set#: A set which contains infinite number of elements.
Injective Function#: A one-to-one function where every distinct input in the domain maps to a unique output in the codomain.
Inverse Conditional Statement#: An inverse of the conditional statement is the negation of both hypothesis and the conclusion.
Inverse Function#: A mathematical operation that reverses or “undoes” the actions of an original function.
Level#: The distance of a vertex from the root.
Logical Connectives#: Symbols or words used to combine simple propositions into complex compound statements.
Loop#: An edge that starts and ends at the same vertex.
Many-to-One Function#: A function where two or more distinct inputs from the domain map to the same single output in the codomain.
Matrix#: A table of numbers, symbols, or mathematical objects coming from a set.
Matrix Multiplication#: The result of the multiplication is another matrix whose number of rows equals the left-hand matrix’s and whose number of columns equals the right-hand matrix’s.
Membership#: The basic property of sets from which all other operatiosn and properties can be defined. A set either contains an object or does not contain an object. Sets define a clear and unambiguous description of its members.
Modus Ponens#: Latin for “method of affirming”; a fundamental rule of inference which states that if a conditional statement and its antecedent are both true, then its consequent must also be true.
Multigraph#: A graph that allows multiple edges between vertices.
Negation#: The negation of proposition \(A\) (written as \(¬A\)) is false when \(A\) is true, and is true when \(A\) is false.
Natural Language Description#: Often called a semantic description of the set, where a sentence is used to describe the properties of objects contained in a set.
Neighbourhood#: The set of all vertices adjacent to \(v\) in \(G\).
Open Interval#: The set of all numbers between two end points, excluding those endpoints. It is denoted by parentheses. \((a, b)\) is all numbers \(x\) such that \(a < x < b\).
Out-Degree#: The number of edges which start at \(v\). It is denoted \(deg^+(v)\).
Overlapping Set#: Two sets that have at least one common element are called overlapping sets.
Parallel Edges#: Two or more edges joining a pair of vertices.
Planar Graph#: A graph that can be drawn with no overlapping edges.
Power Set#: Power set of a set \(S\) is the set of all subsets of \(S\) including the empty set. The cardinality of a power set of a set \(S\) of cardinality \(n\) is \(2^n\). Power set is denoted as \(P(S)\).
Predicate#: An expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.
Predicate Logic#: Deals with predicates, which are propositions containing variables.
Proper Subset#: A set \(X\) is a proper subset of set \(Y\) (written as \(X \subset Y\)) if every element of \(X\) is an element of set \(Y\) and \(|X| < |Y|\).
Proposition#: A collection of declarative statements that has either a truth value true or false.
Propositional Equivalence#: Two statements \(A\) and \(B\) are logically equivalent if either: the truth tables of each statement have the same truth values; or, the biconditional statement \(A ⇔ B\) is a tautology.
Propositional Logic#: Concerned with statements to which the truth values, true and false, can be assigned. The purpose is to analyze these statements either individually or in a composite manner.
Range#: Subset of the codomain.
Root#: “Oldest” ancestor in a rooted tree.
Rooted Tree#: A tree in which one of the vertices has been designated as the root.
Roster Form#: The set is represented by listing all the elements comprising it.
Rules of Inference#: Standard logical templates used to build valid arguments and prove conclusions from given premises in propositional logic.
Scalar Multiplication#: A simple operation which multiplies a single number against each entry of a matrix to produce another matrix of the same dimensions.
Set#: An unordered collection of different elements.
Set Builder Notation#: The set is defined by specifying a property that elements of the set have in common.
Set Difference#: The set difference of sets \(A\) and \(B\) (denoted by \(A - B\)) is the set of elements which are only in \(A\) but not in \(B\). Hence, \(A - B = \{ x | x \in A \text{AND} x \notin B \}\).
Set Intersection#: The intersection of sets \(A\) and \(B\) (denoted by \(A \cap B\)) is the set of elements which are in both \(A\) and \(B\). Hence, \(A \cap B = \{ x | x \in A \text{AND} x \in B \}\).
Set Theory#: Forms the basis of several other fields of study like counting theory, relations, graph theory, and finite state machines.
Set Union#: The union of sets \(A\) and \(B\) (denoted by \(A \cup B\)) is the set of elements which are in \(A\), in \(B\), or in both \(A\) and \(B\). Hence, \(A \cup B = \lbrace x \:| \: x \in A\ OR\ x \in B \rbrace\).
Singleton Set#: A set that contains only one element. A singleton set is denoted by \(\{ s \}\).
Square Matrix#: When \(m = n\), the matrix is a square matrix.
Subset#: A set \(X\) is a subset of set \(Y\) (written as \(X \subseteq Y\)) if every element of \(X\) is an element of set \(Y\).
Surjective Function#: Also called an onto function; a function where every element in the codomain is mapped to by at least one element from the domain.
Symmetric Difference#: The set of elements which are members of \(A\) or members of \(B\) but not both. The symmetric difference of \(A\) and \(B\) is denoted \(A \oplus B\).
Tautology#: A formula which is always true for every value of its propositional variables.
Transpose#: An operation performed on a matrix which reverses its dimensions. In particular, it exchanges the rows of the matrix with its columns.
Tree#: A simple connected graph with no cycles.
Universal Quantifier#: States that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol \(∀\).
Universal Set#: It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set. Universal sets are represented as \(U\).
Venn Diagram#: A schematic diagram that shows all possible logical relations between different mathematical sets.
Vertex#: A discrete object of the graph.
Weighted Graph#: A graph where each edge is assigned a numerical label or “weight”.
Well Formed Formula#: A predicate holding either: all propositional constants and propositional variables are WFFs; if \(x\) is a variable and \(Y\) is a WFF, \(∀xY\) and \(∃xY\) are also WFFs; truth value and false values are WFFs; each atomic formula is a WFF; or, all connectives connecting WFFs are WFFs.
Wheel Graph#: A cycle graph in which one extra vertex has been added which connects to every other vertex in the cycle. The wheel graph of order \(n\) is denoted \(W_n\).
Zero Matrix#: A matrix with all zero entries. The \(m\) by \(n\) zero matrix is denoted by \(0_{m, n}\).
Zero-One Matrix#: A special class of matrices whose entries come from the set \(\{ 0, 1 \}\).