Quantifier evaluation using translation to english

Question

Which one of the following well-formed formulae is a tautology?
$\hspace {2pt}$ a)$\forall x \exists y R(x,y) \leftrightarrow \exists y \forall x R(x,y) $
$\hspace{2pt}$b)$\forall x[\exists y\hspace{1pt} R(x,y)\rightarrow S(x,y)]\rightarrow \forall x \exists y \hspace{1pt} S(x,y)$
$\hspace{2pt}$c)$\forall x \exists y[P(x,y)\rightarrow R(x,y)]\leftrightarrow \forall x\exists y(\neg P(x,y) \lor R(x,y))$
$\hspace{2pt}$d)$\forall x \forall y P(x,y)\rightarrow \forall x \forall y P(y,x)$

Now, let x be set of all boys, y be set of all girls, R(x,y): x loves y P(x,y): x knows y S(x,y); x marries y, then
a) Every boy loves some girl is not equivalent to Some girl is loved by every boy
b)For every boy, if he loves a girl then he marries that girl doesnot imply Every boy marries a girl as in the left side, a boy might love some girl but get married to some one else.
c) RHS is the expansion of implication.
d) Every boy knows every girl doesn't imply Every boy is known by Every girl
Is this correct way to interpret?

For option d, i am taking quantifier to have highest precedance, is that ryt? — Curious, Mar 04 '18 at 05:35
Can you clarify what you mean by taking quantifier to have the highest precedance? Your interpretation: Every boy knows every girl doesn't imply every boy is known by every girl is correct since x comes before y — Jesse Meng, Mar 04 '18 at 05:41
@JesseMeng Order of operations Implication is evaluated after quantifiers unless bracetted. — Graham Kemp, Mar 04 '18 at 06:00

score 0 · Accepted Answer · answered Mar 04 '18 at 05:47

Now, let x be set of all boys, y be set of all girls, R(x,y): x loves y, P(x,y): x knows y, S(x,y): x marries y, then

For a start, you don't declare different implicit domains for entities outside the statement; the literals are untyped. Well, we'll let that slide this time.

a)$\hspace {2ex}\forall x ~\exists y~ R(x,y) ~\leftrightarrow~ \exists y ~\forall x~R(x,y) $

a) Every boy loves some girl is not equivalent to Some girl is loved by every boy

$\color{red}\checkmark$ Okay

b)$\quad\forall x~[\exists y~ R(x,y)\rightarrow S(x,y)]\rightarrow \forall x ~\exists y ~ S(x,y)$

Order of operations places $S(x,y)$ outsode the scope of the first existential. Assuming that is unintentional, the brace should occur after the quanitfication rather than before.

$$\quad\forall x~\exists y~ [R(x,y)\rightarrow S(x,y)]~~\rightarrow~~\forall x ~\exists y ~ S(x,y)$$

b)For every boy, if he loves a girl then he marries that girl doesnot imply Every boy marries a girl as in the left side, a boy might love some girl but get married to some one else.

$\color{red}\chi$ No, that's not the reason it is not a tautology. What you need to consider is that not every boy may love some girl.

c)$\quad\forall x~\exists y~[P(x,y)\to R(x,y)]~\leftrightarrow~ \forall x~\exists y~(\neg P(x,y) \lor R(x,y))$

c) Both are negation of one another.

$\color{red}\chi$ No, they are not. Try again.

d)$\qquad\forall x~\forall y~P(x,y)~~\rightarrow~~\forall x~\forall y~P(y,x)$

d) Every boy knows every girl doesn't imply Every boy is known by Every girl

Is this correct way to interpret?

$\color{red}\checkmark$ Indeed, that is okay.

I have edited translation of c, thanks for pointing out, it was unintentional — Curious, Mar 04 '18 at 05:52

Quantifier evaluation using translation to english

1 Answers1