Discrete Mathematics – Lecture 1: Introduction to Discrete

Mathematics

Introduction
From now onwards we are going to start with an all-new series on discrete mathematics and this is
the first lecture of discrete mathematics course. In this lecture, we are going to have an
introduction to discrete mathematics. We will discuss who is the target audience. We will
understand why discrete mathematics is needed. Finally, at the end of the lecture, we are going to
have a quick look into the syllabus.

Target Audience
This course is definitely intended for students who are preparing for GATE and other competitive
examinations. Of course, the students specially who are preparing for GATE. Especially if there are
computer science students, then definitely this course is for them. Because we are going to cover
lot of topics related to GATE in this particular course. Therefore, such students can benefit from
this course.

Students who want to learn competitive programming will also get lot of benefits from this course.​
Because in competitive programming, discrete mathematics is a very important subject to learn.
Apart from that, college-going students who want to learn discrete mathematics are also welcome.​
This might be the course in their syllabus. Then they are most welcome to take this course.

Everyone who wants to learn discrete mathematics as a whole is also welcome. Maybe it is
possible that you want to learn a small sub topic in this discrete mathematics subject. Or maybe
you want to learn this whole subject. In either case, you are most welcome. This course is intended
for all such learners.

Why We Need to Study Discrete Mathematics

It definitely develops your mathematical thinking. There is no doubt about it. It improves your
problem-solving ability. Because it is after all a mathematical subject. Therefore, it improves your
problem-solving ability as well.

If you are a computer science student, then no need to go anywhere else. Because discrete
mathematics is for you. Discrete mathematics is important to survive in subjects like compiler
design. It is also important in databases, computer security, operating system, automated theory,
etc. Discrete mathematics is very important to survive in these subjects.

This will act like a foundational subject for many courses like these. Therefore, this is a very
important subject to study. Apart from that, there are many problems that can be solved using
discrete mathematics. So these are all the problems which can be solved using discrete
mathematics.

1
Like for example sorting the list of integers. Finding the shortest path from your home to your
friend's home.

Drawing a graph with two conditions. That you are not allowed to lift your pen. You are not allowed
to repeat edges.

I would encourage you to please try to draw this graph available over here. Without lifting your pen.
And you are also not allowed to repeat the edges. Try drawing this graph on your own.

​
How many different combinations of passwords are possible with just eight alphanumeric
[Link] is also a very important problem which can be solved with the help of discrete
[Link] a message and deliver it to your friend. And you don't want anybody to read
that message except your friend. After studying the subject called discrete mathematics. We would
be able to solve these different problems very easily.

What is Discrete Mathematics?

Now let's try to understand what is discrete mathematics. Discrete mathematics is the study of
discrete objects. Discrete means distinct or not connected.

It is not a branch of [Link] is rather a description of set of branches that have one common
property. That they are discrete and not continuous. This is also a very important point to note. This
is not a branch of mathematics. It is rather a description of set of branches. That is it can be a
collection of set of branches. That have one common property. That they are discrete and not
continuous.

Discrete vs Continuous
Now let us try to understand the difference between discrete and continuous. The whole world of
mathematics is divided into two. Discrete and continuous. Okay now let's try to differentiate
between discrete objects and continuous objects. Natural numbers are discrete.

For example 1, 2, 3, 4, 5 are all natural numbers. That are starting from 1 and going up to infinity.​
Between 1 and 2 there is no number. There is a sharp transition from 1 to 2 and 2 to 3.​
And 3 to 4 and 4 to 5 etc.

Suppose I asked you to draw a graph for y = x. Where x belongs to natural numbers. And y
belongs to natural numbers. Then how a graph will look like. This is how a graph will look like.

2
So here this is an x-axis. And this will be a y-axis. Right in this graph you can observe distinct
points. y = x means when y is 1 x is 1. We are going to plot a point. When y is 2 x is 2. We are
going to plot another point. When y is 3 and x is 3. We are going to plot another point and so on.
This is the graph of y = x.

Where x belongs to natural numbers. Please note down x belongs to natural numbers. And y also
belongs to natural numbers. Therefore the graph consists of distinct points. These points are not
connected continuously. Please observe the gaps in between. As I already told you, discrete
means distinct or not connected. As you can see, we are not getting the continuous line over here.​
We are only getting distinct points which are not connected with each other. Therefore, this graph
is a discrete graph.

