Предисловие

Дискретная математика лишь в последнее время стала включаться в программу технических вузов, хотя необходимость владения ею современным инженером несомненна. Роль дискретной математики особенно велика для инженеров, работающих в области вычислительных устройств и автоматизированных систем управления.

В МИЭТ дискретную математику изучают студенты нескольких групп факультета МПиТК, а также факультетов ЭКТ, ИМЭ.

Данная книга соответствует курсу дискретной математики, читаемому в 4-м семестре студентам факультета МПиТК, и написана на основе опыта преподавания авторами этого предмета. Авторы считают, что ее использование в полном или частичном виде возможно и на других факультетах.

Книга содержит элементы математической логики (алгебру высказываний, высказывания с кванторами, предикаты), теорию булевых функций, теорию графов (включая потоки в сетях), автоматов, а также машины Тьюринга и рекурсивных функций. Не включены комбинаторика и теория кодирования. Комбинаторика изучается студентами факультета МПиТК в 5-м семестре в курсе теории вероятностей, а теория кодирования – в курсах лекций, читаемых кафедрой ИПОВС.

Авторы старались облегчить усвоение материала, снабжая изложение многочисленными примерами и разбирая типовые задачи. Кроме того, в каждой главе имеется большое количество упражнений для самостоятельного решения, к большинству из которых приведены ответы или указания.