Topics of Discrete Mathematics

Friends, for most of the students, the first and most common area of mathematics in college education is calculus. Calculus is the most important area of study of mathematics whose emergence causes the invention of modern mathematics and it was the key to most of the successful applications of mathematics in the science. It is basically a style of mathematics invented by Sir Isaac Newton. In general the words "calculus" means rock. Calculus is also very technical which takes a lot of time even to introduce its fundamental terms like continuity or derivatives.

Calculus is basically a branch of mathematics focused on limits, functions, derivatives, integrals, and infinite series. Basically it is the study of 'Rates of Change'. There are two main branches of calculus: Differential Calculus and Integral Calculus. Differential calculus determines the rate of change of a quantity and integral calculus finds the quantity where the rate of change is known.

Now I am going to give you a brief introduction of Discrete mathematics. It is a mathematics that deals with discrete objects. Discrete objects are those which are separated from each other. Integers, rational numbers that can be expressed as the quotient of two integers, automobiles, houses, people etc. are all discrete objects. On the other side the real numbers which include irrational as well as rational numbers are not discrete. As we all know that between any of the two distinct real numbers there is another real number different from either of them. So students can define them as they are equipped without any gaps and can't be separated from their immediate neighbors. In this way they are not discrete. Here in our Discrete mathematics syllabus I am going to discuss about objects such as integers, propositions, sets, relations and functions, which are all discrete along with the associated properties and relationships.

The important areas in applied mathematics comes with linear programming, coding theory, theory of computing are some of the applications that is collectively known as discrete mathematics. The most important thing to understand before going to solve a mathematics is that maths cannot be done without proofs.

Following are the topics to cover under Discrete Mathematics :

1. Boolean Functions and Computer Arithmetic
2. Logic
3. Number Theory and Cryptography
4. Sets and Functions
5. Equivalence and Order
6. Induction, Sequences and Series

Lets starts with the first topic:

1. Boolean Function and Computer Arithmetic: This section is further divided into two different sub parts that are :

Boolean Functions : In mathematics, it is a function of the form f : B^k →B, where B =0, 1 is a Boolean Domain and K is a non-negative integer which is called the arity of the function.

If K = 0 then the function is essentially a constant element of B.

It tells us how to find a Boolean value output based on some logical calculation from Boolean inputs. It plays an important role in questions of complexity theory as well as the design of circuits and chips for digital computers. Its properties play a critical role in cryptography, most commonly in the design of symmetric key algorithm. Following are the sub topics : Boolean function, binary operator, unary operator, not (∼), and (∧), or (∨), exclusive or (⊕), truth table, disjunctive normal form, conjunctive normal form.

Number Systems and Computer Arithmetic:

This sub topic covers following topics to cover digit symbols, digit symbol of index or rank i, base-b number, binary arithmetic, two’s complement, logic gate, half adder, full adder.

Now take on another topic that is:

2. Logic :

Reasoning conducted or compute according to strict principles of validity: which tells that "experience is a better guide to this than deductive logic". It is also defined as a particular system or allocation of the principles of proof and assumptions: it is also considered as "Aristotelian logic".

The sub topics of Logic part are:

Propositional Logic:

It is a formal system in which formulas of a formal language may be interpreted as representing propositions. Sentences considered in propositional logic are not approximate sentences, but the sentences or we can say them statement that are either true or false, but not both. If a proposition is true, then we say it has a truth value of "true"; if a proposition is false, its truth value is "false".

The topics to cover are:

Truth table that tells the statements or relations are true or false, statement forms, tautology, contradiction, implication, conditional, con- trapositive, double implication, bi-conditional, converse, inverse, if, only if, sufficient, necessary, unless.

Predicate Logic :

The propositional logic is not powerful enough to represent all types of assertions that are used in computer science and mathematics, or to express certain types of relationships between propositions such as equivalence. So we need Predicate logic , A predicate is basically a verb phrase arrangement that describes a property of objects, or a relationship among objects represented by the variables. Following are the sub topics which we are going to be learned in this section of mathematics: truth set, prime, composite, Fermat number, Mersenne number, perfect numbers, Goldbach conjecture, Fermat’s Last Theorem, Marin Mersenne (1588– 1648), Pierre de Fermat (1601–1665), Christian Goldbach (1690–1764), Leonhard Euler (1707–1783), Karl Friedrich Gauss (1777–1855) .

3 : Number Theory and Cryptography :

Number theory is a branch of pure mathematics which is basically formulated to the study of the integers. It consists of prime numbers (when multiplied give all the integers) as well as the properties of objects made out of integers or defined as abstractions of the integers. The sub topics are:

Basic Facts About Numbers :

Following are the topics which we are going to learn in this section of mathematics: rational numbers, irrational numbers, prime, composite, odd, even, n divides m, prime factorization, infinitely many primes, perfect squares, irrationality of integral square roots, residue classes mod d, mod as binary operator, mod as equivalence relation, modular arithmetic, modular addition, modular multiplication, floor function, ceiling function, diagonalization proofs

Cryptography and Secrecy:

These are some scientific techniques which are used too encrypt or decrypt the message to send forward. Following are the topics which we are going to learn in this section of mathematics :plaintext, ciphertext, key, espionage, greatest common divisor, least common multiple, greatest common division(m, n) as linear combination of m and n, Euclidean algorithm, Euler φ function, public key, symmetric encryption, discrete log problem, Diffie-Hellman algorithm, *RSA algorithm .

4 : Sets and Functions:

There are two sub topics that are:

Sets : It is a collection of well defined and distinct objects,

A set is a collection of well defined and distinct objects, acknowledged as an object in its own right. Sets are one of the most fundamental concepts in mathematics. It can be further defined as a collection of things that are brought together because they obey a certain rule. In this area of study we all are going to deal with following topics that are :intersection, union, difference, complement, symmetric difference, product, Cartesian product, binomial coefficients, C(n, k) = n , algebraic rules, associative rule, distributive rule, idempotent rule, DeMorgan’s rule, absorption rule, commutative rule, lexicographic order, power set, characteristic function, set partitions, Bell numbers, refinement

Functions:

Functions are basically mathematical ideas that hold one or more variables and produce a variable. In more appropriate manner we can say that a function associates one quantity, the argument of the function, also known as the input, with another quantity. The value of the function also known as the output. A function assigns exactly one output to each input. In this section we are going to learn about following topics that are:

domain, range, co-domain, image, relation, functional relation, one-line notation, surjection, onto, injection, one-to-one, bijection, permutation, two-line notation, composition of functions, cycle form of permutation, image of function, inverse image, co-image, set partitions, Stirling numbers S(n, k), Bell numbers .

5 : Equivalence and Order

In the equivalence section we study about equivalence relation, equivalence class, blocks of a partition, co-image, reflexive, symmetric, transitive, relational description, co-image description, pigeonhole principle, subset sums, monotone subsequences, extended pigeonhole principle, transpositions

In Order section we study about following areas of study:

antisymmetric relation, order relation, partially ordered set, incidence matrices, total ordering, linear ordering, set inclusion, lattice of subsets, incomparable subsets, refinement relation, direct product, Cartesian product, coordinate order, characteristic function, directed graph diagrams, transitive closure,

Boolean product, Boolean sum, covering relation, chain, least element.

6 : Induction, Sequences and Series

Induction is a method of mathematical proof which is used to establish that a given statement is true in all positive integers. Sequences is basically an ordered list of objects. Some of the topics to study in this section are induction hypothesis, induction step, base case, product of primes , infinite sequence, limit of sequence, convergent sequence, bounded sequence, monotone sequence, convergent to infinity etc.