On the other hand, real numbers are continuous. For example, between 0 and 1 you will find out
infinite number of points. Like 0.0001, 0.00001, 0.10001 and so on. There are infinitely many points
between 0 and 1. Therefore, real numbers are continuous.

​
Right now let's consider one more example. Digital clock is discrete in nature.

Because there is no continuous time. And transition from one time to another time is very sharp.​
Like for example, consider this clock. Suppose it is right now 10 hours 42 minutes and 57 seconds.​
Transition from 57 seconds to 58 seconds is very sharp. There are no points in between 57 and 58.
Therefore, digital clock is one example. Which we can say that it is discrete in nature.​

3
On the other hand, analog clock is continuous in nature. In analog clock hour, minute and second

hands move smoothly over time.

We are considering the clock where minute hand, hour hand and second hand sweeps around the
time smoothly. We are not considering those analog clocks in which there are sharp transitions
between one time to another time. We are considering a clock in which the second hand, minute
hand and hour hand sweeps around the time very smoothly. Therefore, analog clock is continuous
in nature. And digital clock is discrete in nature.

Syllabus of Discrete Mathematics

Let's consider the syllabus of discrete mathematics. In this course, we are going to talk about
propositional logic and first-order logic. In which we will have a lot of discussion about what is
propositional logic. What is first-order logic. What is predicates and quantifiers and so on.

We are also going to have a discussion on set theory. And then we simply move to relations and
functions. And then finally to partial orders and lattices. These are also important topics in this
course. We will study them in detail.

We are also going to have a lot of discussion on combinatorics. We will study permutations and
combinations. Basics of counting techniques. And certain other advanced counting techniques.​
In this particular topic. We will also talk about graph theory. And we will have a lot of discussion on
this topic as well. Graph theory is very very important from computer science perspective.​
Therefore, we will study this topic very deeply. It is one of the important topics in this course.

Apart from that, at last we are going to cover group [Link] is also a very important topic to
study.

Discrete Mathematics – Lecture 2: Motivation and

Introduction to Propositional Logic

4
In this lecture, we are going to start with the very first chapter of Discrete Mathematics, which is
Propositional [Link] phrase Propositional Logic is composed of two words. One is Proposition
and the other one is Logic. Simple.

Now, let us try to understand what is Logic. Logic is the science of reasoning. It helps us to
understand and reason about different mathematical statements. This is very important. We would
be able to reason about different mathematical statements with the help of Logic.

With the rules of Logic, we would be able to think about mathematical statements. And finally, we
would be able to prove or disprove those mathematical statements precisely. Let us consider one
example. Rules of Logic enable us to reason about mathematical statements.​

For every positive integer (n), the sum of positive integers not exceeding (n) is

We are well familiar with this particular formula. This formula is nothing but the sum of the first (n)
natural numbers. It is also the sum of the first (n) positive integers. We know that this particular
mathematical statement is a valid mathematical statement. And we would be able to prove this
particular statement with the rules of Logic.

Either it is a valid mathematical argument or it is an invalid mathematical argument. But we know

that this mathematical argument is a valid mathematical argument. And we can prove this also with
the help of Logic. This is what Logic is all about. With Logic, we would be able to reason about
statements.

We would be able to think about mathematical statements. And finally, we would be able to prove
them or disprove them. We do this by using certain rules that are provided by Logic itself. Now, let
us try to understand the purpose of Logic. The purpose of Logic is to construct valid arguments.

Purpose of Logic and Introduction to Proposition

We already know that the purpose of Logic is to construct valid arguments. These valid arguments
are also called proofs. Once we prove that a mathematical statement is true, we call it a theorem.

When we prove a mathematical statement is true, then we call it a theorem. And this is the basis of
whole Mathematics, right?

Let us consider one more example here. In this example, we are talking about one famous puzzle
called the Knights and Knaves Puzzle. In an island, there are two kinds of inhabitants.​
Knights always tell the truth. Their opposites, Knaves, always lie.

You encounter two people, Alice and Bob. Who are Alice and Bob? Alice says that Bob is a knight.​
Bob says that the two of us are opposite types. We want to know who Alice and Bob are.

