Discrete Math Notes

Introduction to discrete math notes
Discrete Mathematics deals with a number of selected topics in Mathematics those are essential to the study of many Computer Science areas. Since it is very difficult to cover all the topics, only two topics, namely “Mathematical Logic” and “Groups” have been introduced. These topics will be very much helpful to the students in certain practical applications related to Computer Science. In this article we shall discuss about discrete math notes.

Discrete Mathematics Statements Notes

Logical statement or Proposition:

A statement or a proposition is a sentence which is either true or false but not both.

Simple statements:

A statement is said to be simple if it cannot be broken into two or more statements. All the statements in (a) and (b) of Example 1 are simple statements.

Compound statements:

If a statement is the combination of two or more simple statements, then it is said to be a compound statement.

Negation of a negation:

Negation of a negation of a statement is the statement itself. Equivalently we write ~ (~ p) = p

Conditional and bi-conditional statements:

In Mathematics, we frequently come across statements of the form “If p then q”. Such statements are called conditional statements or implications. They are denoted by p ? q, read as ‘p implies q’. The conditional p ? q is false only if p is true and q is false. Accordingly, if p is false then p ? q is true regardless of the truth value of q.

Tautologies:

If the last columns of  truth table have the value only T a statement is called a tautology, i.e., it is true for all logical possibilities. If the last column of its truth table have the value only F, i.e., it is false for all logical possibilities is called as statement contradiction

Discrete Mathematics Notes Example Problems
Example 1: Construct the truth table for ((~p) ? (~ q))

Truth table for ((~p) ? (~ q))

P          q         ~ p      ~ q      ((~p) ? (~ q))

T          T          F          F          F

T          F          F          T          T

F          T          T          F          T

F          F          T          T          T



Example 2: Show that ~ (p ? q) = (~ p) ? (~ q)

Solution:

Truth table for ~ (p ? q)

P          q         p ? q    ~ (p ? q)

T          T         T          F

T          F          T          F

F          T          T          F

F          F          F          T

Truth table for ((~ p) ? (~ q))

p          q          ~p       ~ q      ((~ p) ? (~ q))

T          T         F         F         F

T          F         F         T         F

F          T         T         F         F

F          F         T         T         T

The last columns are identical. ? ~ (p ? q) = ((~ p) ? (~ q))