Welcome to WordPress. This is your first post. Edit or delete it, then start writing!
Sequence
Sequences are ordered element lists, which are used in many respects in discrete mathematics. They can, for example, be used to solve certain counting problems. They are also a key computer science data structure.The sequence terms can be specified with a formula for each sequence term.
Definition
A sequence is a discrete structure used to represent an ordered list.
For Example:
1,2,3,6,8 is a sequence with five terms and 1, 3, 9, 27, 81 , . . . , 3n, . . . is an infinite sequence.
A Sequence can also be defined as a function whose domain is either the set of the natural numbers (for infinite sequences) or the set of the first n natural numbers (for a sequence of finite length n). [Wikipedia]
We use the notation an to denote the image of the integer n.
We call an a term of the sequence.
Function
Introduction
A function was originally the idealization of how a varying quantity depends on another quantity. In many cases, we assign a particular element of a second set( which might be the same as the first) to each element of a set.
For Example, suppose each student in a class is assigned a letter grade from set S= { A, B, C, D, F} and suppose the grades are A for Alina, B for Ali, C for Robert , D for Noman, F for Amanda . This assignment of grades will be shown as follows
An example of a function is above assignment. In mathematics and computer science, the concept of a function is extremely important.In the definition of such discrete structures as sequences and strings, for example, discrete math functions are utilized.It also shows how long a computer takes to solve problems of a particular size. Many computer programs and subroutines have been designed to calculate function values.Recursive functions, which are self defined functions, are used in computer science.
Function Definition
A function f from a set X to a set Y is a relationship between elements of X and elements of Y such that each element of X is related to a unique element of Y, and is denoted f : X →Y.
The set X is called the domain of f and Y is called the codomain of f.
In many different ways, functions are specified. Sometimes we declare the tasks explicitly. We often provide a formula for defining a function, such as f(x)= x+ 1. We used another time to specify a function using a computer program.
ARROW DIAGRAM OF A FUNCTION
The definition of one function involves the following two properties in the arrow diagram for a function f:
 An arrow comes out of every X element
 No two X elements have two arrows from which two distinct Y elements appear.
Example:
Let X = {a,b,c} and Y={1,2,3,4}.
Define a function f from X to Y by the arrow diagram
The above diagram easily fulfills the two requirements of the function, hence a function graph.
Note that:
f(a) = 2
f(b) = 4
f(c) = 2
Functions and NonFunctions
Which of the arrow diagram describes functions from X={a, b, c} to Y={d, a, f, g}
The relation given in the diagram (a) is Not a function because there is no arrow coming out of 5∈X to any element of Y.
The relation in the diagram (b) is Not a function, because there are two arrows coming out of 4∈X. i.e.,4∈X is not related to a unique element of Y.
Range of function
When “range” is used to mean “codomain“, the image of a function f is already implicitly defined. It is (by definition of image) the subset of the “range” which equals {y  there exists an x in the domain of f such that y = f(x)}.
When “range” is used to mean “image“, the range of a function f is by definition {y  there exists an x in the domain of f such that y = f(x)}. In this case, the codomain of f must not be specified, because any codomain which contains this image as a subset will work. [Wikipedia]
In both cases, image f ⊆ range f ⊆ codomain f, with at least one of the containment being equality.
Note:
 The function f range is always a subset of the codomain of f.
 The range of f: X→Y is also called the image of X under f.
 When y = f(x), then x is called the preimage of y.
 The set of all elements of X, that are related to some y ∈Y is called the inverse image of y.
