數(shù)學(xué)語言與證明方法

1、第一章 數(shù)學(xué)語言與證明方法1集合的概念和運(yùn)算（4學(xué)時(shí)）【教學(xué)目的】了解、掌握集合的基本概念及例子【教學(xué)要求】掌握集合的基本概念及例子；掌握集合五種運(yùn)算和集合相等證明；【教學(xué)重點(diǎn)】掌握集合五種運(yùn)算和集合相等證明；【教學(xué)難點(diǎn)】如何正確的證明集合之間包含和相等關(guān)系【教學(xué)方法】講練結(jié)合教學(xué)法、提問式與啟發(fā)式相結(jié)合教學(xué)法?！窘虒W(xué)手段】傳統(tǒng)板書與多媒體課件輔助教學(xué)相結(jié)合?！菊n型】新授課教學(xué)過程集合是一切數(shù)學(xué)的基礎(chǔ)，每一門數(shù)學(xué)的討論都離不開集合，為此，我們必須掌握集合的基本定義及運(yùn)算規(guī)律，掌握集合的證明方法，這對(duì)于學(xué)習(xí)離散數(shù)學(xué)將有極大的幫助。除此以外，在離散數(shù)學(xué)中，序列、整除、矩陣也將是十分重要的基礎(chǔ)知識(shí)。

2、下面就從6個(gè)知識(shí)點(diǎn)來加以闡述。1.1 集合與元素集合是任意客體(對(duì)象)的聚集?？腕w稱為這個(gè)集合的“成員”或“元素”，元素a要么屬于集合A，要么不屬于集合A,記為：a此時(shí)，要充分的認(rèn)識(shí)“任意客體”和“聚集”的含義。1.2 集合與集合的關(guān)系 (1) B包含A中（或A包含B）,記為BA（2）集合A與集合B相等，記為A=B. 此時(shí)，兩個(gè)集合各自包含的對(duì)象一一對(duì)應(yīng)相等（或者說完全相等），該定義稱為集合的外延性定理。，此時(shí)，也稱集合B不是集合A的子集。（4）集合A與集合B不相等，記為AB。 (5) 集合B真包含在集合A中或集合A真包含集合B,記為B。 ，此時(shí)，也稱集合B是集合A的真子集。 （6）集合B不被

3、A所真包含， 在集合中，常常涉及到集合之間的包含與集合之間相等的證明。證明時(shí)，常依據(jù)上述定義，采用離散數(shù)學(xué)中特有的按定義證明方法來加以證明。由于離散數(shù)學(xué)中的很多定義，都是由兩部分構(gòu)成，即“如，則”，我們把定義中的前半部分叫“已知”，后半部分叫“結(jié)論”，所以，所謂按定義證明方法就是首先敘述出你所要證明問題的定義，利用定義中的“已知”條件，加上題目中的其他的已知條件，推出定義中的“結(jié)論”。1.3 特殊的集合(1) 空集：不含任何元素的集合叫做空集，記為。空集是絕對(duì)唯一的，且是任何集合的子集。證明一個(gè)集合是空集，或證明集合的唯一性，常采用反證方法，即假設(shè)該集合不是空集，或不唯一，導(dǎo)致與已知條件的矛盾

4、或?qū)е挛ㄒ?。?） 全集：在一個(gè)具體的問題中，所研究的集合都是某個(gè)固定集合的子集，則稱這個(gè)固定集合為全集，記為E或U。全集僅是相對(duì)唯一的。（3） 冪集：任一集合A的一切子集作為元素所構(gòu)成的稱謂A的冪集，記為P（A）， 顯然|A|P（A）|，由此可知，集合中不存在最大的集合。1.4 集合的運(yùn)算與定律1. 集合的運(yùn)算 集合的基本運(yùn)算有并，交，差，補(bǔ)，對(duì)陳差，其定義如下： 2. 運(yùn)算的定律 1.5 有窮集合的計(jì)數(shù) 解決有窮集合的計(jì)數(shù)問題有兩種方法：文氏圖法和包含排斥原理。 設(shè)S是有窮集，p1,p2,pm是m條性質(zhì)，S中的任何元素x對(duì)于對(duì)于性質(zhì)pi(i=1,2,m)具有或者不具有，兩種情況必居其一。令

5、表示S中不具有性質(zhì)pi的元素構(gòu)成的集合，則包含排斥原理可描述為： 1.6 無限集合 1 可數(shù)無限集合 自然數(shù)集合N=0，1，2，是一個(gè)可數(shù)（可列）無限集合，凡是與自然數(shù)集合等勢(shì)的集合就是可數(shù)無限集合。如整數(shù)集合、奇數(shù)集合、偶數(shù)集合、素?cái)?shù)集合有理數(shù)集合等。2.不可數(shù)集合 開區(qū)間（0，1）稱為不可數(shù)集合，凡與（0，1）等勢(shì)的集合都是不可數(shù)集合，如閉區(qū)間0，1，實(shí)數(shù)集合、無理數(shù)集合、復(fù)數(shù)集合等。 3.有限集合和無限集合的重要差別 （1）兩個(gè)有限集合等勢(shì)當(dāng)且僅當(dāng)它們有相同個(gè)數(shù)的元素； （2）有限集合不和其任何真子集等勢(shì)； （3）無限集合可以和其真子集等勢(shì)； （4）如A，B是兩個(gè)有限集合，且|A|=|B

6、|，則A=B。1.7 序列 1.序列 一個(gè)序列就是按某種順序排列的一張表。 2.增序列 設(shè)S是一個(gè)序列，如對(duì)任意的n，有：SnSn+1 ,則序列S稱為增序列；如對(duì)任意的n,有Sn+1Sn，則序列S稱為減序列。 3.子序列 對(duì)于n=m,m+1,令Sn是一個(gè)序列，且令n1,n2,n3,是一個(gè)增序列，對(duì)于所有的值在m,m+1,.中的k值，滿足nk<nk+1,我們稱序列Snk是Sn的一個(gè)子序列。 4.序列的運(yùn)算 如是一個(gè)序列，則 式子稱為和符號(hào)，而式子稱為積符號(hào)，i稱為下標(biāo)，m稱為下界，n稱為上界。1.8 整除 1. 數(shù)的定義與表示 如果n和m是整數(shù)，且n>0，則有m=qn+r,其中q,r

7、是整數(shù)，且0。q稱為商，r稱為余數(shù)。 一個(gè)大于1的正整數(shù)p被稱為素?cái)?shù)，如果僅有p自身和數(shù)字1能整除p. 2. 最大公因子 如果a,b和k都是正整數(shù)，且k|a,k|b,則稱k是a和b的公因子。如果d是最大的這種k,則d被稱為最大公因子，記為 d=GCD(a,b)如果a,b是任何正整數(shù)，且GCD(a,b)=1，則我們稱互質(zhì)的。 3最小公倍數(shù) 如果a,b和k都是正整數(shù)，且a|k,b|k,則稱k是a和b的公倍數(shù)。如果c是最小的這種k,則c被稱為最小公倍數(shù)，記為 C=LCM(a,b)1.10 總結(jié)通過本章的學(xué)習(xí)，應(yīng)達(dá)到下面的基本要求：（1） 能正確地表示一個(gè)集合，會(huì)畫文氏圖；（2） 能判定元素是否屬于給

8、定的集合；（3） 能利用安定以證明法證明兩個(gè)集合之間的包含、相等、和真包含的關(guān)系；（4） 能熟練地作集合之間的并、交、差、補(bǔ)和對(duì)稱差運(yùn)算，掌握集合運(yùn)算的定律；（5） 能熟練地計(jì)算P（A）；（6） 能求解與有窮集合計(jì)數(shù)相關(guān)的實(shí)際問題；（7） 會(huì)求序列與子序列，并能進(jìn)行序列的運(yùn)算；（8） 能熟練地將一個(gè)數(shù)分解成素?cái)?shù)的積，并能求兩個(gè)數(shù)的最大公因子和最小公倍數(shù)；（9） 能熟練地進(jìn)行矩陣的各類運(yùn)算。第2章 命題邏輯命題邏輯(4學(xué)時(shí))【教學(xué)目的】介紹命題邏輯的基本概念。掌握利用命題邏輯表示自然語言，描述概念、判斷和推理。建立初步的語言形式化方法?！窘虒W(xué)要求】1識(shí)記命題表示方法、真值判斷、命題公式的遞歸定義

9、。2領(lǐng)會(huì)聯(lián)結(jié)詞真值確定、翻譯、命題公式的等價(jià)性和蘊(yùn)涵性證明、任給公式化為析取范式、任給公式化為主析取范式、任給公式化為合取范式、任給公式化為主合取范式。 3簡(jiǎn)單應(yīng)用命題邏輯推理規(guī)則【教學(xué)重點(diǎn)】掌握數(shù)理邏輯中命題的翻譯及命題公式的定義；利用真值表技術(shù)和公式轉(zhuǎn)換方式求公式的主析取范式和主合取范式；利用規(guī)則、基本等價(jià)和蘊(yùn)涵公式、三種不同的推理方法完成命題邏輯推理；【教學(xué)難點(diǎn)】如何正確地掌握對(duì)語言的翻譯，如何利用推理方法正確的完成命題推理【教學(xué)方法】講練結(jié)合教學(xué)法、提問式與啟發(fā)式相結(jié)合教學(xué)法?！窘虒W(xué)手段】傳統(tǒng)板書與多媒體課件輔助教學(xué)相結(jié)合?！菊n型】新授課教學(xué)過程課題導(dǎo)入數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的

10、形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科，它與數(shù)學(xué)的其他分支、計(jì)算機(jī)學(xué)科、人工智能、語言學(xué)等學(xué)科均有十分密切的聯(lián)系，并且益顯示出它的重要作用和更加廣泛的應(yīng)用前景。要很好地使用計(jì)算機(jī)，就必須學(xué)習(xí)邏輯。數(shù)理邏輯分五大部分。在離散數(shù)學(xué)中僅介紹命題邏輯和謂詞邏輯。命題邏輯是謂詞邏輯的基礎(chǔ)，只有掌握了命題邏輯，才能學(xué)好謂詞邏輯。對(duì)于命題邏輯，下面從六個(gè)知識(shí)點(diǎn)來加以闡述。1.1 命題符號(hào)化及聯(lián)系結(jié)詞1 命題有確切真值的陳述句稱為命題。所謂確切真值是指在具體的環(huán)境，具體的時(shí)間，具體的對(duì)象，具體的位置等情況下能唯一確定真值的。命題分為兩種：(1) 簡(jiǎn)單命題：不能分解為更為簡(jiǎn)單的句子的命題。(2) 復(fù)合命題：能夠分解為更為

11、簡(jiǎn)單的命題。2 命題聯(lián)結(jié)詞聯(lián)結(jié)詞記號(hào)復(fù)合命題讀法記法真值結(jié)果否定乛P是不對(duì)的P的否定乛P乛P為真當(dāng)且僅當(dāng)P為假合取P并且QP與Q的合取PQPQ為真當(dāng)且僅當(dāng)P，Q同為真析取P或者QP與Q的析取PQPQ為真當(dāng)且僅當(dāng)P，Q至少一個(gè)為真蘊(yùn)涵若P，則QP蘊(yùn)涵QPQPQ為假當(dāng)且僅當(dāng)P為真，Q為假等價(jià)P當(dāng)且僅當(dāng)QP等價(jià)于QP QP Q為真當(dāng)縣僅當(dāng)P，Q同為真假關(guān)于聯(lián)結(jié)詞，有如下幾點(diǎn)提醒大家注意：（1）此聯(lián)結(jié)詞是聯(lián)結(jié)的句子與句子之間的聯(lián)結(jié)，而非單純的名記號(hào)、形容詞、數(shù)詞等的聯(lián)結(jié)；（2）此聯(lián)結(jié)詞是兩個(gè)句子真值之間的聯(lián)結(jié)詞，而非句子的具體含義的聯(lián)結(jié)，兩句子之間可以無任何的內(nèi)在聯(lián)系；（3）聯(lián)結(jié)詞與自然語言之間的對(duì)應(yīng)

12、并非一一對(duì)應(yīng)，如合取聯(lián)結(jié)詞“”對(duì)應(yīng)了自然語言中的“既又”、“不僅而且”、“雖然但是”、“并且”、“和”、“與”等。如蘊(yùn)涵聯(lián)結(jié)詞“”，PQ對(duì)應(yīng)了自然語言中的“加P則Q”，“只要P就Q”，“P僅當(dāng)Q”，“只有Q才P”，“除非Q否則乛P”等。如等價(jià)聯(lián)結(jié)詞“ ”對(duì)應(yīng)了自然語言中的“等價(jià)”、“并且僅當(dāng)”、“充分必 ”等。如析取聯(lián)結(jié)詞是對(duì)應(yīng)相容的或(中兼的或)。2.2 命題公式及分類一般稱具有確切真值的簡(jiǎn)單命題叫命題常量，用P，Q，R，等表示。而沒有賦予具體內(nèi)容的簡(jiǎn)單命題稱為命題變量（變?cè)?，此時(shí)的P，Q，R沒有具體的真值。1合式公式（1）單個(gè)的命題變量或常量（含1或0）是合式公式；（2）若P是合式公式，

13、則（乛P）也是合式公式；（3）若P，Q是合式公式，則（PQ）、（PQ）、（PQ）、（P Q）也是合式公式。只有有限次使用上述三步形式的符號(hào)串才是合式公式（命題公式），簡(jiǎn)稱公式。為了簡(jiǎn)化公式，可按如下優(yōu)先級(jí)別進(jìn)行：“（）”“乛”“”“ ”其中，為避免錯(cuò)誤，合取與析取看成是同等優(yōu)先級(jí)別，要改變或強(qiáng)調(diào)其優(yōu)先級(jí)別，采用括號(hào)。另外，最外層的括號(hào)可以省掉，同級(jí)的按從左到右的順序進(jìn)行運(yùn)算。2賦值或解釋與真值表設(shè)G是命題公式，P1，P2，Pn (n/1)是出現(xiàn)在公式G中的所有命題變?cè)付≒1，P2，Pn一組真值，則這組真值稱為G的一個(gè)解釋或賦值。此時(shí)不同的賦值就有2n種。將此2n種不同的賦值下的取值情況列成

14、的表稱為G的真值表。3公式的分類設(shè)G為一公式，（1）如G在它所有的解釋之下都為真，則稱G為永真或重言式；（2）如G在它所有的解釋之下都為假，則稱G為永假或矛盾式；（3）如G在它所有的解釋之下至少有一個(gè)為真，則稱G為可滿足式。2.3 等價(jià)公式與演算1等價(jià)關(guān)系稱公式G，H是等價(jià)的，如果在其任意的解釋下，其真值相同，記為G=H。說明：G=H僅描述了兩公式G，H之間的一種等價(jià)的關(guān)系，G=H本身并非是一個(gè)公式，它不能作直接計(jì)算。要判斷G=H，可采用：G=H當(dāng)且僅當(dāng)公式G H 是一個(gè)永真式。2代入定理設(shè)G(P1，P2，Pn)是一個(gè)公式，G1(P1，P2，Pn)，Gn(P1，P2，Pn)為任意公式，若G是永

15、真式或永假式，則用G1，G2，Gn取代公式G中的P1，P2，Pn后而得的新公式G(G1，Gn)G(P1，P2，Pn)仍是一個(gè)永真式或永假式。3運(yùn)算定律設(shè)G，H，S是任意的公式，則有如下基本的運(yùn)算定律：（1）冪等律：GGG，GGG（2）結(jié)合律：(GH)SG(HS),（GH）SG（HS）（3）交換律：GHHG，GHHG（4）分配律：G（HS）（GH）（GS）， G（HS）（GH）（GS）（5）吸收律：G（GH）G，G（GH）G（6）同一律：G0=G，G1=G(0，1分別是關(guān)于運(yùn)行，的幺元)（7）零 律：G1=1，G0=0(0，1分別是關(guān)于運(yùn)算，的零元)（8）排中律，矛盾律：G乛G=1，G0=0(乛

16、G又叫做G的補(bǔ)元)（9）D，M律：乛(GH)=乛G乛H，乛(GH)=乛G乛H（10）雙重否定律：乛（乛G）G（11）蘊(yùn)涵等值式：GH乛GH（12）等價(jià)等值式：G H（GH）（HG）（乛GH）（乛HG）（13）假言易位：GH乛H乛G（14）等價(jià)否定等值式：G H乛G 乛H（15）歸謬論：(G H)(G 乛H)乛G其中：只要將運(yùn)處“乛”，“”，“”分別對(duì)應(yīng)集合中的運(yùn)算“”，“”、“”，真值“1”，“0”分別對(duì)應(yīng)集合中的全集E和空集，集合對(duì)應(yīng)于命題的公式，則定律(1)(10)就完全同集合中的定律(1)(10).另外,(11)(15)是命題邏輯中特有的公式,重點(diǎn)要求記住(11),(12).4等值演算利

17、用等值定律到已有的公式中而推演出新的公式的過程稱為等值演算。5置換規(guī)則設(shè)G(G1)是含子公式G1的公式，G(G2)是用G2置換了G(G1)之后的公式，若G1G2，則G(G1)G(G2)2.4 全功能聯(lián)結(jié)詞集1其他聯(lián)結(jié)詞表 2.2P QU0 0U10 1U21 0U31 1U4設(shè)P，Q為兩個(gè)命題元，U為其對(duì)應(yīng)的聯(lián)結(jié)詞，則U作用于P，Q后的真值表如表22所示。由組合的意義，U1，U2，U3，U4的不同真值結(jié)果有2416種，即從0000到1111，為此除已有的五個(gè)聯(lián)結(jié)詞以外，還需引入下面四個(gè)聯(lián)結(jié)詞如表23所示。表中，在邏輯電路中稱為異或門，與非門，或非門。2全功能聯(lián)合詞集合設(shè)S是聯(lián)結(jié)詞集合，用S中的

