1.1 Set
Set is a collection of well defined objects.
For example: V={a,e,i,o,u}, N={0,1,2,3,..........} etc.
1.1.1 Types of sets:
i. Empty Set: A set having no elements is a empty set. It is denoted by φ or {}.
For example A = {x:x is student socring 101% in TOC.}
ii. Singleton Set: A set having only one elements is singleton set.
For example A = {0} A = :{x:x is highest mountain in the world.}
iii. Finite Set: A set having finite number of elements is known as finite set.
For example V={a,e,i,o,u}
iv. Infinite Set: A set having infinite elements is known as infinite set.
For example: A={0,1,2,3,.......}
1.1.2 Preperties of Set Operations:
Identity Law:
A∪φ=A, A∩U=A;
Domination Law:
A∪U=U, A∩φ=φ
Indempotency: A∪A=A, A∩A=A
Absorption Law: (A∪B)∩A=A, (A∩B)∪A=A
Commutative Law: A∪B=B∪A, A∩B=B∩A
Associative Law: A∪(B∪C)=(A∪B)∪C,
A∩(B∩C)=(A∩B)∩C
Distribution Law: (A∪B)∩C=(A∩C)∪(B∩C), (A∩B)∪C=(A∪C)∩(B∪C)
De-Morgan's Law: A-(B∪C)=(A-B)∩(A-C), A-(B∩C)=(A-B)∪(A-C)
1.2 Proof Techniques:
1.2.1 Principle of Mathematical Induction:
Mathematical Induction is a technique of proving a statement, theorem or formula which is thought to be true, for each and every natural number n.
It states that if we prove S(i) and we prove P(n) implies P(n+1) ∀ n ≥1
Let P be a property defined on the set of natural numbers which is true for n=1. It(P) is assumed to be true for n=k. If we can show that P is true for n=k+1, We can conclude that P is always true.
Steps:
- We first try to show the given property statement is true for n=0 or 1.
- We assume that given statement is true for n=k.
- We try to prove the given realtion for n=k+1. If this step is vallid, Then we can conclude that given statement is always true.
Example of mathematical induction:
Q. To prove 1+2+3+ ...... +n = \(n(n+1)\over2 \) using principle of mathematical induction.
Solution:
Let P(n) be the statement.
i.e. P(n)=1+2+3+ ...... +n
=\(n(n+1)\over 2 \)
LHS=1
RHS=\(1(1+1)\over2\) = \(2\over 2\) = 1
Since, LHS=RHS. This statemnet is true for n=1.
Let's Suppose this equation is true for n=k. Then,
P(k) = \(1+2+3+.....+k\) = \(k(k+1)\over2\)
When n=k+1,
P(k+1) = 1+2+3+.....+k+(k+1)
=\(k(k+1)\over2\)+k+1
=(\(k\over2\)+1)(k+1)
=\((k+2)(k+1)\over2\)
=\((k+1)[(k+1)+1]\over2\)
So, This theorem also holds true for n=k+1, when n=k true. Hence by principle of mathematical induction, this theorem is true for n ≥1.
1.2.2 Pigeon Hole Principle:
Pigeon Hole Principle states that,"If A and B are finite sets and |A>|B|, There is no one-one function from A to B. If an attemp is made to pair off the element of A (the pigeon) with the elements of B(the pigeon holes), sooner or latter we will have to put more than one pigeon in a pigeon hole."
Q. A sack has 50 marbels of 4 different colours. Show that there are at least 15 marbels of same colours.
Solution: We need to position the set of 50 elements(marbels) into 4 sets(colours). According to pigeon hole principle at least one of the sets(same colour) hases \(50\over4\)=12.5=13 elements(marbels). That is to say that at least 13 marbels has the same colour.
Q. Show that among 2000 people at least 6 were born on the same day of the year.
Solution: Let us label each person with the day on which they can boorn. Then, there are 365 possible labels and 2000 people assigned those labels.
At least \(2000\over365\) = [5.5] = 6 people. Hence, out of 2000 people at least 6 were born on the same day.
1.2.3 Diagonalization Principle:
The diagonalization principle is simple observation. The principle are as:
a) Assume the condition of contradiction.
b) Find the reversed diagram and check whether it is different from each of the row in table or not.
c) If it is different from each row in the table, it contradicts the assumption proving the theorem.
Explanation: Let A be a finite set A={a,b,c,d} and R be the binary relation on set A such that,
R={(a,a),(a,c),(b,b),(b,d),(c,b),(c,d),(d,a)}
Now, we represent R in a square table (row|column) representing the elements and cell having linked with the correspending elements.
| a | b | c | d | |
| a | 0 | 1 | 1 | 0 |
| b | 0 | 1 | 0 | 1 |
| c | 0 | 1 | 0 | 1 |
| d | 1 | 0 | 0 | 0 |
- The reversed daiigonal is 1,0,1,1. And it is different from each row.
- As the complement of diagonal element is different from each row, it contradict the assumption. Hence the theorem can be proven.
Alphabets:
ALphabets is a finite and non-empty set of symbols. It is denoted by Σ.
Σ = {0,1}
={*, #, σ}
={a,b,c,d,e}
Etc.
Strings:
Strings are finite sequence of symbols taken from alphabets, ,not seperated by commas and denotes by 'w'.
a) Length of string: The total number of alphabets in a string. denoted by |w|.
for example |w|=|00110|=5.
b) Empty String: The string that has zero occurance oof string, denoted by ε or e or Λ or λ.
c) Σ*: It is set of all string including empty strings over the alphabets Σ. d) Concatenation of string: The process of appending one string to the end of another string.
e) Reversal of string: w=w1+w2+w3+w4+.........+wn
wR=wn+w(n-1)+.............+w3+w2+w1
For example: If w=abc, Then: wR=cba
Language:
A set of string over a alphabet is known as Language. It is the set of all strings including the empty string or an alphabet.
L={w ε {a,b}*, w has odd numbers of a's}
={a,ab,aaba,.......}
L={w ε {a,b}*, w has equal number of a's and b's}
={ab, aabb, abab, aabbab, ..............}
Concatination of languages:
L1 = {hello}L2{world}
L=L1+L2={helloworld}
Regular Language:
The language that can be constructed from the set of operations: union, concatrinatiion and kleene star is known as regular language.
Regular Expression:
It is designed to represent regular language with mathematical tools to build set of strings combining strings ofo symbols from some alphabets, ε and operators + and *0+1 represents the set {0,1}
(0+1)* represents {ε, (0+1), (0+1)(0+1), (0+1)(0+1)(0+1), .....}
(0+1)+ represents {(0+1), (0+1)(0+1), (0+1)(0+1)(0+1), .....}
Building Regular Expression:
-Zero or more : a*-One or more : aa*
-Zero or one : a + ε
-Any string at all : (a+b+c)*
-Any non-empty string at all : (a+b+c)(a+b+c)*