吉林大學(xué)20202021學(xué)年第二學(xué)期期末考試《離散數(shù)學(xué)》大作業(yè)答案

吉林大學(xué)網(wǎng)絡(luò)教育學(xué)院學(xué)生姓名層次年級(jí)學(xué)習(xí)中心年月日1離散數(shù)學(xué)一綜合題(共1題，總分值10分)設(shè)S1n提示：考慮GG的主合取范式。10分）1n解：任設(shè)一公式G’為從S出發(fā)演繹出來(lái)的公式。則可知G’為G=G…G的一個(gè)邏輯結(jié)果。而G有唯一一個(gè)與其等價(jià)的主合取范式，設(shè)為1nG’’?？稍O(shè)G’’共有m個(gè)極大項(xiàng)，則可以知道令G’’取1的解釋使這m個(gè)極大項(xiàng)也取1。則從S出發(fā)的演繹出來(lái)的的所有命題公式正是從這m個(gè)極大項(xiàng)中任取n(0≤n≤m)個(gè)合取組成，共有2個(gè)，其中包括恒真公式這里用1表示。m設(shè)H為由若干極大項(xiàng)構(gòu)成的合取公式?，F(xiàn)在證明：S=>H，即G=>H。從定義出發(fā)，設(shè)有一解釋I使G=G…G取1值，必使G的主1n合取范式也取1值。即使每一個(gè)極大項(xiàng)都取1值。從而使由若干極大項(xiàng)合取組成的公式H也取1值，則有S=>H。任意設(shè)公式H是S的一個(gè)邏輯結(jié)果，HH的極大項(xiàng)都在G的主合取范式G”中。反證法：若不然，假設(shè)H中有一個(gè)極大項(xiàng)m不在G的主合取范式中。則取使m為0kk的解釋，可有解釋I使H取0值。而I使所有不等于m的極大項(xiàng)都為1，則可有G的k主合取范式G’’在I下取1值，即G在I下取1值，這與G=>H矛盾。二證明題(共1題，總分值10分)設(shè)G1nn1滿足下列條件的有向圖被稱為有向樹(shù)：（1）有且僅有一個(gè)結(jié)點(diǎn)的入度為0；（2）除樹(shù)根外的結(jié)點(diǎn)入度為1；（3）從樹(shù)根到任一結(jié)點(diǎn)有一條有向通路。題目中G不滿足上述條件故不是有向樹(shù)三問(wèn)答題(共10題，總分值80分)是把簡(jiǎn)單命題進(jìn)而分析為其主項(xiàng)、謂項(xiàng)和量項(xiàng)并借以研究命題的形式結(jié)構(gòu)及其推理的規(guī)律與規(guī)則的邏輯演算公式。設(shè)AR={(1，1)，(1，2)，(2，2)，(3，3)，(3，2)}（1,3),(1,2)}謂詞,用來(lái)描述或判定客體性質(zhì)、特征或者客體之間關(guān)系的詞項(xiàng)。分配格是一種組合構(gòu)形，它是滿足下述條件的格：對(duì)于格的任意元素，y和z，均有∧∨z)=(x∧y)∨∧z)。由于格中結(jié)運(yùn)算和交運(yùn)算的對(duì)稱性，上述條件等價(jià)于x∨∧z)=(x∨∧∨z)，當(dāng)L為分配格時(shí)，交運(yùn)算對(duì)于結(jié)運(yùn)算滿足分配律，而且反之亦真。布爾格、除數(shù)格、理想格、鏈等均為分配格。一個(gè)群必須滿足一些被稱為“群公理”的條件，也就是封閉性、結(jié)合律、單位元和對(duì)于集合中所有元素存在逆元素。例如整數(shù)配備上加法運(yùn)算就形成一個(gè)群。設(shè)G是G到H是G在一個(gè)無(wú)向圖G中，若從頂點(diǎn)到頂點(diǎn)有路徑相連（當(dāng)然從到也一定有路徑），則稱和是連通的。如果G是有向圖，那么連接和的路徑中所有的邊都必須同向。如果圖中任意兩點(diǎn)都是連通的，那么圖被稱作連通圖。設(shè)(R,+,S是R(S,+,(S,+,為(R,+,)的子環(huán)。設(shè)R=Z，則S=（2