Derivation of Minimal Cutsets from Minimal Pathsets for a Multi-State System and Utilization of Both Sets in Checking Reliability Expressions
Journal of Engineering Research and Reports,
This paper addresses two important useful extensions of binary reliability techniques to multi-state reliability techniques, namely: (a) the problem of complementation or inversion of the function of system success to that of system failure (or equivalently, of deriving the logical minimal cutsets in terms of the logical minimal paths), and (b) the associated problem of hand-checking of a symbolic reliability expression. The paper deals specifically with the reliability of a multi-state delivery network. It presents two complementation procedures, one via the application of multi-state De Morgan’s rules, and the other via the multi-state Boole-Shannon expansion. The paper also illustrates one case in which this complementation is needed, as it outlines a method for checking the reliability of the multi-state system in terms of its logical minimal paths and logical minimal cutsets.
- Network reliability
- De’ Morgan laws
- Boole-Shannon expansion
- symbolic checking
- probability-ready expression
- multi-state system
How to Cite
Locks MO. Inverting and minimizing Boolean functions, minimal paths and minimal cuts: Noncoherent system analysis. IEEE Transactions on Reliability. 1979;28(5):373-375.
Rai S, Aggarwal KK. On complementation of pathsets and cutsets. IEEE Transactions on Reliability. 1980;29(2):139-140.
Heidtmann KD. Inverting paths & cuts of 2-state systems. IEEE Transactions on Reliability. 1983;32(5):469-474.
Rushdi AM. Map derivation of the minimal sum of a switching function from that of its complement. Microelectronics and Reliability. 1985;25(6):1055-65.
Shier DR, Whited DE. Algorithms for generating minimal cutsets by inversion. IEEE Transactions on Reliability. 1985; 34(4):314-319.
Minato SI, Ishiura N, Yajima S. Shared binary decision diagram with attributed edges for efficient Boolean function manipulation. In 27th ACM/IEEE Design Automation Conference 1990;52-57. IEEE.
Schäbe H. An improved algorithm for cutset evaluation from paths. Micro-electronics Reliability. 1995;35(5):783-787.
Rauzy A. Mathematical foundations of minimal cutsets. IEEE Transactions on Reliability. 2001;50(4):389-396.
Janakiraman TN, Muthammai S, Bhanumathi M. On the Boolean function graph of a graph and on its complement. Mathematica Bohemica. 2005;130(2):113-134.
Rebaiaia ML, Ait-Kadi D. A new technique for generating minimal cut sets in nontrivial network. AASRI Procedia. 2013;5:67-76.
Rushdi AM, Alturki AM. Reliability of coherent threshold systems. Journal of Applied Sciences. 2015;15(3):431-443.
Rushdi AM, Alturki AM. Novel representations for a coherent threshold reliability system: A tale of eight signal ow graphs. Turkish Journal of Electrical Engineering & Computer Sciences. 2018; 26(1):257-269.
Rushdi AM, Alturki AM. Representations of a coherent reliability system via Signal Flow Graphs. Journal of King Abdulaziz University: Engineering Sciences. 2020; 31(1):3-18.
Rushdi AM, Hassan AK. An exposition of system reliability analysis with an ecological perspective. Ecological Indicators. 2016;63:282-295.
Rushdi AM, Goda AS. Symbolic reliability analysis via Shannon's expansion and statistical independence, Microelectronics and Reliability, 1985;25(6):1041-1053.
Rushdi AM, AbdulGhani AA. A comparison between reliability analyses based primarily on disjointness or statistical independence: The case of the generalized INDRA network, Microelectronics and Reliability. 1993;33(7):965-978.
Rushdi AM, Rushdi MA. Switching-algebraic analysis of system reliability, Chapter 6 in M. Ram and P. Davim (Editors), Advances in Reliability and System Engineering. Springer International Publishing, Cham, Switzerland. 2017;139-161.
Rushdi AM. How to hand-check a symbolic reliability expression. IEEE Transactions on Reliability. 1983;32(5):402-408.
Alsalami OM, Rushdi AM. Checking correctness of a symbolic reliability expression for a capacitated network. Journal of Engineering Research and Reports. 2020;18(2):12-29.
Rushdi AMA, Al-Amoudi MA. Switching-algebraic analysis of multi-state system reliability, Journal of Engineering Research and Reports. 2018;3(3):1-22.
Rushdi AMA. Utilization of symmetric switching functions in the symbolic reliability analysis of multi-state k-out-of-n systems. International Journal of Mathematical, Engineering and Management Science (IJMEMS). 2019; 4(2):306-326.
Rushdi AMA, Al-Amoudi MA. Reliability analysis of a multi-state system using multi-valued logic, IOSR Journal of Electronics and Communication Engineering (IOSR-JECE). 2019;14(1):1-10.
Rushdi AMA, Alsayegh AB. Reliability analysis of a commodity-supply multi-state system using the map method. Journal of Advances in Mathematics and Computer Science. 2019;31(2):1-17.
Rushdi AM, Ghaleb FA. Boolean-based symbolic analysis for the reliability of coherent multi-state systems of heterogeneous components. Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2020; 9(2):1-25.
Rushdi AM, AlHuthali SA, AlZahrani NA, Alsayegh AB. Reliability Analysis of Binary-Imaged Generalized Multi-State k-out-of-n Systems. International Journal of Computer Science and Network Security (IJCSNS). 2020;20(9):251-264.
Rushdi AMA, Ghaleb FAM. Reliability characterization of binary-imaged multi-state coherent threshold systems, Inter-national Journal of Mathematical, Engineering and Management Sciences (IJMEMS). 2021;6(1):309-321.
Rushdi AMA, Amashah MH. Symbolic derivation of a probability-ready expression for the reliability analysis of a multi-state delivery network. Journal of Advances in Mathematics and Computer Science. 2021;36(2):37-56.
Rushdi AM, Amashah MH. Conventional and improved inclusion-exclusion derivations of symbolic expressions for the reliability of a multi-state network. Asian Journal of Research in Computer Science. 2021;8(1):21-45.
Rushdi AMA, Amashah MH. Symbolic reliability analysis of a multi-state network. Proceedings of the 2021 IEEE Fourth National Computing Colleges Conference (4th NCCC), Taif, Kingdom of Saudi Arabia. 2021:1-4.
Al-Darrab AI, Rushdi AMA. Multi-state reliability evaluation of local area networks, proceedings of the 2021 IEEE Fourth National Computing Colleges Conference (4th NCCC), Taif, Kingdom of Saudi Arabia. 2021;1-6.
Rushdi AM, Amashah MH. A liaison among inclusion-exclusion, probability-ready expressions and Boole-Shannon expansion for multi-state reliability, Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2021;10(2).
Lin YK, Huang CF, Yeh CT. Network reliability with deteriorating product and production capacity through a multi-state delivery network, International Journal of Production Research. 2014;52(22):6681-6694.
Lisnianski A, Levitin G. Multi-state system reliability: Assessment, optimization and applications. World Scientific Publishing Company. 2003;6.
Lee SC. Modern switching theory and digital design, Prentice-Hall, Englewood Cliffs, New Jersey, NJ, USA; 1978.
Muroga S. Logic design and switching theory. John Wiley, New York, NY, USA; 1979.
Rushdi AM, Al-Khateeb DL. A review of methods for system reliability analysis: A Karnaugh-map perspective, Proceedings of the First Saudi Engineering Conference, Jeddah, Saudi Arabia. 1983;1:57-95.
Hill FJ, Peterson GR. Computer aided logical design with emphasis on VLSI, 4th Edition, Wiley, New York, NY, USA; 1993.
Roth C, Kinney L. Fundamentals of logic design. 7th Edition, Cengage Learning, Stamford, CT, USA; 2014.
Brown FM, Boolean reasoning: The logic of Boolean equations, Kluwer Academic Publishers, Boston, USA; 1990.
Rushdi AM, Alshehri TM, Zarouan M, Rushdi MA. Utilization of the modern syllogistic method in the exploration of hidden aspects in engineering ethical dilemmas. Journal of King Abdulaziz University: Computers and Information Technology. 2014;3(1):73-127.
Rushdi AM, Zarouan M, Alshehri TM, Rushdi MA. The incremental version of the Modern Syllogistic Method. Journal of King Abdulaziz University: Engineering Sciences. 2015;26(1):25-51.
Rushdi AM, Rushdi MA. Switching-algebraic algorithmic derivation of candidate keys in relational databases. Proceedings of the IEEE International Conference on Emerging Trends in Communication Technologies (ICETCT-2016). 2016;1-6.
Rushdi AM, Rushdi MA. Mathematics and examples of the modern syllogistic method of propositional logic. Chapter 6 in Ram M, (Editor), Mathematics Applied in Information Systems, Bentham Science Publishers, Emirate of Sharjah, United Arab Emirates. 2018;123-167.
Rushdi AM, Al-Yahya HA. Derivation of the complete sum of a switching function with the aid of the variable-entered Karnaugh map. Journal of King Saud University-Engineering Sciences. 2001;13(2):239- 68.
Rushdi AM, Albarakati HM. Using variable-entered Karnaugh maps in determining dependent and independent sets of Boolean functions. Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2012; 1(2):45-67.
Rushdi AM, Albarakati HM. The inverse problem for Boolean equations. Journal of Computer Science. 2012;8(12):2098-2105.
Rushdi AM, Zarouan M, Alshehri TM, Rushdi MA. A modern syllogistic method in intuitionistic fuzzy logic with realistic tautology. The Scientific World Journal. 2015;2015; Article ID 327390:1-12.
Rushdi AM, Ahmad W. Finding all solutions of the Boolean Satisfiability problem, If any, via Boolean-equation solving. Journal of King Abdulaziz University: Engineering Sciences. 2016; 27(1):19-34.
Rushdi AM, Rushdi MA, Zarouan M, Ahmad W. Satisfiability in intuitionistic fuzzy logic with realistic tautology. Kuwait Journal of Science. 2018;45(2):15-21.
Rushdi AM, Alturki AM. Unification of mathematical concepts and algorithms of k-out-of-n system reliability: A perspective of improved disjoint products. Journal of Engineering Research. 2018;6(4):1-31.
Rushdi AM, Hassan AK. On the Interplay Between Ecology and Reliability. In Misra, KB (Editor), Handbook of Advanced Performability Engineering, 2021 (pp. 785-809). Springer, Cham, Switzerland.
Rushdi AM, Ghaleb FA. Novel characterizations of the JK bistables (flip flops). Journal of Engineering Research and Reports. 2019;4(3):1-20.
Rushdi AM, Badawi RS. Utilization of eight-Variable Karnaugh maps in the exploration of problems of Qualitative Comparative Analysis. Asian Journal of Research in Computer Science. 2021; 8(2):57-84.
Rushdi AM. Partially-redundant systems: Examples, reliability, and life expectancy, Int. Mag. Adv. Comput. Sci. Telecommun. 2010;1(1):1–13.
Rushdi AM, Alturki AM. Reliability of coherent threshold systems. Journal of Applied Sciences. 2015;15(3):431-443.
Rushdi MAM, Ba-Rukab OM, Rushdi AM. Multi-dimensional recursion relations and mathematical induction techniques: The case of failure frequency of k-out-of-n systems Journal of King Abdulaziz University: Engineering Sciences. 2016; 27(2):15–31.
Rushdi AMA, Ghaleb FAM. A tutorial exposition of semi-tensor products of matrices with a stress on their representation of Boolean functions, Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2016;5(1):3-30.
Ramirez-Marquez JE, Rocco CM, Gebre BA, Coit DW, Tortorella M. New insights on multi-state component criticality and importance. Reliability Engineering & System Safety. 2006;91(8):894-904.
Jane CC, Laih YW. A practical algorithm for computing multi-state two-terminal reliability. IEEE Transactions on Reliability. 2008;57(2):295-302.
Mihova M, Stojkovic N. Minimal cut sets for transportation system. In Proceedings of The 7th International Conference for Informatics and Information Technology (CIIT 2010). 2010;1-8.
Kvassay M, Kostolny J. Evaluation of algorithms for identification of minimal cut vectors and minimal path vectors in multi-state systems. Communications-Scientific letters of the University of Zilina. 2015; 17(4):8-14.
Yeh WC, Bae C, Huang CL. A new cut-based algorithm for the multi-state flow network reliability problem. Reliability Engineering & System Safety. 2015;136:1-7.
Kvaššay M. Reliability Analysis Based on Logical Differential Calculus and Minimal Cut Set Methods. Information Sciences & Technologies: Bulletin of the ACM Slovakia. 2016;8(1):53-68.
Zaitseva E, Levashenko V. Reliability analysis of multi-state system with application of multiple-valued logic. International Journal of Quality & Reliability Management. 2017;34(6):862-878.
Kvassay M, Zaitseva E, Levashenko VG. Minimal cut and minimal path vectors in reliability analysis of binary-and multi- state systems. In ICTERI 2017;713- 726.
Ohi F. From a binary-state system to a multi-state system. International Journal of Industrial Engineering. 2017;24(4):340-365.
Kvassay M, Rabcan J, Rusnak P. Multiple-valued logic in analysis of critical states of multi-state system. In 2017 International Conference on Information and Digital Technologies (IDT) 2017;5:212-217. IEEE.
Ren Y, Zeng C, Fan D, Liu L, Feng Q. Multi-state reliability assessment method based on the MDD-GO model. IEEE Access. 2018;6:5151-5161.
Kvassay M, Rusnak P, Zaitseva E, Stanković RS. Multi-Valued decision diagrams in importance analysis based on minimal cut vectors. In 2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL) 2020;9:265-270. IEEE.
Abstract View: 19 times
PDF Download: 12 times