Results 1 to 15 of 15

Math Help - Laws of logic

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Laws of logic

    I have reached the following point with a statement negation:

    \forall x(\neg Qx \vee \neg (\neg (\neg Px \vee Qx)\vee Qy))

    \equiv \forall x (\neg Qx \vee (\neg Px \vee Qx)\wedge \neg Qy)

    Now, I understand that (Px\vee Qx) \vee Rx is the same as Px\vee (Qx \vee Rx) but can I move terms? For example in my negation, can I put the \neg Qx and the Qx terms next to each other so that I get a true statement? or is there nothing more I can do (other than expanding with the \neg Qy)?

    I couldn't find anything in my list of laws to answer this for me.
    Last edited by terrorsquid; August 28th 2011 at 05:50 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: Laws of logic

    the number of left and right braces don't match..... please correct......
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Laws of logic

    I removed the brackets next to the functions to make it less confusing, hows that?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: Laws of logic

    Quote Originally Posted by terrorsquid View Post
    I have reached the following point with a statement negation:

    \forall x(\neg Qx \vee \neg (\neg (\neg Px \vee Qx)\vee Qy))

    \equiv \forall x (\neg Qx \vee (\neg Px \vee Qx)\wedge \neg Qy)

    Now, I understand that (Px\vee Qx) \vee Rx is the same as Px\vee (Qx \vee Rx) but can I move terms? For example in my negation, can I put the \neg Qx and the Qx terms next to each other so that I get a true statement? or is there nothing more I can do (other than expanding with the \neg Qy)?

    I couldn't find anything in my list of laws to answer this for me.
    use the logical equivalence between

    (\neg p \vee q) \equiv (p \Rightarrow q) so your expression can be transformed to

    \forall x [\neg Qx \vee \neg [\neg (Px \Rightarrow Qx) \vee Qy] ]

    \forall x [\neg Qx \vee \neg [ (Px \Rightarrow Qx) \Rightarrow Qy] ]

    \forall x [ Qx \Rightarrow \neg [ (Px \Rightarrow Qx) \Rightarrow Qy] ]

    by the way , are you sure there is Qy ? because y here remains a free variable. It not bound by the universal quantifier.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Laws of logic

    Quote Originally Posted by terrorsquid View Post
    \equiv \forall x (\neg Qx \vee (\neg Px \vee Qx)\wedge \neg Qy)

    Now, I understand that (Px\vee Qx) \vee Rx is the same as Px\vee (Qx \vee Rx) but can I move terms? For example in my negation, can I put the \neg Qx and the Qx terms next to each other so that I get a true statement?
    No, you can't put \neg Qx next to Qx because the distribution of parentheses is

    \neg Qx \vee \Big((\neg Px \vee Qx)\wedge \neg Qy\Big)

    and not

    \Big(\neg Qx \vee (\neg Px \vee Qx)\Big)\wedge \neg Qy

    However, you can distribute \/ over /\ to get

    \big(\neg Qx\lor \neg Px \vee Qx\big)\land\big(\neg Qx\lor\neg Qy\big)
    \equiv\neg Qx\lor\neg Qy
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Laws of logic

    Quote Originally Posted by issacnewton View Post
    by the way , are you sure there is Qy ? because y here remains a free variable. It not bound by the universal quantifier.
    Maybe I should have just posted the original question from the start. I felt I understood everything other than maybe a technique for organising the last part so I sampled the question to try and explain my question. Seems it just confused matters

    Original question:

    Negate the statement:

    \exists x (\forall y (Qx \wedge ((\neg Px\vee Qx)\rightarrow Qy)))

    Sorry for confusion.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Laws of logic

    So yes, I think the shortest form of negation is \forall x\exists y\,(\neg Qx\lor\neg Qy), or \forall x\exists y\,(Qx\to\neg Qy).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Laws of logic

    Quote Originally Posted by emakarov View Post
    No, you can't put \neg Qx next to Qx because the distribution of parentheses is

    \neg Qx \vee \Big((\neg Px \vee Qx)\wedge \neg Qy\Big)

    and not

    \Big(\neg Qx \vee (\neg Px \vee Qx)\Big)\wedge \neg Qy

    However, you can distribute \/ over /\ to get

    \big(\neg Qx\lor \neg Px \vee Qx\big)\land\big(\neg Qx\lor\neg Qy\big)
    \equiv\neg Qx\lor\neg Qy
    Ok, yes that was what I was looking for.

    Just one thing. I can see how you have applied the distributive law to reduce the statement; however, one thing I don't see is how you know that the distribution of parentheses is like that.

    As I complete my negation going through the steps I seem to arrive at:

    \forall x \exists y (\neg Qx \vee (\neg Px \vee Qx)\wedge \neg Qy)

    I finish without any internal parentheses every time I do it :S
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Laws of logic

    Strictly speaking, A \/ B /\ C is not a well-formed formula: it has to be either (A \/ B) /\ C or A \/ (B /\ C). We can drop parentheses only if we make a convention that, say, /\ binds stronger than \/; then A \/ B /\ C would stand for A \/ (B /\ C).

    In this problem, the conjunction results from the negation of ((\neg Px\vee Qx)\rightarrow Qy). So,

    \neg Qx\lor\neg\Big((\neg Px\vee Qx)\rightarrow Qy\Big)\equiv\neg Qx\lor\Big((\neg Px\vee Qx)\land \neg Qy\Big)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Laws of logic

    So for future instances when I come across problems that result in a conjunction without explicit usage of parentheses, like the above statement, I should assume parentheses around the \wedge terms always? I can see what you are saying for this problem, I am just trying to understand a general rule so when I come across something similar in the future, I will know what to do.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Laws of logic

    In all formal systems I can remember, A \/ B /\ C is interpreted as A \/ (B /\ C). However, this issue does not arise in this problem. Here, you don't start with \neg Qx \vee (\neg Px \vee Qx)\wedge \neg Qy. The (quantifier-free part of the) original formula \exists x (\forall y (Qx \wedge \Big((\neg Px\vee Qx)\rightarrow Qy\Big))) is a conjunction of Qx and an implication. During negation, Qx and the implication are converted separately: Qx turns into Qx, and the implication turns into a conjunction. Therefore, the negation is a disjunction of Qx and this conjunction.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Laws of logic

    Quote Originally Posted by emakarov View Post
    Strictly speaking, A \/ B /\ C is not a well-formed formula: it has to be either (A \/ B) /\ C or A \/ (B /\ C). We can drop parentheses only if we make a convention that, say, /\ binds stronger than \/; then A \/ B /\ C would stand for A \/ (B /\ C).

    In this problem, the conjunction results from the negation of ((\neg Px\vee Qx)\rightarrow Qy). So,

    \neg Qx\lor\neg\Big((\neg Px\vee Qx)\rightarrow Qy\Big)\equiv\neg Qx\lor\Big((\neg Px\vee Qx)\land \neg Qy\Big)
    I think my problem arises because when I complete the steps you did above, I do it this way:

    \neg Qx\lor\neg\Big((\neg Px\vee Qx)\rightarrow Qy\Big)

    Then I change the implication to a conjunction first:

    \equiv\neg Qx \vee \neg \Big(\neg (\neg Px \vee Qx)\vee Qy\Big)

    Then distribute the negative using De Morgan's:

    \equiv \neg Qx \vee (\neg Px \vee Qx) \wedge \neg Qy

    and the parentheses disappear when I us De Morgans to leave an unclear conjunction if you see what I mean?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Laws of logic

    The parentheses do not disappear after the application of De Morgan's law. Remember that all subformulas have parentheses around them; some of them are just not written. So you take ((Qx)) \/ (((_) \/ (_))) and replace ((_) \/ (_)) with (_) /\ (_). The parentheses around (_) are still there, so you get ((Qx)) \/ ((_) /\ (_)).

    It is useful to think about formulas as tree structures. The strings of characters that we use to write formulas are just representations ("concrete syntax" in programming); what is important is the abstract structure. So you take the formula



    and change the circled part to get



    In the end, /\ is still performed first and the root \/ second.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Laws of logic

    See, now I have to donate. That is just TOO helpful
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: Laws of logic

    thanks makarov

    excellent explanation.... makarov is the god of logic on this forum......
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic Laws Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 9th 2010, 09:27 PM
  2. Help with Logic Laws
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 9th 2010, 07:22 PM
  3. Laws of logic question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 14th 2010, 11:31 AM
  4. laws of logic question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 14th 2010, 09:11 AM
  5. laws of logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2010, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum