Switching-Algebraic Analysis of System Reliability

Abstract

This chapter deals with the paradigm of handling system reliability analysis in the Boolean domain as a supplement to (rather than a replacement to) analysis in the probability domain. This paradigm is well-established within the academic circles of reliability theory and engineering, albeit virtually unknown outside these circles. The chapter lists and explains arguments in favor of this paradigm for systems described by verbal statements, fault trees, block diagrams, and network graphs. This is followed by a detailed exposition of the pertinent concept of the Real or Probability Transform of a switching (two-valued Boolean) function, and that of a Probability-Ready Expression (PRE). Some of the important rules used in generating a PRE are presented, occasionally along with succinct proofs. These include rules to achieve disjointness (orthogonality) of ORed formulas, and to preserve statistical independence, as much as possible, among ANDed formulas. Recursive relations in the Boolean domain are also discussed, with an application to the four versions of the AR algorithm for evaluating the reliability and unreliability of the k-out-of-n:G and the k-out-of-n:F systems. These four versions of the algorithm are explained in terms of signal flow graphs that are compact, regular, and acyclic, in addition to being isomorphic to the Reduced Ordered Binary Decision Diagram (ROBDD). An appendix explains some important properties of the concept of Boolean quotient, whose expectation in Boolean-based probability is the counterpart of conditional probability in event-based probability.

1 Introduction

This chapter deals with the paradigm of handling system reliability analysis in the Boolean domain as a supplement to (rather than a replacement to) analysis in the probability domain. This paradigm is called switching-algebraic analysis of reliability or (two-valued) Boolean analysis of reliability. It is also termed Logical Probabilistic Analysis (LPA) by Ryabinin [1], who traced it back to great pioneers such as Boole, Poretskii, and Bernstein. Ryabinin also rebutted dubious criticism cast against LPA, and lamented that LPA is missing in prominent publications on probability theory, including those by celebrated scholars such as Markov and Kolmogorov. A modern revival of LPA was started in 1963 by Merekin [2] and Premo [3] and later in 1973 by Fratta and Montanari [4]. After that, applications of LPA in system reliability analysis were covered by literally hundreds of publications in prestigious journals (see, e.g., [5–62]). It is therefore astonishing that LPA has so far not found its way to popular texts on probability (see, e.g., [63–72]), and is still virtually unknown outside the circles of reliability theorists and engineers. This state of affairs is possibly an obstacle hindering fruitful interplay between system reliability and many of its potential fields of application. This chapter is, therefore, an attempt to review reliability applications of LPA and enhance awareness of the scientific community about it. It is also an invitation to explore its utility in other parts of probability theory that deal with generalized Bernoulli trials.

System reliability analysis deals with expressing the reliability of a system in terms of the reliabilities of its constituent components. Hence, this analysis entails advanced applications of probability theory, and is consequently “based on the algebra of events (a version of set algebra), which is isomorphic to the bivalent or 2-valued Boolean algebra (switching algebra)” [56]. Besides using the algebra of events in what is termed probabilistic or arithmetic analysis [73, 74], modern system reliability analysis also utilizes Boolean algebra by employing the indicator variables for probabilistic events instead of the events themselves. Subsequently, expectations of these indicator variables are used to represent probabilities of the corresponding events. In particular, expectations of system success and failure replace system reliability and unreliability, respectively.

An approach bearing certain similarities to the paradigm exposed herein (without going to the Boolean domain) studies probability via expectations [65]. It is based on an axiomatization of probability theory using expectations instead of probabilities (i.e., using linear operators instead of measures). A related approach is suggested by Feller [63, p. 219] who states that “The reduction of probability theory to random variables is a short-cut to the use of analysis and simplifies the theory in many ways. However, it also has the drawback of obscuring the probability background.” The paradigm exposed herein handles probability in terms of indicator random Bernoulli variables, but it does not obscure the probability background, since it stresses that the random variables are indicators for events, and it keeps two parallel schemes of event-based probability and Boolean-based probability. These schemes are compared in Table 1 which cites well-known results from elementary probability theory. The first scheme utilizes the concepts of probabilities of events, union and intersection operators, and conditional probability, while the second scheme replaces these by expectations of event indicators, logical “OR” and “AND” operators, and Boolean quotient (see Appendix A). Table 1 shows how probability formulas involving the union and intersection operators become simpler when the pertinent events are mutually exclusive or statistically independent, respectively. As indicated in Table 2, the indicator variable $I_{A}$ is a Bernoulli variable of two values 0 and 1, such that

Table 1 Comparison of event-based and boolean-based probability relations

Table 2 Indicator variable for set complementation

$$ I_{A} = 0\quad {\text{iff}}\,{\text{the}}\,{\text{event}} \, A \,{\text{does}}\,{\text{not}}\,{\text{occur}}, $$

(1a)

$$ I_{A} = 1\quad {\text{iff}}\,{\text{the}}\,{\text{event}} \, A \,{\text{occurs}}. $$

(1b)

Table 2 also indicates definitions of the Bernoulli variables $\overline{{I_{A} }},$ $I_{A} \vee I_{B},$ $I_{A} \wedge I_{B},$ so that the following expectations are obtained

