姜譽(yù)

摘 ? ?要：一階謂詞邏輯推理是數(shù)理邏輯教學(xué)的重要內(nèi)容之一。在一階謂詞邏輯推理教學(xué)中，保證量詞引入規(guī)則、量詞消去規(guī)則的內(nèi)容與形式的統(tǒng)一性對(duì)學(xué)生正確接受和理解推理過(guò)程具有重要作用。文章從離散數(shù)學(xué)教學(xué)實(shí)踐出發(fā)，介紹一階謂詞邏輯推理中的存在量詞引入規(guī)則與量詞消去規(guī)則的教學(xué)策略。

關(guān)鍵詞：離散數(shù)學(xué);存在量詞;規(guī)則

中圖分類號(hào)：G642.0 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ?文章編號(hào)：1002-4107（2015）12-0003-02

離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程等本科專業(yè)的一門(mén)基礎(chǔ)課程，而數(shù)理邏輯是離散數(shù)學(xué)課程中的一個(gè)重要組成部分，對(duì)提高學(xué)生理解和構(gòu)造數(shù)學(xué)證明的能力以及培養(yǎng)學(xué)生的計(jì)算思維（computational thinking）具有重要作用[1-2]。

命題邏輯和一階謂詞邏輯是數(shù)理邏輯教學(xué)內(nèi)容中的兩個(gè)部分。一階謂詞邏輯通過(guò)引入量詞來(lái)表達(dá)個(gè)體與總體之間的內(nèi)在聯(lián)系與數(shù)量關(guān)系[3]，從而克服了命題邏輯中無(wú)法表達(dá)數(shù)量關(guān)系的局限性。

量詞包括全稱量詞和存在量詞。全稱量詞表達(dá)個(gè)體域中的所有個(gè)體，通常用符號(hào)“ ? ”表示;存在量詞表達(dá)個(gè)體域中的單個(gè)個(gè)體，通常用符號(hào)“ ? ”表示。一般用小寫(xiě)字母a、b、c等符號(hào)表示個(gè)體常元，用小寫(xiě)字母x、y、z等符號(hào)表示個(gè)體變?cè)?，用大?xiě)字母A、B、C、P、Q、R等符號(hào)表示謂詞。在謂詞公式 ? xP（x）或 ? xP（x）中，x是約束變?cè)卜Q變?cè)獂是約束出現(xiàn)，這時(shí)的P（x）稱為 ? x或

x的轄域;如果謂詞公式Q（y）中不存在變?cè)獃的約束出現(xiàn)，則稱變?cè)獃在Q（y）中自由出現(xiàn)，或稱y是自由變?cè)Ｔ谥^詞公式 ? x ? yP（x，y）或 ? x ? yP（x，y）中，變?cè)獂在 ? x或 ? x的轄域內(nèi)是約束出現(xiàn)，但在 ? y或 ? y的轄域內(nèi)是自由出現(xiàn)。

一階謂詞邏輯推理系統(tǒng)除了具有與命題邏輯推理中一樣推理規(guī)則之外，還有4條與量詞的引入和消去有關(guān)的規(guī)則，分別是全稱量詞引入規(guī)則（簡(jiǎn)記為 ? +或UG）、全稱量詞消去規(guī)則（簡(jiǎn)記為 ?-、UI或US）、存在量詞引入規(guī)則（簡(jiǎn)記為 ?+或EG）、存在量詞消去規(guī)則（簡(jiǎn)記為 ?-、EI或ES）。量詞引入也稱為量詞泛化，量詞消去也稱為量詞實(shí)例化或指定。這4條與量詞有關(guān)的引入和消去規(guī)則極大地豐富了一階謂詞邏輯推理的表達(dá)能力。

在量詞引入規(guī)則和量詞消去規(guī)則的教學(xué)中，保證量詞引入規(guī)則以及量詞消去規(guī)則的內(nèi)容與形式的統(tǒng)一性對(duì)學(xué)生正確理解和接受推理規(guī)則及推理過(guò)程具有重要作用，否則容易引起學(xué)生理解上的困惑。

一、現(xiàn)有的規(guī)則

