Введение. Дискретная математика – часть математики, которая зародилась в глубокой древности

Дискретная математика – часть математики, которая зародилась в глубокой древности. Главной её спецификой является дискретность, т.е. антипод непрерывности. В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика, а также ряд разделов, которые наиболее интенсивно стали развиваться в середине 20-го века благодаря научно-техническому прогрессу, поставившему изучение сложных управляющих систем. В узком смысле дискретная математика ограничивается только этими новыми разделами. К упомянутым новым разделам мы относим: теории функциональных систем, теорию алгоритмов, теорию конечных автоматов и т.п. Именно эти разделы дискретной математики и рассматриваются в данном курсе.

Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования.

Главной задачей курса лекций является овладение студентами методами и мышлением, характерными для дискретной математики. Материал, вошедший в курс, знакомит студентов с теорией булевых функций, теорией конечных автоматов, теорией алгоритмов и алгебры логики предикатов. Данный курс лекций составлен таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество серьезных теорем.

Раздел теории булевых функций является основополагающим при изучении дискретной математики. В лекционном курсе и на практических занятиях ему отводится около четверти всего учебного времени. На материале этого раздела студенты получают первоначальное представление о таких понятиях, как булева функция, операция суперпозиции, функционально полная система. Студенты знакомятся с различными способами заданий булевых функций (табличный способ, представление полиномами и нормальными формами, геометрическое представление с использованием трехмерного куба); изучают применение исследования полноты и замкнутости систем функций, изучают одно из приложений теории булевых функций – релейно-контактные и релейно-логические схемы.

В разделе алгебры логики предикатов излагаются основные сведения из теории предикатов. Данная теория представляет собой более точный инструмент по сравнению с теорией высказываний, которая рассматривается в первом разделе.

В разделе конечные автоматы изучаются детерминированные и ограниченно-детерминированные функции.

В разделе элементы теории алгоритмов изучается строгое математическое определение теории алгоритмов, предложенное Тьюрингом – машина Тьюринга; примитивно-рекурсивные и частично-рекурсивные функции, а также устанавливается их связь с функциями вычислимыми по Тьюрингу.