Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
1
vote
1 answer

Total number of multiplication of upper triangular matrices

Suppose we have to square upper triangular matrices that we want to multiply using the following code: The question is to find the total number of multiplications. I noticed that every time the number of multiplications get decreased by 1 in each…
Avv
  • 1,159
1
vote
1 answer

Im being asked to define a bijection from the set of natural numbers including zero

Im being asked to define a bijection from the set of natural numbers including zero of non negative integers to the set of natural numbers. Then prove that the function is surjective and injective. So far I tried creating a piece wise equation…
Sultan Oloyede
  • 11
1
vote
2 answers

Question on Relations

Each of the following defines a relation on the positive integers $\mathbb{N}$: 1-) "$x$ is greater than $y$", 2-) "$xy$ is the square of an integer", 3-) $x$ + $y$ = $10$, 4-) $x$ + $4y$ = $10$ Determine which of the following relations are (a)…
Sonny Jordan
  • 276
1
vote
1 answer

Solving $n! = 10^9$

What is the largest $n\in \mathbb{R}$ for which one can solve within one second a problem using an algorithm that requires $f (n)$ bit operations, where each bit operation is carried out in $10^−9$ seconds, with $f (n) = n!$? The number of bits…
Avv
  • 1,159
1
vote
3 answers

Determine if relation $P: R^+ \rightarrow R$ is a function, $(x, y) \in P$ means that $x = y^2$

I am self studying discrete mathematics using the book Discrete Mathematics with Applications (Epp, 4e international version) and I have been stuck trying to figure out the answer to the below question (pg. 22, question 11) Define a relation $P$…
laroygreen
  • 13
  • 3
1
vote
1 answer

Prove,that there exists bijection between the sets $\{0,1\}^*$ and $\{0,1,2\}^*$

Should I show, that both of the sets are countable by mapping initial words to natural numbers?
Tabris
  • 53
1
vote
1 answer

Big-$\mathcal{O}$ of the number of comparisons and multiplications needed

The number of comparisons and multiplications for the following algorithm should be: $$\sum_{i=1}^{n}(n-i)\times 2$$ 2 as the amount of operations for multiplication is same as for comparisons. Question: But the solution I found claims that it's…
Avv
  • 1,159
1
vote
1 answer

people liars or trustworthy

I have a visitor that meets A and B.We have trustworth and liars. A declares that he is like B. B declares that one of them is only trustworth. So I have solved this exercise with truth table A: trustworthy so p B: trustworthy so q (cause he is…
ek.Sek
  • 497
1
vote
1 answer

two-member relationship R maths

I have $A=\{a,b,c,d\}$ and we have the two-member relationship : $R=\{(a,a),(a,c),(c,c),(c,b),(b,b),(a,d),(d,d),(b,d)\}$ is it $R$ partial order? is any way that I can solve it and give me the right answer?
ek.Sek
  • 497
1
vote
1 answer

How to simplyfy the expression ${(m+k-1 \text{ mod } k) + 1}$?

$m$ takes values from 1 to an even number $M$ and $k = M/2$. This expression ${(m+k-1 \text{ mod } k) + 1}$ gives the repeated sequence of numbers from 1 to k. How can I further simply the expression to give the same repeated sequence? For example M…
Salwa
  • 67
1
vote
1 answer

Use of rank theorem

Let $$|rank(P)-rank(Q)|^2=(rank(P)-rank(Q))^2=rank(P)^2-2(rank(P))(rank(Q))+rank(Q)^2$$ $$|rank(P)-rank(Q)|^2\le |rank(P)|^2+2|rank(P)||rank(Q)|+|rank(Q)|^2$$ $$|rank(P)-rank(Q)|^2\le |rank(P)|+|rank(Q)|$$ Since, $rank(P)\ge 0$ and $rank(Q)\ge…
user850289
1
vote
1 answer

Proof that it is a ring - new operations

Let {K,+,*} be commutative ring with unit. Define new operations ¤ and o so x¤y=x+y-1 and xoy=x+y-xy. Show that {K,¤,o} is a ring. How can I show that the opeartions are closed for K? How can I show that x+y-1 belongs to K and x+y-xy belongs to K? I…
Erika
  • 387
1
vote
1 answer

Reflexive, $s$, $t$ relations

$A=\{1,2,3,4\}$. Determine with reasons whether $R$ is reflexive, symmetric or transitive. $R=\left\{(1,1),(1,2),(2,1),(2,2)\right\}$ How is this done? Reflexive must contain every element to itself. Therefore it is not reflexive as there is no…
Michael
  • 11
1
vote
0 answers

Is there a mathematical construct that expresses the change of value of a propositional variable A over time?

Is there a mathematical construct that expresses the change of value of a propositional variable A over time? For example: A refers to "Man is mortal", but let's say after time x A now refers to "Some men are mortal" which are both true at their…
Sayaman
  • 303
1
vote
1 answer

Proving a relation R is not a function

I'm working on this basic discrete math question and struggling to understand the notation, We have a relation $R$ on $Z^+$ defined as follows: $mRn$ if and only if $m|n$ Explain why the relation R is not a function Let $A$ and $B$ be nonempty…
Bobby B
  • 419
1 2 3
…
99 100