大学逻辑导论答案.docx
《大学逻辑导论答案.docx》由会员分享，可在线阅读，更多相关《大学逻辑导论答案.docx（16页珍藏版）》请在冰点文库上搜索。
大学逻辑导论答案
大学逻辑导论答案
LT
000010
010010
011011
110110
b.画出该文档集的倒排索引（参考图1-3中的例子）。
解答：
参考a。
习题1-3[*]对于习题1-2中的文档集，如果给定如下查询，那么返回的结果是什么？
a.schizophreniaanddrug解答：
{文档1，文档2}
b.forandnot（drugorapproach）解答：
{文档4}
习题1-4[*]对于如下查询，能否仍然在o（x+y）次内完成？
其中x和y分别是brutus和caesar所对应的倒排记录表长度。
如果不能的话，那么我们能达到的时间复杂度是多少？
a.brutusandnotcaesarb.brutusornotcaesar
解答：
a.可以在o（x+y）次内完成。
通过集合的减操作即可。
具体做法参考习题1-11。
b.不能。
不可以在o（x+y）次内完成。
因为notcaesar的倒排记录表需要提取其他所有词项对应的倒
排记录表。
所以需要遍历几乎全体倒排记录表，于是时间复杂度即为所有倒排记录表的长度的和n，即o（n）或者说o（x+n-y）。
习题1-5[*]将倒排记录表合并算法推广到任意布尔查询表达式，其时间复杂度是多少？
比如，对于查询
c.
解答：
时间复杂度为o（qn），其中q为表达式中词项的个数，n为所有倒排记录表长度之和。
也就是说可以在词项个数q及所有倒排记录表长度n的线性时间内完成合并。
由于任意布尔表达式处理算法复杂度的上界为o（n），所以上述复杂度无法进一步改进。
习题1-6[**]假定我们使用分配律来改写有关and和or的查询表达式。
a.通过分配律将习题1-5中的查询写成析取范式；
12
b.改写之后的查询的处理过程比原始查询处理过程的效率高还是低？
c.上述结果对任何查询通用还是依赖于文档集的内容和词本身？
解答：
a.析取范式为：
（brutusandnotanthonyandnotcleopatra）or（caesarandnotanthonyandnotcleopatra）
b.这里的析取范式处理比前面的合取范式更有效。
这是因为这里先进行and操作（括号内），得到的倒排记录表都不大，再进行or操作效率就不会很低。
而前面需要先进行or操作，得到的中间倒排记录表会更大一些。
（brutusorcaesar）andnot（antonyorcleopatra）
我们能在线性时间内完成合并吗？
这里的线性是针对什么来说的？
我们还能对此加以改进吗？
c.上述结果不一定对，比如两个罕见词a和b构成的查询（aorb）andnot（hongorkong），假设hongkong一起出现很频繁。
此时合取方式可能处理起来更高效。
如果在析取范式中仅有词项的非操作时，b中结果不对。
习题1-7[*]请推荐如下查询的处理次序。
d.（tangerineortrees）and（marmaladeorskies）and（kaleidoscopeoreyes）其中，每个词项对应的倒排记录表的长度分别如下：
词项eyeskaleidoscopemarmaladeskiestangerinetrees解答：
由于：
（tangerineortrees）?
46653+316812=363465（marmaladeorskies）?
107913+271658=379571（kaleidoscopeoreyes）?
87009+213312=30321所以推荐处理次序为：
（kaleidoscopeoreyes）and（tangerineortrees）and（marmaladeorskies）
习题1-8[*]对于查询
e.friendsandromansand（notcountrymen）
如何利用countrymen的文档频率来估计最佳的查询处理次序？
特别地，提出一种在确定查询顺序时对逻辑非进行处理的方法。
倒排记录表长度2133128700910791327165846653316812
解答：
令friends、romans和countrymen的文档频率分别为x、y、z。
如果z极高，则将n-z作为notcountrymen的长度估计值，然后按照x、y、n-z从小到大合并。
如果z极低，则按照x、y、z从小到大合并。
习题1-9[**]对于逻辑与构成的查询，按照倒排记录表从小到大的处理次序是不是一定是最优的？
如果是，请给出解释；如果不是，请给出反例。
解答：
不一定。
比如三个长度分别为x,y,z的倒排记录表进行合并，其中xyz，如果x和y的交集为空集，那么有可能先合并x、y效率更高。
习题1-10[**]对于查询xory，按照图1-6的方式，给出一个合并算法。
解答：
1answer-（）
2whilep1!
=nilandp2!
=nil3doifdocid（p1）=docid（p2）4thenadd（answer,docid（p1））5p1-next（p1）6p2-next（p2）
7elseifdocid（p1）docid（p2）8thenadd（answer,docid（p1））9p1-next（p1）10elseadd（answer,docid（p2））11p2-next（p2）12ifp1!
=nil//x还有剩余
13thenwhilep1!
=nildoadd（answer,docid（p1））14elsewhilep2!
=nildoadd（answer,docid（p2））15return（answer）
习题1-11[*]如何处理查询xandnoty？
为什么原始的处理方法非常耗时？
给出一个针对该查询的高效合并算法。
解答：
由于noty几乎要遍历所有倒排表，因此如果采用列举倒排表的方式非常耗时。
可以采用两个有序集合求减的方式处理xandnoty。
算法如下：
meger（p1,p2）1answer（）2whilep1!
=nilandp2!
=nil3doifdocid（p1）=docid（p2）4thenp1?
next（p1）5p2?
next（p2）6elseifdocid（p1）docid（p2）7thenadd（answer,docid（p1））8p1?
next（p1）9elseadd（answer,docid（p2））10p2?
next（p2）11ifp1!
=nil//x还有剩余
12thenwhilep1!
=nildoadd（answer,docid（p1））13return（answer）
习题1-12[*]利用westlaw系统的语法构造一个查询，通过它可以找到professor、teacher或lecturer中的
任意一个词，并且该词和动词explain在一个句子中出现，其中explain以某种形式出现。
解答：
professorteacherlecturer/sexplain!
习题1-13[*]在一些商用搜索引擎上试用布尔查询，比如，选择一个词（如burglar），然后将如下查
询提交给搜索引擎
（i）burglar；（ii）burglarandburglar；（iii）burglarorburglar。
对照搜索引擎返回的总数和排名靠前的文档，这些结果是否满足布尔逻辑的意义？
对于大多数搜索引擎来说，它们往往不满足。
你明白这是为什么吗？
如果采用其他词语，结论又如何？
比如以下查询
（i）knight；（ii）conquer；（iii）knightorconquer。
第二章词汇表和倒排记录表
习题2-1[*]请判断如下说法是否正确。
a.在布尔检索系统中，进行词干还原从不降低正确率。
b.在布尔检索系统中，进行词干还原从不降低召回率。
c.词干还原会增加词项词典的大小。
d.词干还原应该在构建索引时调用，而不应在查询处理时调用。
解答：
a错b对c错d错
习题2-7[*]考虑利用如下带有跳表指针的倒排记录表
和一个中间结果表（如下所示，不存在跳表指针）进行合并操作。
3589959799100101
采用图2-10所示的倒排记录表合并算法，请问：
a.跳表指针实际跳转的次数是多少（也就是说，指针p1的下一步将跳到skip（p1））？
一次，24—75
b.当两个表进行合并时，倒排记录之间的比较次数是多少？
【如下答案不一定正确，有人利用程序
计算需要21次，需要回到算法，本小题不扣分，下面不考虑重新比较同意对数字】解答：
18次：
3,3,5,5,9,89,
15,89,24,89,75,89,92,89,81,89,84,89,89,89,92,95,115,95,96,95,96,97,97,97,100,99,100,100115,101c.
如果不使用跳表指针，那么倒排记录之间的比较次数是多少？
解答：
19次：
3,3,5,5,9,89,15,89,24,89,39,89,60,89,68,89,75,89,81,89,84,89,89,8992,95,96,95,96,97,97,97,100,99,100,100,115,101
习题2-9[*]下面给出的是一个位置索引的一部分，格式为：
词项:
文档1:
〈位置1,位置2,…〉;文
档2:
〈位置1,位置2,…〉。
angels:
2:
〈36,174,252,651〉;4:
〈12,22,102,432〉;7:
〈17〉;fools:
2:
〈1,17,74,222〉;4:
〈8,78,108,458〉;7:
〈3,13,23,193〉;fear:
2:
〈87,704,722,901〉;4:
〈13,43,113,433〉;7:
〈18,328,528〉;in:
2:
〈3,37,76,444,851〉;4:
〈10,20,110,470,500〉;7:
〈5,15,25,195〉;rush:
2:
〈2,66,194,321,702〉;4:
〈9,69,149,429,569〉;7:
〈4,14,404〉;to:
2:
〈47,86,234,999〉;4:
〈14,24,774,944〉;7:
〈199,319,599,709〉;tread:
2:
〈57,94,333〉;4:
〈15,35,155〉;7:
〈20,320〉;
where:
2:
〈67,124,393,1001〉;4:
〈11,41,101,421,431〉;7:
〈16,36,736〉;那么哪些文档和以下的查询匹配？
其中引号内的每个表达式都是一个短语查询。
a.
“foolsrushin”。
解答：
文档2、4、7
b.“foolsrushin”and“angelsfeartotread”。
【篇三：
《大学逻辑导论》要点个人整理】
章：
绪论
逻辑学：
逻辑学是一门研究思维的形式结构及其规律的科学。
1.思维包括感性认识和理性认识两个阶段，其中感性认识属于低级阶段。
基本形式包括感
觉，知觉和表象。
2.思维的形式结构，即思维的逻辑形式。
包括逻辑常项和逻辑变项。
逻辑常项是判定一种
逻辑形式具体类型的唯一根据。
3.自然语言，即日常语言，人工语言，即符号语言。
4.逻辑思维基本规律：
同一律，矛盾律，排中律，充足理由律。
5.逻辑学具有工具性，全人类性。
逻辑学的作用：
】
1.促进逻辑思维由自发向自觉转变。
2.培养和提高人们认识事物、从事科学研究的能力。
3.有利于识别、驳斥谬误和诡辩。
第二章：
概念的概述
什么是概念：
概念是反映对象本质属性或特有属性的思维形式。
事物的属性：
事物自身的性质及其与其他事物的关系。
属性还分为本质属性和非本质属性，本质属性：
就是决定事物之所以为该事物并区别于其他事物的属性。
非本质属性：
不具有决定性作用。
特有属性：
只为该事物所具有而不为其他事物所具有的属性。
非特有属性：
该事物不单独具有的属性。
概念与语词：
1.概念是一种思维形式，语词是语言形式。
2.任何概念都必须借助语词表达，但不是所有语词都能表达概念。
3.同一概念可以用不同语词表达
4.同一语词在不同情况下表达不同概念
概念的内涵和外延
1.内涵：
反映在概念中的对象的本质属性或特有属性。
2.外延：
具有概念所反映的本质属性或特有属性的对象。
3.内涵、外延具有确定性和灵活性：
在一定的条件下，概念的涵义和适用范围是确定的，
不能任意改变或混淆不清，在不同的条件下，概念的涵义，适用范围可以变化。
概念的种类：
1.单独概念，如“长城”，“中国”
2.普遍概念，如“工人”，“士兵”
3集合和非集合概念辨析：
集合概念，组成该集合的任何个体都具有其性质，具体看来，就是能不能拆分。
具体语境和句子中分析。
4肯定（正）概念，否定（负）概念。
负概念是相对某个特定范围而言，这个范围在逻辑上叫该概念的论域，如“不合法行为”，其论域就是“行为”。
概念间的关系：
1.全同关系：
两个概念外延完全重合。
所有a都是b，所有b都是ａ但内涵不相同，如果内涵也相同，那就是同一概念，不是全同概念。
2.属种关系（真包含关系）：
一个概念的部分外延与另一概念的全部外延相重合的关系。
大的是属概念，小的是种概念。
3.种属关系。
（大多数情况下属种或种属关系的概念不宜并列使用，属于“属种不当并列”。
）
4.交叉关系：
a,b两个概念，仅有一部分重合
以上四种关系统称相容关系，
全异关系，又称不相容关系。
可分为：
（1）.反对关系：
同时包含于另一属概念，其外延之合小于其属概念外延。
（2）矛盾关系，也是同时包含于另一属概念，只不过外延之和恰好等于其属概念的外延
概念的限制、概括
1.反变关系：
只适用于具有属种或者种属关系的两个概念，一个概念外延愈大，内涵愈少，一个概念外延愈少，内涵愈多，反之也是，例：
本科生与大学生是种属概念，本科生外延小，内涵多。
大学生反之。
这是对概念进行限制和概括的逻辑根据。
2.概念的限制：
（1）增加概念内涵，导致其外延缩小。
如：
对“工人”增加“在石油岗位
工作”的内涵，就限制为“石油工人”。
（2）限制是缩小概念的外延，即由属概念推演到种概念的方法。
（3）限制可以一次完成，也可以连续进行。
（单独概念是限制的极限）一般增加限制性语词可以进行对概念的限制，但不是所有，如：
“美丽的杭州西湖”。
概念的限制实现认识由一般到特殊的过渡。
3.概念的概括：
（1）减少概念的内涵，进而扩大其外延。
（2）概括是扩大概念的外延，由种概念过渡到属概念的逻辑方法。
（概括的极限是哲学范畴）
（3）并不一定要通过减去限制词来对概念进行概括，如：
“学生”概括为“人”。
定义
定义：
（1）定义是揭示概念内涵的逻辑方法，给概念下定义，用简短明了的语句将概念所反映的对象的本质属性或特有属性揭示出来。
（2）定义由被定义项，定义项和定义联项三部分组成。
定义的种类：
（1）属加种差定义：
通过揭示被定义项的临近属概念和种差，进而明确概念内涵的
定义。
（被定义项=种差+临近的属概念）
第1步，找出被定义项的邻近属概念。
第2步，揭示被定义项的种差。
第3步，构成定义项。
第4步，构成属加种差定义。
（2）语词定义：
一种特殊定义，通过说明（揭示某语词已经确定的意义）或规定（对
一个新词或有特定意义的语词做出规定性解释）语词的意义来揭示概念内涵。
定义的规则：
1.定义项的外延与被定义项的外延要相等。
（完全重合）
如果不：
那就会发生定义过宽（定义项外延大于被定义项），过窄的错误。
2.定义项中不能直接间接地包含被定义项。
如果有：
直接的话就是“同语反复”（痛苦就是痛苦的感觉），间接的话就是“循环定义”（转了一圈又回到原地）
3.定义一般要用肯定形式（真理不是谬误：
错）（除非是给负概念下定义，因为否定形式
无法揭示被定义项之内涵）
4.定义要清楚，确切，不然就会犯“定义含混”（杜林：
“塑造出来的模式化）或者“用比
喻做定义”的错误
划分
辨析：
与分解不同，分解是整体与部分的关系，划分是属种关系。
定义：
就是把属概念所包含的种概念解释出来，进而明确属概念外延的逻辑方法。
划分三要素：
划分的母项，划分的子项，划分的根据。
种类：
1
（1）一次划分：
只包含一层母项和子项的划分。
（2）.连续划分：
至少包含两层母项和子项。
2
（1）二分法：
一次将母项分为两个子项的划分。
根据是对象有无某种属性，将一个属概念分为一个正和负的概念。
二分法剪接易行，但是负概念内涵不清晰。
非二分法就是二分法以外的划分。
划分规则：
。
1.各子项外延的和必须等于母项外延。
否则，我就会出现“划分不全”（子项外延之和少了）“多出子项”（子项外延之和大于母项外延）的错误。
2.每次划分的根据必须同一，否则，就会犯“划分根据不同一“的错误。
3.划分后的子项应互不相容。
否则，就会犯“子项相容”的错误。
分类与列举：
任何分类都是划分，但有的划分并不是分类。
第三章：
1命题：
定义：
命题就是人在认知过程中，对思维对象属性进行肯定或否定断定的思维形式。
命题的逻辑形式：
1.任何命题要么是肯定断定，要么否定断定。
2.任何命题非真即假。
命题的真、假统称为命题的真值。
命题和语句的联系：
1.所有的命题都通过一定的语句来表达，但并非所有语句都直接表
达命题。
2.同一命题可用不同语句表达。
3.同一语句可以表达不同命题。
推理由三部分组成：
已知命题：
前提，由已知命题推导出来的新命题：
结论，还有推理形式
（前提与结论在形式上的关联关系）
推理的种类：
见书p49页。
必然性推理前提就包含了结论（有效性）。
或然性推理前提真结果不一定真（可靠性）。
推理和复句：
1.推理做为思维形式，必须通过复句或句群来表达，但并非复句和句群都表达命题。
2.从思维过程来看，任何推理都有前提和结论，形式结构是完整的。
3.推理的逻辑形式是规范的、确定的。
性质命题：
对思维对象的性质直接作出肯定或否定断定的命题。
要素：
1.主项：
被断定对象：
s
2.谓项：
表
达命题所断定对象的性质的概念：
p
3.联项：
表达命题所断定对象与其性质联系的概念（语词），分肯定，否定两种。
4.量项：
表达命题所断定对象数量或范围的概念。
（性质命题量项分为：
全称，特称，单称三种）
性质命题的种类：
Ａ（全称肯定）Ｅ（全称否定）Ｉ（特称（某类对象）肯定命题）Ｏ（特称肯定命题）ａ（单称肯定命题）ｅ（单称否定命题（特定对象））（ＳＥ１Ｐ）同a。
性质命题真值规律（背p54表格）
性质命题之间的真值关系（背p57表格）
性质命题主、谓项的周延性。
（背p59性质命题周延情况表）
明确：
1.周延性是对性质命题主、谓项外延被断定情况的分析。
2.主、谓项的周延性根据性质命题的逻辑形式来确定，与主、谓项所反映对象的实际情况无关（如“有的鲜花是要凋谢的”这一命题的鲜花，不周延）
3.周延性跟命题真假无关。
性质命题直接推理（反复看书上的内容p61开始，熟悉符号语言于文字语言间的对应关系）
1.对当关系直接推理（根据相同素材的性质命题间的真值关系，一个命题直接推导出另一个命题的推理）
（1）矛盾关系推理（很简单，就是前四类性质命题的矛盾关系（对角线）可互推）
（2）反对关系推理（就是反对关系间命题不可同真，可同假，即一个为真，另一个就
为假）
（3）下反对关系（一个假，另一个就真）
（4）差等关系推理（全称真推出特称真，特称假推出全称假）
性质命题变形直接推理（改变性质命题的形式，得到一个新的性质命题的必然性推理）（就是换质位推理）
（一）换质推理
通过改变性质命题的质，由此得出新命题的推理
规则：
（肯定变否定，否定变肯定）
2.前提命题的谓项变为矛盾的概念
3.主、谓、量项位置不变（-表示否定，读作并非，命题变化后叫非p（p上面一横，p
的矛盾概念）
ｅｇ：
具体记的时候是ｐ６３，同一横排的ａｅ，ｉｏ之间转换。
（二）换位推理
改变命题主谓项位置，得到新的性质命题的推理
规则：
1.改变主谓项的位置2不改变前提命题的质
3前提中不周延的概念，结论中也不周延。
eg:
具体记p63
换质位推理:
（熟练连续换质位的操作）
第四章：
简单命题及其推理（中）第一节三段论概述：
三段论：
两个包含共同项的性质命题为前提推出一个新的性质命题为结论的推理。
（联系两个前提中的不同概念，推出结论）
三段论的结构（重点）
三段论都只包含三个不同的项，每个项出现两次大项：
（作为结论的命题的谓项）（p）
中项：
（不在结论中出现，起连接作用的在前提中出现的项）（m）
小项：
（作为结论的命题的主项）（s）
任何三段论都由三个性质命题组成。
两个前提，一个结论，大项和中项结合的命题称为大前提，小项和中项结合的命题称为小前提。
在三段论中：
单称肯定命题和单称否定命题当全称肯定和全称否定命题处理。
三段论公理：
如果一类对象的全部是什么或不是什么，那么，该类对象的部分也是什么或不是什么。
三段论的规则
1.三段论中有且只能有三个不同的项。
（错误：
四项错误）
2.中项在前提中至少要周延一次。
（错误：
中项两次不周延）
3.前提中不周延的项在结论中也不得周延（错误：
大项不当周延，小项不当周延）
4.两个否定前提无法推出结论。
5.前提有一个否定，结论必否定，结论否定，前提必有一个否定。
6.两个特称前提无法推出结论
7.前提中有一个特称，结论必特称。
升级会员 