$$ E\{ I_{A} \} = Pr \{ A\} , $$

(2a)

$$ E\left\{ {\overline{{I_{A} }} } \right\} = Pr \{ \bar{A}\} , $$

(2b)

$$ E\left\{ {I_{A} \vee I_{B} } \right\} = {Pr}\{ \bar{A} \cap B\} + {Pr}\{ A \cap \bar{B}\} + {Pr}\{ A \cap B\} = {Pr}\{ A \cup B\} , $$

(2c)

$$ E\{ I_{A} \wedge I_{B} \} = {Pr}\{ A \cap B\} . $$

(2d)

In the sequel, we will use the symbols S and $\bar{S}$ to denote system success and failure, respectively, with their expectations $R = E\{ S\}$ and $U = E\{ \bar{S}\}$ representing system reliability and unreliability, respectively. Subscripts of obvious meanings will be added to distinguish systems of particular types. The corresponding symbols $X_{i},$ $\bar{X}_{i}$, $p_{i} = E\{ X_{i} \} ,$ and $q_{i} = E\{ \bar{X}_{i} \}$ will denote the success, failure, reliability, and unreliability, respectively, for component of number $i, 1 \le i \le n.$ Unless otherwise stated, component successes are assumed statistically independent all throughout this chapter. A Boolean expression for the indicator of system success will be presented as a function of the indicators of component successes. Transition from the Boolean domain to the probability domain is achieved via the Real Transform [75–82] which can be viewed as an expression of system reliability (unreliability) as a function of component reliabilities (unreliabilities).

The organization of the rest of this chapter is as follows. Section 2 lists arguments for handling system reliability in the Boolean domain before going to the probability domain. Section 3 reviews the basic concepts of the Real or Probability Transform of a switching function. Section 4 presents the definition of a Probability-Ready Expression (PRE) and lists some of the rules used in generating a PRE. Section 5 discusses recursive relations in the Boolean domain. Section 6 concludes the chapter (Table 3).

Table 3 Indicator variables for set union and intersection

2 Advantages of Working in the Switching (Boolean) Domain

There is a large potpourri of ways for describing a reliability system, including verbal statements, fault trees, block diagrams, and network graphs. Generally, reliability analysis of a system conducted in the probabilistic (arithmetic) domain is lengthy and error-prone [73, 74]. We will now discuss other arguments for working in the switching (Boolean) domain for each specific type of system description:

• For systems described by verbal statements, work in the Boolean domain allows a separation and distinction between the mathematical formalization of a reliability problem, and the algorithmic derivation of its formal solution. Table 4 shows the verbal description versus the Boolean specification of some common reliability systems, mostly of the k-out-of-n or related types. For lack of space, we omitted more sophisticated systems including some dual, multidimensional, multi-valued extensions of the reported systems. It is clear that the word statement and the mathematical description of each reported system are immediately and obviously equivalent. There is no mental strain or conceptual difficulty in going from the somewhat vague realm of language to the exactly precise arena of mathematics. The primary Boolean description is in terms of system success or failure, depending on the nature of the system, with the complementary description delegated to a secondary role. Once in the Boolean domain, one can solve the problem of reliability evaluation by utilizing an extensive set of algorithmic tools and visual aids. For most of the systems in Table 4, both probabilistic and Boolean solutions exist. For some of the systems, such as the k-out-of-n systems, Boolean solutions [27] were earlier to develop. For other systems, such as the consecutive-k-out-of-n ones, Boolean solutions [32, 33] arrived later, as an afterthought, to provide a more insightful and easy-to-comprehend alternative.

  Table 4 Boolean specification of some common reliability systems

• Formulation of a system reliability problem in the Boolean domain is the natural strategy to use for systems described by fault trees [9, 10, 44, 49, 50, 58], which are composed of logical AND–OR gates, and can similarly be utilized with systems described by block diagrams [15]. Fault trees are used to relate probabilistic events, with its inputs being basic events and its output being the top event. However, it could be more convenient to apply Boolean-based probability to fault trees by using indicators for events rather the events themselves [57, 62, 78, 92].

• Formulation in the Boolean domain is the method of choice with systems described by network graphs when these systems are handled through the enumeration of minimal pathsets and minimal cutsets [12, 23, 26, 48], rather than other graph techniques.

Work in the Boolean domain might allow the treatment of certain types of statistical dependencies among component successes. For example, in the case of total positive dependency ($X_{i} = X_{j}$) idempotency leads to ($X_{i} \vee X_{j} = X_{i}$) and ($X_{i} \wedge X_{j} = X_{i}$), while in the case of total negative dependency ($X_{i} = \bar{X}_{j}$) orthogonality leads to ($X_{i} \vee X_{j} = 1$) and ($X_{i} \wedge X_{j} = 0$). Cases of partial dependencies might be handled via expectations of Boolean quotients.

Work in the Boolean domain also provides the insight necessary to avoid traps and pitfalls, as well as to detect anomalies, inconsistencies, and errors of the third kind (errors of solving the wrong problem). A case in point is that of the so-called strict consecutive-k-out-of-n:G(F) system [93–96], which lacks a definition that avoids ambiguity, inconsistency, or self-contradiction. Unfortunately, many capable and great mathematicians wasted their precious time producing elegant solutions for what they mistakenly assumed to be this system. Insight of the Boolean domain allowed a critical review of literature that partially prevented the publication of more such irrelevant work.

