Kanonický tvar formule

Formule v predikátové logice je v kanonickém tvaru, pokud

1. žádná proměnná, která se ve formuli vyskytuje jako volná, se v ní nevyskytuje jako vázaná,
2. za každým kvantifikátorem je jiná proměnná.

Ke každé formuli existuje ekvivalentní formule v kanonickém tvaru. Každou formuli $F$ lze převést do kanonického tvaru vhodným přejmenováním vázaných proměnných.

Příklad

$F:=\forall x\exists y\left(P\left(x,y\right)\wedge Q\left(x,z\right)\right)$

$G:=\exists u\left(\forall vP\left(u,v\right)\vee Q\left(v,v\right)\right)$

Ve formuli $F$ jsou proměnné $x$ a $y$ vázané a proměnná $z$ volná. $F$ je tedy kanonická. Ve formuli $G$ jsou všechny výskyty proměnné $u$ vázané, ale výskyty proměnné $v$ jsou jak vázané tak volné. $G$ proto není v kanonickém tvaru. Výsledkem převodu $G$ do kanonického tvaru je formule (vzniklá přejmenováním vázaných proměnných):

$G':=\exists u\left(\forall wP\left(u,w\right)\vee Q\left(v,v\right)\right)$

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Bereinigte Normalform na německé Wikipedii.

Související články

• Kanonický tvar