Discrete Math Problems and Solutions

Posted on Dec 24, 2024 in Social sciences

Truth Values of Compound Statements

Let p and q be propositions with truth values ‘True’ and ‘False’ respectively. Find the truth value of the compound statement (pVq) ^ ~q.

Solution:

  1. Truth Value of Compound Statement

Given: p = True, q = False

  • ~q = True (negation of False is True)
  • (pVq) = True (since p is True)
  • (pVq) ^ ~q = True ^ True = True

Diagraph of a Set

Consider the set A= {1,3,5,7} with a relation r defined on A as r = {(1,1), (3,5),(5,7), (7,5)}. Draw the diagraph of A.

Solution:

The diagraph of A is:

  • 1 → 1
  • 3 → 5
  • 5 → 7
  • 7 → 5

Symmetric but Not Reflexive Relation

Give an example of a relation on the set A = {1, 2} which is symmetric but not reflexive.

Solution:

An example of a relation on the set A = {1, 2} which is symmetric but not reflexive is:

R = {(1, 2), (2, 1)}

Solving a Recurrence Relation

Find a2 if the sequence {an} is defined by the recurrence relation an – 2an-1 = 0, a0 = 1.

Solution:

Given the recurrence relation an – 2an-1 = 0, a0 = 1.

To find a2, we need to find a1 first.

  • a1 – 2a0 = 0
  • a1 – 2(1) = 0
  • a1 = 2

Now, find a2:

  • a2 – 2a1 = 0
  • a2 – 2(2) = 0
  • a2 = 4

Transitive Relation Definition

A transitive relation is a relation R on a set A such that for all a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Symbolic Logic

Write the following statements in symbolic form.

  1. “If Maria learns discrete mathematics, then she will find a good job.”
  2. “The automated reply cannot be sent when the file system is full.”

Solution:

  1. Let p = “Maria learns discrete mathematics”

    q = “Maria will find a good job”

    The symbolic representation is: p → q

  2. Let r = “The automated reply can be sent”

    s = “The file system is full”

    The symbolic representation is: s → ¬r

Solving Another Recurrence Relation

Solve the following recurrence relation: an-3an-1+2an-2 = 0.

Solution:

Given the recurrence relation: an – 3an-1 + 2an-2 = 0

To solve this, we can use the characteristic equation method.

Domain and Range of a Relation

Let R be a relation defined as R= {(-2,1), (-1,-1), (0,1), (-1,1)}. Find the domain and range of the relation R. Then determine whether the relation R is a function.

Solution:

Given the relation R = {(-2, 1), (-1, -1), (0, 1), (-1, 1)}

  • Domain of R = {-2, -1, 0}
  • Range of R = {-1, 1}

R is not a function because (-1, -1) and (-1, 1) have the same x-value but different y-values.

QUAD Countries and Top Economies

A set of QUAD countries = {USA, India, Australia, Japan} and B = set of top five economies = {USA, China, Japan, Germany, India}. Find the QUAD countries which are among the top five economies. Also, find the countries which are QUAD countries OR are in the top five economies.

Solution:

A = {USA, India, Australia, Japan}

B = {USA, China, Japan, Germany, India}

  • A ∩ B = {USA, Japan, India}
  • A ∪ B = {USA, India, Australia, Japan, China, Germany}

Finite Set Definition

A finite set is a set with a finite number of elements.

Example: A = {1, 2, 3, 4, 5} is a finite set with 5 elements.

Logical Equivalence Proof

Prove that the following statements are logically equivalent: p→q= ~p V q.

Solution:

To prove that p→q = ~p V q, we can use a truth table:

pqp→q~p~p V q
TTTFT
TFFFF
FTTTT
FFTTT

From the truth table, we can see that p→q and ~p V q have the same truth values for all possible combinations of p and q.

Matrix of a Relation

Let R be the relation on the set {1, 2, 3, 4} defined by ‘x R y if and only if y=x+1′. Write the matrix of R. Check whether R is a reflexive relation. Also, check whether R is a symmetric relation.

Solution:

Given the relation R on the set {1, 2, 3, 4} defined by ‘x R y if and only if y=x+1′:

The matrix of R is:

1234
10100
20010
30001
40000

R is not reflexive because the diagonal elements of the matrix are not all 1.

R is not symmetric because the matrix is not symmetric about the diagonal.

Bit Strings for Subsets

Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is, ai = i. What bit strings represent the subset of all odd integers in U, the subset of all even integers in U?

Solution:

Given U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, the bit strings for the subset of all odd integers in U is:

1 0 1 0 1 0 1 0 1 0

The bit strings for the subset of all even integers in U is:

0 1 0 1 0 1 0 1 0 1

Symbolic Form and Negation

Write the following statements in symbolic form. Also, negate each of them.

“Every student in this class is learning Python. If Ajay is a student of this class, then Ajay is learning Python.”

Solution:

Let p = “x is a student in this class”

q = “x is learning Python”

r = “Ajay is a student of this class”

The symbolic representation of the statements is:

  1. ∀x (p(x) → q(x))
  2. r → q(Ajay)

Negation of each statement:

  1. ∃x (p(x) ∧ ¬q(x))
  2. r ∧ ¬q(Ajay)

Solving a Recurrence Relation with Initial Conditions

Solve the given recurrence relation: an + 3an-1 + 2an-2 = 0; a0 = 0, a1 = 2.

Solution:

Given the recurrence relation: an + 3an-1 + 2an-2 = 0

a0 = 0, a1 = 2

To solve this, we can use the characteristic equation method.

The characteristic equation is:

x2 + 3x + 2 = 0

Factoring the quadratic equation:

(x + 1)(x + 2) = 0

Solving for x:

x = -1 or x = -2

The general solution is:

an = A(-1)n + B(-2)n

Using the initial conditions a0 = 0 and a1 = 2:

  • A + B = 0
  • -A – 2B = 2

Solving the system of equations:

  • A = -2
  • B = 2

The final solution is:

an = -2(-1)n + 2(-2)n