18、聯(lián)結(jié)詞可表示任何的命題公式；且從S中刪除任一個(gè)聯(lián)結(jié)詞后而得的新聯(lián)結(jié)詞集合S1，至少存在一個(gè)命題公式不能用S1中聯(lián)結(jié)詞表示。則稱S是一個(gè)全功能聯(lián)結(jié)詞集合。如乛，乛，乛，等都是全功能聯(lián)結(jié)詞集合。表 2.3聯(lián)結(jié)詞記號(hào)復(fù)合命題讀法記法真值結(jié)果異或G不可兼或HG異或HGHAH為真當(dāng)縣僅當(dāng)G.H不同為真假蘊(yùn)涵否定G與H的蘊(yùn)涵否定G蘊(yùn)涵否定HGHG H為真當(dāng)且僅當(dāng)G為真，H為假與非G與H的與非G與非HGHGH為假當(dāng)且僅當(dāng)G, H同為真或非G與H的或非G或非HGHGH為真當(dāng)且僅當(dāng)G，H同為假2.5 范式1. 析取范式和合取范式(1) 稱命題變?cè)蚱浞穸槲淖郑?2) 有限個(gè)文字的合取稱為短語；(3) 有限個(gè)文

19、字的析取稱為子句；(4) 有限個(gè)短詞的析取稱為析取范式；(5) 有限個(gè)子句的合取稱為合取范式。求一個(gè)公式G所對(duì)應(yīng)的析取、合取范式一般通過公式的等值演算而得到。2. 主析取范式和主合取范式(1) 在含有n個(gè)命題變?cè)狿1, P2, , Pn的公式中，一個(gè)短語或一個(gè)子句如果恰當(dāng)包括所有這n個(gè)命題變?cè)蚱浞穸?，且排列順序與P1, P2, , Pn一致，則稱此短語或子句為關(guān)于P1, P2, , Pn的一個(gè)有小項(xiàng)或極大項(xiàng)。此時(shí)極小項(xiàng)有2n個(gè)，極大項(xiàng)也有2n個(gè)；(2) 由有限個(gè)極小項(xiàng)組成的析取范式稱為主析取范式；(3) 由有限個(gè)極大項(xiàng)組成的合取范式稱為主合取范式。求一個(gè)公式G所對(duì)應(yīng)的主析取、主合取范式可采用

20、真值表技術(shù)、公式的等值演算、公式的主析取與主合取范式之間的轉(zhuǎn)換。其中，最方便、最直觀、最不易出錯(cuò)的方法是真值表技術(shù)。該方法為：設(shè)G（P1, P2, , Pn）是一個(gè)公式，建立該公式所對(duì)應(yīng)的真值表。(4) 在真值表中，公式G取值為真的所有行所對(duì)應(yīng)解釋之極小項(xiàng)的析取為該公式G的主析取范式。(5) 在真值表中，公式G取值為假的所有行所對(duì)應(yīng)解釋之極大項(xiàng)的合取為該公式G的主合取范式。其中，極小項(xiàng)與解釋之間的對(duì)應(yīng)為：如P值為0，在極小項(xiàng)中則還原為乛P，如P值取1，在有小項(xiàng)中則還原為1，如P,Q,R之解釋為010，則對(duì)應(yīng)的有小項(xiàng)為乛P乛Q乛R；極大項(xiàng)與解釋之間的對(duì)應(yīng)為：如P取值0，在極大項(xiàng)中則還原為P，如P

21、取值1，在極大項(xiàng)中則還原為0，如P,Q,R之解釋為110，則對(duì)應(yīng)的極大項(xiàng)為乛P乛QR。3、主要定理(1) 任一命題公式都存在與其等值的析取范式和合取范式；(2) 任一命題公式都存在與其等值的主析取范式和主合取范式；(3) 如果一個(gè)命題公式是永真公式Û它的主析取范式包含所有的極小項(xiàng)，此時(shí)無主合取范式或者說主合取范式為空；(4) 如果一個(gè)命題公式是永假公式Û它的主合取范式包含所有的極大項(xiàng)，此時(shí)無主析取范式或者說主析取范式為空；(5) 兩個(gè)命題公式是相等的Û它們所對(duì)應(yīng)的主析取范式上等和主合取范式相等；(6) 任一公式對(duì)應(yīng)主析取范式包括的極小項(xiàng)的個(gè)數(shù)加對(duì)應(yīng)主合取范式包括的

22、極大項(xiàng)的個(gè)數(shù)為2n。2.6 推理理論1. 推理的形式結(jié)構(gòu)設(shè)G1, G2, , Gn，H是命題公式，稱G1G2GnH為推理的形式結(jié)構(gòu)，其中G1, G2, , Gn為前提，H為結(jié)論。當(dāng)G1G2GnH為永真式時(shí)，則此時(shí)推理正確，并稱G1, G2, , Gn邏輯蘊(yùn)涵H是G1, G2, , Gn的邏輯結(jié)果，并且記為G1G2GnÞH或記為G1, G2, , GnÞH。說明：G1, G2, , GnÞH僅描述了公式G1, G2, , Gn與公式H之間的邏輯蘊(yùn)涵關(guān)系，G1, G2, , GnÞH本身并不是一個(gè)公式，它不能作直接的計(jì)算。要判斷G1, G2, , Gn

23、22;H可采用：G1, G2, , GnÞH當(dāng)且僅當(dāng)G1G2GnH是一個(gè)永真公式。2. 判斷推理是否正確的方法(1) 真值表法：利用真值表法，可建立如下推理定律：設(shè)G，H，S是任意的命題公式，則： 附加定律：GÞGH，HÞGH 化簡(jiǎn)定律：GHÞG，GHÞH 合并定律：G，HÞGH 假言推理：G，GHÞH 拒取式：GH，乛HÞ乛G 析取三段論：GH，乛GÞH 假言三段論：GH，HSÞGS 二難推論：GH，GS，HSÞS 等價(jià)三段論：GH；HSÞGS(2) 等值演算法；(3) 主

24、析?。ㄖ骱先。┓妒椒?；(4) 構(gòu)造證明法。 推理規(guī)則：規(guī)則P（前提引入規(guī)則）：在推導(dǎo)的過程中，可以隨時(shí)引入前提集合中的任一前提及附加前提。規(guī)則T（邏輯結(jié)果引用規(guī)則）：在推導(dǎo)的過程中，可以隨時(shí)引用公式S，該公式S是由其前的一個(gè)或多個(gè)公式推導(dǎo)出的邏輯結(jié)果。規(guī)則P（附加前提規(guī)則）：如果能從給定理前提集合P與公式P推導(dǎo)出S，則能從此前提集中P推導(dǎo)出PS。 直接證明方法：此證明法是一個(gè)描述推理過程的命題公式序列C1, C2, , Cn，其中C1, C2, , Cn或者為已知的前提和附加前提，或者是由某些前提或中間結(jié)論應(yīng)用推理規(guī)則得到的中間結(jié)論或結(jié)論，Cn為最終的結(jié)論。 間接證明法（反證法或歸謬法）：要證

25、明G1, G2, ,GnÞH，等價(jià)地證明G1, G2, , Gn， 乛HÞR乛R，其中R可以是任意的公式，此時(shí)證明G1, G2, , Gn, 乛HÞR乛R即可采取直接證明方法。 帶CP規(guī)則的直接證明方法：帶CP規(guī)則的證明法主要是針對(duì)結(jié)論為PS（或乛PS）的公式十分方便，即要證明G1, G2, , GnÞPS，等價(jià)地證明G1, G2, , Gn，PÞS，此時(shí)證明G1, G2, , Gn, PÞS可采用直接證明方法（此時(shí)P為附加前提）。當(dāng)推出結(jié)論S后，采用CP規(guī)則，即可由G1, Gn推出PS。上述三種方法對(duì)命題邏輯中的任何推理問題都是適用

26、的，只是不同的邏輯推理問題采用不同的方法其方便程度不同而已。2.7 總結(jié)通過本章的學(xué)習(xí)，應(yīng)達(dá)到下面的基本要求：(1) 要弄清命題與陳述句之間的關(guān)系與差別。命題都是陳述句；但陳述句不一定都是命題，只有陳述句所表達(dá)的判斷結(jié)果查惟一確定的，它才是命題；(2) 掌握并能熟練應(yīng)用6種基本的聯(lián)結(jié)詞（乛，）來對(duì)復(fù)合命題進(jìn)行翻譯及判斷真值；(3) 記住24個(gè)基本的等價(jià)公式，并能熟練地應(yīng)用到公式的轉(zhuǎn)換中；(4) 會(huì)利用真值表技術(shù)和公式的演算方法求一公式所對(duì)應(yīng)的主析取范式和主合取范式，并能利用范式判斷兩公式是否相等，是否為永真式、永假式、可滿足式；(5) 掌握并能熟練地應(yīng)用推理的三種證明方法。命題邏輯例題例5.1

27、 設(shè)P表示命題“天下雨”，Q表示命題“他騎自行車上班”，R表示命題“他乘公共汽車上班”，試以符號(hào)形式寫出下列命題（西南交大1995年考研試題）：（1）只要不下雨，他才騎自行車上班；（2）只要不下雨，他就騎自行車上班；（3）除非下雨，否則他就騎自行車上班；（4）他或者騎自行上班，或者乘公共汽車上班。分析 對(duì)于命題只要Q才P，只要P就Q，除非Q，否則P等，都可以翻譯成PQ，所以上述(1)，(2)，(3)分別可翻譯為：(1) Q乛P，(2) 乛PQ，(3) 乛QP。句子(4)可翻譯為QR。例5.2 (1) 使用連接詞乛，構(gòu)造三個(gè)命題變項(xiàng)P,Q,R的公式L（P,Q,R），使得：乛L（P,Q,R）=L(

28、乛P,Q,R)=L(P,乛Q,R)=L(P,Q,乛R)（2）求（1）中公式L（P,Q,R）的主合取范式，（北師大2001年考研試題）。解 (1) 設(shè)L（P,Q,R）=其中，Mi為關(guān)于P,Q,R的極大項(xiàng)。則乛L(P,Q,R)= L(乛P,Q,R)= a0M4a1M5a2M6a3M7a4M0a5M1a6M2a7M3L(P,乛Q,R)= a0M2a1M3a2M0a3M1a4M6a5M7a6M1a7M2L(P,Q,乛R)= a0M1a1M0a2M3a3M2a4M5a5M4a6M7a7M6由乛L(P,Q,R)=L(乛P,Q,R)=L(P,乛Q,R)=L(P,Q,乛R)對(duì)應(yīng)極大項(xiàng)Mi的系數(shù)應(yīng)相等，為此有：

29、(1-a0)= a4= a2= a1，(1-a4)= a0= a6= a5(1-a1)= a5= a3= a0，(1-a5)= a1= a7= a4(1-a2)= a6= a0= a3，(1-a6)= a2= a4= a7(1-a3)= a7= a1= a2，(1-a7)= a3= a5= a6所以 a0= a3= a5= a6 a1= a2= a4= a7如令 a0= a3= a5= a6=0，則a1= a2= a4= a7=1此時(shí) L(P,Q,R)=M1M2M4M7= 乛(乛M1乛M2乛M4乛M7)= 乛(乛(PQ乛R)乛(P乛QR)乛(乛PQR) 乛(乛P乛Q乛R)如令 a0= a3=

30、a5= a6=1，則a1= a2= a4= a7=0此時(shí) L(P,Q,R)=M0M3M5M6=乛(乛M0乛M3乛M5乛M6)= 乛(乛(PQR)乛(P乛Q乛R)乛(乛PQ乛R) 乛(乛P乛QR) (2) L(P,Q,R)=M1M2M4M7=(PQ乛R)乛(P乛QR)(乛PQR)(乛P乛Q乛R)主合取范式=M0M3M5M6=(PQR)(P乛Q乛R)(乛PQ乛R)(乛P乛QR)主合取范式例5.3 沒有命題P：明天上午七點(diǎn)下雨 Q：明天上午七點(diǎn)下雪 R：我將去學(xué)校符號(hào)化下列語句：（1）除非明天上午七點(diǎn)不下雨且不下雪，否則我將不去學(xué)校；（2）只要明天上午七點(diǎn)不下雨或不下雪，我就去學(xué)校；（3）只有明天上

31、午七點(diǎn)不是雨夾雪，我才去學(xué)校；（4）明天上午七點(diǎn)我將雨雪無阻一定去學(xué)校。分析 根據(jù)命題PQ的定義，它可對(duì)應(yīng)語句除非Q，否則乛P；只要P，就Q；只有Q才P。所以上述（1），（2），（3）可分別對(duì)應(yīng)符號(hào)化為：（1）R（乛P乛Q）（2）乛P乛QR（3）R乛（PQ）句子（4）是雨雪無阻一定去學(xué)校，即無論任何天氣都不影響去學(xué)校，即去學(xué)校與天氣無關(guān)，因此，句子（4）可簡(jiǎn)單地符號(hào)化為：R但為了完整的表達(dá)出該句子的全部意思，應(yīng)將雨雪無阻符號(hào)化。所謂雨雪無阻即是：（PQ）（乛PQ）（P乛Q）（乛P乛Q）所以句子（4）完整地符合號(hào)為：（PQ）（乛PQ）（P乛Q）（乛P乛Q）R或 （PQR）（乛PQR）（P乛QR）

32、（乛P乛QR）說明 由于雨雪無阻與R是同時(shí)發(fā)生，沒有因果關(guān)系，所以天氣與去學(xué)校之間用合取。例5.4 求公式G1(P，Q，R)5(PQ)(PQ)G2(P，Q)5(PQ)(PQ)的主析取范式和主合取范式。分析 公式G1，G2的右端雖然是相同的，但公式的左岸表明兩個(gè)公式所含的命題變?cè)煌?，在求主析取，主合取范式時(shí)，由于其極小項(xiàng)，極大項(xiàng)依賴于命題變?cè)?，所以不能僅根據(jù)右端的公式來求，還應(yīng)該根據(jù)該公司所含的命題變?cè)那闆r來求。因此，上述兩個(gè)公式的主析取范式，主合取范式安全不同。下面采用兩種方式來求。方法1 采用真值表技術(shù)。建立公式G1(P，Q，R)5(PQ)(PQ)的真值表如表24所示。表24P，Q，R(

33、PQ)(PQ)0 0 01 0 00 0 11 0 00 1 01 0 00 1 11 0 01 0 00 0 01 0 10 0 01 1 01 1 11 1 11 1 1則公式G1(P，Q，R)所對(duì)應(yīng)的主析取范式、主合取范分別為：G1（P，Q，R）5（PQ乛R）（PQR）主析取范式G1（P，Q，R）5（PQR）（PQ乛R）(P乛QR)(P乛Q乛R) （乛PQR）（乛PQ乛R）主合取范式建立公式G2(P，Q)5（PQ）（PQ）的真值表如表25所示。表25P Q（PQ）（PQ）0 01 0 00 11 0 01 00 0 01 11 1 1則公式G2(P，Q)所對(duì)應(yīng)的主析取范式、主合取范式分別

34、為：G2（P，Q）=（PQ）主析取范式G2（P，Q）=（PQ）（乛PQ）（P乛Q）主合取范式方法2 采用公式轉(zhuǎn)換法。G1（P，Q，R）5（PQ）(PQ)5（乛PQ）PQ5PQ5PQ(乛RR)5（PQ乛R）（PQR）主析取范式G1（P，Q，R）5乛（乛G1(P，Q，R)）5乛（(P乛QR)(乛PQR)(P乛Q乛R)（乛PQ乛R）（乛P乛QR）（乛P乛Q乛R）5(乛PQ乛R)（P乛Q乛R）（乛PQR）(乛PQR)（PQ乛R）（PQR）5(PQR)（PQ乛R）（P乛QR）（P乛Q乛R）(乛PQR)（乛PQ乛R）主合取范式G2（P，Q）5（PQ）（PQ）5（乛PQ）PQ5（PQ）主析取范式G2（P，Q

35、）5乛（乛G2(P，Q)）5乛（(P乛Q)(乛PQ)(乛P乛Q)）5（乛PQ）（P乛Q）（PQ）5（PQ）（乛PQ）（P乛Q）主合取范式從上可以看出，兩個(gè)公式的主析取，主合取范式安全不同。例5.5 判斷下面公式的類型（重言式，矛質(zhì)式，可滿足式）（1）（PQ）（乛Q乛P）（2）（P Q）乛（PQ）（北師大2000年考研試題）解 判斷一個(gè)公式是否是重方式、矛盾式，可滿足公式，可采用三種方式：(1)真值表技術(shù)；(2)公式等值演算；(3)求主析取，主合取范式。下面分別采用三種方法：方法1 真值表技術(shù)。建立公式(1)，(2)的真值表如表26所示。表26P Q（PQ）（乛Q乛P）（P Q）乛（PQ）0 0

36、1 1 11 1 10 11 1 10 1 01 00 1 00 1 01 11 1 11 0 0由上述真值可知，公式(1)是重言式，公式(2)是可滿足式。方法2 公式等值演算。 （PQ）（乛Q乛P）5（P Q）乛（PQ）5乛（乛PQ）（乛PQ）51所以公式是永真式（重言式）。方法3 求公式的主析取、主合取范式。（P Q）乛（PQ）5乛（P Q）乛（PQ）5 乛（PQ）乛（QP）（乛P乛Q）5 乛（乛PQ）乛（乛QP）（乛P乛Q）5 （P乛Q）（乛PQ）（乛P乛Q）主析取范式5 乛（乛(P Q)乛(PQ)）5乛（PQ）5（乛P乛Q）主合取范式顯然公式所對(duì)應(yīng)的主析取范式不包括所有的極小項(xiàng)，所以不

