離散數(shù)學(xué) 課件 thethirdcourse

1、 (PQ(RR)(PR(QQ)(QR(PP) (PQR)(PQR)(PRQ)(PRQ) (PQR)(PQR)(PQR)(PQR) 2.利用等價(jià)式求主析取范式例：（PQ）(PR)(QR) 化歸方法步驟： 1. 化為析取范式。 2. 刪去析取范式中永假的析取項(xiàng)。 3. 將析取式中重復(fù)的合取項(xiàng)和相同的變?cè)喜ⅰ?-7對(duì)偶與范式4. 對(duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的變?cè)?，即添?PP等。 5.用分配律展開(kāi)。 1-7對(duì)偶與范式 上次課我們學(xué)習(xí)了析取范式，形式為：（ ）( )( ),合取范式，形式為：（ ）（ ）（ ）（ ），引入了小項(xiàng)（它是變?cè)蜃冊(cè)姆穸ㄊ浇M成的合取式，但兩者必須出現(xiàn)且僅出現(xiàn)一個(gè)。由小項(xiàng)的析取我

2、們可以得到主析取范式；這樣對(duì)于任一公式，我們都可求出其主析取范式，當(dāng)其變?cè)膫€(gè)數(shù)、次序固定時(shí)，它是唯一的。下面我們主要介紹主合取范式。對(duì)應(yīng)于小項(xiàng)，我們引進(jìn)了大項(xiàng)。 大項(xiàng)的定義為：n個(gè)命題變?cè)奈鋈∈剑渲忻總€(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次，稱為大項(xiàng)，也成為布爾析取。例如:2個(gè)變?cè)狿、Q，可生成22 =4個(gè)大項(xiàng):PQ PQ PQ PQ 3個(gè)變?cè)狿,Q,R，可以生成8個(gè)大項(xiàng):PQR PQR 1-7對(duì)偶與范式 PQR n個(gè)變?cè)獙?duì)應(yīng)著2n個(gè)大項(xiàng)。 小項(xiàng)用m編號(hào)，大項(xiàng)用M表示，兩個(gè)變?cè)脙晌欢M(jìn)制編號(hào)。 小項(xiàng)0：變?cè)穸ǎ?：命題變?cè)?。如m01PQ。而大項(xiàng)正好相反。 大項(xiàng)0：變

3、元本身，1：變?cè)穸?。如：M00PQ。如上面對(duì)應(yīng)2個(gè)變?cè)?個(gè)大項(xiàng)：PQ,PQ,PQ,PQ M00=M0,M01=M1,M10=M2,M11=M3 等等可與上面并在一起寫(xiě)。對(duì)應(yīng)于二進(jìn)制，大項(xiàng)也可以用十進(jìn)制編號(hào)，如上。 大項(xiàng)有如下性質(zhì)：1-7對(duì)偶與范式1. 每個(gè)大項(xiàng)的指派與編號(hào)相同時(shí)，其值為F，而其余2n1種指派情況下其值均為T(mén)。2.任意兩個(gè)不同大項(xiàng)的析取式都為T(mén)。如MiMj（i!=j）總有一個(gè)變?cè)c其否定存在。3.全體大項(xiàng)的合取式必為永假F。 （02n1）Mi=M0M1M2M 2n1 =F由大項(xiàng)，可以得到主合取范式。 對(duì)于一個(gè)公式若存在一個(gè)等價(jià)式，它由大項(xiàng)的合取所組成，則該等價(jià)式稱為原式的主合

