Boolean differential calculus

Originally inspired by the design and testing of switching circuits and the utilization of error-correcting codes in electrical engineering, the roots for the development of what later would evolve into the Boolean differential calculus were initiated by works of Irving S. Reed, David E. Muller, David A. Huffman, Sheldon B. Akers Jr. and {{lang|ru|A. D. Talantsev}} ({{lang|ru|A. D. Talancev}}, {{lang|ru|А. Д. Таланцев}}) between 1954 and 1959, and of Frederick F. Sellers Jr., Mu-Yue Hsiao and Leroy W. Bearnson in 1968.

Since then, significant advances were accomplished in both, the theory and in the application of the BDC in switching circuit design and logic synthesis.

Works of {{lang|fr|André Thayse}}, Marc Davio and {{lang|fr|Jean-Pierre Deschamps}} in the 1970s formed the basics of BDC on which {{lang|de|{{ill|Dieter Bochmann|de}}}}, {{lang|de|Christian Posthoff}} and {{lang|de|{{ill|Bernd Steinbach|de}}}} further developed BDC into a self-contained mathematical theory later on.

{{anchor|Boolean integral calculus}}A complementary theory of Boolean integral calculus (German: {{lang|de|Boolescher Integralkalkül}}) has been developed as well.

BDC has also found uses in discrete event dynamic systems (DEDS) in digital network communication protocols.

{{anchor|Logic differential calculus}}Meanwhile, BDC has seen extensions to multi-valued variables and functions as well as to lattices of Boolean functions.

Boolean differential operators play a significant role in BDC. They allow the application of differentials as known from classical analysis to be extended to logical functions.

The differentials $dx\_i$ of a Boolean variable $x\_i$ models the relation:

: $dx\_i\; =\; \backslash begin\{cases\}$

0, & \text{no change of } x_i\\

1, & \text{change of } x_i

\end{cases}

There are no constraints in regard to the nature, the causes and consequences of a change.

The differentials $dx\_i$ are binary. They can be used just like common binary variables.

• Boolean Algebra
• Boole's expansion theorem
• Ramadge–Wonham framework