Probability Event
The probability event is a set of outcomes of an experiment (a subset of the sample space) to which a probability is assigned. The particular output of sample space is called event
A single outcome may be an element of many different events, and different events in an experiment are usually not equally likely, since they may include very different groups of outcomes. An event defines a complementary event, namely the complementary set (the event not occurring), and together these define a Bernoulli trial.
Typically, when the sample space is finite, any subset of the sample space is an event . However, this approach does not work well in cases where the sample space is uncountably infinite. So, when defining a probability space it is possible, and often necessary, to exclude certain subsets of the sample space from being events. [Wikipedia]
Example:
(1) S={ H , T }
Possible Events[latex]= 2^n = 2^2 = 4[/latex]
Solution:
Possible Events[latex]= 2^n = 2^6 = 64[/latex]
Types of Probability Events
 Impossible event
 Sure/Certain event
 Equally likely events
 Mutually exclusive event
 Exhaustive Event
(1) Impossible event
An event that neither occurs is called impossible event
It is denoted by ɸ
Probability of impossible event is zero
P(impossible event) = 0
P( ɸ ) = 0
(2) Sure/Certain event
An event which surely occur in any condition is called sure or certain event
It is denoted by ‘S’
P(sure event) = 1
P(S) = 1
The range of probability is between 0 & 1
0 ≤ P(E) ≤ 1
(3) Equally likely events
Two or more events are said to be equally likely events if they have an equal chance of occurrence
Example:
S={1, 2, 3, 4, 5, 6}
A={1, 3, 5} B={2, 4, 6}
Above A & B are equally likely event as
A∪B= {1, 2, 3, 4, 5, 6}
(4) Mutually Exclusive Events:
Two or ore events are said to be mutually exclusive events if they cannot occur simultaneously
Inset Notation:
If A and B are two events then A∩B= ɸ
Example:
S={1, 2, 3, 4, 5, 6}
A={1, 3, 5} B={2, 4, 6}
A∪B= { } = ɸ
(5) Exhaustive Events
Two or more mutually exclusive events are said to be exhaustive events if they constitute the sample space
Example:
Probability of an event
If E is an event then probability of an event is denoted by P(E) is given as
[latex]P(E) = \frac{Total\: favorable\: cases}{Total\: possible\: cases}[/latex]
OR
[latex]P(E)= \frac{n(E)}{n(S)} = \frac{ No.\: of \: sample \: probability \: in \: E }{ No. \: of \: sample \: probability \:in \: S }[/latex]
P(E) = ɸ E= Impossible event , denoted by ‘ɸ’
P(E) = 1 E= Sure event denoted by ‘S’
Example1:
A card is drawn at random from a pack of 52 plane cards what is the probability that card is
 Red
 Black
 Diamond
 Pictured Cards
 Divisible by 3
 King
 Red King
 Black Queen
 Jack of club
 Pictured card of heart
Solution:
1.P(a red card) =[latex]\frac{26}{52}\:= \frac{1}{2}[/latex]
2.P(a black card) = [latex]\frac{26}{52}\:= \frac{1}{2} [/latex]
3.P(a diamond card) = [latex]\frac{13}{52}\:= \frac{1}{4}[/latex]
4.P(a pictured card) = [latex]\frac{12}{52}\:= \frac{3}{13}[/latex]
5.P(a card divisible by 3) = [latex]\frac{12}{52}\:= \frac{3}{13} [/latex]
6.P(a king) = [latex]\frac{4}{52}\:= \frac{1}{13} [/latex]
7.P(a red king) =[latex] \frac{2}{52}\:= \frac{1}{26} [/latex]
8.P(black queen) = [latex]\frac{2}{52}\:= \frac{1}{26} [/latex]
9.P(a jack of club) = [latex]\frac{1}{52}[/latex]
10.P( pictured card of heart) = [latex]\frac{26}{52}[/latex]
Example 2:
A coin is tossed 3 times what is the probability the 3 coin shows
 1 Heads
 2 Heads
 3 Heads
 Atleast 1 Head
 Atleast 2 Head
 Atleast 3 Head
 Atmost 1 Head
 Atmost 2 Head
 Atmost 3 Head