If Alice says that Bob is a knight, and Bob says that the two of us are opposite types,​
then these kinds of puzzles can be solved very easily. We can solve them by using an area of
Logic called Propositional Logic.

With Propositional Logic, we would be able to solve these types of puzzles very easily.​
We would also be able to solve them in a systematic manner. That is one application of
Propositional Logic. Therefore, learning Propositional Logic is fun. And it is very important.

5
Now, let us try to understand what is Propositional Logic. We already know that Propositional Logic
is an area of Logic. But in order to understand what is Propositional Logic, we need to understand
what a Proposition is.

A Proposition is a declarative sentence. This is the basic definition of a Proposition. We will use
this definition in the study of Propositional Logic.

Declarative Sentences and Propositions

A declarative sentence is a sentence that is declaring a fact. Or it is stating an argument.​

Such a sentence can be either true or false. But it cannot be both.

A proposition is a declarative sentence. It can be either true or false. But it cannot be both true and
false at the same time. This is the definition of a proposition.

Let us consider some examples.​

"Delhi is the capital of India." It can be true or it can be false. Since it is a declarative sentence, it is
a proposition.

Consider the sentence: "Water froze this morning." Definitely, this statement can be true or false. It
is a declarative sentence. Therefore, it is a proposition.

Consider another statement: "1 + 1 = 2." We know that this statement is true. Also, it is a
declarative sentence. Therefore, this is a proposition.

Now let us consider some more [Link] sentences are not propositions.​
"What time is it?" This is not a proposition. Because it is not a declarative sentence.

It is asking something. "What time is it?" It is not declaring a fact. Therefore, it is not a proposition.

Now consider the statement: "x + 1 = 2." It might seem like it is a declarative sentence.​
But think about it carefully. It can be both true or false. Maybe you provide x = 1.​
In that case, this statement is true. But if you provide x = 2, then this statement is false. Therefore,
we are not certain about this statement.

It totally depends on the value of x. Therefore, we cannot say that it is a proposition. As we know, a
proposition is a declarative sentence. That can be true or false. But it cannot be both.

Consider the sentence: "Send us your résumé before 11 p.m." You are commanding someone to
send the résumé before 11 p.m. It is not a declarative sentence. Hence, it is not a [Link],
it does not make sense to say that this particular statement is either true or false.​
Therefore, it is not a proposition.

Consider the sentence: "I request you to please allow me a day off." This particular statement is
definitely not a declarative sentence. Because you are requesting something. Therefore, it is not a
proposition.

More Examples of Non-Propositions and Homework Problem

You are not declaring some kind of fact. Or stating an argument. Hence, this is not a proposition.​
This follows directly from the definition of a proposition.

6
Consider the sentence:"Fetch my umbrella." Obviously, you are commanding someone to fetch
your umbrella. How can it be a declarative sentence then? Definitely, it is not a proposition.

A proposition must be a declarative sentence. It must declare a fact or state an argument. The
sentence "Fetch my umbrella" does neither of these. Therefore, it is not a proposition.

Now let us consider one homework problem. Which of the following are propositions? Also, if you
find a proposition, state whether it is true or [Link] each statement carefully.

1.​ London is in Denmark.

2.​ Do your homework.
3.​ India wins the match by two runs.
4.​ X is an even number.
5.​ 5 is an odd number.
6.​ Rahul.
7.​ 5 + 7 = 10.
8.​ The moon is made of cheese.
9.​ The only odd prime number is two.
10.​God bless you.

Discrete Mathematics – Lecture 3: Propositional Logic,

Propositional Variables & Compound Propositions

Propositional Logic: Fundamental Concepts

Three Most Important Fundamental Aspects of Propositional Logic

In this lecture, we are going to discuss the three most important fundamental aspects of
propositional logic:

1.​ Propositional Logic

2.​ Propositional Variables
3.​ Compound Propositions

What is Propositional Logic?

Propositional Logic is an area of logic that studies ways of joining and/or modifying propositions
to form more complicated-looking propositions.

In propositional logic, we find out the ways of joining and/or modifying propositions to form more
complicated-looking propositions.

It also studies:

●​ The relationships among these propositions.

●​ The properties that are derived from these combined or altered propositions.

7
Understanding the Definition

Consider the following statement:

