第二章系统可靠性模型课件

第二节第二节 集合代数、布尔代数、容斥集合代数、布尔代数、容斥 原理及不交型算法原理及不交型算法-（2 2）一、布尔代数一、布尔代数-（2 2）第第 二二 章章 系统可靠性模型系统可靠性模型(2)二、容斥原理二、容斥原理-（2222）三、不交型算法三、不交型算法-（3434）+四、例题四、例题-（4646）1第二节第二节 集合代数、集合代数、布尔代数、容斥原理及布尔代数、容斥原理及 不交型算法不交型算法 18471847年英国年英国数学家布尔数学家布尔发表了逻辑的数学分析，发表了逻辑的数学分析，1854年又发表了思维的规律，年又发表了思维的规律，这是把逻辑数学化的一次成这是把逻辑数学化的一次成功的尝试。因此至今人们仍把逻辑代数称之为功的尝试。因此至今人们仍把逻辑代数称之为布尔代数布尔代数。一、布尔代数一、布尔代数 由于产品失效或成功是由零、部件失效或成功的由于产品失效或成功是由零、部件失效或成功的集合集合形成形成的，所以研究产品失效，首先的，所以研究产品失效，首先应研究集合的运算应研究集合的运算。为了便于下面进行系统可靠性的特征量的计算，需要布为了便于下面进行系统可靠性的特征量的计算，需要布尔代数这方面的数学知识，因此，首先介绍布尔代数。尔代数这方面的数学知识，因此，首先介绍布尔代数。逻辑代数有三大分支：逻辑代数有三大分支：以集合为研究对象的称集合代以集合为研究对象的称集合代数；数；以开关线路分析的形式表示的称开关代数；以开关线路分析的形式表示的称开关代数；以命题以命题为研究对象称命题代数。为研究对象称命题代数。21.集合的并、交、补运算集合的并、交、补运算为分析直观起见，用为分析直观起见，用文氏图来说明集合的运算。文氏图来说明集合的运算。（1）集合的并）集合的并仍为集合仍为集合,如图如图2-7（a)中阴影部分中阴影部分图图2-7（a)集合的并集合的并A B集合集合是指具有某种特定性质的总体或全体。是指具有某种特定性质的总体或全体。集合集合C1为集合为集合A和和B的并，或称为的并，或称为A和和B的和。符号为的和。符号为“”，可称，可称并并，也可称也可称加加，中文表示，中文表示或或的意思（即的意思（即A和和B至少发生一个）。至少发生一个）。显然，集合显然，集合C1的元素的元素x是由是由A的元素的元素B的元素汇总而得。的元素汇总而得。3(2)集合的交集合的交 仍为集合,如图如图2-7（b)中阴影部分中阴影部分图图2-7（b)集合的交集合的交A B 集合集合C2为集合为集合A和和B的交的交，或，或C2为为A和和B的的积积。符号。符号“”，可称，可称交交，也可称也可称乘乘，中文表示，中文表示与与、且且的意思的意思（即（即A和和B必须同时发生）。必须同时发生）。显然，显然，C2的元素就是的元素就是A与与B的的公共元素。公共元素。4 (3)集合的补也是集合集合的补也是集合,图图2-7（c）中的阴影部分中的阴影部分 集合集合C3 为集合为集合B的补，或的补，或C3为为B的对立集合。符号的对立集合。符号“”,或或“”，可称，可称“补补”，也可称，也可称非非，中文表示，中文表示“不是不是”之意。之意。图图2-7（c)集合的补集合的补B 显然，显然，C3的元素只能由的元素只能由集合集合B以外的元素所组成。以外的元素所组成。5 并、交、补是集合代数中并、交、补是集合代数中3个最基本的运算。它们用文个最基本的运算。它们用文氏图（氏图（Venn Diagram）表示为：）表示为：图图2-7（a）为）为A与与B的并集的并集;图图2-7（a)集合的并集合的并A B（b）为）为A与与B的交集的交集;（c）为）为B的补集。的补集。图图2-7（b)集合的交集合的交A B图图2-7（c)集合的补集合的补B62.集合代数的基本规律集合代数的基本规律（1）交换律）交换律 AB=BA ,A+B=B+A AB=BA ,AB=BA设设 A、B、C 3个集合。个集合。为空集：是没有任何元素的集合。为空集：是没有任何元素的集合。I 为全集：是在所讨论的一定范围内包含一切可能元素为全集：是在所讨论的一定范围内包含一切可能元素 的集合。的集合。（2）结合律）结合律（AB）C=A（BC）（A+B）+C=A+（B+C）（AB）C=A（BC）（AB）C=A（B C）7（3）分配律）分配律 A（BC）=（AB）（AC）A（B+C）=AB+AC 分配律的文氏图见图分配律的文氏图见图28所示所示。图图2-8图图2-88 A（BC）=（AB）（AC）A+（BC）=（A+B）（）（A+C）分配律的文氏图见图分配律的文氏图见图29 9所示所示。图图2-9图图2-99（4）吸收律）吸收律 A（AB）=A（A+AB）=A A（AB）=A（A（A+B）=A）吸收吸收律的文氏图见图律的文氏图见图210所示所示 图图2-10图图2-1010（5）基元律）基元律 I为为全集：必然事件，一切可能元素的集合。则有全集：必然事件，一切可能元素的集合。则有 A=A ,IA=I设设为空集：不可能事件，无元素的集合；为空集：不可能事件，无元素的集合；A=,I IA=A（6）补元律）补元律注意：集合代数运算也应注意：集合代数运算也应先先后后运算运算，（即先，（即先乘除后加减）乘除后加减）。113.布尔代数的有关基本定理布尔代数的有关基本定理 在在数数学学系系统统中中，如如果果变变量量只只能能取取0 或或 1（失失效效或或不不失失效效），上上述述定定义义的的并并、交交、补补，且且满满足足以以上上6条条基基本本规规律律，该该系系统统叫叫布布尔尔代代数数，“”、“”、“”叫叫布布尔尔运运算算。交这算符号。交这算符号可简化为可简化为“”，而且可以省略，如，而且可以省略，如 书书中中讲讲了了布布尔尔代代数数的的七七个个定定理理:(1)基基元元互互补补律律、(2)双双补补律律、(3)德德摩摩根根定定律律（律律）、(4)等等幂律、幂律、(5)复盖律、（复盖律、（6）归并律和（）归并律和（7）对偶性定理。）对偶性定理。AB=AB=AB12（1）基元互补律基元互补律（2）双补律双补律（3）等幂律等幂律 I为为全集：必然事件，一切可能元素的集合。则有全集：必然事件，一切可能元素的集合。则有 设设为空集：不可能事件，无元素的集合；为空集：不可能事件，无元素的集合；13（4）德摩根）德摩根(De Morgan)律律 图图 De Morgan 律律 文氏图文氏图图图 De Morgan 律律 文氏图文氏图其文氏图为其文氏图为其文氏图为其文氏图为14（5）覆盖律）覆盖律AABAB 覆盖律文氏图为。覆盖律文氏图为。图图 覆盖律覆盖律 文氏图文氏图 A（AB）=AB覆盖律文氏图为。覆盖律文氏图为。图图 覆盖律覆盖律文氏图文氏图15 ABACCB =ABAC覆盖律文氏图见下图覆盖律文氏图见下图 图图 覆覆 盖盖 律律 文文 氏氏 图图16图图 覆覆 盖盖 律律 文文 氏氏 图图 （A AB）(AC）(CB）=（AB）(A AC）覆盖律文氏图见下图覆盖律文氏图见下图 所示。所示。17（6）归并律）归并律图图 2-11 归并律的文氏图归并律的文氏图归并律的文氏图如图归并律的文氏图如图2-11所示。所示。18（7）对偶性定理）对偶性定理 对对偶偶定定理理可可以以证证明明布布尔尔代代数数的的任任何何一一个个定定理理的的对对偶式都成立，并是一条定理，称偶式都成立，并是一条定理，称原定理的对偶性定理原定理的对偶性定理。如果能证明原定理成立，则其对偶定理必定成立。如果能证明原定理成立，则其对偶定理必定成立。对偶式对偶式设在设在任一布尔表达式中，如果把其中的任一布尔表达式中，如果把其中的并与交（即并与交（即与与）互换，空集与全集（即互换，空集与全集（即与与 I）互互换，补（换，补（“”）不变所得到新不变所得到新的的表达式，就叫做表达式，就叫做原表原表达式的对偶式。达式的对偶式。上上述述集集合合代代数数的的6 6个个基基本本规规律律和和布布尔尔代代数数的的7 7个个基基本本定定理理（除除双双补补律律外外因因为为双双补补律律只只有有1 1个个式式子子），它它们们的的式和式和式，或式，或式和式和式都是对偶定理。式都是对偶定理。19例例1：写出下列布尔表达式的对偶式：写出下列布尔表达式的对偶式。注意：布尔代数的运算时也应注意：布尔代数的运算时也应先先后后运算运算，（即先乘除后加减）（即先乘除后加减）。解：解：将上式中的将上式中的（式中省略（式中省略“”标注），标注），和补和补“”不变，得上式的对偶式为：不变，得上式的对偶式为：20 AAB AB A（AB）=AB ABACCB =ABAC例如分析覆盖律的例如分析覆盖律的式式与与式式式，式，式与式与式式 （A AB）(AC）(CB）=（AB）(A AC）由上分析可得由上分析可得式与式式与式式，式，式与式与式的左右均式的左右均为对偶式，故其两两互为原定理和对偶定理。为对偶式，故其两两互为原定理和对偶定理。返回返回121二、容斥原理二、容斥原理 容容斥斥原原理理是是集集合合数数学学中中的的一一个个基基本本概概念念。在在生生活活和和工工作作中中有许多问题可以用容斥原理得到正确的解决。有许多问题可以用容斥原理得到正确的解决。(我们希望能用下式求出产品的失效概率我们希望能用下式求出产品的失效概率)设一产品失效事件为设一产品失效事件为M，形成其的事件由形成其的事件由A、B、C组成组成。则这产品失效的概率为：则这产品失效的概率为：因为可靠性主要是研究产品失效或可靠的概率，而产品因为可靠性主要是研究产品失效或可靠的概率，而产品失效或可靠是由於组成该产品的某些零部件失效或可靠这些失效或可靠是由於组成该产品的某些零部件失效或可靠这些事件形成的。事件形成的。22 若己知若己知P(A)、P(B)、P(C)，则，则 A、B、C事件和的概率等事件和的概率等于于A、B、C事件概率的和事件概率的和,即即 上面等式成立吗？不一定，根据概率论理论，只有当上面等式成立吗？不一定，根据概率论理论，只有当A、B、C互斥互斥（即不相容）时，上式才能成立。（即不相容）时，上式才能成立。当当A、B、C事件事件相容时，相容时，如何求如何求P（M）？下面举例说明。下面举例说明。23 例如某研究室订人民日报有例如某研究室订人民日报有2人，订北京日报人，订北京日报2人，订参考消息人，订参考消息5人，订广播电视人，订广播电视3人。同时又知有人。同时又知有1人订了人订了2种报，有种报，有3人订了人订了3种报。请确定该单位有多少人订报种报。请确定该单位有多少人订报？N=(2+2+5+3)-(12+33)+(1+3)=5（人）（人）上式中第一项为订报数，第一项减第二项是只订一份报上式中第一项为订报数，第一项减第二项是只订一份报的人数，而第三项是订多种报的人数。的人数，而第三项是订多种报的人数。解：解：经分析订报人数为：经分析订报人数为：24 为了方便地解决这类问题，这里介绍为了方便地解决这类问题，这里介绍容斥原理容斥原理的计算的计算公式。公式。设该研究室甲、乙、丙、丁、戊设该研究室甲、乙、丙、丁、戊5人订报。其情况人订报。其情况如表如表2-2所示。所示。由此例可见，相容事件的算法，通俗地说，是一种由此例可见，相容事件的算法，通俗地说，是一种“加加减减加加减减”、逐项逼近的算法。、逐项逼近的算法。戊戊丁丁丙丙乙乙甲甲订报人订报人广播电视报广播电视报参考消息参考消息北京日报北京日报人民日报人民日报表表2-2 某研究室人员的订报情况某研究室人员的订报情况25 1.集合相容和不相容集合相容和不相容 集集合合相相容容:若若集集合合A与与集集合合B有有公公共共元元素素，则则称称为为A和和B相容相容，或称为，或称为相交相交，如图，如图212所示。所示。图图2-12A集与集与B集相交的文氏图集相交的文氏图图图2-13A集与集与B集不相交的文氏图集不相交的文氏图 集集合合不不相相容容:若若集集合合A与与集集合合B没没有有公公共共元元素素，则则称称为为A和和B不相容不相容，或称为，或称为不相交不相交，如图，如图213所示。所示。A、B公共元素公共元素262.容斥原理计算公式容斥原理计算公式 式（式（21）中符号）中符号|A|表示集合表示集合A内的元素数目，（假设内的元素数目，（假设它是可数的、有限的），或表示文氏图中集合它是可数的、有限的），或表示文氏图中集合A的的“面积面积”（假设其元素是不可数的）。（假设其元素是不可数的）。2728下面举例说明以上容斥原理计算公式的应用。下面举例说明以上容斥原理计算公式的应用。例例21 求并事件求并事件ABC 的发生概率。的发生概率。解：设A=x1，B=x2，C=x3。29 因为设因为设A=x1，B=x2，C=x3,所以所以ABC 的的并事件并事件发生概率为发生概率为 30 例例22 求求1、2、500中能被中能被3或被或被5除尽的数的个数。除尽的数的个数。解：设解：设 A1为为1500中能被中能被 3 除尽的数的集合，除尽的数的集合，A2为为1500中能被中能被 5 除尽的数的集合。除尽的数的集合。由式（由式（21）得能被）得能被3或或5除尽的数的集合个数计算式为除尽的数的集合个数计算式为 31故有故有1500中能被中能被 3 或或 5 除尽的数的个数为除尽的数的个数为 因为因为1500中能被中能被3除尽的数的个数：除尽的数的个数：能被能被5除尽的数的个数：除尽的数的个数：同时被同时被3和和5除尽的数的个数：除尽的数的个数：32 由以上两个例子可见，用式（由以上两个例子可见，用式（2-1）和式（）和式（2-2）计算相）计算相交集合的并集元素数目（或文氏图面积）及相交事件的发生交集合的并集元素数目（或文氏图面积）及相交事件的发生概率比较繁琐复杂。概率比较繁琐复杂。若集合或事件不相交（不相容），则计算就简单多了。若集合或事件不相交（不相容），则计算就简单多了。对式（对式（2-1）可为）可为对式（对式（2-2）可为）可为 为此，把为此，把相交集合的运算等效地转换成不相交集合的运相交集合的运算等效地转换成不相交集合的运算算，下面介绍一些不交型算法的常用基本公式。，下面介绍一些不交型算法的常用基本公式。返回返回1331.1.不交型布尔代数及其运算规则不交型布尔代数及其运算规则 三、不交型算法三、不交型算法 “不交并不交并”（即（即“逻辑不交和逻辑不交和”）运算）运算“”是指首先是指首先把输入变量（如欲计算的集合）把输入变量（如欲计算的集合）不交化处理不交化处理后再进行布尔代数后再进行布尔代数的的“并并”运算运算“”的一种运算方法。的一种运算方法。如如A、B为相交的两个集合，它们的并为相交的两个集合，它们的并AB=BA文氏文氏图见图图见图2-14(a)。而它们的而它们的不交并不交并A B=AA AB B 和和B A B A=B BBA BA 的文氏图见图的文氏图见图2-142-14（b b）和（）和（c c）所示。）所示。+图图2-14 A B，B A 的文氏图的文氏图(b)(c)图图2-14 AB 的文氏图的文氏图(a)+34图2-14 A、B合的并与不交并并与不交并文氏图文氏图 从图从图2-14中可以明显地看出，虽然中可以明显地看出，虽然AB=A B，但等号，但等号左边是由两个相交的集合（左边是由两个相交的集合（A和和B）进行并计算而得，而等号进行并计算而得，而等号右边是由两个不相交的集合（右边是由两个不相交的集合（A和和AB）进行并计算而得，进行并计算而得，BA=B A 的情况同样也是这样。的情况同样也是这样。+35 因为可靠性计算是概率计算，故人们希望使用变量的不交因为可靠性计算是概率计算，故人们希望使用变量的不交并来进行概率计算。并来进行概率计算。(1)不交并的计算式不交并的计算式 +(2)不交型的基本规律及定理不交型的基本规律及定理 +交换律交换律 A B=B A ,A B=B A+A（BC）=（AB）C 结合律结合律 A （B C）=（A B）C+36 分配律分配律 A(B C)=AB AC A (BC)=(A B)(A C)+吸收律吸收律 A AB=A,A(A B)=A+对偶性定理对偶性定理 基元律基元律 0 A=A ,1 A=A 1 A=1 ,0 A=0 +补元律补元律 A A=1 ,AA=0 +对偶定理对偶定理可以证明不交型布尔代数的任何一个定可以证明不交型布尔代数的任何一个定理的对偶式仍是一条定理，叫做理的对偶式仍是一条定理，叫做原定理的对偶定理原定理的对偶定理。对偶式对偶式在不交型布尔代数中，把在不交型布尔代数中，把 “”和和“”互换，互换，“0”和和“1”互换，互换，“”运算不变，则得运算不变，则得对偶对偶式式。+37 不交型德摩根不交型德摩根(DeMorgan)定理定理 如如果果能能证证明明原原定定理理成成立立，则则其其对对偶偶定定理理必必定定成成立立。可可以以看看出出以以上上6个个基基本本规规律律中中的的1、2式式和和3、4式式均均互互为为原定理和对偶定理。原定理和对偶定理。例如：例如：+交换律交换律 A B=B A A B=B A+(A B)=A B (AB)=A B+382.直接不交化算法直接不交化算法 这里只介绍直接不交化计算的不交型这里只介绍直接不交化计算的不交型 DeMorgan定理。定理。根据式（根据式（23）可得：）可得：+故有故有39根据对偶定理，可得：根据对偶定理，可得：根据式（根据式（23），上式可得：），上式可得：+故有故有40 以上推导出的式（以上推导出的式（24）和式（）和式（25）即是直接不）即是直接不交化计算的交化计算的不交型不交型De Morgan定理定理。如设变量如设变量 A、B，则有，则有也可推导出也可推导出413.不交型积之和定理不交型积之和定理例如根据式（例如根据式（2-4）和分配律可得）和分配律可得：42（3）由定理）由定理2可以得到以下两个推论：可以得到以下两个推论：4344 推论 2：若 均和 无共同元素，且 则 （28）例如：返回返回145例例 1 设某产品的失效密度函数为：设某产品的失效密度函数为：求：该产品的可靠度求：该产品的可靠度R(t)和失效率和失效率(t)。解解：(1)可靠度可靠度R(t)【=1-累积失效概率函数累积失效概率函数F(t)】(2)失效率失效率(t)46 例例2 如某一个电网系统有下列四种情况引起电网失效：如某一个电网系统有下列四种情况引起电网失效：解：根据概率理论，电网失效解：根据概率理论，电网失效T为为1 2 1和和2同时失效同时失效；1 3 1和和3同时失效同时失效；2 3 2和和3同时失效；同时失效；3 4 5 3、4和和5同时失效。同时失效。47 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End谢谢大家荣幸这一路，与你同行ItS An Honor To Walk With You All The Way演讲人：XXXXXX 时 间：XX年XX月XX日