Solution:
No. of possible outcomes =[latex] n(S) = 2^3 =8[/latex]
S = { HHH, HHT , HTH , HTT , THH ,THT ,TTH ,TTT }
1.[latex]E_1[/latex] = { 1 Head }
={ HHT, THT ,TTH }
[latex]P( E_1) =\frac{n(E_1)}{n(S)}=\: \frac{3}{8}[/latex]
2.[latex]E_2[/latex] = { 2 Head }
={ HHT, HTH, THH }
[latex]P( E_2) =\frac{n(E_2)}{n(S)}=\: \frac{3}{8}[/latex]
3.[latex]E_3 [/latex] = { 3 Head }
={ HHH }
[latex]P( E_3) =\frac{n(E_3)}{n(S)}=\: \frac{1}{8}[/latex]
4.[latex]E_4 [/latex]= { Atleast 1 Head }
= { HHH, HHT , HTH , HTT , THH ,THT ,TTH }
[latex]P( E_4) =\frac{n(E_4)}{n(S)}=\: \frac{7}{8}[/latex]
5.[latex]E_5 [/latex]= { Atleast 2 Head }
= { HHH, HHT , HTH , THH }
[latex]P( E_5) =\frac{n(E_5)}{n(S)}=\: \frac{4}{8} =\: \frac{1}{2} [/latex]
6.[latex]E_6 [/latex]= { Atleast 3 Head }
= { HHH }
[latex]P( E_6) =\frac{n(E_6)}{n(S)}=\: \frac{1}{8}[/latex]
7.[latex]E_7 [/latex]= { Atmost 1 Head }
= { HHH, THT, TTH, TTT }
[latex]P( E_7) =\frac{n(E_6)}{n(S)}=\: \frac{4}{8} =\: \frac{1}{2} [/latex]
8.[latex]E_8 [/latex]= { Atmost 1 Head }
= { HHT , HTH , HTT , THH ,THT ,TTH ,TTT }
[latex]P( E_8) =\frac{n(E_8)}{n(S)}=\: \frac{7}{8}[/latex]
9.[latex]E_9 [/latex]= { Atmost 3 Head }
= { HHH, HHT , HTH , HTT , THH ,THT ,TTH ,TTT }
[latex]P( E_9) =\frac{n(E_9)}{n(S)}=\: \frac{8}{8}[/latex]
Probability
The numerical evaluation of degree of uncertainty is called probability
The word probability derives from the Latin probabilitas, which can also mean “probity”
Chances of occurrences lies between two things possible and impossible
Introduction
 The probability and combinatorics have common origins.
 It was first developed when gambling games were analysed more than 300 years ago.
 While probability theory has originally been invented to learn gambling, it is now a key Role in a wide range of fields.
 For example, the theory of probability is widely used Genetics Study where the inheritance of characteristics can be understood.
 The likelihood of applicability of mathematics is still a very popular element, which is still a very popular human effort.
 The theory of probability plays an important role in studying computer science algorithms
 The average case complexity of algorithms is determined by ideas and techniques from probability theory.
 Probabilistic algorithms can be used to solve many problems which deterministic algorithms cannot easily or practically solve.
 In a probabilistic algorithm, instead of always taking the same steps as a deterministic algorithm when given the same input, the algorithm makes one or more random choices that can lead to different outputs.
 Probability theory can help us answer questions that involve uncertainty
To calculate the probability, note that there are nine possible outcomes, and four of
these possible outcomes produce a blue ball. Hence, the probability that a blue ball is chosen
is 4/9.
Theory of probability
 Like other theories, the theory of probability is a representation of its concepts in formal terms—that is, in terms that can be considered separately from their meaning.
 These formal terms are manipulated by the rules of mathematics and logic, and any results are interpreted or translated back into the problem domain.
 The scientific study of probability is a modern development of mathematics. [Wikipedia]
