1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Question about propositional logic

  1. Dec 20, 2017 #1
    1. The problem statement, all variables and given/known data
    I have to prove that ##(p \equiv q) \equiv ((p ∧ q) ∨ (¬p ∧ ¬q))##
    With no premisses

    In order to prove this, I first need to prove that:
    ##(p \equiv q) \to ((p ∧ q) ∨ (¬p ∧ ¬q))##

    And:
    ##((p ∧ q) ∨ (¬p ∧ ¬q)) \to (p \equiv q)##

    I was able to find the second implication, but I am still looking how I can prove the first one.

    2. Relevant equations

    I have the inference rules, contraposition, modus tollens ...

    3. The attempt at a solution
    I started with the hypothetical statement:
    ##(p \equiv q)##
    But then I need to end the hypothetical statement with:
    ##((p ∧ q) ∨ (¬p ∧ ¬q))##

    So I have tried to start a new hypothetical statement:
    ##¬((p ∧ q) ∨ (¬p ∧ ¬q))##
    And to introduce a negation.
    ##¬((p ∧ q) ∨ (¬p ∧ ¬q)) \to (p \equiv q)## was easy to find, but I can't find a way to prove:
    ##¬((p ∧ q) ∨ (¬p ∧ ¬q)) \to ¬(p \equiv q)##
    So that I could eliminate the negation afterwards.
    I was looking to prove
    ##¬(p \equiv q)##
    But I couldn't find a way to introduce the negation.

    So I've tried to eliminate the disjuntion of:
    ##(p ∧ q) ∨ (¬p ∧ ¬q)##
    By starting a new hypothetical statement, but this couldn't help me any futher.

    Thank you in advance!
     
  2. jcsd
  3. Dec 20, 2017 #2

    nomadreid

    User Avatar
    Gold Member

    There are many ways you could prove this. The easiest way to prove both directions is with truth tables, but if you don't like that, then for example you can write out what p≡q means, that is (p→q)∧(q→p), then write A→B as A∨~B for each pair, then use the distributive law: (M∨N)∧(R∨S) ≡ (M∧R)∨(M∧S)∨(N∧R)∨(N∧S), and then simplify.
     
  4. Dec 20, 2017 #3
    I think that we haven't seen the distributive law in logics. I've put all the rules that we have just below. For this exercise we are not allowed to use truth tables, so we have to use these rules to prove it.

    ##A, B / A∧B ##
    ##A∧B / A resp. A∧B / B##
    ##A / A∨B resp. B / A∨B##
    ##A∨B, A \to C, B \to C / C##
    ##A \to B, A \to ¬B / ¬A##
    ##¬¬A / A##
    ##A \to B, B \to A / A≡B ##
    ##A≡B / A \to B, B \to A##
    ##A, A \to B / B##
    ##A (Hyp), B / A \to B##
    ##A \to B, ¬B / ¬A ##
    ##¬A, A∨B / B##
    ##A \to B, B \to C / A \to C##
    ##A \to B / ¬B \to ¬A##
    ##¬(A∧B) / ¬A∨¬B##
    ##¬(A∨B) / ¬A∧¬B ##
    ## ¬(A \to B) / A∧¬B##
     
  5. Dec 20, 2017 #4

    nomadreid

    User Avatar
    Gold Member

    I find your statement that
    was easy to prove a bit odd, since if the statement that you are trying to prove
    is correct (which it is if you think about what it is saying), then
    by substitution (and a couple more easy steps).
    This is not a solution, it is just pointing out that since the first and the third implication cannot both be correct, you apparently made a mistake in the derivation of the second implication above. If you find that mistake, you will probably be on your way to finding the correct derivation.
    By the way, to find out if you have a mistake, although you are not allowed to use truth tables in your solution, you can use them to check a statement as being correct or not for your own peace of mind; you just don't hand that work in.
     
  6. Dec 20, 2017 #5
    I think that I do understand what you mean and I see that introducing the negation on
    ##¬(p∧q)∨(¬p∧¬q)##
    By doing
    ##¬((p∧q)∨(¬p∧¬q))→(p≡q)##
    ##¬((p∧q)∨(¬p∧¬q))→¬(p≡q)##
    Is unnecessary because when I use the transposition rule on
    ##¬((p∧q)∨(¬p∧¬q))→¬(p≡q)##
    I get
    ##(p \equiv q) \to ((p∧q)∨(¬p∧¬q))##
    And that is what I need.

    I just don't see what you mean by mistake, because I was trying to use the rule:
    ##A \to B, A \to ¬B / ¬A##

    And I will try write the truth table down! (Thank you for the tip!)
     
  7. Dec 20, 2017 #6
    So I've set up some truth tables and I was able to find out that I can prove them. But now I am trying an other way. I'm trying to prove
    ##¬((p∧q)∨(¬p∧¬q)) \to ¬(p \equiv q)##

    So I started my hypothetical statement with
    ##¬((p∧q)∨(¬p∧¬q))##
    ##¬(p∧q)∧¬(¬p∧¬q)##

    Then I started a new hypothetical statement with
    ##(p \equiv q)##

    I want to prove that
    ##(p \equiv q) \to ?## and
    ##(p \equiv q) \to ¬?##

    So that I can conclude to
    ##¬(p \equiv q)##

    But I don't see what I need to put on the question marks. I've looked for information that I have, which is:
    ##¬p∨¬q##
    ##p∨q##
    ##p \to q##
    ##q \to p##
     
  8. Dec 21, 2017 #7

    Delta²

    User Avatar
    Homework Helper
    Gold Member

    I think the idea behind this exercise is a lemma (##p \equiv q## is equivalent to ##A(p) \equiv A(q)## )where A(p) is any sentence that has p as variable and A(q) is the same sentence where we replace p with q. You can prove this lemma by induction in the form of A(p). Have you been taught this type of induction?
     
  9. Dec 21, 2017 #8
    No we haven't seen that, I'm only in my first year psychology and I think we will only see the basics of logics
     
  10. Dec 21, 2017 #9

    nomadreid

    User Avatar
    Gold Member

    Sorry for the mess in the first sending of this post that arrived in your email inbox, and also for delay in responding, Florence, but I'm probably in a different time zone than you are, and sleep tends to interfere with one's schedule, and this morning my keyboard is acting up.
    First, to your post asking where you had the mistake. This was my mistake in not reading your post carefully enough to see that you were attempting a proof by contradiction.
    Let me recap.
    So far you proved the second part of your task
    ((p∧q)∨(¬p∧¬q))→(p≡q)
    and then you started on the first part, proving by contradiction:
    ¬((p∧q)∨(¬p∧¬q)) / (¬((p∧q)∨(¬p∧¬q))→(p≡q))
    which did not get you very far.

    Going back to your original statement, you want to prove
    (p≡q)→((p∧q)∨(¬p∧¬q))
    i.e.
    (p∨¬q)∧(¬p∨q)→((p∧q)∨(¬p∧¬q))
    Since you like proof by contradiction, let me restate this:
    ~((p∧q)∨(¬p∧¬q))→~((p∨¬q)∧(¬p∨q)) (*)
    (I will now be lazy and use ~ as being the same thing as the crook symbol, and omit the obvious double negation elimination steps)
    (Also I will omit the obvious step of double negation elimination
    First apply deMorgan to the LHS to get

    (~(p∧q)∧~(¬p∧¬q))
    Apply deMorgan again

    Apply deMorgan to the RHS of (*) to get
    ~(p∨¬q)∨~(¬p∨q))
    deMorgan again
    (~p∧q)∧ (p∧~q)
    Using your rule
    several times, you get
    (~p∨~q)
    and again
    (p∨q)
    Then use your rule that allows you to join them with ∧
    Now, do you suppose you can get a contradiction?
    Sorry for the lack of detail, but I must run out for the rest of the day. I will be back online tomorrow.
     
    Last edited: Dec 21, 2017
  11. Dec 21, 2017 #10
    No problem! I really appreciate all of your help!

    But I don't really get what I need to do now
    Do I need to start the hypothetical statement with
    ##(p \equiv q)##
    Then start another hypothetical statement with
    ## ¬((p∧q)∨(¬p∧¬q))##
    This? Or
    ##¬((p∨¬q)∧(¬p∨q))##
    This?
     
  12. Dec 21, 2017 #11

    nomadreid

    User Avatar
    Gold Member

    Right, I was a little sketchy on how the proof proceeded after the last line. You can proceed either by proof by contradiction, or a straight proof without it. You seemed to be partial to proof by contradiction, so I first converted the original statement into something easier to prove by contradiction. I started with the statement you wanted to prove, converted ≡, took the contrapositive, used deMorgan, elimination of double negation, & the rules that I quoted about ∧,....so far, notice that I had not tried a proof by contradiction. But after you convert both sides, you end up with
    (~p∨~q)∧(p v q))→(~p∨~q)∧(p∨q).
    which is just A→A.
    That was to show you what could go into the brackets if iI started with ~(original statement).
    So, to do the proof, you can just start again but this time start with ~(original statement), and you will end up with
    ~ (A→A), which is (or can be turned into, according to your definition) a contradiction.
    That is, you will have proven
    ~(original statement)→contradiction.
    and thus you will have proven the original statement.

    No guarantee that this is the shortest way; a direct proof would also be possible through the same types of conversions.
     
  13. Dec 21, 2017 #12
    I think that I get it! I will try it out!

    Thank you!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted