# Mathematics for computer science

1. Feb 14, 2007

### majeedh

i was hoping somebody could help me with these problems
1) Are the following statements true or false?
(a) 2 є S, where
S= {x є R|x is the square root of an integer}
b) ø є {ø}
c) ø c ø
d) {{ø}} c {ø, {ø}}
e) {ø, {ø}, {ø, {ø}}} has the cardinality 4
f) {ø, {a}, {ø,a}} is the powerset of set of cardinaltiy 2
g) if A,B and C are sets such that AuC = BuC and AuC = BnC then A=B

also another problem I had was:

Prove that the square of an odd number is an odd
number using

Last edited: Feb 15, 2007
2. Feb 14, 2007

### cristo

Staff Emeritus
Please show your working as we cannot help you until you do. So, do you have any thoughts on the questions?

3. Feb 14, 2007

### majeedh

im sure very sure how to prove the odd number by using the proofs
but for problem 1
1) Are the following statements true or false?
(a) 2 2 S, where
S= {x 2 R|x is the square root of an integer}
(b) ; 2 {;}
(c) ; ;
(d) {{;}} {;, {;}}
(e) {;, {;}, {;, {;}}} has the cardinality 4.
(f) {;, {a}, {;, a}} is the powerset of a set of cardinality

this is what i got for number 1 but im not sure about them
a) true
b) true
c) false
d) true
e) false
f) true

i got the following for direct proof but dont know how to solve it using indirect and contradiction:

This is a statement of the form P-->Q where
Domain = integers
P = x is an odd number
Q = x^2 is odd
direct proof: assume P true and try to prove Q
Assume P true =======> x is odd
=======> x = 2k + 1 where k is an integer

By substitution x^2 = x.x = (2k + 1)(2k + 1) = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1
This number is of the form 2(integer) + 1 so it is odd
Therefore P-->Q is true and the statement is true

Last edited: Feb 15, 2007
4. Feb 15, 2007

### cristo

Staff Emeritus
I'll try and help as much as I can, but I'm not a computer scientist, and haven't studied any formal logic as such, so I may not be much help!

Could you explain your notation; for example what does ; mean?

That looks fine for the direct proof. I'm not too sure what your definition of indirect proof is here, but since the last question asks for a proof by contradiction, I would assume that indirect in this sense means a proof by contrapositive.

If so, to prove a statement by the contrapositive, you would show ~q=>~p. I.e. assume that x2 is not odd, and use it to prove that x is not odd.

For a proof by contradiction, you would assume x2 is not odd, and arrive at a contradiction.

Last edited: Feb 15, 2007
5. Feb 15, 2007

### majeedh

i have managed to prove it by direct and indirect but dont know how to prove it by contradiction...
i also had some typo errors in the question which i have resolved

Last edited: Feb 15, 2007
6. Feb 15, 2007

### cristo

Staff Emeritus
Well, we want to prove for odd x, x2 is odd. So, let x be odd and suppose that x2 is even. Then, write x=2k+1 and square it; arrive at a contradiction.

(Ive just spotted a typo in my above post, which may have confused you; the last line should be assume x2 is not odd, and arrive at a contradiction)

7. Feb 15, 2007

### majeedh

i could start the proof by assuming its odd but then what?

Last edited: Feb 15, 2007