Булево дифференциальное исчисление
Предметная область булевой алгебры, обсуждающая изменения булевых переменных и функций

Булево дифференциальное исчисление ( БДИ ) (нем. Boolescher Differentialkalkül ( BDK )) — раздел булевой алгебры, в котором изучаются изменения булевых переменных и булевых функций .

Концепции булевого дифференциального исчисления аналогичны концепциям классического дифференциального исчисления , в частности, изучая изменения функций и переменных по отношению к другому/другим. [1]

Булево дифференциальное исчисление допускает различные аспекты теории динамических систем, такие как

должны обсуждаться в единой и замкнутой форме, объединяя их индивидуальные преимущества.

История и применение

Первоначально вдохновлённое проектированием и тестированием коммутационных схем и использованием кодов с исправлением ошибок в электротехнике , развитие того, что позже превратилось в булево дифференциальное исчисление, было инициировано работами Ирвинга С. Рида [3] , Дэвида Э. Мюллера [4], Дэвида А. Хаффмана [5], Шелдона Б. Эйкерса-младшего [ 6] и А. Д. Таланцева [ 7 ] в период с 1954 по 1959 год, а также Фредерика Ф. Селлерса-младшего [8] [9] Му-Юэ Сяо [ 8] [9] и Лероя В. Бирнсона [8] [9] в 1968 году.

С тех пор были достигнуты значительные успехи как в теории, так и в применении BDC в проектировании коммутационных схем и логическом синтезе .

Работы Андре Тайса [10] [ 11] [12] [13] [14] Марка Давио [11] [12] [13] и Жан-Пьера Дешама [13] в 1970-х годах заложили основы теории BDC, на основе которых Дитер Бохман  [de] , [15], Кристиан Постхофф [15] и Бернд Штайнбах  [de] [16] позднее развили теорию BDC в самостоятельную математическую теорию.

Также была разработана дополнительная теория булева интегрального исчисления (нем. Boolescher Integralkalkül ). [15] [17]

BDC также нашел применение в дискретно-событийных динамических системах (DEDS) [18] в протоколах цифровой сетевой связи .

Между тем, BDC расширился до многозначных переменных и функций [15] [19] [20], а также до решеток булевых функций. [21] [22]

Обзор

Булевы дифференциальные операторы играют важную роль в BDC. Они позволяют распространить применение дифференциалов , известных из классического анализа, на логические функции.

Дифференциалы булевой переменной моделируют отношение: г х я {\displaystyle dx_{i}} х я {\displaystyle x_{i}}

