下载文档原格式
《离散数学》复习题一、填空题1、若P ，Q 为二命题，Q P ↔真值为1，当且仅当 。
2、对公式),()),(),((y x xR z x zQ y x yP ∀∨∃∧∀中自由变元进行代入的公式为 。
3、))(()(x xG x xF ∃⌝∧∀的前束范式为 。
4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则 被称为全称量词消去规则，记为US 。
5、与非门的逻辑网络为 。
6、}0|{>∧∈=+x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算的幺元是 ，零元是 。
7、代数系统<A,*>中，|A|>1，如果θ和e 分别为<A,*>的幺元和零元， 则θ和e 的关系为 。
8、设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是 。
9、图的完全关联矩阵为 。
10、一个图是平面图的充要条件是 。
二、选择题1、下列各符号串，不是合式公式的有（ ）。
A 、R Q P ⌝∧∧)(；B 、)()((S R Q P ∧→→；C 、R Q P ∧∨∨；D 、S R Q P ∨∧∨⌝))((。
2、下列语句是命题的有（ ）。
A 、2是素数；B 、x+5 > 6；C 、地球外的星球上也有人；D 、这朵花多好看呀！。
3、下列公式是重言式的有（ ）。
A 、)(Q P ↔⌝；B 、Q Q P →∧)(；C 、P P Q ∧→⌝)(；D 、P Q P ↔→)(4、下列问题成立的有（ ）。
若C B C A ∨⇔∨，则B A ⇔； B 、若C B C A ∧⇔∧，则B A ⇔； C 、若B A ⌝⇔⌝，则B A ⇔； D 、若B A ⇔，则B A ⌝⇔⌝。
5、命题逻辑演绎的CP 规则为（ ）。
A 、在推演过程中可随便使用前提；B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；D 、设)(A Φ是含公式A 的命题公式，A B ⇔，则可用B 替换)(A Φ中的A 。
*第三章消解原理3.1 斯柯伦标准形内容提要我们约定，本章只讨论不含自由变元的谓词公式(也称语句,sentences)，所说前束范式均指前束合取范式。
全称量词的消去是简单的。
因为约定只讨论语句，所以可将全称量词全部省去，把由此出现于公式中的“自由变元”均约定为全称量化的变元。
例如A(x)实指∀xA(x)。
存在量词的消去要复杂得多。
考虑∃xA(x)。
（1）当A(x)中除x外没有其它自由变元，那么，我们可以像在自然推理系统中所做那样，可引入A(e/x)，其中e为一新的个体常元，称e为斯柯伦（Skolem）常元，用A(e/x)代替∃xA(x),但这次我们不把A(e/x)看作假设,详见下文。
（2）当A中除x外还有其它自由变元y1,…,y n，那么∃xA(x, y1,…,y n) 来自于∀y1…∀y n∃xA(x, y1,…,y n)，其中“存在的x”本依赖于y1,…,y n的取值。
因此简单地用A(e/x, y1,…,y n)代替∃xA(x, y1,…,y n) 是不适当的，应当反映出x对y1,…,y n的依赖关系。
为此引入函数符号f，以A(f(y1,…,y n)/x, y1,…,y n) 代替∃xA(x, y1,…,y n)，它表示：对任意给定的y1,…,y n, 均可依对应关系f确定相应的x，使x, y1,…,y n满足A。
这里f是一个未知的确定的函数，因而应当用一个推理中尚未使用过的新函数符号，称为斯柯伦函数。
定理3.1（斯柯伦定理）对任意只含自由变元x, y1,…,y n的公式A(x, y1,…,y n)，∃xA(x, y1,…,y n)可满足，当且仅当A(f(y1,…,y n), y1,…,y n)可满足。
这里f为一新函数符号；当n = 0时，f为新常元。
定义3.1设公式A的前束范式为B。
C是利用斯柯伦常元和斯柯伦函数消去B中量词（称斯柯伦化）后所得的合取范式，那么称C为A的斯柯伦标准形（Skolem normal form）。
⼈⼯智能期末试题2.证明G 是否为1F ,2F ,……，n F 的逻辑结论。
1F ：()()()()()()x x x x R Q P ∧→? 1F ：()()()()x x x S P ∧?G ：()()()()x x x R S ∧?2.先把G 否定，并放⼊F 中，得到的｛F1,F2, ?G ｝为｛()()()()()()x x x x R Q P ∧→?，()()()()x x x S P ∧?，?（()()()()x x x R S ∧?）｝再把｛F1,F2, ?G ｝化为⼦句集，得到①)x ()x (Q P ∨? ②)y ()y (R P ∨? ③)a (P ④)a (S⑤)b ()b (R S ?∨?其中①②是由F1化为的两个⼦句，③④是由F2化为的两个⼦句，⑤是由G 化为的⼦句。
由⼦句集可以看出只有唯⼀的⼀个Q 因此可以得出G 不是F 的逻辑结构。
3.假设张被盗，公安局派出5⼈去调查。
案情分析时，侦查员A 说：“赵与钱中⾄少有⼀⼈作案”；侦查员B 说：“钱与孙中⾄少有⼀⼈作案”；侦查员C 说：“孙与李中⾄少有⼀⼈作案”；侦查员D 说：“赵与孙中⾄少有⼀⼈与此案⽆关”；侦查员E 说：“钱与李中⾄少有⼀⼈与此案⽆关”。
如果这5个侦查员的话都是可信的，试⽤归结演绎推理求出谁是盗窃犯。
3.解：(1) 先定义谓词和常量设C(x)表⽰x 作案，Z 表⽰赵，Q 表⽰钱，S 表⽰孙，L 表⽰李 (2) 将已知事实⽤谓词公式表⽰出来赵与钱中⾄少有⼀个⼈作案：C(Z)∨C(Q) 钱与孙中⾄少有⼀个⼈作案：C(Q)∨C(S) 孙与李中⾄少有⼀个⼈作案：C(S)∨C(L)赵与孙中⾄少有⼀个⼈与此案⽆关：? (C (Z)∧C(S))，即?C (Z) ∨?C(S) 钱与李中⾄少有⼀个⼈与此案⽆关：? (C (Q)∧C(L))，即?C (Q) ∨?C(L) (3) 将所要求的问题⽤谓词公式表⽰出来，并与其否定取析取。
谓词逻辑王剑§2.5谓词演算中的范式（前束范式和斯柯林范式）定义: 一个公式，若它的所有量词均非否定地出现在公式的最左边，而它们的辖域一直延伸到公式之末，且公式中不出现联接词“→”及“↔”，则此种形式的公式称前束范式。
EX1 :(1) ∀x∃y∀z (P(x) ∨Q(y)∧R(x, z))(2) ∃x∀y∀z ((P(x,y)∧(⌝Q(x))) ∨(R(y,z)∨(⌝Q(x))))都是前束范式。
定理任一谓词公式都可以化成为与之等值的前束范式。
任一公式化归为前束范式的过程如下:1. 消去联结词→, ↔。
2. 将联结词⌝向内深入, 使之只作用于原子公式。
3. 利用换名或代入规则使所有约束变元的符号均不同, 并且自由变元与约束变元的符号也不同。
4. 利用量词辖域的扩张和收缩律, 将所有量词以在公式中出现的顺序移到公式最前面, 扩大量词的辖域至整个公式。
EX2: 求公式A：(∀x P(x)∨∃y Q(y)) →∀x R(x)的前束范式。
解:A ⇔⌝(∀xP(x)∨∃yQ(y))∨∀xR(x)消去联结词→⇔(⌝∀xP(x)∧⌝∃yQ(y))∨∀xR(x)德.摩根律⇔(∃x⌝P(x)∧∀y⌝Q(y))∨∀zR(z)换名⇔∃x∀y ∀z ((⌝P(x)∧⌝Q(y))∨R(z))量词辖域扩张EX3：求公式(∀x P(x,y) →∃yQ(y))→∀xR(x,y)的前束范式解原式⇔(∀xP(x,t) →∃yQ(y)) →∀xR(x,t) 代入⇔(∀xP(x,t) →∃yQ(y)) →∀z R(z,t)换名⇔⌝(⌝∀xP(x,t)∨∃yQ(y))∨∀zR(z,t)消去联结词→⇔(∀xP(x,t)∧⌝∃yQ(y))∨∀zR(z,t)⌝向内深入⇔(∀xP(x,t)∧∀y⌝Q(y))∨∀zR(z,t)量词转换⇔∀x(P(x,t)∧∀y⌝Q(y))∨∀zR(z,t)量词辖域扩张⇔∀x∀y(P(x,t)∧⌝Q(y))∨∀zR(z,t)量词辖域扩张⇔∀x∀y∀z(P(x,t)∧⌝Q(y))∨R(z,t)量词辖域扩张⏹前束范式的优点在于它的量词全部集中在公式的前面, 此部分称为公式的首标。
第4章 习题与参考答案【题4-1】 写出图题4-1的输出逻辑函数式。
图题4-1解：（1）C A A AC B A Y +=++=1（2）D B C B A CD B A CD B A D BD CD A B A Y ++=++=+=++=）（2 【题4-2】 使用与门、或门实现如下的逻辑函数式。
（1）1Y ABC D =+ （2）2Y A CD B =+（） （3）3Y AB C =+ 解：&1≥AB C DY11≥&&A B C DY2&A B 1≥Y3C....【题4-3】 使用与门、或门和非门，或者与门、或门和非门的组合实现如下的逻辑函数式。
（1）1Y AB BC =+（2）2Y A C B =+（） （3）3Y ABC B EF G =++（）ABC.Y2A B C .E F G...【题4-4】试写出图题4-4所示电路的逻辑函数式，列出真值表，并分析该电路的逻辑功能。
图题4-4解：=1+ACBCABY+此电路是三人表决电路，只要有两个人输入1，输出就是1。
Y+CDABCDBA++⋅=⋅⋅=2BCDABCDCDDABCABBDCAABCDA该电路在4个输入中有3个为1时，输出Y2为1。
【题4-5】 逻辑电路与其输入端的波形如图题4-5所示，试画出逻辑电路输出端Y 的波形。
图题4-5解：B A Y +=BA.Y..【题4-6】 图题4-6所示的逻辑电路中，与非门为74LS00，或非门是74LS02，非门是74LS04。
试分析该电路的最大传输延迟时间。
图题4-6解：74LS00、74LS02和74LS04的最大t PHL 和t PLH 都是15ns ，因为A 信号经过4级门达到输出端X ，因此最大传输延迟时间为4×15ns=60ns 。
【题4-7】 图题4-7所示的是家用报警器装置，该装置具有6个开关，各开关动作如下：ALARM....图题4-7人工报警开关M ，该开关闭合时，报警信号ALARM=1，开始报警。
逻辑Boldface练习题与方法总结By Anchoret很多朋友提出由于手头上的复习资料大多为笔考材料，缺乏新题型的练习，特别是逻辑中的Boldface题，只有Official Guide中的205题这一题，由此我们就希望能为大家提供多些Boldface练习题。
感谢liu9903提供的这9道题目，真诚希望这些题目对即将考试的朋友能有所帮助。
另外还要感谢qxz9524为我们提供的一些关于作Boldface题的总结。
8/29/2003 欢迎转载，转载请于醒目位置注明来源于。
下载地址：/dispbbs.asp?boardid=22&id=127691. Modern navigation systems, which are found in most of today’s commercial aircraft, are made with low-power circuitry, which is more susceptible to interference than the vacuum-tube circuitry found in older planes. During landing, navigation systems receive radio signals from the airport to guide the plane to the runway. Recently, one plane with low-power circuitry veered off course during landing, its dials dimming, when a passenger turned on a laptop computer. Clearly, modern aircraft navigation systems are being put at risk by the electronic devices that passengers carry on board, such as cassette players and laptop computers.The two portions in boldface play which of the following roles?(A) The first is a principle that the argument relies on and the second is a conclusion that can be drawn from the first.(B) The first is a fact that argument relies on and the second is a conclusion that must be drawn from this argument.(C) The first acknowledges a consideration that supports that main position; the second is that conclusion.(D) The first is an evidence that supports the conclusion, the second is that conclusion.(E) The first is a principle that is necessary for this argument, the second is a conclusion that could be drawn from this argument.2. A double-blind study, in which neither the patient nor the primary researcher knows whether the patient is being given the drug being tested or a placebo, is the most effective procedure for testing the efficacy of a drug.But we will not be able to perform such a study on this new drug, since the drug will have various effects on the patients’ bodies, which will make us aware of whether the patients are getting the drug or a placebo.The two portions in boldface play which of the following roles?(A) The first is a general consideration that introduces the argument; the second is a special situation that weighs against the first.(B) The first is a general principle that is necessary for this argument; the second is an anti-consideration that the argument includes.(C) The first is a premise that this argument includes; the second is a main idea that can be drawn from this argument.(D) The first is an evidence that this argument includes; the second is a conclusion that can not be drawn from this argument.(E) The first is a general situation that supports this argument; the second is a conclusion that can be drawn from a special fact.3. The interstitial nucleus, a sub-region of t he brain’s hypothalamus, is typically smaller for male cats than for female cats. A neurobiologist performed autopsies on male cats who died from disease X, a disease affecting no more than 0.5 percent of male cats, and found that these male cats had interstitial nuclei that were as large as those generally found in female cats. Thus, the size of the interstitial nucleus determines whether or not male cats can contract disease X, but, the hypothalamus is known not to be causally linked to disease Y, and disease X is a subtype of disease Y.The two portions in boldface play which of the following roles?(A) The first is a fact in support of the consideration that is one of two points of this argument; the second is the alternative point that weighs against the first.(B) The first is an evidence that supports the consideration that the argument includes; the second is the fact that weighs against that consideration that could be drawn from the first.(C) The first is a general principle that is against the conclusion; the second is that conclusion.(D) The first is an evidence that supports the conclusion; the second is an exceptional example.(E) The first is a fact in support of the conclusion that the argument depends on; the second is a fact that is against the first one.4. More and more computer programs that provide solutions to mathematical problems in engineering are being produced, and it is thus increasingly unnecessary for practicing engineers to have a thorough understanding of fundamental mathematical principles. Consequently, in training engineers who will work in industry, less emphasis should be placed on mathematical principles, so that space in the engineering curriculum will be available for other important subjects.The two portions in boldface play which of the following roles?(A) The first is the second-premise that the argument includes; the second is the conclusion that could be drawn from this passage.(B) The first is the fact that is necessary for this argument; the second is the conclusion that mustbe drawn from this passage.(C) The first is the part of premise that the argument includes; the second is the inference that could be drawn from this passage.(D) The first is the part of evidence that supports this argument; the second is the inference that could be drawn from this passage.(E) The first is the first conclusion in this argument; the second is the second conclusion in this argument.5. Gasoline-powered boat engines manufactured in the a North American country prior to 1990 contribute significantly to the pollution found in the world’s oceans. In 1990, however, the government imposed stricter pollution controls on gasoline engines manufactured for boats, and beginning in 1995, the government imposed a program of inspections for pre-1990 boat engines with increasingly rigorous pollution standards. As the older boat engines fail to pass inspection, boat owners are increasingly retiring their old engines in favor of newer, less-polluting boat engines. As a result, the amount of pollution these older boat engines emit into the world’s oceans will steadily decrease over the next en years.The two portions in boldface play which of the following roles?(A) The first is a pattern of cause and effect that acts as an evidence in support of this argument; the second is the conclusion that can be drawn from this argument.(B) The first is a fact that acts as a principle in support of this argument; the second is the conclusion that must be drawn from this argument.(C) The first is a pattern of cause and effect that acts as an special evidence in support of the conclusion; the second is a general point that can be drawn from this argument.(D) The first is a pattern of cause and effect that acts as the third evidence in support of the argument; the second is a conclusion that must be true.(E) The first is a final evidence in support of the argument; the second is a conclusion that can be drawn only from the first.6. Plants that exhibit certain leaf diseases tend to measure extremely high in the amount of zinc in their leaf and stem tissue. Botanists have discovered that phosphorus of the type typically used in a phosphorus-high fertilizer reacts with the zinc in such a way as to prevent treated plants from exhibiting the leaf diseases, and zinc is the cause and not merely an effect of the leaf diseases. Thus, plants can be cured from these leaf diseases by the use of a fertilizer high in phosphorus.The two portions in boldface play which of the following roles?(A) The first is the first-premise that the argument includes; the second is the second-premise that is in support of this argument.(B) The first is the background that the argument includes; the second is the part of evidence in support of this argument.(C) The first is the first-premise that the argument includes; the second is the consideration that is in support of the first.(D) The first is the premise that supports the evidence; the second is that evidence.(E) The first is the first-premise that the argument includes; the second is the second-premise that is complementary to other evidence.7. To be accepted as a member at the Brown Country Club, one must have a net worth of over ten million dollars and must not have any connections to the entertainment industry. Robert Chase, the publishing magnate, has a net worth of 5 billion dollars and chase has not financed any Hollywood movies, so he must be accepted as a member at the Brown Country Club.The two portions in boldface play which of the following roles?(A) The first is the part of evidence in support of this argument; the second is the conclusion that could not be drawn from all evidence that the argument contains.(B) The first is the first-evidence that supports this argument; the second is the mainpoint that must be drawn from all evidence that the argument includes.(C) The first is the one fact of two that argument includes; the second is the conclusion that could be drawn from this passage.(D) The first is the background that is necessary for this argument; the second is the conclusion that is not drawn only from the first.(E) The first is the cause that the argument includes; the second is the effect that can be drawn only from this cause.8. The survival of the publishing industry depends upon the existence of a public who will buy the printed word in the form of newspapers, books and magazines. Over the past several years, however, the advance of electronic media, particularly CD-ROMs, online computer services, and the Internet, has made 9information available to the public electronically without the need for printed materials. As the availability of electronic media increases and as it is more easily accessible, the public has less need for printed materials. So the publishing industry is threatened by the advance of the computer information age.The two portions in boldface play which of the following roles?(A) The first is the part of evidence that the argument includes, the second is the conclusion that can be drawn only from the first.(B) The first is the second-premise that the argument includes; the second is the conclusion that is reasonably drawn form this passage.(C) The first is the second-premise that the argument includes, the second is the inference that must be drawn from this argument.(D) The first is the fact that must be true, the second is the inference that can be correctly drawn from this argument.(E) The first is the part of premise that the argument depends on; the second is the conclusion that is incorrectly drawn from this argument9. Something must be done to ease traffic congestion. In traditional small towns, people used to work and shop in the same town in which they lived; but now that stores and workplaces are located far away from residential areas, people cannot avoid traveling long distances each day. Traffic congestion is so heavy on all roads that, even on major highways where the maximum speed limit is 55 miles per hour, the actual speed averages only 35 miles per hour. So new businesses should be encouraged to locate closer to where their workers would live.The two portions in boldface play which of the following roles?(A) Background that the argument depends on and conclusion that can be drawn from the argument.(B) Part of evidence that the argument includes, and inference that can be drawn from this passage.(C) Pre-evidence that the argument depends on and part of evidence that supports the conclusion.(D) Background that argument depends on and part of evidence that supports the conclusion.(E) Pre-evidence that argument includes and a method that helps to supports that conclusion.Answers:(Only for reference)1.C2.B3.A4.E5.A6.E7.A8.D9.B注：此为作者提供的答案，并非一定正确。
2004年GCT逻辑推理能力测试（50题，每题2分，共100分）1.中国女排在雅典奥运会夺冠的事实，使我们明白许多道理。
例如，失败还未成为最后的事实时，决不能轻易接受失败！在胜利尚存一丝微弱的希望时，仍要拼尽全力去争取胜利！否则，就不是真正的强者。
从上述题干可以推出下面哪个选项？A．真正的强者决不接受失败。
B．只有在失败成为不可能改变的事实时，真正的强者才会去接受失败。
C．失败者会轻易地接受失败。
D．正如女排队员爱唱的那首歌说的，阳光总在风雨后。
2.新疆北鲵一种濒危珍稀动物，1840年有沙俄探险家首次发现，此后一百年多年不见踪影，1898年在新疆温泉县重新被发现。
但资料显示，自1898年以后的15年间，新疆北鲵的数量减少了一半。
有专家认为，新疆北鲵的栖息地原是当地的牧场，每年夏季在草原上随处走走动的牛羊会将其大量踩死，因而造成其数量锐减。
以下哪项为真，将对上述专家的观点提出最大质疑？A．1997年“温泉新疆北鲵自然保护区”建立，当地牧民保护新疆北鲵的意识日益提高。
B．近年来雨水减少，地下水位下降，新疆北鲵赖以栖息的水源环境受到影响。
C．新疆北鲵是一种怕光的动物，白天大多躲在小溪的石头下，也避开了牛羊的踩踏。
D．新疆北鲵的栖息地位于山间，一般游人根本无法进入。
3. 散文家：智慧与聪明是令人渴望的品质。
但是，一个聪明并不意味着他很有智慧，而一个人有智慧也不意味着他很聪明。
在我所遇到的人中，有的人聪明，有的人有智慧，但是，却没有人同时具备这两种品质。
A．没有人聪明但没有智慧，也没有人有智慧却不聪明。
B．大部分人既聪明，又有智慧。
C．没有人即聪明，又有智慧。
D．大部分人既不聪明，也没有智慧。
4. 在回答伊拉克是否实际拥有大规模杀伤性武器或者只是曾试图获得这些武器时，美国总统布什称：“这有什么区别吗？如果他获得这些武器，他会变得更危险。
他是‘9.11事件’后美国应当解决掉的威胁。
在12年这么长的时间里，世界一直在说他很危险，到现在我们才解决了这一危险。
2 把下列谓词公式化成子句集：⑴(x)( y)(P(x, y)A Q(x, y))(2) ( x)( y)(P(x, y)f Q(x, y))(3) ( x)( y)(P(x, y)V (Q(x, y)~ R(x, y)))(4) ( x) ( y) ( z)(P(x, y 尸 Q(x, y)V R(x, z))解：⑴ 由于(x)( y)(P(x, y)A Q(x, y))已经是Skolem 标准型，且合取范式，所以可直接消去全称量词、合取词，得{ P(x, y), Q(x, y)}再进行变元换名得子句集：S={ P(x, y), Q(u, v)}(2) 对谓词公式(x)( y)(P(x, y)f Q(x, y)),先消去连接词得:( x)( y)(P(x, y)V Q(x, y))此公式已为 Skolem 标准型。
再消去全称量词得子句集：S={P(x, y)V Q(x, y)}(3) 对谓词公式(x)( y)(P(x, y)V (Q(x, y)~ R(x, y))),先消去连接词( x)( y)(P(x, y)V (Q(x, y)V R(x, y)))此公式已为前束范式。
再消去存在量词，即用 Skolem 函数f(x)替换y 得：( x)(P(x, f(x))V Q(x, f(x))V R(x, f(x)))此公式已为 Skolem 标准型。
最后消去全称量词得子句集：S={P(x, f(x))V Q(x, f(x))V R(x, f(x))}(4) 对谓词(x) ( y) ( z)(P(x, y 尸 Q(x, y) V R(x, z)),先消去连接词( x) ( y) ( z)(P(x, y)V Q(x, y)V R(x, z))再消去存在量词，即用 Skolem 函数f(x)替换y 得：( x) ( y) (P(x, y)V Q(x, y)V R(x, f(x,y)))此公式已为 Skolem 标准型。
