Discrete Mathematics

Distinct and separable mathematical structures

What is Discrete Mathematics?

Discrete Mathematics is a branch of mathematics that is concerned with “discrete” mathematical structures instead of “continuous”. Discrete mathematical structures include objects with distinct values like graphs, integers, logic-based statements, etc. It is increasingly being applied in the practical fields of mathematics and computer science. It is an excellent tool for improving reasoning and problem-solving capabilities. Discrete Mathematics includes fundamental concepts of Sets, Relations and Functions, Mathematical Logic, Group theory, Counting Theory, Probability, Mathematical Induction and Recurrence Relations, Graph Theory, Trees and Boolean Algebra.

Discrete Mathematics Topics

Set Theory:

A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using a set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set.

Example − Set of odd numbers less than 10, A = {1,3,5,7,9}

The cardinality of a Set:

The cardinality of a set S, denoted by |S|, is the number of elements of the set. The number is also referred to as the cardinal number. If a set has an infinite number of elements, its cardinality is ∞.

Example − |{1,4,3,5}|=4, |{1,2,3,4,5,…}|=∞

Types of Sets:

1. Finite Set

A set which contains a definite number of elements is called a finite set.

Example − S={x|x∈N and 70>x>50}

2. Infinite Set

A set which contains an infinite number of elements is called an infinite set.

Example − S={x|x∈N and x>10}

3. Subset

A set X is a subset of set Y (Written as X⊆Y) if every element of X is an element of set Y.

Example 1 − Let, X = {1,2,3,4,5,6}and Y = {1,2}. Here set Y is a subset of set X as all the elements of set Y are in set X. Hence, we can write Y⊆X.

4. 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.

Example − We may define U as the set of all animals on Earth. In this case, the set of all mammals is a subset of U, the set of all fishes is a subset of U, the set of all insects is a subset of U, and so on.

5. Empty Set or Null Set

An empty set contains no elements. It is denoted by ∅. As the number of elements in an empty set is finite, an empty set is a finite set. The cardinality of an empty set or null set is zero.

Example − S={x|x∈N and 7<x<8}=∅

6. Unit Set

Singleton set or unit set contains only one element. A singleton set is denoted by {s}.

Example − S={x|x∈N, 7<x<9} = {8}

7. Equal Set

If two sets contain the same elements they are said to be equal.

Example − If A={1,2,6} and B={6,1,2} they are equal as every element of set A is an element of set B and every element of set B is an element of set A.

8. Equivalent Set

If the cardinalities of two sets are the same, they are called equivalent sets.

Example − If A={1,2,6} and B={16,17,22} they are equivalent as the cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3

9. Disjoint Set

Two sets A and B are called disjoint sets if they do not have even one element in common. Therefore, disjoint sets have the following properties

• n(A∩B) = ∅
• n(A∪B) = n(A)+n(B)

Example − Let, A={1,2,6} and B={7,9,14} there is not a single common element, hence these sets are overlapping sets.

Relations:

Whenever sets are discussed, the relationship between the elements of the sets is the next thing that comes up. Relations may exist between objects of the same set or between objects of two or more sets.

Types of Relations

• The Empty Relation between sets X and Y, or on E, is the empty set ∅
• The Full Relation between sets X and Y is the set X×Y
• The Identity Relation on set X is the set {(x,x)|x∈X}
• The Inverse Relation R’ of a relation R is defined as − R′={(b, a)|(a,b)∈R}
• A relation R on set A is called Reflexive if ∀a∈A is related to an (aRa holds)
• A relation R on set A is called Irreflexive if no a∈A is related to an (aRa does not hold).
• A relation R on set A is called Symmetric if xRy implies yRx, ∀x∈A and ∀y∈A.
• A relation R on set A is called Anti-Symmetric if xRy and yRx imply x=y ∀x∈A and ∀y∈A.
• A relation R on set A is called Transitive if xRy and yRz imply xRz,∀x,y,z∈A.

Functions:

A function or mapping (Defined as f: X→Y) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function ‘f’.

Function ‘f’ is a relation on X and Y such that for each x∈X, there exists a unique y∈Y such that (x,y)∈R. ‘x’ is called pre-image and ‘y’ is called the image of function f.

