I'm having a hard time with these 2 problems.

http://i53.tinypic.com/doneb4.gif

http://i51.tinypic.com/2u6eoh2.gif

I could tip 3$US for your help. If it's against the rules let me know and I'll edit my post.

Printable View

- Sep 21st 2010, 03:43 PMZathanSets and logic [SOLVED]
I'm having a hard time with these 2 problems.

http://i53.tinypic.com/doneb4.gif

http://i51.tinypic.com/2u6eoh2.gif

I could tip 3$US for your help. If it's against the rules let me know and I'll edit my post. - Sep 21st 2010, 04:41 PMemakarov
You could consider the domain to be a group of people and P(x,y) to mean "x knows y". Try to figure out, provided the first proposition is true, whether the second proposition is always true, is always false, or can be either.

Also, if is false, it means that is true. You can move the negation inside, i.e., put it in front of . Then it is easier to compare the two formulas. Moving negation inside is also useful in problem #2. (*Edit: Disregard the following*. Basically, it reduces to question whether implies . To answer it, it is important to know if the domain is empty.) - Sep 21st 2010, 05:49 PMZathan
Is it correct to say (for #1): AxEy P(x,y) can be false. If we let the domain of discourse be the persons: Roger, John, Tony and let P(x,y) be the statement "x knows y". Then ExAy P(x,y) is true, but AxEy P(x,y) is false ?

- Sep 22nd 2010, 12:04 AMemakarovQuote:

If we let the domain of discourse be the persons: Roger, John, Tony and let P(x,y) be the statement "x knows y". Then ExAy P(x,y) is true, but AxEy P(x,y) is false

*can*be false is not the whole answer: it is not clear if it is*always*false under the given assumption or if it can be true as well. However, the idea is right: by varying who knows whom, you can construct situations where ExAy P(x,y) is false (hence, the assumption is true), and AxEy P(x,y) is true in some situations and false in others. - Sep 22nd 2010, 12:10 AMTikoloshe
First, before addressing the problem as stated, I think the crucial point is that as long as , you may use the following theorems (which are really the same theorem in disguise):

So for example in your first problem, you use theorem 2 followed by theorem 1 (written with judicious use of parentheses).

.

Unfortunately, what you assume ( ) does not imply anything about the statement you are given to evaluate ( ). This most likely means that your question is mis-worded. This can be seen further by specifying two examples for P which exhibit opposite behavior.

Let . Let . Then it is clear that your assumption holds: the statement “there exists an x such that for all y, x is less than y” is false. Again, this is the same thing as asserting . Now, one may evaluate the statement “for all x, there exists a y such that x < y” as being true. Thus, is true.

Now, with the same D, let . Then it is clear that your assumption holds: the statement “there exists an x such that for all y, y-squared is -1” is false. Again, this is the same thing as asserting . Now, one may evaluate the statement “for all x, there exists a y such y-squared is -1” as being false. Thus, is false.

So question 1 as given has no correct answer (your assumption tells you nothing about the truth or falsehood of the statement you wish to evaluate).

You can do similar analysis to show that question 2 is also mis-worded. You may, however, be able to show the converse using the following theorem (assuming a non-empty domain): - Sep 22nd 2010, 02:16 AMemakarov
Well, let's see. The fact holds without the assumption that the domain is nonempty. I agree that in problem 1, the second formula can be true in some interpretations and false in others. However, in problem 2, the second formula is false (provided the first one is false). Here the fact that the domain is nonempty is essential because otherwise the second formula is vacuously true.