1、離散數(shù)學，第5講，第26課，Toe范式，要求：理解Toe范式、Toe合取范式和Toe析取范式的定義，將謂詞公式wffA轉(zhuǎn)化為Toe范式、Toe合取范式和Toe析取范式。學習本節(jié)的目的是掌握謂詞公式的標準化形式。強調(diào)：謂詞公式被更改為前束范式。綜述：(1)量詞和連詞的關(guān)系，(2)量詞的擴張/收縮規(guī)律，其中A(x)是包含個體變量x的任何謂詞公式，B是排除個體變量x的任何謂詞公式，(3)量詞和命題連詞之間的一些等價關(guān)系，量詞分布規(guī)律，(4)引導論元、范圍論元、約束論元、自由論元、量詞、引導論元、管轄論元、約束論元、自由論元，(5)約束論元重命名和自由論元包含在同一個公式中，一些個體論元同時表現(xiàn)為約束

2、論元和自由論元。為了避免混淆，我們可以更改約束參數(shù)的名稱或自由更改它。改變約束論元的名稱，會把個體論元和出現(xiàn)在量詞域約束中的相應(yīng)的引導論元變成從未出現(xiàn)在該域中的個體論元，其余的保持不變。自由變量元可以代替自由出現(xiàn)的單個變量，它可以是單個常數(shù)變量，也可以是與原子公式中所有單個變量不同的單個變量，它在任何地方都可以被代替。第2章謂詞邏輯)2。6普倫特范式，2.6前nex范式2.6.1前NEX范式2.6.2前NEX析取范式和前NEX合取范式，范式，2。6 Prenex范式)，2.6.1 Prenex范式定義了2.6.1:中的任何謂詞公式A，如果它具有以下形式：(x1) (x2) (xn)B，其中它可

3、以是量詞或量詞，而xi(i=1，n)是對象參數(shù)。它表明：的前束范式的量詞都在整個形式的開始，它們的范圍延伸到整個公式的末尾。示例1:xy (f (x) g (y) h (x，y) xy (f (x，y) g (y，z) x h (x，y，z)，定理2.5.1:任何謂詞公式都有前束范式如何找到前束范式：步驟1:深度否定。也就是說，利用量詞轉(zhuǎn)換公式，否定連詞深入到命題論證和謂詞填充詞的前面。步驟2:重命名。也就是說，通過使用名稱改變規(guī)則和替換規(guī)則來改變一些參數(shù)的名稱，從而消除混淆。第三步：向前移動量詞。也就是說，利用量詞范圍的收縮和擴張將量詞移到前面。這樣，就可以得到相當于公式的前束范式。例1，例

4、2，例3，例2在第73頁，公式(x) (y) (z) (p (x，z) p (y，z) (u) q (x，y，U)是前束范式，原始公式(x)(y(U)，(x) (y) (z) (u) (p (x，z) p (y，z) q (x，y，U)，第一步是否定深度和原始形式，第二步是改變它的名稱，以便使，示例3輸入公式，練習第75頁的問題(1 ),將約束變量x重命名為u，將約束變量y重命名為z，并將其轉(zhuǎn)換為toe-in范式，并在示例2:中找到以下公式的toe-in范式。，解：2.5.2 Prenex析取范式Prenex相干范式在預束范式的基礎(chǔ)上，可以定義預束解析(組合)取范式。定義2.6.2:中的任何謂

5、詞公式。如果它具有以下形式，則稱為toe合取范式：(x1)(x2)(xn)(a11a 12 a1 k1)(a21a 22 a2 k2)(am1a m2am km)，其中n大于或等于1，并且AIJ (j=1，ki，I=1，2，3，m)是原子謂詞公式或其否定形式。任何謂詞公式A如果具有以下形式，則稱為toe析取范式：(x1)(x2)(xn)(a11a 12 a1 k1)(a21a 22 a2 k2)(am1a m2am km)其中N大于或等于1，AIJ (j=1，ki，I=1，2，3，m) N)是一個對象參數(shù)。定理2.6.2:每一個謂詞公式都可以轉(zhuǎn)化為它的等價形式(組合)。2。腳趾合取范式的定義2

6、-6.2如果一個wffA具有下列形式，則稱它為腳趾合取范式：(QX1)(QX2)(QKXK)(A11a 12 a1L 1)，如公式，是腳趾合取范式，定理2-6.2中的每個wffA都可以轉(zhuǎn)化為它的等價腳趾合取范式。示例4將wffD:轉(zhuǎn)換為其等效的toe合取范式。第一步是取消多余的量詞，第二步是改名，第三步是消除條件連詞，第四步是加深否定，第五步是把量詞推到左邊，(x) (z) (w) (p (x) r (x，w) (q (z，y) r (x，w)。如果它有下列形式：(q1x 1)(q2x 2)(qkxk)(a11a 12 a1 1)(a21a 22 a2 2)(am1a m2am lm)，其中Qi(1ik)是量詞或，(i=1，2，n)是賓語引數(shù)，Aij是原子公式或其否定式。如公式，是腳趾析取范式。)，定理2-6.3每個wffA都可以轉(zhuǎn)化為它的等價toe析取范式。示例4將w