A function can be one-to-one or many-to-one but not one-to-many.

The inverse of a Function

The inverse of a one-to-one corresponding function f:A→B, is the function g:B→A, holding the following property −

f(x) = y ⇔ g(y) = x

The function f is called invertible if its inverse function g exists.

Composition of Functions

Two functions f: A→B and g: B→C can be composed to give a composition go f. This is a function from A to C defined by (go f)(x) = g(f(x))

Propositional Logic:

A proposition is a collection of declarative statements that has either a truth value of “true” or a truth value of “false”. A propositional consists of propositional variables and connectives. We denote the propositional variables with capital letters (A, B, etc). The connectives connect the propositional variables.

Some examples of Propositions are given below −

• “Man is Mortal”, returns the truth value “TRUE”
• “12 + 9 = 3–2”, it returns the truth value “FALSE”

Connectives

OR (∨) − The OR operation of two propositions A and B (written as A∨B) is true if at least any of the propositional variables A or B is true.

AND (∧) − The AND operation of two propositions A and B (written as A∧B) is true if both the propositional variable A and B are true.

Negation (¬) − The negation of proposition A (written as ¬A) is false when A is true and is true when A is false.

Implication / if-then (→) − An implication A→B is the proposition “if A, then B”. It is false if A is true and B is false.

If and only if (⇔) − A⇔B is bi-conditional logical connective which is confirmed when p and q are the same, i.e. both are false or both are true.

Tautologies:

A Tautology is a formula which is always true for every value of its propositional variables.

Example − Prove [(A→B)∧A]→B is a tautology.

Contradictions:

A Contradiction is a formula which is always false for every value of its propositional variables.

Example − Prove (A∨B)∧[(¬A)∧(¬B)] is a contradiction

Predicate Logic:

A predicate is 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.

The following are some examples of predicates −

• Let E(x, y) denote “x = y”
• Let X(a, b, c) denote “a + b + c = 0”
• Let M(x, y) denote “x is married to y”

Rules of Inference:

To deduce new statements from the statements whose truth we already know, Rules of Inference are used.

Rules of Inference provide the templates or guidelines for constructing valid arguments from the statements that we already have.

De Morgan’s Law:

De Morgan’s Laws give a pair of transformations between the union and intersection of two (or more) sets in terms of their complements. The laws are −

(A∪B)′=A′∩B′

(A∩B)′=A′∪B′

Group Theory:

Group Theory is a branch of mathematics and abstract algebra that defines an algebraic structure named a group. Generally, a group comprises a set of elements and an operation over any two elements on that set to form a third element also in that set.

• Closure − For every pair (a,b)∈S, (aοb) has to be present in the set S.
• Associative − For every element a,b,c ∈ S, (aοb)οc = aο(bοc) must hold.
• Group: A group is a monoid with an inverse element. The inverse element (denoted by I) of a set S is an element such that (aοI) = (Iοa) = a, for each element a∈S. So, a group holds four properties simultaneously — i) Closure, ii) Associative, iii) Identity element, iv) Inverse element. The order of a group G is the number of elements in G and the order of an element in a group is the least positive integer n such that an is the identity element of that group G.

Abelian Group:

An abelian group G is a group for which the element pair (a,b)∈G always holds commutative law. So, a group holds five properties simultaneously — i) Closure, ii) Associative, iii) Identity element, iv) Inverse element, v) Commutative.

Cyclic Group:

A cyclic group is a group that can be generated by a single element. Every element of a cyclic group is a power of some specific element which is called a generator. A cyclic group can be generated by a generator ‘g’, such that every other element of the group can be written as a power of the generator ‘g’.

Subgroup:

A subgroup H is a subset of a group G (denoted by H≤G) if it satisfies the four properties simultaneously − Closure, Associative, Identity element, and Inverse.

Counting Theory:

• The Rule of Sum − If a sequence of tasks T1, T2,…, Tm can be done in w1,w2,…wm ways respectively (the condition is that no tasks can be performed simultaneously), then the number of ways to do one of these tasks is w1+w2+⋯+wm. If we consider two tasks A and B which are disjoint (i.e. A∩B=∅), then mathematically |A∪B| = |A|+|B|
• The Rule of Product − If a sequence of tasks T1, T2,…, Tm can be done in w1,w2,…wm ways respectively and every task arrives after the occurrence of the previous task, then there are w1×w2×⋯×wm ways to perform the tasks. Mathematically, if task B arrives after task A, then |A×B| = |A|×|B|

