Page 1 of 3 123 LastLast
Results 1 to 15 of 42

Math Help - logic related question ...

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    logic related question ...

    Below is the proof for the following proposition:

    (p q) (q p)

    For each step in the proof indicate which law is used.
    We start with:

    p q

    Step 1: p q
    Step 2: q p
    Step 3: (q) p
    Step 4:
    qp

    What law belongs to what step?
    Law 1: (a
    b) (b a) (commutativity of )
    Law 2: (a) a(law of negation)
    Law 3:
    (a⇒ b) (a b) (law of implication)
    Law 4:
    (a b) ((a b) ∧ (b a))(law of equivalence)

    I really have no clue where to start here ... so maybe someone can give me a hand ...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    I found this explanation ... can someone confirm this is correct?

    CNF = Conjunctive Normal Form
    wff = Well Formed Formula

    The following is the procedure to transform any wff into a logically equivalent wff that is in CNF.

    Step 1. Eliminate ⇔s (using the Law of Equivalence)

    Step 2. Eliminate ⇒s (using the Law of Implication)

    Step 3. Move s inwards (using De Morgans Laws), eliminating any double negations (using the Law of Negation).

    Step 4. Use the Distribute Law (∨ over ∧) to move the ∧s up and the ∨s down; use commutativity and associativity of ∧ and ∨ to reorder subformulas so that this law may be used.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: logic related question ...

    We start with:

    p ⇒ q

    Step 1: p ∨ q
    Hmm, let's see, which of the following four laws is responsible for this step:
    Law 1: (a ∨ b) ⇔ (b∨ a) (commutativity of ∨)
    Law 2: (a) ⇔ a(law of negation)
    Law 3: (a⇒ b) ⇔ (a∨ b) (law of implication)
    Law 4: (a⇔ b) ⇔ ((a⇒ b) ∧ (b ⇒ a))(law of equivalence)
    I really have no clue where to start here
    To be honest, if you don't see which of the four laws is responsible for converting p ⇒ q into p ∨ q, I am also at a loss concerning how to explain it.

    I found this explanation ... can someone confirm this is correct?
    Yes, but if this is an unrelated question, please post it in a different thread.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    Yes, but if this is an unrelated question, please post it in a different thread.
    I think this is related but I am not sure...

    To be honest, if you don't see which of the four laws is responsible for converting p ⇒ q into p ∨ q, I am also at a loss concerning how to explain it.
    We need the 4 laws in a specific order right?
    But isn't there a trick to see this? Or is this just information that is by rule?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: logic related question ...

    I think this is related but I am not sure...
    I don't think so.

    We need the 4 laws in a specific order right?
    No, to convert p ⇒ q into p ∨ q we need only law 3.

    But isn't there a trick to see this?
    I am not sure which trick.

    Or is this just information that is by rule?
    I don't know by which rule and what you mean by "information is by rule."
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    I just want to understand what I should do in order to understand/solve the question...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: logic related question ...

    In order to understand what you need to do, you need to realize that each step is a transformation of the previous step by some instance of the provided laws. Which law do you use? That is for you to figure out by simple pattern matching. As already pointed out to you, the first step is a direct application (instance) of Law 3. Do you not see why? If you replace the generic "a" and "b" in Law 3 by the specifics given in the problem "p" and "q", you get exactly the transformation we see from our assumption to step 1.

    Now think about step 2. What has changed between step 1 and step 2? Which of the provided laws represent that change?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    I think that Step 2 belongs to Law 2 ... am I correct?

    Now think about step 2. What has changed between step 1 and step 2? Which of the provided laws represent that change?
    The change is that NOT p swapped places with q ... And the law of negation represents this change right?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: logic related question ...

    You are right, the commutative law of disjunction allows us to transpose positions of each disjunct. The point of the law is to generalize a schema of something that is true for every similar instance. While in your case you are dealing with "p v q" it would also work for complex statements like "(p & r) v q" (i.e., it is equivalent to "q v (p & r)"). The point of these exercises is to become familiar with what the laws entail. The name of the law helps explain that. Commutitive laws allow you to commute (transpose, switch positions, etc.) terms around the connective. The law of (double) negation allows you to add a double negative or take it away. The law of implication gives you an equivalent form that is useful for conjunctive or disjunctive normal forms. The law of equivalence lets you break up a biconditional into conjunctions (and from the conjunct of implication with law 3 you can have a conjunction of disjunctions).

    Now do you see how the laws justify each transformation at each step? More importantly, do you see why each step is performed due to the provided law?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    Commutitive laws allow you to commute (transpose, switch positions, etc.) terms around the connective
    The law of (double) negation allows you to add a double negative or take it away
    The law of implication gives you an equivalent form that is useful for conjunctive or disjunctive normal forms
    The law of equivalence lets you break up a biconditional into conjunctions (and from the conjunct of implication with law 3 you can have a conjunction of disjunctions)
    Now do you see how the laws justify each transformation at each step? More importantly, do you see why each step is performed due to the provided law?
    I can see a pattern indeed ...

    SO with this information given I think Step3 = Law 1
    And Step 4 = Law 4

    Am I correct?

    Thanks,
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: logic related question ...

    Why do you think that? Does it fit the pattern of behavior I described each of the laws to have as you quoted above? Note, you're not using every law in that proof. Some of them are used more than once. Often a pattern of reasoning is like that: you put the statement in other terms that make it easier to put into another form that can then be put into other terms that are desired. That is what is going on here. Remember, your end goal of the proof is to show that q → p. Just as before, what has changed between steps 2 and 3? What is changed between 3 and 4? That change is indicative of some law, otherwise you would not be able to make that sort of transformation. If you can understand that pattern of change, you can answer my original question as to why the law is used at that step. If you cannot answer the 'why' question, you have not grasped the exercise. The point of it is to obtain that pattern recognition skill and relate it to your knowledge of the logical operations involved.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    Step 1: p ∨ q = Law 3
    Step 2: q ∨p = Law 2
    Step 3: (q) ∨p = Law 4
    Step 4: q⇒ p = Law 1

    So if I understand correctly they want you to start with the first step (p ∨ q) where you see almost immediately that this belons to Law 3 ... only the characters are different.
    And the end result should be q ⇒ p
    ANd we get there with using the different laws in the correct order right?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: logic related question ...

    Here is a quote from the thread's first post, to remind the law numbers.

    Quote Originally Posted by iwan1981 View Post
    Law 1: (a ∨ b) ⇔ (b∨ a) (commutativity of ∨)
    Law 2: (a) ⇔ a(law of negation)
    Law 3: (a⇒ b) ⇔ (a∨ b) (law of implication)
    Law 4: (a⇔ b) ⇔ ((a⇒ b) ∧ (b ⇒ a))(law of equivalence)
    So, in step 2, we go from p ∨ q to q ∨p. Why do you think that this is described by law 2: (a) ⇔ a rather than by law 1: (a ∨ b) ⇔ (b ∨ a)? Does the starting formula, i.e., p ∨ q, look more like (a) or like a ∨ b?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: logic related question ...

    Does the starting formula, i.e., p ∨ q, look more like (a) or like a ∨ b?
    It looks more like "a ∨ b" right?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: logic related question ...

    Yes. But before we go further, could you explain this line:
    Quote Originally Posted by iwan1981 View Post
    Step 3: (q) ∨p = Law 4
    I really want to understand you reasoning. We are converting

    q ∨ p (*)

    into

    (q) ∨ p (**).

    You are saying this is done by law 4:

    (a ⇔ b) ⇔ ((a ⇒ b) ∧ (b ⇒ a))

    Yet, this law does not mention either ∨ or , which are the only connectives (operations) in the formulas (*) and (**) above. Why do you think law 4 applies?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 3 123 LastLast

Similar Math Help Forum Discussions

  1. Logic Question
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: July 20th 2010, 01:43 PM
  2. [SOLVED] A logic question!!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 11th 2010, 03:05 PM
  3. 2 simple proof questions, logic related
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 10th 2009, 08:16 PM
  4. logic question
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 4th 2009, 06:39 AM
  5. Question about logic
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 5th 2008, 06:51 AM

/mathhelpforum @mathhelpforum