Mathematics for computer science

[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
proof by contradiction

 

[cristo]

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

 

[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 I am not sure about them
a) true
b) true
c) false
d) true
e) false
f) true

i got the following for direct proof but don't 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

 

[cristo]

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!

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 I am not sure about them
a) true
b) true
c) false
d) true
e) false
f) true

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

i got the following for direct proof but don't 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

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 x² is not odd, and use it to prove that x is not odd.

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

 

[majeedh]

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

 

[cristo]

Well, we want to prove for odd x, x² is odd. So, let x be odd and suppose that x² 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 x² is not odd, and arrive at a contradiction)

 

[majeedh]

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