離散數(shù)學(xué)數(shù)理邏輯部分綜合練習(xí)輔導(dǎo)

1、離散數(shù)學(xué)數(shù)理邏輯部分綜合練習(xí)輔導(dǎo)本次活動(dòng)（2008.12.17）是本學(xué)期的第三次活動(dòng)，主要是針對(duì)第三單元數(shù)理邏輯的重點(diǎn)學(xué)習(xí)內(nèi)容進(jìn)行輔導(dǎo)，方式還是通過(guò)講解一些典型的綜合練習(xí)題目，幫助大家進(jìn)一步理解和掌握數(shù)理邏輯的基本概念和方法數(shù)理邏輯作為離散數(shù)學(xué)的一部分，主要介紹命題邏輯和謂詞邏輯命題邏輯部分的主要內(nèi)容：命題及其表示法、聯(lián)結(jié)詞、命題公式與翻譯、真值表與等價(jià)公式、重言式與蘊(yùn)含式、范式、推理理論等；謂詞邏輯部分的主要內(nèi)容：謂詞及其表示法、命題函數(shù)與量詞、謂詞公式與翻譯、變?cè)s束、謂詞演算的等價(jià)式與蘊(yùn)含式、前束范式、謂詞演算的推理理論等。本次綜合練習(xí)主要是復(fù)習(xí)這一部分的主要概念與計(jì)算方法，與前兩個(gè)單元

2、不同的是，這一部分除了有單項(xiàng)選擇題、填空題，判斷說(shuō)明題、計(jì)算題、證明題等五種題型外，還要增加一種公式翻譯題，這種題型也是期末考試題型的一種，因此希望同學(xué)們要熟悉所有的題型，使我們?cè)诳荚囍心軌蝽樌亟獯痤}目，獲得好成績(jī)。下面按題型分別講解。一、單項(xiàng)選擇題1設(shè)P：我將去市里，Q：我有時(shí)間命題“我將去市里，僅當(dāng)我有時(shí)間時(shí)”符號(hào)化為( )A B C D 正確答案：B因?yàn)檎Z(yǔ)句“僅當(dāng)我有時(shí)間時(shí)”是“我將去市里”的必要條件，所以答案B是正確的。問(wèn)：如果把“我將去市里”改成“我將去打球”、“我將去旅游”等，會(huì)符號(hào)化嗎？2設(shè)命題公式G：,則使公式G取真值為1的P，Q，R賦值分別是 ( )A0, 0, 0 B0,

3、 0, 1 C0, 1, 0 D1, 0, 0 正確答案：D 由教材162頁(yè)的條件聯(lián)結(jié)詞“”運(yùn)算的真值表可知，當(dāng)P取真值時(shí)，P取假值，則無(wú)論后件QR取真值還是假值，結(jié)果都是真的。因此答案D是正確的。3下列公式 ( )為重言式A(P(PQ) Q B(B(AB) (A(AB) C(P(QP)(P(PQ) DABAB正確答案：C 因?yàn)椋?P(PQ) P (PQ) P (PQ) P (P Q) P (Q P) P (Q P) P (Q P) 所以，C是重言式 4命題公式的主析取范式是( )A B C D正確答案：A復(fù)習(xí)主析取范式的定義：定義 對(duì)于給定的命題變?cè)绻幸粋€(gè)等價(jià)公式，它僅僅有小項(xiàng)的析取組

4、成，則該等價(jià)式稱為原式的主析取范式而小項(xiàng)的定義是：定義 n個(gè)命題變?cè)暮先∈剑Q為布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次由此可知，答案C和D是錯(cuò)的。又因?yàn)?(P Q ) (P Q) P Q所以，答案A是正確的。5設(shè)C(x): x是國(guó)家級(jí)運(yùn)動(dòng)員，G(x): x是健壯的，則命題“沒(méi)有一個(gè)國(guó)家級(jí)運(yùn)動(dòng)員不是健壯的”可符號(hào)化為 ( ) A BC D正確答案：D 由題設(shè)知道，C(x) G(x)表示國(guó)家級(jí)運(yùn)動(dòng)員不是健壯的，而“沒(méi)有一個(gè)”就是“不存在一個(gè)”，因此用存在量詞的否定，即$x，得到公式D。 如果把命題改為:“不是所有人都是運(yùn)動(dòng)員”,你會(huì)符號(hào)化嗎? 6表達(dá)式中的

5、轄域是( ) AP(x, y) BP(x, y)Q(z) CR(x, y) DP(x, y)R(x, y)正確答案：B 所謂轄域是指“緊接于量詞之后最小的子公式稱為量詞的轄域”那么看題中緊接于量詞x之后最小的子公式是什么呢？顯然是P(x, y)Q(z)，因此，答案B是正確的。 二、填空題1命題公式的真值是 應(yīng)該填寫：1因?yàn)镻(QP) 1，所以應(yīng)該填寫：1。2設(shè)P：他生病了，Q：他出差了R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號(hào)化的結(jié)果為 應(yīng)該填寫：(PQ)R一般地，當(dāng)語(yǔ)句是由“如果，那么”，或“若，則”組成，它的符號(hào)化用條件聯(lián)結(jié)詞3含有三個(gè)命題變項(xiàng)P，Q，

