Scribd Logo
Upload

Welcome to Scribd!

  • 23 views

    DSTL Paper 2019-20

    Uploaded by

    Dhruv Tomar
    This document contains the questions from a discrete structures and theory of logic exam for a third semester bachelor's of technology degree. There are 7 sections with multiple choice, short answer, and multi-part problems. The questions cover topics like functions, relations, groups, lattices, Boolean algebras, graphs, recurrence relations, logic, and probability. Students are instructed to attempt all questions that showcase their understanding of core discrete mathematics and logic concepts.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    DSTL Paper 2019-20

    Uploaded by

    Dhruv Tomar
    23 views3 pages
    This document contains the questions from a discrete structures and theory of logic exam for a third semester bachelor's of technology degree. There are 7 sections with multiple choice, short answer, and multi-part problems. The questions cover topics like functions, relations, groups, lattices, Boolean algebras, graphs, recurrence relations, logic, and probability. Students are instructed to attempt all questions that showcase their understanding of core discrete mathematics and logic concepts.

    Original Title

    DSTL PAPER 2019-20

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains the questions from a discrete structures and theory of logic exam for a third semester bachelor's of technology degree. There are 7 sections with multiple choice, short answer, and multi-part problems. The questions cover topics like functions, relations, groups, lattices, Boolean algebras, graphs, recurrence relations, logic, and probability. Students are instructed to attempt all questions that showcase their understanding of core discrete mathematics and logic concepts.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    23 views3 pages

    DSTL Paper 2019-20

    Uploaded by

    Dhruv Tomar
    This document contains the questions from a discrete structures and theory of logic exam for a third semester bachelor's of technology degree. There are 7 sections with multiple choice, short answer, and multi-part problems. The questions cover topics like functions, relations, groups, lattices, Boolean algebras, graphs, recurrence relations, logic, and probability. Students are instructed to attempt all questions that showcase their understanding of core discrete mathematics and logic concepts.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)

    B.Tech.
    (SEM. III) ODD SEMESTER
    THEORY EXAMINATION, 2019-20
    DISCRETE STRUCTURES & THEORY
    OF LOGIC
    Time : 3 Hours Max. Marks : 100

    Note : 1. Attempt all Section.

    Section-A

    1. Answer all questions in brief. (2 × 10 = 20)


    a. Define various types of functions.

    b. How many symmetric and reflexive relations are possible


    from a set A containing ‘n’ elements ?

    c. Let Z be the group of integers with binary operation *


    defined by a * b = a + b – 2, for all a, b  Z. Find the identity
    element of the group (Z, *).

    d. Show that every cyclic group is abelian.

    e. Prove that a lattice with 5 elements is not a boolean


    algebra.

    f. Write the contrapositive of the implication: “if it is Sunday


    then it is a holiday”.

    g. Show that the propositions p  q and p  q are logically


    equivalent.

    h. Show that there does not exist a graph with 5 vertices


    with degress 1, 3, 4, 2, 3 respectively.

    i. Obtain the generating function for the sequence 4, 4, 4, 4, 4,


    4, 4.

    j. Define Pigeon hole principle.


    Ans. Refer Q. 5.13, Page SQ–21C, Unit-5, Two Marks Questions.
    Section-B
    2. Answer any three of the following : (3 × 10 = 30)
    SP–2 C (CS/IT-Sem-3) Solved Paper (2019-20)

    1 1 1 1
    a. Prove that + + + ............ + > n for n  2 using
    1 2 3 n
    principle of mathematical induction.

    b. What do you mean by cosets of a subgroup ? Consider the


    group Z of integers under addition and the subgroup
    H = {....., – 12, – 6, 0, 6, 12, .....} considering of multiple of 6
    i. Find the cosets of H in Z.
    ii. What is the index of H in Z.

    c. Show that the following are equivalent in a Boolean


    algebra.
    a  b  a * b = 0  b  a  a  b = 1

    d. Show that ((P  Q)  (QR))  (P Q)  (P R) is


    tautology by using equivalences.

    e. Define planar graph. Prove that for any connected planar


    graph, v – e + r = 2 where v, e, r is the number of vertices,
    edges, and regions of the graph respectively.

    Section-C

    3. Answer any one part of the following : (1 × 10 = 10)


    a. Find the number between 1 to 500 that are not divisible by
    any of the integers 2 or 3 or 5 or 7.

    b. Is the “divides” relations on the set of positive integers


    transitive ? What is the reflexive and symmetric closure of
    the relation ?
    R = {(a, b)|a > b} on the set of positive integers.

    4. Answer any one part of the following : (1 × 10 = 10)


    a. What is ring ? Define elementary properties of ring with
    example.

    b. Prove or dis prove that intersection of two normal


    subgroups of a group G is again a normal subgroup of G.

    5. Answer any one part of the following : (10 × 1 = 10)


    a. Let (L, , , ) be a distribute lattice and a, b  L. If a  b = a
     c and a  b = a  c then show that b = c.

    b. Obtain the principle disjunction and conjunctive normal


    forms of the formula (p  r)  (q  p).
    Discrete Structures & Theory of Logic SP–3 C (CS/IT-Sem-3)

    6. Answer any one part of the following : (1 × 10 = 10)


    a. Explain various rules of inference for propositional logic.

    b. Prove the validity of the following argument “if the races


    are fixed so the casinos are cooked, then the tourist trade
    will decline. If the tourist trade decreases, then the police
    will be happy. The police force is never happy. Therefore,
    the races are not fixed.”

    7. Answer any one part of the following : (7 × 1 = 7)


    a. Solve the following recurrence equation using generating
    function
    G(K) – 7 G(K – 1) + 10 G (K – 2) = 8K + 6

    b. A collection of 10 electric bulbs contain 3 defective ones.


    i. In how many ways can a sample of four bulbs be selected ?
    ii. In how many ways can a sample of 4 bulbs be selected
    which contain 2 good bulbs and 2 defective ones ?
    iii. In how many ways can a sample of 4 bulbs be selected so
    that either the sample contain 3 good ones and 1 defectives
    ones or 1 good and 3 defectives ones ?

    

    You might also like