Without resort to the Boolean domain, one might be obliged to use the notorious Inclusion–Exclusion (IE) Principle to compute the probability of the union of n events [63, 67], where n might be large. Use of the IE Principle in system reliability analysis is undesirable, since “(a) it produces an exponential number of terms that have to be reduced subsequently via addition and cancellation, and (b) it involves too many subtractions, making it highly sensitive to round-off errors, and possibly leading to catastrophic cancellations” [52, 54, 56].

3 The Real Transform of a Switching Function

Various forms of the Real Transform (also called the Probability or Arithmetic transform) are discussed in [75–82]. The definition given in [79, 82] states that the real transform $R(\varvec{p}) = R(p_{1} ,p_{2} , \ldots ,p_{n} )$ of a switching function f(X) possesses the following two properties:

• (a) R(p) is a multiaffine continuous real function of continuous real variables $\varvec{p} = [p_{1} \,p_{2} \ldots p_{n} ]^{\text{T}} ,$ i.e., R(p) is a first-degree polynomial in each of its arguments $p_{i}.$

• (b) R(p) has the same “truth table” as f(X), i.e.

  $$ R\left( {\varvec{p} = \varvec{t}_{j} } \right) = f(\varvec{X} = \varvec{t}_{j} ),\quad {\text{for}}\,{j} = 0, 1, \ldots ,\left( {2^{n} - 1} \right), $$

  (3)

  where t _j is the jth input line of the truth table; t _j is an n-vector of binary components such that

  $$ \sum\limits_{i = 1}^{n} {} {2}^{{{n}-{i}}} {t}_{ji} = {j}, \quad {\text{for}}\,{j} = 0,{1}, \ldots ,\left( {2^{n} -{1}} \right). $$

  (4)

We stress that property (b) above does not suffice to produce a unique $R(\varvec{p})$ and it must be supplemented by the requirement that $R(\varvec{p})$ be multiaffine to define $R(\varvec{p})$ uniquely [77, 79]. We also note that if the Real Transform R and its arguments p are restricted to discrete binary values (i.e., if $R:\left\{ {0,1} \right\}^{n} \to \{ 0,1\}$) then R becomes the multilinear form of a switching function [11, 97]. This form is typically referred to as the structure function [98, 99] in system reliability, and is a way to mimic Boolean algebra in terms of arithmetic operators rather than Boolean ones.

The definition above for $R(\varvec{p})$ implies that it is a function from the n-dimensional real space to the real line $(R(\varvec{p}):\varvec{R}^{n} \to \varvec{R}).$ Though both R and p could be free real values, they have very interesting interpretations as probabilities, i.e., when restricted to the [0.0, 1.0] and [0.0, 1.0]ⁿ real intervals. An important property of the Real Transform R(p) is that if its vector argument or input p is restricted to the domain within the n-dimensional interval [0.0, 1.0 ]ⁿ, i.e., if 0.0 ≤ p _i  ≤ 1.0 for 1 ≤ i ≤ n, then the image of R(p) will be restricted to the unit real interval [0.0, 1.0].

The Real Transform is a bijective (one-to-one and onto) mapping from the set of switching functions to the subset of multiaffine functions such that if the function’s domain is the power binary set $\{ 0, 1\}^{n}$ then its image belongs to the binary set {0, 1}. Evidently, an R(p) restricted to binary values whenever its arguments are restricted to binary values can produce the “truth table” that completely specifies its inverse image f(X) via (3). On the other hand, a multiaffine function of n variables is completely specified by $2^{n}$ independent conditions [77, 79], e.g., the ones in (3).

The transform $R(\varvec{p})$ is related to the original function $f(\varvec{X})$ via the truth table in (3), which consists of 2ⁿ lines. Therefore, the complexity of implementing the Real Transform, i.e., of going from $f(\varvec{X})$ to $R(\varvec{p})$ is exponential, and the problem of implementing the Real Transform is generally intractable. However, if $f(\varvec{X})$ is cast in PRE form, then it can be converted trivially (at no cost) to $R\left( \varvec{p} \right).$ In this case, the burden of achieving the Real Transform is shifted to the Boolean domain where the initial formula for $f(\varvec{X})$ is to be converted (at a potentially reduced cost) to a PRE.

4 Probability-Ready Expressions

A Reliability-Ready Expression (RRE) is an expression in the switching (Boolean) domain that can be directly transformed, on a one-to-one basis, to its Real or Probability Transform by replacing switching (Boolean) indicators by their statistical expectations, and also replacing logical multiplication and addition (ANDing and ORing) by their arithmetic counterparts [25, 42, 49, 50, 54, 56]. We now present some useful rules that might be required in the conversion of an arbitrary switching (Boolean) expression to an equivalent compact PRE:

