1. ## 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.

2. ## Re: Laws of logic

the number of left and right braces don't match..... please correct......

3. ## Re: Laws of logic

I removed the brackets next to the functions to make it less confusing, hows that?

4. ## Re: Laws of logic

Originally Posted by terrorsquid
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.

5. ## Re: Laws of logic

Originally Posted by terrorsquid
$\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$

6. ## Re: Laws of logic

Originally Posted by issacnewton
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.

7. ## 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)$.

8. ## Re: Laws of logic

Originally Posted by emakarov
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

9. ## 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)$

10. ## 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.

11. ## 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.

12. ## Re: Laws of logic

Originally Posted by emakarov
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?

13. ## 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.

14. ## Re: Laws of logic

See, now I have to donate. That is just TOO helpful

15. ## Re: Laws of logic

thanks makarov

excellent explanation.... makarov is the god of logic on this forum......