Ugrás a tartalomhoz

Prenex-formula

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

Egy formula prenex-alakúvá tételéhez először változó-tiszta alakra kell hozni a formulát.

Változótiszta alak

[szerkesztés]

Minden kvantor különböző változót köt, és egyik kötött változó sem egyezik meg egyetlen szabad változóval sem. Az a legegyszerűbb megoldás, hogy indexeljük a kötött változókat. Ha változótiszta lett a formula, utána alkalmazni kell a kvantorkiemelési törvényeket.

Egyoldali kvantorkiemelési törvények

[szerkesztés]

∀xA(x) ∧ B ∼ ∀x(A(x) ∧ B)
A ∧ ∀xB(x) ∼ ∀x(A ∧ B(x))

∃xA(x) ∨ B ∼ ∃x(A(x) ∨ B)
A ∨ ∃xB(x) ∼ ∃x(A ∨ B(x))

¬∀xA(x) ∼ ∃x¬A(x)
¬∃xA(x) ∼ ∀x¬A(x)

A ⊃ ∃xB(x) ∼ ∃x(A ⊃ B(x))
A ⊃ ∀xB(x) ∼ ∀x(A ⊃ B(x))

∃xA(x) ⊃ B ∼ ∀x(A(x) ⊃ B)
∀xA(x) ⊃ B ∼ ∃x(A(x) ⊃ B)

∀xf(x) = ⌐∃x ⌐f(x)