37、是重言式，公式所對(duì)應(yīng)的主合取范式不包括所有的極大項(xiàng)，所以不是矛盾式，因此，僅是可滿足式。例5.6 符號(hào)化下列命題，并證明其結(jié)論：一公安人員審查一件盜竊案，已知事實(shí)如下：（1）張平或王磊盜竊了機(jī)房的計(jì)算機(jī)一臺(tái)；（2）若張平盜竊了計(jì)算機(jī)，則作案時(shí)間不可能發(fā)生在午夜之前；（3）若王磊的證詞正確，則午夜時(shí)機(jī)房里的燈未滅；（4）若王磊的證詞不正確，則作案時(shí)間發(fā)生在午夜之前；（5）午夜時(shí)機(jī)房燈光滅了。問：盜竊計(jì)算機(jī)的是張平？王磊？分析 首先將事實(shí)符號(hào)化：設(shè)P：張平盜竊了計(jì)算機(jī)； Q：王磊盜竊了計(jì)算機(jī)； R：作案時(shí)間發(fā)生在午夜前；S：王磊的證詞正確；T：午夜時(shí)燈光滅了。則前提可符號(hào)化為：PQ，P 乛R，S

38、乛T，乛S R，T證明的結(jié)論為P或Q。證明 （1）TP（2）S 乛TP（3）乛ST，(1)，(2)，I（4）乛S RP（5）RT，(3)，(4)，I（6）P 乛RP（7）乛PT，(5)，(6)，I（8）PQP（9）QT，(7)，(8)，I此結(jié)論說明是王磊盜竊了機(jī)房的計(jì)算機(jī)。例5.7 符號(hào)化下列命題，并用演譯法加以證明：如果6是偶數(shù)，則2不能整除7；或者5不是素?cái)?shù)，或2整除7；5是素?cái)?shù)。因此，6是奇數(shù)。解 首先將上述事實(shí)符號(hào)化設(shè)P：6是偶數(shù) Q：2能整除7 R：5是素?cái)?shù)則命題可符號(hào)化為P乛Q，乛RQ，R乛P證明 （1）乛RQP（2）RP（3）QT，(1)，(2)，I（4）P乛QP（5）乛PT，(

39、3)，(4)，I說明 本例的證明十分簡(jiǎn)單，但該例卻說明了一個(gè)十分重要的情況：該列的結(jié)論是一個(gè)錯(cuò)誤的結(jié)論。我們不能誤認(rèn)為該推導(dǎo)是錯(cuò)誤的，或認(rèn)為該前提不能邏輯地蘊(yùn)涵結(jié)論。實(shí)際上，在邏輯推理中，完全允許在錯(cuò)誤的假設(shè)下邏輯推導(dǎo)出一個(gè)錯(cuò)誤的結(jié)論。一問題正是在錯(cuò)誤的前提下（如6是偶數(shù)，則2不能整除7），導(dǎo)致了錯(cuò)誤的結(jié)論，它們之間仍有邏輯蘊(yùn)涵關(guān)系。例5.8 符號(hào)化下列句子，并用反證法（歸謬法）加以證明。（1）如果A因病缺了許多課，那么也中學(xué)考試不及格；（2）如果A中學(xué)考試不及格，則他沒有知識(shí)；（3）如果A讀了許多書，則他有知識(shí)。（4）所以，A沒有缺很多課或沒有讀很多書。解 首先將事實(shí)符號(hào)化：設(shè)P：A因病缺了

40、許多劉；Q：他中學(xué)考試及格；R：他有知識(shí)；S：他讀了許多書。則上述句子可符號(hào)化為：P乛Q，乛Q乛R，SR乛P乛S證明 采用歸謬法就是將結(jié)論的否定作為附加前提加入到前提集合之中，導(dǎo)致與已知條件的矛盾。（1）乛（乛P乛S）P(附加前提)（2）PST，(1)，(2)，E（3）PT，(2)，I（4）ST，(2)，I（5）P乛QP（6）乛QT，(3)，(5)，I（7）SRP（8）RT，(4)，(7)，I（9）乛Q乛RP（10）QT，(8)，(9)，I（11）Q乛QT，(6)，(10)，I所以，由歸謬法知：P乛Q，乛Q乛R，SR乛P乛S。例5.9 設(shè)前提集合為P5PQ，PR，QS，G5SR，證明PG。解

41、對(duì)于該題分別有用三種證明方法加以證明。證法1 直接證明法。（1）PQP（2）乛PQT，(1)，E（3）QSP（4）乛PST，(2)，(3)，I（5）乛SPT，(4)，E（6）PRP（7）乛SRT，(5)，(6)，I（8）SRT，(7)，E證法2 帶CP規(guī)則的直接證明法。因G5 SR5乛SR，為此，可將乛S作為附加前提加入前提集合中，如能證明P，乛SR，則由CP規(guī)則知：P乛SR即PSR。（1）乛SP(附加前提)（2）QSP（3）乛QT，(1)，(2)，I（4）PQP（5）PT，(3)，(4)，I（6）PRP（7）RT，(5)，(6)，I（8）乛SRCP，(1)，(7)（9）SRT，(8)，E證法

42、3 歸謬法。（1）乛（SR）P(附加前提)（2）乛S乛RT，(1)，E（3）乛ST，(2)，I（4）乛RT，(2)，I（5）PRP（6）乛PT，(4)，(5)，I（7）QSP（8）乛QT，(3)，(7)，I（9）乛P乛QT，(6)，(8)，I（10）乛（PQ）T，(9)，E（11）PQP（12）（PQ）乛(PQ)T，(10)，(11)，I例5.10 證明P(QS)是P(QR)，R(QS)的邏輯結(jié)果。分析 對(duì)于這類問題(結(jié)論是蘊(yùn)涵的形式)，采用帶CP規(guī)則的直接證明法最方便。（1）PP(附加前提)（2）P（QR）P（3）QRT(1)，(2)，I（4）R（QS）P（5）Q（QS）T，(3)，(4)，

