Tutorial 8

1

There exists x that for all y, P(x,y) is true.

1. False, consider when P(x, y) = false.
2. False,
3. True, there must exist at least one scenario where P(x, y) is true.

title: Correct answers.

2

“It is false that ‘for all x, there exists y P(x,y)’”

1. $\exists x\neg \forall yP(x,y)$ = $\neg \neg \exists x\neg \forall yP(x,y)$ = $\neg \forall x\neg \neg \forall yP(x,y)$ = $\neg \forall x\forall yP(x,y)$ Not equivalent.
2. $\forall x\neg \exists yP(x,y)$ = $\neg \neg \forall x\neg \exists yP(x,y)$ = $\neg \exists$ Not equivalent.
3. $\exists x\forall y\neg P(x,y)$ = $\neg \neg \exists x\forall y\neg P(x,y)$ = $\neg \forall x\neg \forall y\neg P(x,y)$ = $\neg \forall x\neg \neg \exists yP(x,y)$ = $\neg \forall x\exists yP(x,y)$ Equivalent.
4. $\exists x\exists y\neg P(x,y)$ = $\neg \neg \exists x\exists y\neg P(x,y)$ = $\neg \forall x\neg \exists y\neg P(x,y)$ = $\neg \forall x\neg \neg \forall yP(x,y)$ = $\neg \forall x\forall yP(x,y)$ Not equivalent.

title: Correct answers.

3

Use successive equivalence to show the following are equivalent:

$$\begin{array}{rl}LHS& =\neg \exists x\forall y(\neg P(x)\wedge (Q(y)\to R(x,y)))\\ RHS& =\forall x(P(x)\vee \exists y(Q(y)\wedge \neg R(x,y)))\end{array}$$ $$\begin{array}{rl}LHS& =\neg \exists x\forall y(\neg P(x)\wedge (Q(y)\to R(x,y)))\\ & =\neg \exists x(\neg P(x)\wedge \forall y(Q(y)\to R(x,y)))\\ & =\neg \neg \forall x\neg (\neg P(x)\wedge \forall y(Q(y)\to R(x,y)))\\ & =\forall x\neg (\neg P(x)\wedge \forall y(Q(y)\to R(x,y)))\\ & =\forall x(P(x)\vee \neg \forall y(Q(y)\to R(x,y)))\\ & =\forall x(P(x)\vee \neg \neg \exists y\neg (Q(y)\to R(x,y)))\\ & =\forall x(P(x)\vee \exists y\neg (Q(y)\to R(x,y)))\\ & =\forall x(P(x)\vee \exists y\neg (\neg Q(y)\vee R(x,y)))\\ & =\forall x(P(x)\vee \exists y(Q(y)\wedge \neg R(x,y)))\\ & =RHS\text{ as required}\end{array}$$

title: Correct answers.

4

1. $\forall x\exists y(R(x)\to F(x,y))$
2. $\forall x(R(x)\vee L(x)\vee S(x))$
3. $\forall x(R(x)\to \forall y(R(y)\to \neg (F(x,y)\wedge F(y,x))))$
4. $\exists x(L(x)\to \exists yF(x,y))\wedge \exists x(L(x)\to \neg \exists yF(x,y))$ Note: This is $\exists$, should use $\wedge$ instead of $\to$.

5

• $\text{Vertex}(x)$: $x$ is a vertex of the graph
• $\text{Edge}(x,y)$: there is an edge between $x$ and $y$

Formula	${\mathcal{G}}_1$	${\mathcal{G}}_2$	${\mathcal{G}}_3$
i	$\top$	$\top$	$\top$
ii	$\top$	$\top$	$\top$
iii	$\perp$	$\top$	$\top$
iiii	$\perp$	$\perp$	$\top$