4、取范式。 求主合取范式的方法： 1 真值表法 定理:在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的1-7對(duì)偶與范式合取，即為此公式的主合取范式。我們求主析取范式時(shí)是將所有值為T(mén)的指派對(duì)應(yīng)的小項(xiàng)析??；這里求主合取范式是將所有取值為F的所有可能值列出來(lái)、取合取。（析取與合取對(duì)偶）要注意大項(xiàng)的寫(xiě)法不同于小項(xiàng)，另外列真值表必須注意次序，先列T，后列F1-7對(duì)偶與范式1-7對(duì)偶與范式對(duì)于上述定理就不證明了，方法與前面類(lèi)似。2 用等價(jià)公式，其步驟為： 1) 劃歸為合取范式。 2) 刪去合取式中永真的合取式。 3) 合并相同的析取項(xiàng)和相同的變?cè)?4)對(duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的變?cè)囱a(bǔ)入形如：(PP) 式

5、。 5) 應(yīng)用分配律展開(kāi)。上述五個(gè)步驟與主析取范式類(lèi)似。例：化原式為主析取范式（上例）1-7對(duì)偶與范式這樣當(dāng)變?cè)涡蛞欢〞r(shí)，每個(gè)公式都有唯一與之等價(jià)的主合取范式 一個(gè)公式，既有與之相等價(jià)的唯一的主析取范式，又有唯一的主合取范式，它們之間有何關(guān)系呢？首先它們分別由小項(xiàng)、大項(xiàng)決定的，看看小項(xiàng)、大項(xiàng)之間有何關(guān)系。1-7對(duì)偶與范式 1） 大項(xiàng)與小項(xiàng)有什么關(guān)系？1-7對(duì)偶與范式總結(jié)：學(xué)習(xí)數(shù)理邏輯主要適用于推理，有了前面的這些基礎(chǔ)知識(shí)，就可以進(jìn)行推理1-8推理理論 推理就是用一些已知的東西得出另外一些結(jié)論。而在推理過(guò)程中，常把一些定律、定理和條件，作為假設(shè)前提，使用一些公認(rèn)的規(guī)則，得到另外的命題，形成結(jié)論

6、，這種過(guò)程就是論證。定義：1-7對(duì)偶與范式判別有效結(jié)論的過(guò)程就是論證過(guò)程，方法多種多樣，但基本上有三種方法。1-8命題演算的推理理論例如 P41. 例 1. 讀題；首先找出命題變?cè)?，P : 材料不可靠，Q : 計(jì)算有錯(cuò)誤。論證 : T T T FT F T F T T T TF F F T1-8命題演算的推理理論(2) 直接證法從已知前提出發(fā)，使用公認(rèn)的推理規(guī)則，利用等價(jià)式或蘊(yùn)含式，得到結(jié)論。規(guī)則有 P規(guī)則 前提在論證過(guò)程中任何時(shí)候都可用。 T規(guī)則 在論證中，如果一個(gè)或多個(gè)公式蘊(yùn)含公式S，則S可以引入推理中。等價(jià)式與蘊(yùn)含式在書(shū) P 43 表 1- 8. 3 , 1- 8. 4可見(jiàn)。1-8命題演

7、算的推理理論證明：注意：必須將證明過(guò)程編號(hào)一一寫(xiě)出理由。 這里須將每一步依次編號(hào)，得出理由；書(shū)上給了兩種證明法，論證方法不唯一，但方向是明確的，最終能到達(dá)C，且步驟越少越好。（3）間接證法1-8命題演算的推理理論(3) 間接證法：1-8命題演算的推理理論1-8命題演算的推理理論注意：永假不是永真的否定，但若要證A為永真，可證明 A為永假。1-8命題演算的推理理論 前面介紹了邏輯推理，所謂邏輯推理就是由一組前提，用一些公認(rèn)的推理規(guī)則，利用等價(jià)或蘊(yùn)含式，推出結(jié)論成立，就是論證。證明 有三種方法。1-8命題演算的推理理論1-8命題演算的推理理論1-8命題演算的推理理論例2P46例題6M：天晴；Q：下

