Results 1 to 15 of 15

Thread: Laws of logic

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Laws of logic

    I have reached the following point with a statement negation:

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

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

    Now, I understand that $\displaystyle (Px\vee Qx) \vee Rx$ is the same as $\displaystyle Px\vee (Qx \vee Rx)$ but can I move terms? For example in my negation, can I put the $\displaystyle \neg Qx$ and the $\displaystyle 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 $\displaystyle \neg Qy$)?

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

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

    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
    208

    Re: Laws of logic

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

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

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

    Now, I understand that $\displaystyle (Px\vee Qx) \vee Rx$ is the same as $\displaystyle Px\vee (Qx \vee Rx)$ but can I move terms? For example in my negation, can I put the $\displaystyle \neg Qx$ and the $\displaystyle 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 $\displaystyle \neg Qy$)?

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

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

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

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

    $\displaystyle \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,577
    Thanks
    790

    Re: Laws of logic

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

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

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

    and not

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

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

    $\displaystyle \big(\neg Qx\lor \neg Px \vee Qx\big)\land\big(\neg Qx\lor\neg Qy\big)$
    $\displaystyle \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:

    $\displaystyle \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,577
    Thanks
    790

    Re: Laws of logic

    So yes, I think the shortest form of negation is $\displaystyle \forall x\exists y\,(\neg Qx\lor\neg Qy)$, or $\displaystyle \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 $\displaystyle \neg Qx$ next to $\displaystyle Qx$ because the distribution of parentheses is

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

    and not

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

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

    $\displaystyle \big(\neg Qx\lor \neg Px \vee Qx\big)\land\big(\neg Qx\lor\neg Qy\big)$
    $\displaystyle \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:

    $\displaystyle \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,577
    Thanks
    790

    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 $\displaystyle ((\neg Px\vee Qx)\rightarrow Qy)$. So,

    $\displaystyle \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 $\displaystyle \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,577
    Thanks
    790

    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 $\displaystyle \neg Qx \vee (\neg Px \vee Qx)\wedge \neg Qy$. The (quantifier-free part of the) original formula $\displaystyle \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 $\displaystyle ((\neg Px\vee Qx)\rightarrow Qy)$. So,

    $\displaystyle \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:

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

    Then I change the implication to a conjunction first:

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

    Then distribute the negative using De Morgan's:

    $\displaystyle \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,577
    Thanks
    790

    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
    208

    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: Apr 9th 2010, 09:27 PM
  2. Help with Logic Laws
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Apr 9th 2010, 07:22 PM
  3. Laws of logic question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 14th 2010, 11:31 AM
  4. laws of logic question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 14th 2010, 09:11 AM
  5. laws of logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 9th 2010, 05:12 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum