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

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

2、不同的是，這一部分除了有單項選擇題、填空題，判斷說明題、計算題、證明題等五種題型外，還要增加一種公式翻譯題，這種題型也是期末考試題型的一種，因此希望同學(xué)們要熟悉所有的題型，使我們在考試中能夠順利地解答題目，獲得好成績。下面按題型分別講解。一、單項選擇題1設(shè)P：我將去市里，Q：我有時間命題“我將去市里，僅當(dāng)我有時間時”符號化為( )A B C D 正確答案：B因為語句“僅當(dāng)我有時間時”是“我將去市里”的必要條件，所以答案B是正確的。問：如果把“我將去市里”改成“我將去打球”、“我將去旅游”等，會符號化嗎？2設(shè)命題公式G：,則使公式G取真值為1的P，Q，R賦值分別是 ( )A0, 0, 0 B0,

3、 0, 1 C0, 1, 0 D1, 0, 0 正確答案：D 由教材162頁的條件聯(lián)結(jié)詞“”運算的真值表可知，當(dāng)P取真值時，P取假值，則無論后件QR取真值還是假值，結(jié)果都是真的。因此答案D是正確的。3下列公式 ( )為重言式A(P(PQ) Q B(B(AB) (A(AB) C(P(QP)(P(PQ) DABAB正確答案：C 因為： 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í)主析取范式的定義：定義 對于給定的命題變元，如果有一個等價公式，它僅僅有小項的析取組

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

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因為P(QP) 1，所以應(yīng)該填寫：1。2設(shè)P：他生病了，Q：他出差了R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號化的結(jié)果為 應(yīng)該填寫：(PQ)R一般地，當(dāng)語句是由“如果，那么”，或“若，則”組成，它的符號化用條件聯(lián)結(jié)詞3含有三個命題變項P，Q，

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

7、除量詞的規(guī)則為：設(shè)Da1, a2, , an，則所以，應(yīng)該填寫：(A(1) A(2) (B(1) B(2)如果個體域D=a, b, c, 怎么做?6謂詞命題公式(x)(P(x)Q(x)R(x，y)中的約束變元為 應(yīng)該填寫：x 因為約束變元就是受相應(yīng)的量詞約束的變元，在公式(x)(P(x)Q(x)R(x，y)中， x是受全稱量詞約束的變元所以應(yīng)該填寫：x。問: 公式中的自由變元是什么?三、公式翻譯題 1請將語句“今天不是天晴”翻譯成命題公式解：設(shè)P：今天是天晴； 命題公式為： P 2請將語句“我去書店，僅當(dāng)天不下雨”翻譯成命題公式解：設(shè) P：我去書店，Q：天不下雨， 命題公式為：P Q 3請將語

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

9、 US (1) 解：錯推理過程應(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)如果把原題中的推理過程改為(1) (x)A(x) B(x) 前提引入(2) A(y)B(y) US (1)更好些。這個推理的第2步也是錯的，正確的應(yīng)該是：A(y)B(z)，因為約束變元與自由變元不能混淆。五計算題1（1）求命題公式的主析取范式、主合取范式；（2）求該命題公式的成假賦值解：（1） (主析取范式) (主合取范式)（2）因為命題公式的成真賦

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) （主析取范式）問: 公式的析取、合取、主析取、主合取范式?3設(shè)謂詞公式試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元 解:（1）$x量詞的轄域為， z量詞的轄域為, y量詞的轄域為 （2）自由變元為與中的y，以及中的z 約束變元為中的x與中的z，以及中的y 六、證明題 1試證明命題公式 (P(QR)PQ

11、與（PQ）等價 證：(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)下面對本課程的考核做一些說明。 考核對象：本課程的考核是中央廣播電視大學(xué)開放教育本科電氣信息類計算機科學(xué)與技術(shù)專業(yè)的學(xué)生考核依據(jù)

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