Homework Help: Propositional Functions

1. Jul 8, 2013

Bashyboy

1. The problem statement, all variables and given/known data
Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”)

a) Every student in this class has taken exactly two mathematics classes at this school.

b)Someone has visited every country in the world except Libya.

c) No one has climbed every mountain in the Himalayas.

d)Every movie actor has either been in a movie withKevin Bacon or has been in a movie with
someone who has been in a movie with Kevin Bacon.

2. Relevant equations

3. The attempt at a solution

I just simply wanted to know if I was beginning correctly.

For a), would the statement translate into $\forall x \exists ! y \exists ! z ((S(x,y) \wedge S(x,z)) \implies (y \ne z$, where S(x,y) is, " Student x has taken mathematics course y"?

For b), would the statement translate into $\exists x \forall y ((V(x,y) \wedge \neg V(x, Lybia))$, or would it be $\exists x \forall y ((V(x,y) \wedge y \ne ~Lybia)$, where V(x,y) is, "x has visited country y."?

Last edited: Jul 8, 2013
2. Jul 8, 2013

verty

These questions are difficult and you probably aren't allowed to use E!. I think you may be advancing too quickly because these questions rely on everything that came before, you need to know everything that came before. I would actually read everything from the start, start with truth tables and read everything again, you'll get more from it this time because it'll be familiar, and try to understand everything before advancing. But the time you get back to these questions, you'll be ready for them.

3. Jul 8, 2013

Bashyboy

So, are you suggesting that my translations are incorrect? And why would I not be permitted to use the unique existential quantifier?

4. Jul 10, 2013

ArcanaNoir

I think you are lacking a component in your solutions that specifies the set from which your x, y, or z come from.
(changed my example statement)
For example, if I wanted to write: "Everyone in my class has exactly one ipod" I might set it up like this:

Let C be the set of my classmates.
Let I be the set of ipods.
$$\forall c \in C, \; \; \exists ! \; i \in I : S(c,i)$$ where S(c,i) means i belongs to c.

Last edited: Jul 10, 2013
5. Jul 10, 2013

verty

I just want to show how these forms relate to each other. $$\forall c \in C, \; P(c)$$ is shorthand for $$\forall c (c \in C → P(c))$$ is shorthand for $$\forall c (\in(c,C) → P(c))$$.

If we write C(c) instead of $\in(c,C)$, we have $$\forall c (C(c) → \exists! i \; (I(i) \wedge S(c,i)))$$ as a variant of $$\forall c \in C, \; \; \exists ! \; i \in I : S(c,i)$$.

Logically they are the same, the difference is a matter of style. The first is expressed in a language with only variables and predicates, nothing more fancy than that. This is good when one is learning about logic itself, about how ideas are expressed by means of the logical operators.

The second form is more readable, using symbols from set theory. We can see here that set theory is either an extension or a specialization of logic, contingent on whether set membership is thought of as a predicate or not.