Author |
Topic: Discrete Math Help (Read 13392 times) |
|
Wardub
Junior Member
Gender: 
Posts: 130
|
 |
Discrete Math Help
« on: Sep 16th, 2007, 8:12pm » |
 Quote  Modify
|
1. suppose g: A--->B and f: B---> C are both one to one, prove f (o) g what does the little o mean?) i have no idea how to start this.
2. if E is an equivalance equation on A , then prove or give an counter example, E (o) E is an equivalnce on A. Im not even sure what this is asking. i dont really get equivalance equations or sets and relations really, all i know is E are transitive, reflexive and symmetric.
Update: i have a 13 chpt test on monday, im going to post notes on this post, and ask questions and problems on another post in this thread, feel free to discuss terms, Also thanks Thunda for the math type but its to hard to make it look neat.
Symbols:
x A means x is in the set A
A B means all elements in A are in B
 means no elements in a set
Chapter 2: Logical Equivalances
Laws of Logic:
 (p)  p double negation
p  p identity Laws
p  p
ppp Idempotent Laws
pp p
(pq)r p(qr) Associative Laws
(pq) rp(qr)
p q (p q) (qp)
pq (pq)
pq qp
Chapter 4: Rules of Inference
An argument is valid, if you accept all hypothesis are true, then you must accept the truth of a conclusion
R.O.I
1. Modus Ponens: p and p q  q
2. Modus Tollens: q and pq p
3. Hypo Syllogism: pq qr pr
4. Addition: p pq
5. Simplification: pq p
6. Conjunction: p and q pq (this is the example in the book, does anyone have a better one because they look exactly the same, how could this be of any help?
7.Disjunctive Syllogism: pq and p q
Chapter 5: Sets
Set (A,B,...) are collections of objects.
elements are objects that make up the set.
means in the set.
cardinality is the number of distinct elements in a set.
Power set = set of all subsets of a set, empty sets are included as a subset.
|
| « Last Edit: Sep 22nd, 2007, 6:23pm by Wardub » |
 IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #1 on: Sep 16th, 2007, 8:55pm » |
Quote Modify
|
on Sep 16th, 2007, 8:12pm, Wardub wrote:
1. suppose g: A--->B and f: B---> C are both one to one, prove f (o) g what does the little o mean?) i have no idea how to start this.
|
|
fog is nothing but a composite of a function.
Let's say you have a function defined as f(x) = x2 and g(x) = x3
fog(x) = f(g(x))
What this means that x you take belongs to the domain of g and the range belongs to f i.e. fog : A --> C
In order that this exists B should be a subset of B (This is true because they are the same set). Given this let's try to find fog.
we know g(x) = x3
so fog(x) = f(g(x)) = f(x3)
If we take u = x3 then f(u) = u2
Thus f(x3) = (x3)2 = x6 = fog(x)
I hope this gets you started with the concept!!
|
| « Last Edit: Sep 16th, 2007, 8:57pm by Sameer » |
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #2 on: Sep 16th, 2007, 9:38pm » |
Quote Modify
|
ok that makes sense. i also wrote the question sorta wrong, im suppose to prove that fog is one to one, now i understand how to find fog but they didn;t give me f or g just that they were 1-1. Where do i go from here? wait i think i have a start, in my notes it says A to C there is one value (a,c) which i think leads to being only one in the row, bah i dont know, can anyone explain boolean product, or help on the other?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #3 on: Sep 16th, 2007, 11:43pm » |
Quote Modify
|
if a function is one to one, then if every element from the domain (A) maps to exactly one element of the range (B), and vice versa every element from the range (B) is mapped to from exactly one element from the domain (A).
So if for example f(x) = 2x
Then if you know the value of the function, you know the argument, if f(x)=4, then x can only be 2
Compare this with the function x2: if x2=4, then x can be either 2 or -2.
Conversely, if you have f(4), it can only be 8; compare it to  x: 4 could be -2 or 2 (That is if you take as the inverse of 2, often we use it as a function, and take the positive real value.)
So if f and g are one to one, and the range of f and the domain of g are equal, then every element from the domain of A maps to one element from the range of B which maps to one element from the range of C, and conversely. So each element from A maps to exactly one from C and back, i.e. its also a bijection (one to one).
You probably want to put it more formally, in terms of injection and surjection, or in terms of determinism and functionality
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Discrete Math Help
« Reply #4 on: Sep 17th, 2007, 2:05am » |
Quote Modify
|
on Sep 16th, 2007, 8:12pm, Wardub wrote:| 1. suppose g: A--->B and f: B---> C are both one to one, prove f (o) g what does the little o mean?) i have no idea how to start this. |
|
Make a list of what you know. The fact that f and g are injective means, by definition:
(1) If f(b)=f(b'), for some b,b' B, then b=b'
(2) If g(a)=g(a'), for some a,a' A, then a=a'.
Now, what you want to prove is
(3) If f(g(a)) = f(g(a')), then a=a'.
So suppose f(g(a))=f(g(a')). What can you conclude?
Quote:| 2. if E is an equivalance equation on A , then prove or give an counter example, E (o) E is an equivalnce on A. Im not even sure what this is asking. |
|
I don't know what this means either. Maybe it means: define a relation E x E on the set A x A by saying two ordered pairs (a1, a2) and (a1', a2') of AxA are equivalent iff both a1 is equivalent to a1', and a2 is equivalent to a2'.
Quote:| can someone explain Boolean product between matrices? |
|
I'm not familiar with the term. Can you describe it? I can take a guess: in the normal definition of matrix product, if C = AB, then
cij =  k=1m aikbkj.
For a Boolean product, I would guess that you replace all the multiplications with AND, and the addition with OR. So
cij = (ai1b1j) (ai2b2j) ... (aimbmj),
or in terms of 0s and 1s,
cij = MAX( MIN(aik, bkj) : k=1..m).
This is 1 iff aikbkj=1 for some k. In other words, cij=1 if there is some k such that aik=bkj=1, and 0 otherwise.
|
| « Last Edit: Sep 17th, 2007, 3:54pm by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #5 on: Sep 17th, 2007, 3:03am » |
Quote Modify
|
on Sep 16th, 2007, 8:12pm, Wardub wrote:| 2. if E is an equivalance equation on A , then prove or give an counter example, E (o) E is an equivalnce on A. Im not even sure what this is asking. i dont really get equivalance equations or sets and relations really, all i know is E are transitive, reflexive and symmetric. |
|
Transitivity should be enough.
It means that E o E = E
Basically an equivalence relation says which elements are equivalent to each other. And obviously if X is equivalent to Y and Y is equivalent to Z, then X must be equivalent to Z.
Are you given the first order logic expressions for the relations to work with?
i.e. transitivity of R == forall a,b,c (aRb & bRc => aRc)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Discrete Math Help
« Reply #6 on: Sep 17th, 2007, 4:58am » |
Quote Modify
|
http://en.wikipedia.org/wiki/Composition_of_relations
Given this and towr's post above, i think the answer to 2 is complete.
Frankly speaking, this is the first time i heard of composition of relations.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Discrete Math Help
« Reply #7 on: Sep 17th, 2007, 5:21am » |
Quote Modify
|
Me too. And given this definition, it makes sense to investigate boolean matrix products as defined by Eigenray.
|
| « Last Edit: Sep 17th, 2007, 5:21am by Grimbal » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #8 on: Sep 17th, 2007, 10:38am » |
Quote Modify
|
Thanks a lot everyone, i'm starting to understand but I have a long ways to go. As for Boolean product, I believe what Eigenray said is correct, but I don't know what it means. As for doing it in a matrice this is an example in my notes.
1 0 1 0 ___1 0 0 1____1 0 1 1
0 1 0 0 o 0 1 0 0 = 0 1 0 0 sorry my matrices look bad
0 0 1 1____ 0 0 1 0 ____0 0 1 0
The professor says something, about taking the first row and then comparing it with the first column or something? I'm going to ask him after class today how he does it.
Also how do you post the epsilon and other symbols?
Thanks again, i'll probably have quite a few more questions so be sure to stay tuned LOL 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #10 on: Sep 17th, 2007, 11:05am » |
Quote Modify
|
I found a little bit at http://tinyurl.com/ys824j about boolean matrix multiplication; and it's basically as [e]SMQ Eigenray[/e] explained.
And it also makes sense in the context of relations (like the other problems). If you have two sets with a relation between them, then you can use a boolean matrix to represent this relation. If you have aiRbi, then you put a 1 at position i,j of the matrix, otherwise 0.
Now the nice thing about this, is that if you have two relations between A and B and B and C, then you can just multiply the two matrices and you get the relation between A to C (via B), i.e. the composition of the two relations.
The problem with the example you posted earlier, is that the dimensions of the matrices aren't right. The columns of the second matrix is shorter than the rows of the first matrix. And so you can't do what your professor said: take the first column of the second matrix, compare it to the first row of the first matrix, if any 1's agree, put a 1 in the top left position of the third matrix (otherwise 0). Then compare the same column to the second row, if there is a match, put a 1 in the second position of the first column of the third matrix. etc untill you reach the last row; Then take the second column, and repeat (filling the second column of the third matrix) etc
/ 1 0 1 \ / 1 0 0 1 \ / 1 . . . \
| 0 1 0 | o | 0 1 0 1 | = | . . . . |
| 0 0 1 | \ 0 0 1 0 / | . . . . |
\ 1 1 0 / \ . . . . /
/ 1 0 1 \ / 1 0 0 1 \ / 1 . . . \
| 0 1 0 | o | 0 1 0 1 | = | 0 . . . |
| 0 0 1 | \ 0 0 1 0 / | . . . . |
\ 1 1 0 / \ . . . . /
/ 1 0 1 \ / 1 0 0 1 \ / 1 . . . \
| 0 1 0 | o | 0 1 0 1 | = | 0 . . . |
| 0 0 1 | \ 0 0 1 0 / | 0 . . . |
\ 1 1 0 / \ . . . . /
/ 1 0 1 \ / 1 0 0 1 \ / 1 . . . \
| 0 1 0 | o | 0 1 0 1 | = | 0 . . . |
| 0 0 1 | \ 0 0 1 0 / | 0 . . . |
\ 1 1 0 / \ 1 . . . /
(now in larger steps)
/ 1 0 1 \ / 1 0 0 1 \ / 1 0 . . \
| 0 1 0 | o | 0 1 0 1 | = | 0 1 . . |
| 0 0 1 | \ 0 0 1 0 / | 0 0 . . |
\ 1 1 0 / \ 1 1 . . /
/ 1 0 1 \ / 1 0 0 1 \ / 1 0 1 . \
| 0 1 0 | o | 0 1 0 1 | = | 0 1 0 . |
| 0 0 1 | \ 0 0 1 0 / | 0 0 1 . |
\ 1 1 0 / \ 1 1 0 . /
/ 1 0 1 \ / 1 0 0 1 \ / 1 0 1 1 \
| 0 1 0 | o | 0 1 0 1 | = | 0 1 0 1 |
| 0 0 1 | \ 0 0 1 0 / | 0 0 1 0 |
\ 1 1 0 / \ 1 1 0 1 /
|
| « Last Edit: Sep 17th, 2007, 1:19pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #11 on: Sep 17th, 2007, 11:11am » |
Quote Modify
|
Ok thanks a lot I see how it's done now, this helps a bunch.
Thanks for the script link also  just testing
|
| « Last Edit: Sep 17th, 2007, 11:31am by Wardub » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Discrete Math Help
« Reply #12 on: Sep 17th, 2007, 12:18pm » |
Quote Modify
|
on Sep 17th, 2007, 11:05am, towr wrote:
Thanks for the confidence, but I think it was Eigenray who explained.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #13 on: Sep 17th, 2007, 1:21pm » |
Quote Modify
|
on Sep 17th, 2007, 12:18pm, SMQ wrote:| Thanks for the confidence, but I think it was Eigenray who explained. |
|
Doh  
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #14 on: Sep 17th, 2007, 3:59pm » |
Quote Modify
|
Thanks a lot guys, I didn't get homework today, and I only have one class tomorrow so I'm going to be reviewing my notes all day and try to understand it better and see what I don't understand.
One more question for now, would it be OK if I made another thread for notes? I don't know how to make the symbols in word, and my handwriting is a joke. If so where could I possibly make this thread?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #15 on: Sep 18th, 2007, 1:28am » |
Quote Modify
|
on Sep 17th, 2007, 3:59pm, Wardub wrote:| One more question for now, would it be OK if I made another thread for notes? I don't know how to make the symbols in word, and my handwriting is a joke. If so where could I possibly make this thread? |
|
If it's only because Word sucks, and not because you want to discuss them, I'd say it doesn't really have a place on the forum. But if you don't mind discussing them with anyone that's interested, general would probably be the best place.
You could also consider installing MikTex (it's a LaTeX compiler for windows), it allows much nicer formulas than this board. LaTeX is a typesetting standard in mathematical publishing.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #16 on: Sep 18th, 2007, 9:29am » |
Quote Modify
|
Its mainly because Word sucks, but I have no problem discussing with people, I just don't know how much interest there would be? Thanks for the MikTex, I'll just use that, if a lot of other people are going through the same hell I am then i'll post it and we can discuss i guess.
I just installed the MikTex, how do I use it with word? Is there suppose to be a box or something?
|
| « Last Edit: Sep 18th, 2007, 9:48am by Wardub » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #17 on: Sep 18th, 2007, 2:30pm » |
Quote Modify
|
Miktex isn't meant to be used with word. It can be used as a replacement (although it may not be worth the effort unless you need special things like formulas)
You first write your document in the latex markup language using an editor (e.g. notepad). Then you compile this source text using miktex (or any other tex implementation). Which should result in a splendidly looking document.
It may take some getting used to though, especially if you're used to wysiwyg (what you see is what you get) editors. The upside is that you have more control (and with practice it can be faster), the downside you need to compile it before you see the result, and it has a steeper learning curve.
As an example, to get a formula like
you'd write the following in your tex-document:
\[
\int_0^y{\phi(y_0) \over \sqrt{y-y_0} }\,dy_0 =
\int_0^y \int_0^{y_0}{h(u) \over \sqrt{2g(y-y_0)(y_0-u)} }\,du\,dy_0 =
\int_0^y{h(u) \over \sqrt{2g} } \int_u^y{dy_0 \over \sqrt{(y-y_0)(y_0-u)} }\,du
\]
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #18 on: Sep 18th, 2007, 3:35pm » |
Quote Modify
|
Never mind then I think it's a bit to confusing for me. I think for notes ill just add them to my first post, that way people can discuss, and it won't take up more board space
My first post is too long so im continuing my notes on this post
Chapter 6: Set Operations
Intersection  means Elements in both sets
Union  means elements in either set
Exor  means elements in either set but not both.
Complement: complement of B relative to A = B-A everything in A and not in B
Cartesian Product: AxB comprises all ordered pairs from first coordinate A and second B
Chapter 7: Styles of Proof
Direct Proof: hypothesis as steps, last step is the conclusion
Note: a int n = 2k means even
a int n = 2k+1 means odd
Indirect Proof: replace the implication with the contrapositive and prove that instead
Proof by Contradiction: replace proposition(s) r with r
 denotes a fallacy an end of contradiction
Proof by Cases: prove each individual case. ex |N|
 N then prove for N>0 and N 0.
|
| « Last Edit: Sep 22nd, 2007, 8:27pm by Wardub » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #19 on: Sep 22nd, 2007, 4:27pm » |
Quote Modify
|
ok im screwed for this test.
Prove: (pr)q p(qr)
i am getting q(pr) going from the above to q(pr) then that last portion is equal to pq
what am i doing wrong? i dont think my answer is equal to the books answer
|
| « Last Edit: Sep 22nd, 2007, 4:31pm by Wardub » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #20 on: Sep 22nd, 2007, 4:46pm » |
Quote Modify
|
Chapter 3 i understand except for one little thing.
let p(x,y) be x has read y
 xp(x, the great gatsby) i assume in english this means, there is someone who hasn't read the great gatsby? so when there is a negation it only applies to the x and not the y?
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #21 on: Sep 22nd, 2007, 4:59pm » |
Quote Modify
|
on Sep 22nd, 2007, 4:27pm, Wardub wrote:ok im screwed for this test.
Prove: (pr)q p(qr)
i am getting q(pr) going from the above to q(pr) then that last portion is equal to pq
what am i doing wrong? i dont think my answer is equal to the books answer |
|
p q = p' + q
Use this to get your result
L.H.S. = (p r') q'
= (p r')' + q'
= p' + r + q'
R.H.S = p (q r)
= p' + (q r)
= p' + (q' + r)
L.H.S = R.H.S.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #22 on: Sep 22nd, 2007, 5:21pm » |
Quote Modify
|
Thanks Sameer, im really bad at seeing these things, is there a way to solve these better, like get them to their simplest form first or does it just take practice.
show pq and pr qr
I suck at this, i mean i can clearly see that this is a true conslusion but i cant prove it by steps. Wait is this valid
(pp) (qr) and (pp) so (qr)
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #23 on: Sep 22nd, 2007, 6:27pm » |
Quote Modify
|
As far as chapter 5 is concerned i get it all except some properties of the empty set. why is the empty set a subset of every set? What does {\emptyset , {\emptyset }} mean?
one problem i don't get is, Determine the power set of {1,\emptyset , {1}} but how can this have 1 and the empty set and what does {1} mean?
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #24 on: Sep 22nd, 2007, 7:20pm » |
Quote Modify
|
on Sep 22nd, 2007, 5:21pm, Wardub wrote:Thanks Sameer, im really bad at seeing these things, is there a way to solve these better, like get them to their simplest form first or does it just take practice.
show pq and pr qr
I suck at this, i mean i can clearly see that this is a true conslusion but i cant prove it by steps. Wait is this valid
(pp) (qr) and (pp) so (qr)
|
|
Understand the fundamentals. Use diagrams or sentences, whichever helps you understand. If you think p, q, etc. as statements. Let's say
p: It is raining now
q: My car is black
p or q means, It is raining now or my car is black.
p and q means, It is raining now and my car is black.
So lets say p is a false statement and q is a true statement.
p or q will be true (Why?)
p and q will be false (why?).
If you get these fundamentals you go to the next step in reducing the logic down in fundamental logic statements.
You can alternatively think of them as points A and B connected by logic switches
| | p | | | | ---/ --- | | | A-----| | | |----B | | | ---/ --- | | | | q | |
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print