• 1. A switching expression is a PRE expression if

  • (a) all ORed terms are orthogonal (disjoint), and

  • (b) all ANDed sums are statistically independent.

  The conversion is achieved by replacing Boolean variables by their expectations, AND operations by arithmetic multiplications, and OR operations by arithmetic additions. While there are literally hundreds of methods to introduce characteristic (a) of orthogonality (disjointness) into a Boolean expression (see, e.g., Bennetts [9, 15], Abrahams [13], Dotson and Gobien [14], and Rushdi [17, 20]) there is no way to induce characteristic (b) of statistical independence. The best that one can do is to observe statistical independence when it exists, and then take care to preserve it and take advantage of it [25, 42, 62].

• 2. As an analog to series-parallel reduction, any set of ANDed or ORed variables that do not appear elsewhere in a formula should be combined into a single variable. This might considerably reduce the number of variables involved, and helps in producing a more compact expression.

• 3. Two terms are disjoint if they have at least a single opposition, i.e., if there is at least one variable that appears complemented in one term and appears un-complemented in the other, e.g., the two terms $A\bar{B}C$ and $BC$ are disjoint since the complemented literal $\bar{B}$ appears in $A\bar{B}C$ while the un-complemented literal B appears in $BC$.

• 4. If neither of the two terms A and B in the sum $(A \vee B)$ subsumes the other ($A \vee B \ne A$ and $A \vee B \ne B$) and the two terms are not disjoint ($A \wedge B \ne 0$), then B can be disjointed with A by the relation

  $$ \begin{aligned} A \vee B & = A \vee B \left( {\overline{{y_{1} y_{2} \ldots y_{e} }} } \right) \\ & = A \vee B \left( {\overline{{y_{1} }} \vee y_{1} \overline{{y_{2} }} \vee \ldots \vee y_{1} y_{2} \ldots y_{e - 1} \overline{{y_{e} }} } \right), \\ \end{aligned} $$

  (5)

  where {$y_{1} ,y_{2} , \ldots ,y_{e}$} is the set of literals that appear in the term A and do not appear in the term B. Note that the term B is replaced by e (≥1) terms that are disjoint with one another besides being disjoint with the term A [9, 15, 54, 56]. Formula (5) might be seen as an immediate extension of the familiar Reflection Law [100–105].

  $$ a \vee b = a \vee (b \wedge \bar{a}). $$

  (5a)

A formal proof of (5) is possible via perfect induction over a much reduced truth table that consists of the ($e + 1$) orthonormal cases $\{ y_{1} = 0\},$ $\{ y_{1} = 1, y_{2} = 0\},$ $\{ y_{1} = y_{2} = 1, y_{3} = 0\}, \ldots ,$ $\{ y_{1} = y_{2} = \cdots = y_{e - 1} = 1, y_{e} = 0\},$ and $\{ y_{1} = y_{2} = \cdots = y_{e - 1} = y_{e} = 1\}$. For the first e cases, the L.H.S. = the R.H.S = B. For the last case, the L.H.S. = $A/y_{1} y_{2} \cdots y_{e} \vee B$, while the R.H.S. = $A/y_{1} y_{2} \cdots y_{e}.$ The two sides are equal since B subsumes $A/y_{1} y_{2} \cdots y_{e},$ and hence is absorbed in it. The term $(A/y_{1} y_{2} \cdots y_{e} )$ is the Boolean quotient obtained by restricting A through the assignment $\{ y_{1} = y_{2} = \cdots y_{e} = 1\}$ (See Appendix A). In passing, we note that the roles of A and B can be reversed in (5), and that (5) does not guarantee minimality of the resulting disjointed expression [51]. Disjointness typically results in an (often dramatic) increase in the number of terms in sum-of-products (sop) switching expressions. However, there are more sophisticated disjointness techniques that achieve “shellability”, i.e., they obtain a disjoint sop expression that retains the same number of terms as the original sop expression [34, 46, 55, 105]. Notable examples of shellable expressions include those of the success or failure of a k-out-of-n:G or a k-out-of-n:F system [39], and that of the success of a coherent threshold system [55].

• 5. Given a term P and two sums of products A and B where A has no variables in common with P, while B shares some variables with P, then the logical product $\left( {A \wedge B} \right)$ is disjointed with P by disjointing B and P and keeping A unchanged [42].

• 6. The complements of a sum and a product are given by a product and a disjoint sum, namely, PRE versions of De Morgan’s Laws [102]

$$ \overline{{{\vee }_{i = 1}^{n} A_{i} }} = {\wedge }_{i = 1}^{n} \bar{A}_{i} , $$

(6)

$$ \overline{{{\wedge }_{i = 1}^{n} A_{i} }} = \overline{{A_{1} }} \vee A_{1} \overline{{A_{2} }} \vee \cdots \vee A_{1} A_{2} \cdots A_{n - 1} \overline{{A_{n} }} . $$

(7)

A formal proof of (6) is achieved by considering just two exhaustive cases, namely: (a) the case of all $A_{i}$’s being 0, for which the L.H.S. = the R.H.S = 1, and (b) the case when at least one $A_{i}$ is 1, for which the L.H.S. = the R.H.S. = 0. Likewise, a formal proof of (7) is obtained via perfect induction over the ($n + 1$) orthonormal cases $\{ A_{1} = 0\},$ $\{ A_{1} = 1, A_{2} = 0\},$ $\{ A_{1} = A_{2} = 1, A_{3} = 0\}, \ldots,$ $\{ A_{1} = A_{2} = \ldots = A_{n - 1} = 1, A_{n} = 0\},$ and $\{ A_{1} = A_{2} = \ldots = A_{n - 1} = A_{n} = 1\}.$ For the first n cases, the L.H.S. = the R.H.S = 1. For the last case, the L.H.S. = the R.H.S. = 0.

