Elements of Discrete Mathematics
Components of Discrete Mathematics:
A brief description of these branches which included below:
1. Mathematical Logic:
Logic is the science dealing with the methods of reasoning. It uses symbolic language to express its principles in precise and unambiguous terms known as mathematical logic. Mathematical logic has become an accepted part of discrete mathematics. One reason for this is that all efforts at the verification of algorithms inevitably the notation and methods of logic.
An understanding of the basic principles of logic underpins many important topics in computing ranging from basic hardware concepts to artificial intelligence. This requires that one must learn to use logically valid forms of arguments, to avoid common logical errors.
2. Set Theory:
A set is a collection of well-defined objects. The idea of a set is fundamental in the study of mathematical structures. A focal point of today’s mathematics isn’t numbered but sets or more precisely, sets with additional structures. All mathematical objects defined in terms of sets and the language of set theory. The set theory showed its usefulness in various mathematical disciplines such as Topology, mathematical logic and the foundation of mathematics.
Computer scientists deal with many different types of objects, which can in turn combined in different ways. To understand these compound objects and their manipulation, one has to understand the concepts of sets. The fuzzy set theory introduced by Zadeh in 1966. It is a generalization of abstract set theory. A fuzzy set consists of objects and their respective grade of membership in the set. These sets used in artificial intelligence, especially in the form of knowledge-based expert systems.
3. Boolean Algebra:
Binary logic deals with variables that take on two discrete values (like 1 or 0, True or False) and with operations that assume logical meaning. To build digital logic circuits of various families for different operations, the basic electronic circuits used in inverters and gates. Since digital devices and digital circuits operate in the binary number system.
They make it possible to use Boolean algebra as a mathematical tool for the analysis and design of digital circuits and systems. Boolean algebra is a simple and systematic way of representing and performing the operations of logic circuits in modern digital systems. The problem of optimizing the design of these circuits is essentially a problem of Boolean algebra.
Data is frequently arranged in arrays that are sets whose elements indexed by one or more subscripts. Frequently, a one-dimensional array called a vector and a two-dimensional array called a matrix. Thus matrix is a representation of mn elements in a rectangular array.
Matrix provides a means of storing large quantities of information in such a way that each piece can be identified and manipulated. Matrices used throughout discrete mathematics to express the relationship between elements in a set. This algebra used in analyzing the relationship between the vertices of a graph and the movement of robots and many other areas.
5. Number Theory:
Number theory is the part of mathematics that seeks to investigate the properties of integers, more specifically the properties of positive integers. It is a broad subject with many strong connections with other branches of mathematics.
A subject once viewed as the purest of pure mathematics but that in recent years has been applied to problems associated with the transmission, coding and manipulation of data. It has many applications in computer science which include hashing function, the generation of pseudo-random numbers and a recently invented type of cryptosystem called a public key system.
The concept of a relationship is a basic concept in computer science as well as in real life. This concept arises when we consider a pair of objects and compare one with another. We can express the relation by ordered pairs for instance.
One of the important concepts in discrete mathematics is that of function. The term “map“, “mapping“, “transmission” and many others mean the same thing. Relations in mathematics describe the connections between different elements of the same set whereas functions describe connections between two different sets.
The theory of function provides the foundation for what called mathematical modelling whereby One mathematical object represents certain features of another or some non-mathematical object. Or perhaps with the elimination of some distracting complexities.
Moreover, functions give a mathematical precise framework for the intuitive idea of transformation. An important result for computer science is that the general recursive functions conclude with the functions defined by a Turing machine, which is a simple form of computer. The study of computable functions is the domain of recursive function theory, an active branch of mathematics.
8. Poset and Lattices:
A set is a partially ordered set concerning a relation if, and only if, is a partial order relation. Order and precedence relationships appear in many different places in mathematics and computer science.
Latices are a special kind of ordered set. Two important and widely used applications of partial order relation are PERT (Program Evaluation and Review Technique) and CPM (Critical Path Method). These techniques deal with the complexities of scheduling the individual activities needed to complete very large projects.
Combinatorics is the mathematics of counting, selecting and arranging objects. It includes the theory of permutations and combinations. These topics have an enormous range of applications in pure and applied mathematics and computer science. These processes by which we organize sets up so that we can interpret and apply the data they contain.
Generally speaking, combinatorial questions ask whether a subset of a given set can be chosen and arranged in a way that conforms with certain constraints and if so, in how many ways it can be done. The application of combinatorics play a major role in the analysis of algorithms.
10. Abstract and Linear Algebra:
Algebras generally deal with discrete objects and are, therefore a natural part of discrete mathematics. Algebra consists largely of the investigation of various types of structure which are abstractions from situations occurring widely in regular mathematical practice. Some of the most important of them are groups, rings and fields. Abstract algebra has many applications in computer science.
Linear algebras are uncommon topics in discrete mathematics. But those are quite natural since the variables in linear algebra are normally real variables. The structure and manipulations are discrete. Moreover, vector space, linear transformation and the matrix theory are the main contents of linear algebra.
11. Graph Theory:
A graph is a set of points commonly known as vertices or nodes. It is interconnected by a set of lines called edges. Graph theory is one of the most important branches of discrete mathematics and the source of many algorithms of practical importance. Among all the discrete structures, graphs are the most flexible and adaptable to suit the needs of applications.
It uses in areas such as syntactic analysis, fault detection and diagnosis in computers, and minimal path problems. Indeed, in many problems dealing with discrete objects and binary relation is a graphical representation of the objects and the binary relations on them. It is a very convenient form of representation.
Tree is a special class of graph. It is a kind of data structure that looks very much similar to our normal tree. In computer science, a tree is a data structure that represents hierarchical relationships between individual data items. That tree in which no parent has more than two children called a binary tree.
Probability is a branch of mathematics that deals with phenomena whose outcomes involve uncertainty. The fundamental idea in probability is that measured on a scale which runs from zero to one. In coding theory, to correct errors in a code, rather than know how many errors we need to be able to correct, some estimates of the probability of a single error and likely independence of the occurrence of errors are desirable. In designing, a large computer needs to take into account how frequently its various components are likely to be used and how reliable they are.
14. Language, Grammar and Automata:
A formal language is a set of finite-length words drawn from some alphabet. Grammar is an algebraic system describing the process by which instances of a language can be constructed. Thus grammar imposes a structure on the sentence of a language.
Automata theory is a mathematical discipline concerned with the invention and study of mathematically abstract, idealized machines called Automata. These automata are usually abstractions of information processing devices such as computers. It has a mechanism for reading input strings over a given alphabet written on an input file.
This has been quite a brief survey of discrete mathematics. One thing that can be said with certainty about discrete mathematics that the importance of its various branches. It will continue to grow as the applications of computers permeate more and more aspects of science, technology, and everyday life.