勵志

勵志人生知識庫

前束範式公式

前束範式(prenex normal form)是數理邏輯中使用謂詞邏輯所描述的形式語言的一種格式。它具有以下特點:

所有量詞(∀和∃)都出現在公式的最前端,未被否定。

量詞的轄域延伸至公式的末端,即覆蓋了公式中的所有內容。

一個公式如果滿足上述條件,就可以被稱為前束範式。例如,公式 \((\forall x)(\exists y)P(x,y)\) 就是前束範式,因為它符合量詞在前,轄域覆蓋整個公式的特點。

要將一個公式轉換為前束範式,可以使用以下方法:

消去公式中的聯結詞 → 和 ↔。

將公式內的否定符號深入到謂詞變元前並化簡,確保謂詞變元前只有一個否定號。

利用改名、代入規則使所有的約束變元均不同名,且使自由變元與約束變元亦不同名。

擴充量詞的轄域至整個公式。

通過這些步驟,可以將任一謂詞公式化成前束範式。例如,公式 \((\forall x)P(x) \lor (\exists y)Q(y)) \rightarrow (\forall x)R(x)\) 可以轉換為 \((\forall x)(\forall z)(P(x) \lor Q(y)) \rightarrow R(z)\),其中 \(z\) 是新引入的變元,用於擴展量詞的轄域。