我們以文獻(xiàn)[3]中關(guān)于存在量詞引入規(guī)則（ ?+或EG）和存在量詞消去規(guī)則（ ?-、EI或ES）為例進(jìn)行說(shuō)明。文獻(xiàn)[3]是普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材，具有代表性。在文獻(xiàn)[3]中給出的全稱量詞引入規(guī)則和全稱量詞消去規(guī)則的內(nèi)容與形式是統(tǒng)一的，不存在理解上的困惑。

文獻(xiàn)[3]給出的存在量詞引入規(guī)則（ ?+或EU）形式為：

或 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

以及

或 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

其中，x、y是個(gè)體變?cè)?hào)，c是個(gè)體常元符號(hào)。應(yīng)用該規(guī)則的前提要求是：在謂詞公式A中，變?cè)獃不在 ? x和 ? ?x的轄域內(nèi)自由出現(xiàn)，常元c不在 ? x和 ? x的轄域內(nèi)出現(xiàn)。

在上述式（1）這對(duì)表述中，第一個(gè)表述成立的依據(jù)是公式A（c）→ ? xA（x）永真，因此有A（c） ? ? ? ?xA（x）;第二個(gè)表述成立的依據(jù)是假言三段論規(guī)則：（B→A（c））∧（A（c）→ ? xA（x）） ? ? B→ ? xA（x）。式（2）的情形類似。 我們看到，這個(gè)規(guī)則稱為“存在量詞引入規(guī)則”，其推理結(jié)果在形式上也體現(xiàn)了存在量詞 ? ，規(guī)則的內(nèi)容與符號(hào)形式是統(tǒng)一的，學(xué)生易于理解和接受。

然而，文獻(xiàn)[3]給出的存在量詞消去規(guī)則（ ? -或EI）的形式為：

或 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

以及

或 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

其中，y是個(gè)體變?cè)?hào)，c是個(gè)體常元符號(hào)，應(yīng)用該規(guī)則的前提要求是：變?cè)獃不在推理的任何前提公式以及謂詞公式B中自由出現(xiàn)，常元c不在推理的任何前提公式以及謂詞公式 ? xA（x）及B中出現(xiàn)。

我們看到，在這個(gè)稱為“存在量詞消去規(guī)則”的推理結(jié)果形式中反而出現(xiàn)了存在量詞 ? ，使得規(guī)則的內(nèi)容與符號(hào)形式不統(tǒng)一，導(dǎo)致學(xué)生理解上的困惑。

實(shí)際上，在上述式（3）這對(duì)表述中，第一個(gè)表述可以當(dāng)作一條存在量詞引入規(guī)則;該表述成立的依據(jù)是假言三段論規(guī)則：

（ ?xA（x）→A（c））∧（A（c）→B） ? ? ? ?xA（x）→B。其中，常元c是滿足謂詞公式 ?xA（x）的個(gè)體。

而式（3）中的第二個(gè)表述在本質(zhì)上不是消去存在量詞，而是得出結(jié)論B，其成立的依據(jù)實(shí)質(zhì)上是假言推理規(guī)則，即：

（ ?xA（x）→A（c））∧（ ?xA（x）） ? ? A（c）

以及

A（c）∧（A（c）→B） ? ? B。

其中，常元c是滿足謂詞公式 ?xA（x）的個(gè)體。因此，在該規(guī)則描述中的第二個(gè)表述其實(shí)是不必要的，可以從該規(guī)則中刪去。

類似地，在式（4）這對(duì)表述中，第一個(gè)表述也可以當(dāng)作一條存在量詞引入規(guī)則;考慮到變?cè)獃的任意性，該表述成立的依據(jù)是假言推理規(guī)則（ ?xA（x）→A（c））∧

（ ?xA（x）） ? ? A（c）、化簡(jiǎn)規(guī)則A（y）→B ? ?A（c）→B以及假言三段論規(guī)則（ ?xA（x）→A（c））∧（A（c）→B） ? ? ? xA（x）→B 。

其中，常元c是滿足謂詞公式 ?xA（x）的個(gè)體。

式（4）中的第二個(gè)表述在本質(zhì)上也不是消去存在量詞，而是得出結(jié)論B，其成立的依據(jù)實(shí)質(zhì)上是假言推理規(guī)則（ ?xA（x）→A（c））∧（ ?xA（x）） ? ? A（c）、化簡(jiǎn)規(guī)則A（y）→B ? ?A（c）→B以及假言推理規(guī)則A（c）∧（A（c）→B）

