Set Theory Questions: Equivalence Rules and Tautology Proof

[MathematicalPhysicist]

i searched in the homework section and there isn't a section for logic an set theory so i ask my questions here (begging for replies):
1)expand the proposition (by the equivalence rules):
[~(pvq)v((~p)^q)]
i got to this: [(~pv~p)^(~pv~q)]^[(qv~p)^(qv~q)]
is it correct?
2) prove/disprove:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
which means to prove that the double implication is tautology.
so i have assumed that:
T-(Ex)(Ay)p(x,y)
T-(Ay)p(a,y)
T-p(a,y)
T-(Ea)p(a,y)
T-(Ay)(Ex)P(x,y)
is this correct or where i am wrong?

your replies is much appreciated.

 

[honestrosewater]

1)expand the proposition (by the equivalence rules):
[~(pvq)v((~p)^q)]
i got to this: [(~pv~p)^(~pv~q)]^[(qv~p)^(qv~q)]
is it correct?

I'm not sure what "expand" means. Do you want to distribute them, using

(P v (Q & R)) <=> ((P v Q) & (P v R))
(P & (Q v R) <=> ((P & Q) v (P & R))

??

2) prove/disprove:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
which means to prove that the double implication is tautology.
so i have assumed that:
T-(Ex)(Ay)p(x,y)
T-(Ay)p(a,y)
T-p(a,y)
T-(Ea)p(a,y)
T-(Ay)(Ex)P(x,y)
is this correct or where i am wrong?
your replies is much appreciated.

Consider this example.

(1) \forall x \exists y (x = y)

This says that for every x that I choose, I can find at least one y that is equal to that x.

(2) \exists y \forall x (x = y)

This says that I can find at least one y that is equal to every x.

Can you think of a case where (1) is true and (2) is false?

 

[AKG]

I don't know if "tautology" is the right word to be using there. Perhaps you mean to show that it is a theorem? As for your proof, you probably shouldn't instatiate y with y, but at any rate, when you instatiate x, you have to do so as an assumption. Within the scope of that assumption, you have to derive some existentially quantified sentence that does not contain the constant by which you instantiated x. From that you can conclude that your derived sentence is true even beyond the scope of your assumption, and then you can make the desired conclusion that you have. So your proof, although sketchy, is the right idea behind proving that (Ex)(Ay)p(x,y) -> (Ay)(Ex)p(x,y). However, this proof does not give you the converse because the converse is, in fact, not true, as honestrosewater's example demonstrates.

For #1, by "expand" it appears you mean that you wish to express your sentence in conjunctive normal form, that is, in the form:

[A v B] & [C v D] & ... & [Y v Z]

where I believe A, B, ..., Y, Z have to be either atomic sentences or negations of atomic sentences. I looked it up, and CNFs take the above form, but inside the brackets you can have any number of disjuncts (even just 1), not only 2. I don't know whether you did the work right, but one way to check that you've done it right is to look at what the CNF shows you. Since the CNF of your sentence is equivalent to your sentence, your sentence is true iff the CNF is true. The CNF is true iff all its conjuncts are true. All the conjuncts are true iff:

(~pv~p) is true, (~pv~q) is true, (qv~p) is true, and (qv~q) is true

iff

* ~p is true, (~pv~q) is true, (qv~p) is true, and (qv~q) is true

iff

~p is true. Why? Because clearly if all the sentences following * are true, then the first one is, and the first one is just ~p. On the other hand, if ~p is true, then certainly ~p is true, and the second and third sentences are also true (by the rule of disjunction introduction, i.e. the fact that a implies (a v b)), and the last sentence is a tautology so it's always true.

Now, check that your sentence is true iff ~p is true. I would rewrite your sentence as:

[~(pvq)v((~p)^q)]
[((~p)^(~q))v((~p)^q)] by DeMorgan's
[(~p)^((~q)vq)] by distribution
~p since ((~q)vq) is tautologous

From here, it's more than obvious that your sentence is true iff ~p is true.

 

[MathematicalPhysicist]

I'm not sure what "expand" means. Do you want to distribute them, using

(P v (Q & R)) <=> ((P v Q) & (P v R))
(P & (Q v R) <=> ((P & Q) v (P & R))

these are the equivalence rules i used, so yes.

??
Consider this example.

(1) \forall x \exists y (x = y)

This says that for every x that I choose, I can find at least one y that is equal to that x.

(2) \exists y \forall x (x = y)

This says that I can find at least one y that is equal to every x.

Can you think of a case where (1) is true and (2) is false?

yes i can see your point, but how do i translate it in mathematical sense?
i mean we start with assuming the antecedant is T and we should be getting that the consequent is F, and thus it will not be "<=>".
how do i write it?
thanks in advance. (you guys are superb!).

 

[AKG]

So what exactly do you have to do when they ask you to "expand"? And for the second problem, how are you supposed to go about proving/disproving? Do you need to prove/disprove that it is a tautology (I think you would mean "valid", not "tautology") or prove/disprove that it is a theorem? Or if you're not sure, what is it that you know so far, and what kind of methods are you expected to use?

 

[MathematicalPhysicist]

it's my mistake, it should be "simplify". (it has gone wrong in my interpratation from hebrew to english).
ok, so i get the first question, but what about the second one how do i formulate it?

 

[MathematicalPhysicist]

you know,i still need the help about question two, and how to formulate the proof?
:zzz:

 

[AKG]

2) prove/disprove:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
which means to prove that the double implication is tautology.

Do we agree, first of all, that the sentence isn't always true, so we'll be proving it's not a "tautology?" So you're either asked to prove that it is not a theorem, or that it is not valid. I'm not sure how, in general, to prove something is not a theorem unless you prove that it's not valid and use the Soundness Theorem (which states that if something is a theorem, then it is valid, i.e. if it's not valid it's not a theorem). If you're not allowed to do that, then I don't know what to do. On the other hand if you're just asked to show that it is not valid, then you simply have to construct an interpretation on which the sentence is false. You've been given a good hint from honestrosewater, all you have to do is formalize what he said into a proof. But that's your homework, not ours.

 

[MathematicalPhysicist]

so let see if i figured it out:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
i need to prove/disprove the sentence.
lets assume:
ExAyp(x,y) is true.
then there's a specific x=a
so
EaAyp(a,y) is true.
the sentence "AyExp(x,y)" is actually "~Ey~Axp(x,y)"
and by the contrapositive we can see that is only one way material implication and not double material implication.

therefore the sentence isn't correct.

should i say q.e.d or it's not formalise as it should? :zzz:

 

[AKG]

the sentence "AyExp(x,y)" is actually "~Ey~Axp(x,y)"

No it's not.

and by the contrapositive we can see that is only one way material implication and not double material implication.

The contrapositive of what? Also, looking at something and seeing that a certain implication holds doesn't count as proof that a different implication doesn't hold. By the way, "double material implication" is simply called "material equivalence."

Anyways, the only way I can think to do this is to come up with a counterexample. There is a formal way to come up with a counterexample (it involves producing a structure which does not model the sentence), but the informal way should be fine if you haven't learned anything about models. I believe honestrosewater has already given you a counterexample.

 

[MathematicalPhysicist]

so counterexample, is what called a formal proof in maths.
blamy, i didn't know that.
thank you, very much.
have a nice day/evening/midday.
|-: