[subject]/[topic]

Az informatika logikai alapjaikimaradt

Kötött és szabad változók

Mikor szabad és mikor kötött egy változó előfordulása, nyitott és zárt formulák, változóiban tiszta formula, és a kötött változók átnevezése.

Forrás: eloadas02-2026.pdf, eloadas03-2026.pdf

Szabad és kötött előfordulás

A kvantor egy változót „leköt” egy részformulán belül, ez a kvantor hatásköre. Ugyanaz a változó egy formulában többször is előfordulhat, és az előfordulások különbözőek lehetnek.

Definíció

Legyen AA formula, xx változó. xx egy előfordulása AA-ban

  • szabad, ha nem esik AA egyetlen ∀xB\forall x B vagy ∃xB\exists x B alakú részformulájába sem;
  • kötött, ha nem szabad.
Definíció · nyitott és zárt formula
  • AA nyitott, ha legalább egy változó legalább egy helyen szabadon fordul elő benne.
  • AA zárt, ha minden változó minden előfordulása kötött.

Miért fontos? Egy zárt formulának egy interpretációban egyértelmű igazságértéke van. Egy nyitott formula igazságértéke attól is függ, mit jelölnek a szabad változói (lásd Interpretáció). A „xx páros” se nem igaz, se nem hamis, amíg nem tudjuk, mi az xx.

Példák az előadásból

Példa

∀y ¬∃x(P(f(x))∨Q(x,y))\forall y\, \neg \exists x (P(f(x)) \vee Q(x, y))

A ∃x\exists x hatásköre az egész (P(f(x))∨Q(x,y))(P(f(x)) \vee Q(x, y)), a ∀y\forall y hatásköre minden utána következő. Minden előfordulás kötött, a formula zárt.

Példa

∀y (¬∃xP(f(x))∨Q(x,y))\forall y\, (\neg \exists x P(f(x)) \vee Q(x, y))

Most a ∃x\exists x csak a P(f(x))P(f(x))-re vonatkozik (a kvantor a legerősebben köt). A Q(x,y)Q(x, y)-beli xx ezért szabad, az yy kötött. A formula nyitott.

Ugyanazok a jelek, más zárójelezés: egészen más formula.

Változóiban tiszta formula

Definíció

Egy formula változóiban tiszta, ha

  • nincs olyan változó, amely szabadon és kötötten is előfordul, és
  • különböző kvantorok különböző változókat kötnek.
Példa

∀x(P(x)⊃Q(x,y))∧R(x)\forall x (P(x) \supset Q(x, y)) \wedge R(x) nem tiszta: az xx az első részben kötött, az R(x)R(x)-ben szabad.

A kötött változók átnevezésével tisztává tehető: ∀z(P(z)⊃Q(z,y))∧R(x)\forall z (P(z) \supset Q(z, y)) \wedge R(x). Az átnevezés nem változtat a jelentésen, ha új (sehol nem szereplő) változónevet választunk, és a kvantorral együtt az összes általa kötött előfordulást átírjuk. Az így kapott formulák kongruensek.

Figyelem

Szabad változót nem szabad átnevezni: P(x)P(x) és P(y)P(y) más-más dolgot állít. Csak a kvantor által kötött változók neve „mindegy”, mint egy függvény paraméterének a neve a programban.

Próbáld ki

Minden kvantor saját színt kap, és az általa kötött előfordulások ugyanazt a színt viselik. Ha az egeret egy színes jelre viszed, a többi elhalványul. A szabad előfordulás piros, hullámos aláhúzással.

Interaktív

Elsőrendű formula vizsgálata

Minden kvantor saját színt kap, és az általa kötött változók is ezt a színt viselik; a szabad előfordulás piros. Változók: x y z v w (számmal is), más kisbetűs szó név (pl. u), kisbetű + ( függvény, nagybetű predikátum. Írhatsz forall x / exists x-et is.

Példák:
∀y(¬∃x P(f(x)) ∨ Q(x,y))
nyitott / zárt
nyitott
szabad változók
x
kötött változók
x, y
változóiban tiszta?
nem x szabadon és kötötten is előfordul. Nevezd át a kötött változókat!
fő logikai jel
∀y
közvetlen részformulák
(¬∃x P(f(x)) ∨ Q(x, y))
összetettség
4
P(f(x))∃x¬Q(x, y)∨∀y

Gyakorló feladatok

Gyakorló feladat

Melyik előfordulás szabad, melyik kötött? Zárt-e a formula? Tiszta-e?

∃x∀yR(x,y)⊃∀x(P(x)∧Q(y))\exists x \forall y R(x, y) \supset \forall x (P(x) \wedge Q(y))
Megoldás

Az első részben xx és yy is kötött. A második részben a P(x)P(x)-beli xx kötött (a második ∀x\forall x köti), a Q(y)Q(y)-beli yy viszont szabad, mert az első ∀y\forall y hatásköre csak R(x,y)R(x, y)-ig tart. A formula nyitott és nem tiszta: yy szabadon és kötötten is előfordul, és az xx-et két kvantor is köti. Írd be a vizsgálóba így: exists x forall y R(x,y) -> forall x (P(x) & Q(y)).