Statement 1:

Adam is good in playing football.

Now consider another statement:

Statement 2:

Adam is good in playing football and this time he is representing his college at national
level.

In other words:

Not only Adam is good in playing football, but this time he is also representing his
college at national level.

Here, the statement has been rewritten. If we observe carefully, in this statement we are trying to
combine two propositions together.

Understanding Propositions, Logical Connectives, and Negation

Combining Propositions Using a Logical Connective

Consider the following propositions:

Proposition 1:

Adam is good in playing football.

Proposition 2:

This time he is representing his college at national level.

These two propositions are combined with the help of a logical connective called "and."

The resulting statement is:

Adam is good in playing football and this time he is representing his college at national
level.

We are trying to combine these two propositions together with the help of the logical connective
and.

This is what propositional logic deals with.

As discussed earlier, propositional logic studies the ways of joining propositions to form more
complicated-looking propositions.

8
In this example, two propositions are combined using and to form a more complicated-looking
proposition.

Modifying a Proposition Using Negation

Consider the statement:

I enjoy watching television.

Now consider the statement:

It is not the case that I enjoy watching television.

Difference Between the Two Statements

The second statement is the negation of the first statement. Here, we are trying to modify the
statement using negation. This is also consistent with the definition of propositional logic.

In propositional logic:

●​ We combine two or more propositions together.

●​ We also modify propositions.

Other Names of Propositional Logic

One important fact is that propositional logic is sometimes called:

●​ Sentential Logic
●​ Statement Logic

Why is Propositional Logic Also Called Sentential Logic or Statement Logic?

Propositional logic is called sentential logic or statement logic because it deals with statements
such as the examples discussed above.

Need for Compound Propositions and Introduction to Propositional Variables

Purpose of Propositional Logic

Propositional logic tries to find out the ways of modifying or joining propositions together so that we
would be able to form even more complicated propositions.

Why Do We Need Compound Propositions?

A question arises:

What is the need for creating those complicated-looking propositions?

These complicated-looking propositions are also called compound propositions.

9
The reason for considering compound propositions is that most mathematical statements are
constructed by combining one or more propositions.

In other words:

●​ Most mathematical statements are formed by combining two or more propositions.

●​ Therefore, we need to study compound propositions.
●​ Ultimately, we need to deal with mathematical statements.

As simple as that.

Introduction to Propositional Variables

After discussing propositional logic and learning how propositions can be combined and modified,
the next topic is propositional variables.

Consider the following question:

Which of the following is more convenient to express?

Statement Form

Adam is good in playing football and this time he is representing his college at national
level.

Variable Form

Suppose:

●​ P represents the statement:​

Adam is good in playing football.
●​ Q represents the statement:​
This time he is representing his college at national level.

Then, instead of writing the complete statement, we can write:

P and Q

Thus, instead of writing the entire statement, we can express it as P and Q.

Propositional Variables and the AND Operator

Representing Propositions Using Variables

Consider the following representations:

●​ P represents the first proposition.

●​ Q represents the second proposition.

10
Since P represents the first proposition and Q represents the second proposition, these two
propositions can be combined using the AND operator.

Thus,

P and Q

is equivalent to combining the two propositions represented by P and Q.

In propositional logic, this is called the AND operator.

Why Do We Need Propositional Variables?

It is not very difficult to understand why propositional variables are needed. Propositional variables
help us reduce the burden of writing long statements. Instead of writing long statements
repeatedly, we can represent them in a shorter form using variables.

This representation is:

●​ More convenient to write.

●​ More convenient to deal with.

Definition of Propositional Variables

Definition:

Variables that are used to represent propositions are called propositional variables.

In simple words, propositional variables are variables used to represent propositions.

Combining Propositions Using Operators

Once propositions are represented using propositional variables, it becomes much more
convenient to combine them using certain operators available in propositional logic.

The AND operator is one such operator.

More operators available in propositional logic will be discussed in subsequent lectures.

For now, it is sufficient to know that:

●​ Propositions can be represented using propositional variables.

●​ These propositions can then be combined using logical operators.

Conclusion

For now, the important idea is that propositions can be represented by propositional variables, and
these variables can be combined using operators available in propositional logic.

11
East or West, Luians of CSE 69,
Section G, are the Best.

12