wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Discrete Math Help
        
(Message started by: Wardub on Sep 16^th, 2007, 8:12pm)

Title: Discrete Math Help
Post by Wardub on Sep 16^th, 2007, 8:12pm

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:
xhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifA means x is in the set A
Ahttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gifB means all elements in A are in B
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gifmeans no elements in a set

Chapter 2: Logical Equivalances
Laws of Logic:
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifp double negation
phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbt.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifp identity Laws
phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbf.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifp
phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifp Idempotent Laws
phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifp http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifp
(phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gif(qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr) Associative Laws
(phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifq) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifrhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gif(qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifr)

phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftrightarrow.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif(phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gif(qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifp)
phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq)
phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifqhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifq
2. Modus Tollens: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifq and phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp
3. Hypo Syllogism: phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr
4. Addition: p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq
5. Simplification: phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifp
6. Conjunction: p and q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifq (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: phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifq

Chapter 5: Sets
Set (A,B,...) are collections of objects.
elements are objects that make up the set.
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifmeans 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.

Title: Re: Discrete Math Help
Post by Sameer on Sep 16^th, 2007, 8:55pm

on 09/16/07 at 20:12:49, 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) = x² and g(x) = x³

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) = x³

so fog(x) = f(g(x)) = f(x³)

If we take u = x³ then f(u) = u²

Thus f(x³) = (x³)² = x⁶ = fog(x)

I hope this gets you started with the concept!!

Title: Re: Discrete Math Help
Post by Wardub on Sep 16^th, 2007, 9:38pm

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?

Title: Re: Discrete Math Help
Post by towr on Sep 16^th, 2007, 11:43pm

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 x²: if x²=4, then x can be either 2 or -2.
Conversely, if you have f(4), it can only be 8; compare it to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifx: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif4 could be -2 or 2 (That is if you take http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifas the inverse of ², 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

Title: Re: Discrete Math Help
Post by Eigenray on Sep 17^th, 2007, 2:05am

on 09/16/07 at 20:12:49, 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' http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif B, then b=b'
(2) If g(a)=g(a'), for some a,a' http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif 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 (a₁, a₂) and (a₁', a₂') of AxA are equivalent iff both a₁ is equivalent to a₁', and a₂ is equivalent to a₂'.

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

c_ij = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1^m a_ikb_kj.

For a Boolean product, I would guess that you replace all the multiplications with AND, and the addition with OR. So

c_ij = (a_i1http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifb_1j) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gif (a_i2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifb_2j) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gif... (a_imhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifb_mj),

or in terms of 0s and 1s,

c_ij = MAX( MIN(a_ik, b_kj) : k=1..m).

This is 1 iff a_ikhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifb_kj=1 for some k. In other words, c_ij=1 if there is some k such that a_ik=b_kj=1, and 0 otherwise.

Title: Re: Discrete Math Help
Post by towr on Sep 17^th, 2007, 3:03am

on 09/16/07 at 20:12:49, 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)

Title: Re: Discrete Math Help
Post by TenaliRaman on Sep 17^th, 2007, 4:58am

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

Title: Re: Discrete Math Help
Post by Grimbal on Sep 17^th, 2007, 5:21am

Me too. And given this definition, it makes sense to investigate boolean matrix products as defined by Eigenray.

Title: Re: Discrete Math Help
Post by Wardub on Sep 17^th, 2007, 10:38am

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 ;)

Title: Re: Discrete Math Help
Post by towr on Sep 17^th, 2007, 10:51am

on 09/17/07 at 10:38:15, Wardub wrote:

Also how do you post the epsilon and other symbols?

It's explained here:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1171644142

Title: Re: Discrete Math Help
Post by towr on Sep 17^th, 2007, 11:05am

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 a_iRb_i, 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 /

Title: Re: Discrete Math Help
Post by Wardub on Sep 17^th, 2007, 11:11am

Ok thanks a lot I see how it's done now, this helps a bunch.
Thanks for the script link also http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/x.gif just testing

Title: Re: Discrete Math Help
Post by SMQ on Sep 17^th, 2007, 12:18pm

on 09/17/07 at 11:05:08, towr wrote:

