Discrete Mathematics Help

[Wesley]

I'm finding my math class a bit tricky and was wondering if anyone could help.

Here's my problem:

True or False: For each of the following statements, determine whether the statement is true or false and then prove your assertion. That is, for each true statement, please supply a proof, and for each false statement, present a counterexample (with explanation).
In the following, A, B, and C denote sets.
a.) A-(B-C)=(A-B)-C.
b.) (A-B)-C=(A-C)-B.
c.) (A∪B)-C=(A-C)∩(B-C).
d.) If A=B-C, then B=A∪C.
e.) If B=A∪C, then A=B-C.
f.) |A-B|=|A|-|B|.
g.) (A-B)∪B=A.
h.) (A∪B)-B=A.

Simply stating why each is true or false would be fine. Explanations always help, however.

This may become a periodical thread. Thanks for the help.

[King Harold]

Don't trust me too much on this..

a.) A-(B-C)=(A-B)-C. false (ex. (B∩C)⊆A)
b.) (A-B)-C=(A-C)-B. true
c.) (A∪B)-C=(A-C)∩(B-C). false (ex. |B|=0 and |A-C| > 0)
d.) If A=B-C, then B=A∪C. true?
e.) If B=A∪C, then A=B-C. true?
f.) |A-B|=|A|-|B|. hell no, very false (ex. |A|=|B| and A-B=A)
g.) (A-B)∪B=A. false (ex. |B-A| > 0)
h.) (A∪B)-B=A. false (ex. |B-A| > 0)

[Wesley]

The professor showed us in class today. All are false except b.).

[King Harold]

Good to know that only ones I didn't get right were the ones I doubted

[kv83]

I'm really wondering how example "a" can be "true". It should be false, as Harold said.

[Wesley]

I'm really wondering how example "a" can be "true". It should be false, as Harold said.

Look at what I said again. Only b.) is true.

[kv83]

I'm really wondering how example "a" can be "true". It should be false, as Harold said.

Look at what I said again. Only b.) is true.

Oooooh. I thought you ment that all answers except answer b of Harold were false

[Wesley]

Here are a couple more.

Code: Select all

13.1 For each of the following relations defined on the set {1, 2, 3, 4, 5}, determine whether the relation is reflexive, irreflexive, symmetric, antisymmetric, and/or transitive.
	a. R={(1,1),(2,2),(3,3),(4,4),(5,5)}.
	b. R={(1,2),(2,3),(3,4),(4,5)}.
	c. R={(1,1),(1,2),(1,3),(1,4),(1,5)}.
	d. R={(1,1),(1,2),(2,1),(3,4),(4,3)}.
	e. R={1,2,3,4,5}×{1,2,3,4,5}.

Where a. is "reflexive, symmetric, antisymmetric, transitive", and b. is "irreflexive, antisymmetric".

Code: Select all

14.1 Which of the following are equivalence relations?
	a. R={(1,1),(1,2),(2,1),(2,2),(3,3) } on the set {1, 2, 3}.
	b. R={(1,2),(2,3),(3,1) } on the set {1, 2, 3}.
	c. | on Z.
	d. ≤ on Z.
	e. {1,2,3}×{1,2,3} on the set {1,2,3}.
	f. {1,2,3}×{1,2,3} on the set {1,2,3,4}.
	g. Is-an-anagram-of on the set of English words. (For example, STOP is an anagram of POTS because we can form one from the other by rearranging its letters.)

Where a. is "Yes", f. is "No", and g. is "Yes".

Code: Select all

14.5 For each equivalence relation, find the requested equivalence class.
	a. R={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)} on {1,2,3,4}. Find [1].
	b. R={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)} on {1,2,3,4}. Find [4].
	c. R is has-the-same-tens-digit-as on the set {x∈Z∶100<x<200}. Find [123].
	d. R is has-the-same-parents-as on the set of all human beings. Find [you].
	e. R is has-the-same-birthday-as on the set of all human beings. Find [you].
	f. R is has-the-same-size-as on 2^({1,2,3,4,5}). Find [{1,3}].

Where a. is "[1]={1, 2}", and e. is "[you] is the set containing all people born on your birthday".

The given statements are hints and answers, given from the textbook.

[Wesley]

Man, good thing I'm not putting up all of my homework problems. Don't worry about the ones I posted previously. Also, don't worry about trying to answer all of my questions, answering one is helpful enough. Here are the next few:

Code: Select all

15.11 Twenty people are to be divided into two teams with ten players on each team. In how many ways can this be done?

NOTE: If six people are to be divided into two teams with three players on each team, there are 10 ways this can be done.

Code: Select all

15.16 Let A be a set and let P be a partition of A. Is it possible to have A=P?

NOTE: It is possible, find the set A.

Code: Select all

16.1 Mixed Matched Marvin has a drawer full of 30 different socks (no two are the same). He reaches in and grabs two. In how many different ways can he do this? Now he puts them on his feet (presumably, one on the left and the other on the right). In how many different ways can he do that?

NOTE: The second answer is twice the first.

Code: Select all

16.7 In how many different ways can we partition an n-element set into two parts if one part has four elements and the other part has all the remaining elements?

