Is this the correct way to translate this formula into CN prenex form?

66 Views Asked by At

Is this the correct way to solve the following problem?

$$(∀x ∃y P( x, g (y, f(x)) ∨ ¬Q(z))) ∨ ¬∀x R(x,y)$$

  1. Import the negation.

$$(∀x ∃y P( x, g (y, f(x)) ∨ ¬Q(z))) ∨ ∃x ¬R(x,y)$$

  1. Substitute the x in R(x,y) to u, Substitute the y in R(x,y) to w

$$(∀x ∃y P( x, g (y, f(x)) ∨ ¬Q(z))) ∨ ∃u ¬R(u,w)$$

  1. Since there are no free occurrences of x and y, take out there quantifiers.

$$∀x ∃y (P( x, g (y, f(x)) ∨ ¬Q(z))) ∨ ∃u ¬R(u,w)$$

  1. Since there are no free occurrences of u, take out its quantifiers.

$$∀x ∃y ∃u(P( x, g (y, f(x)) ∨ ¬Q(z))) ∨ ¬R(u,w)$$

  1. Rearrange ()'s

$$∀x ∃y ∃u (P( x, g (y, f(x)) ∨ ¬Q(z) ∨ ¬R(u,w))$$

Thanks for your help!

1

There are 1 best solutions below

9
On BEST ANSWER

Perfect, except for parenthesis:

$$∀x ∃y \color{red}{(}P( x, g (y, f(x))\color{red}{)} ∨ ¬Q(z)) ∨ ¬∀x R(x,y)$$

  1. Import the negation.

$$∀x ∃y (P( x, g (y, f(x))) ∨ ¬Q(z)) ∨ ∃x ¬R(x,y)$$

  1. Rename bound variables: Change the second x to u, change the second y in to w

$$∀x ∃y (P( x, g (y, f(x))) ∨ ¬Q(z)) ∨ ∃u ¬R(u,w)$$

  1. Since there are no free occurrences of x and y $\color{red}{in ∃u ¬R(u,w)}$, take out $\color{red}{their}$ quantifiers.

$$∀x ∃y ((P( x, g (y, f(x))) ∨ ¬Q(z)) ∨ ∃u ¬R(u,w))$$

  1. Since there are no free occurrences of u $\color{red}{in (P( x, g (y, f(x))) ∨ ¬Q(z))}$, take out its quantifiers.

$$∀x ∃y ∃u((P( x, g (y, f(x))) ∨ ¬Q(z)) ∨ ¬R(u,w))$$

  1. Rearrange ()'s

$$∀x ∃y ∃u (P( x, g (y, f(x))) ∨ ¬Q(z) ∨ ¬R(u,w))$$