It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem-solving capabilities.
It is characterized by the fact that between any two numbers, there are almost always an infinite set of numbers. For example, a function in continuous mathematics can be plotted in a smooth curve without breaks. For example, if we have a finite set of objects, the function can be defined as a list of ordered pairs having these objects, and can be presented as a complete list of those pairs. A Set is an unordered collection of objects, known as elements or members of the set.
Two sets are said to be equal if both have same elements. A set A is said to be subset of another set B if and only if every element of set A is also a part of other set B. This includes classification, properties, and biological importance of biomolecules. It will introduce the students to the concept of genetic code and concept of heredity.
The key emphasis is placed on understanding the basic principles that govern the biological functions of biomolecules. Topics in our Discrete Mathematics Notes PDF The topics we will cover in these Discrete Mathematics Handwritten Notes PDF will be taken from the following list: Introduction: Sets — finite and infinite sets, uncountable infinite sets; functions, relations, properties of binary relations, closure, partial ordering relations; counting — Pigeonhole Principle, permutation and combination; mathematical induction, Principle of Inclusion and Exclusion.
Recurrence: recurrence relations, generating functions, linear recurrence relations with constant coefficients and their solution, recursion trees, Master Theorem Graph Theory: basic terminology, models and types, multi-graphs and weighted graphs, graph representation, graph isomorphism, connectivity, Euler and Hamiltonian Paths and Circuits, planar graphs, graph coloring, Trees, basic terminology and properties of Trees, introduction to spanning trees.
In this chapter, we will cover the different aspects of Set Theory. Set — Definition A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using 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. The elements are enclosed within braces and separated by commas. Some of which are finite, infinite, subset, universal, proper, singleton set, etc.
Here set X is a subset of set Y as all the elements of set X is in set Y. Here set X is a proper subset of set Y as at least one element is more in set Y. 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 , set of all mammals is a subset of U, set of all fishes is a subset of U, set of all insects is a subset of U, and so on.
Empty Set or Null Set An empty set contains no elements. As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero. Equivalent Set If the cardinalities of two sets are same, they are called equivalent sets. Disjoint Set If two sets C and D are disjoint sets as they do not have even one element in common.
Venn Diagrams Venn diagram, invented in by John Venn, is a schematic diagram that shows all possible logical relations between different mathematical sets. The cardinalit y of a power set of a set S of cardinality n is 2n.
Power set is denoted as P S. Relations may exist between objects of the same set or between objects of two or more sets. If the ordered pair of G is reversed, the relation also changes. Generally an n-ary relation R between sets A 1 , The minimum cardinality of a relation R is Zero and maximum is n2 in this case.
For two distinct sets, A and B, having cardinalities m and n respectively, the maxi mu m cardinality of a relation R from A to B is mn. The number of vertices in the graph is equal to the number of elements in the set from which the relation has been defined.
A relation is an Equivalence Relation if it is reflexive, symmetric , and transitive. Functions find their application in various fields like representation of the computational complexity of algorithms, counting objects, study of sequences and strings, to name a few. The third and final chapter of this part highlights the important aspects of functions. A function can be one to one, many to one not one to many. Example 1. Explanation: We have to prove this function is both injective and surjective.
Hence, f is injective. Hence, f is surjective. Since f is both surjective and injective, we can say f is bijective. Greek philosopher, Aristotle, was the pioneer of logical reasoning. Logical reasoning provides the theoretical base for many areas of mathematics and consequently computer science. It has many practical applications in computer science like design of computing machines, artificial intelligence, definition of data structures for programming languages etc. The purpose is to analyze these statements either individually or in a composite manner.
A propositional consists of propositional variables and connectives. We denote the propositional variables by capital letters A, B, etc. The connectives connect the propositional variables. It is because unless we give a specific value of A, we cannot say whether the statement is true or false. The rest cases are true. Contradictions A Contradiction is a formula which is always false for every value of its propositional variables.
Contingency A Contingency is a formula which has both some true and some false values for every value of its propositional variables. Inverse, Converse, and Contra-positive A conditional statement has two parts: Hypothesis and Conclusion. Inverse: An inverse of the conditional statement is the negation of both the hypothesis and the conclusion. Contra-positive: The contra-positive of the conditional is computed by interchanging the hypothesis and the conclusion of the inverse statement.
Duality Principle Duality principle set states that for any true statement, the dual statement obtained by interchanging unions into intersections and vice versa and interchanging Universal set into Null set and vice versa is also true. If dual of any statement is the statement itself, it is said self-dual statement. Predicate Logic — Definition 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. There are two types of quantifier in predicate logic: Universal Quantifier and Existential Quantifier. Universal Quantifier Universal quantifier states that the statements within its scope are true for every value of the specific variable.
Existential Quantifier Existential quantifier states that the statements within its scope are true for some values of the specific variable. Nested Quantifiers If we use a quantifier that appears within the scope of another quantifier, it is called nested quantifier.
What are Rules of Inference for? Mathematical logic is often used for logical proofs. Proofs are valid arguments that determine the truth values of mathematical statements. An argument is a sequence of statements. The last statement is the conclusion and all its preceding statements are called premises or hypothesis.
A valid argument is one where the conclusion follows from the truth values of the premises. Rules of Inference provide the templates or guidelines for constructing valid argument s from the statements that we already have.
Generally, a group comprises of a set of elements and an operation over any two elements on that set to form a third element also in that set.
These symbols are not in general convertible [commutative], but are associative. Any set of elements in a mathematical system may be defined with a set of operators and a number of postulates. A binary operator defined on a set of elements is a rule that assigns to each pair of elements a unique element from that set.
The postulates of a mathematical system form the basic assumptions from which rules can be deduced. The postulates are: Closure A set is closed with respect to a binary operator if for every pair of elements in the set , the operator finds a unique element from that set. Here a,b A but c A. Example: The set of positive integers excluding zero with addition operation is a semigroup. An identity element is also called a unit element. So, a monoid holds three properties simultaneously: Closure, Associative, Identity element.
Example The set of positive integers excluding zero with multiplication operation is a monoid. Here identity element is 1. Group A group is a monoid with an inverse element. So, a group holds four properties simultaneously - i Closure, ii Associative, iii Identity element, iv Inverse element. Matrix multiplication itself is associative. Hence, associative property holds. As all the matrices are non-singular they all have inverse elements which are also non- singular matrices.
Hence, inverse property also holds. 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. Example The set of positive integers including zero with addition operation is an abelian group.
Here, identity element is 1. Every element of a cyclic group is a power of some specific element which is called a generator. Hence, it is a cyclic group. The rational numbers under addition is not cyclic but is abelian.
A subgroup of a cyclic group is cyclic and a abelian subgroup is also abelian. Examples 1. Hence, it is a poset. Hasse Diagram The Hasse diagram of a poset is the directed graph whose vertices are the element of that poset and the arcs covers the pairs x, y in the poset.
Trichotomy law defines this total ordered set. Hence, it is not a total ordered set. Some other lattices are discussed below: Bounded Lattice A lattice L becomes a bounded lattice if it has a greatest element 1 and a least element 0. Complemented Lattice A lattice L becomes a complemented lattice if it is a bounded lattice and if every element in the lattice has a complement.
For instance, in how many ways can a panel of judges comprising of 6 men and 4 women be chosen from among 50 men and 38 women?
How many different 10 lettered PAN numbers can be generated such that the first five letters are capital alphabets, the next four are digits and the last is again a capital letter. For solving these problems, mathematical theory of counting are used. Counting mainly encompasses fundamental counting rule, the permutation rule, and the combination rule.
If we consider two tasks A and B which are disjoint i. From his home X he has to first reach Y and then Y to Z. He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z.
How many ways are there to go from X to Z? Permutations A permutation is an arrangement of some elements in which order matters. In other words a Permutation is an ordered Combination of elements. Different three digit numbers will be formed when we arrange the digits. There are n number of ways to fill up the first place. After filling the first place n -1 number of elements is left. Hence, there are n-1 ways to fill up the second place.
After filling the first and second place, n-2 number of elements is left. Hence, there are n-2 ways to fill up the third place. The number of permutations of n dissimilar elements when r specified things always come together is: r! The number of permutations of n dissimilar elements when r specified things never come together is: n!
The rest cases are true. A Contradiction is a formula which is always false for every value of its propositional variables. A Contingency is a formula which has both some true and some false values for every value of its propositional variables.
Duality principle states that for any true statement, the dual statement obtained by interchanging unions into intersections and vice versa and interchanging Universal set into Null set and vice versa is also true. If dual of any statement is the statement itself, it is said self-dual statement. A compound statement is in conjunctive normal form if it is obtained by operating AND among variables negation of variables included connected with ORs.
In terms of set operations, it is a compound statement obtained by Intersection among variables connected with Unions. A compound statement is in disjunctive normal form if it is obtained by operating OR among variables negation of variables included connected with ANDs.
0コメント