Boolsk differensialregning

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

Boolsk differensialregning (tysk: Boolescher Differentialkalkül – BDK, engelsk: Boolean differential calculus – BDC) er et emne innen Boolsk algebra som beskriver endring av boolske variabler og boolske funksjoner.

Boolsk differensialregning kan beskrive ulike aspekter av dynamisk systemteori slik som automata teori for finite automata, petri-net teori,[1] og tilsynskontrollteori (Supervisory control theory – SCT), slik at de kan bli behandlet på en enhetlig og lukket form, og at deres egenskaper kan behandles samlet.

En tilsvarende teori om boolsk integralregning har også blitt utviklet.[2][3]

Historie[rediger | rediger kilde]

Fagfeltet ble som senere ble til boolsk differensialregning ble inspirert av design og testing av switching circuits og bruk av feilrettende koder i elektroteknikk. I perioden fra 1954 til 1959 kom det flere verk, skrevet av Irving S. Reed,[4] David E. Müller,[5] David A. Huffman,[6] Sheldon B. Akers Jr.[7] og A. D. Talantsev (A. D. Talancev, А. Д. Таланцев)[8] , og senere av Frederick F. Sellers, Jr,[9][10] Mu-Yue Hsiao[9][10] og Leroy W. Bearnson[9][10] i 1968. På 1970-tallet ble grunnlaget for boolsk differensialregning lagt med verk av André Thayse,[11][12][13][14][15] Marc Davio[12][13][14] og Jean-Pierre Deschamps[14]. Senere  videreutviklet Dieter Bochmann,[2] Christian Posthoff[2] og Bernd Steinbach[16] boolsk differensialregning til en fullverdig matematisk teori.

Siden har det blitt gjort betydelige fremskritt innen både teori og anvendelse av boolsk differensialregning, også på området som initierte fagfeltet – design og logisk syntese av switching circuits.

Anvendelser[rediger | rediger kilde]

Boolsk differensialregning har anvendelser innen dynamiske systemer for diskrete hendelser (discrete event dynamic systems – DEDS)[17]. Et eksempel på slike er kommunikasjons protokoller for digitale nettverk.

Diskrete hendelser er også en vesentlig del av biologiske nevrale nett og noen typer nevromorfe nevrale nettverk. I biologiske nevrale nett vil nervecellenes (nevronenes) axon hillock utløse en tilnærmet diskret nerveimpuls, en spike, som propagerer ut til andre nerveceller via nervecellens axoner. Dette vil danne et dynamisk system med diskrete hendelser.

Boolsk differensialregning har også blitt utvidet til variable og funksjoner med flere verdier,[2][18][19] og også nettverk av boolske funksjoner.[20][21]

En Tsetlin-maskin vil bruke variable for å implementere læring i et nettverk av boolske funksjoner.

Oversikt[rediger | rediger kilde]

Boolske differensialoperatorer har en betydelig rolle i boolsk differensialregning. De gjør at differensialligninger, kjent fra klassisk matematisk analyse, kan utvides til logiske funksjoner.

Differensialene av boolske variable modeller relasjonene:

Det er ingen begrensning i forhold til egenskapene, årsakene til endringer, og konsekvensene av endringer.

Differensialene er binære, og kan brukes akkurat som vanlig binære variabler.

Se også[rediger | rediger kilde]

