Discrete Mathematics
As my study process continues, I am now starting a phase of one of my favorite subjects: Math. Before delving into some aspects of statistics, about which I hope to blog soon, I am starting Discrete Mathematics.
What is Discrete Math? Why is it relevant to a Data Science career?
Well, since it provides the mathematical foundations for numerous algorithms utilized in data analysis and machine learning, discrete mathematics is an essential tool for data scientists. Let’s look at some of the most important discrete mathematics ideas and methods used in data science.
The concept of a set is one of discrete mathematics’ most fundamental ideas. A set is simply a collection of objects with particular properties, or elements. In data science, sets can be used to represent data, and many algorithms use sets to get insights from data.
A function is yet another significant idea in discrete mathematics. A rule that gives each input a distinct output is called a function. Functions can be used to make predictions about the data that will come in the future and to model the relationships between various pieces of data.
A subfield of discrete mathematics, combinatorics deals with counting and arranging set elements. In data science, combinatorics is used to figure out how many possible outcomes or data combinations there are, which can be used to make probabilistic predictions.
Two concepts in combinations: permutations and combinations. Both are ways of counting the number of ways that a set of items can be arranged or combined, but they differ in how they treat the order of the items.
Permutations are the number of ways that a set of items can be arranged in a specific order. For example, the permutations of the set {1, 2, 3} are {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. The set is the same, the order changes, and we count how many ways we can arrange the same set of three numbers.
Combinations, on the other hand, are the number of ways that a set of items can be selected without regard to order. For example, the combinations of the set {1, 2, 3} are {1, 2}, {1, 3}, {2, 3}, {1}, {2}, and {3}. The set of combinations is never the same. Once we count {1, 2}, we do not count {2, 1}.
In short, permutations take into account the order of the elements and combinations don’t.
Discrete mathematics includes the study of logic, which is the study of reasoning and the properties of statements. In logic, statements are declarative sentences that can be either true or false. For example, “The sky is blue” is a statement that can be evaluated as true or false.
Logical connectives are symbols or words used to connect statements and create compound statements. The most common logical connectives are “not” (often represented by the symbol “¬”), “and” (represented by the symbol “∧”), and “or” (represented by the symbol “∨”). For example, “The sky is not blue” is a compound statement created by negating the statement “The sky is blue” with the “not” connective. “It’s raining and the streets are wet” is a compound statement created with the “and” connective.
Truth tables are a way to evaluate the truth or falsehood of a compound statement. A truth table lists all possible combinations of truth values for the simple statements that make up the compound statement and the corresponding truth value of the compound statement. For example, the truth table for the conjunction “p ∧ q” would have the following rows: (T,T) | T , (T,F) | F, (F,T) | F, (F,F) | F.
Truth table for the conjunction “p ∧ q”:
De Morgan’s laws are two laws that state the relationship between the negation of a conjunction and the disjunction of negations, and the negation of a disjunction and the conjunction of negations. For example, the first De Morgan’s law states that ¬(p ∧ q) = ¬p ∨ ¬q. These laws are useful for producing logical equivalence, which is when two statements have the same truth value in all possible cases.
Get Rafael V. Rabinovich’s stories in your inbox
Join Medium for free to get updates from this writer.
Conditional statements are statements of the form “if p, then q”, which are denoted by “p → q”. The negation of a conditional statement is “not p or q”, which is denoted by “¬p ∨ q”. In a truth table, the rows where p is true and q is false are the only rows where the conditional statement is false.
Conjunctions and disjunctions: A conjunction is a compound statement formed by connecting two or more simple statements using the logical connective “and”, typically represented by the symbol “∧”. The conjunction is true only when all the simple statements it connects are true.
A disjunction is a compound statement formed by connecting two or more simple statements using the logical connective “or”, typically represented by the symbol “∨”. The disjunction is true when at least one of the simple statements it connects is true.
With these methods we can show the combinations that makes a hypothesis true or false, for example, a hypothesis like “If it’s raining, the streets are wet”, we can show that this statement is true if it’s raining and the streets are wet and false otherwise by using a truth table:
The conditional statement is only false when the antecedent is true and the consequent is false, this is the second row of the truth table. In all other cases the conditional statement is true.
The disjunction is true when at least one of the simple statements is true, which is the case in the rows 1,2 and 3. In the only case where both statements are false, the disjunction is false.
Another area of discrete mathematics that is relevant to data science is graph theory. Graphs can be used to analyze data patterns and to model relationships between various elements in a set. In order to extract insights from data, graph algorithms can be used to identify important nodes or edges in a graph.
In discrete mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relationships between objects. A graph is made up of a set of vertices (or nodes) and a set of edges that connect them. These edges can be directed or undirected, weighted or unweighted, and can represent any type of relationship between the vertices.
One of the basic concepts in graph theory is that of a walk, which is a sequence of vertices connected by edges, starting and ending at the same vertex. A path is a walk that doesn’t repeat any vertices, and a circuit is a walk that starts and ends at the same vertex and repeats at least one vertex.
Another concept in graph theory is that of a tree. A tree is a connected graph with no circuits. A decision tree is a tree-like graph that is used to model decisions and their consequences. It is a commonly used in computer science, Artificial Intelligence, and operations research.
Here is an example of a simple decision tree:
A tree is a connected graph with no circuits, it starts with a root node and it branches into multiple child nodes. The child nodes can be further branched into other child nodes.
In the case represented above, the decision tree is a tree because it starts with one node and branches into multiple child nodes and it has no circuits, the decision can’t come back to the previous decision point.
A forest is a collection of trees, it is not connected and it can have one or more trees. It can be used to represent multiple decision trees, or it can be used to represent different connected components of a disconnected graph.
Optimization also makes use of discrete mathematics. Given a set of constraints, optimization is the process of finding the best solution to a problem. The best data combination or model parameters can be found with the help of discrete optimization algorithms.
In conclusion, numerous data science algorithms and methods are theoretically supported by discrete mathematics. In order to comprehend and analyze data, concepts like sets, functions, combinatorics, graph theory, decision trees and optimization are all crucial. Data scientists can design algorithms that are more effective and efficient as well as more effectively extract insights from data if they have a solid understanding of discrete mathematics.
This is, of course, only a brief introduction. Please tell me in the comments if you would like me to delve further into this subject in future articles.
