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

function Example
Assigning grades to to the students of a class

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 co-domain 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:

  1. An arrow comes out of every X element
  2. 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

Function Example

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 Non-Functions

Which of the arrow diagram describes functions from X={a, b, c} to Y={d, a, f, g}

Non-Function Example

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 co-domain of f must not be specified, because any co-domain which contains this image as a subset will work. [Wikipedia]


In both cases, image f ⊆ range f ⊆ co-domain f, with at least one of the containment being equality.

Note:

  1. The function f range is always a subset of the co-domain of f.
  2. The range of f: X→Y is also called the image of X under f.
  3. When y = f(x), then x is called the pre-image of y.
  4. 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:

Probability Event

Possible Events[latex]= 2^n = 2^6 = 64[/latex]

probability Event

Types of Probability Events

  1. Impossible event
  2. Sure/Certain event
  3. Equally likely events
  4. Mutually exclusive event
  5. 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 AB= ɸ

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:

Exhaustive event
Exhaustive Event
They are different sets but when combined make one set that is constitute of its sample space is known as exhaustive events

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

  1. Red
  2. Black
  3. Diamond
  4. Pictured Cards
  5. Divisible by 3
  6. King
  7. Red King
  8. Black Queen
  9. Jack of club
  10. 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. 1 Heads
  2. 2 Heads
  3. 3 Heads
  4. At-least 1 Head
  5. At-least 2 Head
  6. At-least 3 Head
  7. At-most 1 Head
  8. At-most 2 Head
  9. At-most 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]= { At-least 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]= { At-least 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]= { At-least 3 Head }

= { HHH }

[latex]P( E_6) =\frac{n(E_6)}{n(S)}=\: \frac{1}{8}[/latex]

7.[latex]E_7 [/latex]= { At-most 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]= { At-most 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]= { At-most 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

  1. It consist of more than one outcome
  2. The possible outcomes of experiment are known in advance
  3. 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]

=  {(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:

Probability Event

Possible Events[latex]= 2^n = 2^6 = 64[/latex]

probability Event

Venn Diagram


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 .

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

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:

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}

Intersection is an associative operation; that is, for any sets AB, 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 ABC, and D, for example, is unambiguously written A ∩ B ∩ C ∩ D. [Wikipedia]

VENN DIAGRAM FOR INTERSECTION:

Venn Diagram Intersection
A ∩ B is Shaded

MEMBERSHIP TABLE FOR INTERSECTION:

Membership table for intesection

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:

Venn Diagram set difference
A-B is shaded

MEMBERSHIP TABLE 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:
                                    Ac = {x ∈ U | x ∉ A}

EXAMPLE:

                                    Let       U = {a, b, c, d, e, f, g]

                                                A = {a, c, e, g}

                                    Then    Ac = {b, d, f} 

VENN DIAGRAM FOR COMPLEMENT:

Venn Diagram Complement
A Complement is Shaded

MEMBERSHIP TABLE 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:

  1. A ∪ B = {x | x ∈ A ∨ x ∈ B}. The union of A and B.
  2. A ∩ B = {x | x∈ A ^ x ∈ B}. The intersection of A and B.
  3. 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:

Venn Diagram Union
A ∪ B is Shaded

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 AB, 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 ABC, 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:

Venn Diagram Intersection
A ∩ B is Shaded

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:

Venn Diagram set difference
A-B is shaded

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:
                                    Ac = {x ∈ U | x ∉ A}

EXAMPLE:

                                    Let       U = {a, b, c, d, e, f, g]

                                                A = {a, c, e, g}

                                    Then    Ac = {b, d, f} 

VENN DIAGRAM FOR COMPLEMENT:

Venn Diagram Complement
A Complement is Shaded

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 Operations

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

Discrete Mathematics MCQS

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:

  1. 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

  1. 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

  1. 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

  1. 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

  1. Recursive definitions can be used in a “_________” manner.

(a) Generative   (b) Non-generative  (c)both a & b.

  1. An integer n is _______ if, and only if n=2k for some integer k.

(a) Even    (b) odd   (c) prime

  1. An integer n is ______ if, and only if n=2k+1 for some integer k.

(a) Even    (b) odd   (c) prime

  1. 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

  1. 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

  1. 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

  1. An integer n is called a perfect _______ if and only if n= for  some integer k.

(a) cube    (b) square  (c) multiple

  1. Square of an even integer is _____ .

(a) Even    (b) odd   (c) both

    1. If a graph is a tree, then its only ________ is itself.

    (a) Rooted tree   (c) Binary tree    (c) Trivial tree

  1. 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.

  1. (a) Minimal rooted     (b) Minimal spanning      (c) minimal  trivial

  1. How many bit strings of length 8 begin and end with 1.

(a) 87     (b) 64    (c) 72

  1. How many three digit integers are divisible by 5.

(a) 140    (b) 160    (c) 180

  1. A k-sample 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

  1. 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) k-permutation   (b) k-selections    (c) k-combinations

  1. With a k-combination the order in which the elements are selected ________ and the elements cannot repeat.

(a) Does matter   (b) does not matter    (c) none

  1. C (n, 0) = __.

(a) 0     (b) 1     (c) 2

  1. C (n, n) = __.