6、R的命題公式PQ的主析取范式是 應(yīng)該填寫：(PQR) (PQR) 關(guān)于主析取范式的定義，在單選題的第4題已經(jīng)復(fù)習(xí)了，由小項(xiàng)的定義知道，命題公式PQ中缺少命題變項(xiàng)R與它的否定，因此，應(yīng)該補(bǔ)上，即PQPQ (RR) (PQ R) (PQR)得到命題公式PQ的主析取范式。4設(shè)F(x)：x是鳥(niǎo)，G(x)：x會(huì)飛翔則命題“鳥(niǎo)會(huì)飛”符號(hào)化為 應(yīng)該填寫：(x)(F(x) G(x)注意，一般情況下，謂詞邏輯中命題符號(hào)化時(shí)，使用全稱量詞，特性謂詞后用；使用存在量詞$，特性謂詞后用5設(shè)個(gè)體域D=1, 2,那么謂詞公式消去量詞后的等值式為 應(yīng)該填寫：(A(1) A(2) (B(1) B(2) 因?yàn)樵谟邢迋€(gè)體域下，消

7、除量詞的規(guī)則為：設(shè)Da1, a2, , an，則所以，應(yīng)該填寫：(A(1) A(2) (B(1) B(2)如果個(gè)體域D=a, b, c, 怎么做?6謂詞命題公式(x)(P(x)Q(x)R(x，y)中的約束變?cè)獮?應(yīng)該填寫：x 因?yàn)榧s束變?cè)褪鞘芟鄳?yīng)的量詞約束的變?cè)诠?x)(P(x)Q(x)R(x，y)中， x是受全稱量詞約束的變?cè)詰?yīng)該填寫：x。問(wèn): 公式中的自由變?cè)鞘裁?三、公式翻譯題 1請(qǐng)將語(yǔ)句“今天不是天晴”翻譯成命題公式解：設(shè)P：今天是天晴； 命題公式為： P 2請(qǐng)將語(yǔ)句“我去書店，僅當(dāng)天不下雨”翻譯成命題公式解：設(shè) P：我去書店，Q：天不下雨， 命題公式為：P Q 3請(qǐng)將語(yǔ)

