Simplification of logical functions with application to circuits

Jun-e Feng; Rong Zhao; Yanjun Cui; Jun-e Feng; Rong Zhao; Yanjun Cui

doi:10.3934/era.2022168

Electronic Research Archive

2022, Volume 30, Issue 9: 3320-3336. doi: 10.3934/era.2022168

Previous Article Next Article

Research article Special Issues

Simplification of logical functions with application to circuits

1.
School of Mathematics, Shandong University, Jinan 250100, China
2.
College of Science and Engineering, University of Minnesota Twin Cities, Minneapolis 55455, USA

Academic Editor: Wei Lin

Received: 26 May 2022 Revised: 28 June 2022 Accepted: 01 July 2022 Published: 11 July 2022

The simplification problem of logical functions is investigated via the matrix method. First, necessary and sufficient conditions are put forward for the decomposition of logical matrices. Based on this, several criteria are proposed for the simplification of logical functions. Furthermore, an algorithm, which can derive simpler logical forms, is developed, and illustrative examples are given to verify the effectiveness. Finally, the obtained theoretical results are applied to the simplification of electric circuits.
- circuits,
- logical functions,
- simplification,
- semi-tensor product
Citation: Jun-e Feng, Rong Zhao, Yanjun Cui. Simplification of logical functions with application to circuits[J]. Electronic Research Archive, 2022, 30(9): 3320-3336. doi: 10.3934/era.2022168

Related Papers:

Abstract

The simplification problem of logical functions is investigated via the matrix method. First, necessary and sufficient conditions are put forward for the decomposition of logical matrices. Based on this, several criteria are proposed for the simplification of logical functions. Furthermore, an algorithm, which can derive simpler logical forms, is developed, and illustrative examples are given to verify the effectiveness. Finally, the obtained theoretical results are applied to the simplification of electric circuits.

References