8、雨；S：我看電影；R：我看書(shū)。1-8命題演算的推理理論要證明：MQ,MS,S RRQ證： (1)R P(附加前提) (2)S R P (3)R S T(2)E (4) S T(1)(3)I11 (5)MS P (6) S M T(5)E (7) M T(4)(6)I11 (8) (MQ) P1-8命題演算的推理理論(9)M Q T(8)E22(10)(M Q)( Q M) T(9)E(11) QM T(10)I(12) MQ T(11)E(13)Q T(7)(12)I11(14)RQ CP 或(8)MQ P(9) MQ T(8)E1-8命題演算的推理理論(10)( M Q) (Q M) T(9

9、)E(11) M Q T(10)I(12)Q T(7)(11)I所有推理方法不唯一，使用的等價(jià)或蘊(yùn)含式也不一定相同，但是越簡(jiǎn)潔越好。關(guān)于命題邏輯就介紹這么多。主要有命題九個(gè)聯(lián)接詞；五個(gè)主要聯(lián)接詞，最小連接詞組為 ,或 ,或或等，和一些公式（重言式，蘊(yùn)含式，對(duì)偶式，合取、析取范式）以及推理。下面介紹謂詞邏輯（數(shù)理邏輯的另一基本內(nèi)容）。1-8命題演算的推理理論 在命題邏輯中，P, Q R是無(wú)法推出的。命題邏輯具有局限性，刻畫(huà)命題不夠深刻，因此有必要研究謂詞邏輯。在命題邏輯中，基本單位是原子命題，它是不可再分的。但是原子命題間還是有一些共同特征的，需要進(jìn)一步解析。例如：例1：P：小李是學(xué)生。 Q：

10、小張是學(xué)生。 在命題邏輯中，這是兩個(gè)不同命題，無(wú)法再分了，但共性“是學(xué)生”（命題的本質(zhì)屬性）無(wú)法進(jìn)一步刻劃出來(lái)，還有些很簡(jiǎn)單的三段論也是無(wú)法用命題邏輯的理論推出的。例2： P： 人是要呼吸的。 Q ：老張是人。 R：老張是要呼吸的。第二章謂詞邏輯命題邏輯具有局限性，刻畫(huà)命題不夠深刻。有必要研究謂詞邏輯。命題是反映判斷的陳述句，它至少有主語(yǔ)和謂語(yǔ)兩部分組成。 如：小王是學(xué)生。 5大于7。 點(diǎn)a位于點(diǎn)b與點(diǎn)c之間。 1定義 1） 主語(yǔ)：稱為客體（個(gè)體），用a,b,c表示?？陀^存在的東西，可以是具體的，也可以是抽象的。 2） 用來(lái)描述客體的性質(zhì)，或客體之間的關(guān)系的稱為謂詞。用P,Q,R（大寫(xiě)字母）表

11、示。2-1謂詞的概念與表示1a:5b:7B:大于B(a,b):5大于7a:點(diǎn)Ab:點(diǎn)Bc:點(diǎn)CL:位于與之間L(a,b,c)表示，A位于B與C之間 2. 這樣命題就可用謂詞與客體表示： a:小王A:是學(xué)生A(a):小王是學(xué)生 a:老張 H:是老師 H(a):老張是老師 2-1謂詞的概念與表示 所以，單獨(dú)一個(gè)謂詞不是命題，只有填入客體后才是命題，叫謂詞填式。定義：H是n元謂詞，a1,a2,a3an是n個(gè)客體，H(a1,a2an)所代表的式子是一個(gè)命題，稱為謂詞填式。（當(dāng)ai是客體時(shí)，A(a1an)才是命題。）3除了謂詞，我們今后還要用到函數(shù)這一概念例：老張是小張的父親。 小張的父親=老張 f:.

12、的父親； a:小張； b:老張； 則b=f(a)2-1謂詞的概念與表示 今天南京的氣溫是20度 a :今天 ； b:南京； g:某天某城市的溫度 則g(a,b)=20度 所以，函數(shù)是將客體映射到客體。而謂詞是將客體映射到真或假 的命題。 如：小王是學(xué)生 是謂詞填入客體得到的命題。 7大于5 是兩個(gè)客體填入后得到命題，T 用f,g,h.表示函數(shù)，如h表示：和.之和， 則a:3,b:4 h(a,b)=72-1謂詞的概念與表示4. 定義1）個(gè)體域（客體的論述范圍） 2）客體變?cè)▊€(gè)體變?cè)阂詡€(gè)體域中客體為值的變?cè)?x,y,z表示 3）論域：所有客體的集合。全總個(gè)體域：各種個(gè)體域綜合在 一起，作

