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
2
votes
0 answers

$\sum_{i=1}^n \prod_{j \neq i} \frac{1}{x_j-x_i}$

Is it true that $\sum_{i=1}^n \prod_{j \neq i} \frac{1}{x_j-x_i} = 0$ for distinct $x's$? I tried for $n=1,2,3,4,5$ and these are true. But I cannot generalize it for natural number $n$. I just tried mathematical induction, but it was also…
2
votes
5 answers

Proving statement $(A \cup C)\setminus B=(A\setminus B)\cup C \iff B\cap C= \varnothing$

I want to prove the following statment: $$(A \cup C)\setminus B=(A\setminus B)\cup C \iff B\cap C= \varnothing$$ Do I need to prove each side? Or is one side enough? I mean, if I get from the left side to the right is it enough? How do the following…
Ofir Attia
  • 3,136
2
votes
2 answers

Associative Laws

Associative laws: $\begin{align}(p\lor q)\lor r&\equiv p\lor(q\lor r)\\(p\land q)\land r&\equiv p\land(q\land r)\end{align}$ Just curious is $(r\land p)\land q$ also the same as $(p\land q)\land r$? Like are there $3$ options here because I'm only…
2
votes
2 answers

Number of arrangement of the word JANUARY such that N is before Y and no two vowels are next to eachother

My attempt to the question is no vowel next to eachother: 4!/2!*(6P3)/2!. How do I find that N is left to Y?
noname
  • 27
2
votes
0 answers

Which statements using quantifiers is true?

I have a task here with the expression $(m|p^n-n)$ and some quantifiers in front, where I need to pick the one that is true. The universal set is ${R}$. Edit: I read wrong, universal set is $(2,3,4...)$. The four options…
2
votes
1 answer

Need helping solving this reflexive, symmetric, and transitive closure question

I'm working on a sample exam with no solutions and I've googled examples of similar problems but can't understand them either. Can someone show me a clear cut way to solve this problem: Let R be a relation on { a,b,c,d,e } defined by R = { ( a,c )…
Goose
  • 245
2
votes
1 answer

Problem involving demonstration technique with integer $≥ 0$, such that $n2+n$ is divisible by $2$

I'm learning about discrete math, more precisely about demonstration techniques. The thing is, I'm not always sure if I'm doing it the right way, I don't want to trust my intuition because maybe I'm doing it the wrong way. So I would like to know if…
Bah Soh
  • 111
2
votes
2 answers

Simple set theory question with empty elements

Very simple question, I prob look like an idiot lol. but hey, I'm here to learn so if I have a set A where A = {$a∈ℕ$ | $a^2 = 5$} is set A then A = ∅ or is it A = {∅}? also, if it's the latter, if I have set B say B = {1, 2, 3} and want to find the…
2
votes
0 answers

Inequality induction

I don't know how to go on from here. This is what I have done so far minus the base case which is trivial. Prove by induction the inequality: $n^{n-3}\geq n!$ for $n\geq 9$ the hypothesis: $j^{j-3}\geq j!$ for $j\geq 9$ the claim wit the induction…
2
votes
1 answer

Ore's theorem & Contraposition

This is a question about contraposition i.e. if P implies Q then it is logically equivalent to not Q implies not P (~Q implies ~P) What is wrong with the following taken from Graph Theory? Let G be a (finite and simple) graph with n ≥ 3 vertices. We…
Dan317
  • 123
2
votes
1 answer

Is $( (\lnot p \lor q ) \lor ( p \lor r ) )$ equivalent to $( \lnot p \lor q \lor p \lor r )$?

Determine whether $( p \land q ) \to ( p \lor ( q \land r ) )$ is tautology or not. In line 5 of my given picture can I write this $( (\lnot p \lor q ) \lor ( p \lor r ) )$ as $( \lnot p \lor q \lor p \lor r )$ If yes then what is this rule…
2
votes
2 answers

Why does the Tower of Hanoi problem take $2^n - 1$ transfers to solve?

According to http://en.wikipedia.org/wiki/Tower_of_Hanoi, the Tower of Hanoi requires $2^n-1$ transfers, where $n$ is the number of disks in the original tower, to solve based on recurrence relations. Why is that? Intuitively, I almost feel that it…
David Faux
  • 3,425
2
votes
2 answers

False implies anything

I understand Implication, as follows: p = rain stopped. q = i go out. p->q = if "rain stopped" then "i go out". p q …
user366312
  • 1,641
2
votes
1 answer

Proof that there there is no method to divide students into 3 groups

There are 10 students in a class: Michael Michelle Jack Daniel James Jane Tom Thompson Chris Tracy These are the pairs that like to talk together in class: Michael - Michelle Michael - Jack Michael - Daniel Michelle - James Michelle - Jane Jane -…
Kain
  • 155
2
votes
1 answer

arrange numbers into 3 groups (by sum) in an ordered list

I am looking for a way to group numbers into 3 groups, which each group has a sum as close to others as possible. And the order of original list is preserved. For example , here is a list: 5,7,2,4,3,10 I should group them into (5,7) (2,4,3)…
Reed
  • 123