I found a little bit at http://tinyurl.com/ys824j about boolean matrix multiplication; and it's basically as SMQ explained.

Thanks for the confidence, but I think it was Eigenray who explained. ;)

--SMQ

Title: Re: Discrete Math Help
Post by towr on Sep 17^th, 2007, 1:21pm

on 09/17/07 at 12:18:01, SMQ wrote:

Thanks for the confidence, but I think it was Eigenray who explained. ;)

Doh :-[ ;D

Title: Re: Discrete Math Help
Post by Wardub on Sep 17^th, 2007, 3:59pm

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?

Title: Re: Discrete Math Help
Post by towr on Sep 18^th, 2007, 1:28am

on 09/17/07 at 15:59:27, 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.

Title: Re: Discrete Math Help
Post by Wardub on Sep 18^th, 2007, 9:29am

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?

Title: Re: Discrete Math Help
Post by towr on Sep 18^th, 2007, 2:30pm

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
http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?md5=0dfb0d32d8119c23841cd902c6d0cae4
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
\]

Title: Re: Discrete Math Help
Post by Wardub on Sep 18^th, 2007, 3:35pm

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gifmeans Elements in both sets
Union http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cup.gifmeans elements in either set
Exor http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/oplus.gifmeans 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifr http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbf.gif
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif denotes a fallacy an end of contradiction
Proof by Cases: prove each individual case. ex |N|
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifN then prove for N>0 and Nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif0.

Title: Re: Discrete Math Help
Post by Wardub on Sep 22^nd, 2007, 4:27pm

ok im screwed for this test.
Prove: (phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifr)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif(qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr)

i am getting qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif(phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr) going from the above to qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr) then that last portion is equal to phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq

what am i doing wrong? i dont think my answer is equal to the books answer

Title: Re: Discrete Math Help
Post by Wardub on Sep 22^nd, 2007, 4:46pm

Chapter 3 i understand except for one little thing.