• 7. The most effective way for converting a Boolean formula into a PRE form is the Boole–Shannon Expansion

$$ f(\varvec{X}) = (\bar{X}_{i} \wedge f\left( {\varvec{X} |0_{i} )} \right) \vee (X_{i} \wedge f\left( {{\mathbf{X}} |1_{i} } \right)), $$

(8)

which expresses a (two-valued) Boolean function $f(\varvec{X})$ in terms of its two subfunctions $f\left( {\varvec{X} |0_{i} } \right)$ and $f\left( {\varvec{X} |1_{i} } \right).$ These subfunctions are equal to the Boolean quotients $f(\varvec{X})/\bar{X}_{i}$ and $f\left( \varvec{X} \right)/X_{\text{i}},$ and hence are obtained by restricting ${X}_{i}$ in the expression $f(\varvec{X})$ to 0 and 1, respectively. If $f(\varvec{X})$ is a sop expression of n-variables, the two subfunctions $f\left( {\varvec{X} |0_{i} } \right)$ and $f\left( {\varvec{X} |1_{i} } \right)$ are functions of at most (n − 1) variables. A formal proof of (8) is achieved by considering just two exhaustive cases, namely: (a) the case {$X_{i} = 0$}, for which the L.H.S. = the R.H.S = $f\left( {\varvec{X} |0_{i} } \right),$ and (b) the case {$X_{i} = 1$}, for which the L.H.S. = the R.H.S. = $f\left( {\varvec{X} |1_{i} } \right)$. The expansion (8) serves our purpose very well. Once the subfunctions in (8) are expressed by PRE expressions, $f(\varvec{X})$ will be also in PRE form, thanks to the facts that (a) The R.H.S. of (8) has two disjoint parts, with the first part containing the complemented literal $\bar{X}_{i}$ and the second part containing the un-complemented literal ${\text{X}}_{i},$ and (b) Each of these two parts is a product of two statistically-independent entities. The Boole–Shannon Expansion in the Boolean domain is equivalent to the Total Probability Theorem [67] in the probability domain and to the Factoring Theorem [56] in the “Graph Domain”. A visual aid or tool to implement this expansion is provided by the Variable-Entered Karnaugh Map (VEKM) [17].

• 8. Let a success formula be written in the form

$$ S = N_{1} M_{1} \vee N_{2} M_{2} , $$

(9)

where the set of formulas {$N_{1} ,N_{2}$} is statistically independent of the set of formulas {$M_{1} ,M_{2}$}. Expression (9) might result due to path enumeration via network decomposition [22, 106–109]. A PRE formula of S (that preserves the original statistical independence as much as possible) is [22]

$$ S_{PRE} = N_{1(PRE)} M_{1(PRE)} \vee (\overline{{N_{1} }} N_{2} )_{(PRE)} M_{2(PRE)} \vee (N_{1} N_{2} )_{(PRE)} (\overline{{M_{1} }} M_{2} )_{(PRE)} . $$

(10)

A formal proof of (10) is possible via perfect induction over a much reduced truth table that consists of only the three orthonormal cases $\{ N_{1} = 0\},$ $\{ N_{1} = 1, M_{1} = 0\},$ and $\{ N_{1} = M_{1} = 1\}.$ For the first two cases, the L.H.S. = the R.H.S. = $N_{2(PRE)} M_{2(PRE)}.$ For the third case, the L.H.S. = the R.H.S = 1. Note that this proof entails a partitioning of the higher-level space of $N_{1}$ and $M_{1}$ rather than a partitioning of the space of the underlying arguments X.

• 9. Products might be kept compact by utilizing the following rules of disjoint intelligent multiplication

$$ (a \vee x)(a \vee y) = a \vee \bar{a}xy, $$

(11)

$$ (a \vee x)\left( {\bar{a} \vee y} \right) = \bar{a}x \vee ay. $$

(12)

Formula (11) results due to the absorption of the terms $ax$ and $ay$ in their subsumed term $a,$ and then using the Reflection Law (5a). The term $xy$ that would have appeared in formula (12) is deleted since it is the consensus of $\bar{a}x$ and $ay,$ and hence it is covered by their disjunction $\bar{a}x \vee ay.$ A corollary of (11) is

$$ \overline{ab} \wedge \overline{ac} \wedge \overline{ad} = \bar{a} \vee a\bar{b}\bar{c}\bar{d}. $$

(13)

The complemented form of (13) is a ANDed with the complement of $\bar{b}\bar{c}\bar{d}.$ This complemented form allows separating the common factor $a$ in the formula without introducing the OR ($\vee$) operator in it, and hence leads to full utilization of statistical independence [25].

• 10. When one has a partially-factored expression of system success or failure such as the following one [56]

$$ S = X_{3} \vee X_{7} \vee \left( {X_{5} \vee X_{8} } \right)\left( {X_{4} \vee X_{2} X_{9} } \right) \vee (X_{1} \vee X_{6} )(X_{2} \vee X_{4} X_{9} ), $$