{{Reflist|refs=

{{cite journal |first=Irving Stoy |last=Reed |author-link=Irving Stoy Reed |date=1954 |title=A Class of Multiple-Error-Correcting Codes and the Decoding Scheme |journal=Transactions of the IRE Professional Group on Information Theory |publisher=IEEE |volume=4 |issue=4 |pages=38–49|doi=10.1109/TIT.1954.1057465}}

{{cite journal |first=David Eugene |last=Muller |author-link=David Eugene Muller |title=Application of Boolean algebra to switching circuit design and to error detection |journal=Transactions of the IRE Professional Group on Electronic Computers |volume=EC-3 |date=1954 |issue=3 |pages=6–12|doi=10.1109/IREPGELC.1954.6499441}}

{{cite journal |first=David Albert |last=Huffman |author-link=David Albert Huffman |title=Solvability criterion for simultaneous logical equations |publisher=MIT Research Laboratory of Electronics |location=Cambridge, MA, USA |journal=Quarterly Progress Report |number=48 |id=AD 156-161 |date=1958-01-15 |pages=87–88}} (2 pages)

{{cite journal |first=Sheldon Buckingham |last=Akers Jr. |title=On a Theory of Boolean Functions |journal=Journal of the Society for Industrial and Applied Mathematics |publisher=Society for Industrial and Applied Mathematics |volume=7 |number=4 |date=December 1959 |issn=0368-4245 |doi=10.1137/0107041 |pages=487–498}} (12 pages)

{{cite journal |first=А. Д. [A. D.] |last=Таланцев [Talantsev] |script-title=ru:б анализе и синтезе некоторых электрических схем при помощи специальных логических операторов |title=Ob analize i sinteze nekotorykh električeskikh skhem pri pomośći special'nykh logičeskikh operatorov |language=ru |trans-title=Analysis and synthesis of certain electric circuits by means of special logical operators |journal=Автоматика и телемеханика |trans-journal=Avtomatika i Telemekhanika |volume=20 |number=7 |date=1959 |location=Moscow, Russia |pages=898–907 |id={{mathnet|at12783}} |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=12783&option_lang=rus |access-date=2017-10-17 |url-status=live |archive-url=https://web.archive.org/web/20171017090358/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=12783&option_lang=rus |archive-date=2017-10-17 |quote=[…] Основное содержание статьи доложено на семинаре по техническим приложениям математической логики в МГУ 2/Х 1958 г. и 16/1 1959 […] Автор считает своим долгом выразить признательность {{ill|Vadim Aleksandrovich Trapeznikov{{!}}В. А. Трапезникову|ru|Трапезников, Вадим Александрович}}, В. И. Шестакову и М. Л. Цетлину за интерес к работе и ценные замечания при обсуждении результатов. […] …] 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 {{ill|Vadim Aleksandrovich Trapeznikov{{!}}V. A. Trapeznikov|ru|Трапезников, Вадим Александрович}}, V. I. Shestakov and M. L. Tsetlin for interest in the work and valuable comments in discussing the results.[…]]}} (10 pages)

{{cite journal |first1=Frederick F. |last1=Sellers Jr. |first2=Mu-Yue |last2=Hsiao |first3=Leroy W. |last3=Bearnson |title=Analyzing Errors with the Boolean Difference |journal=IEEE Transactions on Computers |volume=C-17 |issue=7 |pages=676–683 |date=July 1968 |issn=0018-9340 |doi=10.1109/TC.1968.227417|s2cid=206617023 }} (8 pages)

{{cite book |first1=Frederick F. |last1=Sellers Jr. |first2=Mu-Yue |last2=Hsiao |first3=Leroy W. |last3=Bearnson |title=Error Detecting Logic for Digital Computers |publisher=McGraw-Hill Book Company |location=New York, USA |edition=1st |oclc=439460 |lccn=68-16491 |pages=17–37 |date=November 1968}} (21 of xviii+295 pages)

{{cite journal |first=André |last=Thayse |title=Transient analysis of logical networks applied to hazard detection |journal=Philips Research Reports |publisher=Philips Research Laboratory |location=Brussels, Belgium |volume=25 |number=5 |date=October 1970 |orig-year=May 1970 |pages=261–336 |id=R737 |url=http://www.extra.research.philips.com/hera/people/aarts/_Philips%20Bound%20Archive/PRRep/PRRep-25-1970-261.pdf |access-date=2017-10-17 |url-status=dead |archive-url=https://web.archive.org/web/20170308203506/http://www.extra.research.philips.com/hera/people/aarts/_Philips%20Bound%20Archive/PRRep/PRRep-25-1970-261.pdf |archive-date=2017-03-08 |quote=[…] 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. […]}} (76 pages)

{{cite journal |first=André |last=Thayse |title=Boolean Differential Calculus |journal=Philips Research Reports |publisher=Philips Research Laboratory |location=Brussels, Belgium |volume=26 |number=2 |date=February 1971 |pages=229–246 |id=R764 |url=http://www.extra.research.philips.com/hera/people/aarts/_Philips%20Bound%20Archive/PRRep/PRRep-26-1971-229.pdf |access-date=2017-10-16 |url-status=dead |archive-url=https://web.archive.org/web/20170308203806/http://www.extra.research.philips.com/hera/people/aarts/_Philips%20Bound%20Archive/PRRep/PRRep-26-1971-229.pdf |archive-date=2017-03-08 |quote=[…] 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. […]}} (18 pages)

{{cite journal |first1=André |last1=Thayse |first2=Marc |last2=Davio |title=Boolean Differential Calculus and its Application to Switching Theory |journal=IEEE Transactions on Computers |volume=C-22 |issue=4 |date=1973-04-01 |pages=409–420 |doi=10.1109/T-C.1973.223729|s2cid=13480467 }} (12 pages)

{{cite book |first1=Marc |last1=Davio |first2=Jean-Pierre |last2=Deschamps |first3=André |last3=Thayse |title=Discrete and Switching Functions |publisher=Georgi Publishing Company / McGraw-Hill International Book Company |location=New York, USA |edition=1st |date=1978-08-01 |isbn=0-07-015509-7 |lccn=77-030718 |url-access=registration |url=https://archive.org/details/discreteswitchin0000davi}} (xx+729 pages)

{{cite book |first=André |last=Thayse |editor-first1=Gerhard |editor-last1=Goos |editor-link1=:de:Gerhard Goos |editor-first2=Juris |editor-last2=Hartmanis |editor-link2=Juris Hartmanis |title=Boolean Calculus of Differences |series=Lecture Notes in Computer Science |volume=101 |publisher=Springer-Verlag |location=Berlin |edition=1st |date=1981 |isbn=3-540-10286-8}} (144 pages)

{{cite book |first1=Dieter |last1=Bochmann |author-link1=:de:Dieter Bochmann |first2=Christian |last2=Posthoff |title=Binäre dynamische Systeme |language=de |trans-title=Binary dynamic systems |publisher=Akademie-Verlag, Berlin / {{ill|R. Oldenbourg Verlag|de}}, München |edition=1st |date=1981 |isbn=3-486-25071-X |id={{DNB-IDN|810757168|810200317|}}. {{ill|License number (East German books){{!}}License number|de|Lizenznummer}}: 202.100/408/81. Order code: 7623619 (6391).}} (397 pages) (NB. Per {{DNB-IDN|368893146}} a Russian translation of this work was released in 1986.)

{{cite book |first1=Dieter |last1=Bochmann |author-link1=:de:Dieter Bochmann |first2=Bernd |last2=Steinbach |author-link2=:de:Bernd Steinbach |title=Logikentwurf mit XBOOLE – Algorithmen und Programme |language=de |trans-title=Logic design with XBOOLE – Algorithms and programs |publisher=Verlag Technik |location=Berlin, Germany |edition=1st |date=1991 |isbn=3-341-01006-8 |id={{DNB-IDN|911196102}}}} (303 pages + 5.25-inch floppy disk)

{{cite journal |title=On the Design of Discrete Event Dynamic Systems by Means of the Boolean Differential Calculus |first1=Rainer |last1=Scheuring |first2=Herbert "Hans" |last2=Wehlan |date=1991-09-01 |journal=First IFAC Symposium on Design Methods of Control Systems |publisher=International Federation of Automatic Control (IFAC) / Pergamon Press |location=Zürich, Switzerland |editor-first1=Dieter |editor-last1=Franke |editor-first2=Franta |editor-last2=Kraus |volume=2 |issue=8 |doi=10.1016/S1474-6670(17)54214-7 |pages=723–728}} (6 pages)

{{cite journal |title=Der Boolesche Differentialkalkül – eine Methode zur Analyse und Synthese von Petri-Netzen |language=de |trans-title=The Boolean differential calculus – A method for analysis and synthesis of Petri nets |first1=Rainer |last1=Scheuring |first2=Herbert "Hans" |last2=Wehlan |editor-first=Georg |editor-last=Bretthauer |orig-year=July 1991 |date=1991-12-01 |journal=At – Automatisierungstechnik – Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik |publisher={{ill|R. Oldenbourg Verlag|de}} |issn=0178-2312 |location=Stuttgart, Germany |volume=39 |number=7 |pages=226–233 |doi=10.1524/auto.1991.39.112.226 |s2cid=56766796 |url=https://www.degruyter.com/view/j/auto.1991.39.issue-1-12/auto.1991.39.112.226/auto.1991.39.112.226.xml |access-date=2017-10-16 |url-status=live |archive-url=https://web.archive.org/web/20171016190403/https://www.degruyter.com/view/j/auto.1991.39.issue-1-12/auto.1991.39.112.226/auto.1991.39.112.226.png |archive-date=2017-10-16}} (8 pages)

{{cite thesis |first=Svitlana N. |last=Ânuškevič |author-link=Svetlana Yanushkevich |title=Logic Differential Calculus in Multi-Valued Logic Design |type=PhD thesis |publisher=Instytut Informatyki, Technical University of Szczecin |location=Szczecin, Poland |edition=1st |date=1998 |issn=1506-3054 |isbn=978-8-387423-16-2}} (326 pages)

{{cite book |first=Dieter |last=Bochmann |author-link=:de:Dieter Bochmann |title=Binary Systems - A BOOLEAN Book |publisher=TUDpress Verlag der Wissenschaften |location=Dresden, Germany |edition=1st |date=2008-09-01 |isbn=978-3-940046-87-1 |id={{DNB-IDN|989771636}}}} (421 pages) Translation of: {{cite book |first=Dieter |last=Bochmann |author-link=:de:Dieter Bochmann |title=Binäre Systeme - Ein BOOLEAN Buch |language=de |trans-title=Binary systems - A Boolean book |publisher=LiLoLe-Verlag GmbH (Life-Long-Learning) / BoD GmbH |location=Hagen, Germany |edition=1st |date=February 2006 |isbn=3-934447-10-4 |id={{ISBN|978-3-934447-10-3}}. {{DNB-IDN|978899873}}}} (452 pages)

{{cite journal |first1=Bernd |last1=Steinbach |author-link1=:de:Bernd Steinbach |first2=Christian |last2=Posthoff |title=Derivative Operations for Lattices of Boolean Functions |journal=Proceedings Reed-Muller Workshop 2013 |location=Toyama, Japan |date=2013 |pages=110–119 |url=http://www.informatik.tu-freiberg.de/prof2/publikationen/RM_2013_dolbf.pdf |access-date=2017-10-21 |url-status=live |archive-url= https://web.archive.org/web/20171021224454/http://www.informatik.tu-freiberg.de/prof2/publikationen/RM_2013_dolbf.pdf |archive-date=2017-10-21}} (10 pages)

{{cite book |first1=Bernd |last1=Steinbach |author-link1=:de:Bernd Steinbach |first2=Christian |last2=Posthoff |editor-first=Mitchell A. |editor-last=Thornton |title=Boolean Differential Equations |series=Synthesis Lectures on Digital Circuits and Systems |publisher=Morgan & Claypool Publishers |location=San Rafael, CA, USA |date=2013-07-01 |id=Lecture #42 |edition=1st |isbn=978-1-62705-241-2 |doi=10.2200/S00511ED1V01Y201305DCS042|s2cid=17528915 }} (158 pages)

{{cite book |first1=Bernd |last1=Steinbach |author-link1=:de:Bernd Steinbach |first2=Christian |last2=Posthoff |editor-first=Mitchell A. |editor-last=Thornton |title=Boolean Differential Calculus |series=Synthesis Lectures on Digital Circuits and Systems |publisher=Morgan & Claypool Publishers |location=San Rafael, CA, USA |date=2017-06-07 |id=Lecture #52 |edition=1st |isbn=978-1-62705-922-0 |doi=10.2200/S00766ED1V01Y201704DCS052|s2cid=10178376 }} (216 pages)

}}

• {{cite journal |first1=Marc |last1=Davio |first2=Philippe M. |last2=Piret |title=Les dérivées Booléennes et leur application au diagnostic |language=fr |trans-title=Boolean derivatives and their application and diagnosis |journal=Philips Revue |publisher=Philips Research Laboratory, {{lang|fr|Manufacture Belge de Lampes et de Materiel Electronique}} (MBLE Research Laboratory) |location=Brussels, Belgium |volume=12 |issue=3 |pages=63–76 |date=July 1969}} (14 pages)
• {{cite book |first=Sergiu |last=Rudeanu |title=Boolean Functions and Equations |date=September 1974 |publisher=North-Holland Publishing Company/American Elsevier Publishing Company |isbn=0-44410520-4 |id={{isbn|0-72042082-2}}}} (462 pages)
• {{cite journal |first=Dieter |last=Bochmann |author-link=:de:Dieter Bochmann |title=Boolean differential calculus (a survey) |journal=Engineering Cybernetics |publisher=Institute of Electrical and Electronics Engineers (IEEE) |volume=15 |number=5 |date=1977 |issn=0013-788X |pages=67–75}} (9 pages) Translation of: {{cite journal |first=Dieter |last=Bochmann |author-link=:de:Dieter Bochmann |language=ru |title=[Boolean differential calculus (survey)] |journal=Известия Академии наук СССР – Техническая кибернетика (Izvestii︠a︡ Akademii Nauk SSSR – Tekhnicheskai︠a︡ kibernetika) [Proceedings of the Academy of Sciences of the USSR – Engineering Cybernetics] |number=5 |date=1977 |pages=125–133}} (9 pages)
• {{cite journal |first=Martin |last=Kühnrich |title=Differentialoperatoren über Booleschen Algebren |language=de |trans-title=Differential operators on Boolean algebras |journal=Zeitschrift für mathematische Logik und Grundlagen der Mathematik |date=1986 |location=Berlin, Germany (East) |doi=10.1002/malq.19860321703 |volume=32 |issue=17–18 |id=#18 |pages=271–288}} (18 pages)
• {{cite book |first=Frank |last=Dresig |title=Gruppierung – Theorie und Anwendung in der Logiksynthese |language=de |trans-title=Grouping – Theory and application in logic synthesis |series=Fortschritt-Berichte VDI, Ser. 9 |volume=145 |publisher=VDI-Verlag |location=Düsseldorf, Germany |date=1992 |isbn=3-18-144509-6 |id={{DNB-IDN|940164671}}}} (NB. Also: Chemnitz, Technische Universität, Dissertation.) (147 pages)
• {{cite book |chapter=Control of Discrete Event Systems by Means of the Boolean Differential Calculus |first1=Rainer |last1=Scheuring |first2=Herbert "Hans" |last2=Wehlan |date=1993 |editor-first1=Silvano |editor-last1=Balemi |editor-first2=Petr |editor-last2=Kozák |editor-first3=Rein |editor-last3=Smedinga |title=Discrete Event Systems: Modeling and Control |series=Progress in Systems and Control Theory (PSCT) |volume=13 |publisher=Birkhäuser Verlag |location=Basel, Switzerland |pages=79–93 |doi=10.1007/978-3-0348-9120-2_7|isbn=978-3-0348-9916-1 }} (15 pages)
• {{cite book |first1=Christian |last1=Posthoff |first2=Bernd |last2=Steinbach |author-link2=:de:Bernd Steinbach |title=Logic Functions and Equations – Binary Models for Computer Science |publisher=Springer Science + Business Media B.V. |location=Dordrecht, Netherlands |date=2004-02-04 |edition=1st |isbn=1-4020-2937-3 |oclc=254106952 |doi=10.1007/978-1-4020-2938-7 |id={{ISBN|978-1-4020-2937-0}}}} (392 pages)
• {{cite book |first1=Bernd |last1=Steinbach |author-link1=:de:Bernd Steinbach |first2=Christian |last2=Posthoff |title=Logic Functions and Equations – Examples and Exercises |publisher=Springer Science + Business Media B.V. |location=Dordrecht, Netherlands |date=2009-02-12 |edition=1st |isbn=978-1-4020-9594-8 |lccn=2008941076 |doi=10.1007/978-1-4020-9595-5}} (xxii+232 pages) [http://www.e-reading.club/bookreader.php/135805/Posthoff%2C_Steinbach_-_Logic_Functions_and_Equations_-_Examples_and_Exercises.pdf] (NB. Per {{DNB-IDN|1010457748}} this hardcover edition has been rereleased as softcover edition in 2010.)
• {{cite journal |first1=Bernd |last1=Steinbach |author-link1=:de:Bernd Steinbach |first2=Christian |last2=Posthoff |title=Boolean Differential Calculus – Theory and Applications |journal=Journal of Computational and Theoretical Nanoscience |publisher=American Scientific Publishers |volume=7 |issue=6 |date=2010-06-01 |pages=933–981 |issn=1546-1955 |doi=10.1166/jctn.2010.1441 |url=http://www.ingentaconnect.com/content/asp/jctn/2010/00000007/00000006/art00001}} (49 pages)
• {{cite book |first1=Bernd |last1=Steinbach |author-link1=:de:Bernd Steinbach |first2=Christian |last2=Posthoff |chapter=Chapter 3: Boolean Differential Calculus |editor-first1=Tsutomu |editor-last1=Sasao |editor-first2=Jon T. |editor-last2=Butler |title=Progress in Applications of Boolean Functions |url=https://archive.org/details/progressapplicat00sasa |url-access=limited |series=Synthesis Lectures on Digital Circuits and Systems |location=San Rafael, CA, USA |publisher=Morgan & Claypool Publishers |orig-year=2009 |date=2010-01-15 |id=Lecture #26 |edition=1st |isbn=978-1-60845-181-4 |pages=[https://archive.org/details/progressapplicat00sasa/page/n69 55]–78, 121–126 |doi=10.2200/S00243ED1V01Y200912DCS026|s2cid=37053010 }} (24 of 153 pages)

• {{cite encyclopedia |chapter =Boolean differential calculus |author-first=Herbert "Hans" |author-last=Wehlan |title=Boolean differential calculus - Encyclopedia of Mathematics |encyclopedia =Encyclopedia of Mathematics |isbn=978-1-4020-0609-8 |editor-first=Michiel |editor-last=Hazewinkel |editor-link=Michiel Hazewinkel

|publisher=Springer Science+Business Media |date=2010-12-06 |chapter-url=http://www.encyclopediaofmath.org/index.php?title=Boolean_differential_calculus&oldid=12153 |access-date=2017-10-16 |url-status=live |archive-url=https://web.archive.org/web/20171016111554/https://www.encyclopediaofmath.org/index.php/Boolean_differential_calculus |archive-date=2017-10-16}}

• {{cite web |title=XBOOLE |author=Institut für Informatik (IfI) |publisher=TU Bergakademie Freiberg |date=2017 |url=http://www.informatik.tu-freiberg.de/xboole/index.php?language=English&aktwindow=home |access-date=2017-10-31 |url-status=live |archive-url=https://web.archive.org/web/20171031105416/http://www.informatik.tu-freiberg.de/xboole/index.php?language=English&aktwindow=home |archive-date=2017-10-31}} with {{cite web |title=XBOOLE Monitor |date=2008-07-23 |url=http://www.informatik.tu-freiberg.de/xboole/XBOOLEMonitor.zip?Submit=XBOOLE+Monitor |access-date=2017-10-31 |url-status=dead |archive-url=https://web.archive.org/web/20171031002108/http://www.informatik.tu-freiberg.de/xboole/XBOOLEMonitor.zip?Submit=XBOOLE+Monitor |archive-date=2017-10-31}}

{{Authority control}}

Category:Boolean algebra

Category:Automata (computation)

Category:Mathematical logic

Category:Order theory

Category:Set theory