Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Discrete Mathematics Part B Solutions

    Uploaded by

    wotohe5000
    DM SOLUTUIONS

    Copyright:

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

    Discrete Mathematics Part B Solutions

    Uploaded by

    wotohe5000
    13 views2 pages
    DM SOLUTUIONS

    Original Title

    Discrete_Mathematics_Part_B_Solutions

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    DM SOLUTUIONS

    Copyright:

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

    Discrete Mathematics Part B Solutions

    Uploaded by

    wotohe5000
    DM SOLUTUIONS

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Discrete Mathematics Part B Solutions

    Question 1: Use quantifiers to express the statement that "There does not exist a woman who has taken a flight on every airline in
    Answer 1: Statement: There does not exist a woman who has taken a flight on every airline in the world.
    Solution: Not (there exists a woman (w) in the set of women (W) such that for all airlines (a) in the set of airlin
    Mathematically: not exists w in W for all a in A TakenFlight(w, a)
    Where:
    W is the set of all women.
    A is the set of all airlines.
    TakenFlight(w, a) denotes that woman w has taken a flight on airline a.

    Question 2: Show that the following set of premises are inconsistent P → Q, P → R, Q → ¬R, P
    Answer 2: Premises:
    1. P -> Q
    2. P -> R
    3. Q -> not R
    4. P
    Solution:
    To show that these premises are inconsistent, we need to derive a contradiction.
    From P, and P -> Q, we get Q.
    From P, and P -> R, we get R.
    From Q, and Q -> not R, we get not R.
    This gives us both R and not R, which is a contradiction. Therefore, the premises are inconsistent.

    Question 3: Define a function. List all possible functions from X = {a, b, c} to Y = {0, 1} and indicate whether each function is one-to
    Answer 3: A function f: X -> Y assigns each element of X to exactly one element of Y.
    Possible functions:
    1. f1(a) = 0, f1(b) = 0, f1(c) = 0
    2. f2(a) = 0, f2(b) = 0, f2(c) = 1
    3. f3(a) = 0, f3(b) = 1, f3(c) = 0
    4. f4(a) = 0, f4(b) = 1, f4(c) = 1
    5. f5(a) = 1, f5(b) = 0, f5(c) = 0
    6. f6(a) = 1, f6(b) = 0, f6(c) = 1
    7. f7(a) = 1, f7(b) = 1, f7(c) = 0
    8. f8(a) = 1, f8(b) = 1, f8(c) = 1
    Injective (One-to-One): None of these functions are injective as the domain has more elements than the cod
    Surjective (Onto): Only f2, f3, f4, f6, f7 are surjective.
    Bijective (One-to-One Onto): None of these functions are bijective.

    Question 4: Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, transitive, and/o
    (a) x + y = 0
    (b) x = ± y
    Answer 4: Relation R on the set of all real numbers:
    (a) x + y = 0
    Reflexive: A relation R is reflexive if (x, x) in R for all x. Since x + x = 2x not equal 0 for all x not equal 0, R is
    Symmetric: A relation R is symmetric if (x, y) in R implies (y, x) in R. Since x + y = 0 implies y + x = 0, R is sy
    Antisymmetric: A relation R is antisymmetric if (x, y) in R and (y, x) in R implies x = y. Since x + y = 0 and y +
    Transitive: A relation R is transitive if (x, y) in R and (y, z) in R implies (x, z) in R. Since x + y = 0 and y + z =
    Asymmetric: A relation R is asymmetric if (x, y) in R implies (y, x) not in R. Since R is symmetric, it cannot be
    (b) x = plus or minus y
    Reflexive: x = x, hence reflexive.
    Symmetric: If x = plus or minus y, then y = plus or minus x, hence symmetric.
    Question 5: Solve the recurrence relation a_n - 7a_{n-1} + 10a_{n-2} = 0 for n ≥ 2 using generating functions.
    Answer 5: Using generating functions:
    A(x) = sum(a_n * x^n, for n=0 to infinity)
    a_n = r^n
    The characteristic equation:
    r^2 - 7r + 10 = 0
    Solving:
    (r - 5)(r - 2) = 0 implies r = 5, r = 2
    The general solution:
    a_n = A * 5^n + B * 2^n
    Using initial conditions to find A and B.

    Question 6: Explain Generating function and explain various operation on generating function.
    Answer 6: A generating function is a formal power series in which the coefficients correspond to terms in a s
    G(x) = sum(a_n * x^n, for n=0 to infinity)
    Operations:
    Addition: G(x) + H(x) = sum((a_n + b_n) * x^n, for n=0 to infinity)
    Multiplication by a scalar: c * G(x) = sum((c * a_n) * x^n, for n=0 to infinity)
    Differentiation: G'(x) = sum(n * a_n * x^(n-1), for n=1 to infinity)
    Integration: int G(x) dx = sum((a_n * x^(n+1)) / (n+1), for n=0 to infinity)

    Question 7: Let X be a random variable on a sample space S such that X(s) ≥ 0 for all s ∈ S. Show that P(X(s) ≥ a) ≤ E(X)/a for ev
    Answer 7: Using Markov's inequality:
    P(X >= a) <= E(X) / a

    Question 8: What is the concept of Bayes theorem with example?


    (b) What is the expected value of a discrete random variable, and how is it calculated?
    Answer 8: Bayes Theorem:
    P(A|B) = (P(B|A) * P(A)) / P(B)
    Example: Medical testing.
    Expected Value:
    E(X) = sum(x * P(X = x), for all x)

    Question 9: What is the chromatic number of the following


    (i) C_4 (ii) K_4 (iii) K_{m,n} (iv) tree with n vertices
    Answer 9: Chromatic Number:
    (i) C_4: 2
    (ii) K_4: 4
    (iii) K_{m,n}: 2
    (iv) Tree with n vertices: 2

    Question 10: Explain Kruskal’s algorithm to find minimal spanning tree of a graph with suitable example.
    Answer 10: Kruskal's Algorithm:
    1. Sort all edges in non-decreasing order of their weight.
    2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If not, include it in th
    Example:
    1. Graph with vertices and edges.
    2. Apply the algorithm step-by-step.

    You might also like