<4D F736F F F696E74202D203034B5DAB6FED5C2CFB5CDB3BFC9BFBFD0D4C4A3D0CD30322E707074>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D203034B5DAB6FED5C2CFB5CDB3BFC9BFBFD0D4C4A3D0CD30322E707074>"

速臧
7 years ago
Views:

1 1 第二章系统可靠性模型内容提要 - 集合代数布尔代数容斥原理及不交型算法一布尔代数二容斥原理三不交型算法

2 - 集合代数布尔代数容斥原理及不交型算法 1847 年英国数学家布尔发表了逻辑的数学分析,1854 年又发表了思维的规律, 这是把逻辑数学化的一次成功的尝试因此至今人们仍把逻辑代数称之为布尔代数一布尔代数由於产品失效或成功是由零部件失效或成功的集合形成的, 所以研究产品失效, 首先应研究集合的运算

3 1. 集合的并交补运算为直观起见, 用文氏图表示 3 (1) 集合的并仍为集合, 图 -7(a), 阴影集合 C=A B, 集合 C 为集合 A 和 B 的并, 或 C 为 A 和 B 的和, 符号为, 可称并, 也可称加, 中文表示或的意思 ( 即 A 和 B 至少发生一个 ) 图 -7 集合的并

4 () 集合的交仍为集合, 图 -7(b), 阴影集合 C=A B, 集合 C 为集合 A 和 B 的交, 或 C 为 A 和 B 的积, 符号, 可称交, 也可称乘, 中文表示与且的意思 ( 即 A 和 B 必须同时发生 ) 4 图 -7 集合的交

5 (3) 集合的补也是集合图 -7(c), 阴影集合, 集合 C 为集合 B 的补, 或 C 为 B 的对立集合, ' 符号, C = B = B 也可 -, 可称补, 也可称非, 中文表示不是之意 5 图 -7 集合的补

6 集合代数的基本规律 6 设 A B C 3 个集合,Φ 为空集,I 为全集 (1) 交换律 A B=B A A B=B A [(A+B=B+A)] [(AB=BA)] () 结合律 (A B) C = A (B C) [(A+B)+C = A+(B+C)] (A B) C=A (B C) [(A B) C = A (B C)]

7 (3) 分配律 7 A (B C)=(A B) (A C) [A(B+C)= AB+AC] 其文氏图见图 8 所示

8 A (B C)=(A B) (A C) 8 其文氏图见图 9 所示

9 (4) 吸收律 9 A (A B)=A [(A+AB)= A ] A (A B)=A [(A(A+B)= A)] 其文氏图见图 10 所示

10 (5) 基元律 10 Φ A = A, I A = I Φ A = Φ, I A = A Φ : 空集, 不可能事件, 无元素的集合 I: 全集, 必然事件, 一切可能元素的集合 (6) 补元律 AU A = I AI A = Φ

11 3. 布尔代数的有关基本定理 : 11 在数学系统中, 如果变量只能取 0 或 1( 失效或不失效 ), 上述定义的并交补, 且满足以上 6 条基本规律, 该系统叫布尔代数, 叫布尔运算交这算符号可简化为., 且 A B=A B=AB 书中讲了七个定理 : 基元互补律双补律德摩根定律等幂律复盖律, 归并律和对偶性定理

12 (1) 基元互补律 1 φ = I I = φ 1' = 0 0' = 1