Referanser[rediger | rediger kilde]

  1. ^ Scheuring, Rainer; Wehlan, Herbert "Hans" (1. desember 1991) [Juli 1991]. Bretthauer, Georg, red. «Der Boolesche Differentialkalkül – eine Methode zur Analyse und Synthese von Petri-Netzen» [The Boolean differential calculus – A method for analysis and synthesis of Petri nets]. at – Automatisierungstechnik – Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik (German). Stuttgart, Germany: R. Oldenbourg Verlag. 39 (7): 226–233. ISSN 0178-2312. doi:10.1524/auto.1991.39.112.226. Arkivert fra originalen 16. oktober 2017. Besøkt 16. oktober 2017. 
  2. ^ a b c d Bochmann, Dieter; Posthoff, Christian (1981). Binäre dynamische Systeme [Binary dynamic systems] (German) (1st utg.). Akademie-Verlag, Berlin / R. Oldenbourg Verlag, München. ISBN 3-486-25071-X. 
  3. ^ Steinbach, Bernd; Posthoff, Christian (1. juli 2013). Thornton, Mitchell A., red. «Boolean Differential Equations». Synthesis Lectures on Digital Circuits and Systems. 8 (3) (1st utg.). San Rafael, CA, USA: Morgan & Claypool Publishers. ISBN 978-1-62705-241-2. ISSN 1932-3166. doi:10.2200/S00511ED1V01Y201305DCS042. Lecture #42. Besøkt 15. oktober 2017. 
  4. ^ Reed, Irving Stoy (1954). «A Class of Multiple-Error-Correcting Codes and the Decoding Scheme». Transactions of the IRE Professional Group on Information Theory (PGIT). Institute of Radio Engineers (IRE). PGIT-4 (4): 38–49. 
  5. ^ Muller, David Eugene (1954). «Application of Boolean algebra to switching circuit design and to error detection». Transactions of the IRE Professional Group on Electronic Computers (PGEC). PGEC-3: 6–12. 
  6. ^ Huffman, David Albert (15. januar 1958). «Solvability criterion for simultaneous logical equations». Quarterly Progress Report. Cambridge, MA, USA: MIT Research Laboratory of Electronics (48): 87–88. AD 156-161. 
  7. ^ Akers, Jr., Sheldon Buckingham (Desember 1959) [1957-09-27]. «On a Theory of Boolean Functions». Journal of the Society for Industrial and Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM). 7 (4): 487–498. ISSN 0368-4245. doi:10.1137/0107041. 
  8. ^ Таланцев [Talantsev], А. Д. [A. D.] (1959) [1958-11-01 (submission)]. «Ob analize i sinteze nekotorykh električeskikh skhem pri pomośći special'nykh logičeskikh operatorov» [Analysis and synthesis of certain electric circuits by means of special logical operators]. Автоматика и телемеханика (Avtomatika i telemekhanika) (Russian). Moscow, Russia. 20 (7): 898–907. Arkivert fra originalen 17. oktober 2017. Besøkt 17. oktober 2017. «[…] Основное содержание статьи доложено на семинаре по техническим приложениям математической логики в МГУ 2/Х 1958 г. и 16/1 1959 […] Автор считает своим долгом выразить признательность Vadim Aleksandrovich Trapeznikov, В. И. Шестакову и М. Л. Цетлину за интерес к работе и ценные замечания при обсуждении результатов. […] [[…] The main content of the article was presented at the technical application workshop on mathematical logic at the Moscow State University on 1958-10-02 and 1959-01-16 […] The author considers it his duty to express gratitude to Vadim Aleksandrovich Trapeznikov, V. I. Shestakov and M. L. Tsetlin for interest in the work and valuable comments in discussing the results.[…]]» 
  9. ^ a b c Sellers, Jr., Frederick F.; Hsiao, Mu-Yue; Bearnson, Leroy W. (Juli 1968). «Analyzing Errors with the Boolean Difference». IEEE Transactions on Computers. C–17 (7): 676–683. ISSN 0018-9340. doi:10.1109/TC.1968.227417. 
  10. ^ a b c Sellers, Jr., Frederick F.; Hsiao, Mu-Yue; Bearnson, Leroy W. (November 1968). Error Detecting Logic for Digital Computers (1st utg.). New York, USA: McGraw-Hill Book Company. s. 17–37. LCCN 68-16491. OCLC 439460. 
  11. ^ Thayse, André (Oktober 1970) [Mai 1970]. «Transient analysis of logical networks applied to hazard detection» (PDF). Philips Research Reports. Brussels, Belgium: Philips Research Laboratory, Manufacture Belge de Lampes et de Materiel Electronique (MBLE Research Laboratory). 25 (5): 261–336. R737. Arkivert fra originalen (PDF) 8. mars 2017. Besøkt 17. oktober 2017. «[…] The author is indebted to Dr M. Davio for his continuing interest and comments on this work. Thanks are also due to Mr C. Fosséprez who initially suggested the basic problem considered here. […]» 
  12. ^ a b Thayse, André (Februar 1971). «Boolean Differential Calculus» (PDF). Philips Research Reports. Brussels, Belgium: Philips Research Laboratory, Manufacture Belge de Lampes et de Materiel Electronique (MBLE Research Laboratory). 26 (2): 229–246. R764. Arkivert fra originalen (PDF) 8. mars 2017. Besøkt 16. oktober 2017. «[…] Abstract: After a brief outline of classical concepts relative to Boolean differential calculus, a theoretical study of various differential operators is undertaken. Application of these concepts to several important problems arising in switching practice is mentioned. […] Acknowledgement: The author is especially grateful to Dr M. Davio for his encouragement and support and for several ideas in the presentation. […]» 
  13. ^ a b Thayse, André; Davio, Marc (1. april 1973). «Boolean Differential Calculus and its Application to Switching Theory». IEEE Transactions on Computers. Philips Research Laboratory, Manufacture Belge de Lampes et de Materiel Electronique (MBLE Research Laboratory), Brussels, Belgium: IEEE Computer Society. C–22 (4): 409–420. ISSN 0018-9340. doi:10.1109/T-C.1973.223729. Besøkt 15. oktober 2017. 
  14. ^ a b c Davio, Marc; Deschamps, Jean-Pierre; Thayse, André (1. august 1978). Discrete and Switching Functions (1st utg.). St. Saphorin, Switzerland: Georgi Publishing Company / McGraw-Hill International Book Company. ISBN 0-07015509-7. LCCN 77030718. 
  15. ^ Thayse, André (1981). Goos, Gerhard; Hartmanis, Juris, red. Boolean Calculus of Differences. Lecture Notes in Computer Science. 101 (1st utg.). Philips Research Laboratory, Brussels, Belgium: Springer-Verlag. ISBN 3-540-10286-8. 
  16. ^ Bochmann, Dieter; Steinbach, Bernd (1991). Logikentwurf mit XBOOLE – Algorithmen und Programme [Logic design with XBOOLE – Algorithms and programs] (German) (1st utg.). Berlin, Germany: Verlag Technik. ISBN 3-341-01006-8. 
  17. ^ Scheuring, Rainer; Wehlan, Herbert "Hans" (1. september 1991). Franke, Dieter; Kraus, Franta, red. «On the Design of Discrete Event Dynamic Systems by Means of the Boolean Differential Calculus». First IFAC Symposium on Design Methods of Control Systems. Zürich, Switzerland: International Federation of Automatic Control (IFAC) / Pergamon Press. 2: 723–728. doi:10.1016/S1474-6670(17)54214-7. 
  18. ^ Ânuškevič [Yanushkevich], Svitlana N. [Svetlana N.] (1998). Logic Differential Calculus in Multi-Valued Logic Design. Journal Prace Naukowe Politechniki Szczecińskiej (PhD thesis) (1st utg.). Szczecin, Poland: Instytut Informatyki, Technical University of Szczecin. ISBN 978-8-387423-16-2. ISSN 1506-3054. ISBN 8-387423-16-5. 
  19. ^ Bochmann, Dieter (1. september 2008). Binary Systems - A BOOLEAN Book (1st utg.). Dresden, Germany: TUDpress Verlag der Wissenschaften. ISBN 978-3-940046-87-1.  (421 pages) Translation of: Bochmann, Dieter (februar 2006). Binäre Systeme - Ein BOOLEAN Buch [Binary systems - A Boolean book] (German) (1st utg.). Hagen, Germany: LiLoLe-Verlag GmbH (Life-Long-Learning) / BoD GmbH. ISBN 3-934447-10-4. ISBN 978-3-934447-10-3. 
  20. ^ Steinbach, Bernd; Posthoff, Christian (2013). «Derivative Operations for Lattices of Boolean Functions» (PDF). Proceedings Reed-Muller Workshop 2013. Toyama, Japan: 110–119. Arkivert fra originalen (PDF) 21. oktober 2017. Besøkt 21. oktober 2017. 
  21. ^ Steinbach, Bernd; Posthoff, Christian (7. juni 2017). Thornton, Mitchell A., red. «Boolean Differential Calculus». Synthesis Lectures on Digital Circuits and Systems. 12 (1) (1st utg.). San Rafael, CA, USA: Morgan & Claypool Publishers. ISBN 978-1-62705-922-0. ISSN 1932-3166. doi:10.2200/S00766ED1V01Y201704DCS052. Lecture #52. Besøkt 15. oktober 2017. 

Videre lesning[rediger | rediger kilde]

Eksterne lenker[rediger | rediger kilde]