離散數(shù)學(xué)重點(diǎn)筆記

1、第一章， 0命題邏輯素?cái)?shù) = 質(zhì)數(shù)，合數(shù)有因子 和 或 假必真 同為真(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。若公式A是單個(gè)的命題變項(xiàng)，則稱A為0層合式(pq)r，(pq)(rs)p)分別為3層和4層公式【例】求下列公式的真值表，并求成真賦值和成假賦值。 (pq)r公式(1)的成假賦值為011，其余7個(gè)賦值都是成真賦值第二章， 命題邏輯等值演算（1）雙重否定律 AA（2）等冪律 AAA ； AAA（3）交換律 ABBA ； ABBA（4）結(jié)合律 （AB）CA（BC） ； （AB）CA（BC）（5）分配律 （AB）C（AC）（BC） ； （A

2、B）C（AC）（BC）（6）德·摩根律 （AB）AB ； （AB）AB（7）吸收律 A（AB）A；A（AB）A（8）零一律 A11 ； A00（9）同一律 A0A ； A1A（10）排中律 AA1（11）矛盾律 AA0（12）蘊(yùn)涵等值式 ABAB（13）假言易位 ABBA（14）等價(jià)等值式 AB（AB）（BA）（15）等價(jià)否定等值式 ABABBA（16）歸繆式 （AB）（AB）AAi(i=1,2,s)為簡單合取式，則A=A1A2As為析取范式 (pq)(qr)p A=A1A2As為合取范式 (pqr)(pq)r 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡單合取式都是矛盾式一個(gè)合取范式是重

3、言式當(dāng)且僅當(dāng)它的每個(gè)簡單析取式都是重言式 主范式 【小真，大假】 成真 小寫【例】 (pq)(qp) = (pq)(qp) (消去) = (pq)pq (內(nèi)移) (已為析取范式) = (pq)(pq)(pq)(pq)(pq) （*） = m2m0m1m1m3 = m0m1m2m3 (冪等律、排序) (*)由p及q派生的極小項(xiàng)的過程如下： p = p(qq) = (pq)(pq) q = (pp)q = (pq)(pq) 熟練之后，以上過程可不寫在演算過程中。 該公式中含n=2個(gè)命題變項(xiàng)，它的主析取范式中含了22=4個(gè)極小項(xiàng)，故它為重言式，00，01，10，11全為成真賦值?！纠?pq)p =

4、 (pq)p (消去) = p(pq) (分配律、冪等律) 已為析取范式 = (pq)(pq) = m0m1【例】(pq)(pq) = (pp)(pq)(qp)(qq) = (pq)(pq)重言蘊(yùn)涵式 【例】用附加前提證明法證明下面推理。前提：P（QR），SP，Q 結(jié)論：SR證明：（1）SP 前提引入規(guī)則 （2）S 附加前提引入規(guī)則 （3）P （1）（2）析取三段論規(guī)則 （4）P（QR） 前提引入規(guī)則 （5）QR （3）（4）假言推理規(guī)則 （6）Q 前提引入規(guī)則 （7）R （5）（6）假言推理規(guī)則【例】用歸繆法證明。前提：PQ，PR，QS 結(jié)論：SR證明（1）（SR） 附加前提引入規(guī)則 （2）

5、SR （1）置換規(guī)則 （3）S （2）化簡規(guī)則 （4）R （2）化簡規(guī)則 （5）QS 前提引入規(guī)則 （6）QS （5）置換規(guī)則 （7）Q （3）（6）析取三段論 （8）PQ 前提引入規(guī)則 （9）P （7）（8）析取三段論規(guī)則 （10）PR 前提引入規(guī)則 （11）PR （10）置換規(guī)則 （12）R （9）（11）析取三段論規(guī)則 （13）RR （4）（12）合取引入規(guī)則全稱量詞""對""無分配律。同樣的，存在量詞""對""無分配律 (3) xyF(x,y) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a

6、,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) 謂詞邏輯的等價(jià)公式 定理1 設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個(gè)等價(jià)公式：（1）x A（x）xA（x）（2）x A（x）xA（x）定理2 設(shè)A（x）是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B是不含x出現(xiàn)的公式，則有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x） B）x A（x） B（4）x（BA（x）B x A（x）（5）x（A（x）B） x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x） B）x A（x） B（8）x（BA（x）Bx A

7、（x） 定理3 設(shè)A（x）、B（x）是任意包含自由出現(xiàn)個(gè)體變元x的公式,則有：（1）x（A（x）B（x）x A（x）x B（x）（2）x（A（x）B（x）x A（x）x B（x） 定理4 下列蘊(yùn)涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x） B（x）x A（x） x B（x）（4）x（A（x） B（x）x A（x） x B（x）（5）x A（x） x B（x）x（A（x） B（x）【例】【例】【例】【例】【例】在一階邏輯自然推理系統(tǒng)F中構(gòu)造下面推理的證明 （1）所有的人或者是吃素的或者是吃葷的，吃素的常吃豆制品，因

