1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematics for computer science

  1. Feb 14, 2007 #1
    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: Feb 15, 2007
  2. jcsd
  3. Feb 14, 2007 #2

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    Please show your working as we cannot help you until you do. So, do you have any thoughts on the questions?
     
  4. Feb 14, 2007 #3
    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
  5. Feb 15, 2007 #4

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    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
  6. Feb 15, 2007 #5
    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
  7. Feb 15, 2007 #6

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    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)
     
  8. Feb 15, 2007 #7
    i could start the proof by assuming its odd but then what?
     
    Last edited: Feb 15, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mathematics for computer science
  1. Mathematical induction (Replies: 3)

  2. Direct Proofs (Replies: 3)

  3. Mathematical Induction (Replies: 1)

  4. Mathematical proof (Replies: 4)

Loading...