離散數學知識點總結-謂詞邏輯

目錄

• 1.謂詞邏輯基本概念
• 2.量詞
• 謂詞公式：
• 量詞的作用域
• • 一、量詞的作用域
  • 自由變元與限制變元
  • 換名規則
• 謂詞演算中的命題符号化
• • 三種基本類型
  • 舉例
• 謂詞演算的等價與蘊含
• 有限個體域下的量詞消去公式
• 量詞轉換率
• 量詞作用域的擴充與收縮
• 量詞的配置設定公式
• 前束範式

1.謂詞邏輯基本概念

能夠獨立存在的具體或抽象的事物，稱之為個體，也稱之為客體。通常用小寫英文字母a、b、c…表示

例如：小張、小李、8，a，沈陽，社會主義都是客體。

個體常項:具體的或特定的個體。常用a,b,c,…等小寫字母表示

個體變元:泛指某一個個體。常用x,y,z,…等小寫字母表示

謂詞：用以刻化個體屬性或者表達個體之間關系的詞，即為謂詞。謂詞用大寫字母表示。

謂詞也有常項與變項之分。表示具體性質與關系的謂詞稱為謂詞常項。泛指某–性質或關系的謂詞稱為謂詞變項。

将不帶個體變元的謂詞稱為0元謂詞。例如，S(a)， G(3,7) 等。當謂詞是常項時，0元謂詞是命題;否則當謂詞是變項時，0 元謂詞是命題變元。

含有n個變元的命題函數是以個體域為定義域，以{ F,T }為值域的n元函數。

注意:命題函數本身并不是命題，隻有在括号内填入足夠的具體客體，或用足夠的量詞限制後才變成命題。

個體變元的取值範圍，稱之為個體域，也稱之為論域。

由所有個體構成的個體域，稱之為全總個體域。它是“最大的個體域。

約定:對于一個命題函數，如果沒有指明其個體域，則假定其個體域是全總個體域。

2.量詞

在命題中，表示對個體量化的詞，稱之為量詞。例如:有些人是大學生。所有事物都是發展變化的。有些“所有的”就是對個體量化的詞。

有兩種量詞

量詞的指導變元:量詞後邊要有一個個體變元，指明對哪個個體變元進行量化，稱此個體變元是指導變元。

當F是謂詞常項時，∀xF(x) 是一個命題。

例：所有的自然數都是整數

若沒設個體域，即個體域為全總個體域，則需用特性謂詞加以限定。

設N(x): X是自然數(特性謂詞)。l(x): x是整數。此命題可以寫成∀x(N(x)→l(x))。

有些大學生吸煙。∃x(S(x)∧A(x))

特性謂詞:一般來說，特性謂詞是描述個體特征的謂詞，往往就是給定命題中量詞後邊的那個名詞。

比如:有些大學生吸煙中，有些後面的大學生是特性謂詞。

特性謂詞的添加規則:

對全稱量詞，特性謂詞常作蘊涵前件。

對存在量詞，特性謂詞常作合取項。

分析一-下特性謂詞和原謂詞所表達概念之間的關系:對于全稱量詞:例如，所有的自然數都是整數。

令N:自然數集合，|:整數集合。

對于存在量詞:例如，有些大學生吸煙。令S:大學生集合，A:煙民的集合。

每個人都有一個生母：

設P(x):x是人，M(x,y):y是x的生母

∀x(P(x)→∃y(P(y)∧M(x,y)))

謂詞公式：

原子謂詞公式：稱n元謂詞P(x1,x2,…xn)為原子命題公式

例如P,Q(x),B(x,y,a)都是原子謂詞公式

謂詞合式公式定義：

二、謂詞合式公式

定義(1) 原子謂詞公式是合式公式。

(2)如果A是合式公式，則¬A也是合式公式。

(3)如果A、B是合式公式，則(A∧B)、(A∨B)、(A→B)、(A<->B)都是合式公式。

(4)如果A是合式公式，x是A中的個體變元，則∀xA和∃xA也是合式公式。

(5)隻有有限次地應用(1)至(4)得到的符号串才是合式公式。

合式公式也稱為謂詞公式，簡稱公式。

下面都是合式公式:

注意:若量詞後邊有括号，則此括号不能省略。例如上述公式3中量詞括号不能省略。

量詞的作用域

一、量詞的作用域