let p(x,y) be x has read y

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/exists.gifxhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp(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?

Title: Re: Discrete Math Help
Post by Sameer on Sep 22^nd, 2007, 4:59pm

on 09/22/07 at 16:27:32, Wardub wrote:

p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif q = p' + q

Use this to get your result

L.H.S. = (p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifr') http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifq'
= (p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gifr')' + q'
= p' + r + q'

R.H.S = p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif(q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr)
= p' + (q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr)
= p' + (q' + r)

L.H.S = R.H.S.

Title: Re: Discrete Math Help
Post by Wardub on Sep 22^nd, 2007, 5:21pm

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 phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gifqhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr
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

(phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gif(qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr) and (phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbf.gif so http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gif(qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr)

Title: Re: Discrete Math Help
Post by Wardub on Sep 22^nd, 2007, 6:27pm

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?

Title: Re: Discrete Math Help
Post by Sameer on Sep 22^nd, 2007, 7:20pm

on 09/22/07 at 17:21:35, Wardub wrote:

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

Title: Re: Discrete Math Help
Post by Wardub on Sep 22^nd, 2007, 7:57pm

In your example i understand why the answer is p or q
because p and not p cannot both be true at the same time. which means if both hypothesis are correct. and for example we say p is true then we know r is true. and if p is false we know that q is true. since we don't know p's truth value it is q or r but i have no idea how to go about proving it with steps and rules of inference and junk.

Bah i can do it in my mind, but i can't do it on paper because its more like a branch. If there was a Hypothesis "p" i could do it in a second. I think i have to do something with phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifp'

wait im coming to a conclusion how about
1.http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gifp http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr Hypothesis
2. phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifr
3.phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq Hypothesis
4.rhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifq if p then r, so can you substitute the p for an r?
5.qhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vee.gifr

Chpt 7 questions:
Prove by contradiction that if 5n-1 is odd then n is even. Do i make it if 5n-1 is even then n is odd? and then solve?
how do i go about proving this without just saying it must be an odd number
if 5n-1 is even then n = 2k+1, = 10k -4 = even
2k +1 is odd. so is this enough?

Chapter 8 is making sense i did it on paper because it needed graphs. I have no questions thanks to Towr for explain Boolean Product i finally understand composition S o R i just need to make sure i get the order correct.

Title: Re: Discrete Math Help
Post by Sameer on Sep 22^nd, 2007, 11:05pm

I think you need to get help from a tutor. It is hard helping over a forum!!

Title: Re: Discrete Math Help
Post by towr on Sep 23^rd, 2007, 7:16am

on 09/22/07 at 18:27:45, Wardub wrote:

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?

Because there are no elements in the empty set that aren't in the (super)set.
For any two sets, A is a subset of B, if and only if every element in A is also an element of B. When there are no elements in A, this is trivially true (Because "for-all .." claims over an empty domain are always true. This is related to everything being derivable from absurdity. Because there are no elements there are no elements for which it isn't true, hence it's true for all.)

Quote:

What does {http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif , {http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif ] mean?

That you have a set that contain and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif and it contains a set containing http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif.
Look at each set as a box: you have one large box, containing two smaller boxes. One of these is empty, and the other contains a fourth, smaller, box which is empty.
Visualization and analogies can help a lot (although you should never mistake them for being real; intuition can in some cases lead you astray. But for the moment this works).

Quote:

one problem i don't get is, Determine the power set of {1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif, {1] but how can this have 1 and the empty set and what does {1} mean?

{1} is a set containing the element 1. (Look at it as boxes again: you have a large box, with inside it a '1', an empty box, and a box with a '1')

To find the powerset you don't have to consider what the elements are (it doesn't matter that some of them are sets). Just treat every element as a single object.
There are three distinct elements in our set (1 and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif and {1}); so the powerset must consist of 2³ subsets.
To avoid confusion, let's take a=1, b=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif, c={1}. So then our set is {a,b,c}
This looks easier, but is exactly the same problem; the powerset is (spread over several lines so you can clearly see the eight subsets of {a,b,c} which together form the powerset):
{
{},
{a},
{b},
{c},
{a,b},
{a,c},
{b,c},
{a,b,c}
}

Now we can replace the placeholders a,b,c with the originals again and get
{
{},
{1],
{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif},
[1],
{1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif},
{1, {1],
{ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif, {1],
{1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif, {1]
}

Title: Re: Discrete Math Help
Post by towr on Sep 23^rd, 2007, 7:37am

on 09/22/07 at 19:57:02, Wardub wrote:

Chpt 7 questions:
Prove by contradiction that if 5n-1 is odd then n is even. Do i make it if 5n-1 is even then n is odd? and then solve?
how do i go about proving this without just saying it must be an odd number
if 5n-1 is even then n = 2k+1, = 10k -4 = even
2k +1 is odd. so is this enough?

You have the claim: Odd(5n+1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif Even(n)
To prove by contradiction, means that we assume this claim is false, and then show that this leads to an absurd conclusion. So what is the negation of Odd(5n+1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif Even(n)?
It will be Odd(5n+1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lnot.gif Even(n), that n is (or can be) not-even despite 5n+1 being odd.

If n is not even, then it is odd*); so we have an odd n. 5 is also an odd number, and an odd number times an odd number is odd *); so 5n is odd. 1 is an odd number as well, and adding two odd numbers gives an even number *), therefore 5n+1 is even.
But we started by assuming both that n was odd, and that 5n+1 was odd, clearly 5n+1 can't be both even and odd *). And so here we reach a contradiction: it cannot be true that 5n+1 and n are both odd, so if 5n+1 is odd, n must be even.

*) here I'm taking these claims for granted, but of course in some way they have to follow from the axioms of arithmetic and the definition of "odd" and "even" (if odd numbers are defined as those that are not even, then it follows immediately that a number can't be both; the other two claims follow from modular arithmetic)

Title: Re: Discrete Math Help
Post by Wardub on Sep 23^rd, 2007, 2:35pm

Thanks a lot guys, this is making sense now, I think my main problem is seeing the proofs but i assume that will come. And Sameer, i tried to get a tutor but they didn't have any for this class and it has no TA's im going to ask him after the test if there is anyone he knows that will help me. O and towr that box example really helped me thanks.

im doing the rest of my notes by hand, its easier to do matrices. Im having trouble with what a transitive Matrix would look like, could anyone help. It says a matrix M is transitive if M http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/odot.gif M http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifM. Does that M http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/odot.gifM mean take the boolean product?

Title: Re: Discrete Math Help
Post by towr on Sep 23^rd, 2007, 3:23pm

on 09/23/07 at 14:35:34, Wardub wrote:

im doing the rest of my notes by hand, its easier to do matrices. Im having trouble with what a transitive Matrix would look like, could anyone help. It says a matrix M is transitive if M http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/odot.gif M http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif M. Does that M http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/odot.gif M mean take the boolean product?

I'm fairly sure it does.

Transitivity means that if aRb and bRc then aRc: so you can already get to c from a in one step (i.e. it's in the original matrix)

Title: Re: Discrete Math Help
Post by Wardub on Sep 30^th, 2007, 9:57pm

Hey guys im back again, this time we are proving by induction, and i understand how to prove a sequence is equal to a certain equation. But i had to miss last class and i don't understand how to solve by induction if the thing im solving is not suppose to be equal. Im not sure im making sense right now in writting let me know if you need clarifacation.

1. prove for every int N > 4 that 2^N > N^2

2. prove for every int n > 0 the number n^5-n is a multiple of 5.

I know i need to prove the first the first term is true, then i need to substitute (n+1) for n correct? but in these examples i don't know where i am suppose to go. like if i was proving something was equal, i could make the left side look like the right, but i don't know how i would go about proving something is greater, or a multiple of 5, im really stumped.

Title: Re: Discrete Math Help
Post by Sameer on Sep 30^th, 2007, 10:11pm

For induction three steps

1) Prove for smallest integer n
2) Assume it is true for some integer n = k
3) Prove that using assumption in 2) the equation is true for n = k + 1

Let' take for e.g. your first problem 2ⁿ > n²

Step 1:
For n = 5
2⁵ = 32
5² = 25

So 32 > 25

Step 2:
Assume it is true for some n = k
then 2^k > k²

Step 3:

L.H.S = 2^k+1
= 2^k . 2
> k² . 2
= k² + k²
> k² + 2k + 1 (because k² > 2k + 1 (why? - you should probably try to prove this)
= (k+1)²

Thus by induction ... 2ⁿ > n² for n > 5

see how in step 3. how I need to prove 2^k+1 > (k+1)² so I adjusted terms to get the RHS... hope this helps.

Title: Re: Discrete Math Help
Post by Wardub on Sep 30^th, 2007, 10:29pm

yes that helps quite a bit, one quick question so in step 3, to prove that k^2 > 2k+1 do i prove this inductivly also?
so

im skipping the first step cuz i no i can do that
L.H.S
(K+1)(K+1)

R.H.S
2(K+1)+1
(K+1) (2 + 1/(K+1))

hmm i dont think thats right and im really tired ill pick up on this in the morning.

Title: Re: Discrete Math Help
Post by Sameer on Sep 30^th, 2007, 10:37pm

You can prove without induction.. you can start this (k-1)² - 2 > 0 for k > 5
giving k² > 2k + 1

Title: Re: Discrete Math Help
Post by Wardub on Oct 1^st, 2007, 10:34am

Hmm im so confused. after 2^k * 2 why do you have > k^2*2, and then K^2 + k^2, because 2^(k+1) != k^2 + k^2
That made no sense, anyway im getting closer

ok so we multiple both sides by 2 right
so we have 2^(k+1) > 2K^2 = k^2 + k^2
then where do i go from here? im not following your steps

Title: Re: Discrete Math Help
Post by Sameer on Oct 1^st, 2007, 10:54am

on 10/01/07 at 10:34:46, Wardub wrote:

Hmm im so confused. after 2^k * 2 why do you have > k^2*2,

Because from step 2., we have 2^k > k² so 2^k . 2 > k² . 2

Quote:

and then K^2 + k^2, because 2^(k+1) != k^2 + k^2
That made no sense, anyway im getting closer

2k² = k² + k²

Mind you we haven't yet reached k+1 part yet.

Quote:

ok so we multiple both sides by 2 right
so we have 2^(k+1) > 2K^2 = k^2 + k^2
then where do i go from here? im not following your steps

Maybe use my steps as a guide and try to do it yourself and see if you can relate!!

Title: Re: Discrete Math Help
Post by towr on Oct 1^st, 2007, 10:56am

on 10/01/07 at 10:34:46, Wardub wrote:

Hmm im so confused. after 2^k * 2 why do you have > k^2*2, and then K^2 + k^2, because 2^(k+1) != k^2 + k^2
That made no sense, anyway im getting closer

He used the induction hypothesis there.

We try to prove 2^(k+1) > (k+1)² using the hypothesis 2^k > k²

We have 2^(k+1) = 2*2^k, so we can apply the hypothesis to 2^k

Title: Re: Discrete Math Help
Post by Wardub on Nov 18^th, 2007, 9:00am

OK I am back and in need of a lot of help. I have a test tomorrow and I've been studying all weekend but I still don't get these. Ill make a list and give sample problems.

combinatorial arguments - I don't understand how to get this, or how to show it. i know it has something to do with counting something in two ways, still makes no sense to me.

We also are suppose to validate this with a tree diagram, But I have no idea how this works.

Given a sequence find recurrence relation - I can do this if I see the pattern, but I have no idea how to get it into degree 2. Sample problem An(a sub n) = n^2 for n>=2. I can get it into a degree one but need to know to degree 2.

Given an closed form find the recurrence relation. I might be able to do this.

I'm also having big trouble with some of the order and repetition concepts.
Order n and Rep y = C(r+n-1,r)
Order y and rep some C(r,k1...kn)
Order n and Rep some C(r+n-1,r) with I.E Im not sure what these are or how to perform them

Anyway here are some samples.
8 types of donuts. have to choose 36 donuts. only can have max of 4 of a, 6 of b and 8 of c. how many ways total?

how many solutions to x1+x2+x3+x4+x5+x6+x7 = 54 where 3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifx1 4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifx2 5http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifx3 6 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gifx4,x5,x6,x7

If you can help please do, I need explanations mostly, correct answers would help too. I probably didn't clarify myself well enough, so if you have questions ask please Ill be studying all day pretty much. Thank You

Title: Re: Discrete Math Help
Post by towr on Nov 18^th, 2007, 9:29am

on 11/18/07 at 09:00:16, Wardub wrote:

combinatorial arguments - I don't understand how to get this, or how to show it. i know it has something to do with counting something in two ways, still makes no sense to me.

I'm not sure what sort of problems you mean; could you give an example (even if you might not understand it)
In general, a specific example-problem would be helpfull

Quote:

Given a sequence find recurrence relation - I can do this if I see the pattern, but I have no idea how to get it into degree 2. Sample problem An(a sub n) = n^2 for n>=2. I can get it into a degree one but need to know to degree 2.

Again, I'm not entirely sure what you mean. There's a number of things I could think of. For example A_n= A_n-1+2n+1 would be a recursion which yields the same sequence as A_n= n².
Given the sequence
1 4 9 16 25 36
you can start by taking difference, and differences of differences
3 5 7 9 11
2 2 2 2
Since the last is constant, and having done two difference-sequences, we must have a degree two recurrence (afaik)
working up, a[n] =2
b[n] = b[n-1]+a[n-1] = b[n-1]+2 = 2n+1
c[n] = c[n-1] + b[n-1] = c[n-1] + b[n-1] = c[n-1] + 2n +1 (hey, that looks familiar)

Title: Re: Discrete Math Help
Post by towr on Nov 18^th, 2007, 9:40am

on 11/18/07 at 09:00:16, Wardub wrote:

how many solutions to x1+x2+x3+x4+x5+x6+x7 = 54 where 3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x1 4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x2 5 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x3 6 < x4,x5,x6,x7

subtracting 3,4,5, and 4*7 respectively brings all variables to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif0, so solving the number of ways to get
x1'+x2'+x3'+x4'+x5'+x6'+x7' = 14
should do it. And this is a matter of dividing 14 'balls' over 7 'bins', or in yet again other words the number of distinct permutations of 14 identical elements with 6 (identical) separators, i.e. C(20,14) = 38760

Title: Re: Discrete Math Help
Post by Wardub on Nov 18^th, 2007, 2:38pm

Thanks so far. As far as the other problem it should look somewhat like. ao = 1, a1 = 6 and an= an-1+6an-2 for nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif2 That is the form but not the actual answer.

Do you have any idea what I mean by tree diagram? We used it for like counting some binary strings with 00 or stuff.
Here is a small example but I don't know how he did it.
The problem was something like all binary strings of length n with no double 0's. so the tree branched out 0 or 1

x - 1 <---- then he put a y here and said http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifSn-1

x-0 ----> 01 (or else theres 2 0s) and he called this w http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifSn-2
and then he concluded Sn = Sn-1 + Sn-2

O and here is an example for combinatorial problem. Prove C(2n,2) = 2C(n,2)+ n^2. and its not suppose to be algebraic proof either

Title: Re: Discrete Math Help
Post by towr on Nov 18^th, 2007, 3:05pm

on 11/18/07 at 14:38:23, Wardub wrote:

Do you have any idea what I mean by tree diagram?

I didn't.

Quote:

We used it for like counting some binary strings with 00 or stuff.
Here is a small example but I don't know how he did it.
The problem was something like all binary strings of length n with no double 0's. so the tree branched out 0 or 1

x - 1 <---- then he put a y here and said http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif Sn-1

x-0 ----> 01 (or else theres 2 0s) and he called this w http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif Sn-2
and then he concluded Sn = Sn-1 + Sn-2

That makes some sense.
if the string ends in 1 you can put anything behind it, if it ends in 0 you can only put 1 behind it. But also, if it ends in 0, then it must end in 10 so you go two steps back in length.
Every valid bitstring is made by taking a valid bitstring (starting with the empty string and 0) and adding either 1 or 10

Quote:

O and here is an example for combinatorial problem. Prove C(2n,2) = 2C(n,2)+ n^2. and its not suppose to be algebraic proof either

What do you mean not algebraic?
Is C(2n,2)=(2n)(2n-1)/2 = n(n-1) + n² = 2C(n,2) + n² not allowed?

Title: Re: Discrete Math Help
Post by Obob on Nov 18^th, 2007, 3:11pm

Usually proving an identity combinatorially would mean to show that both sides of the equation "count" the same thing. For example, with C(2n,2)=2 C(n,2) + n², the left hand side counts the number of two element subsets of a 2n element set. Now you can form such a subset in 3 different ways. Either you can choose 2 elements from the first n elements of the 2n element subset, you can choose 2 elements from the second n elements of the 2n element subset, or you can pick one element from the first n elements and one element from the second n elements. So there are C(n,2)+C(n,2)+n*n total 2 element subsets of a 2n element set, i.e. C(2n,2)=2 C(n,2) + n².

Title: Re: Discrete Math Help
Post by Wardub on Nov 18^th, 2007, 3:50pm

Ya what Obob is talking about is correct. Am i suppose to just write that? Seems long. I have a few more questions. How many strings of length 12 have atleast 1 x and 1 y. So would this be C(8,1) * C(8,1) * 26^10?
string length 12 which contain atleast one vowel where letters cant be repeat? Would that be C(8,1)C(26,5) *25!/14!?

Also does anyone know what C(r, k1 + k2 +... kn) means?

Title: Re: Discrete Math Help
Post by Obob on Nov 18^th, 2007, 4:17pm

Proofs require that you explain all your logic and all the steps involved, so you do need to write a fair amount. Whether you write your solution into sentences and/or paragraphs is up to you, but I would highly encourage it.

Title: Re: Discrete Math Help
Post by towr on Nov 19^th, 2007, 12:07am

on 11/18/07 at 15:50:13, Wardub wrote:

I have a few more questions. How many strings of length 12 have atleast 1 x and 1 y. So would this be C(8,1) * C(8,1) * 26^10?

I'd go with the method of taking all strings of length 12 and excluding those without x's or y'; i.e. 26¹² - 2 25¹² + 24¹²
(subtract the strings without x's, subtract the strings without y's, but then we subtracted the strings with neither x's or y's twice, so add them back once).

Quote:

string length 12 which contain at least one vowel where letters can't be repeated? Would that be C(8,1)C(26,5) *25!/14!?

There are C(26,12) ways to make a string, C(21,12) ways to make a string that doesn't contain a vowel. So subtract the latter from the former and you have all strings of length 12 with at least one vowel.
Basically it's the same trick as before. Rather than count in how many ways you can do a certain thing, you can also count in how many ways you can do the opposite and subtract this from the total number of ways to do anything (in the context).

Quote:

Also does anyone know what C(r, k1 + k2 +... kn) means?

It might, possibly, denote the multinomial r!/(k₁! * k₂! * .. * k_n!)
Doesn't your textbook have an overview of the notations and what they mean? (it's usually in an appendix or on the insides of the cover)