13 () 双补律 13 ( A ')' = A (3) 等幂律 A U A = A A I A = A

14 (4)Demorgan 律 14 ( A U B) = A B 图

15 15 ( A B) = A U B 图

16 (5) 覆盖律 16 A A B=A B, 覆盖律文氏图见下图图

17 A(A B)= AB; 覆盖律文氏图见下图所示 17 图

18 AB A C CB = AB A C 18 覆盖律文氏图见下图所示图

19 (A B)(A C)(C B) = (A B)(A C) 19 覆盖律文氏图见下图所示图

20 (6) 归并律 AB U AB = A, 0 ( A U B)( AU B ) = A 11

21 (7) 对偶性定理 1 布尔代数任何一个定理的对偶式都成立, 并是一条定理, 称原定理的对偶定理对偶式任一布尔表达式, 如果把其中的与互换,Φ 与 I 互换, ˊ 不变所得的新表达式叫做原表达式的对偶式例 1: 写出下列布尔表达式的对偶式 AB [ CD U AB( AU BC )]I 对偶式为 : A U B U ( C U D)( A U B) U A( B U C ) { [ ]} 注意 : 布尔代数式也应先后运算, ( 即先乘除后加减 )

22 二容斥原理容斥原理是集合数学中的一个基本概念因为可靠性中主要是研究产品失效或可靠的概率, 而产品失效或可靠是由於组成该产品的某些零部件失效或可靠这些事件形成的设一产品失效事件为 M, 形成其的事件为 A B C 则这产品失效的概率为: 我们希望能用下式求出产品的失效概率 : P( M ) = P( AU B U C) = P( A) + P( B) + P( C)

23 3 若己知 : P( A), P( B), P( C) A B C 事件和的概率等于 A B C 事件概率的和 ) 上面等式成立吗? 不一定, 根据概率论理论, 只有当 A B C 互斥 ( 即不相容 ) 时, 上式才能成立

24 当 A B C 相容时,P(M) 如何求? 4 例如某单位订人民日报有人, 订北京日报人, 订参考消息 5 人, 订广播电视 3 人同时又知有 1 人订了种报, 有 3 人订了 3 种报请确定该单位有多少人订报? 经分析订报人数为 : N=(++5+3)-(1 +3 3) + (1+3)=5 上式中第一项为订报数, 第一项减第二项是只订一份报的人数, 而第三项是订多种报的人数

25 设该单位甲乙丙丁戊 5 人订报其情况如表 - 所示 5 由此可见, 相容事件的算法是 : 加加减减, 逐项逼近的算法为了方便地解决这类问题, 这里我们介绍容斥原理公式

26 1. 集合相容和不相容 6 集合 A 与集合 B 有公共元素, 则称为 A 和 B 相容, 或称为相交, 如图 1 所示 1

27 若集合 A 与集合 B 没有公共元素, 则称为 A 和 B 互不相容, 或称为不相交, 如图 13 所示 7 13

28 . 容斥原理公式设有 n 个任意集合 A, A, L, An 1, 纳法可以证得容斥原理公式如下 :, 用数学归 8 A 1 U A... U A n = n i= 1 A i 1 i< j n A A i j + A A i 1 i< j< k n j A k... ± A A... A 1 n n = ( 1) i 1 A A... A j1 j j i i= 1 1 j < j <... < j n 1 i ( 1)