Example:
An bag contains four blue balls and five red balls. What is the probability that a ball chosen at random from the bag is blue?
Solution:
To calculate the probability, note that there are nine possible outcomes, and four of
these possible outcomes produce a blue ball. Hence, the probability that a blue ball is chosen
is 4/9.
Random experiment
An experiment which produces different results even when it is repeated under similar conditions is called random experiment
For Example:
Tossing a coin is a simple random experiment
Properties:
The random experiment has following three properties
 It consist of more than one outcome
 The possible outcomes of experiment are known in advance
 The experiment can be repeated many/any number of times
Sample Space:
The set containing all possible outcomes of the random experiment is named as sample space
It is denoted by ‘S’ . Each member of the sample space is named as sample point.
Trail
The single repetition of random experiment is called trail
If trails are more than one then:
[latex] No. of possible outcomes= n( S ) =m^n [/latex]
m = Outcomes of single trail
n = No. of outcomes
Examples:
Random Experiment= Tossing 3 coins
(1) [latex]Total no. of possible outcomes= n(S) =m^n=2^3=8[/latex]
{ HHH, HHT , HTH , HTT , THH ,THT ,TTH ,TTT }
(2) [latex] Total no. of possible outcomes= n(S) =m^n=2^4=16[/latex]
{ HHHH , HHHT , HHTH , HHTT , HTHH , HTHT , HTTH , HTTT ,
THHH , THHT , THTH , THTT , TTHH , TTHT , TTTH , TTTT }
(3) [latex] Total no. of possible outcomes= n(S) =m^n=6^1=6[/latex]
S={ 1, 2, 3, 4, 5, 6 }
(4) [latex]Total no. of possible outcomes= n(S) =m^n=6^2=36 [/latex]
S = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6)
(2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6)
(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6)
(4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6)
(5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6)
(6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)}
Event
The particular output of sample space is called event
Example:
(1) S={ H , T }
Possible Events[latex]= 2^n = 2^2 = 4[/latex]
Solution:
Possible Events[latex]= 2^n = 2^6 = 64[/latex]
Venn Diagram
A Venn diagram is a diagram that shows all possible logical relations between a finite collection of different sets
Introduction
Venn charts, named after the English mathematician John Venn, which introduced their use in 1881, Venn diagram can be used to represent sets graphically. In Venn diagrams the universal set U which contains all the subjects that are shown as a rectangle.
In this rectangle, the circles or other geometric figures are used to represent the sets.( Note that the universal sets vary depending on which objects are of interest.) Sometimes points represent the specific elements of the set
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 diagrams can be used to illustrate that a set A is a subset of a set B. We draw the universal set S as a rectangle.Within this rectangle we draw a circle for B and a circle for A .
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
EXAMPLES:
(1) If A = {1, 3, 5, 7} and B = {1, 2, 4, 6} then A ∪ B = {1, 2, 3, 4, 5, 6, 7}.
(2)
A = {x is an even integer larger than 1}
B = {x is an odd integer larger than 1}
[latex]{\displaystyle A\cup B=\{2,3,4,5,6,\dots \}}[/latex]
(3) 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:
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}
Intersection is an associative operation; that is, for any sets A, B, and C, one has A ∩ (B ∩ C) = (A ∩ B) ∩ C. Intersection is also commutative; for any A and B, one has A ∩ B = B ∩ A. It thus makes sense to talk about intersections of multiple sets. The intersection of A, B, C, and D, for example, is unambiguously written A ∩ B ∩ C ∩ D. [Wikipedia]
VENN DIAGRAM FOR INTERSECTION:
MEMBERSHIP TABLE FOR INTERSECTION:
DIFFERENCE:
Let A and B be subsets of a universal set U. The difference of “A and B” (or relative complement of B in A) is the set of all elements in U that belong to A but not to B, and is denoted A – B or A \ B.
Symbolically:
A – B = {x ∈U  x ∈ A and x ∈B}
EXAMPLE:
Let U = {a, b, c, d, e, f, g}
A = {a, c, e, g}, B = {d, e, f, g}
Then A – B = {a, c}
VENN DIAGRAM FOR SET DIFFERENCE:
MEMBERSHIP TABLE FOR SET DIFFERENCE:
COMPLEMENT:
Let A be a subset of universal set U. The complement of A is the set of all element in U that do not belong to A, and is denoted AN, A or Ac
Symbolically:
A^{c} = {x ∈ U  x ∉ A}
EXAMPLE:
Let U = {a, b, c, d, e, f, g]
A = {a, c, e, g}
Then A^{c} = {b, d, f}
VENN DIAGRAM FOR COMPLEMENT:
MEMBERSHIP TABLE FOR COMPLEMENT:
Set Operations
Set operations can be performed in many different ways, they can be performed by combining two or more sets.
For example, starting with a set of majors of mathematics in your school and a set of informatics majors at your college, we can train students who are majors in mathematics or informatics, a set of students who are mathematics and IT collaborators, and a set of students who do not study mathematics.
If we think of sets as representing , each logical connective that gives
rise to a corresponding set operations:
 A ∪ B = {x  x ∈ A ∨ x ∈ B}. The union of A and B.
 A ∩ B = {x  x∈ A ^ x ∈ B}. The intersection of A and B.
 A \ B = {x  x ∈ A ^ x ∉ B}. The set difference of A and B.
