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

word文檔精品文檔分享第一章，0命題邏輯素數(shù)=質(zhì)數(shù)，合數(shù)有因子和或假必真同為真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r→(r→q)等不是合式公式。假設(shè)公式A是單個的命題稱A為0層合式(┐∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分為3層和4層公式【例】求以下公式的真值表，并求成真賦值和成假賦值。(┐p∧q)→┐r公式(1)的成假賦值為011，其余7個賦值都是成真賦值第二章，命題邏輯等值算〔〕雙重否認律AA〔〕等冪律A∧AA；A∨AA〔〕交換律A∧B∧A；A∨B∨A〔〕結(jié)合律〔∧〕∧C∧〔∧〕；〔∨〕∨C∨〔∨〕〔〕分配律〔∧〕∨C〔∨〕∧〔∨〕；〔∨〕∧C〔∧〕∨〔∧〕〔〕德·摩根律〔∨〕∧B；〔∧〕∨B〔〕吸收律A∨〔∧〕；∧〔∨〕A〔〕零一律A∨11；A∧00〔〕同一律A∨0A；A∧1A〔〕排中律A∨A1〔〕矛盾律A∧A0〔〕蘊涵等值式A→B∨B〔〕假言易位A→B→A〔〕等價等值式AB〔→〕∧〔→〕〔〕等價否認等值式ABABBA〔〕歸式〔→〕∧〔→〕Aword文檔精品文檔分享i(i=1,2,?,s)為簡單合取式，A=A∨∨?∨s為析取X式(p∧┐q)∨(┐q∧┐r)∨pA=A1∧2∧?∧s為合取X式(p∨q∨r)∧(┐p∨┐q)∧r一個析取X式是矛盾式當且僅當它的每個簡單合取式都是矛盾式一個合取X式是重言式當且僅當它的每個簡單析取式都是重言式主X式【∧小真，∨大假】∧成真小寫【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)(消去→)=(p∧┐q)∨┐∨q(┐內(nèi)移)(已為析取X式)=(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐∧q)∨(p∧q)〔*〕=m2∨m0∨m1∨m1∨m3=m0∨m1∨m2∨m3(冪等律、排)(*)由┐p及q派生的極小項的過程如：┐p=┐p∧(┐∨q)=(┐p∧┐q)∨(┐∧q)q=(┐∨p)∧q=(┐p∧q)∨(p∧q)熟練之后，以上過程可不寫在演算過程中。該公式中n=2個命題變項，它的主析取X式中了22=4個極小項，故它為重言式，00，01，10，11全為成真【例】(p→q)∧┐p=(┐p∨q)∧┐p(消去→)=┐p∨(┐∧q)(分配律、冪等律)已為析取X式word文檔精品文檔分享=(┐p∧┐q)∨(┐∧q)=m0∨m1【例】(p∧┐q)∨(┐p∧q)=(p∨┐p)∧∨q)∧(┐q∨┐p)∧(┐∨q)=(p∨q)∧┐∧q)重言蘊涵式【例】用附加前提證明法證明下面推理。前提：→〔→∨，Q結(jié)：→R〕∨P前提引入那么〔〕S附加前提引入那么〔〕P〔〕析取三段〔〕→〔→〕前提引入那么〔〕→R〔34〕假言推理那么〔〕Q前提引入那么〔〕R〔5〕假言推理那么【例】用歸繆法證明。前提：∨，→，→S結(jié)：∨R證明〔1〕〔∨〕附加前提引入那么〔2〕∧R〔1〕置〔3〕S〔〕化〔4〕R〔〕化〔5〕→S前提引入那么〔6〕∨S〔〕置〔7〕Q〔3〕析取三段論〔8〕∨Q前提引入那么〔9〕P〔8〕析取三段〔10〕→R前提引入那么word文檔精品文檔分享〔11〕∨R〔10〕置〔12〕R〔11〕析取三段〔13〕∧R〔12〕合取引入那么全稱量"""∨"無分配律。同樣的，存在量"""∧"無分配律(3)xyF(x,y)x(F(x,a)∧F(x,b)∧F(x,c))word文檔精品文檔分享(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〔x〕是謂詞公式，有關(guān)量詞否認的兩個等價公式：〔〕xA〔x〕x〔x〕〔〕xA〔x〕x〔x〕定理2〔x〕是任意的含自由出現(xiàn)個體項x的公式，B是不含x出現(xiàn)的公式，那么有〔〕x〔〔x〕∨〕xA〔〕∨B〔〕x〔〔x〕∧〕xA〔〕∧B〔〕x〔〔x〕→B〕xA〔x〕→B〔〕x〔→〔x→xA〔x〕〔〕x〔〔x〕∨〕xA〔x〕∨B〔〕x〔〔x〕∧〕xA〔x〕∧B〔〕x〔〔x〕→B〕xA〔x〕→B〔〕x〔→〔x→xA〔x〕定理3〔x〔〕是任意包含自由出現(xiàn)個體元x的公式,那么有：〔〕x〔〔x〕∧〔xA〔x〕∧xB〔x〕〔〕x〔〔x〕∨〔xxA〔x〕∨xB〔〕定理4以下蘊涵式成立〔〕xA〔x〕∨xB〔x〕x〔〔x〕∨〔x〔〕x〔〔x〕∧〔xxA〔x〕∧xB〔x〕〔〕x〔〔x〕→B〔xxA〔x〕→xB〔x〕〔〕x〔〔x〕→B〔xxA〔x〕→xB〔x〕〔〕xA〔x〕→xB〔x〕x〔〔x〕→B〔xword文檔精品文檔分享【例】【例】【例】word文檔精品文檔分享【例】word文檔精品文檔分享【例】在一階邏輯自然推理系統(tǒng)F中構(gòu)造下面推理的證明〔1〕所有的人或者是吃素的或者是吃葷的，吃素的常吃豆制品，因而不吃豆制品的人是吃葷的?！矀€體域為人的集合〕?！?〕每個喜歡步行的人都不喜歡騎自行車，每個人或者是喜歡騎自行車或者喜歡乘汽車，有的人不喜歡乘汽車，所以有的人不喜歡步行?！矀€體域為人的集合〕。word文檔精品文檔分享【例】符號化下面的命題以任何虛數(shù)既不是有理數(shù)也不是無理數(shù)證設(shè)：〔xx是有理數(shù)。Q〔xx是無理數(shù)。R〔xx是實數(shù)。S〔xx是虛數(shù)。此題符號化：x〔〔x〕→R〔xx〔〔x〕→R〔xx〔〔x〕→〔xx〔〔x〕→〔x〕〔x〔〕x〔〔x〕→〔xP〔〕〔y〕→〔y〕US〔1〕〔〕x〔〔x〕→R〔xP〔〕〔y〕→R〔y〕US〔3〕〔〕〔y〕→〔y〕T〔4〕E〔〕x〔〔x〕→R〔xP〔〕〔y〕→R〔y〕US〔6〕〔〕〔y〕→〔y〕T〔7〕E〔〕〔y〕→P〔y〕T〔5〕I〔〕S〔〕→Q〔y〕T〔28〕I〔〔y〕→P〔y〔y〕→Q〔y〕T〔10〕I〔〔y〕∨〔yS〔y〕∨Q〔yT〔11〕E〔〕S〔y〕∨〔P〔〕∧Q〔yT〔12〕Eword文檔精品文檔分享〔〕S〔〕→〔P〔y〕∧Q〔yT〔13〕E〔〕x〔S〔x〕→P〔x〕∧〔xUG〔14〕第六章，集合代數(shù)自然數(shù)集合在離散數(shù)學(xué)中為0也是自然數(shù))，整數(shù)集合，有理數(shù)集合，實數(shù)集合，復(fù)數(shù)集合C全集U，空集是一切集合的子集〔〕冪等律：∩A＝AA∪A＝A〔〕同一律：∩U＝A〔〕零律：∩＝A∪E＝E〔〕結(jié)合律：(A∩B)∩C＝∩(B∩C)(A∪B)∪＝A∪(B∪C)〔〕交換律：∩B＝∩AA∪B＝B∪A(6)分配律B∪C〕＝〔∩B〕∪〔∩C〕A∪〔∩C〕＝〔A∪BA∪〕吸收律A∪〔∩B〕＝A∩〔A∪B〕＝A同一律A∪＝A∩E＝AA-B稱為集合B關(guān)于A的補集Ａ-B＝｛x|xＡ且xB｝補集~A~〔A∪B〕＝∩~B~〔∩B〕＝~A∪~B〔〕雙重否認律：〔~A〕＝A〔〕摩根律：~＝U~U＝A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)=～∩～C～(B∩～B∪～C〔〕矛盾律：∩〔~A〕＝〔〕排中律：A∪〔~A〕＝U集合A和B的對稱差A(yù)B，它是一個集合，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。AB＝(A∪B)-(A∩B)〔〕AA＝〔〕A＝Aword文檔精品文檔分享〔〕AＵ＝~Ａ〔〕AB＝BA〔AB〕＝A〔BC〕〔〕AB＝(A-B)∪(B-A)第七章，二元關(guān)系B={<x，y>x∈∧y∈B}A×B={a，b}×{c，d}={<a，c>，，d>，<b，c>，<b，d>}自反性和反自反性定4.10R是集合A上的二元關(guān)系，如果對于每xA，都有<x，x>R，那么稱二元關(guān)系R是自反的。R在A上是自反的x〔xA<x，x>R〕定4.11R是集合A上的二元關(guān)系，如果對于每xA，都有<x，x>R，那么稱二元關(guān)系R是反自反的。word文檔精品文檔分享R在A上是反自反的x〔xA<x，x>R〕4.4.2對稱性和反對稱性定4.12R是集合A上的二元關(guān)系，如果對于每x，yA，當<x，y>R，就有<y，x>R，那么稱二元關(guān)系R是對稱的。R在A上是對稱的xy〔xA∧yA∧<x，y>R<y，x>R〕定4.13R是集合A上的二元關(guān)系，如果對于每x，yA，當<x，y>R和<y，x>R時，必有x=y，那么稱二元關(guān)系R是反對稱的。4.4.3傳遞性定4.14R是集合A上的二元關(guān)系，如果對于任x，y，zA，當<x，y>R，<y，z>，就有<x，z>R，那么稱二元關(guān)系R在A上是傳遞的。R在A上是傳遞的xy〔xA∧yA∧zA∧<x，y>R∧<y，z>R<x，z>R〕例A={a，b，c}，R，S，T是A上的二元關(guān)系，其中R={<a，，<b，，，c>}S={<a，，<b，c>，<c，c>}T={<a，b>}說R，，T是否為A上的傳遞關(guān)系。解根據(jù)傳遞性的定R和T是A上的傳遞關(guān)系，S不是A上的傳遞關(guān)系，為，b>R，<b，c>R，但，c>R。如果R是自反的、反對稱的和傳遞的，那么稱R為A上的偏序關(guān)系，記作。為偏序關(guān)系，如果<x，y>∈，那么記作xy，讀作“小于或等