What is Discrete mathematics: Definition and 106 Discussions
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets (finite sets or sets with the same cardinality as the natural numbers). However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.
Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development of digital computers which operate in discrete steps and store data in discrete bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems, such as in operations research.
Although the main objects of study in discrete mathematics are discrete objects, analytic methods from continuous mathematics are often employed as well.
In university curricula, "Discrete Mathematics" appeared in the 1980s, initially as a computer science support course; its contents were somewhat haphazard at the time. The curriculum has thereafter developed in conjunction with efforts by ACM and MAA into a course that is basically intended to develop mathematical maturity in first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well. Some high-school-level discrete mathematics textbooks have appeared as well. At this level, discrete mathematics is sometimes seen as a preparatory course, not unlike precalculus in this respect.The Fulkerson Prize is awarded for outstanding papers in discrete mathematics.
Homework Statement
Hello.
Here is the question:
Determine whether or not R is some sort of order relation on the given set X.
X = {∅, {∅}, {{∅}} } and R ε ⊆.
I can't seem to figure out why the ordered pairs given are what they are.
Homework Equations
None.
The Attempt at...
Homework Statement
c) Is 'g' a surjective function (onto) ? Justify your answer.
Homework Equations
Let 'f' be a relation on ℤ (the set of integers) , defined by the entrance requirement :
(x;y) ∊ ƒ iff y = x + 15
and let 'g' be the function on ℤ defined by the...
I apologize for the repost, but I had no replies to my previous post. I figured that I didn't put down a good enough attempt of a solution. I will try to explain what I did in more detail. I have read the rules for the forum, but if I'm still doing something wrong, please tell me. I want to...
Homework Statement
Determine the dom(g)
Homework Equations
Let 'f' be a relation on ℤ (the set of integers) , defined by the entrance requirement :
(x;y) ∊ ƒ iff y = x + 15
and let 'g' be the function on ℤ defined by the entrance requirement :
(x;y)...
Homework Statement
Question 1 :
a) Use Venn diagrams to determine whether or not, for all subnets A,B and C of a universal set U, (A-B) ∪ C = (A∪C) - (A∩B)
b) If the statement appears to hold, give a proof, if not, give a counter example.
Homework Equations
(A-B) ∪...
Question 2:
--------------------
Homework Statement
Consider the following sets, where U represents a universal set :
U = {1, 2, 3, 4, ∅, {1}}
A = {1, 3}
B = {{1}, 1}
C = {2 , 4}
D = { ∅ , 1, 2 }
Homework Equations
A+D is the set : (Choose only one )
1. {1, 3}...
Question 1 :
--------------------
Homework Statement
Consider the following sets, where U represents a universal set :
U = {1, 2, 3, 4, ∅, {1}}
A = {1, 3}
B = {{1}, 1}
C = {2 , 4}
D = { ∅ , 1, 2 }
Homework Equations
Choose the correct option : D - B is the set ...
Homework Statement
The Question data is as follows :
Consider the following sets, where U represents a universal set :
U = {1, 2, 3, 4, ∅, {1}}
A = {1, 3}
B = {{1}, 1}
C = {2 , 4}
D = { ∅ , 1, 2 )
Homework Equations
Which one of the following statements is true ?
1. The...
I've been having trouble finding many pure math Ph.D. programs with active research groups in the general field of discrete mathematics (perhaps due to its interdisciplinary nature). I'm only aware of the top schools in this field (e.g. Carnegie Mellon, Georgia Tech, UCSD, Rutgers); can anyone...
Q 1. On a circular island we build n straight dams going from
Sea to sea, so the ever two intersect but no three go through
the same point. Use Euler’s Formula to determine how many
Q 2. Into how many parts do two quadrilaterals divide the plane, If
(a) They are convex
(b) They are not...
Homework Statement
Question 1:
a) Suppose you have brought four pens of different colours to the exam. For each of the ten question on the exam, you choose one pen. In how many ways can this be done?
b) In how many ways can you distribute six bananas and five oranges between three children...
Homework Statement
For every non-negative integer z, z2 - 3z is an even integer. Prove this statement. So far, I have learned about direct proofs and indirect proofs such as contraposition and contradiction.
Homework Equations
An integer z is odd when there is an integer a so that z = 2a+1...
Ok, so I'm having difficulty adapting to subjects like set theory etc.
For example this question:
L.{A,a} = {A, a, b, ab, ba, aba}
Find L
Now, I know the answer but it was a battle getting there. It took me 30 mins before giving up and turning on my PC. I got annoyed so much that...
None of my advanced courses require discrete math as a requisite. In fact, the only course that does explicitly require it is not on my degree plan of operations research. However, is this going to bother me when it comes time for say Real Analysis, Advanced Calc, or Abstract Algebra? I think...
Homework Statement
There are 17 street lamps along a straight street. In order to save electricity and not affect the regular use at the same time, we can shut down 5 of these lamps. But we cannot turn off a lamp at either end of the street, and we cannot turn off a lamp adjacent to a lamp...
Homework Statement
There are 17 street lamps along a straight street. In order to save electricity and not affect the regular use at the same time, we can shut down 5 of these lamps. But we cannot turn off a lamp at either end of the street, and we cannot turn off a lamp adjacent to a lamp...
Discrete Mathematics -- Symmetric Closure Math help in Numerical Analysis, Systems of
I can't seem to find the way to approach this problem. Because it has symbols I don't know how to type here, I have attached an image here instead. Please help me if you can. Any input would be greatly...
Hi, i have studied discrete math and there are topics like linear algebra and analytic geometry and googling i found that there are not in other courses,
what are the topics in your discrete math courses?
Discrete Mathematics - (A∪B)-(A∩B)=(A-B)∪(B-A) - prove by cases??
Hi, I'm new to these forums so please redirect me if I've posted this in the wrong place.
I'm trying to graduate and this is my last class, but as I'm not a math major, I'm really struggling with this particular problem. I've...
Hi all,
I am going to be taking Discrete Mathematics in August and my last Math course was about 5 years ago. I am a little intimidated to just 'jump' back into Math especially a course like this one.
Can anyone who was successful give me a few pointers? I ordered the Textbook and will...
Hi guys! I got really stuck with a Discrete Mathematics homework in Integers and Algorithms.
I know it is not very clear due to lack of symbols. If anyone didn't understand some part of the exercise I would like to clarify it.
The exercise is the following :
Homework Statement
Define for B...
Homework Statement
For all n ∈ Z+, the function Pn of i variables is defined recursively as follows:
Pn(x1,...,xn) = Pn-1(x1 + x2, x2 + x3,...,xn-1 + xn) and P1(x1) = x1.
Find a closed formula for Pn.
Homework Equations
Pn(x1,...,xn) = Pn-1(x1 + x2, x2 + x3,...,xn-1 + xn) and P1(x1)...
Homework Statement
The question is to provide a new composite heuristic h3 that is admissible and dominates h1 and h2. Then show the cost of each of the states through H according to h3.
Homework Equations
States:
A B C D E F G H
h1: 10,12,12,6,7,7,2,10
h2: 8, 9, 14,4,9,7,1,9...
I am starting a maths major and I will going to go into pure maths. I am going to specialize in either analysis or discrete maths. I understand that mathematical analysis has a very strong connection to calculus and that discrete mathematics is used mainly in the cryptography and security...
Ex 36, p 147.
Let f be a function from the set A to the Set B. Let S and T be the subset of A. Show that
b) f(S \cap T) \subseteq f(S) \cap f(T).
Thanks.
Homework Statement
Which is larger, square root of 2 or cubed root of 3? Prove one is larger than the other without using decimal approximations for either number.
The Attempt at a Solution
I attempted to solve this through the contradiction that they were even. If they are not even then...
Apparently everyone uses either Discrete Mathematics and Its Applications by Kenneth H. Rosen or Discrete Mathematics with Applications by Susanna S. Epp. Are these really the best ones? Both are very long texts which make me think they're not rigorous and they're descriptive like Stewart’s...
Homework Statement
Find a formula for when m \sum k=0 the flooring function of[k1/3 ] ,m is a positive integer.
Homework Equations
n\prod j=m aj
The Attempt at a Solution
the flooring function of[k1/3] = K
the summation of K is \frac{m(m+1)}{2}
There's a table of...
Homework Statement
I'm supposed to prove the following. I assume it means that (w,v) and (v,w) don't both belong to f. If they do, then f certainly isn't a single function. For instance take f= x^2. The point (2,4) certainly belongs to f, but the point (4,2) does not. It in fact belongs to...
Hello all,
I am stuck on some homework, basically I am stuck on the problems dealing with proofs. I am not asking for complete answers just any direction would be helpful.
1) I have to prove the Grötzsch graph is not 3-colorable (vertex can be colored in such a way that no edge shares 2...
Hello,
I'm looking for a decent Discrete Mathematics book..
Well,
- Discrete Mathematics & Its Applications.
- Discrete Mathematics With Its Applications.
Are the top-sellers and the top-rated books @ Amazon on this field.
Has anyone read any of them? Recommendations? Pros & Cons? I'm...
Homework Statement
a.)
F = {(1, a), (2, b), (3, a), (4, c)}
G = {(b, 1), (a, 2), (c, 3)}
i. Find F o G
ii. Find G o F
b.)
A function F: N x N --> N is represented 2(m + n) + 1 for F(m, n)
i. Is F one-to-one?
ii. Is F onto?
c.)
Prove by Mathematical Induction...
Homework Statement
Prove that for all integers a >= 1, a^n - 1 is divisible by a - 1 for all n >= 1.
Homework Equations
None.
The Attempt at a Solution
Proof - Let P(n): a^n - 1 is divisible by a - 1, then
P(1): a^1 - 1 is divisible by a - 1 is TRUE since a^1 - 1 = a - 1, and...
Describe an algorithm that takes as input a list of n distinct integers and finds the location of the largest even integer in the list or returns 0 if there are no even integers in the list.
Please Help me on how to solve this type of question I am clueless.
Homework Statement
a 1= 2, a k+1, 2ak-1
Homework Equations
What is the 5th term
The Attempt at a Solution
a1= 2
a2=2(2)-1= 3
a3=2(3)-1=5
a4=2(4)-1=7
a5=2(5)-1=9
5th term =9?
:confused: Construct a formal proof of the theorem:
If (p-> q), (neg [r] -> s), and (neg [q] V neg [s], then (p-> r).
[refer to table of logical equivalences (p62) and the table of logical implication (p62)]The tables are in the textbook Kenneth Ross, 5th edition, Discrete Math's...
I know I have to write an equation to solve the problem down. But I really don't know how to use the given information. I did it by enumeration, but I don't get it how this will be shown by an algebriac argument. Please some one help me at least with an idea.
If S = {1,2,3,4}, consider the...
Dear all,
I have an example taken from the book titled "Discrete Mathematics For Computer Science" by Kenneth Bogart. In the book, page 11, example 1.2-2, it says: Write down all the functions from the two element set {1,2} to the two element set {a,b}.
I couldn't understand the...
Hi,
Im after some advice on what materials to use in order to gain a fairly 'decent' understanding of the following topics:
Elementary Set Theory, Subsets, Unions, Intersections, Complements. Logic, Functions, Mappings, Injectivity. Subjectivity. Bijectivity, Permutations, Proof techniques...
Homework Statement
Find the range of the function g: ZxZ --> ZxZ given by g(m,n)=(m-n,m+n). Hints: First recall that if f: A ---> B then Range (f)={b e B such that there exists an A in A with b=f(a). Second, if you claim that some set C is the range, then you must show that i) C is a subset...
Homework Statement
An electronic switch bank consists of a row of six on - off switches. How many different
settings are possible if exactly three of the switches are set to off?
(a) 12 (b) 144 (c) 60 (d) 30 (e) 20
Homework Equations
Factorial rule...
Homework Statement
A certain state issues a series of automobile license plates such that each license plate
must have 2 letters followed by three digits. An example license plate would be AD 025 .
If the letters and the digits cannot be repeated, how many different license plates can be...
[SOLVED] Propositional logic Discrete Mathematics
Homework Statement
Assuming atleast one of the following statements is true, which one is it? why?
a. Exactly one of these statements is true
b. Exactly two of these statements are true
c. Exactly three of these statements are true
d...
Homework Statement
For all integers m, m^{}2=5k, or m^{}2=5k+1, or m^{}2=5k+4 for some integer k.
Relevant equations
I'm pretty sure we have to use the Quotient Remainder THM, which is:
Given any integer n and positive integer d, there exists unique integers q and r such that...
Homework Statement
Prove the following statement:
For all real numbers x and y, |x| times |y| = |xy|
Homework Equations
I really don't know how to start this as a formal proof.
The Attempt at a Solution
I was thinking I'd have to break it down into four cases and logically prove...
Homework Statement
Suppose a, b, and c are integers and x, y, and z are nonzero real numbers that satisfy the following equations:
xy/(x+y)=a
xz/(x+z)=b
yz/(y+z)=c
Is x rational? If so, express it as a ratio of two integers.
Homework Equations
I substituted a lot of equations...
Geometry and Discrete Mathematics notes?? Resources?
Hello everyone, I'm going to take Geometry and Discrete Mathematics, next year in high school (grade 12). So this summer I'm planning to read some books that would help me out next year, to bulit up my basic skills. So anyone know any sites...
Let \Sigma = { \beta,x,y,z} where \beta denotes a blank, so x\beta \neq x, \beta \beta \neq \beta, and x\betay \neq xy but x \lambday = xy.
Compute each of the following:
1: \parallel \lambda \parallel
2: \parallel \lambda \lambda \parallel
3: \parallel \beta \parallel
4...