(Of these, union and intersection are the most important in practice.)
Corresponding to implication is the notion of a subset:
A ⊆ B (“A is a subset of B”) if and only if
8x : x 2→A ! x ∈ B.
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
EXAMPLE:
The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5}
that is,
{1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}.
VENN DIAGRAM 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}
Intersection is an associative operation; that is, for any sets A, B, and C, one has A ∩ (B ∩ C) = (A ∩ B) ∩ C. Intersection is also commutative; for any A and B, one has A ∩ B = B ∩ A. It thus makes sense to talk about intersections of multiple sets. The intersection of A, B, C, and D, for example, is unambiguously written A ∩ B ∩ C ∩ D. [Wikipedia]
EXAMPLE:
The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3}
that is,
{1, 3, 5} ∩ {1, 2, 3} = {1, 3}.
VENN DIAGRAM FOR INTERSECTION:
Disjoint
Two sets are called disjoint if their intersection is the empty set.
EXAMPLE:
Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}.
Because A ∩ B = ∅, A and B are disjoint
DIFFERENCE
Let A and B be subsets of a universal set U. The difference of “A and B” (or relative complement of B in A) is the set of all elements in U that belong to A but not to B, and is denoted A – B or A \ B.
Symbolically:
A – B = {x ∈U  x ∈ A and x ∈B}
EXAMPLE:
Let U = {a, b, c, d, e, f, g}
A = {a, c, e, g}, B = {d, e, f, g}
Then A – B = {a, c}
VENN DIAGRAM FOR SET DIFFERENCE:
COMPLEMENT:
Let A be a subset of universal set U. The complement of A is the set of all element in U that do not belong to A, and is denoted AN, A or Ac
Symbolically:
A^{c} = {x ∈ U  x ∉ A}
EXAMPLE:
Let U = {a, b, c, d, e, f, g]
A = {a, c, e, g}
Then A^{c} = {b, d, f}
VENN DIAGRAM FOR COMPLEMENT:
Set Identities:
Following Lists key identities of the set. There are three different methods to prove several of those identities. These methods are presented to show that many approaches to solving a problem often exist. Set identities and propositional equivalence are only special cases of identity for Boolean algebra as evidence of the remaining identities.
Set
A set is a welldefined 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:
 A collection of students going on a trip is a set
 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:
 The objects are called the elements or members of the set.
 Sets are denoted by capital letters A, B, C …, X, Y, Z.
 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 A, B includes A, or B contains A. [wikipedia]