(14)

then it should be converted into PRE form via (10) without spoiling or expanding the factored form, so as to preserve statistical independence [22, 25, 42, 56]

$$ \begin{aligned} S_{PRE} & = X_{3} \vee \overline{{X_{3} }} \left( {X_{7} \vee \overline{{X_{7} }} \left( {\left( {X_{5} \vee \overline{{X_{5} }} X_{8} } \right)\left( {X_{4} \vee \overline{{X_{4} }} X_{2} X_{9} } \right)} \right.} \right. \\ & \left. {\left. { \vee \left( {X_{1} \vee \overline{{X_{1} }} X_{6} } \right) \left( {\overline{{X_{5} }} \overline{{X_{8} }} \left( {X_{2} \vee \overline{{X_{2} }} X_{4} X_{9} } \right) \vee \left( {X_{5} \vee \overline{{X_{5} }} X_{8} } \right)X_{2} \overline{{X_{4} }} \overline{{X_{9} }} } \right)} \right)} \right). \\ \end{aligned} $$

(15)

This transforms on a one-to-one basis to the reliability expression [56]

$$ \begin{aligned} R & = p_{3} + q_{3} \left( {p_{7} + q_{7} \left( {\left( {p_{5} + q_{5} p_{8} } \right)\left( {p_{4} + q_{4} p_{2} p_{9} } \right)} \right.} \right. \\ & \quad \left. {\left. { + \left( {p_{1} + q_{1} p_{6} } \right)\left( {q_{5} q_{8} \left( {p_{2} + q_{2} p_{4} p_{9} } \right) + \left( {p_{5} + q_{5} p_{8} } \right)p_{2} q_{4} q_{9} } \right)} \right)} \right). \\ \end{aligned} $$

(16)

5 Recursive Relations in the Boolean Domain

This Section provides a novel discussion about the utility of the Boolean domain in deriving recursive relations for the two versions of the k-out-of-n system. The reader is referred to [32, 33] for Boolean-domain derivations of recursive relations for consecutive systems. The success $S_{G} (k, j,\varvec{X}_{j} )$ of a k-out-of-j:G system is a symmetric monotonically nondecreasing switching function, and hence satisfies recursive relations obeyed by such a function [27]. Equivalently, it is given by its Boole–Shannon expansion about its last argument $X_{j}$ (namely, Eq. (5.40a) of Rushdi [39]):

$$ S_{G} (k, j,\varvec{X}_{j} ) = \overline{{X_{j} }} S_{G} (k, j - 1,\varvec{X}_{j - 1} ) \vee X_{j} S_{G} (k - 1, j - 1,\varvec{X}_{j - 1} ),1 \le k \le j \le n, $$

(17a)

where $\varvec{X}_{j} = \left[ {X_{1} ,X_{2} , \ldots ,X_{j} } \right]^{\text{T}}$ is the vector of the first j component successes. The R.H.S. of Eq. (17a) involves two subfunctions $S_{G} (k, j - 1,\varvec{X}_{j - 1} )$ and $S_{G} (k - 1, j - 1,\varvec{X}_{j - 1} )$ of the original success function. The region of validity of (17a) in the $kj$-plane is bordered by two straight lines on which the following two boundary conditions hold

$$ S_{G} \left( {k, j,\varvec{X}_{j} } \right) = 1, \quad k = 0, j \ge 1, $$

(17b)

$$ S_{G} \left( {k,j,\varvec{X}_{j} } \right) = 0, \quad k = j + 1, j \ge 1, $$

(17c)

Equations (17) are in PRE form, with Probability Transforms

$$ R_{G} (k, j,\varvec{p}_{j} ) = q_{j} R_{G} (k, j - 1,\varvec{p}_{j - 1} ) + p_{j} R_{G} (k - 1, j - 1,\varvec{p}_{j - 1} ), \quad 1 \le k \le j \le n, $$

(18a)

$$ R_{G} \left( {k, j,\varvec{p}_{j} } \right) = 1, \quad k = 0, j \ge 1, $$

(18b)

$$ R_{G} \left( {k,j,\varvec{p}_{j} } \right) = 0, \quad k = j + 1, j \ge 1, $$

(18c)

