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

第一章，0命題邏輯素?cái)?shù)=質(zhì)數(shù)，合數(shù)有因子和或假必真同為真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是單個的命題變項(xiàng)，則稱A為0層合式(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分別為3層和4層公式【例】求下列公式的真值表，并求成真賦值和成假賦值。(┐p∧q)→┐r公式(1)的成假賦值為011，其余7個賦值都是成真賦值命題邏輯等值演算第二章，（1）雙重否定律（2）等冪律AAA∧AA；A∨AA1/20（3）交換律（4）結(jié)合律（5）分配律（B∧C）A∧BB∧A；A∨BB∨A（A∧B）∧CA∧（B∧C）；（A∨B）∨CA∨（B∨C）（A∧B）∨C（A∨C）∧（B∨C）；（A∨B）∧C（A∧C）∨（6）德·摩根律（7）吸收律（8）零一律（9）同一律（10）排中律（11）矛盾律（A∨B）A∧B；（A∧B）A∨BA∨（A∧B）A；A∧（A∨B）AA∨11A∨0AA∨A1A∧A0；A∧00；A∧1A（12）蘊(yùn)涵等值式A→BA→BB→A（14）等價等值式AB（A→B）∧（B→A）A∨B（13）假言易位A（15）等價否定等值式ABABB（16）歸繆式（A→B）∧（A→B）AA(i=1,2,…,s)為簡單合取式，則A=A∨A∨…∨A為析取范式(p∧┐q)∨(┐q∧┐r)∨pi12sA=A∧A∧…∧A為合取范式(p∨q∨r)∧(┐p∨┐q)∧r12s一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式主范式【∧小真，∨大假】2/20∧成真小寫【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)=(p∧┐q)∨┐p∨q(消去→)(┐內(nèi)移)(已為析取范式)=(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)（*）=m2∨m0∨m1∨m1∨m3=m0∨m1∨m2∨m3(冪等律、排序)(*)由┐p與q派生的極小項(xiàng)的過程如下：┐p=┐p∧(┐q∨q)=(┐p∧┐q)∨(┐p∧q)q=(┐p∨p)∧q=(┐p∧q)∨(p∧q)熟練之后，以上過程可不寫在演算過程中。3/20該公式中含n=2個命題變項(xiàng)，它的主析取范式中含了22=4個極小項(xiàng)，故它為重言式，00，01，10，11全為成真賦值?！纠?p→q)∧┐p=(┐p∨q)∧┐p=┐p∨(┐p∧q)=(┐p∧┐q)∨(┐p∧q)=m0∨m1(消去→)(分配律、冪等律)已為析取范式【例】(p∧┐q)∨(┐p∧q)=(p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q)=(p∨q)∧┐(p∧q)重言蘊(yùn)涵式【例】用附加前提證明法證明下面推理。前提：P→（Q→R），S∨P，Q結(jié)論：S→R4/20證明：（1）S∨P（2）S前提引入規(guī)則附加前提引入規(guī)則（1）（2）析取三段論規(guī)則（3）P（4）P→（Q→R）前提引入規(guī)則（5）Q→R（6）Q（3）（4）假言推理規(guī)則前提引入規(guī)則（7）R（5）（6）假言推理規(guī)則【例】用歸繆法證明。前提：P∨Q，P→R，Q→S結(jié)論：S∨R證明（1）（S∨R）（2）S∧R（3）S附加前提引入規(guī)則（1）置換規(guī)則（2）化簡規(guī)則（4）R（2）化簡規(guī)則（5）Q→S（6）Q∨S（7）Q前提引入規(guī)則（5）置換規(guī)則（3）（6）析取三段論前提引入規(guī)則（8）P∨Q（9）P（7）（8）析取三段論規(guī)則前提引入規(guī)則（10）P→R（11）P∨R（12）R（10）置換規(guī)則（9）（11）析取三段論規(guī)則（4）（12）合取引入規(guī)則（13）R∧R5/20全稱量詞""對"∨"無分配律。同樣的，存在量詞""對"∧"無分配律xyF(x,y)(3)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))6/20謂詞邏輯的等價公式定理1設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個等價公式：（1）﹁xA（x）（2）﹁xA（x）x﹁A（x）x﹁A（x）定理2設(shè)A（x）是任意的含自由出現(xiàn)個體變項(xiàng)x的公式，B是不含x出現(xiàn)的公式，則有（1）x（A（x）∨B）（2）x（A（x）∧B）xA（x）∨BxA（x）∧B（3）x（A（x）→B）xA（x）→B（4）x（B→A（x））B→xA（x）（5）x（A（x）∨B）（6）x（A（x）∧B）xA（x）∨BxA（x）∧B（7）x（A（x）→B）xA（x）→B（8）x（B→A（x））B→xA（x）定理3設(shè)A（x）、B（x）是任意包含自由出現(xiàn)個體變元x的公式,則有：（1）x（A（x）∧B（x））xA（x）∧xB（x）（2）x（A（x）∨B（x））xA（x）∨xB（x）定理4下列蘊(yùn)涵式成立（1）xA（x）∨xB（x）x（A（x）∨B（x））（2）x（A（x）∧B（x））xA（x）∧xB（x）（3）x（A（x）→B（x））xA（x）→xB（x）（4）x（A（x）→B（x））xA（x）→xB（x）（5）xA（x）→xB（x）x（A（x）→B（x））7/20

