Discrete Mathematics

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Introduction

Discrete mathematics is a branch of mathematics that is concerned with discrete mathematical structures. It provides an essential foundation for virtually every area of computer science, and its applications are vast. It is increasingly being applied in the practical fields of mathematics and computer science. Discrete mathematics is in contrast to continuous mathematics, which deals with structures that can range in value over the real numbers, or have some non-separable quality. Discrete mathematics concerns itself mainly with finite collections of discrete objects. With the growth of digital devices, especially computers, discrete mathematics has become more and more important. Discrete mathematics is the mathematical language of computer science, and as such, its importance has increased dramatically in recent decades.

Topics covered in discrete mathematics related to computer science

Combinatorics

Combinatorics is often concerned with how things are arranged. In this context, an arrangement is a way objects could be grouped. The most basic rules regarding arrangements are the rule of product and the rule of sum.

Sum Rule Principle

Assume some event E can occur in m ways and a second event F can occur in n ways, and suppose both events cannot occur simultaneously. In such a case, E or F can occur in m + n ways. In general, if there are n events and no two events occurs in same time then the event can occur in n1+n2..........n ways.

Product Rule Principle

Suppose there is an event E that can occur in m ways and, independent of this event, a second event F can occur in n ways. In such a case, combinations of E and F can occur in mn ways. In general, if there are n events occurring independently, all events can occur in the order indicated as n1 x n2 x n3.........n ways.

Permutation

A permutation is an arrangement of some elements in which order matters. Any arrangement of a set of n objects in a given order is called Permutation of Object. Any arrangement of any r ≤ n of these objects in a given order is called an r-permutation or a permutation of n object taken r at a time. It is denoted by P (n, r)  $_{n}P_{r}={\frac {n!}{(n-r)!}}$

Combination

A combination is an arrangement of objects without regard to order. The number of all combinations of n things, taken r at a time is C (n, r)  $_{n}C_{r}={\frac {n!}{r!(n-r)!}}$

Set Theory

A set is an unordered collection of objects, known as elements or members of the set. An element 'a' belonging to a set A can be written as 'a ∈ A' and 'a ∉ A' denotes that a is not an element of the set A. German mathematician G. Cantor introduced the concept of sets. He had defined a set as a collection of definite and distinguishable objects selected by the means of certain rules or description. Sets can be represented mainly in two ways.

Roster or tabular form

In this form of representation, we list all the elements of the set within braces { } and separate them by commas. If A = a set of all even numbers less than 10, then in the roster form, it can be expressed as A = { 2,4,6,8}.

Set Builder Notation

The set is defined by specifying a property that elements of the set have in common. The set is described as A={x:p(x)}In Set-builder set is described by a property that its member must satisfy. {x : x is a natural number less than 10}.

Equal Set

Two sets are said to be equal if both have same elements. For example, A = {2, 4, 6, 8} and B = {4, 2, 6, 8} are equal sets. Order of elements of a set doesn't matter.

Cardinality

The total number of unique elements in the set is called the cardinality of the set. Cardinality can also be extended to infinite sets. Although this kind of cardinality cannot be counted, each cardinality can be compared with another cardinality.

Mathematical Induction

Mathematical Induction is a mathematical proof method that is used to prove a given statement about any well-organized set. It is a mathematical technique that is used to prove a statement, a formula, or a theorem is true for every natural number. If n is a natural number, the technique involves three steps to prove a statement, P(n), as stated below:
Basic Induction Step: Verify if the statement is true for trivial cases like n = a i.e., P(a) is true.
Induction Step (Hypothesis): Assume that the statement is true for n = k for some k ≥ a i.e., P(k) is true.
Induction Step (Final): If the truth of P(k) implies the truth of P(k + 1), the statement P(n) is true for all n ≥ a.
The base step and the inductive step, together, prove that P(k) => P(k + 1) => P(k + 2) .... is true. Therefore, P(n) is true for all integers n ≥ a.

Example 1

Prove that, $3^{n}-1$ is a multiple of 2 for natural number. (n=1,2,3,.....)
Basic Induction Step: For $n=1$, $3^{1}-1=3-1=2$ which is a multiple of 2
Induction Step (Hypothesis): Let us assume $3^{n}-1$ is multiple of 2, is true for $n=k$, Hence, $3^{k}-1$ is true (It is an assumption)
Induction Step (Final): We have to prove that $3^{k+1}-1$ is also a multiple of 2.
$3^{k+1}-1=3^{k}.3^{1}-1=2.3^{k}+(3^{k}-1)$
As we assume $3^{k}-1$ is a multiple of 2 and $2.3^{k}$ is certain multiple of 2. So, it is proved that $3^{n}-1$ is a multiple of 2 for natural number.