8、句 “有人不去工作”翻譯成謂詞公式 解：設(shè)P(x)：x是人，Q(x)：x去工作， 謂詞公式為： ($x)(P(x) Q(x)如果語(yǔ)句是“所有人都不去上課”,那么謂詞公式應(yīng)該怎樣呢? 4請(qǐng)將語(yǔ)句“所有人都努力工作”翻譯成謂詞公式 解：設(shè)P(x)：x是人，Q(x)：x努力工作 謂詞公式為： (x)(P(x) Q(x)四、判斷說(shuō)明題（判斷下列各題，并說(shuō)明理由） 1命題公式為永假式 解：正確 因?yàn)?，由真值?PQQP( QP)( QP) P00100010101010011100可知，該命題公式為永假式 2下面的推理是否正確，請(qǐng)給予說(shuō)明(1) xA(x)$ xB(x) 前提引入(2) A(y)B(y)

9、 US (1) 解：錯(cuò)推理過(guò)程應(yīng)為：(1) xA(x)$xB(x) 前提引入(2) xA(x)$uB(u) T(1)（換名規(guī)則）(3) x$u(A(x)B(u) T(2)(4) x(A(x)B(y) ES(3)(5) A(y)B(y) US (4)如果把原題中的推理過(guò)程改為(1) (x)A(x) B(x) 前提引入(2) A(y)B(y) US (1)更好些。這個(gè)推理的第2步也是錯(cuò)的，正確的應(yīng)該是：A(y)B(z)，因?yàn)榧s束變?cè)c自由變?cè)荒芑煜Ｎ逵?jì)算題1（1）求命題公式的主析取范式、主合取范式；（2）求該命題公式的成假賦值解：（1） (主析取范式) (主合取范式)（2）因?yàn)槊}公式的成真賦

10、值是(1, 0)，所以它的成假賦值是(0, 0)，(0, 1)，(1, 1)2求公式的析取、合取、主析取、主合取范式 解： （析取、合取、主合取范式）(P(QQ)(RR)(PP)Q(RR)(PP)(QQ)R) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) （主析取范式）問(wèn): 公式的析取、合取、主析取、主合取范式?3設(shè)謂詞公式試（1）寫出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)?解:（1）$x量詞的轄域?yàn)椋?z量詞的轄域?yàn)? y量詞的轄域?yàn)?（2）自由變?cè)獮榕c中的y，以及中的z 約束變?cè)獮橹械膞與中的z，以及中的y 六、證明題 1試證明命題公式 (P(QR)PQ

11、與（PQ）等價(jià) 證：(P(QR)PQ(P(QR)PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ （吸收律） (PQ) （摩根律） 2試證明 xA(x)xB(x)x(A(x)B(x)分析：前提：xA(x)xB(x)結(jié)論：x(A(x)B(x)證：(1) xA(x)P(2) A(a) US(1) (3) xB(x) P(4) B(a) US(3)(5) A(a) B(a) T(2),(4) I (6) x(A(x)B(x) UG(5)下面對(duì)本課程的考核做一些說(shuō)明。 考核對(duì)象：本課程的考核是中央廣播電視大學(xué)開(kāi)放教育本科電氣信息類計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生考核依據(jù)

12、：以本課程的教學(xué)大綱（2007年6月審定）和指定的參考教材為依據(jù)制定的本課程指定的參考教材是李偉生主編的、中央廣播電視大學(xué)出版社出版的離散數(shù)學(xué) 考核方式：本課程的考核實(shí)行形成性考核和終結(jié)性考核相結(jié)合的方式其中終結(jié)性考核采用半開(kāi)卷、筆試方式，試卷滿分100分 半開(kāi)卷考試允許考生攜帶指定的一張專用A4紙（統(tǒng)一印制），考生可以將自己對(duì)全課程學(xué)習(xí)內(nèi)容的總結(jié)歸納寫在這張A4紙上帶入考場(chǎng)，作為答卷時(shí)參考 考試時(shí)間：90分鐘試題類型及結(jié)構(gòu)：?jiǎn)雾?xiàng)選擇題的分?jǐn)?shù)占15，填空題的分?jǐn)?shù)占15，公式翻譯題的分?jǐn)?shù)占12，判斷說(shuō)明題的分?jǐn)?shù)占14，計(jì)算題的分?jǐn)?shù)占36；證明題的分?jǐn)?shù)占8單項(xiàng)選擇題和填空題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡(jiǎn)單計(jì)算單項(xiàng)選擇題給出四個(gè)備選答案，其一