【例】【例】8/20【例】9/20【例】10/20【例】在一階邏輯自然推理系統(tǒng)F中構(gòu)造下面推理的證明（1）所有的人或者是吃素的或者是吃葷的，吃素的常吃豆制品，因而不吃豆制品的人是吃葷的。（個體域?yàn)槿说募希?。?）每個喜歡步行的人都不喜歡騎自行車，每個人或者是喜歡騎自行車或者喜歡乘汽車，有的人不喜歡乘汽車，所以有的人不喜歡步行。（個體域?yàn)槿说募希?1/20【例】符號化下面的命題“所有的有理數(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）US（1）12/20（3）x（P（x）→R（x））（4）P（y）→R（y）PUS（3）（5）﹁R（y）→﹁P（y）（6）x（Q（x）→R（x））（7）Q（y）→R（y）T（4）EPUS（6）T（7）E（8）﹁R（y）→﹁Q（y）（9）S（y）→﹁P（y）T（2）（5）IT（2）（8）IT（9）（10）I（10）S（y）→﹁Q（y）（11）（S（y）→﹁P（y））∧（S（y）→﹁Q（y）（12）（﹁S（y）∨﹁P（y））∧（S（y）∨﹁Q（y））T（11）E（13）﹁S（y）∨（﹁P（y）∧﹁Q（y））（14）S（y）→（﹁P（y）∧﹁Q（y））（15）x（S（x）→﹁P（x）∧﹁R（x））T（12）ET（13）EUG（14）第六章，集合代數(shù)自然數(shù)集合N(在離散數(shù)學(xué)中認(rèn)為0也是自然數(shù))，整數(shù)集合Z，有理數(shù)集合Q，實(shí)數(shù)集合R，復(fù)數(shù)集合C全集U，空集是一切集合的子集（1）冪等律：A∩A＝AA∪A＝A（2）同一律：A∩U＝A（3）零律：A∩＝A∪E＝E（4）結(jié)合律：(A∩B)∩C＝A∩(B∩C)(A∪B)∪C＝A∪(B∪C)（5）交換律：A∩B＝B∩AA∪B＝B∪A13/20(6)分配律A∩（B∪C）＝（A∩B）∪（A∩C）A∪（B∩C）＝（A∪B）∩（A∪C）吸收律A∪（A∩B）＝AA∩（A∪B）＝A同一律A∪＝AA∩E＝AA-B稱為集合B關(guān)于A的補(bǔ)集Ａ-B＝｛x|xＡ且xB｝補(bǔ)集記作~A~（A∪B）＝~A∩~B~（A∩B）＝~A∪~B（1）雙重否定律：~（~A）＝A（2）摩根律：~＝U~U＝A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)=～B∩～C～(B∩C)=～B∪～C（4）矛盾律：A∩（~A）＝（5）排中律：A∪（~A）＝U14/20集合A和B的對稱差記作AB，它是一個集合，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。AB＝(A∪B)-(A∩B)（1）AA＝（2）A＝A（3）AＵ＝~Ａ（4）AB＝BA（5）（AB）C＝A（BC）（6）AB＝(A-B)∪(B-A)15/20第七章，二元關(guān)系A(chǔ)×B={<x，y>x∈A∧y∈B}A×B={a，b}×{c，d}={<a，c>，<a，d>，<b，c>，<b，d>}自反性和反自反性定義4.10設(shè)R是集合A上的二元關(guān)系，如果對于每個xA，都有<x，x>R，則稱二元關(guān)系R是自反的。R在A上是自反的x（xA<x，x>R）定義4.11設(shè)R是集合A上的二元關(guān)系，如果對于每個xA，都有<x，x>R，則稱二元關(guān)系R是反自反的。R在A上是反自反的x（xA<x，x>R）4.4.2對稱性和反對稱性定義4.12設(shè)R是集合A上的二元關(guān)系，如果對于每個x，yA，當(dāng)<x，y>R，就有<y，x>R，則稱二元關(guān)系R是對稱的。R在A上是對稱的xy（xA∧yA∧<x，y>R<y，x>R）定義4.13設(shè)R是集合A上的二元關(guān)系，如果對于每個x，yA，當(dāng)<x，y>R和<y，x>R時，必有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（xA∧yA∧zA∧<x，y>R∧<y，z>R<x，z>R）例4.13設(shè)A={a，b，c}，R，S，T是A上的二元關(guān)系，其中16/20R={<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)系，如果<x，y>∈，則記作xy，讀作