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!

Give the Formal Proof

  1. May 22, 2009 #1

    tgt

    User Avatar

    1. The problem statement, all variables and given/known data
    GIve a formal proof or derivation of:

    (a iff (b iff c)) iff ((a iff b) iff c))


    3. The attempt at a solution
    I've tried it for a long time. Idea is to assume (a iff (b iff c)) then get ((a iff b) iff c)) and then vice versa. BUt no matter how I try, I always get some if conditions istead of the iff.
     
    Last edited: May 22, 2009
  2. jcsd
  3. May 22, 2009 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, the most brain-dead way is to write down a truth table, and invoke the fact that a proposition is a tautology if and only if all of the entries in its truth table are "true".
     
  4. May 22, 2009 #3

    tgt

    User Avatar

    The aim was to use deduction rules to prove it. In other words to deduce it all. That is the method I'm trying to use to prove it.
     
  5. May 22, 2009 #4

    tgt

    User Avatar

    Just thinking about it, deductions are always tautologies. i.e if one is asked to deduce B from A, A and B are the same statement but in different form.
     
  6. May 22, 2009 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Not so. The simplest counterexample is probably to let A be "contradiction" and to let B be "tautology". You can deduce B from A, but I doubt you could argue that they are "the same statement but in a different form".

    (I chose contradiction and tautology because they appear in the two trivial proofs: you can deduce anything from a contradiction, and from anything you can deduce a tautology)
     
  7. May 23, 2009 #6

    tgt

    User Avatar

    How about the solution to the OP? It seems impossible but it is so obvious.
     
  8. May 24, 2009 #7

    tgt

    User Avatar

    What do you mean by being able to deduce anything from a contradiction?

    Is that this: Suppose we have a contradiction then we add the negation of the thing we are trying to deduce at the beginning of the contradiction. Then the end result is that we have deduced the thing we are trying to prove.

    i.e Assume

    John is dead,
    Tim has a bread,
    Tim does not have a bread
    Contradiction!
    Hence John is not dead.

    But we could just as easily prove John is dead by reversing things.
     
  9. May 24, 2009 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That is exactly correct. Such is the nature of contradictions.
     
  10. May 24, 2009 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Just use the definition:

    A=>B is not(A) OR B

    Plug things in and reduce both sides to some canonical form.
     
  11. May 24, 2009 #10

    tgt

    User Avatar

    What about the example,

    Phil is gone,
    John is dead,
    Tim has a bread,
    Tim does not have a bread
    Contradiction!

    Now we could choose between concluding
    John is not dead and Phil is not gone?

    Any choice would be okay?


    What about the example,

    John is dead,
    Suppose there are finitely many primes,
    Conclude a contradiction that the product of those primes plus 1 cannot be a prime nor not a prime.

    Now we can either conclude John is not dead or There are infinitely many primes. EIther choice being correct?


    What about the example,

    pi is an irrational number
    Suppose there are finitely many primes,
    Conclude a contradiction that the product of those primes plus 1 cannot be a prime nor not a prime.

    Now we can either conclude pi is rational or There are infinitely many primes. EIther choice being correct?
     
  12. May 24, 2009 #11

    tgt

    User Avatar

    I've worked out the problem using the technique of deduction.
     
  13. May 24, 2009 #12

    Mark44

    Staff: Mentor

    This seems to me to be nonsense, not a contradiction. Presumably, the way this is laid out, the first three statements are the hypothesis, and the fourth is the conclusion. Because Phil being gone and John being dead have nothing to do with Tim having bread, it seems to me that this can be reduced to
    Tim has bread ==> Tim doesn't have bread
    This is not a contradiction. If Tim has bread, then it is not true that he doesn't have bread, so the first statement does not imply the second. If Tim indeed doesn't have bread, then the first statement isn't true, so any statement at all could be appear as the conclusion, and the implication would be true, but meaningless.

    BTW, in English, we don't say someone has "a bread": we say someone has bread or has a loaf of bread.
     
  14. May 24, 2009 #13

    tgt

    User Avatar

    You are misunderstood. All 4 statements are intended to be the hypothesis which we arrive at a contradiction. The conclusion is that one of the hypothesis was wrong.
     
    Last edited: May 25, 2009
  15. May 25, 2009 #14

    Mark44

    Staff: Mentor

    Maybe I misunderstood, but I wasn't misunderstood, since you apparently understood what I was saying.

    It wasn't clear to me which statements were the hypothesis, and which were the conclusion. Going back to your syllogism, let's throw out the statements about Phil and John, since they don't have anything to do with anything. That leaves us with a hypothesis of (Tim has bread) AND (Tim does not have bread). This hypothesis can never be true, so you could have any conclusion, and overall the implication would be true.

    For any implication, p ==> q, the implication will be true or valid under three circumstances, and false or invalid under one circumstance. The three true circumstances are:
    1. p is true and q is true.
    2. p is false and q is true.
    3. p is false and q is false.

    The invalid circumstance is:
    4. p is true and q is false.

    Depending on what you have for the conclusion, your syllogism of Tim having and not having bread falls into the 2nd or 3rd category.
     
  16. May 25, 2009 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    tgt: you seem to be confusing this example of a vacuous proof with proof by contradiction.

    Here are three valid arguments:

    Tim has a bread.
    Tim does not have a bread.
    Therefore, John is dead

    Tim has a bread.
    Tim does not have a bread.
    Therefore, John is alive.

    Phil is gone implies Tim has a bread.
    Phil is gone imples Tim does not have a bread.
    Therefore, Phil is not gone.


    The first two are an example of "contradiction implies anything". The third is an example of proof by contradiction.
     
  17. May 25, 2009 #16

    tgt

    User Avatar

    Well, I understood that you misunderstood which seems valid.

    I do acknowledge that my presentation of arguments was not clear.
     
  18. May 25, 2009 #17

    tgt

    User Avatar

    Wouldn't your proof by contradiction need the extra assumption to get the contradiction. So it would be better if it was:

    1. Phil is gone
    2. Phil is gone implies Tim has a bread.
    3. Phil is gone imples Tim does not have a bread.
    Therefore, Phil is not gone.

    Where 1,2 and 3 are assumptions.
     
  19. May 25, 2009 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Heavens no! Those three statements are a contradiction!
     
  20. May 25, 2009 #19

    tgt

    User Avatar

    We are trying to deduce a contradiction which is what we get after combining those three statements.

    To give more detail it's

    If:
    Phil is gone
    Phil is gone implies Tim has a bread.
    Phil is gone imples Tim does not have a bread.

    Then:
    Tim has a bread
    Tim does not have a bread

    We get a contradiction.

    Conclusion:
    One or more of our assumptions was wrong (or is it only one assumption was wrong?)
    We say that Phil is not gone.

    But couldn't we conclude that the statement 'Phil is gone implies Tim has a bread' is incorrect hence the reverse of that statement is true instead?
     
  21. May 25, 2009 #20

    tgt

    User Avatar

    With regards to the OP. I realised that I've made a mistake. The technique is to use natural deduction to prove the statement.

    http://www.ags.uni-sb.de/~chris/papers/2002-pisa.pdf [Broken]
     
    Last edited by a moderator: May 4, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Give the Formal Proof
  1. Formal limit proof (Replies: 8)

Loading...