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

Logical Implication 4

I got stuck while reading the Discrete Mathematics book of Grimaldi. Say there are two primitives. p: I read physics. q: I pass physics. Now consider below lines. (p $\to$ q) $\Leftrightarrow$ ($\neg$p $\lor$ q) which can be read as "I don't…
Madhusoodan P
  • 123
1
vote
2 answers

Confusion about power set

For any set $A$, is $A \in P(A)$, where $P(A)$ is the power set of $A$? I am having trouble figuring this out. The power set of a set is a set of all possible subsets of that set, so $P(A)$ contains all possible subsets of $A$, and $\in$ symbol…
GarudaAiacos
  • 11
1
vote
2 answers

Truth value of a false negation

I'm trying to prove something by negation, and was wondering. For all statements, if their negation can be shown to be false (under one or more circumstances) then is the original statement guaranteed to be true? Or does the negation have to be a…
Howard P
  • 409
  • 4
  • 16
1
vote
1 answer

Show that $g:B\to A$ is a bijection. Show that $g=f^{-1}$.

Let $f:A\to B$ be a bijection for any set A and B. Show there exists $g:B\to A$ which is also a bijection. Show $g=f^-1$. This is what I have done: Proof: Suppose $g(y_1)=g(y_2)$ for some $y_1$ and $y_2$ in B. Since f is surjective, $ \exists$…
Lily
  • 395
1
vote
1 answer

Let A be a totally ordered alphabet. Let L the lexicographic ordering on A*

Let A be a totally ordered alphabet. Let L the lexicographic ordering on A*, and S the standard ordering on A* A / L is well-founded and S is well-founded B/ L is not well-founded and S is well-founded C/ L is well-founded and S is not…
pkim
  • 89
  • 9
1
vote
2 answers

Justify if the following is true/false. $\exists\ $an integer $a$ such that $\forall\ $integers $b$, $a+b=0$.

Indicate whether each of the following statements is true or false and justify your answer. i) $\forall\ $integers$\ $a$, \exists\ $an integer b such that $a+b=0$. ii) $\exists\ $an integer $a$ such that $\forall\ $integers $b$, $a+b=0$. For part…
iamaweed
  • 154
1
vote
1 answer

measure functions for 'chaosity' and 'order' of a sequence

Is there function $f(s)$ to measure "chaosity" of a sequence $s$? For example, sequence $s_1=1,2,3,4,5$ is ordered so $f(s_1)$ equals zero and $s_2 = 3,1,2,5,4$ is not actually ordered but less ordered than $s_3=1,2,3,5,4$, so $f(s_2) > f(s_3)$. Is…
ashim
  • 904
1
vote
0 answers

Partial Order set equation and element

b) Determine whether each of the relations defined below on the set of positive integers is a partial order? (a) (x,y) ϵ R if x = y2 (b) (x,y) ϵ R if x > y (c) (x,y) ϵ R if x y (d) (x,y) ϵ R if x = y (e) (x,y) ϵ R if 3 divides x-y
Robert Quaye
  • 11
1
vote
0 answers

Symmetry of inverse relations

For a homework assignment, we have receive the question: Let A and B be sets and let $R \subseteq A \times B$ be a relation. The inverse relation of R is the subset $R^{-1} = \{\langle b,a \rangle : \langle a,b\rangle \in R\}$. Prove or disprove…
O. Aharoni
  • 11
1
vote
1 answer

Union of Intersections

I am trying to prove that $S\cup(S\cap T)=S$ and the dual statement $S\cap(S\cup T)=S$ for a class, and have gotten stuck with my proof. $$ S\cup(S\cap T) $$ $$ =\{x|x\in S\lor x\in (S\cap T)\} $$ $$ =\{x|x\in S\lor (x\in S\land ]x\in…
Brandon Myers
  • 296
1
vote
1 answer

Karnaugh map. Adjacent rows and columns

I need help about this exercise: Which rows and which columns of a 4 x 16 map for Boolean functions in six variables using the Gray codes 1111, 1110, 1010, 1011, 1001,1000,0000,0001, 0011, 0010, 0110,0111, 0101,0100, 1100, 1101 to label the…
Math Newbie
  • 67
  • 6
1
vote
3 answers

Show equivalence class of equality

How do I show equivalence class of "=" let R={(a,a) such that $a\in$ A}. I know I have to show reflexive, transitive, symmetry properties to show that this relation is an equivalence relation. Reflexive: For all a in A, a=a. proved. Symmetry:…
Lily
  • 395
1
vote
0 answers

Interpret $\mathbb{R}^3$ as a coordinate system

Interpret $\mathbb{R}^3$ as coordinate system. I know coordinate system involves a $x$-axis, a $y$-axis, and a $z$ axis. I also know that $\mathbb{R}^3=\{(x,y,z): x,y,z\in\mathbb{R}\}$. This expressed as a set. But, I have no idea how to express…
Lily
  • 395
1
vote
1 answer

Logical Equivalences

The problem: Prove that $p↔q$ is logically equivalent to $(p∧q)∨(¬p∧¬q)$. Work so far: $p↔q≡(p→q)∧(q→p)$ $≡(¬p∨q)∧(¬q∨p)$ $≡(¬p∨q)∧(p∨¬q)$ by communicative Law My question: I was thinking I could use the distributive law for the final step, but…
OneStepForward
  • 11
  • 2
1
vote
1 answer

discrete math tiling

Suppose we can only use $5$ kinds of tiles to cover a $1 \times n$ board: (1) $1 \times 1$ size with red color, (2) $1 \times 1$ size with blue color, (3) $1 \times 2$ size with black color, (4) $1 \times 2$ size with green color, (5) $1 \times 2$…
Daveo Tran
  • 11
  • 1
1 2 3
…
99
100