which govern the reliability of the k-out-of-j:G system. Based on the recursive relation (18a) together with the boundary conditions (18b and 18c), a quadratic-time iterative algorithm was developed by Rushdi [27], and later named the AR algorithm [37, 39]. The AR algorithm has the beautiful characteristic of having the same form (and hence same complexity) for computing both the reliability and unreliability of either the k-out-of-n:G system or its dual the k-out-of-n:F system. Table 5 illustrates this point by listing various recursive relations together with boundary conditions for the two dual types of k-out-of-n systems in the Boolean and probabilistic domains. Entries in the lower two rows of Table 5 are Probability Transforms of the corresponding entries of the upper two rows, which happen to be in PRE form. Entries in the left column of Table 5 are inversions of the corresponding entries of the right column. Power of working in the Boolean domain is manifested in the complementation and dualization operations that transform $S_{G} (k, j,\varvec{X}_{j} )$ in (17) to $\bar{S}_{G} (k, j,\varvec{X}_{j} )$ and $S_{F} (k, j,\varvec{X}_{j} )$, respectively. First, we note that both complementation and dualization change a boundary condition of 1 to 0 and a boundary condition of 0 to 1. We next consider the recursive domain $1 \le k \le j \le n.$ Inverting $S_{G} (k, j,\varvec{X}_{j} )$ to produce $\bar{S}_{G} (k, j,\varvec{X}_{j} )$ is straightforward since $S_{G} (k, j,\varvec{X}_{j} )$ When one has a partially-factored expression of system success or failure such as the following one [56] basis $\{ \bar{X}_{j} ,X_{j} \}$ with coefficients $S_{G} (k,j - 1,\varvec{X}_{j - 1} )$ and $S_{G} (k - 1, j - 1,\varvec{X}_{j - 1} )$, respectively, and hence $\bar{S}_{G} (k, j,\varvec{X}_{j} )$ is expressed in terms of the same orthonormal basis, but with inverted coefficients $\bar{S}_{G} \left( {k, j - 1,\varvec{X}_{j - 1} } \right)$ and $\bar{S}_{G} (k - 1, j - 1,\varvec{X}_{j - 1} )$. Since $S_{F} (k, j,\varvec{X}_{j} )$ is the dual function of $S_{G} (k, j ,\varvec{X}_{j} )$, it is obtained from it by inverting both its output $S_{G}$ and inputs (arguments) $\varvec{X}_{j},$ namely $S_{F} (k, j,\varvec{X}_{j} )$ $= \bar{S}_{G} \left( {k,j,\bar{\varvec{X}}_{j} } \right)$, and hence it is given by the complement of (17a) with inputs inverted, i.e., it is given by the complement of

Table 5 Various recursive relations together with boundary conditions for the two dual types of k-out-of-n systems in the Boolean and probabilistic domains

$$ X_{j} S_{G} (k, j - 1,\bar{\varvec{X}}_{j - 1} ) \vee \overline{{X_{j} }} S_{G} (k - 1,j - 1,\bar{\varvec{X}}_{j - 1} ). $$

This complement is given by

$$ \begin{aligned} & X_{j} \bar{S}_{G} (k,j - 1,\bar{\varvec{X}}_{j - 1} ) \vee \overline{{X_{j} }} \bar{S}_{G} (k - 1,j - 1,\bar{\varvec{X}}_{j - 1} ) \\ & \quad = X_{j} S_{F} (k,j - 1,\varvec{X}_{j - 1} ) \vee \overline{{X_{j} }} S_{F} (k - 1, j - 1,\varvec{X}_{j - 1} ). \\ \end{aligned} $$

Rushdi [52] noted that the AR algorithm is, in fact, an implementation of the Reduced Ordered Binary Decision Diagram (ROBDD) strategy when this strategy is adapted for computing the k-out-n-reliability. The ROBDD strategy was proposed by Bryant [110] as an extension of the BDD methodology of Akers [111]. The ROBDD deals with general switching (two-valued Boolean) functions, and is now considered the state-of-the-art data structure for handling such functions, with extensive applications in reliability [112–122]. As stated earlier, the AR algorithm has a domain of applicability that is narrower than that of the ROBDD algorithm, as it is restricted to switching functions that are both monotonically nondecreasing and totally symmetric. Apart from this, the AR algorithm has exactly the same features as the ROBDD algorithm, namely:

• 1. Both the AR and ROBDD algorithms are based on the Boole–Shannon expansion in the Boolean domain.

• 2. Both algorithms visit the variables in a certain order, typically monotonically ascending or monotonically descending.

• 3. Both algorithms reduce the resulting expansion tree (which is exponential in size) to a rooted acyclic graph that is both canonical and hopefully compact or sub-exponential. The reduction rules [122] require 3(a) merging isomorphic subtrees, and 3(b) deletion of useless nodes whose outgoing edges point to the same child node.

Figure 1 translates the lower two rows of Table 5 into a quad of Mason Signal Flow Graph (SFGs) for computing the reliability and unreliability of the $k_{1}$-out-of-($k_{1} + k_{2}$):G system and the $k_{1}$-out-of-($k_{1} + k_{2}$):F system for $k_{1} \le 0$ and $k_{2} \le - 1.$ Figure 1 is drawn over a rectangular grid of coordinates $k_{1} = k,$ $k_{2} = n - k_{1}.$ The graphs in Fig. 1 are the essence of the four versions of the iterative AR algorithm. Striking similarities (and trivial, albeit subtle differences) of these graphs with ROBDDs are discussed in Rushdi and Alturki [61].

Fig. 1

Translation of the lower two rows of Table 5 into a quad of Mason signal flow graph (SFGs)

Though the recursive relation (17a) was discovered initially in the Boolean domain [27], it can be derived, as an afterthought, in the probability domain. For this purpose, we employ the Total Probability Theorem with the two mutually exclusive and exhaustive events {component j is failed} and {component j is good}, for $1 \le k \le j \le n,$ as follows