量詞的作用域(轄域)：在謂詞公式中，量詞的作用範圍稱之為量詞的作用域，也叫量詞的轄域。

一般地：

如果量詞後邊隻是一個原子謂詞公式時，該量詞的轄域就是此原子謂詞公式。例如: ∀xA(x)

如果量詞後邊是括号，則此括号所表示的區域就是該量詞的轄域。例如: ∃x(A(x)→B(x))

如果多個量詞緊挨着出現，則後邊的量詞及其轄域就是前邊量詞的轄域。

例如:∀x∃y∀z(A(x,y)→B(x,y,z))∧C(t)

自由變元與限制變元

在謂詞公式中的個體變元可以分成兩種，一種是受到量詞限制的，一種是不受量詞限制的。

定義:如果客體變元x在∀x或者∃x的轄域内，則稱x在此轄域内限制出現，并稱x在此轄域内是限制變元。否則x是自由出現，并稱x是自由變元。

注意：(1)一個n元謂詞P(x1…xn), 若在前邊添加k個量詞，使其中的k個個體變元變成限制變元，則此n元謂詞就變成了n-k元謂詞。

(2)一個謂詞公式如果無自由變元，它就表示一個命題。

y既是自由變元，也是限制變元。為避免混淆，需要對限制變元換名。

換名規則

限制變元的換名規則:設A為一謂詞公式，将A中某量詞轄域内的一個限制變元的所有出現及相應的指導變元全部改成A中沒出現過的某個變元符号，A中其餘部分不變，所得公式為A’，則A⇔A’。

對自由變元也可以換名，此換名叫代入。

自由變元的代入規則:設A為一謂詞公式，将A中某個自由出現的個體變元的所有出現用某個A中沒出現過的變元符号代替，A中其餘部分不變，記所得公式為A’，則A⇔A’。

謂詞演算中的命題符号化

三種基本類型

命題的符号化表達式與個體域有關系。而個體域的指定需随題目而定。能指定個體域的當然要指定，這樣會使表達式變得簡。若不指定個體域，則為全總個體域。

在謂詞演算中，最基本的命題符号化就三種類型:

1、主語、賓語是具體個體對象的，用謂詞加括号，括号裡是具體個體表示。

2、描述所有的、任意的個體對象，用全稱量詞，特性謂詞作蘊含前件。

若寫成∃x(M(x)∧F(x))則表示宇宙間的所有個體都是人并且都會呼吸

3、描述一些客體對象， 用存在量詞，特性謂詞作合取項。

若寫成∀x(M(x)→F(x))則表達宇宙間存在某個個體，若這個個體是人，則它用左手寫字

舉例

不是所有的自然數都是偶數

N(x):x是自然數，E(x):x是偶數

¬(∀x(N(x)→E(x)))

不是所有的按照字面直接翻譯，為¬∀x

這句話也等價于存在一些自然數不是偶數

∃x(N(x)∧¬E(x))

沒有不犯錯誤的人

M(x):x是人，F(x):x會犯錯誤

¬∃x(M(x)∧¬F(x))

這句話也等價于：所有的人都會犯錯誤

(∀x(M(x)→F(x)))

所有大學生都喜歡一些歌星

S(x):x是大學生，G(x):x是歌星，L(x,y):x喜歡y

∀x(S(x)→∃y(G(y)∧L(x,y)))

每個自然數都有唯一的後繼數

在有些命題中，某些個體對象的量詞沒有明确給出，要仔細分析并寫出這些隐含的量詞。

金子發光，但閃光的不一定都是金子

令G(x):x是金子，F(x):x閃光

命題表達為：

∀x(G(x)→F(x))∧¬∀x(F(x)→G(x))

或者

∀x(G(x)→F(x))∧¬∃x(F(x)∧¬G(x))

命題的符号表達式中所有個體變元必須都是限制變元，才表示命題。即在命題的符号表達式中，一定沒有自由變元。

謂詞演算的等價與蘊含

命題邏輯中命題有兩個真值，可以畫真值表

對謂詞公式指派(給謂詞公式一個解釋)

對一個謂詞公式指派由如下四部分組成:

(1)指定非空個體域集合;

(2)将謂詞公式中的命題變元，用确定的命題替代;

(3)對公式中的個體變元用論域中的具體個體替代;

