Булево дифференциальное исчисление
Булево дифференциальное исчисление ( BDC ) (нем. Boolescher Differentialkalkül ( BDK )) — предметная область булевой алгебры, в которой обсуждаются изменения булевых переменных и булевых функций .
Концепции булевого дифференциального исчисления аналогичны концепциям классического дифференциального исчисления , в частности, они изучают изменения функций и переменных по отношению к другим/другим. [1]
Булево дифференциальное исчисление позволяет использовать различные аспекты теории динамических систем, такие как
обсуждаться в единой и закрытой форме, с объединением их отдельных преимуществ.
История и приложения
[ редактировать ]Первоначально вдохновленный проектированием и тестированием коммутационных схем и использованием кодов с исправлением ошибок в электротехнике , корни развития того, что позже разовьется в булево дифференциальное исчисление, были заложены работами Ирвинга С. Рида , [3] Дэвид Э. Мюллер , [4] Дэвид А. Хаффман , [5] Шелдон Б. Эйкерс мл. [6] and A. D. Talantsev ( A. D. Talancev , А. Д. Таланцев ) [7] между 1954 и 1959 годами и Фредерика Ф. Селлерса-младшего , [8] [9] Му-Юэ Сяо [8] [9] и Лерой В. Беарнсон [8] [9] в 1968 году.
С тех пор были достигнуты значительные успехи как в теории, так и в применении BDC при проектировании коммутационных схем и логическом синтезе .
Работы Андре Тейза , [10] [11] [12] [13] [14] Марк Давио [11] [12] [13] и Жан-Пьер Дешам [13] в 1970-е годы сформировались основы BDC, на которых основывался Дитер Бохманн , [15] Кристиан Постхофф [15] и Бернд Штайнбах [16] Позже BDC развилась в самостоятельную математическую теорию.
дополнительная теория булева интегрального исчисления (нем. Boolescher Integralkalkül ). Также была разработана [15] [17]
BDC также нашел применение в динамических системах дискретных событий (DEDS). [18] в цифровых сетей протоколах связи .
Тем временем в BDC появились расширения для многозначных переменных и функций. [15] [19] [20] а также решеткам булевых функций. [21] [22]
Обзор
[ редактировать ]Булевы дифференциальные операторы играют важную роль в BDC. применение дифференциалов , известных из классического анализа, Они позволяют распространить на логические функции.
Дифференциалы логической переменной моделирует отношение:
Никаких ограничений относительно характера, причин и последствий изменения не существует.
Дифференциалы являются двоичными. Их можно использовать так же, как обычные двоичные переменные .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Х. Велан, Булева алгебра в математической энциклопедии
- ^ Шеринг, Райнер; Велан, Герберт «Ганс» (1 декабря 1991 г.) [июль 1991 г.]. Бреттауэр, Георг (ред.). «Булево дифференциальное исчисление – метод анализа и синтеза сетей Петри » . Ат – технология автоматизации – методы и применения управления, регулирования и информационных технологий (на немецком языке). 39 (7). Штутгарт, Германия: Р. Ольденбург Верлаг : 226–233. дои : 10.1524/auto.1991.39.112.226 . ISSN 0178-2312 . S2CID 56766796 . Архивировано из оригинала 16 октября 2017 г. Проверено 16 октября 2017 г. (8 страниц)
- ^ Рид, Ирвинг Стой (1954). «Класс кодов, исправляющих множественные ошибки, и схема декодирования». Труды профессиональной группы IRE по теории информации . 4 (4). ИИЭР: 38–49. дои : 10.1109/TIT.1954.1057465 .
- ^ Мюллер, Дэвид Юджин (1954). «Применение булевой алгебры к проектированию коммутационных схем и обнаружению ошибок». Труды профессиональной группы IRE по электронным компьютерам . ИК-3 (3): 6–12. дои : 10.1109/IREPGELC.1954.6499441 .
- ^ Хаффман, Дэвид Альберт (15 января 1958 г.). «Критерий разрешимости одновременных логических уравнений». Ежеквартальный отчет о проделанной работе (48). Кембридж, Массачусетс, США: Исследовательская лаборатория электроники Массачусетского технологического института: 87–88. 156–161 годы нашей эры. (2 страницы)
- ^ Акерс-младший, Шелдон Бэкингем (декабрь 1959 г.). «К теории булевых функций». Журнал Общества промышленной и прикладной математики . 7 (4). Общество промышленной и прикладной математики : 487–498. дои : 10.1137/0107041 . ISSN 0368-4245 . (12 страниц)
- ^ Таланцев [Talantsev], А. Д. [A. D.] (1959). "Ob analize i sinteze nekotorykh električeskikh skhem pri pomośći special'nykh logičeskikh operatorov" б анализе и синтезе некоторых электрических схем при помощи специальных логических операторов «Анализ и синтез некоторых электрических цепей с помощью специальных логических операторов». Автоматика и телемеханика [ Автоматика и телемеханика ] (на русском языке). 20 (7). Москва, Россия: 898–907. Mi at12783 . Archived from the original on 2017-10-17 . Retrieved 2017-10-17 .
[…] Основное содержание статьи доложено на семинаре по техническим приложениям математической логики в МГУ 2/Х 1958 г. и 16/1 1959 […] Автор считает своим долгом выразить признательность В. А. Трапезникову , В. И. Шестакову и М. Л. Цетлину за интерес к работе и ценные замечания при обсуждении результатов. […] [[…] 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 V. A. Trapeznikov , V. I. Shestakov and M. L. Tsetlin for interest in the work and valuable comments in discussing the results.[…]]
(10 pages) - ↑ Перейти обратно: Перейти обратно: а б с Селлерс-младший, Фредерик Ф.; Сяо, Му-Юэ; Бернсон, Лерой В. (июль 1968 г.). «Анализ ошибок с помощью логической разницы». Транзакции IEEE на компьютерах . С-17 (7): 676–683. дои : 10.1109/TC.1968.227417 . ISSN 0018-9340 . S2CID 206617023 . (8 страниц)
- ↑ Перейти обратно: Перейти обратно: а б с Селлерс-младший, Фредерик Ф.; Сяо, Му-Юэ; Бернсон, Лерой В. (ноябрь 1968 г.). Логика обнаружения ошибок для цифровых компьютеров (1-е изд.). Нью-Йорк, США: Книжная компания McGraw-Hill . стр. 17–37. LCCN 68-16491 . OCLC 439460 . (21 из xviii+295 страниц)
- ^ Тайзе, Андре (октябрь 1970 г.) [май 1970 г.]. «Переходный анализ логических сетей, применяемый для обнаружения опасностей» (PDF) . Отчеты об исследованиях Philips . 25 (5). Брюссель, Бельгия: Исследовательская лаборатория Philips : 261–336. Р737. Архивировано из оригинала (PDF) 8 марта 2017 г. Проверено 17 октября 2017 г.
[…] Автор благодарен доктору М. Давио за его постоянный интерес и комментарии к этой работе. Благодарим также г-на К. Фоссепре , который первоначально предложил основную проблему, рассматриваемую здесь. […]
(76 страниц) - ↑ Перейти обратно: Перейти обратно: а б Тайзе, Андре (февраль 1971 г.). «Булево дифференциальное исчисление» (PDF) . Отчеты об исследованиях Philips . 26 (2). Брюссель, Бельгия: Исследовательская лаборатория Philips : 229–246. Р764. Архивировано из оригинала (PDF) 8 марта 2017 г. Проверено 16 октября 2017 г.
[…] Аннотация: После краткого изложения классических понятий, касающихся булевого дифференциального исчисления, проводится теоретическое исследование различных дифференциальных операторов. Упоминается применение этих концепций к нескольким важным проблемам, возникающим в практике переключения. […] Благодарность: Автор особенно благодарен доктору М. Давио за его поддержку и поддержку, а также за несколько идей, изложенных в презентации. […]
(18 страниц) - ↑ Перейти обратно: Перейти обратно: а б Тайзе, Андре; Давио, Марк (1 апреля 1973 г.). «Булево дифференциальное исчисление и его применение к теории переключения». Транзакции IEEE на компьютерах . С-22 (4): 409–420. дои : 10.1109/TC.1973.223729 . S2CID 13480467 . (12 страниц)
- ↑ Перейти обратно: Перейти обратно: а б с Давио, Марк; Дешам, Жан-Пьер; Тейзи, Андре (1 августа 1978 г.). Дискретные и переключающие функции (1-е изд.). Нью-Йорк, США: Издательство Джорджи / Международная книжная компания McGraw-Hill . ISBN 0-07-015509-7 . ЛЦН 77-030718 . (xx+729 страниц)
- ^ Тайзе, Андре (1981). Гус, Герхард [на немецком языке] ; Хартманис, Юрис (ред.). Булево исчисление разностей . Конспекты лекций по информатике. Том. 101 (1-е изд.). Берлин: Springer-Verlag . ISBN 3-540-10286-8 . (144 страницы)
- ↑ Перейти обратно: Перейти обратно: а б с д Бохманн, Дитер [на немецком языке] ; Постхофф, Кристиан (1981). Бинарные динамические системы [ Бинарные динамические системы ] (на немецком языке) (1-е изд.). Akademie-Verlag , Берлин / R. Oldenbourg Verlag , Мюнхен. ISBN 3-486-25071-Х . DNB-IDN 810757168 , 810200317 . Номер лицензии : 202.100/408/81. Код заказа: 7623619 (6391). (397 страниц) (NB. Per DNB-IDN 368893146 (русский перевод этого произведения вышел в 1986 году.)
- ^ Бохманн, Дитер [на немецком языке] ; Штайнбах, Бернд [на немецком языке] (1991). Логическое проектирование с помощью XBOOLE – Алгоритмы и программы [ Логическое проектирование с помощью XBOOLE – Алгоритмы и программы ] (на немецком языке) (1-е изд.). Берлин, Германия: Verlag Technik . ISBN 3-341-01006-8 . DNB-IDN 911196102 . (303 страницы + 5,25-дюймовая дискета)
- ^ Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (1 июля 2013 г.). Торнтон, Митчелл А. (ред.). Булевы дифференциальные уравнения . Синтезирующие лекции по цифровым схемам и системам (1-е изд.). Сан-Рафаэль, Калифорния, США: Издательство Morgan & Claypool. дои : 10.2200/S00511ED1V01Y201305DCS042 . ISBN 978-1-62705-241-2 . S2CID 17528915 . Лекция № 42. (158 страниц)
- ^ Шеринг, Райнер; Велан, Герберт «Ганс» (1 сентября 1991 г.). Франке, Дитер; Краус, Франта (ред.). «О проектировании дискретно-событийных динамических систем с помощью булевого дифференциального исчисления». Первый симпозиум МФБ по методам проектирования систем управления . 2 (8). Цюрих, Швейцария: Международная федерация автоматического управления (IFAC) / Pergamon Press : 723–728. дои : 10.1016/S1474-6670(17)54214-7 . (6 страниц)
- ^ Анушкевич [Янушкевич], Светлана Н. [Светлана Н.] (1998). Логическое дифференциальное исчисление в построении многозначной логики (кандидатская диссертация) (1-е изд.). Щецин, Польша: Институт информатики, Технический университет Щецина. ISBN 978-8-387423-16-2 . ISSN 1506-3054 . (326 страниц)
- ^ Бохманн, Дитер [на немецком языке] (1 сентября 2008 г.). Двоичные системы - булева книга (1-е изд.). Дрезден, Германия: TUDpress Verlag der Wissenschaften. ISBN 978-3-940046-87-1 . DNB-IDN 989771636 . (421 страница) Перевод: Бохманн, Дитер [на немецком языке] (февраль 2006 г.). Двоичные системы - Булева книга [ Двоичные системы - Булева книга ] (на немецком языке) (1-е изд.). Хаген, Германия: LiLoLe-Verlag GmbH (Обучение на протяжении всей жизни) / BoD GmbH. ISBN 3-934447-10-4 . ISBN 978-3-934447-10-3 . DNB-IDN 978899873 . (452 страницы)
- ^ Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (2013). «Операции по производной для решеток логических функций» (PDF) . Материалы семинара Рида-Мюллера, 2013 г. Тояма, Япония: 110–119. Архивировано (PDF) из оригинала 21 октября 2017 г. Проверено 21 октября 2017 г. (10 страниц)
- ^ Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (7 июня 2017 г.). Торнтон, Митчелл А. (ред.). Булево дифференциальное исчисление . Синтезирующие лекции по цифровым схемам и системам (1-е изд.). Сан-Рафаэль, Калифорния, США: Издательство Morgan & Claypool. дои : 10.2200/S00766ED1V01Y201704DCS052 . ISBN 978-1-62705-922-0 . S2CID 10178376 . Лекция №52. (216 страниц)
Дальнейшее чтение
[ редактировать ]- Давио, Марк; Пире, Филипп М. (июль 1969 г.). «Булевы производные, их применение и диагностика». Philips Revue (на французском языке). 12 (3). Брюссель, Бельгия: Исследовательская лаборатория Philips , Manufacture Belge de Lampes et de Materiel Electronique (Исследовательская лаборатория MBLE): 63–76. (14 страниц)
- Рудяну, Сергей (сентябрь 1974 г.). Булевы функции и уравнения . Издательская компания Северной Голландии / Американская издательская компания Elsevier . ISBN 0-44410520-4 . ISBN 0-72042082-2 . (462 страницы)
- Бохманн, Дитер [на немецком языке] (1977). «Булево дифференциальное исчисление (обзор)». Инженерная кибернетика . 15 (5). Институт инженеров по электротехнике и электронике (IEEE): 67–75. ISSN 0013-788X . (9 страниц) Перевод: Bochmann, Dieter [in German] (1977). "[Boolean differential calculus (survey)]". Известия Академии наук СССР – Техническая кибернетика (Izvestii︠a︡ Akademii Nauk SSSR – Tekhnicheskai︠a︡ kibernetika) [Proceedings of the Academy of Sciences of the USSR – Engineering Cybernetics] (in Russian) (5): 125–133. (9 pages)
- Кюнрих, Мартин (1986). «Дифференциальные операторы на булевых алгебрах». Журнал математической логики и основ математики (на немецком языке). 32 (17-18). Берлин, Германия (Восток): 271–288. дои : 10.1002/malq.19860321703 . № 18. (18 страниц)
- Дрезиг, Фрэнк (1992). – Теория и применение в логическом синтезе Группировка . Отчеты о ходе работ ВДИ, Сер. 9 (на немецком языке). Том 145. Дюссельдорф, Германия: VDI-Verlag . ISBN 3-18-144509-6 . ДНБ ИНН 940164671 . (Примечание. Также: Хемниц, Технический университет, диссертация.) (147 страниц)
- Шеринг, Райнер; Велан, Герберт «Ганс» (1993). «Управление дискретными системами событий с помощью булевого дифференциального исчисления». В Балеми — Сильвано; Козак, Петр; Смединга, Рейн (ред.). Дискретные событийные системы: моделирование и управление . Прогресс в теории систем и управления (PSCT). Том. 13. Базель, Швейцария: Birkhäuser Verlag . стр. 79–93. дои : 10.1007/978-3-0348-9120-2_7 . ISBN 978-3-0348-9916-1 . (15 страниц)
- Постхофф, Кристиан; Штайнбах, Бернд [на немецком языке] (4 февраля 2004 г.). Логические функции и уравнения - бинарные модели для информатики (1-е изд.). Дордрехт, Нидерланды: Springer Science + Business Media BV doi : 10.1007/978-1-4020-2938-7 . ISBN 1-4020-2937-3 . ОСЛК 254106952 . ISBN 978-1-4020-2937-0 . (392 страницы)
- Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (12 февраля 2009 г.). Логические функции и уравнения - примеры и упражнения (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 году.)
- Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (1 июня 2010 г.). «Булево дифференциальное исчисление – теория и приложения» . Журнал вычислительной и теоретической нанонауки . 7 (6). Американские научные издательства: 933–981. дои : 10.1166/jctn.2010.1441 . ISSN 1546-1955 . (49 страниц)
- Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (15 января 2010 г.) [2009]. «Глава 3: Булево дифференциальное исчисление». В Сасао — Цутому; Батлер, Джон Т. (ред.). Прогресс в применении булевых функций . Синтезирующие лекции по цифровым схемам и системам (1-е изд.). Сан-Рафаэль, Калифорния, США: Издательство Morgan & Claypool. стр. 55–78 , 121–126. дои : 10.2200/S00243ED1V01Y200912DCS026 . ISBN 978-1-60845-181-4 . S2CID 37053010 . Лекция №26. (24 из 153 страниц)
Внешние ссылки
[ редактировать ]- Велан, Герберт «Ганс» (6 декабря 2010 г.). «Булево дифференциальное исчисление» . В Хазевинкеле, Михил (ред.). Булево дифференциальное исчисление — Математическая энциклопедия . Энциклопедия математики . Springer Science+Business Media . ISBN 978-1-4020-0609-8 . Архивировано из оригинала 16 октября 2017 г. Проверено 16 октября 2017 г.
- Институт компьютерных наук (IfI) (2017). «XBOOLE» . ТУ Бергакадемии Фрайберга . Архивировано из оригинала 31 октября 2017 г. Проверено 31 октября 2017 г. с «XBOOLE-монитор» . 23 июля 2008 г. Архивировано из оригинала 31 октября 2017 г. Проверено 31 октября 2017 г.