$$ \begin{aligned} R_{G} (k, j,\varvec{p}_{j} ) & = Pr \{ {\text{at}}\,{\text{least}}\,k\,{\text{components}}\,{\text{out}}\,{\text{of}}\,j\,{\text{are}}\,{\text{good}}\} \\ & = Pr\{ {\text{at}}\,{\text{least}}\,k\,{\text{components}}\,{\text{out}}\,{\text{of}}\,j\,{\text{are}}\,{\text{good}}|{\text{component}}\,j\,{\text{is}}\,{\text{failed}}\} \\ & Pr\{ component\,j\,is\,failed\} \\ & \quad + Pr\{ {\text{at}}\,{\text{least}}\,k\,{\text{component}}s\,{\text{out}}\,{\text{of}}\,j\,{\text{are}}\,{\text{good}}|{\text{component}}\,j\,{\text{is}}\,{\text{good}}\} \\ & Pr\{ \text{component}\,j\,{\text{is}}\,{\text{good}}\} \\ & = Pr\{ {\text{at}}\,{\text{least}}\,k\,{\text{components}}\,{\text{out of}}\,(j - 1)\,{\text{are}}\,{\text{good}}\} q_{j} \\ & \quad + Pr\{ {\text{at least}}\,(k - 1)\,{\text{component}}s\,{\text{out of}}\,(j - 1)\,{\text{are good}}\} p_{j} \\ & = q_{j} R_{G} (k,j - 1,\varvec{p}_{j - 1} ) + p_{j} R_{G} (k - 1,j - 1,\varvec{p}_{j - 1} ). \\ \end{aligned} $$

The derivation above should not be viewed as a defeat of purpose of the paradigm presented herein. Simple as it may be, this derivation was arrived at only after (18a) became known, as a transform of the Boolean result (17a).

6 Conclusions

This chapter gives a detailed overview of the current practice of solving system reliability problems by first formulating and manipulating them in the Boolean domain, and subsequently going to the probability domain. This practice is a supplementary alternative of the more dominant practice of working solely in the probability domain all throughout the solution process. The equivalence between event-based probability (which uses probabilities of events) and Boolean-based probability (which employs expectations of indicator variables of such events) is demonstrated. In particular, the expectation of a Boolean quotient is identified as a conditional probability, and the Boole–Shannon expansion is recognized as a Boolean-domain counterpart of the Total Probability Theorem.

Formulation of a system reliability problem in the Boolean domain is conceptually very simple for systems described by verbal statements. It is the natural strategy to use for systems described by fault trees, which are composed of logical AND–OR gates, and can similarly be utilized with systems described by block diagrams. It is the method of choice with systems described by network graphs, when these systems are handled through the enumeration of minimal pathsets and minimal cutsets, rather than via other graph techniques. Manipulations in the Boolean domain are facilitated for small problems by the existence of insightful manual tools such as the Karnaugh map or the variable-entered Karnaugh map, and for large problems due to the availability of many scalable efficient algorithms such as those utilizing the ROBDD. Transfer from the Boolean domain to the probability domain is achieved via the Real or Probability Transform of a switching (two-valued Boolean) function, which is generally an intractable process of exponential complexity. However, computational burden can be shifted to the Boolean domain, with a potential decrease in complexity, if the pertinent Boolean function is first cast into the form of a PRE. Some of the important rules used in generating a PRE are presented, occasionally along with succinct proofs. These include rules to achieve disjointness (orthogonality) of ORed formulas, and to preserve statistical independence as much as possible among ANDed formulas.

The chapter reports a special case of Boolean-domain success by discussing recursive relations governing the reliability and unreliability of the k-out-of-n:G and the k-out-of-n:F systems. The complementation (inversion) and dualization operations in the Boolean domain are utilized to interrelate these four entities, and to evaluate them via four versions of the same algorithm. These four versions of the algorithm are explained in terms of signal flow graphs that are compact, regular, and acyclic, in addition to being isomorphic to the ROBDD, which is reputed to be the most efficient technique for manipulating Boolean functions.

From a pedagogical point of view, the paradigm and concepts discussed herein might be too involved to be of utility in elementary probability education. However, a somewhat bold suggestion is to employ the present paradigm and concepts in areas constituting advanced applications of probability (beside that of system reliability) such as telecommunications, genetics, and finance.

Appendix A: Boolean Quotient

Let us define a literal to be a letter or its complement, where a letter is a constant or a variable. A Boolean term or product is a conjunction or ANDing of m literals in which no letter appears more than once. For m = 1, a term is a single literal and for m = 0, a term is the constant 1. Note that, according to this definition the constant 0 is not a term. Given a Boolean function and a term t, the Boolean quotient of with respect to t, denoted by (), is defined to be the function formed from by imposing the constraint {t = 1} explicitly [103], i.e.,

(19)

The Boolean quotient is also known as a ratio, a subfunction, or a restriction. Brown [103] lists and proves several useful properties of Boolean quotients, of which we reproduce the following ones:

(20)

(21)

{for n-variable functions and g and an m-variable term t with m ≤ n},

(22)

(23)

(24)

(25)

In this Appendix, we followed Brown [103] in denoting a Boolean quotient by an inclined slash . However, it is possible to denote it by a vertical bar to stress the equivalent meaning (borrowed from conditional probability) of conditioned by t or given t.