Введение

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

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

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

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

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

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

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

Следующая >