(4)對公式中含有的謂詞變項，用謂詞常項替代。

例:給公式P→N(x)作指派。

個體域:實數集合;

P:2>1;

N(x): x是自然數; x=4.是它的一個指派:此公式變成T→ N(4),它的真值為T

一個不含自由變元的謂詞公式是命題。而含有n個自由變元的原子謂詞公式，可以看成是命題變元。是以隻要不牽涉到量詞的運算，命題演算中的等價公式和重言蘊含公式均可推廣到謂詞演算中使用。

謂詞公式的永真式

給定謂詞公式A,如果不論對其作任何指派，都使得謂詞公式A的真值為真，則稱A為永真式。

例如，公式l(x)∨¬l(x)

謂詞公式的等價公式:給定謂詞公式A、B，如果A<->B是永真式，則稱A與B等價，記作A⇔B.

等價于說，如果不論對A、B作任何同樣的指派,A與B的真值都相等，則A與B等價。例如，N(x)→l(x)⇔N(x)∨l(x)。

給定謂詞公式A、B,如果A→B為永真式，則稱A永真蘊含B，記作A=>B。

有限個體域下的量詞消去公式

有限個體域消去量詞的等價公式，設論域為{a1,a2…an},.則

1. ∀xA(x)⇔A(a1)∧A(a2)∧A(a3)…∧A(an)

2. ∃xA(x)⇔B(a1)∨B(a2)∨B(a3)…∨B(an)

   謂詞邏輯與命題邏輯的差別在于命題的表達不同。謂詞公式與命題公式的最大差別在于多了量詞,

   

   

量詞轉換率

謂詞邏輯與命題邏輯的差別在于命題的表達不同。謂詞公式與命題公式的最大差別在于多了量詞，而所有的命題表達式都可以表示成隻含有聯結詞∧∨¬的表達式，是以隻要研究清楚量詞與∧∨¬之間的關系，謂詞表達式的運算也就清楚

一、量詞否定等價公式（量詞與¬的關系）

直覺解釋:

“并不是所有的x都有性質A’”與“存在x沒有性質A”是一個意思。

不存在有性質A的X與“所有x都沒有性質A’是一個意思。

例:令A(x)表示:x是天才，個體域: {我們班}

¬∀xA(x)表示:不是我們班所有同學都是天才。

∃x¬A(x)表示:我們班有些同學不是天才。

¬∃xA(x)表示:我們班沒有同學是天才。

∀x¬A(x)表示:我們班所有同學都不是天才。

可見，這是符合我們思維習慣的。

量詞作用域的擴充與收縮

量詞轄域的擴充與收縮研究的是量詞與∧∨的關系，其中一個運算對象不受該量詞限制，有如下公式:

其它公式:

量詞轄域的擴充和收縮，當隻有一個運算對象受量詞限制時，如果中間連接配接詞時析取合取，加不加括号都沒影響。如果中間連接配接詞時蘊含，量詞提前不說影響，但是上面這種情況注意，這裡把則劃開，是要加非的，∀xA(x)→B,等價于¬∀xA(x)∨B。比如：如果所有人都到齊了，我們就開會，等價于要麼不是所有人都到期了，要麼開會（說明都到齊了）。或者我們可以把非移動到量詞符号的右邊，量詞變為存在兩次，要麼有人沒來，要麼開會。

量詞的配置設定公式

若兩個運算對象均受同一個量詞限制，量詞與“v，^”運算是什麼關系?有如下的量詞

配置設定公式:

可用公式1來證明公式2

舉例說明公式3：

任意x合取（聯想個體域消去），存在x析取都是等價配置設定，但是任意x析取，存在x合取都是隻有蘊含關系。

前束範式

前束範式—所有量詞都在公式前邊。

前束範式的定義：

如果一個謂詞公式符合下面條件，它就是前束範式：

所有量詞前面都沒有聯接詞;所有量詞前面都沒有聯接詞;所有量詞的轄域都延伸到公式的末尾。

求前束範式的步驟:

1)消去公式中的聯接詞和->,<->(為了便于量詞轄域的和擴充)

2)如果量詞前有¬,用量詞轉化率将¬後移。

3)用限制變元的改名規則或自由變元的代入規則對變元換名(為量詞轄域擴充做準備)。

4)用量詞轄域擴充公式提取量詞，使之成為前束範式的形式。