2019年大連海事大學計算機科學與技術考研專業(yè)課離散數學（同等學力加試）考試大綱

1、大連海事大學碩士研究生入學考試大綱大連海事大學碩士研究生入學考試大綱考試科目：離散數學試卷滿分及考試時間:試卷滿分為100分，考試時間為180分鐘。一、命題邏輯一、命題邏輯考試內容考試內容命題，連接詞的真值，重言式矛盾式可滿足式，代入規(guī)則與替換規(guī)則，等價與蘊含，對偶式與對偶原理，連接詞的最小功能完備集，范式與主范式，命題邏輯的推理規(guī)則法考試要求考試要求1理解命題的概念，理解連接詞的真值（特別是單條件連接詞的真值）。2簡要了解重言式矛盾式

2、可滿足式，以及代入規(guī)則與替換規(guī)則。3掌握等價式和蘊含式的的推導，掌握常見的基本等價式和基本蘊含式。4簡要了解對偶式的概念與對偶原理的公式。5了解連接詞的最小功能完備集。6掌握范式的概念，特別是主范式的概念，會求命題公式的主析取范式和主合取范式，并能表示成?mi和ΠMj的形式。7重點掌握推理規(guī)則法的證明題。二、謂詞邏輯二、謂詞邏輯謂詞，量詞與全總個體域與特性謂詞，謂詞公式，自由變元與約束變元，謂詞公式的等價式與蘊含式，謂詞邏輯的推理規(guī)則法

3、考試要求考試要求1理解謂詞的概念，會使用謂詞和量詞對一個問題符號化，特別要理解符號化時默認個體域是全總個體域時的處理。2簡要了解什么是自由變元與約束變元。3掌握謂詞公式的等價推導和蘊含推導（重點是一元量詞公式的量詞轉換律，量詞轄域擴大收縮律和量詞分配律）4重點掌握謂詞邏輯的推理規(guī)則法的證明題三、集合三、集合集合的基本概念和基本定理，集合的運算，容斥原理，笛卡爾積考試要求考試要求1理解空集、全集、冪集的概念的理解，會熟練求冪集。掌握集合相

4、等的判定定理、空集的屬性定理以及冪集計數定理。2掌握集合的基本運算和常見的集合等式，會做集合等式的證明推導。2代數系統(tǒng)的概念和子代數系統(tǒng)的概念，要會證一個代數系統(tǒng)A是代數系統(tǒng)B的子代數。3重點理解同態(tài)、同構，理解同態(tài)與同構的性質，會做同態(tài)、同構的證明題。4簡要了解代換性質與同余關系的概念。七、群七、群半群、子半群、循環(huán)半群，群，阿貝爾群，群同態(tài)，循環(huán)群，子群?？荚囈罂荚囈?了解半群、子半群、循環(huán)半群的概念。2理解群的概念及群的基本性

5、質，會證明給定的代數系統(tǒng)是否是群，會證明阿貝爾群以及群同態(tài)（同構）問題的證明。3理解循環(huán)群概念以及循環(huán)群的分類4理解子群的概念，掌握子群的證明方法。八、圖八、圖圖的相關基本概念，子圖，路徑與連通性，圖的矩陣表示考試要求考試要求1理解簡單圖的概念、特別度相關的概念、掌握握手定理與奇結點個數必是偶數的定理，零圖、平凡圖、正則圖、完全圖的概念，以及完全圖的邊數定理。會判斷圖同構的問題。2理解常見的幾種子圖的概念，特別是生成子圖和導出子圖，會求

6、相對于完全圖的補圖。3理解基本路徑簡單路徑，可達性，掌握無向圖和有向圖的連通性及分圖（分支）的概念以及相關的定理。4圖的矩陣表示中主要理解鄰接矩陣A（無向圖有向圖）、AAT、ATA、Am表示的意義。九、特殊圖九、特殊圖歐拉圖與哈密頓圖，平面圖，樹與生成樹考試要求考試要求1理解歐拉圖的概念，掌握判斷無向圖是歐拉圖的歐拉定理。2了解哈密頓圖的概念。3會用簡單連通平面圖的歐拉不等式結合握手定理做計算或證明。會用庫拉托夫斯基定理判斷平面圖還是非