If you are even bothering to look at this, I much appreciate it.

[benryves]

Code: Select all

15.11 Twenty people are to be divided into two teams with ten players on each team. In how many ways can this be done?

NOTE: If six people are to be divided into two teams with three players on each team, there are 10 ways this can be done.

This one looks a little out of place, so apologies if I'm missing something here. I was never any good at maths.

If you have twenty people and choose ten for a team, that's 20 nCr 10 = 184,756 possible combinations (the remaining ten people you haven't chosen form the other team).

However, let's say we go back to the six people and teams of three example, one combination would return ABC and you'd use DEF as the other team, and another combination would return DEF and you'd use ABC as the other team. These are both effectively the same, so you need to divide the result by two - there are only 92,378 combinations.

((6 nCr 3)/2 = 10 as per your example).

Code: Select all

16.1 Mixed Matched Marvin has a drawer full of 30 different socks (no two are the same). He reaches in and grabs two. In how many different ways can he do this? Now he puts them on his feet (presumably, one on the left and the other on the right). In how many different ways can he do that?

NOTE: The second answer is twice the first.

The first half deals with combinations, 30 nCr 2 = 435 combinations. The second half deals with permutations, 30 nPr 2 = 870. Use combinations when you don't care about the order, permutations when you do!

[King Harold]

15.16: almost, the partition P can be the set containing only A. But it will never have the same "type" as A since P is a set of non-empty subsets of A - so level of nested sets in P is always 1 more in P than in A. So, it can be so that P = { A }, but whether that means that P = A depends on how strict you are. A may not be empty (if it is, P does not exist)

16.1: 30 * 29, there are 30 ways to draw the first sock and there are 29 ways left to draw the second sock. The second part depends on what exactly they mean, do they mean how many ways there are to put The 2 socks on 2 feet in such that both feet get exactly 1 sock? 2. Or do they mean how many ways there are to put Any 2 of the 30 socks on 2 feet such that both feet get exactly 1 sock? 30 * 2 * 29 (30 choices for the first foot, 2 choices what feet you put it on, 29 choices for the seconds sock but only 1 foot left)
edit: ok I forgot to account for the fact that the socks may be drawn in any order and they will still be 2 socks, so divide those two answers by 2..

Sadly I don't have clue about the other combinatorial problems, I never was much good at them without writing programs to calculate them on my GR
And I can't actually guarantee that I got any of these 2 answers right

[Wesley]

You guys are dead on with 15.11 and 16.1, I think. Man, I should've thought back to probability and statistics in high school. In this Discrete Mathematics course, they don't use the notation nCr and nPr, so I didn't think about it, but they actually use those for the math of the permutations and without permutations, but they say "repetitions are permitted" and "repetitions are forbidden". This class is such a joke, only pre-calculus is required to take it and I should be in calculus 3 right now .

Now for 15.16, I think you might be getting somewhere, King Harold. But I'm not even sure where to start.

Then, for 16.7, anyone care to give it a try? My book gives hints in the back for a few problems, but for this one it just says "Warning: There's a little trap waiting for you. Be sure you don't step into it."

Again, thanks for the help. I'm gonna need all I can get, since the professor doesn't want to help and the tutors don't understand how to do it .

[King Harold]

Well I can say "some things" about 16.17
For n = 0 through n = 3, the answer is 0 (there is no way to put 4 out of less than 4 items in a set)
For n = 4, there is only 1 way.
For n = 5 there are 5 ways

In general, for n > 3, [draw 4 elements out of n without putting back] / [4 * 3 * 2]
The the first part makes a lot of sense - choose the 4 elements for the first set. The second part is needed because all permutations of that set are the same set.

At least, that is what I think

[Wesley]

King Harold, you are a genius! I think you are correct, of course there is that "Warning" in the back of the book. I wrote out up to n=8 and found that the answer is n nPr 4 n is the number of elements in the set. I don't think you even have to worry about n>3 because 3 nPr n>3 is 0. Thanks for the help. I just hope we didn't step into that trap.

[Wesley]

I have found a solution to all my problems! I will no longer have to gruel everyone with my math. I found out about a website, from my chemistry professor, that has solutions to math, chemistry, engineering, etc. problems in textbooks. The website also has a Q&A Board where you can ask additional questions and get help within minutes from all kinds of people!

What's better is that all of this is free! In order to have some added benefits you can pay a small amount also. But the free membership is good enough. Also, when you are a member you can get what they call Karma Points where you can get points from answering peoples' questions on the Q&A Board and then you can redeem those points for Premium Membership or all kinds of things, like iPods.

Another easy way is to get points is by getting other people interested and getting them to sign up, either as Free Members or Premium Members. If anyone is interested in checking out the site or getting signed up as a Free Member go to Cramster. This address is not the homepage because it allows for me to get credit for referring people who sign up. If you choose to sign up, sign up using a .edu e-mail address because they have the most reliability to Cramster. But a .edu e-mail is not a requirement for signing up.

If you have any questions, feel free to let me know! If anyone doesn't have need of the website, it would be awesome if you signed up anyways because then I could get more points.