離散數(shù)學重點筆記.doc

第一章， 0命題邏輯素數(shù) = 質數(shù)，合數(shù)有因子 和 或 假必真 同為真(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。若公式A是單個的命題變項，則稱A為0層合式(pq)r，(pq)(rs)p)分別為3層和4層公式【例】求下列公式的真值表，并求成真賦值和成假賦值。 (pq)r公式(1)的成假賦值為011，其余7個賦值都是成真賦值第二章， 命題邏輯等值演算（1）雙重否定律 AA（2）等冪律 AAA ； AAA（3）交換律 ABBA ； ABBA（4）結合律 （AB）CA（BC） ； （AB）CA（BC）（5）分配律 （AB）C（AC）（BC） ； （AB）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）蘊涵等值式 ABAB（13）假言易位 ABBA（14）等價等值式 AB（AB）（BA）（15）等價否定等值式 ABABBA（16）歸繆式 （AB）（AB）AAi(i=1,2,s)為簡單合取式，則A=A1A2As為析取范式 (pq)(qr)p A=A1A2As為合取范式 (pqr)(pq)r 一個析取范式是矛盾式當且僅當它的每個簡單合取式都是矛盾式一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式 主范式 【小真，大假】 成真 小寫【例】 (pq)(qp) = (pq)(qp) (消去) = (pq)pq (內移) (已為析取范式) = (pq)(pq)(pq)(pq)(pq) （*） = m2m0m1m1m3 = m0m1m2m3 (冪等律、排序) (*)由p及q派生的極小項的過程如下： p = p(qq) = (pq)(pq) q = (pp)q = (pq)(pq) 熟練之后，以上過程可不寫在演算過程中。 該公式中含n=2個命題變項，它的主析取范式中含了22=4個極小項，故它為重言式，00，01，10，11全為成真賦值?！纠?pq)p = (pq)p (消去) = p(pq) (分配律、冪等律) 已為析取范式 = (pq)(pq) = m0m1【例】(pq)(pq) = (pp)(pq)(qp)(qq) = (pq)(pq)重言蘊涵式 【例】用附加前提證明法證明下面推理。前提：P（QR），SP，Q 結論：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 結論：SR證明（1）（SR） 附加前提引入規(guī)則 （2）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,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) 謂詞邏輯的等價公式 定理1 設A（x）是謂詞公式，有關量詞否定的兩個等價公式：（1）x A（x）xA（x）（2）x A（x）xA（x）定理2 設A（x）是任意的含自由出現(xiàn)個體變項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（x） 定理3 設A（x）、B（x）是任意包含自由出現(xiàn)個體變元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 下列蘊涵式成立（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中構造下面推理的證明 （1）所有的人或者是吃素的或者是吃葷的，吃素的常吃豆制品，因而不吃豆制品的人是吃葷的。（個體域為人的集合）。 （2）每個喜歡步行的人都不喜歡騎自行車，每個人或者是喜歡騎自行車或者喜歡乘汽車，有的人不喜歡乘汽車，所以有的人不喜歡步行。（個體域為人的集合）?！纠糠柣旅娴拿}“所有的有理數(shù)都是實數(shù)，所有的無理數(shù)也是實數(shù)，任何虛數(shù)都不是實數(shù)，所以任何虛數(shù)既不是有理數(shù)也不是無理數(shù)”，并推證其結論。證明 設：P（x）：x是有理數(shù)。 Q（x）：x是無理數(shù)。 R（x）：x是實數(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） 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(在離散數(shù)學中認為0也是自然數(shù))，整數(shù)集合Z，有理數(shù)集合Q，實數(shù)集合R，復數(shù)集合C 全集U，空集是一切集合的子集（1）冪等律：AAA AAA （2）同一律：AUA（3）零律：A AEE（4）結合律：(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關于A的補集 -Bx|x且xB補集記作A（AB）AB（AB）AB （1）雙重否定律：（A）A（2） 摩根律：U U A(BC)(AB)(AC)A(BC)(AB)(AC)(BC)=BC(BC)=BC（4）矛盾律：A（A）（5） 排中律：A（A）U集合A和B的對稱差記作AB，它是一個集合，其元素或屬于A，或屬于B，但不能既屬于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章 ，二元關系AB=xAyBAB=a，bc，d=，自反性和反自反性 定義4.10 設R是集合A上的二元關系，如果對于每個xA，都有R，則稱二元關系R是自反的。R在A上是自反的x（xAR） 定義4.11 設R是集合A上的二元關系，如果對于每個xA，都有R，則稱二元關系R是反自反的。R在A上是反自反的x（xAR） 4.4.2 對稱性和反對稱性 定義4.12 設R是集合A上的二元關系，如果對于每個x，yA，當R，就有R，則稱二元關系R是對稱的。R在A上是對稱的xy（xAyARR） 定義4.13 設R是集合A上的二元關系，如果對于每個x，yA，當R和R時，必有x=y，則稱二元關系R是反對稱的。 4.4.3 傳遞性 定義4.14 設R是集合A上的二元關系，如果對于任意x，y，zA，當R，R，就有R，則稱二元關系R在A上是傳遞的。R在A上是傳遞的xyz（xAyAzARRR） 例4.13 設A=a，b，c，R，S，T是A上的二元關系，其中R=，S=，T=說明R，S，T是否為A上的傳遞關系。解 根據(jù)傳遞性的定義知，R和T是A上的傳遞關系，S不是A上的傳遞關系，因為R，R，但R。如果R是自反的、反對稱的和