Permutations:

A permutation is an arrangement of some elements in which order matters. In other words, a Permutation is an ordered Combination of elements.

Examples:

• We have to form a permutation of three-digit numbers from a set of numbers S={1,2,3}. Different three-digit numbers will be formed when we arrange the digits. The permutation will be = 123, 132, 213, 231, 312, 321

Problem − From a bunch of 6 different cards, how many ways we can permute it?

Solution − As we are taking 6 cards at a time from a deck of 6 cards, the permutation will be 6P6 = 6! = 720

Combinations:

A combination is a selection of some given elements in which order does not matter.

Problem:

Find the number of subsets of the set {1,2,3,4,5,6} having 3 elements.

Solution:

The cardinality of the set is 6 and we have to choose 3 elements from the set. Here, the ordering does not matter. Hence, the number of subsets will be 6C3 = 20.

Pigeonhole Principle

Pigeonhole Principle states that if there are fewer pigeonholes than a total number of pigeons and each pigeon is put in a pigeonhole, then there must be at least one pigeonhole with more than one pigeon. If n pigeons are put into m pigeonholes where n > m, there’s a hole with more than one pigeon.

Example:

• Ten men are in a room and they are taking part in handshakes. If each person shakes hands at least once and no man shakes the same man’s hand more than once then two men took part in the same number of handshakes.

Probability:

Probability can be conceptualized as finding the chance of occurrence of an event. Mathematically, it is the study of random processes and their outcomes. The laws of probability have wide applicability in a variety of fields like genetics, weather forecasting, opinion polls, stock markets etc.

Random Experiment − An experiment in which all possible outcomes are known and the exact output cannot be predicted in advance is called a random experiment. Tossing a fair coin is an example of a random experiment.

Sample Space − When we perform an experiment, then the set S of all possible outcomes is called the sample space. If we toss a coin, the sample space S = {H, T}

Event − Any subset of a sample space is called an event. After tossing a coin, getting Head on the top is an event.

Examples:

Throwing a Dice

When a dice is thrown, six possible outcomes can be on the top − 1,2,3,4,5,6

The probability of any one of the numbers is 1/6

The probability of getting even numbers is 3/6 = 1/2

The probability of getting odd numbers is 3/6 = 1/2

Conditional Probability:

The conditional probability of event B is the probability that the event will occur given that event A has already occurred. This is written as P(B|A)P(B|A).

Mathematically − P(B|A) = P(A∩B)/P(A)

If event A and B are mutually exclusive, then the conditional probability of event B after event A will be the probability of event B that is P(B).

Problem:

In a country, 50% of all teenagers own a cycle and 30% of all teenagers own a bike and cycle. What is the probability that a teenager owns a bike given that the teenager owns a cycle?

Solution:

Let us assume A is the event of teenagers owning only a cycle and B is the event of teenagers owning only a bike.

So, P(A) = 50/100 = 0.5 and P(A∩B) = 30/100 = 0.3 from the given problem.

P(B|A) = P(A∩B)/P(A) = 0.3/0.5 = 0.6

Hence, the probability that a teenager owns a bike given that the teenager owns a cycle is 60%.

Bayes’ Theorem:

Theorem − If A and B are two mutually exclusive events, where P(A) is the probability of A and P(B) is the probability of B, P(A|B) is the probability of A given that B is true. P(B|A) is the probability of B given that A is true, then Bayes’ Theorem states −

Recurrence Relation:

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing Fn as some combination of Fi with i<n).

Example − Fibonacci series − Fn = Fn−1+Fn−2, Tower of Hanoi − Fn = 2F n−1+1

Discrete Mathematics Applications

• The research of mathematical proof is especially important in logic and has applications to automated theorem demonstrating and regular verification of software.
• Partially ordered sets and sets with other relations have been used in different areas.
• Number theory has applications in cryptography and cryptanalysis.
• In situations where all the events of sample space are mutually exclusive events.
• In situations where either P(A∩B) for each A or P(A) and P(B|A) for each A is known.