[
Discrete Mathematics MCQS
Discrete Mathematics MCQS:
Following are some mcqs that will be very useful to test yourself that how strong is your grip in discrete mathematics:
 A sequence in which every term after the first is obtained from the preceding term by adding a constant number is called _________.
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 A sequence in which every term after the first is obtained from preceding term by multiplying it with a constant number is called __________.
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 In general, if a is the first term and d the common difference of an _____________then the series is given as: a+(a+d)+(a+2d)+….
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 In general, if a is the first term and r the common ratio of a ________, then the series is given as: a+ar+a+a+….
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 Recursive definitions can be used in a “_________” manner.
(a) Generative (b) Nongenerative (c)both a & b.
 An integer n is _______ if, and only if n=2k for some integer k.
(a) Even (b) odd (c) prime
 An integer n is ______ if, and only if n=2k+1 for some integer k.
(a) Even (b) odd (c) prime
 An integer n is _______ if and only if n>1 and for all positive integers r and s, if n=r.s, then r = 1 or s = 1.
(a) Rational (b) composite (c) prime
 An integer n>1 is ________ if and only if n=r.s for some positive integer rand s with r ≠ 1 and s ≠ 1
(a) Rational (b) composite (c) prime
 A real number r is ________ if and only if for some integers a and b with b ≠ 0.
(a) Rational (b) composite (c) prime
 If n and d are integers and d ≠ 0, then d _______ n if and only if n=d.k for some integers k.
(a) Multiplies (b) divides (c) subtracts
 An integer n is called a perfect _______ if and only if n= for some integer k.
(a) cube (b) square (c) multiple
 Square of an even integer is _____ .
(a) Even (b) odd (c) both

 If a graph is a tree, then its only ________ is itself.
(a) Rooted tree (c) Binary tree (c) Trivial tree

A _______ spanning tree for a weighted graph is a spanning tree that has the least possible total weight compared to all other spanning trees of the graph.

(a) Minimal rooted (b) Minimal spanning (c) minimal trivial
 How many bit strings of length 8 begin and end with 1.
(a) 87 (b) 64 (c) 72
 How many three digit integers are divisible by 5.
(a) 140 (b) 160 (c) 180
 A ksample of a set of n elements is a choice of k elements taken from the set of n elements such that the order of elements matters and elements _________ .
(a) Can be repeated (b) cannot be repeated (c)none
 A ________ of a set of n elements is a selection of k elements taken from the set of n elements such that the order of elements matter but repetition of elements is not allowed.
(a) kpermutation (b) kselections (c) kcombinations
 With a kcombination the order in which the elements are selected ________ and the elements cannot repeat.
(a) Does matter (b) does not matter (c) none
 C (n, 0) = __.
(a) 0 (b) 1 (c) 2
 C (n, n) = __.
(a) 0 (b) 1 (c) 2
 C (n, 1) = __.
(a) n (b) n1 (c) n2
 C (n, 2) =______.
(a) n (n1) (b) n (n2) (c) n (n1)/2
 C (n, k) = ______ .
(a) n, nk (b) n, n1 (c) n, n2
 C (n, k) + C (n, k+1) = ___________ .
(a)n+1, k+1 (b) n+2, k+2 (c)C(n+1, k+1)
 How many 16bit strings contain at least one 1’s.
(a)45573 (b) 84522 (c) 65535
 __________ are similar to kcombinations in that the order in which the elements are selected does not matter, but in this case repetitions can occur.
(a) kpermutation (b) kselections (c) kcombinations
 A ________ is a useful tool to list all the logical possibilities of a sequence of events where each event can occur in a finite number of ways.
(a) logical diagram (b) mathematical diagram (c) tree diagram
 n (AB)= _____________.
(a) n(A) + n(B) (b) n(A) – n(B) + n(AB) (c) n(A) + n(B) – n(AB)
 A function from a set of k+1 or more elements to a set of k elements must have at least two elements in domain that have the same image in the codomain is called _____________ .
(a) sparrowhole principle (b) pigeonhole principle (c) logical principle
 The theory of probability was first developed in the ______ century when certain gambling games were analyzed by the French mathematician Blaise Pascal.
(a) 16^{th} (b) 17^{th} (c) 18^{th}
 In the 18^{th} century, the French mathematician Laplace, who also studied gambling, gave definition of the _________ as the number of successful outcomes divided by the number of total outcomes.
(a) Sample space (b) Event (c) probability
 An _________ is a procedure that yields a given set of possible outcomes.
(a) Sample space (b) Event (c) Experiment
 The __________ of the experiment is the set of possible outcomes.
(a) Sample space (b) Event (c) Experiment
 An _____ is a subset of the sample space.
(a) Sample space (b) Event (c) Experiment
 If A and B are two disjoint events of a sample space S, then P (AB) = _________ .
(a) P(A) (b) P(A) + P(B) (c) P(A) – P(B)
 If A and B are any two events of a sample space S, then P (AB) = __________ .
(a) P(A) + P(B) (b) P(A) – P(B) + P(A∩B) (c) P(A) + P(B) –P(A∩B)
 A ________ X is a rule that assigns a numerical value to each outcome in a sample space S.
(a) Random variable (b) Unique variable (c) None
 A ________ is a nonempty set of points called vertices and a set of lines segments joining pairs of vertices called edges.
(a) Chart (b) Graph (c) Diagram
 An edge connects either one or two vertices are called its ________.
(a) Incident (b) Adjacent (c) Endpoints
 An edge with just one end point is called a _______.
(a) Incident (b) Loop (c) isolated
 Two vertices that are connected by an edge are called ________.
(a) Incident (b) Adjacent (c) Endpoints
 An edge is said to be _________ to each of its endpoint.
(a) Incident (b) Adjacent (c) Endpoints
 A vertex on which no edges are incident is called _______.
(a) Incident (b) Loop (c) isolated
 Two distinct edges with the same set of end point are said to be ________.
(a) Incident (b) parallel (c) isolated
 A graph G is regular of degree or kregular if every _______ of G has degree k.
(a) Vertex (b) Edge (c) Loop
 The complete graph is ______ regular.
(a) n (b) (n1) (c) (n+1)
 The __________ G is a simple graph whose vertex set can be partitioned into two ,mutually disjoint non empty subsets A and B such that the vertices in A may be connected to vertices in B, but no vertices in A are connected to vertices in A and no vertices in B are connected to B.
(a) Regular graph (b) Bipartite graph (c) Complete bipartite graph
 A ________________ on (m+n) vertices denoted is a simple graph whose vertex set can be partitioned into two mutually disjoint non empty subsets A and B containing m and n vertices respectively, such that each vertex in set A is connected to every vertex in set B, but the vertices within a set are not connected.
(a) Regular graph (b) Bipartite graph (c) Complete bipartite graph
 A square matrix A=[] of size n×n is called _______ if and only if .
(a) Transpose (b) symmetric (c) Graph
 If the number of columns of A is not equal to the number of rows of B, then the product AB is ________.
(a) Defined (b) not defined (c) none
 A directed graph or digraph, consists of two finite sets: a set V (G) of vertices and a set D (G) of directed edges, where each edge is associated with an ordered pair of vertices called its_________ .
(a) End points (b) vertices (c) loop
 A _____ is a connected graph that does not contain any nontrivial circuit.
(a) Tree (b) trivial tree (c) empty tree
 A graph that consists of single vertex is a called a _______ .
(a) Tree (b) trivial tree (c) empty tree
 A tree that does not have any vertices or edges is called an _________.
(a) rooted Tree (b) trivial tree (c) empty tree
 A graph is called a _______ if and only if it is circuitfree.
(a) rooted Tree (b) Binary tree (c) forest
 A tree with n vertices has _______ edges.
(a) n (b) n + 1 (c) n – 1
 A tree has no nontrivial circuit; but if one new edge (but no new vertex) is added to it, then the resulting graph has exactly one _____________.
(a) trivial circuit (b) Non trivial circuit (c) binary circuit
 A tree is connected but if any edge is _________ from it, then the resulting graph is not connected.
(a) Deleted (b) subtracted (c) None
 Any tree that has more than one vertex has at least _____ vertices of degree 1.
(a) Two (b) three (c) four
 A graph is a _____ if there is a unique path between any two of its vertices.
(a) Binary tree (b rooted tree (c) tree
 A ________ is a tree in which one vertex is distinguished from the others is called the root.
(a) Binary tree (b) rooted tree (c) tree
 The ______ of a vertex is the number of edges along the unique path between it and the root.
(a) Level (b) Height (c) Children
 The _________ of a rooted tree is the maximum level to any vertex of the tree.
(a) Level (b) Height (c) Children
 The ________ of any internal vertex v are all those vertices that are adjacent to v and are one level further away from the root then v.
(a) Level (b) Height (c) Children
 If w is a child of v, then v is called the _______ of w.
(a) Children (b) parent (c) siblings
 Two vertices that are both children of same parent are called ______.
(a) Children (b) parent (c) siblings
 Given vertices v and w, if v lies on the unique path between w and the root, then v is an ancestor of w and w is the _________of v.
(a) Descendant (b) parent (c) siblings
 A _________ is a rooted tree in which every internal vertex has at most two children.
(a) Rooted tree (c) Binary tree (c) Trivial tree
 Every child in a binary tree is designated either a left or right child but ________.
(a) Both (b) not both (c) none
 A full binary tree is a binary tree in which each internal vertex has exactly ______ children.
(a) Two (b) Three (c) Four
 A ________ for a graph G is a sub graph of G that contains every vertex of G and is a tree.
(a) Rooted tree (c) Binary tree (c) Spanning tree
 Every connected graph has a __________.
(a) Rooted tree (c) Binary tree (c) Trivial tree
 A graph may have more than ______ spanning trees.
(a) Two (b) Three (c) Four
 Any two spanning trees for a graph have the ______ number of edges.
(a) Same (b) Different (c) Both a & b
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:
 It is Friday today
 Islamabad is capital of Pakistan
 3 + 2 = 6
 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:
 “6 + 4 = 10” and “Multan is a city in Pakistan”
 “The grass is green” or “It is sunny today”
 “English is not difficult for me”
Logical Connectives:
AND, OR, NOT are called 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 .
p = 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.
Negation:
If p is a statement variable, then negation of p, “not p”, is denoted as “~p”
It has opposite truth value from p i.e.,
if p is true, ~p is false; if p is false, ~p is true.
Example 1:
Find the negation of the proposition
“Ayesha’s PC runs windows 10.”
Solution: “Ayesha’s PC does not run Windows 10.”
Example 2:
Find the negation of the proposition
“Nabiha’s phone has at least 18 GB of memory.”
Solution: “Nabiha’s phone does not have at least 18 GB of memory.”
TRUTH TABLE FOR ~ p :
Conjunction:
If p and q are statements, then the conjunction of p and q is “p and q”, denoted as “p Λ q”.
It is true when, and only when, both p and q are true. If either p or q s false, or if both are false, pΛq is false.
Example 3:
Find the conjunction of the propositions p and q where p is the proposition“Multan is a city of Pakistan.”and q is the proposition “Ali’s PC run faster than 1 GHz.”
Solution: “Multan is a city of Pakistan and Ali’s PC run faster than 1 GHz. .”
Truth table for p ∧ q:
DISJUNCTION:
If p & q are statements, then the disjunction of p and q is “p or q”, denoted as“p ∨ q”.It is true when at least one of p or q is true and is false only when both p and q are false.
Example 3:
Find the disjunction of the propositions p and q where p is the proposition“Multan is a city of Pakistan.”and q is the proposition “Ali’s PC run faster than 1 GHz.”
Solution: “Multan is a city of Pakistan, or Ali’s PC run faster than 1 GHz. .”
TRUTH TABLE FOR p ∨ q: