吉大2019-2020學(xué)年第一學(xué)期期末考試《離散數(shù)學(xué)》大作業(yè)答案

1、吉林大學(xué)網(wǎng)絡(luò)教育學(xué)院2019-2020學(xué)年第一學(xué)期期末考試離散數(shù)學(xué)大作業(yè)學(xué)生姓名 專業(yè) 層次年級(jí) 學(xué)號(hào) 學(xué)習(xí)中心 成績 年 月 日作業(yè)完成要求：大作業(yè)要求學(xué)生手寫，提供手寫文檔的清晰掃描圖片，并將圖片添加到word文檔內(nèi)，最終wod文檔上傳平臺(tái)，不允許學(xué)生提交其他格式文件（如JPG，RAR等非word文檔格式），如有雷同、抄襲成績按不及格處理。1、 簡答題（每小題7分，共56分）1、 什么是命題公式的演繹？答：首先定義了消解復(fù)雜性的兩種范式:最簡范式和文字范式,在此基礎(chǔ)上采用演繹方法證明了L中的可判定性定理,并設(shè)計(jì)了命題公式的演繹判定算法P(F).P(F)的時(shí)間復(fù)雜度為O(n3),遠(yuǎn)遠(yuǎn)小于基于

2、真值表法的O(2n)和基于策略方案HAL的O(n5).2、 什么是子句？請(qǐng)給出一例。答：子句是一組包含一個(gè)主詞和一個(gè)動(dòng)詞的關(guān)連字。子句與片語有明顯的不同，后者為一組不含主詞與動(dòng)詞關(guān)系的關(guān)連字，如 "in the morning" 或 "running down the street" 或 "having grown used to this harassment."3、 什么是短語？請(qǐng)給出一例。答：短語是由句法、語義和語用三個(gè)層面上能夠搭配的語言單位組合起來的沒有句調(diào)的語言單位，又叫詞組。它是大于詞而又不成句的語法單位。簡單的短語可以

3、充當(dāng)復(fù)雜短語的句法成分，短語加上句調(diào)可以成為句子。由語法上能夠搭配的詞組合起來的沒有句調(diào)的語言單位例如：糧食/豐收 （名/動(dòng)）（什么/怎么樣）4、 什么是命題邏輯中的文字？答：檢測(cè)和消除命題邏輯公式中的冗余文字,是人工智能領(lǐng)域廣泛研究的基本問題。針對(duì)命題邏輯的子句集中子句的劃分,結(jié)合冗余子句和冗余文字的概念,將命題邏輯的子句集中的文字分為必需文字、有用文字和無用文字3類,5、 什么是析取范式？請(qǐng)給出一例。答：在離散數(shù)學(xué)中，僅由有限個(gè)文字構(gòu)成的合取式稱為簡單合取式，而由有限個(gè)簡單合取式構(gòu)成的析取式稱為析取范式。范式存在定理說明了它的存在性：任一命題公式都存在著與之等值的析取范式與合取范式。但它并

4、不是惟一的。主析取范式是惟一的。例如， 等為一個(gè)文字構(gòu)成的簡單析取式。一個(gè)文字既是簡單析取式，又是簡單合取式。 6、 什么是關(guān)于P1，P2，¼，Pn的極小項(xiàng)？請(qǐng)給出一例。答：關(guān)于P1,P2,Pn的極小項(xiàng)（0 k1 < k2 < <ks 2n-1 ）則稱mk1 mk2 mks為關(guān)于P1,P2,Pn的主析取范式，并簡記為 k1， k2 ， ，ks * 定理7、 什么是謂詞邏輯中的項(xiàng)？8、 什么是Skolem范式？ 答; Skolem標(biāo)準(zhǔn)型是Skolem于1920年提出的一個(gè)使一階公式標(biāo)準(zhǔn)化的方法，其定義如下：Skolem標(biāo)準(zhǔn)型是如下任意一種形式的一階命題：(1

5、)x1x2.xmy1y2.ynUx1x2.xmy1y2.yn(型 )；(2)x1x2.xmUx1x2.xm(型)；(3)x1x2.xmUx1x2.xm(型)。其中，U是不包含量詞且連接符僅僅為，的公式。二、綜合題（共44分）1、求證若G的元數(shù)是一個(gè)質(zhì)數(shù)，則G必是循環(huán)群。 (7分）2、令S=所有正偶數(shù)集合。證明：(I+，D)與(S，D)同構(gòu)。 （7分）證明:對(duì)任意n,I，規(guī)定I到S的映射:g:n,2n +顯然此映射是一對(duì)一的。與這兩個(gè)格等價(jià)的代數(shù)格的*，?運(yùn)算都是求最大公因和最小公倍。 對(duì)任n,n,I,n*n為其最大公因，記為d.而2n,2n,S,2n*2n為2n和2n的最大公因。12+1212

6、1212為2d 。故g(n*n)=g(d)=2d=2n*2n=g(n)*g(n). 121212同理可證g(n n)=g(n) g(n) 1212即g是同態(tài)映射，故(I，D)和(S，D)同構(gòu)。 3、證明：4個(gè)元素的格(L，*，)必同構(gòu)于格(I4，£)或者格(S6，D)。 （10分）證明:設(shè)4個(gè)元素的格L=a,a,a,a，L有限，故必有最大，最小元素，不妨設(shè)為1234a,a,則a,a,a,a其中，a,a有兩種可能: 。41123423(1)a,a(a,a有關(guān)系,，不妨設(shè)為如此)則成為鏈，因此與(I，,)同構(gòu)。 23234(2)a,a沒有,關(guān)系，則此格與(S，D)同構(gòu). 4、試證明群G的所有內(nèi)自同構(gòu)映射在映射的乘法下作成群。 （10分）證明:同一變換可表示成，故此集合非空。對(duì)任意屬于該集合的，因?yàn)閷?duì)任1xy,-1-11 -1意的g,G，有(g)= (xgx)=y(xgx)y=(yx) g(yx)= (g)，所以此集合在乘yxyyx法運(yùn)算下是封閉的。顯然該集合在乘法運(yùn)算下滿足結(jié)合律。該集合內(nèi)有單位元素，容易1-1驗(yàn)證 =在該集合中。5、求證任意無零因子的有限環(huán)必是一個(gè)體。