B。其中，常元c是滿足謂詞公式 ? xA（x）的個(gè)體。因此，該表述其實(shí)也是不必要的，可以從該規(guī)則中刪去。

二、修改后的規(guī)則

為了保證規(guī)則內(nèi)容與形式的統(tǒng)一性，我們可以將式（3）的第一個(gè)表述以及式（4）的第一個(gè)表述納入到存在量詞引入規(guī)則中，這種做法

其中，x、y是個(gè)體變?cè)?hào)，c是個(gè)體常元符號(hào)。應(yīng)用該規(guī)則的前提要求是：應(yīng)用式（5）或（7）時(shí)要求常元c、變?cè)獃分別不在公式A中 ? x和 ? x的轄域內(nèi)出現(xiàn)和自由出現(xiàn);應(yīng)用式（6）或（8）時(shí)要求常元c、變?cè)獃分別不在公式A中 ? x和 ? x的轄域內(nèi)、公式B以及推理的任何前提公式中出現(xiàn)和自由出現(xiàn)。

在修改后的存在量詞引入規(guī)則（ ?+或EU）中，式（5）的第二個(gè)表述和式（7）的第二個(gè)表述可以看成是在蘊(yùn)含式的后件引入存在量詞的情形，式（6）和式（8）的表述可以看成是在蘊(yùn)含式的前件引入存在量詞 ? 的情形。這些表述具有內(nèi)容與形式的統(tǒng)一性，便于學(xué)生理解和記憶，可以根據(jù)不同情形選擇使用。

那么，存在量詞消去規(guī)則應(yīng)具有怎樣的形式呢？我們可如下表述存在量詞消去規(guī)則（ ? -、EI或ES）：

其中，c是個(gè)體常元符號(hào)。應(yīng)用該規(guī)則前二個(gè)表述的前提要求是：常元c是滿足公式 ? xA（x）的個(gè)體。

在修改后的存在量詞消去規(guī)則（ ?-、EI或ES）中，當(dāng)常元c是滿足公式 ? xA（x）的個(gè)體時(shí)，式（9）中第一個(gè)表述成立的依據(jù)是公式 ?xA（x）→A（c）為永真式，因此有

xA（x） ? ?A（c）;第二個(gè)表述成立的依據(jù)是假言三段論規(guī)則：

（B→ ? xA（x））∧（ ?xA（x）→A（c）） ? ? B→A（c）。第三個(gè)表述成立的依據(jù)是假言三段論規(guī)則：

（A（c）→ ?xA（x））∧（ ?xA（x）→B） ? ?A（c）→B 。

與對(duì)修改后的存在量詞引入規(guī)則（ ?+或EU）形式的看法類似，在修改后的存在量詞消去規(guī)則（ ?-、EI或ES）中，第二個(gè)表述可以看成是在蘊(yùn)含式的后件消去存在量詞 ? 的情形，第三個(gè)表述可以看成是在蘊(yùn)含式的前件消去存在量詞 ? ?的情形，這樣更便于學(xué)生理解和記憶。修改后的存在量詞消去規(guī)則（ ?-、EI或ES）也是對(duì)文獻(xiàn)[4]中對(duì)應(yīng)規(guī)則的進(jìn)一步擴(kuò)充。

綜上所述，在一階謂詞邏輯推理中，我們應(yīng)保證規(guī)則的內(nèi)容與形式的統(tǒng)一性，使學(xué)生正確理解和接受相應(yīng)的推理規(guī)則，合理構(gòu)造推理過(guò)程，從而有利于培養(yǎng)學(xué)生的計(jì)算思維能力以及提高學(xué)生的推理能力。

參考文獻(xiàn)：

[1]Kenneth H.Rosen. Discrete mathematics and its

applications（7th Ed.）[M].McGraw-Hill（Asia）

Education Press，2012：xvi.

[2]Jeannette M.Wing. Computational thinking[J].

Communications of the ACM，2006，49（3）：33-35.

[3]屈婉玲，耿素云，張立昂.離散數(shù)學(xué)（第二版）[M].北京：

高等教育出版社，2015：60，81.

[4]左孝凌，李為鑑，劉永才.離散數(shù)學(xué)[M].上海：上?？茖W(xué)

技術(shù)文獻(xiàn)出版社，1982：76.