[1]	K. Hilary, The laws of thought, Philoso. Phenomen. Res., 52 (1992), 895–911. https://doi.org/10.2307/2107916 doi: 10.2307/2107916
[2]	C. E. Shannon, A symbolic analysis of relay and switching circuits, Trans. Am. Inst. Electr. Eng., 57 (1938), 713–723. https://doi.org/10.1109/t-aiee.1938.5057767 doi: 10.1109/t-aiee.1938.5057767
[3]	D. Cheng, J. Feng, J. Zhao, S. Fu, On adequate sets of multi-valued logic, J. Franklin Inst., 358 (2021), 6705–6722. https://doi.org/10.1016/j.jfranklin.2021.07.003 doi: 10.1016/j.jfranklin.2021.07.003
[4]	M. Karnaugh, The map method for synthesis of combinational logic circuits, Trans. Am. Inst. Electr. Eng., 72 (1953), 593–599. https://doi.org/10.1109/TCE.1953.6371932 doi: 10.1109/TCE.1953.6371932
[5]	J. P. Hayes, Introduction to digital logic design, Prent. Hall, 1993. https://doi.org/978-0-201-15461-0
[6]	R. H. Katz, G. Borriello, Contemporary logic design, Prent. Hall, 2004. https://doi.org/10.1016/0026-2692(95)90052-7
[7]	X. L. Wang, X. Y. Zhang, W. L. Wang, A new representation and simplification method of logic function, in International Conference on Computer & Automation Engineering, 2010. https://doi.org/10.1109/ICCAE.2010.5451556
[8]	S. Kahramanli, S. Guenes, S. Sahan, F. Basciftci, A new method based on cube algebra for the simplification of logic functions, Arab. J. Sci. Eng., 32 (2007), 101–114. https://doi.org/10.1016/j.agee.2006.06.020 doi: 10.1016/j.agee.2006.06.020
[9]	D. Cheng, Semi-tensor product of matrices and its applications-a survey, Methods Appl. Anal., 3 (2007), 641–668. https://doi.org/10.1007/10984413_5 doi: 10.1007/10984413_5
[10]	D. Cheng, H. Qi, Z. Li, Analysis and control of boolean networks: A semi-tensor product approach, London: Springer-Verlag, 2011. https://doi.org/10.3724/SP.J.1004.2011.00529
[11]	F. Li, Y. Tang, Pinning controllability for a Boolean network with arbitrary disturbance inputs, IEEE Trans. Cybern., 51 (2019), 3338–3347. https://doi.org/10.1109/TCYB.2019.2930734 doi: 10.1109/TCYB.2019.2930734
[12]	Y. Li, H. Li, G. Xiao, Set controllability of Markov jump switching Boolean control networks and its applications, Nonlinear Anal. Hybri., 45 (2022), 101179. https://doi.org/10.1016/j.nahs.2022.101179 doi: 10.1016/j.nahs.2022.101179
[13]	Y. Yu, M. Meng, J. Feng, Observability of Boolean networks via matrix equations, Automatica, 111 (2020), 108621. https://doi.org/10.1016/j.automatica.2019.108621 doi: 10.1016/j.automatica.2019.108621
[14]	S. Zhu, J. Lu, L. Lin, Y. Liu, Minimum-time and minimum-triggering control for the observability of stochastic Boolean networks, IEEE Trans. Autom. Control, 67 (2022), 1558–1565. https://doi.org/10.1109/TAC.2021.3069739 doi: 10.1109/TAC.2021.3069739
[15]	B. Wang, J. Feng, H. Li, Y. Yu, On detectability of Boolean control networks, Nonlinear Anal. Hybri., 36 (2020), 100859. https://doi.org/10.1016/j.nahs.2020.100859 doi: 10.1016/j.nahs.2020.100859
[16]	Z. Gao, B. Wang, J. Feng, T. Li, Finite automata approach to reconstructibility of switched Boolean control networks, Neurocomputing, 454 (2021), 34–44. https://doi.org/10.1016/j.neucom.2021.05.019 doi: 10.1016/j.neucom.2021.05.019
[17]	C. V. A. Yerudkar, L. Glielmo, Feedback stabilization control design for switched Boolean control networks, Automatica, 115 (2020), 108934. https://doi.org/10.1016/j.automatica.2020.108934 doi: 10.1016/j.automatica.2020.108934
[18]	M. Meng, J. Lam, J. Feng, K. Cheung, Stability and stabilization of Boolean networks with stochastic delays, IEEE Trans. Autom. Control, 64 (2019), 790–796. https://doi.org/10.1109/TAC.2018.2835366 doi: 10.1109/TAC.2018.2835366
[19]	N. Bof, E. Fornasini, M. Valcher, Output feedback stabilization of Boolean control networks, Automatica, 57 (2015), 21–28. https://doi.org/10.1016/j.automatica.2015.03.032 doi: 10.1016/j.automatica.2015.03.032
[20]	J. Lu, L. Sun, D. W. C. Liu, Y. Ho, J. Cao, Stabilization of Boolean control networks under aperiodic sampled-data control, SIAM J. Control Optim., 56 (2018), 4385–4404. https://doi.org/10.1137/18M1169308 doi: 10.1137/18M1169308
[21]	Y. Wu, T. Shen, A finite convergence criterion for the discounted optimal control of stochastic logical networks, IEEE Trans. Autom. Control, 63 (2018), 262–268. https://doi.org/10.1109/TAC.2017.2720730 doi: 10.1109/TAC.2017.2720730
[22]	Y. Wu, X. Sun, X. Zhao, T. Shen, Optimal control of Boolean control networks with average cost: a policy iteration approach, Automatica, 100 (2019), 378–387. https://doi.org/10.1016/j.automatica.2018.11.036 doi: 10.1016/j.automatica.2018.11.036
[23]	Y. Wu, Y. Guo, M. Toyoda, Policy iteration approach to the infinite horizon average optimal control of probabilistic Boolean networks, IEEE Trans. Neural Netw. Learn. Syst., 32 (2021), 2910–2924. https://doi.org/10.1109/TNNLS.2020.3008960 doi: 10.1109/TNNLS.2020.3008960
[24]	S. Wang, H. Li, New results on the disturbance decoupling of Boolean control networks, IEEE Control Syst. Lett., 5 (2021), 1157–1162. https://doi.org/10.1109/LCSYS.2020.3017645 doi: 10.1109/LCSYS.2020.3017645
[25]	Y. Li, J. Zhu, B. Li, Y. Liu, J. Lu, A necessary and sufficient graphic condition for the original disturbance decoupling of Boolean networks, IEEE Trans. Autom. Control, 66 (2021), 3765–3772. https://doi.org/10.1109/TAC.2020.3025507 doi: 10.1109/TAC.2020.3025507
[26]	J. Zhang, J. Sun, Exponential synchronization of complex networks with continuous dynamics and Boolean mechanism, Neurocomputing, 307 (2018), 146–152. https://doi.org/10.1016/j.neucom.2018.03.061 doi: 10.1016/j.neucom.2018.03.061
[27]	R. Li, T. Chu, X. Wang, Bisimulations of Boolean control networks, SIAM J. Control Optim., 56 (2018), 388–416. https://doi.org/10.1137/17M1117331 doi: 10.1137/17M1117331
[28]	Q. Zhang, J. Feng, The solution and stability of continuous-time cross-dimensional linear systems, Front. Inf. Tech. El., 22 (2021), 210-221. https://doi.org/10.1631/FITEE.1900504 doi: 10.1631/FITEE.1900504
[29]	Y. Zheng, J. Feng, Output tracking of delayed logical control networks with multi-constraints, Front. Inf. Tech. El., 21 (2020), 316–323. https://doi.org/10.1631/FITEE.1900376 doi: 10.1631/FITEE.1900376
[30]	J. Yue, Y. Yan, Z. Chen, X. Jin, Identification of predictors of Boolean networks from observed attractor states, Math. Methods Appl. Sci., 42 (2019), 3848–3864. https://doi.org/10.1002/mma.5616 doi: 10.1002/mma.5616
[31]	D. Cheng, H. Qi, Controllability and observability of Boolean control networks, Automatica, 45 (2009), 1659–1667. https://doi.org/10.1007/s00034-014-9900-8 doi: 10.1007/s00034-014-9900-8
[32]	M. D. Ciletti, Advanced digital design with the verilog HDL, Prent. Hall Upper Saddle River, 2003. https://doi.org/978-0-13-089161-7
[33]	K. H. Rosen, Discrete mathematics and its applications, New York: McGraw-Hill, 2002. https://doi.org/978-0-07-242434-8
[34]	S. Zhu, J. Feng, The set stabilization problem for Markovian jump Boolean control networks: An average optimal control approach, Appl. Math. Comput., 402 (2021), 126133. https://doi.org/10.1016/j.amc.2021.126133 doi: 10.1016/j.amc.2021.126133

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)