北語直屬15春《離散數學》作業1

北語直屬15春《離散數學》作業1離散數學作為計算機科學與技術領域的基礎學科，其嚴謹的邏輯體系和抽象思維方式是構建后續專業知識的重要基石。本次作業1作為課程開篇的檢驗，主要聚焦于命題邏輯的核心內容，包括命題與聯結詞、真值表、等值演算、范式以及命題邏輯的推理理論。本文旨在為同學們提供一份針對性的復習指南與解題思路梳理，助力大家更好地理解并掌握這些基礎概念與方法。一、命題與聯結詞：邏輯的基石命題邏輯研究的基本單位是命題。理解命題的定義及其分類是入門的關鍵。1.命題的界定：命題是指具有唯一真值的陳述句。這里有兩個核心要素：“陳述句”和“唯一真值”。感嘆句、疑問句、祈使句通常不構成命題。真值可以是真（用T或1表示）或假（用F或0表示），但一個命題的真值必須是確定的，不能模棱兩可。例如，“雪是白色的”是一個真命題，而“這個語句是假的”則因產生自指矛盾，不成為命題。2.原子命題與復合命題：不能再分解為更簡單命題的命題稱為原子命題或簡單命題。由原子命題通過聯結詞組合而成的命題則為復合命題。識別原子命題是進行邏輯分析的第一步。3.邏輯聯結詞：這是將原子命題組合成復合命題的基本工具，務必準確理解每種聯結詞的邏輯含義、真值表定義以及自然語言中的表達方式。*否定（?）：對原命題的真值取反。*合取（∧）：只有當所有支命題都為真時，復合命題才為真。*析取（∨）：至少有一個支命題為真時，復合命題為真（注意區分“相容或”與“排斥或”，后者在自然語言中常見，需用∨和?的組合來精確表達）。*蘊含（→）：這是最容易產生混淆的聯結詞。P→Q表示“如果P，則Q”。其真值表中，只有當P為真且Q為假時，P→Q才為假。要特別注意理解“善意的推定”，即當前件P為假時，無論后件Q真假，整個蘊含式都為真。*等價（?）：當兩個支命題的真值完全相同時，等價式為真。解題要點：在面對具體問題時，首先要準確地將自然語言描述的命題符號化，這需要對上述聯結詞的深刻理解。例如，“只有A，才B”應符號化為B→A，而非A→B。二、命題公式與真值表：形式化與語義由命題變元、邏輯聯結詞和括號按照一定規則組成的符號串稱為命題公式。真值表則是研究命題公式語義的重要工具，它清晰地展示了公式在所有可能的命題變元真值組合下的取值情況。1.命題公式的定義與層次：理解公式的遞歸定義方式，能夠判斷一個符號串是否為合法的命題公式，并分析其層次結構。2.真值表的構造：構造真值表時，需先確定命題變元的個數，列出所有可能的真值組合（若有n個變元，則有2^n種組合），然后按照公式的層次結構由內向外逐步計算各子公式的真值，最終得到整個公式的真值。3.公式的分類：根據真值表，可將命題公式分為重言式（永真式）、矛盾式（永假式）和可滿足式。重言式在任何解釋下都為真，矛盾式則相反，可滿足式至少存在一種解釋使其為真。解題要點：真值表法是一種直觀且萬能的方法，可用于判斷公式類型、驗證等值式、判斷公式間的蘊含關系等。在作業中，對于一些不太復雜的公式，構造真值表是解決問題的有效途徑。例如，驗證兩個公式是否等值，只需構造它們的真值表，看其最后一列是否完全相同。三、等值演算與范式：公式的變形與標準化等值演算是命題邏輯中的核心方法，它基于已知的等值式（如雙重否定律、冪等律、交換律、結合律、分配律、德摩根律、吸收律、蘊含等值式、等價等值式等）對命題公式進行等價變換。1.基本等值式：務必牢記并熟練運用這些基本的“邏輯代數”法則。例如，德摩根律?(A∨B)??A∧?B和?(A∧B)??A∨?B在化簡公式時非常有用。蘊含等值式A→B??A∨B則揭示了蘊含聯結詞與否定、析取聯結詞之間的聯系。2.等值演算的應用：通過等值演算，可以實現公式的化簡、判斷公式的類型（如證明某公式為重言式，可嘗試將其等值演算為“1”）、證明兩個公式等值等。演算過程中，要注意每一步變換的依據，確保推理的正確性。3.范式：范式是命題公式的標準形式，具有唯一性（主范式），為我們提供了一種統一的方法來比較和研究公式。*析取范式與合取范式：析取范式是由有限個簡單合取式組成的析取式；合取范式是由有限個簡單析取式組成的合取式。任何命題公式都存在與之等值的析取范式和合取范式，但它們不唯一。*主析取范式與主合取范式：這是更為精細的范式。主析取范式由極小項的析取組成，每個極小項對應著使得公式為真的一組命題變元真值組合（成真賦值）；主合取范式由極大項的合取組成，每個極大項對應著使得公式為假的一組命題變元真值組合（成假賦值）。它們具有唯一性，因此是判斷公式等值、求解公式類型、解決實際邏輯問題的有力工具。解題要點：等值演算是核心技能，需要大量練習才能熟練掌握。在求范式時，通常的步驟是：消去→和?，內移否定號（德摩根律），然后使用分配律將公式化為所需的范式形式。求主范式時，可以通過真值表法（找出所有成真/成假賦值對應的極小項/極大項）或等值演算法（添加缺少的變元，再用分配律展開）。四、命題邏輯的推理理論：由前提到結論的過渡推理是從給定的前提集合出發，應用推理規則得出結論的過程。這部分內容直接關系到邏輯思維能力的培養。1.推理的形式結構：將推理符號化為“H?∧H?∧...∧H?→C”的形式，其中H?...H?是前提，C是結論。若該蘊含式為重言式，則稱推理有效或正確。2.推理規則：常用的推理規則包括：前提引入規則、結論引入規則、置換規則，以及假言推理（肯定前件）、附加、化簡、拒取式（否定后件）、假言三段論、析取三段論、構造性二難等。這些規則是進行有效推理的依據，必須準確理解其含義和使用條件。3.判斷推理有效性的方法：*真值表法：判斷蘊含式是否為重言式。*等值演算法：將蘊含式化簡，看是否能得到“1”。*主范式法：檢查主析取范式是否包含所有極小項（或主合取范式是否為空）。*自然推理系統P中的形式證明：這是作業和考試中重點考察的內容。從前提出發，嚴格按照推理規則，逐步推導出結論。常用的技巧包括直接證明法、附加前提證明法（適用于結論為蘊含式）和歸謬法（反證法，假設結論的否定為真，推出矛盾）。解題要點：形式證明是難點。在進行證明時，要明確每一步推理所依據的前提和規則，保持清晰的思路。對于復雜的推理，可以嘗試從結論入手進行反向思考，或者利用歸謬法將問題轉化。五、學習建議與常見誤區1.深刻理解基本概念：離散數學的特點是概念性強，務必不要死記硬背，要理解概念的內涵和外延。2.多做練習：只有通過大量不同類型的習題練習，才能真正掌握各種解題方法和技巧，熟悉各種聯結詞和推理規則的應用場景。3.注重邏輯思維的培養：學習離散數學的過程本身就是邏輯思維訓練的過程，要養成嚴謹、清晰的思維習慣。4.常見誤區提醒：*對“蘊含”聯結詞的理解不準確，特別是P為假時P→Q為真的情況。*自然語言符號化時，對聯結詞的選擇不當，如混淆“如果...則...”與“只有...才...”。*在等值演算中，隨意使用“自創”的等值式，而不是基于基本等值式進行推導