離散數(shù)學復習提綱(1-4章)

離散數(shù)學復習提綱命題邏輯1．（PQ）（QR）的主合取范式和主析取范式。2．試求下列公式的主析取范式：（1）；（2）（an:）3．用真值表判斷下列公式是恒真？恒假？可滿足？（1）（PP）Q（2）（PQ）Q（3）（（PQ）（QR））（PR）(an:解：真值表PQPPP（PP）Q00101011001000111000因此公式（1）為可滿足。)真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（2）為恒假。真值表PQRPQQRPR（（PQ）（QR））（PR）00011110011111010101101111111000101101011111010011111111因此公式（3）為恒真。4．┐Q（P→Q）蘊涵┐P法1：真值表法2：若┐Q（P→Q）為真，則┐Q，P→Q為真，所以Q為假，P為假，所以┐P為真。法3：若┐P為假，則P為真，再分二種情況：①若Q為真，則┐Qù（P→Q）為假②若Q為假，則P→Q為假，則┐Q（P→Q）為假根據(jù)①②，所以┐Q（P→Q）蘊涵┐P。）5．利用基本等價式證明下列命題公式為恒真公式。（（PQ）（QR））（PR）（（PQ）（P（QR）））（PQ）（PR）（an:1、證明：（（PQ）（QR））（PR）=（（PQ）（QR））（PR）=（（PQ）（QR））（PR）=（PQ）（QR）PR=（（PQ）P）（（QR）R）=（1（QP））（（QR）1）=QPQR=（QQ）PR=1PR=1（（PQ）（P（QR）））（PQ）（PR）=（（PQ）（P（QR）））（P（QR））=（P（QQR））（P（QR））=（P（QR））（P（QR））=1）6．用形式演繹法證明：{}蘊涵(an:證明：（1）規(guī)則P（2）規(guī)則Q（1）（3）規(guī)則P（4）規(guī)則Q（3）（5）規(guī)則Q（2）（4）（6）RS規(guī)則P（7）PS規(guī)則Q（5）（6）)7．用形式演繹法證明：（蘊涵A（an:、證明：(改()（1）A規(guī)則D（2）A∨B規(guī)則Q（1）（3）規(guī)則P（4）規(guī)則Q（2）（3）（5）D規(guī)則Q（4）（6）規(guī)則Q（5）（7）規(guī)則P（8）E規(guī)則Q（6）（7）（9）規(guī)則Q（1）（8））8．┐（P∧┐Q），┐Q∨R，┐R蘊涵┐P（an:（1）┐Q∨R （2）┐R （3）┐Q （4）┐（P∧┐Q） （5）┐P∨Q （6）┐P）9．某案涉及甲、乙、丙、丁四個，根據(jù)已有線索，已知：若甲、乙均未作案，則丙、丁也均未作案；若丙、丁均未作案，則甲、乙也均未作案；若甲與乙同時作案，則丙與丁有一人且只有一人作案；若乙與丙同時作案，則甲與丁同時作案或同未作案。辦案人員由此得出結(jié)論：甲是作案者。這個結(jié)論是否正確？為什么？（an:解：對問題中的四個簡單命題用P1，P2，P3，P4分別表示甲，乙，丙，丁作案，則辦案人員的推理如下：前提：1)P1P2P3P42)P3P4P1P23)P1P2(P3P4)(P3P4)4)P3P4(P1P2)(P1P2)結(jié)論：P1。(P1P2P3P4)(P3P4P1P2)(P1P2(P3P4)(P3P4))(P3P4(P1P2)(P1P2))P1不是永真式，比如：P1取假，P2取真，P3取假，P4取真時，上式為假所以P1不是前提的有效結(jié)論，所以甲是作案者的結(jié)論是錯誤的)課后習題：p8：1，5p19：7p23：6，7，8p39：4p47：4，5謂詞邏輯1．設個體域D={1，2，5}，F(xiàn)（x）：x≤2，G（x,y）：x≥y,消去（x）(F(x)（y）G(y,x))中的量詞，并討論其真值。2．所有的主持人都很有風度。李明是個學生并且是個節(jié)目主持人。因此有些學生是很有風度。請用謂詞邏輯中的推理理論證明上述推理。（個體域：所有人的集合）3．設數(shù)，小于，將“不存在最小的數(shù)。”符號化。（an:）4．利用一階邏輯的基本等價式，證明：（x）（y）（F（x）G（y））=（x）F（x）（y）G（y）(an:xy（F（x）G（y））=x（F（x）yG（y））=x（F（x）yG（y））=x（F（x））yG（y）=xF（x）yG（y）=xF（x）yG（y）)5．（x）（F(x)→┐A(x)），（x）（A(x)∨B(x)，（x）┐B(x)蘊涵（x）┐F(x)（an:（1）x┐B(x) （2）┐B(c) （3）x（A(x)∨B(x)） （4）A(c)∨B(c) （5）A(c) （6）x（F(x)→┐A(x)） （7）F(c)→┐A(c) （8）┐F(c) （9）x┐F(x)）6．符號化下列命題并推證其結(jié)論：沒有不守信用的人是可以信賴的，有些可以信賴的人是受過教育的人，因此，有些受過教育的人是可守信用的。（個體域：所有人的集合）（an:令M(x)：x是守信用的；J(x)：x是受過教育的；D(x)：x是可以信賴的前提：┐x（┐M(x)∧D(x)），（xD(x)∧J(x)）有效結(jié)論：x（J(x)∧M(x)）證明： 1）（xD(x)∧J(x)） 前提 2）xD(x)∧J(y) 代替規(guī)則 3）xD(x) 合取 4）D(c) EI規(guī)則 5）J(y) 合取 6）zJ(z) UG規(guī)則 7）J(c) UI規(guī)則8）┐x（┐M(x)∧D(x)） 前提規(guī)則 9）x┐（┐M(x)∧D(x)）等價 10）x（M(x)┐D(x)） 等價 11）M(c)┐D(c) UI規(guī)則 12）M(c) 等價 13）M(c)∧J(c) 合取 14）x（J(x)∧M(x)） EG規(guī)則)7．在一階邏輯中，構造下面的證明：前提：，F(xiàn)(a)結(jié)論:（an:1)x(F(x)G(x))2)F(a)G(a)3)F(a)4)G(a)5)G(x))8．設解釋I為：定義域D={-2，3，6}；F（x）：x3；G（x）：x5。在解釋I下求公式(x)（F（x）G（x））的真值。（an:(x)（F（x）G（x））=（F（-2）G（-2））（F（3）G（3））（F（6）G（6））=（10）（10）（01）=1）9．不存在能表示成分數(shù)的無理數(shù)。有理數(shù)都能表示成分數(shù)。因此，有理數(shù)都不是無理數(shù)。（an:F(x)：x為無理數(shù)，G(x)：x為有理數(shù)，H(x)：x能表示成分數(shù)）10．設個體域為集合{a,b,c},試消去下列公式中的量詞。（x）P(x)∧（x）Q(x)（x）（P(x)→Q(x)）課后習題：p59：1，2p62：3，6p65：2，3p72：1，4p75：1p79：2，3集合論1．設〈A，〉是偏序集，A={1，2，3，4，5，6，8}，是整除關系，請畫出〈A，〉的哈斯圖。寫出A中的極大元，極小元和最大元，最小元。2．設A={1，2，3}，求A上所有等價關系。3．設全集有下列子集A=B=C={求1）2）3）（an:）4．設集合，試求：1）A×B2）3）（an:）5．一個年級170人中，120名學生學英語，80名學生學德語，60名學生學日語，50名學生既學英語又學德語，25名學生既學英語又學日語，30名學生既學德語又學日語，還有10名學生同時學習三種語言。試問：有多少名學生這三種語言都沒有學習？（an:解：設E為全集，A為學英語學生的集合，B為學德語學生的集合，C為學日語學生的集合。由公式，|ABC|=|A|+|B|+|C|-|AB|-|BC|-|AC|+|ABC|可得：|ABC|=120+80+60-50-30-25+10=165所以，這三種語言都沒有學習的學生為170-165=5人。）6．A={a，b，c，d}，R1，R2是A上的關系，其中R1={（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。寫出R1和R2的關系矩陣，并畫出R1和R2的關系圖；判斷它們是否為等價關系，是等價關系的求A中各元素的等價類。（an:）R1為等價關系等價類M1={a,b}，M2={c,d}R2不為等價關系7．集合，R是集合A上的關系，，求，并分別畫出它們的關系圖。（an:它們的關系圖：）8．設集合，R為A上的整除關系，（1）畫出偏序集（A，R）的哈斯圖；（2）寫出集合A中的最大元、最小元、極大元、極小元；（3）寫出A的子集的上界、下界、最小上界、最大下界。（an:（1）半序集（A，R）的哈斯圖如下所示：2412623（2）集合A中的最大元是24，無最小元，極大元是24，極小元是2與3。（3）集合B的上界是12與24，無下界，最小上界是12，無最大下界。）9．設集合，試畫出偏序集的哈斯圖，并寫出A的最大元，最小元，極大元和極小元。（an:（A，）的哈斯圖為：ebcdaa為A的極小元，也是最小元；e為A的極大元，也是最大元。）11．設R是集合A上的二元關系，證明：R是傳遞的，當且僅當t（R）=R。（an:證明：若R是傳遞的，又有RR，對于任何包含R的傳遞關系，都有，所以R滿足傳遞閉包定義中的全部條件，即t（R）=R。反之，若t(R)=R，由傳遞閉包含定義中的條件1可得R是傳遞的。）12．設集合上的關系則R在A上構成的等價類是？（an:）13．設集合A=，為A上的二元關系，則是？（an:{（1，1），（1，2），（1，3），（2，1），（2，2），（2，3），（3，1），（3，2），（3，3）}）14．設R是一個二元關系，設S={<a,b>|存在某個C，使<a,c>∈R且<c,b>∈R}，證明R是一個等價關系，則S也是一個等價關系。（an:1、證明：

（1）∵R是自反，

∴若有x∈A就有＜x，x＞∈R

∴＜x，x＞∈S

∴S是自反的。

（2）因有＜a，b＞∈S

且存在c，使＜a，c＞∈R且＜c，b＞∈R

∵R是對稱的

∴＜c，a