離散數(shù)學(xué)知識(shí)匯編

...wd......wd......wd...離散數(shù)學(xué)筆記第一章命題邏輯合取析取定義1.1.3否認(rèn)：當(dāng)某個(gè)命題為真時(shí)，其否認(rèn)為假，當(dāng)某個(gè)命題為假時(shí)，其否認(rèn)為真定義1.1.4條件聯(lián)結(jié)詞，表示“如果……那么……〞形式的語句定義1.1.5雙條件聯(lián)結(jié)詞，表示“當(dāng)且僅當(dāng)〞形式的語句定義1.2.1合式公式(1)單個(gè)命題變元、命題常元為合式公式，稱為原子公式。(2)假設(shè)某個(gè)字符串A是合式公式，則A、(A)也是合式公式。(3)假設(shè)A、B是合式公式，則AB、AB、AB、AB是合式公式。(4)有限次使用(2)~(3)形成的字符串均為合式公式。1.3等值式1.4析取范式與合取范式將一個(gè)普通公式轉(zhuǎn)換為范式的基本步驟1.6推理定義1.6.1設(shè)A與C是兩個(gè)命題公式，假設(shè)A→C為永真式、重言式，則稱C是A的有效結(jié)論，或稱A可以邏輯推出C，記為A=>C?！灿玫戎笛菟慊蛘嬷当怼车诙轮^詞邏輯2.1、基本概念?：全稱量詞?：存在量詞一般情況下，如果個(gè)體變元的取值范圍不做任何限制即為全總個(gè)體域時(shí)，帶“全稱量詞〞的謂詞公式形如"?x(H(x)→B(x))，即量詞的后面為條件式，帶“存在量詞〞的謂詞公式形如?x(H(x)∨WL(x))，即量詞的后面為合取式例題R(x)表示對象x是兔子，T(x)表示對象x是烏龜，H(x,y)表示x比y跑得快，L(x,y)表示x與y一樣快，則兔子比烏龜跑得快表示為：?x?y(R(x)∧T(y)→H(x,y))有的兔子比所有的烏龜跑得快表示為：?x?y(R(x)∧T(y)→H(x,y))2.2、謂詞公式及其解釋定義2.2.1、非邏輯符號(hào)：個(gè)體常元(如a,b,c)、函數(shù)常元(如表示的f(x,y))、謂詞常元(如表示人類的H(x))。定義2.2.2、邏輯符號(hào)：個(gè)體變元、量詞(??)、聯(lián)結(jié)詞(﹁∨∧→?)、逗號(hào)、括號(hào)。定義2.2.3、項(xiàng)的定義：個(gè)體常元、變元及其函數(shù)式的表達(dá)式稱為項(xiàng)(item)。定義2.2.4、原子公式：設(shè)R()是n元謂詞，是項(xiàng)，則R(t)是原子公式。原子公式中的個(gè)體變元，可以換成個(gè)體變元的表達(dá)式(項(xiàng))，但不能出現(xiàn)任何聯(lián)結(jié)詞與量詞，只能為單個(gè)的謂詞公式。定義2.2.5合式公式：(1)原子公式是合式公式；(2)假設(shè)A是合式公式，則(﹁A)也是合式公式；(3)假設(shè)A,B合式，則A∨B,A∧B,A→B,A?B合式(4)假設(shè)A合式，則?xA、?xA合式(5)有限次使用(2)~(4)得到的式子是合式。定義2.2.6量詞轄域：?xA和?xA中的量詞?x/?x的作用范圍，A就是作用范圍。定義2.2.7約束變元：在?x和?x的轄域A中出現(xiàn)的個(gè)體變元x，稱為約束變元，這是與量詞相關(guān)的變元，約束變元的所有出現(xiàn)都稱為約束出現(xiàn)。定義2.2.8自由變元：謂詞公式中與任何量詞都無關(guān)的量詞，稱為自由變元，它的每次出現(xiàn)稱為自由出現(xiàn)。一個(gè)公式的個(gè)體變元不是約束變元，就是自由變元。注意：為了防止約束變元和自由變元同名出現(xiàn)，一般要對“約束變元〞改名，而不對自由變元改名。定義2.2.9閉公式是指不含自由變元的謂詞公式從本例(已省)可知，不同的公式在同一個(gè)解釋下，其真值可能存在，也可能不存在，但是對于沒有自由變元的公式(閉公式)，不管做何種解釋，其真值肯定存在謂詞公式的類型：重言式(永真式)、矛盾式(永假式)、可滿足公式三種類型定義2.2.10在任何解釋下，公式的真值總存在并為真，則為重言式或永真式。定義2.2.11在任何解釋下，公式的真值總存在并為假，則為矛盾式或永假式。定義2.2.12存在個(gè)體域并存在一個(gè)解釋使得公式的真值存在并為真，則為可滿足式。定義2.2.13代換實(shí)例設(shè)是命題公式中的命題變元，是n個(gè)謂詞公式，用代替公式中的后得到公式A，則稱A為的代換實(shí)例。如A(x)∨﹁A(x)，?xA(x)∨﹁?xA(x)可看成p∨﹁p的代換實(shí)例，A(x)∧﹁A(x)，?xA(x)∧﹁?xA(x)可看成p∧﹁p的代換實(shí)例。定理2.2.1命題邏輯的永真公式之代換實(shí)例是謂詞邏輯的永真公式，命題邏輯的永假公式之代換實(shí)例是謂詞邏輯的永假式?！泊鷵Q前后是同類型的公式〕2.3、謂詞公式的等值演算定義2.3.1設(shè)A、B是兩個(gè)合法的謂詞公式，如果在任何解釋下，這兩個(gè)公式的真值都相等，則稱A與B等值，記為AB。當(dāng)AB時(shí)，根據(jù)定義可知，在任何解釋下，公式A與公式B的真值都一樣，故A?B為永真式，故得到如下的定義。定義2.3.2設(shè)A、B是兩個(gè)合法謂詞公式，如果在任何解釋下，A?B為永真式，則A與B等值，記為AB。一、利用代換實(shí)例可證明的等值式(p?﹁﹁p永真，代換實(shí)例?xF(x)?﹁﹁?xF(x)永真)二、個(gè)體域有限時(shí)，帶全稱量詞、存在量詞公式的等值式如：假設(shè)D={}，則?xA(x)A()∧A()∧…∧A()三、量詞的德摩律1、﹁?xA(x)?x﹁A(x)2、﹁?xA(x)?x﹁A(x)四、量詞分配律1、?x(A(x)∧B(x))?xA(x)∧?xB(x)2、?x(A(x)∨B(x))?xA(x)∨?xB(x)記憶方法：?與∧，一個(gè)尖角朝下、一個(gè)尖角朝上，相反可才分配。2式可看成1式的對偶式五、量詞作用域的收縮與擴(kuò)張律A(x)含自由出現(xiàn)的個(gè)體變元x，B不含有自由出現(xiàn)的x，則有：1、?/?(A(x)∨B)?/?A(x)∨B2、?/?(A(x)∧B)?/?A(x)∧B對于條件式A(x)?B，利用“基本等值一〞將其轉(zhuǎn)換為析取式，再使用德摩律進(jìn)展演算六、置換規(guī)則假設(shè)B是公式A的子公式，且BC，將B在A中的每次出現(xiàn)，都換成C得到的公式記為D，則AD七、約束變元改名規(guī)則將公式A中某量詞的指導(dǎo)變元及轄域中約束變元每次約束出現(xiàn)，全部換成公式中未出現(xiàn)的字母，所得到的公式記為B，則AB例證明步驟：2.4、謂詞公式的范式從定理證明過程，可得到獲取前束范式的步驟：(1)剔除不起作用的量詞；(2)如果約束變元與自由變元同名，則約束變元改名；(3)如果后面的約束變元與前面的約束變元同名，則后的約束變元改名；(4)利用代換實(shí)例，將→、?轉(zhuǎn)換﹁∨∧表示；(5)利用德摩律，將否認(rèn)﹁深入到原子公式或命題的前面；(6)利用量詞轄域的擴(kuò)張與收縮規(guī)律或利用量詞的分配律，將量詞移到最左邊2.5、謂詞推理定義2.5.1假設(shè)在各種解釋下只能為真即為永真，則稱為前提可推出結(jié)論B。定義2.5.2在所有使為真的解釋下，B為真，則稱為前提可推出結(jié)論B。謂詞邏輯的推理方法分為以下幾類：一、謂詞邏輯的等值演算原則、規(guī)律：代換實(shí)例、量詞的德摩律、量詞的分配律、量詞轄域的擴(kuò)張與收縮、約束變元改名。二、命題邏輯的推理規(guī)則的代換實(shí)例，如假言推理規(guī)則、傳遞律、合取與析取的性質(zhì)律、CP規(guī)則、反證法等。三、謂詞邏輯的推理公理第三章集合與關(guān)系3.1、基本概念在離散數(shù)學(xué)稱“不產(chǎn)生歧義的對象的聚集一塊〞便構(gòu)成集合。常用大寫字母表示集合，如R表示實(shí)數(shù)，N表示自然數(shù)，Z表示整數(shù)，Q表示有理數(shù)，C表示復(fù)數(shù)。描述一個(gè)集合一般有“枚舉法〞與“描述法〞，“枚舉法〞。元素與集合之間有“屬于〞或“不屬于〞二種關(guān)系。定義3.1.1設(shè)A，B是兩個(gè)集合，如果A中的任何元素都是B中的元素，則稱A是B的子集，也稱B包含于A，記為BA，也稱A包含B，記為AB。3.2集合運(yùn)算性質(zhì)定義3.2.1設(shè)A、B為集合，A與B的并集AB、A與B的的交集AB、A-B的定義：AB={x|xAxB}，AB={x|xAxB}，A-B={x|xAxB}定義3.2.2設(shè)A、B為集合，A與B的對稱差，記為AB={x|(xAxB)(xAxB)}=AB-AB。定義3.2.3設(shè)A、B是兩個(gè)集合，假設(shè)AB、BA則A=B，即兩個(gè)集合相等。冪等律AA=A、AA=A結(jié)合律ABC=A(BC)=(AB)CABC=A(BC)=(AB)C交換律AB=BA、AB=BA分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一/零律A?=A、A?=?排中/矛盾律AA=E、AA=?吸收律(大吃小)A(BA)=A、A(BA)=A德摩律(AB)=AB、(AB)=AB雙重否認(rèn)A=A3.3、有窮集的計(jì)數(shù)定理3.3.1二個(gè)集合的包含排斥原理||=||+||-||3.4、序偶定義3.4.2令<x,y>與<u,v>是二個(gè)序偶，如果x=u、y=v，那么<x,y>=<u,v>即二個(gè)序偶相等。定義3.4.3如果<x,y>是序偶，且<<x,y>,z>也是一個(gè)序偶，則稱<x,y,z>為三元組。3.5、直積或笛卡爾積定義3.5.1令A(yù)、B是兩個(gè)集合，稱序偶的集合{<x,y>|xA,yB}為A與B的直積或笛卡爾積，記為AB。如：A={1,2,3}，B={a,b,c}則AB={1,2,3}{a,b,c}={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}直積的性質(zhì)1、A(BC)=ABAC2、A(BC)=ABAC3、(BC)A=BACA4、(BC)A=BACA5、ABACBCCACB6、AB,CDACBD定義3.5.2令是n個(gè)集合，稱n元組的集合{<>|}，為的直積或笛卡爾積，記為。3.6、關(guān)系定義3.6.1稱直積中局部感興趣的序偶所組成的集合為“關(guān)系〞，記為R。如在直積{1,2,3,4,5,6,7,8}{1,2,3,4,5,6,7,8}中，只對第1個(gè)元素是第2個(gè)元素的因數(shù)的序偶感興趣，即只對R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>}，RAA〔A={1,2,3,4,5,6,7,8}〕定義3.6.2如果序偶或元組屬于某個(gè)關(guān)系R，則稱序偶或元組具有關(guān)系R。關(guān)系圖，關(guān)系矩陣3.7、關(guān)系的復(fù)合定義3.7.1假設(shè)關(guān)系FAA，關(guān)系GAA，稱集合{<x,y>|t使得<x,t>F，<t,y>G}為F與G的復(fù)合，記為FG。例題3.7.1令A(yù)={1,2,3}，F(xiàn)={<1,1>,<1,2>}G={<2,2>,<1,3>,<1,1>}則解：FG={<1,3>,<1,1>,<1,2>}，GF={<1,2>,<1,1>}，因此關(guān)系的復(fù)合不滿足交換律。采用復(fù)合的定義去計(jì)算，只適合于人工計(jì)算，為了編程實(shí)現(xiàn)，故采用矩陣表示關(guān)系。說明：的第i行與的第j列相乘時(shí)，乘法是合取，加法是析取，如MF的1行與MG的第3列相乘是：(11)(10)(00)，結(jié)果為1。定義3.7.2假設(shè)關(guān)系FAA，稱集合{<y,x>|<x,y>F}為F的逆，記為例題3.7.2令A(yù)={1,2,3}，F(xiàn)={<1,2>,<1,3>,<2,1>}，則={<2,1>,<3,1>,<1,2>}。3.8、關(guān)系的分類定義3.8.1假設(shè)都有<x,x>R，則R是自反關(guān)系。(自己到自己的關(guān)系全屬于R)定義3.8.2假設(shè)都有<x,x>R,則R是反自反的。(自己到自己的關(guān)系全不屬于R)定義3.8.4如果所有形如<x,x>的序偶都在關(guān)系R中，R也只有這種形式的序偶，則稱R為恒等關(guān)系，記為。對于恒等關(guān)系而言，其關(guān)系矩陣是單位矩陣，即其主對角線全是1，其他位置全是0，對關(guān)系圖是每個(gè)點(diǎn)都有自旋，僅只有自旋，沒有其他邊。定義3.8.5令關(guān)系RAA，如果當(dāng)<x,y>R時(shí)<y,x>R，則稱R為對稱關(guān)系。定義3.8.6令關(guān)系RAA，如果當(dāng)<x,y>R且xy時(shí)<y,x>R，則稱R為反對稱關(guān)系。定義3.8.8令關(guān)系RAA，假設(shè)當(dāng)<x,y>R,<y,z>R時(shí)有<x,z>R，則稱R為可傳遞關(guān)系。從RR的關(guān)系矩陣可知，其非0元素在R的關(guān)系矩陣都出現(xiàn)，即，凡滿足這個(gè)不等式的關(guān)系，肯定為可傳遞關(guān)系。所以不可傳遞。從RR的關(guān)系矩陣可知，其非0元素出現(xiàn)在(1,1)，(1,3)，(2,2)，(2,4)，在R的關(guān)系矩陣都沒出現(xiàn)，不滿足，不可傳遞關(guān)系。3.9、關(guān)系的閉包將關(guān)系矩陣的主角線上全部變成1，即得到其自反閉包的關(guān)系矩陣，從而可得到其自反閉包。3.10、等價(jià)關(guān)系與集合的劃分定義3.10.1設(shè)RAA，如果R是自反、對稱、可傳遞的關(guān)系則稱為等價(jià)關(guān)系。定義3.10.2設(shè)RAA，如果R是等價(jià)關(guān)系，BA，B中任意二個(gè)元素之間都有關(guān)系R，則B是一個(gè)等價(jià)類。定義3.10.3設(shè)RAA，R是等價(jià)關(guān)系，是基于R得到的等價(jià)類，則稱集合{}為A關(guān)于R的商集，記為A/R。定義3.10.3假設(shè)是A的子集，假設(shè)時(shí)，并且，則稱是A的一個(gè)劃分。定理3.10.1設(shè)RAA，R是等價(jià)關(guān)系，是利用R得到的k個(gè)不同的等價(jià)類，則為集合A的劃分。定理3.10.2設(shè)是A的劃分，R=，則R是等價(jià)關(guān)系。3.11、偏序關(guān)系定義3.11.1設(shè)RAA，如果R是自反、反對稱、可傳遞的關(guān)系則稱為偏序關(guān)系。如：R是實(shí)數(shù)中小于等于關(guān)系，則R是偏序關(guān)系。定義3.11.2設(shè)RAA，R偏序關(guān)系，x與y是A中的元素，假設(shè)序偶<x,y>與<y,x>至少有一個(gè)在R中，則稱x與y可比。定義3.11.3設(shè)RAA，R偏序關(guān)系，假設(shè)A中任意二個(gè)元素都可比，則稱A為全序關(guān)系或線序關(guān)系。定義3.11.4設(shè)RAA，R偏序關(guān)系，將關(guān)系圖繪制成所有箭頭都朝上，然后去掉所有箭頭、去掉自旋邊、去掉復(fù)合邊，得到關(guān)系圖的簡化形式，稱為哈斯圖。定義3.11.5在哈斯圖中，如果某個(gè)元素y在元素x的直接上方，則稱y蓋住了x。記COVA={<x,y>}定義3.11.6設(shè)RAA，R偏序關(guān)系，將偏序關(guān)系與集合A一塊稱為偏序集，記為<A,R>，表示是A上的偏序關(guān)系。以后說偏序關(guān)系時(shí)，可簡單地說偏序集<A,R>。定義3.11.7在偏序集<A,R>中，BA，yB，假設(shè)都有<x,y>R，則稱y是最大元。即最大元與B中每個(gè)元素都可比，并且都比其大。定義3.11.8在偏序集<A,R>中，BA，yB，假設(shè)都有<y,x>R，則稱y是最小元。即最小元與B中每個(gè)元素都可比，并且都比其小。一個(gè)子集中沒有最大元或最小元時(shí)，可能存在極大元或極小元。定義3.11.9在偏序集<A,R>中，BA，yB，假設(shè)不存在xB使得<y,x>R，則稱y是極大元，即B中不存在比y“大〞的元素。即極大元與B中有些元素是否可比不做要求。定義3.11.10在偏序集<A,R>中，BA，yB，假設(shè)不存在xB都有<x,y>R，則稱y是極小元，不存在比y小的元素。即極小元與B中元素是否可比不做要求。定義3.11.11在偏序集<A,R>中，BA，yB，假設(shè)任意xB都有<x,y>R，則稱y是B的上界。與B中每個(gè)元素都可比，并且都B中的元素大。3.12、其它關(guān)系定義3.6.1給定集合A上的關(guān)系ρ，假設(shè)ρ是自反的、