(a) 0     (b) 1     (c) 2 

  1. C (n, 1) = __.

(a) n     (b) n-1      (c) n-2

  1. C (n, 2) =______.

(a) n (n-1)    (b) n (n-2)    (c) n (n-1)/2

  1. C (n, k) = ______ .

(a) n, n-k    (b) n, n-1   (c) n, n-2

  1. C (n, k) + C (n, k+1) = ___________ .

(a)n+1, k+1    (b) n+2, k+2   (c)C(n+1, k+1)

  1. How many 16-bit strings contain at least one 1’s.

(a)45573  (b) 84522   (c) 65535

  1. __________ are similar to k-combinations in that the order in which the elements are selected does not matter, but in this case repetitions can occur.

(a) k-permutation   (b) k-selections    (c) k-combinations

  1. 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

  1. n (AB)= _____________.

(a) n(A) + n(B)      (b) n(A) – n(B) + n(AB)      (c) n(A) + n(B) – n(AB)

  1. 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 co-domain is called _____________ .

(a) sparrowhole principle     (b) pigeonhole principle   (c) logical principle

  1. The theory of probability was first developed in the ______ century when certain gambling games were analyzed by the French mathematician Blaise Pascal.

(a) 16th      (b) 17th      (c) 18th

  1. In the 18th 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

  1. An _________ is a procedure that yields a given set of possible outcomes.

(a) Sample space    (b) Event     (c) Experiment

  1. The __________ of the experiment is the set of possible outcomes.

(a) Sample space    (b) Event     (c) Experiment

  1. An _____ is a subset of the sample space.

(a) Sample space    (b) Event     (c) Experiment

  1. 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)

  1. 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)

  1. 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

  1. A ________ is a non-empty set of points called vertices and a set of lines segments joining pairs of vertices called edges.

(a) Chart    (b) Graph   (c) Diagram

  1. An edge connects either one or two vertices are called its ________.

(a) Incident     (b) Adjacent     (c) Endpoints

  1. An edge with just one end point is called a _______.

(a) Incident   (b) Loop     (c) isolated

  1. Two vertices that are connected by an edge are called ________.

(a) Incident     (b) Adjacent     (c) Endpoints

  1. An edge is said to be _________ to each of its endpoint.

(a) Incident     (b) Adjacent     (c) Endpoints

  1. A vertex on which no edges are incident is called _______.

(a) Incident   (b) Loop     (c) isolated

  1. Two distinct edges with the same set of end point are said to be ________.

(a) Incident   (b) parallel     (c) isolated

  1. A graph G is regular of degree or k-regular if every _______ of G has degree k.

(a) Vertex    (b) Edge     (c) Loop

  1. The complete graph  is ______ regular.

(a) n     (b) (n-1)    (c) (n+1)

  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

  1. 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

  1. A square matrix A=[] of size n×n is called _______ if and only if .

(a) Transpose      (b) symmetric    (c)  Graph

  1. 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

  1. 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

  1. A _____ is a connected graph that does not contain any non-trivial circuit.

(a) Tree     (b) trivial tree    (c) empty tree

  1. A graph that consists of single vertex is a called a _______ .

(a) Tree     (b) trivial tree    (c) empty tree

  1. A tree that does not have any vertices or edges is called an _________.

(a) rooted Tree     (b) trivial tree    (c) empty tree

  1. A graph is called a _______ if and only if it is circuit-free.

(a) rooted Tree     (b) Binary tree    (c) forest

  1. A tree with n vertices has _______ edges.

(a) n       (b) n + 1     (c) n – 1

  1. A tree has no non-trivial 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

  1. A tree is connected but if any edge is _________ from it, then the resulting graph is not connected.

(a) Deleted     (b) subtracted    (c) None

  1. Any tree that has more than one vertex has at least _____ vertices of degree 1.

(a) Two      (b) three     (c) four

  1. A graph is a _____ if there is a unique path between any two of its vertices.

 (a) Binary tree    (b rooted tree    (c) tree

  1. 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

  1. The ______ of a vertex is the number of edges along the unique path between it and the root.

(a) Level      (b) Height    (c) Children

  1. The _________ of a rooted tree is the maximum level to any vertex of the tree.

(a) Level      (b) Height    (c) Children

  1. 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

  1. If w is a child of v, then v is called the _______ of w.

(a) Children   (b) parent    (c) siblings

  1. Two vertices that are both children of same parent are called ______.

(a) Children   (b) parent    (c) siblings

  1. 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

  1. A _________ is a rooted tree in which every internal vertex has at most two children.

(a) Rooted tree   (c) Binary tree    (c) Trivial tree

  1. Every child in a binary tree is designated either a left or right child but ________.

(a) Both     (b) not both     (c) none

  1. A full binary tree is a binary tree in which each internal vertex has exactly ______ children.

(a) Two      (b) Three     (c) Four

  1. 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

  1. Every connected graph has a __________.

(a) Rooted tree   (c) Binary tree    (c) Trivial tree

  1. A graph may have more than ______ spanning trees.

(a) Two      (b) Three     (c) Four

  1. 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:

  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

Symbols

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.

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 :

Truth table for negation logic

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:

Conjunction

DISJUNCTION:


If p & q are statements, then the dis-junction 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:

Disjunction