Discrete Mathematics As A Subject Complete Guide

Discrete Mathematics


What is Discrete Mathematics:


Discrete Mathematics concerns processes that consist of a sequence of individual steps. Discrete mathematics is the part of mathematics devoted to the study of discrete objects. (Here discrete means consisting of different or unconnected elements)

Discrete mathematics is used whenever objects are counted, when relationships between continuous or countable sets are studied.

Discrete Mathematics Study Importance:

In Computer Science:

Discrete Mathematics has a special value in computer science.Computer is a binary machine and all the algorithms in computer science are based on digits 0 and 1. We therefore say computer science is inherently discrete.

As a student of computer science there are good reasons to study discrete mathematics the most important reason is that it will develop a mathematical maturity in you which is essential in studying any scientific discipline

In other Fields:

Discrete Mathematics has Applications in many other diverse areas like management sciences ,network analysis, social decision making and finance.

An important reason for studying this subject is that discrete mathematics is pre-exquisite for a number of other advanced courses in Computer Science, Data Structures, Algorithm analysis, Theory of Automata, Computer Theory and some of those courses that can only be studied after a course in discrete mathematics

Objectives of studying this Subject

  1. Express declarations with formal logic precision.
  2. To test the validity of arguments
  3. Apply the fundamental properties and sets related operations
  4. Apply for defining the fundamental properties and functional activities
  5. Prove a mathematical induction formula
  6. Prove declarations by direct and indirect methods
  7. Calculate the probability of simple and dependent events
  8. Identify and use combinatorial formulas in various problems
  9. Explain the basic graph theory definitions and characteristics

The kinds of issues that can be solved using this subject include:

  • How can it be proved that a sorting algorithm correctly sorts a list
  • How will a circuit  that adds 2 integers be designed?
  • What is the chance of winning a lottery?

Discrete Mathematics as a subject covers the following topics:

  1. Logic
  2. Sets and Operations on sets
  3. Venn Diagram
  4. Relations & Their Properties
  5. Functions
  6. Sequence and Series
  7. Recurrence Relations
  8. Mathematical Induction
  9. Combinatorics
  10. Probability
  11. Conditional Probability
  12. Graphs and Trees

1) Logic


Logic is the study of principles and methods that distinguish between a valid and invalid statement


It can also be referred as proposition

Logic is the basis of mathematical reasoning.

It will help you develop strong skills that is needed to make programming logic, algorithms and it will also be helpful in other fields of computer Science.

To understand mathematics one must understand to make a mathematical argument that is proof or logic

Statement:

“A statement is a declarative sentence that is either true or false but not both”

If a proposition is true we can say that it has a truth value of ‘true’ .
If a proposition is false its truth value is false.

For Example:

  1. It is Friday today
  2. Islamabad is capital of Pakistan
  3. 3 + 2 = 6
  4. 1 + 2 = 4

In above examples truth value of statement 1 and 2 is true . In the example 3 and 4 the truth value of statements is false

Compound Statement:

Simple statement could be used to build a compound statement

For Example:

  1. “6 + 4 = 10” and “Multan is a city in Pakistan”
  2. “The grass is green” or “It is sunny today”
  3. “English is not difficult for me”

Logical Connectives:

AND, OR, NOT are called LOGICAL CONNECTIVES

Logical Connectives

Prepositional Variables:

Variables that represent prepositions such as ‘p , q , r , s …..’ are prepositional or statement variables. Statements are symbolically represented by these letters.

The truth value of a statement is true ,denoted by T , if it is a true statement.

The truth value of a statement is false, denoted by f , if it is a false statement .

= Islamabad is capital of Pakistan

q = “15 is divisible by 5”

Truth Table : 

A convenient method for analyzing a compound statement is to make a truth table.A truth table specifies a truth value of a compound preposition.

2) Set


A set is a well-defined collection of distinct objects. The objects that make up a set (also known as the set’s elements or members) can be anything: numbers, people, letters of the alphabet, other sets, and so on.[wikipedia]


For Example:

  1. A collection of students going on a trip is a set
  2. A collection of whole or integer numbers is a set

Mostly the study of discrete mathematics include discrete structures.

Most important discrete structures are built using sets, that are collection of objects.

We will study the fundamental discrete structures on which all other discrete structures are built, namely set.

Representation of sets:

  1. The objects are called the elements or members of the set.
  2. Sets are denoted by capital letters A, B, C …, X, Y, Z.
  3. The elements of a set are represented by lowercase letters
    a, b, c, … , x, y, z.

TABULAR FORM:

Listing all the elements of a set, separated by commas and                         enclosed within braces or curly brackets{} is tabular form

For Example:

In the following examples we write the sets in Tabular Form.

X = {1, 2, 3, 4, 5,6,7,8,9,10}    is the set of first ten Natural Numbers.

Y = {2, 4, 6, 8, …20} is the set of Even numbers up to 20.

Z = {1, 3, 5, 7, 9, …} is the set of positive odd numbers.

Descriptive Form:

Stating in words the elements of a set is descriptive form

For Example:

A=Set of Prime Numbers (is the descriptive form)

B=Set of even numbers up to 50( is the descriptive form)

Set Builder Form:

Writing the elements of set in symbolic form is Set builder form

For Example:

A = {x ∈ E / 0 < x <=50}

B = {x ∈ N / x<=5}

SUBSET:

If every member of set A is also a member of set B, then A is said to be a subset of B, written A ⊆ B (also pronounced A is contained in B). Equivalently, we can write B ⊇ A, read as B is a superset of AB includes A, or B contains A. [wikipedia]

Subset
A is a Subset of B

3) Venn Diagram


Venn diagram  is a diagram that shows all possible logical relations between a finite collection of different sets

 These diagrams shows elements as points in the plane, and sets as regions inside closed curves.

A Venn diagram consists of multiple overlapping closed curves, usually circles, each representing a set.

The points inside a curve represent elements of the set S, while points outside the boundary represent elements not in the set S.[wikipedia]

Venn diagram
Venn diagram

Union

Let A and B be subsets of a universal set U. The union of sets A and B is the set   of all elements in U that belong to A or to B or to both, and is denoted A ∪ B.


Symbolically:
                                     A ∪ B = {x ∈U | x ∈A or x ∈ B}

EMAMPLE:

                                    Let U = {1, 2, 3, 4, 5, 6, 7}

                                 A = {1, 3, 5, 7},           B = {2, 4, 5, 6}

                                Then     A ∪ B = {x ∈U | x ∈A or x ∈ B}

                                                      ={1, 3, 4, 5 ,6, 7}

VENN DIAGRAM FOR UNION:

Venn Diagram Union
A ∪ B is Shaded

MEMBERSHIP TABLE FOR UNION:

Membership table for union

INTERSECTION:


Let A and B subsets of a universal set U. The intersection of sets A and B is the set of all elements in U that belong to both A and B and is denoted as  A  ∩ B.


Symbolically:
                                    A ∩ B = {x ∈U | x ∈ A and x ∈B}

VENN DIAGRAM FOR INTERSECTION:

Venn Diagram Intersection
A ∩ B is Shaded

MEMBERSHIP TABLE FOR INTERSECTION:

Membership table for intesection