離散數(shù)學(xué)王元元習題解答(1)

《離散數(shù)學(xué)王元元習題解答(1)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1命題演算及其形式系統(tǒng)1.1命題與聯(lián)結(jié)詞內(nèi)容提要1.1.1命題我們把對確定的對象作出判斷的陳述句稱作命題（propositions），當判斷正確或符合客觀實際時，稱該命題真（true），否則稱該命題假（false）?！罢?、假”常被稱為命題的真值。自然語言中“并非、或者、并且、如果…，那么…、當且僅當”這樣的聯(lián)結(jié)詞稱為邏輯聯(lián)結(jié)詞（logicalconnectives）。通常把不含有邏輯聯(lián)結(jié)詞的命題稱為原子命題或原子（atoms），而把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱為復(fù)合命題（compositiv

2、epropositions）。1.1.2聯(lián)結(jié)詞否定詞(negation)“并非”（not），用符號┐表示。設(shè)p表示一命題，那么┐p表示命題p的否定。p真時┐p假，而p假時┐p真。┐p讀作“并非p”或“非p”。合取詞(conjunction)“并且”（and），用符號∧表示。設(shè)p，q表示兩命題，那么p∧q表示合取p和q所得的命題，即p和q同時為真時p∧q真，否則p∧q為假。p∧q讀作“p并且q”或“p且q”。析取詞(disjunction)“或”（or）用符號∨表示。設(shè)p，q表示兩命題，那么p∨q表示p

3、和q的析取，即當p和q有一為真時，p∨q為真，只有當p和q均假時p∨q為假。p∨q讀作“p或者q”、“p或q”。蘊涵詞(implication)“如果……，那么……”（if…then…），用符號→表示。設(shè)p，q表示兩命題，那么p→q表示命題“如果p，那么q”。當p真而q假時，命題p→q為假，否則均認為p→q為真。p→q中的p稱為蘊涵前件，q稱為蘊涵后件。p→q的讀法較多，可讀作“如果p則q”，“p蘊涵q”，“p是q的充分條件”，“q是p的必要條件”，“q當p”，“p僅當q”等等。數(shù)學(xué)中還常把q→p，┐

4、p→┐q，┐q→┐p分別叫做p→q的逆命題，否命題，逆否命題。雙向蘊涵詞(two-wayimplication)“當且僅當”（ifandonlyif），用符號?表示之。設(shè)p，q為兩命題，那么p?q表示命題“p當且僅當q”，“p與q等價”，即當p與q同真值時p?q為真，否則為假。p?q讀作“p雙向蘊涵q”，“p當且僅當q”，“p等價于q”。由于“當且僅當”“等價”常在其它地方使用，因而用第一種讀法更好些。1.1.3命題公式及其真值表我們把表示具體命題及表示常命題的p，q，r，s與f，t統(tǒng)稱為命題常元（p

5、ropositionconstant）。深入的討論還需要引入命題變元（propositionvariable）的概念，它們是以“真、假”或“1，0”為取值范圍的變元，為簡單計，命題變元仍用p，q，r，s等表示。定義1.1以下三條款規(guī)定了命題公式（propositionformula）的意義：（1）命題常元和命題變元是命題公式，也稱為原子公式或原子。（2）如果A，B是命題公式，那么（┐A），（A∧B），（A∨B），（A→B），（A?B）也是命題公式。（3）只有有限步引用條款（1），（2）所組成的符號串是

6、命題公式。如果公式A含有命題變元p1，p2，…，pn，記為A(p1,…,pn)，并把聯(lián)結(jié)詞看作真值運算符，那么公式A可以看作是p1,…,pn的真值函數(shù)。對任意給定的p1,…,pn的一種取值狀況，稱為指派（assignments），用希臘字母a，b等表示，A均有一個確定的真值。當A對取值狀況a為真時，稱指派a弄真A，或a是A的成真賦值，記為a(A)=1；反之稱指派a弄假A，或a是A的成假賦值，記為a(A)=0。對一切可能的指派,公式A的取值可能可用一張表來描述,這個表稱為真值表（truthtable）。

7、當A(p1,…,pn)中有k個聯(lián)結(jié)詞時，公式A的真值表應(yīng)為2n行、k+n列（不計表頭）。1.1.4語句的形式化用我們已有的符號語言，可以將許多自然語言語句形式化。語句形式化要注意以下幾個方面。要善于確定原子命題，不要把一個概念硬拆成幾個概念，例如“弟兄”是一個概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一個原子命題。要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略）。例如“風雨無阻，我去上學(xué)”一句，可理解為“不管是否刮風、是否下雨我都去上學(xué)”。否定詞的位置要放準確。需要的括號不能省略，而可以省略的括號

8、，在需要提高公式可讀性時亦可不省略。另外要注意的是,語句的形式化未必是唯一的。習題解答練習1.11、判斷下列語句是否是命題，若是命題則請將其形式化：（1）a+b（2）x>0（3）“請進！”（4）所有的人都是要死的，但有人不怕死。（5）我明天或后天去蘇州。（6）我明天或后天去蘇州的說法是謠傳。（7）我明天或后天去北京或天津。（8）如果買不到飛機票，我哪兒也不去。（9）只要他出門，他必買書，不管他余款多不多。（10）除非你陪伴我或代我雇輛車子，否則我不去。（