29 式 ( 1) 中符号 A 表示集合 A 内的元素数目,( 假设它是可数的有限的 ), 或表示文氏图中集合 A 的面积 ( 假设其元素是不可数的 ) 同理可以证明任意事件发生的概率为 : M1, M, L, Mn 的并事件 9 P r n ( 1) i 1 P ( r i= 1 1 j < j <... j n ( M U M U... U M 1 n = M j 1 i (-) M... M ) 1 j j i

30 下面举例说明以上容斥原理公式的应用 30 例 1 求并事件 A B C 的发生概率解 : 设 A=M 1,B=M,C=M 3 由式 ( ) 得 : P ( M r 1 U M M U M 3 ) = 3 ( ) i 1 1 Pr i= 1 1 j < j < j 3 [ P M P M P M ] = ( 1) ( ) + ( ) + ( ) + ( 1) 11 1 r 1 r r 3 [ ] 31 P( MM) + P( MM) + P( MM) + ( 1) [ P( MMM) ] r 1 r 1 3 r 3 r ( M M 1 M 3 )

31 31 P r ( M U M U M 3) 1 = P ( M ) + P( M ) + P( M ) P( M M ) r 1 r r 3 r 1 P ( MM) P( MM) + P( MMM) r 1 3 r 3 r 1 3 故并事件 AUBUC 的发生概率为 P( AUBUC) = P( A) + P( B) + P( C) r r r r P ( AB) P ( AC) P ( BC) + P ( ABC) r r r r

32 例求 1,,,500 中能被 3 或 5 除尽的数的个数解 : 设 A 1 为 1~500 中能被 3 除尽的数的集合,A 为 1~500 中能被 5 除尽的数的集合由式 ( 1) 得能被 3 或 5 除尽的数的集合个数为 : 1 1 ( 1) i U = j1 j i 1 1 j1< j ( 1) 11 A A ( 1) 1 AA 1 1 A A A A = = A + A A A 1 1

33 因为 1~500 中能被 3 除尽的数的个数 : 33 A 1 = 500 /3 = 166 能被 5 除尽的数的个数 : A = 500 / 5 = 100 同时被 3 和 5 除尽的数的个数 : AA 1 = 500 /(3 5) = 33 故有 1~500 中能被 3 或 5 除尽的数的个数 : AUA = A+ A AA = =

34 由此可见, 运用以上两式计算集合并不太方便为此, 下面介绍不交型算法 34 三不交型算法 1. 不交型布尔代数及其运算规则不交并 ( 即逻辑不交和 ) 运算, 是首先把输入变量 ( 如欲计算的集合 ) 不交化处理后再进行布尔代数的并运算的一种运算方法 U 如 A B 为相交的两个集合, 它们的并

35 A B = B A 文氏图见图 -14(a) 35 而它们的不交并 B U (b) (c) 图 A,B 合的并与不交并 A A= B B A U B= A A B 和的文氏图见图 -14

36 从图中可以明显地看出, 虽 A B = A B 然, 但等号左边是由两个相交的集合 (A 和 B) 进行并计算而得, 而等号右边是由两个不相交的集合 (A 和 A B) B A 进行并计算而得 = B UA, 的情况同样也是这样 U 36 因为可靠性计算是概率计算, 故人们希望使用变量的不交并来进行概率计算设变量为计算为 : M1, M, L, Mn, 则它们的不交并

37 M 1 U M UU U M n = 37 M 1 M 1 M M 1 M M 3 M 1 M M n-1 M n = M1+ MM 1' + MMM 1' ' 3+ L+ MM 1' ' L+ M' n 1M n ( 3) 同上述的集合代数及布尔代数一样, 不交型布尔代数也有以下基本规律及定理 (1) 交换律 AU B= BU A, AB = BA ;

38 U U U U () 结合律 A (B C) = (A B) C A (BC) = (AB) C ; 38 (3) 分配律 A(B C) = AB AC U U U U U A (BC) = (A B) (A C) (4) 吸收律 AU AB= A, A(AU B) = A U U (5) 基元律 0 A = A, 1 A = A 1 A = 1, 0 A = 0 ; (6) 补元律 AU A = 1, A A = 0 ;

39 (7) 对偶性定理在不交型布尔代数中, 39 把 U 和互换, 0 和 1 互换, ˊ 运算不变, 则得对偶式可以证明不交型布尔代数的任何一个定理的对偶式仍是一条定理, 叫做原定理的对偶定理如果能证明原定理成立, 则其对偶定理必定成立可以看出以上 6 个基本规律中的 1 式和 3 4 式均互为原定理和对偶定理 (8) 不交型 DeMorgan 定理 U (A B) = A U B (A B) = A B,

40 . 直接不交化算法 40 这里只介绍直接不交化计算的不交型 DeMorgan 定理设变量为 x1, x, L, x n, 根据不交型 DeMorgan 定理可得 : (x 1 x x n ) = x 1 x x n U U U 根据式 ( 3) 可得 : x 1 U x U U x n = x + x x + x x x + + x x x x n 1 n

41 故有 41 ( x xlx) = x + xx + xxx + L+ xxxlx x 1 n n 1 n ( 4) 根据对偶定理, 可得 : (x 1 x x n ) = x 1 x x n U U U 根据式 ( 3), 上式可得 : (x 1 x x n ) U U U = (x 1 +x 1 x +x 1 x x 3 + +x 1 x x 3 x n-1 x n )

42 故有 4 ( x x x + x x x + + x x x x ) = n 1 x x 1 x n ( 5) 以上推导出的式 ( 4) 和式 ( 5) 即是直接不交化计算的不交型 De Morgan 定理例如由式 (-4) 和式 (-5) 可得 A B 变量 : A +AB = A +A(B ) = (AB ) n

43 3. 不交型积之和定理 43 设布尔积 S i p = t = 1 x it xit si 其中为中的元素,t=1~p S, S ' i j 定理 1: 若 i j如不包含共同元素, 则 S S 可用不交型运算规则直接展开例如根据式 ( 4) 和分配律可得 : ( BC) AF = ( B + BC ) AF = B AF + BC AF

44 定理 : 若 SS, i j 包含一些共同元素, 则 44 S' S S' S S = ( 6) i j i j j Si 式中 i j 具有而 j 没有的元素的布尔积例如 : S ( ABC)' AE = ( BC)' AE

45 由定理可以得到以下两个推论 : 推论 1: 若 S1, S, L, Sn 都和包含一些共同的元素, 则 S k 45 SS ' ' LS' S= S' S' L S' S ( 7) 1 n k 1 k k n k k S 式中 1 k 具有的而没有的元素的布尔 k 积 S ; S 具有的而没有的元素的布尔积 ; n k M k S 1 例如 : ( ABC)'( BCE)' BC = A' E ' BC S S k S 具有的而没有的元素的布尔积 S n S k

46 推论 : 若 S 1, S, L, S n 均和 S k 无共同元素, 且 S1 S S1 S3 LS1 S n,,, 则 46 S ' S ' S' S = S ' S L ( 8) 1 n k 1 k 例如 : A'( ABC) '( ACE) ' GF = A' GF

47 47 例 1 设某产品的失效密度函数为 : f (t) = 0 t<0 0 t te t 求 : 该产品的可靠度 R(t) 和失效率 λ(t) 解 :(1) 可靠度 ) ( 1 ) ( 1 1 ) ( 1 ) ( t t t t t t t e e t d e dt te dt t f t R = + = + = = =

48 () 失效率 λ(t) 48 λ ( t ) = f R ( ( t t ) ) = te e t t = t

49 例如某一个电网系统有下列四种情况引起电网失效 : 1 1 和同时失效 ; 和 3 同时失效 ; 3 和 3 同时失效 ; 和 5 同时失效 ; 49 已知和 5 的失效概率分别为 q, q 3, q 4, q 5, 且相互独立求 : 电网失效概率解 : 根据概率理论, 电网失效 T 为 T =1 U13U3U345 q 1,

50 首先不交化处理 : 50 T = = 1+ (1)13 + (1) (13) 3(1) (13) (3) 345 = = P( T ) = + q q 1 )(1- (1- + (1 q 1 q q ) q q 1 ) q 3 3 q 4 + (1 q 注意 : 有时难于判断事件是否相容, 要作相容处理, 先不交化再做之 q 5 1 ) q q 3

51 51 中国可靠性网感谢 kingdodoo 分享

Ps22Pdf

Ps22Pdf A B C D A B C D A B C D a a b c x x x x x x x x x x x x x x x x x a b c x a x x x x x x x x x x a b a b a b x x x x x x x x x x x x A B C A B C A B A B A x B C x D A B C a b c a b x x x x x x x A B A