A Word About The Primer
This primer is by no means exhaustive of the subject. Treat it as what you’d learn before you’re fully introduced to the subject. I hope this brief primer on Discrete Mathematics will be of some use to you. This subject is extremely useful in describing objects and problems in computer science especially in these topics: algorithms, programming languages, databases, and cryptography. In the future I intend on going into depth into each of the main areas that’ll be discussed in this primer. Enjoy!
What is discrete mathematics?
It is the branch of mathematics that only deals with objects that can only assume distinct separated values.
There are five main areas we will discuss, in the following order:
- Logic
- Set theory
- Relations
- Functions
- Combinatorics
- Graphs
Logic
What is Logic?
It is the study of correct reasoning. We will be focusing on idealization and then formalization. Informal logic is the use of natural language arguments.
Formal logic is the study of inference with purely formal content eg. of formal logic would be symbolic logic and syllogistic logic (for example found in Aristotle’s work).
Let us begin by setting the foundations. Take this natural language statement
“If I am hungry, then I eat”.
Let ‘hungry’ be the premise A and ‘eat’ be the conclusion B. We would try and formalize it like this,
A => B, (which reads, A implies B)
N.b. a premise and a conclusion are both propositions.
Logical Expressions
We care about form NOT content. The truth value is determined by the validity of form.
For example, 10 < 4 is FALSE, whilst 10 > 4 is TRUE.
Logical Connectives
A proposition P is a statement that can be either true or false.
Let the P value ‘1’ imply true and Let the P value ‘0’ imply false.
Also let another proposition exist; let Q value ‘1’ imply true and let the Q value ‘0’ imply false.
The following are logical connectives which lie between propositions that contain truth values, and hence produce truth values of their own based on the combination of the propositions truth values and their respective connectives:
Negation
OR
AND
Equivalence
Implication
Exclusive OR
The Three Laws
Now we also introduce the proposition R which is a statement that can be either true or false.
Let the R value ‘1’ imply true and Let the R value ‘0’ imply fals
The Associative Law
The Distributive Law
De Morgan’s Laws
Logical formula
Are made up of propositions, parentheses, and these following connectives:
| Tautology | Satisfiable | Contradiction |
| No matter what logical value P and Q have, the formulation will result in TRUE | TRUE in at least one interpretation of P and Q | Formula is false no matter what logical value P and Q have |
Quantifiers
What is a quantifier? A quantifier in natural language is a word that lends meaning on the property of quantity (how much). Examples of quantifiers would be ‘all’, ‘some’, ‘many’, ‘few’, ‘most’, and ‘no’.
Set Theory
What is a set?
A collection of data. This data is referred to as elements (of the set). No elements are repeated in the set. An important feature is that sets are unordered, which means the order by which we display elements has no effect on its being.
Eg. if A = {1, 2, 3, 4} & B = {2, 4 , 1, 3} & there is no order then, A = B
With this understanding, we can more concisely define a set as a collection of well-defined distinct objects.
Often we would like to define an infinite set. The obvious problem would be that we cannot write down all its elements. Therefore, we can also define sets by their characteristic property.
Set Operations
Subset
Cardinality
Union
Intersection
Complements
Relations
Relations are the study of relationships between mathematical objects. We can relate with n elements (n denoting and positive natural number).
A binary relation is when we have two elements (objects) that are in relation to each other. The formal way of denoting any relation between x and y would be as follows: x ~ y
Eg. 4 < 8, or “I am in relation to being the student of my professor”.
Properties of Binary Relations
Number Sets
Functions
A function is a relation that assigns values to other values. In other words, it is a relation between a set A and a set B.
Properties
Function Composition
It is the pointwise application of a function to result in another function.
Combinatorics
Simply put, it is the study of counting.
Permutations
Is an arrangement of objects without repetition where order is important.
Combinations
Is an arrangement of objects without repetition where order is not important
Counting Techniques Flowchart
Graphs
What is a graph?
It is a collection of points called nodes or vertices, and lines between those points called edges. An edge connects exactly two nodes. An edge can be oriented; pointing to a direction, or unoriented.
