• Support PF! Buy your school textbooks, materials and every day products Here!

Mathematics for computer science

  • Thread starter majeedh
  • Start date
  • #1
14
0
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
 
Last edited:

Answers and Replies

  • #2
cristo
Staff Emeritus
Science Advisor
8,107
73
Please show your working as we cannot help you until you do. So, do you have any thoughts on the questions?
 
  • #3
14
0
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:
  • #4
cristo
Staff Emeritus
Science Advisor
8,107
73
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 im 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 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
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:
  • #5
14
0
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:
  • #6
cristo
Staff Emeritus
Science Advisor
8,107
73
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
14
0
i could start the proof by assuming its odd but then what?
 
Last edited:
Top