定義
一個公式,如果量詞均在全式的開頭,它們的作用域延伸到整個公式的末端,則該公式叫做 前束範式(Prenex Normal Form)。
![前束範式](/img/b/af6/wZwpmL2MDOwQzMyADOzYTN1UTM1QDN5MjM5ADMwAjMwUzLwgzL1IzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![前束範式](/img/7/0ef/wZwpmL3EzM5EDMzYDM3QTN1UTM1QDN5MjM5ADMwAjMwUzL2AzL0IzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![前束範式](/img/b/643/wZwpmL0IDOzAzN1UTMxMzM1UTM1QDN5MjM5ADMwAjMwUzL1EzL4AzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![前束範式](/img/0/5f7/wZwpmLwADO1kDOxITMzEzM1UTM1QDN5MjM5ADMwAjMwUzLyEzLyQzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![前束範式](/img/4/913/wZwpmLyEjM0IzM4YzMwEDN0UTMyITNykTO0EDMwAjMwUzL2MzLygzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
前束範式可記為下述形式 ,其中 為 或 , 為個體變元,A是沒有量詞的謂詞公式。
![前束範式](/img/4/11f/wZwpmL3UzN1YDO1kDM0YTN1UTM1QDN5MjM5ADMwAjMwUzL5AzL1czLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![前束範式](/img/a/550/wZwpmLzgTOyYzMxMDOxUTN1UTM1QDN5MjM5ADMwAjMwUzLzgzL1gzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
例如, 等都是前束範式,而 等都不是前束範式。
![前束範式](/img/b/af6/wZwpmL2MDOwQzMyADOzYTN1UTM1QDN5MjM5ADMwAjMwUzLwgzL1IzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
定義 設P是具有形式 的前束範式,若A是合取範式,則稱P為 前束合取範式;若A是析取範式,則稱P為 前束析取範式。
利用換名規則、代替規則、量詞的否定公式及量詞轄域的擴張與收縮公式等,可以將任一謂詞公式化成前束範式。
定理
任何一個謂詞公式,均和一個前束範式等價。
![前束範式](/img/0/252/wZwpmL0EzN1YjN0EzNxUTN1UTM1QDN5MjM5ADMwAjMwUzLxczL2AzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![前束範式](/img/4/11f/wZwpmLxQDNzMTM1EzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLxczLwgzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
證明 首先利用量詞轉化公式,把否定深入到命題變元和謂詞填式的前面,其次,利用 和 把量詞移到全式的最前面,這樣便得到前束範式。
求前束範式的過程
求一個謂詞公式的前束範式的過程為:
![前束範式](/img/2/37d/wZwpmLygDM3gTO2MDM0YTN1UTM1QDN5MjM5ADMwAjMwUzLzAzLxczLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![前束範式](/img/e/de0/wZwpmLxcDO0MTN0ETOzYTN1UTM1QDN5MjM5ADMwAjMwUzLxkzLwQzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![前束範式](/img/2/29a/wZwpmLwMTM0IzM4QTOwADN0UTMyITNykTO0EDMwAjMwUzL0kzLzMzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![前束範式](/img/a/9f1/wZwpmLxQTO1UjMxQTM2EzM1UTM1QDN5MjM5ADMwAjMwUzL0EzL1UzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
(1)通過利用公式 及 消去渭詞公式中的聯結詞 和 ;
![前束範式](/img/2/c26/wZwpmLzcDM3ITN5QDOwMzM1UTM1QDN5MjM5ADMwAjMwUzL0gzL2gzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
(2)消去 ;
(3)否定深入,即利用量詞轉化公式把否定聯結詞深入到命題變元和謂詞填式的前面;
(4)運用換名規則和代替規則,將公式中所有變元均用不同的符號;
(5)量詞前移,即利用量詞轄域的擴張把量詞移到前面。
例題解析
求下列公式的前束範式:
![前束範式](/img/0/d11/wZwpmL1cTN1YDO2kTOzYTN1UTM1QDN5MjM5ADMwAjMwUzL5kzL0IzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
(1)
![前束範式](/img/e/778/wZwpmL1YDNwQzM5gDOzYTN1UTM1QDN5MjM5ADMwAjMwUzL4gzLyUzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![前束範式](/img/9/848/wZwpmL4UzN0YDM1IzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLyczL0QzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
或者
![前束範式](/img/e/385/wZwpmLxIjNxEjMzIDOxUTN1UTM1QDN5MjM5ADMwAjMwUzLygzLxIzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
從(1)中可以看出一個公式的前束範式不是唯一的。
![前束範式](/img/7/9bb/wZwpmLxgDO4cTOzkzNzYTN1UTM1QDN5MjM5ADMwAjMwUzL5czLwMzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
(2)
![前束範式](/img/e/7d0/wZwpmL2QDM0MjM4UDM0YTN1UTM1QDN5MjM5ADMwAjMwUzL1AzLzIzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![前束範式](/img/1/1f7/wZwpmL1EzM2UTMzUDNxUTN1UTM1QDN5MjM5ADMwAjMwUzL1QzL0czLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![前束範式](/img/5/1cd/wZwpmL3MDN5ITNzEDOzYTN1UTM1QDN5MjM5ADMwAjMwUzLxgzLxczLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![前束範式](/img/c/0eb/wZwpmL1cTNyIjNxADOzYTN1UTM1QDN5MjM5ADMwAjMwUzLwgzLwAzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![前束範式](/img/f/efc/wZwpmLzgjN5kDMyADOzYTN1UTM1QDN5MjM5ADMwAjMwUzLwgzLxgzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)