PART COMPUTERSOFTWARECHAPTER3MATHEMATICFUNDAMENTALS3 1BOOLEANALGEBRA chapter3 3 1 3 1BOOLEANALGEBRA Mainpoint Mainpoint Developmentandfunctionofbooleanalgebra Conceptofsetalgebra Setoperations Booleanoperations 计算机英语 第三版 1 计算机英语 第三版 TheconceptofaBooleanalgebrawasfirstproposedbytheEnglishmathematicianGeorgeBoolein1847 Sincethattime Boole soriginalconceptionhasbeenextensivelydevelopedandrefinedbyalgebraistsandlogicians 1 TherelationshipsamongBooleanalgebra setalgebra logic andbinaryarithmetichavegivenBooleanalgebrasacentralroleinthedevelopmentofelectronicdigitalcomputers 1 Whatisthefundamentalsofelectronicdigitalcomputers 计算机英语 第三版 Themostintuitivedevelopmentofbooleanalgebrasarisesfromtheconceptofasetalgebra LetS a b c andT a b c d e betwosetsconsistingofthreeandfiveelements respectively WesaythatSisasubsetofT sinceeveryelementofS namely a b andc belongstoT SinceThasfiveelements thereare25subsetsofT forwemaychooseanyindividualelementtobeincludedoromittedfromasubset 2 Notethatthese32subsetsincludeTitselfandtheemptyset whichcontainsnoelementsatall 3 原因状语从句 原因状语从句 计算机英语 第三版 IfTcontainsallelementsofconcern itiscalledtheuniversalset GivenasubsetofT suchasS wemaydefinethecomplementofSwithrespecttoauniversalsetTtoconsistofpreciselythoseelementsofTwhicharenotincludedinthegivensubset 4 Thus Sasabovedefinedhasasitscomplement withrespecttoT S d e Theunionofanytwosets subsetsofagivenset consistsofthoseelementsthatareinoneortheotherorinbothgivensets 5 theintersectionoftwosetsconsistsofthoseelementsthatareinbothgivensets 宾语补足语 定语从句 定语从句 定语从句 Weusethesymbol todenotetheunion and todenotetheintersectionoftwosets Forexample ifB b d e thenB S a b c d e andB S b 2 计算机英语 第三版 2 Explaintheoperationsofunionandintersection Whileothersetoperationsmaybedefined 6 theoperationsofcomplementation union andintersectionareofprimaryinteresttous 让步状语从句 ABooleanalgebraisafiniteorinfinitesetofelementstogetherwiththreeoperations negation addition andmultiplication thatcorrespondtothesetoperationsofcomplementation union andintersection respectively AmongtheelementsofaBooleanalgebraaretwodistinguishedelements 0 correspondingtotheemptyset and1 correspondingtotheuniversalset ForanygivenelementofaBooleanalgebra thereisauniquecomplementwiththepropertythata a 1andaa 0 同位语 定语从句 条件状语 计算机英语 第三版 Booleanadditionandmultiplicationareassociativeandcommutative 7 asareordinaryadditionandmultiplication butotherwisehavesomewhatdifferentproperties TheprincipalpropertiesaregiveninTable3 1 wherea b andcareanyelementsofaBooleanalgebra 3 3 ListtheprincipalpropertiesofBooleanalgebra 计算机英语 第三版 Table3 1 Table3 1 8 Distributivity a b c ab aca bc a b a c Idempotency a a aaa aAbsorptionlaws a ab aa a b aDeMorgan slaws a b ab ab a b Sinceafinitesetofnelementshasexactly2nsubsets anditcanbeshownthatthefiniteBooleanalgebrasarepreciselythefinitesetalgebras 9 eachfiniteBooleanalgebraconsistsofexactly2nelementsforsomeintegern 原因状语从句 主语从句 计算机英语 第三版 Forexample thesetalgebraforthesetTdefinedabovecorrespondstoaBooleanalgebraof32elements Tables3 2definetheBooleanoperationsforBooleanalgebrasoftwoelements respectively Table3 2Twoelements WhileitispossibletouseadifferentsymboltodenoteeachelementofaBooleanalgebra itisoftenmoreusefultorepresentthe2nelementsofafiniteBooleanalgebrabybinaryvectorshavingncomponents 让步状语从句 Table3 2 WithsucharepresentationtheoperationsoftheBooleanalgebraareaccomplishedcomponentwise 10 byconsideringeachcomponentasanindependenttwo elementBooleanalgebra 11 Thiscorrespondstorepresentingsubsetsofafinitesetbybinaryvectors Forexample sincethesetThasfiveelements wemayrepresentitssubsetsbyfive componentbinaryvectors eachcomponentdenotinganelementofthesetT Anumeral1intheithcomponentofthevectordenotestheinclusionoftheithelementofthatparticularsubset a0denotesitsexclusion 计算机英语 第三版 原因状语从句 Thus thesubsetS a b c hasthebinaryvectorrepresentation 1 1 1 0 0 ThesetoperationsbecomeBooleanoperationsonthecomponentsofthevectors Thisrepresentationofsets andthecorrespondencetoBooleanorlogicaloperations isveryusefulininformationretrieval Becauseofit setsofdocumentandquerycharacteristicsmaybeeasilyandrapidlymatched 4 4 Whatisveryusefulininformationretrieval 计算机英语 第三版 NOTES1 1 refine原意为 精炼 提纯 精纯 此处翻译为 精炼 该句中使用了完成时被动式 从而强调从这一概念产生时起 就一直被发展 developed 与精炼 refined 2 该句中since引导一个原因状语从句 for也引导一个原因状语从句 补充说明子集总数为什么是这么多 3 which引导一个非限制性定语从句 说明空集的含义 NOTES 计算机英语 第三版 4 句中Given为分词引导的条件状语 不定式toconsistof对complementofS起补充说明的作用 whicharenot 引导一个限制性定语从句 修饰elements 5 inoneortheotherorinbothgivensets该并列介词短语说明并集的元素来源于两个集合中的一个 inone 或另一个 theother 或同时出现于两个之中 inbothgivensets 6 句中operation在布尔代数中译为 运算 而不译为 操作 while引导一个让步状语从句 计算机英语 第三版 NOTES2 7 associative结合的 commutative交换的 8 表3 1中distributivity为分配律 idempotency为同一律 Absorptionlaws为吸收律 Demorgan slows为德 摩根定律 9 有限布尔代数 和 有限集合代数 中的 有限 是指其中集合的元素个数有限 运算也建立在该有限集之上 10 componentwise wise后缀 用以构成副词 表示 逐一 状态 样子 等 计算机英语 第三版 NOTES3 11 byconsidering 此处by表示方法 手段等 作状语 two elementBooleanalgebra意指只含0和1的布尔代数 计算机英语 第三版 NOTES4 KEYWORDS Booleanalgebra布尔代数union并setalgebra集合代数Intersection交set集 合 c