Logical statements with multiple quantifiers - discrete math

Question

So I have some questions below that I don't understand because I'm struggling with solving questions that involve multiple quantifiers. I was wondering if someone could walk me through how to do these? I need help especially with 2) because I don't even understand the context of that question. I'm confused by the universe of discourse being { a, b, c }, and I don’t know what that means or how to take that knowledge and apply it to getting a solution.

For 1, I think I can solve it if there wasn't the added statement 'K(x, y) denote "x knows y"'. The answer I came up with is ∀x(C(x)→∃x(H(x))) but I’m not sure how the “x knows y” details change that answer.

1. Let H(x) denote "x is a hockey player", C(x) denote "x is a hockey coach", O(x) denote "x is a person in Ottawa", and K(x, y) denote "x knows y". State the universe of discourse and translate the following proposition into a predicate logic formula: "Every hockey coach in Ottawa knows at least one hockey player in Ottawa."

2. Let the universe of discourse be { a, b, c }. Write out the following propositions explicitly so that they do not contain any universal or existential quantifiers:

   a. ∀x Ǝy F(x, y)

   b. Ǝx ∀y F(x, y)

   c. ¬(∀x Ǝy F(x, y))

Answer 1

$\newcommand{\sem}[1]{[\![#1[\!]}$ The universe of discourse is the same as what is sometimes called the domain in a structure $\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$, where $\mathcal{D}$ is the domain/universe of discourse and $\mathcal{I}$ is the interpretation of the non-logical symbols (= predicates, function symbols, individual constants) of the formal language.

The universe of discourse is the set of objects that are being talked about, or more precisely the domain that variables are interpreted into:
For any variable $x$, the interpretation of $x$ relative to an assignment function $v$ and structure $\mathcal{M}$, denoted $\sem{x}_{v,\ \mathcal{M}}$, is given by $v(x)$, where $v$ is an assignment function

$$v: VAR \to \mathcal{D}$$

i.e. a function that maps each variable to an element in the universe of discourse.
So the elements of $\mathcal{D}$ are the concrete objects which the terms (amongst others, variables) of the language are interpreted as.

• $\forall x \phi(x)$ is true iff every way of mapping $x$ to discourse elements $a \in \mathcal{D}$ makes $\phi$ true for that particular $a$, thus $\forall x \phi(x)$ means that $\phi$ applies to all elements in $\mathcal{D}$.
• $\exists x \phi(x)$ is true iff there is at least one way of mapping $x$ to a discourse element $a \in \mathcal{D}$ such that $\phi$ is true of $a$, thus $\exists x \phi(x)$ means that $\phi$ applies to at least one element in $\mathcal{D}$.

Hint for 2.:

• $\forall$ corresponds to conjunction between all discourse elements: $\forall x \phi(x) \equiv \phi(a_1) \land ... \land \phi(a_n)$, where $\{\sem{a_1}_{\mathcal{M}}, ..., \sem{a_n}_{\mathcal{M}}\} = \mathcal{D}$
• $\exists$ corresponds to disjunction between all discourse elements: $\exists x \phi(x) \equiv \phi(a_1) \lor... \lor \phi(a_n)$, where $\{\sem{a_1}_{\mathcal{M}}, ..., \sem{a_n}_{\mathcal{M}}\} = \mathcal{D}$

(where $\mathcal{D}$ is the universe of discourse)

Now you just need to figure out how to combine these paraphrases when you have nested quantifiers (like $\forall x \exists y$).

The quantifier-less paraphrase for a. would be (where the constant symbol $a$ denotes the object $a$, $b$ denotes $b$ and $c$ denotes $c$):

$(F(a,a) \lor F(a,b) \lor F(a,c)) \land (F(b,a) \lor F(b,b) \lor F(c,c)) \land (F(c,a) \lor F(c,b) \lor F(c,c))$

Can you infer from this how the other examples should go?