Goundoubuf

Answered

2022-11-25

What does it mean when x is 'free'?

In the context of first-order logic and resolution (I'm trying to study Skolemization for a midterm tomorrow), I am seeing several references to $x$ being free or not free. What does this mean?

To pull all quantifiers in front of the formula and thus transform it into a prenex form, use the following equivalences, where $x$ is not free in Q:

Edit:

$\mathrm{\forall}xP(x)\wedge \mathrm{\exists}xQ(x)\equiv \mathrm{\forall}x(P(x)\wedge \mathrm{\exists}xQ(x))\equiv \mathrm{\forall}x(P(x)\wedge \mathrm{\exists}yQ(y))\equiv \mathrm{\forall}x\mathrm{\exists}y(P(x)\wedge Q(y)).$

If the second x is bound by the existential quantifier - why can it be pulled into prenex form if the blurb above says that this can be done only if x is not free? Or am I misunderstanding something?

Edit 2:

OK, i'm clearly not all here at the moment. Ignore that question

In the context of first-order logic and resolution (I'm trying to study Skolemization for a midterm tomorrow), I am seeing several references to $x$ being free or not free. What does this mean?

To pull all quantifiers in front of the formula and thus transform it into a prenex form, use the following equivalences, where $x$ is not free in Q:

Edit:

$\mathrm{\forall}xP(x)\wedge \mathrm{\exists}xQ(x)\equiv \mathrm{\forall}x(P(x)\wedge \mathrm{\exists}xQ(x))\equiv \mathrm{\forall}x(P(x)\wedge \mathrm{\exists}yQ(y))\equiv \mathrm{\forall}x\mathrm{\exists}y(P(x)\wedge Q(y)).$

If the second x is bound by the existential quantifier - why can it be pulled into prenex form if the blurb above says that this can be done only if x is not free? Or am I misunderstanding something?

Edit 2:

OK, i'm clearly not all here at the moment. Ignore that question

Answer & Explanation

Bryson Carlson

Expert

2022-11-26Added 10 answers

A variable ${x}_{1}$ in a formula $\varphi ({x}_{1},{x}_{2},\cdots ,{x}_{n})$ is called bound if ${x}_{1}$ is contained in some sub-formula of the form $\mathrm{\forall}{x}_{1}(\psi ({x}_{1},\cdots ))$. If ia variable is not bound, it is free. That is, a variable is free if it is not being quantified over, so that it is "free" to assume different values. On the other hand, if a variable is being quantified over, it is almost like a placeholder -- it doesn't make sense to try and input different values for that variable.

With regards to your second question, since $x$ is bound it is not free.

With regards to your second question, since $x$ is bound it is not free.

armlanna1sK

Expert

2022-11-27Added 1 answers

$x$ is free in $Q$ if it is not quantified over.

So in the ${L}_{Ring}$ formula $x=1$, $x$ is free.

But in the ${L}_{Ring}$ formula $\mathrm{\forall}x(x=1)$, $x$ is not free (in which case we call $x$ bound)

So in the ${L}_{Ring}$ formula $x=1$, $x$ is free.

But in the ${L}_{Ring}$ formula $\mathrm{\forall}x(x=1)$, $x$ is not free (in which case we call $x$ bound)

Most Popular Questions