Читать онлайн «Дискретная математика. Булева алгебра, комбинационные схемы, преобразования двоичных.»

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ И. Л. Ерош ДИСКРЕТНАЯ МАТЕМАТИКА БУЛЕВА АЛГЕБРА, КОМБИНАЦИОННЫЕ СХЕМЫ, ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Учебное пособие Ñàíêò-Ïåòåðáóðã 2001 УДК 519. 6(075) ББК 22. 19 E78 Ерош И. Л. Е78 Дискретная математика. Булева алгебра, комбинационные схемы, пре- образования двоичных последовательностей: Учеб. пособие/СПбГУАП. СПб. , 2001. 30 c. Приводятся методы анализа и синтеза булевых выражений, примеры реализации комбинационных схем, построенных по словесному описа- нию алгоритма функционирования. Рассмотрены булевы преобразова- ния двоичных последовательностей и показана возможность использова- ния этих преобразований при решении некоторых задач криптографии. Пособие ориентировано на студентов технических университетов, ас- пирантов и преподавателей дисциплины “Дискретная математика“ техни- ческих вузов. Рецензенты: кафедра радиосистем Санкт-Петербургского электротехнического университета; канд. техн. наук доц. В. Н. Сасковец Утверждено редакционно-издательским советом университета в качестве учебного пособия © СПбГУАП, 2001 © И. Л. Ерош, 2001 2  Предисловие Цифровые устройства (цифровые автоматы) обычно делятся на два класса: автоматы без памяти (однотактные автоматы, комбинацион- ные схемы) и автоматы с памятью (многотактные автоматы). Комби- национные схемы составляют основу дискретных вычислительных и управляющих устройств. Они могут выполнять как самостоятельные функции: преобразователи кодов, дешифраторы и т. п. , – так и входить в состав цифровых автоматов с памятью, реализуя функции переключе- ния элементов памяти в новые состояния, выработку логических и уп- равляющих сигналов. Сами элементы памяти могут быть построены в виде комбинационных схем с обратными связями. В настоящем учебном пособии в краткой форме изложены основные понятия и методы построения однотактных цифровых устройств конт- роля и управления, логика работы которых описывается булевыми фун- кциями. Булевы преобразования двоичных последовательностей выде- лены в самостоятельный раздел, в котором описаны возможные облас- ти применения булевых преобразований при решении некоторых задач защиты информации. 3  1. БУЛЕВЫ ФУНКЦИИ И КОМБИНАЦИОННЫЕ СХЕМЫ 1. 1. Понятие о булевых функциях. Булевы функции одного и двух аргументов Булевыми функциями (функциями алгебры логики) называют фун- кции, аргументы которых, так же как и сама функция, принимают только два значения – 0 или 1.