13、為論述范圍的域。 2-2命題函數(shù)與量詞 例1：H:到達(dá)山頂 l:李四 t:老虎 c:汽車(chē) H(l):李四到達(dá)山頂。2-1謂詞的概念與表示 H(t):老虎到達(dá)山頂。 H(c): 汽車(chē)到達(dá)山頂。 H(x)表示H的共同形式。但單寫(xiě)H不知是幾元謂詞，所以需加客體變?cè)?。?： L(x,y):xy L(2,3):2z A(4,3,5):4+35 所以，H(x),L(x,y),M(x,y,z)本身不是命題，但當(dāng)變?cè)√囟?值后成為命題。2-2命題函數(shù)與量詞定義：（1）簡(jiǎn)單命題函數(shù)：一個(gè)謂詞+一些客體變?cè)M成的表達(dá)式 稱為簡(jiǎn)單命題函數(shù)。但A(x,y,z)不是命題 （2）n元謂詞就是有n個(gè)客體變?cè)拿}函數(shù)。

14、（3）復(fù)合命題函數(shù)：由簡(jiǎn)單命題函數(shù)和邏輯聯(lián)結(jié)詞構(gòu)成的 命題函數(shù) 例如1：S(x)表示x學(xué)習(xí)很好 W(x): x工作很好 S(x)：x學(xué)習(xí)不是很好 S(x)W(x): x學(xué)習(xí)很好，工作也好 S(x) W(x):若x學(xué)習(xí)好，則x工作也好 2-2命題函數(shù)與量詞又如例2： H(x,y):x比y長(zhǎng)得高 l:李四 c:張三 H(l,c):李四比張三長(zhǎng)得高 例3：R(x):x是大學(xué)生 x的個(gè)體域：某大學(xué)中某班 P(x)永真 x的個(gè)體域：某中學(xué)中某班 P(x)永假 x的個(gè)體域：某劇場(chǎng)中觀眾 P(x)有真有假 2-2命題函數(shù)與量詞 命題函數(shù)不是命題，只有客體變?cè)√囟腕w時(shí)，才是命題。而且真假與其取值也有關(guān)系。

15、例4：又（P(x,y) P(y,z)）P(x,z)若P(x,y):xxF(x):x是自然數(shù)G(x):x是素?cái)?shù)H(x,y):xy每一步必須非常清楚，內(nèi)在關(guān)系把握住，就不會(huì)錯(cuò)。2-3謂詞公式與翻譯(4)沒(méi)有不犯錯(cuò)誤的人。(F(x),M(x)(書(shū)上)譯為：不存在x，x是人且x是不犯錯(cuò)誤的。F(x):x犯錯(cuò)誤。 M(x):x是人所以(5)愛(ài)新覺(jué)羅弘歷的爸爸到北京去了。“到去了”是謂詞。F(x,y):x到y(tǒng)去了。a:愛(ài)新覺(jué)羅弘歷,f(x):x的爸爸，b:北京 所以F(f(a),b)(6)戴婷婷和他的父親及祖父三人一起去看演出。F(x,y,z):x,y和z一起去看演出2-3謂詞公式與翻譯f(x):x的父親a:戴婷婷(7)這只大紅書(shū)柜擺滿了那些古書(shū)。F(x,y):x擺滿了y a:這只大紅書(shū)柜 b:那些古書(shū)可譯為：F(a, b)，但描述太粗略。另譯為：R(x):x是書(shū)柜 B(x):x是大的 C(x):x是紅的 D(y):y是古老的E(y):y是書(shū)