8、而不吃豆制品的人是吃葷的。（個(gè)體域?yàn)槿说募希?（2）每個(gè)喜歡步行的人都不喜歡騎自行車，每個(gè)人或者是喜歡騎自行車或者喜歡乘汽車，有的人不喜歡乘汽車，所以有的人不喜歡步行。（個(gè)體域?yàn)槿说募希??！纠糠柣旅娴拿}“所有的有理數(shù)都是實(shí)數(shù)，所有的無理數(shù)也是實(shí)數(shù)，任何虛數(shù)都不是實(shí)數(shù)，所以任何虛數(shù)既不是有理數(shù)也不是無理數(shù)”，并推證其結(jié)論。證明 設(shè)：P（x）：x是有理數(shù)。 Q（x）：x是無理數(shù)。 R（x）：x是實(shí)數(shù)。 S（x）：x是虛數(shù)。本題符號化為：x（P（x） R（x），x（Q（x） R（x），x（S（x）R（x）x（S（x）P（x）R（x）解（1）x（S（x）R（x） P（2）S（y）R（y）

9、 US（1）（3）x（P（x） R（x） P（4）P（y） R（y） US（3）（5）R（y）P（y） T（4）E（6）x（Q（x） R（x） P（7）Q（y） R（y） US（6）（8）R（y）Q（y） T（7）E （9）S（y）P（y） T（2）（5）I（10）S（y）Q（y） T（2）（8）I（11）（S（y）P（y）（S（y）Q（y） T（9）（10）I（12）（S（y）P（y）（S（y）Q（y） T（11）E（13）S（y）（P（y）Q（y） T（12）E（14）S（y）（P（y）Q（y） T（13）E（15）x（S（x）P（x）R（x） UG（14）第六章，集合代數(shù)自然數(shù)集合N(在

10、離散數(shù)學(xué)中認(rèn)為0也是自然數(shù))，整數(shù)集合Z，有理數(shù)集合Q，實(shí)數(shù)集合R，復(fù)數(shù)集合C 全集U，空集是一切集合的子集（1）冪等律：AAA AAA （2）同一律：AUA（3）零律：A AEE（4）結(jié)合律：(AB)CA(BC) (AB)CA(BC) （5）交換律：ABBA ABBA (6) 分配律 A（BC）（AB）（AC） A（BC）（AB）（AC） 吸收律 A（AB）A A（AB）A 同一律 AA AEA A-B稱為集合B關(guān)于A的補(bǔ)集 -Bx|x且xB補(bǔ)集記作A（AB）AB（AB）AB （1）雙重否定律：（A）A（2） 摩根律：U U A(BC)(AB)(AC)A(BC)(AB)(AC)(BC)=BC

11、(BC)=BC（4）矛盾律：A（A）（5） 排中律：A（A）U集合A和B的對稱差記作AB，它是一個(gè)集合，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。AB(AB)-(AB)（1）AA（1）（2）AA（3）A（4）ABBA（5）（AB）CA（BC）（6）AB(A-B)(B-A)第7章 ，二元關(guān)系A(chǔ)×B=<x，y>xAyBA×B=a，b×c，d=<a，c>，<a，d>，<b，c>，<b，d>自反性和反自反性 定義4.10 設(shè)R是集合A上的二元關(guān)系，如果對于每個(gè)xA，都有<x，x>R，則稱二元關(guān)

12、系R是自反的。R在A上是自反的x（xA<x，x>R） 定義4.11 設(shè)R是集合A上的二元關(guān)系，如果對于每個(gè)xA，都有<x，x >R，則稱二元關(guān)系R是反自反的。R在A上是反自反的x（xA< x，x >R） 4.4.2 對稱性和反對稱性 定義4.12 設(shè)R是集合A上的二元關(guān)系，如果對于每個(gè)x，yA，當(dāng)<x，y>R，就有<y，x>R，則稱二元關(guān)系R是對稱的。R在A上是對稱的xy（xAyA<x，y>R<y，x>R） 定義4.13 設(shè)R是集合A上的二元關(guān)系，如果對于每個(gè)x，yA，當(dāng)<x，y>R和<y，x

13、>R時(shí)，必有x=y，則稱二元關(guān)系R是反對稱的。 4.4.3 傳遞性 定義4.14 設(shè)R是集合A上的二元關(guān)系，如果對于任意x，y，zA，當(dāng)<x，y>R，<y，z>R，就有<x，z>R，則稱二元關(guān)系R在A上是傳遞的。R在A上是傳遞的xyz（xAyAzA<x，y>R<y，z>R<x，z>R） 例4.13 設(shè)A=a，b，c，R，S，T是A上的二元關(guān)系，其中R=<a，a>，<b，b>，<a，c>S=<a，b>，<b，c>，<c，c>T=<a，b>說明R，S，T是否為A上的傳遞關(guān)系。解 根據(jù)傳遞性的定義知，R和T是A上的傳遞關(guān)系，S不是A上的傳遞關(guān)系，因?yàn)?lt;a，b>R，<b，c>R，但<a，c>R。如果R是自反的、反對稱的和傳遞的，則稱R為A上的偏序關(guān)系，記作。設(shè)為偏序關(guān)系，如