Prenex-formula

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

∀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)