г х я = { 0 , никаких изменений  х я 1 , изменение  х я {\displaystyle dx_{i}={\begin{cases}0,&{\text{без изменений}}x_{i}\\1,&{\text{изменение}}x_{i}\end{cases}}}

Не существует никаких ограничений относительно характера, причин и последствий изменения.

Дифференциалы являются бинарными. Их можно использовать так же, как обычные бинарные переменные . г х я {\displaystyle dx_{i}}

Смотрите также

Ссылки

  1. ^ Х. Велан, Булева алгебра в Энциклопедии математики
  2. ^ Шеуринг, Райнер; Велан, Герберт «Ганс» (1 декабря 1991 г.) [июль 1991 г.]. Бреттауэр, Георг (ред.). «Der Boolesche Differentialkalkül – eine Methode zur Analysis und Synthese von Petri-Netzen» [Булевое дифференциальное исчисление – метод анализа и синтеза сетей Петри]. At – Automatisierungstechnik – Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik (на немецком языке). 39 (7). Штутгарт, Германия: Р. Ольденбург Верлаг  [де] : 226–233. дои : 10.1524/auto.1991.39.112.226. ISSN  0178-2312. S2CID  56766796. Архивировано из оригинала 2017-10-16 . Получено 2017-10-16 .(8 страниц)
  3. ^ Рид, Ирвинг Стой (1954). «Класс кодов с исправлением множественных ошибок и схема декодирования». Труды профессиональной группы IRE по теории информации . 4 (4). IEEE: 38–49. doi :10.1109/TIT.1954.1057465.
  4. ^ Мюллер, Дэвид Юджин (1954). «Применение булевой алгебры к проектированию коммутационных схем и обнаружению ошибок». Труды Профессиональной группы IRE по электронным компьютерам . EC-3 (3): 6–12. doi :10.1109/IREPGELC.1954.6499441.
  5. ^ Хаффман, Дэвид Альберт (1958-01-15). «Критерий разрешимости одновременных логических уравнений». Ежеквартальный отчет о ходе работ (48). Кембридж, Массачусетс, США: Исследовательская лаборатория электроники Массачусетского технологического института: 87–88. 156–161 гг. н. э.(2 страницы)
  6. ^ Эйкерс-младший, Шелдон Бакингем (декабрь 1959 г.). «О теории булевых функций». Журнал Общества промышленной и прикладной математики . 7 (4). Общество промышленной и прикладной математики : 487–498. doi :10.1137/0107041. ISSN  0368-4245.(12 страниц)
  7. ^ Таланцев [Таланцев], А. Д. [Н.Э.] (1959). «Об анализе и синтезе некоторых электрических схем при помощи специальных логических операторов» б анализа и синтезе некоторых электрических схем при помощи специальных логических операторов. Автоматика и телемеханика [ Автоматика и телемеханика ] (на русском языке). 20 (7). Москва, Россия: 898–907. Ми  в 12783. Архивировано из оригинала 17 октября 2017 г. Проверено 17 октября 2017 г. […] Основное содержание статьи доложено на семинаре по техническим приложениям математической логики в МГУ 2/Х 1958 г. и 16/1 1959 […] Автор считает своим долгом выражение признательности В. А. Трапезникову  [ru] , В. И. Шестакову и М. Л. Цетлину за интерес к работе и ценные замечания при обсуждении результатов. […] [[…] Основное содержание статьи было представлено на технико-прикладном семинаре по математической логике в МГУ 1958-10-02 и 1959-01-16 […] Автор считает своим долгом выражаем благодарность В.А. Трапезникову  [ru] , В.И. Шестакову и М.Л. Цетлину за интерес к работе и ценные замечания при обсуждении результатов.[…]](10 страниц)
  8. ^ abc Sellers Jr., Frederick F.; Hsiao, Mu-Yue; Bearnson, Leroy W. (июль 1968). «Анализ ошибок с помощью булевой разности». IEEE Transactions on Computers . C-17 (7): 676–683. doi :10.1109/TC.1968.227417. ISSN  0018-9340. S2CID  206617023.(8 страниц)
  9. ^ abc Sellers Jr., Frederick F.; Hsiao, Mu-Yue; Bearnson, Leroy W. (ноябрь 1968 г.). Error Detecting Logic for Digital Computers (1-е изд.). Нью-Йорк, США: McGraw-Hill Book Company . стр. 17–37. LCCN  68-16491. OCLC  439460.(21 из xviii+295 страниц)
  10. ^ Thayse, André (октябрь 1970 г.) [май 1970 г.]. «Анализ переходных процессов в логических сетях, применяемых для обнаружения опасностей» (PDF) . Philips Research Reports . 25 (5). Брюссель, Бельгия: Philips Research Laboratory : 261–336. R737. Архивировано из оригинала (PDF) 2017-03-08 . Получено 2017-10-17 . […] Автор признателен доктору М. Давио за его постоянный интерес и комментарии к этой работе. Также выражается благодарность г-ну К. Фоссепре, который изначально предложил основную проблему, рассматриваемую здесь. […](76 страниц)
  11. ^ ab Thayse, André (февраль 1971 г.). "Булевое дифференциальное исчисление" (PDF) . Philips Research Reports . 26 (2). Брюссель, Бельгия: Philips Research Laboratory : 229–246. R764. Архивировано из оригинала (PDF) 2017-03-08 . Получено 2017-10-16 . […] Аннотация: После краткого обзора классических концепций, относящихся к булевому дифференциальному исчислению, предпринято теоретическое исследование различных дифференциальных операторов. Упоминается применение этих концепций к нескольким важным проблемам, возникающим в практике коммутации. […] Благодарность: Автор особенно благодарен доктору М. Давио за его поддержку и поощрение, а также за несколько идей в презентации. […](18 страниц)
  12. ^ ab Thayse, André; Davio, Marc (1973-04-01). «Булево дифференциальное исчисление и его применение к теории коммутации». IEEE Transactions on Computers . C-22 (4): 409–420. doi :10.1109/TC.1973.223729. S2CID  13480467.(12 страниц)
  13. ^ abc Davio, Marc; Deschamps, Jean-Pierre; Thayse, André (1978-08-01). Дискретные и коммутационные функции (1-е изд.). Нью-Йорк, США: Georgi Publishing Company / McGraw-Hill International Book Company . ISBN 0-07-015509-7. LCCN  77-030718.(xx+729 страниц)
  14. ^ Тайзе, Андре (1981). Гус, Герхард [на немецком языке] ; Хартманис, Юрис (ред.). Булево исчисление разностей . Конспекты лекций по информатике. Том. 101 (1-е изд.). Берлин: Springer-Verlag . ISBN 3-540-10286-8.(144 страницы)
  15. ^ abcd Бохманн, Дитер [на немецком языке] ; Постхофф, Кристиан (1981). Binäre dynamische Systeme [ Бинарные динамические системы ] (на немецком языке) (1-е изд.). Akademie-Verlag , Берлин / R. Oldenbourg Verlag  [de] , Мюнхен. ISBN 3-486-25071-X. DNB-IDN  810757168, 810200317. Номер лицензии  [de] : 202.100/408/81. Код заказа: 7623619 (6391).(397 страниц) (Примечание. Согласно DNB-IDN  368893146 русский перевод этой работы был выпущен в 1986 году.)
  16. ^ Бохманн, Дитер [на немецком языке] ; Штайнбах, Бернд [на немецком языке] (1991). Logikentwurf mit XBOOLE – Algorithmen und Program [ Логическое проектирование с помощью XBOOLE – Алгоритмы и программы ] (на немецком языке) (1-е изд.). Берлин, Германия: Verlag Technik . ISBN 3-341-01006-8DNB -IDN  911196102.(303 страницы + 5,25-дюймовая дискета)
  17. ^ Steinbach, Bernd [на немецком языке] ; Posthoff, Christian (2013-07-01). Thornton, Mitchell A. (ред.). Boolean Differential Equations . Synthesis Lectures on Digital Circuits and Systems (1-е изд.). Сан-Рафаэль, Калифорния, США: Morgan & Claypool Publishers. doi :10.2200/S00511ED1V01Y201305DCS042. ISBN 978-1-62705-241-2. S2CID  17528915. Лекция №42.(158 страниц)
  18. ^ Scheuring, Rainer; Wehlan, Herbert "Hans" (1991-09-01). Franke, Dieter; Kraus, Franta (ред.). "On the Design of Discrete Event Dynamic Systems by Means of the Boolean Differential Calculus". Первый симпозиум IFAC по методам проектирования систем управления . 2 (8). Цюрих, Швейцария: Международная федерация автоматического управления (IFAC) / Pergamon Press : 723–728. doi :10.1016/S1474-6670(17)54214-7.(6 страниц)
  19. ^ Анушкевич [Янушкевич], Светлана Н. [Светлана Н.] (1998). Логическое дифференциальное исчисление в построении многозначной логики (кандидатская диссертация) (1-е изд.). Щецин, Польша: Институт информатики, Технический университет Щецина. ISBN 978-8-387423-16-2. ISSN  1506-3054.(326 страниц)
  20. ^ Бохманн, Дитер [на немецком языке] (1 сентября 2008 г.). Двоичные системы - булева книга (1-е изд.). Дрезден, Германия: TUDpress Verlag der Wissenschaften. ISBN 978-3-940046-87-1DNB-IDN  989771636 .(421 страница) Перевод: Бохманн, Дитер [на немецком языке] (февраль 2006 г.). Binäre Systeme - Ein BOOLEAN Buch [ Двоичные системы - Булева книга ] (на немецком языке) (1-е изд.). Хаген, Германия: LiLoLe-Verlag GmbH (Обучение на протяжении всей жизни) / BoD GmbH. ISBN 3-934447-10-4. ISBN 978-3-934447-10-3 . DNB-IDN  978899873. (452 страницы)
  21. ^ Steinbach, Bernd [на немецком языке] ; Posthoff, Christian (2013). "Производные операции для решеток булевых функций" (PDF) . Труды семинара Рида-Мюллера 2013 г. Тояма, Япония: 110–119. Архивировано (PDF) из оригинала 21.10.2017 г. . Получено 21.10.2017 г. .(10 страниц)
  22. ^ Steinbach, Bernd [на немецком языке] ; Posthoff, Christian (2017-06-07). Thornton, Mitchell A. (ред.). Boolean Differential Calculus . Synthesis Lectures on Digital Circuits and Systems (1-е изд.). Сан-Рафаэль, Калифорния, США: Morgan & Claypool Publishers. doi :10.2200/S00766ED1V01Y201704DCS052. ISBN 978-1-62705-922-0. S2CID  10178376. Лекция №52.(216 страниц)

Дальнейшее чтение

  • Давио, Марк; Пире, Филипп М. (июль 1969 г.). «Les dérivées Booléennes et leur application au Diagnostic» [Булевы производные, их применение и диагностика]. Philips Revue (на французском языке). 12 (3). Брюссель, Бельгия: Исследовательская лаборатория Philips , Manufacture Belge de Lampes et de Materiel Electronique (Исследовательская лаборатория MBLE): 63–76.(14 страниц)
  • Рудяну, Серджиу (сентябрь 1974 г.). Булевы функции и уравнения . North-Holland Publishing Company / American Elsevier Publishing Company . ISBN 0-44410520-4. ISBN 0-72042082-2 . (462 страницы)
  • Бохманн, Дитер [на немецком языке] (1977). «Булево дифференциальное исчисление (обзор)». Инженерная кибернетика . 15 (5). Институт инженеров по электротехнике и электронике (IEEE): 67–75. ISSN  0013-788X.(9 страниц) Перевод: Бохманн, Дитер [на немецком языке] (1977). «[Булево дифференциальное исчисление (опрос)]». Известия Академии наук СССР – Техническая кибернетика (Известия Академии наук СССР – Техническая кибернетика) [Известия Академии наук СССР – Инженерная кибернетика] (5): 125–133.(9 страниц)
  • Кюнрих, Мартин (1986). «Дифференциальные операторы на булевых алгебрах». Zeitschrift für mathematische Logik und Grundlagen der Mathematik (на немецком языке). 32 (17–18). Берлин, Германия (Восток): 271–288. дои : 10.1002/malq.19860321703. № 18.(18 страниц)
  • Дрезиг, Фрэнк (1992). Gruppierung – Theorie und Anwendung in der Logiksynthese [ Группировка – Теория и применение в логическом синтезе ]. Fortschritt-Berichte VDI, сер. 9 (на немецком языке). Том. 145. Дюссельдорф, Германия: VDI-Verlag . ISBN 3-18-144509-6DNB -IDN  940164671.(Примечание. Также: Хемниц, Технический университет, диссертация.) (147 страниц)
  • Scheuring, Rainer; Wehlan, Herbert "Hans" (1993). "Управление дискретными системами событий с помощью булевого дифференциального исчисления". В Balemi, Silvano; Kozák, Petr; Smedinga, Rein (ред.). Дискретные системы событий: моделирование и управление . Progress in Systems and Control Theory (PSCT). Том 13. Базель, Швейцария: Birkhäuser Verlag . С. 79–93. doi :10.1007/978-3-0348-9120-2_7. ISBN 978-3-0348-9916-1.(15 страниц)
  • Posthoff, Christian; Steinbach, Bernd [на немецком языке] (2004-02-04). Логические функции и уравнения – бинарные модели для компьютерных наук (1-е изд.). Дордрехт, Нидерланды: Springer Science + Business Media BV doi :10.1007/978-1-4020-2938-7. ISBN 1-4020-2937-3. OCLC  254106952. ISBN 978-1-4020-2937-0 . (392 страницы)
  • Steinbach, Bernd [на немецком] ; Posthoff, Christian (2009-02-12). Логические функции и уравнения – примеры и упражнения (1-е изд.). Дордрехт, Нидерланды: Springer Science + Business Media BV doi :10.1007/978-1-4020-9595-5. ISBN 978-1-4020-9594-8. LCCN  2008941076.(xxii+232 страницы) [1] (Примечание. Согласно DNB-IDN  1010457748, это издание в твердом переплете было переиздано в мягком переплете в 2010 году.)
  • Steinbach, Bernd [на немецком] ; Posthoff, Christian (2010-06-01). "Булево дифференциальное исчисление – теория и приложения". Журнал вычислительной и теоретической нанонауки . 7 (6). American Scientific Publishers: 933–981. doi :10.1166/jctn.2010.1441. ISSN  1546-1955.(49 страниц)
  • Steinbach, Bernd [на немецком] ; Posthoff, Christian (2010-01-15) [2009]. "Глава 3: Булево дифференциальное исчисление". В Sasao, Tsutomu; Butler, Jon T. (ред.). Progress in Applications of Boolean Functions . Synthesis Lectures on Digital Circuits and Systems (1-е изд.). Сан-Рафаэль, Калифорния, США: Morgan & Claypool Publishers. стр. 55–78, 121–126. doi :10.2200/S00243ED1V01Y200912DCS026. ISBN 978-1-60845-181-4. S2CID  37053010. Лекция №26.(24 из 153 страниц)
Взято с "https://en.wikipedia.org/w/index.php?title=Булевое_дифференциальное_исчисление&oldid=1250418008"