43、I（6）QP(附加前提)（7）QST，(5)，(6)，I（8）P（QS）CP，(1)，(7)例5.11 一個(gè)排隊(duì)線路，輸入為A，B，C，其輸出分別為FA，F(xiàn)B，F(xiàn)C，在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過。如果同時(shí)有兩個(gè)或兩個(gè)以上信號(hào)通過時(shí)，則按A，B，C的順序輸出，例如：A，B，C同時(shí)輸入時(shí)，只能A有輸出，寫出FA，F(xiàn)B，F(xiàn)C的邏輯表達(dá)式，并化成全功能集中的表達(dá)式。解 設(shè)P：A輸入 Q：B輸入 R：C輸入由提所給的條件，易寫出FA，F(xiàn)B，F(xiàn)C的真值表如表2.7所示。表2.7PQRFAFBFC000011110011001101010101000011110011000001000000由真值表知：它

44、們的主析取范式分別為：FA5（PQR）（PQ乛R）（P乛QR）（P乛Q乛R）5（PQ）（R乛R）（P乛Q）（R乛R）5（PQ）（P乛Q）5 P（Q乛Q）5 P 15 P 5乛乛（PP）5乛（PP）5（PP）（PP）FB（乛PQ乛R）（乛PQR）5（乛PQ）（乛RR）5 乛PQ5乛乛（乛PQ）5乛（P乛Q）5P乛Q5P（QQ）FC（乛P乛QR）5乛（PQ）R5（PQ）R5乛乛（PQ）乛乛R5乛（乛（PQ）乛R）5乛（PQ）乛R5（PQ）（PQ）（RR）例5.12 某勘探隊(duì)有3名隊(duì)員，有一天取得一塊礦樣，3人的判斷如下：甲說：這不是鐵，也不是銅；乙說：這不是鐵，是錫；丙說：這不是錫，是鐵。經(jīng)實(shí)驗(yàn)鑒

45、定后發(fā)現(xiàn)，其中一人兩個(gè)判斷正確，一個(gè)人判對(duì)一半，另一個(gè)全錯(cuò)了。根據(jù)以上情況判斷礦樣的種類。分析 設(shè)P：礦樣是鐵；Q：礦樣是銅；R：礦樣是錫。則上述情況可能有：F1：甲全對(duì)、乙對(duì)一半，丙全錯(cuò)；F2：甲全對(duì)、乙全錯(cuò)、丙對(duì)一半；F3：甲對(duì)一半、乙全對(duì)、丙全錯(cuò)；F4：甲對(duì)一半、乙全錯(cuò)、丙全對(duì)；F5：甲全錯(cuò)、乙全對(duì)、丙對(duì)一半；F6：甲全錯(cuò)、乙對(duì)一半、丙全對(duì)。由于F（一人全對(duì)）（一人對(duì)一半）（一人全錯(cuò)），所以，上述F1，F(xiàn)2，F(xiàn)6這六種情況應(yīng)有一種發(fā)生，即：FF1F2F3F4F5F61根據(jù)命題的表示：F1，F(xiàn)2，F(xiàn)6中分別表示如下：F1（乛P乛Q）（乛P乛R）（PR）（R乛P）（乛P乛QR乛P乛P乛R）（

46、乛P乛QR乛PPR）000F2（乛P乛Q）（P乛R）（乛R乛P）（RP）0（乛RP）（RP）0F3（P乛Q）（乛PQ）（乛PR）（R乛P）（P乛Q乛PRR乛P）（乛PQ乛PRR乛P）=0（乛PQR）= 乛PQRF4（P乛Q）（乛PQ）（P乛R）（乛RP）=（P乛QP乛R乛RP）（乛PQ乛PRR乛P）=（P乛Q乛R）05（P乛Q乛R）F5（PQ）（乛PR）（RP）（乛R乛P）=（PQ乛PR）（RP）（乛R乛P）= 0（RP）（乛R乛P）= 0F6（PQ）（乛P乛R）（PR）（乛RP）=（PQ乛P乛R乛RP）（PQPR乛RP）=00 = 0所F00（乛PQR）（P乛Q乛R）00（乛PQR）（P乛Q

47、乛R）= 1但礦樣即不可能既是銅又是錫，所以Q，R中必有假命題，即Q，R不能同為真，所以乛PQR = 0，因而必有P乛Q乛R = 1所以P為真，乛Q為真，乛R為真，即P為真，Q為假，R為假，即礦樣為鐵。例5.13 用P規(guī)則和T規(guī)則證明下列命題演算的推理關(guān)系。（1）乛PQ，乛QR，RSPS（2）A（BC），D（B乛C），AD是不相容的（人大2001年考研試題）證明（1）乛PQP PQT，E 乛QRP QRT，E PR T，I RSP PST，I故 乛RQ，乛QR，RSÞPS（2）QDP A（BC） P AT，I BCT，I D（B乛C）P DT，I （B乛C）T，I BT，I CT，I

48、乛CT，I11 C乛CT，I第3章 謂詞邏輯一階謂詞邏輯（4學(xué)時(shí)）【教學(xué)目的】掌握數(shù)理邏輯中謂詞的翻譯及公式的解釋；利用規(guī)則、基本等價(jià)和蘊(yùn)涵公式、三種不同的推理方法完成謂詞邏輯的推理?！窘虒W(xué)要求】1. 理解謂詞、量詞、個(gè)體詞、個(gè)體域、原子公式、謂詞公式和變?cè)雀拍?。?huì)將不太復(fù)雜的命題符號(hào)化。2. 掌握在有限個(gè)體域下求公式的真值和某些公式在給定解釋下真值的方法，判別公式類型(永真式、永假式和可滿足式)的方法。3. 掌握謂詞演算的等值式和重言蘊(yùn)含式 (六種情況：(1)命題公式的推廣；(2)量詞否定式的等值式；(3)量詞轄域擴(kuò)張和收縮的等值式；(4)量詞與聯(lián)結(jié)詞Ú，Ù，®的等值式；(5)量詞與聯(lián)結(jié)詞的重言蘊(yùn)含式；(6)兩個(gè)量詞公式間的等值式與重言蘊(yùn)含式)。會(huì)進(jìn)行謂詞公式的等值演算。4. 了解前束范式的概念，會(huì)求公式的前束范式。5. 了解謂詞邏輯推理的規(guī)則：全量詞消去規(guī)則