ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ

ТЕМАТИЧЕСКИЙ ОБЗОР*

ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ

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

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

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

|же объект может рассматриваться с двух точек зрения и в зависимости от этого выбирается непрерывная или дискретная модель. Сегодня ДМ является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов -обязательное квалификационное требование к специалистам в области информатики.

Знание дискретной математики необходимо для создания и эксплуатации интегрированных систем обработки информации и их компонент (математического обеспечения, пакетов прикладных программ, распределенных банков данных, сетей передачи данных, систем с разделением ресурсов и распределенной обработкой информации).

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

Еще в доньютоновский период появились простейшие понятия комбинаторики (П.Ферма, Б.Паскаль, Франция, XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи сисследованиями в области азартных игр. Л.Эйлер в середине XVIII в. закладывает основы теории графов; в середине XIX в. Дж. Буль, опираясь на некоторые идеи Г.Лейбница, придумывает свою "универсальную алгебру" в продолжение наметившегося еще в средние века стремления к формализации аристотелевой логики. Конец XIX в., характеризующийся, с одной стороны, обобщающе-синтетическим подходом к различным разделам математики, а с другой - стремлением к строгости математических обоснований, дает толчок к созданию и быстрому расцвету математической логики.

Основным поставщиком задач и идей для ДМ в XX в. становится кибернетика, а универсальным вычислительным средством - ЭВМ Задачи анализа и конструирования сложных систем послужили стимулом для разработки теории графов; задачи хранения, обработки и передачи информации привели к теории кодирования (дискретной теории информации); задачи оптимизации вызвали появление дискретного программирования (методы исследования и решения экстремальных задач на конечных множествах); исследование основных понятий вычислительной математики - вычислимости и алгоритма -стимулировало появление теории алгоритмов и теории сложности.

* * *

Напомним некоторые основные понятия базового курса [10]. Множество- это совокупность объектов, называемых

Элементамимножества: записьобозначает принадлежность

принадлежит А . Множествоне содержащее ни одного элемента, называется пустым Равенство множеств А и В (запись А = В) означает, что А и В состоят из… подмножеств любого множества В - пустое множество 0 и само В . Множества А и В…

Высказываниемназывается любое повествовательное предложение, относительно которого имеет смысл утверждать либо, что оно истинно,либо, что оно ложно(установить истинность того или иного высказывания бывает не просто, - иногда для этого нужно решить серьезную задачу). Предложение, содержащее переменную, при различных значениях которой оно становится истинным или ложным, называется неопределенным высказыванием.

Из простых высказываний p,q строятся сложныес помощью следующих основных логических операций:

конъюнкцияесть высказывание " р и q " (обозначенияили

), которое истинно тогда и только тогда, когда истинны оба составляющих высказывания p,q

дизъюнкция- высказывание "р или q" (обозначение ),

истинное тогда и только тогда, когда истинно хотя бы одно из высказываний p,q

импликация- высказывание "если р , то q ", или "из р следует <7 " (обозначение), которое ложно тогда и только тогда, когда р

истинно, a q - ложно;

эквивалентность- высказывание " р эквивалентно q" (обозначение), истинное в том и только в том случае, если р и q

оба истинны, либо оба ложны.

Отрицанием высказывания р называется высказывание "не Р",

или "неверно, что р " (обозначение), истинное тогда и только

тогда, когда р ложно.

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

Неопределенному высказыванию Р(Х), содержащему переменную X, можно сопоставить высказывания ."для всех X Р(Х) истинно", обозначаемое, _и "существует X такое, что Р(Х) истинно",

обозначаемое такие операции называются кванторами:

квантором общности V и квантором существования- высказывание истинное, если для всякого (каждого, любого) X выполнено Р(Х) и ложное, если, напротив, существует , для котороголожно.- высказывание истинное, если хотя

бы для одного высказывание истинно, и ложное, если,

напротив, такогонет, т.е. для всех X Р(Х) ложно. ГЛАВА 1. ФУНКЦИОНАЛЬНЫЕ СООТВЕТСТВИЯ И ОТНОШЕНИЯ

Операции над множествами

Множество может быть задано перечислением его элементов, либо указанием характерного свойства, которым обладают элементы множества и только они.

Определить, обладает ли тот или иной объект заданным свойством' и тем более найти все такие объекты, может быть сложной задачей/ Например, найти множество корней уравнения означает решить' уравнение. Решение вопроса о том, существует ли процедура распознавания тех или иных свойств математических объектов, относится к проблемам теории алгоритмов.

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

Перечислим основные свойства этих операций. Пусть U -универсальное множество, А, В, С - его подмножества,- пустое множество. Равенства 1-10, 15-18 относятся к операциям объединения и пересечения; равенства 11-14 и 19-21 - к операции дополнения.

Приведем также ряд свойств операции разности множеств.

Еще один способ задания множества связан с понятием

Порождающей процедуры

Задавая различные значения параметра k, мы можем вычислять элементы множестваи… может быть явным, как в данном примере, или неявным, требующим разрешения. В частности, используются возвратные,или…

Суперпозиция функций

соответствует а . Множество всех соответствующих элементу , называется образомэлемента а . Множество всехкоторым соответствует элемент,… прообразомэлемента b .

Бинарные отношения

квадратами, как 4, 81, 144, или не быть ими, как 5, 30, 48. Это свойство, или признак числа можно трактовать как принадлежность к определенному подмножеству натуральных чисел - полных квадратов

Отношения порядка

обозначение - (а предшествует Ь). Примерами могут служить отношения "больше", "меньше", "старше" и т.п.… Отношение нестрогого порядка -бинарное рефлексивное, антисимметричное и транзитивное отношение. Наряду с естественными…

ГЛАВА 2. ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫ

Операции на множестве

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

/i-арная операция на множестве М - отображение типа: , гдеМ - произвольное множество, не обязательно числовое; обозначение:. Для п — 1 операция

называется бинарной и вместоупотребляется

a-b, fib ит.п.).

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

МножествоМ называется замкнутым относительно операции

если выполнено условие , т.е. применение

операции не выводит за пределы множества М .

Примеры.1) Множества действительных, рациональных, целых чисел замкнуты относительно операций сложения, вычитания, умножения, причем первые два множества замкнуты и относительно операции деления (исключая деление на 0). Множество целых чисел не замкнуто относительно деления.

2) Множество четных целых чисел замкнуто относительно операций сложения и умножения: сумма и произведение четных чисел также четны. Напротив, множество нечетных чисел не замкнуто относительно тех же операций.

Если для некоторой операциирассмотреть отношениееслиили , то для любых двух элементов

множества, замкнутого относительно операции, выполнено , где - транзитивное замыкание отношения

Свойства бинарных операций

' позволяет записывать последовательность таких операций без скобок: f . Ср. в арифметике формулы. Примером U ассоциативных операций служат объединениеи пересечение множеств. '• Операция… Г Коммутативной бинарной операциейназывается операция,

Алгебры

множество М вместе с заданной на нем системой операций называется сигнатурой алгебры, а Л/ - носителем. Обозначение.

Операции над двоичными числами

Каждому с детства привычен способ записи чисел в десятичной системе. Эта система называется позиционной десятичной,потому что натуральное число представляется словом в алфавите из десяти

арабскихцифр , причем знаки числа изображают

различные его составляющие в зависимости от разряда- позиции в числе и служат коэффициентами при степенях 10. Например,

48087 = 40000 + 8000 + 80 + 7 = 4-Ю⁴+8-10³+0-10²+8-10'+7-10°, и цифра 8 во втором разряде изображает число 80, а та же цифра в четвертом разряде - число 8000. Позиционная система исторически

вытеснила другие способы представления чисел благодаря удобствам использования, главным образом, из-за достаточно простых алгоритмов арифметических действий над многозначными числами, которые сводятся к действиям над однозначными числами. При этом используются таблица сложения, т.е. правила типа 3+6=9, 4+8=12 и т.п., общеизвестная таблица умножения и - при сложении и умножении столбиком - правила переноса десятков в старшие разряды ("шестью девять - пятьдесят четыре; четыре пишем, пять в уме"). Отметим, что при сложении столбиком справа налево двух слагаемых каждый очередной знак суммы определяется знаками слагаемых в этом разряде с учетом знака переноса (0, если сумма не превышает 9, или 1, если сумма

двузначная). При умножении многозначных чисел Ах В столбиком каждое умножение А на однозначное число, каким является очередной

разряд числа В, также сопровождается переносом числа десятков в следующий разряд. Далее следует сложение нескольких многозначных чисел, записываемых со сдвигом. При сложении большого количества чисел может возникать накопление знаков переноса. Важно заметить, что как при сложении, так и при умножении каждый знак результата зависит от знаков слагаемых/сомножителей, находящихся в том же разряде и правее, и не зависит от старших разрядов (находящихся левее). Так, младший разряд результата является функцией двух однозначных чисел - младших разрядов слагаемых/сомножителей. Второй справа разряд есть функция 4 однозначных переменных - знаков двух младших разрядов слагаемых/сомножителей и т.д.

Таким же образом, только много проще, устроена двоичная система счисления.Числа представляются словами в алфавите

и, например, =

(подстрочные индексы 2 и 10

обозначают, что одно число записано в двоичной, а другое - в десятичной системе). Вот двоичные представления нескольких первых натуральных чисел (в левом столбце - десятичные; в правом -двоичные):

Подобно тому, как в десятичной системе счисления целые степени основания системы 10 записываются единицей с нулями, а число на 1

меньшее - 99...9, в двоичной системе числонулями изображает

число, а число 11...1 из k единиц равно

Таблица сложения для двоичных чисел чрезвычайно проста: 0 + 0 = 0; 0+1 = 1+0=1; 1 + 1 = 10. Таблица умножения еще проще:

0x0 = 0x1 = 1x0-0; 1x1 = 1.

Их можно представить и таблицами с двумя входами:

Отсюда- простота действий над многозначными числами, хотя двоичная запись числа длиннее десятичной более, чем втрое. Предыдущий пример демонстрирует перевод двоичного числа в десятичное. Для этого, так же как и для обратного перехода полезно знать значения целых степеней числа 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 и т.д. Например, 179 = 128 + 51 = 2⁷ +32 +19 = = 2⁷ + 2⁵ + 16 + 3 = 2⁷ + 2⁵ + 2⁴ + 2 + 1 поэтому двоичная запись числа 179 - 10110011 (слагаемые 2⁶,2³,2² входят в сумму 179 с коэффициентом 0, остальные степени 2-е коэффициентом 1). Ниже -примеры арифметических действий над двоичными числами (параллельно приведены действия с теми же числами в десятичной записи).

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

Однако накопление знаков переноса при сложении возникает здесь значительно чаще: каждые две единицы дают перенос одной единицы в следующий - старший - разряд, сложение четырех единиц дает две единицы переноса, т.е. перенос одной единицы на два разряда влево.

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

частного, остаток не должен быть меньше делителя, - в этом случае знак частного 1; в противном случае, как и для десятичных чисел он равен 0, и нужно приписать к остатку (снести) очередной разряд делимого.

Рассмотрим последовательностьвсех двоичных наборов длины

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

натурального ряда от 0 до. Для любогосумма k -го от

начала числаот концаравна одному и тому же числу

i, которое в двоичной записи^состоит из п единиц. При вычитании

из двоичного числалюбого меньшего числа не требуется

заимствования единиц из старших разрядов (подобно вычитанию из числа 99...9 в десятичной системе), и единице в вычитаемом соответствует ноль в разности, и наоборот, нулю в вычитаемом отвечает

единица в разности. Поэтому двоичные знаки числапротивоположны

соответствующим знакам числаДругими словами, таблица

антисимметрична относительно своей середины.

Таблица, строки которой суть наборы из 0 и 1 длины п , может быть построена по индуктивному правилу:

1) таблица- это столбец из двух однозначных чисел 0 и 1;

2) таблица получается из двух экземпляров таблицы : к

первому из них присоединяется слева столбец из нулей, а ко

второму - столбец из единиц. Расположенные одна под другой,

обе таблицы образуют таблицустрок.

ГЛАВА 3. БУЛЕВЫ ФУНКЦИИ

Представления логических функций

- функциональный язык. Будем считать простые высказывания независимыми переменными, сопоставив истинным высказываниям значение 1, а ложным -… ! высказываниями представляют собой функции этих переменных Введем F необходимые понятия.

Булева функция (логическая функция, функция алгебры

I, гдеZ - логические переменные, ' т.е. и значения аргументов, и значение функции - ноль или единица . Тем… 'равны 0 или 1:. Можно применять векторные обозначения

Логические формулы. Булева алгебра

функций меньшего числа переменных, прежде всего через функции 1 и 2 переменных. Формулы алгебры логики (пропозициональные формулы) - формулы, построенные из знаков переменных и знаков функциональных операций с соблюдением определенных правил…

Дизъюнктивные нормальные формы

в виде | Справедливостьэтого тождества следует из того, что оба слагаемых, связанных знаком дизъюнкции, не могут одновременно…

ГЛАВА 4. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ

Замкнутые классы булевых функций

символы переменных Еще один интересный пример дает система функций (1) Выше показано, что. Используя это равенство и закон

I §2. Предполные классы

1) Класс - класс функций, сохраняющих 0, т.е. функций, для которых. Замкнутость класса очевидна: если в функцию вместо некоторых переменных подставить функции, принадлежащие , то на нулевом наборе

Критерий полноты системы булевых функций

/

—Рассмотренные 5 классов функций используются при решении Вопроса о функциональной полноте

Критерий полноты системы булевых функций (теорема

Принадлежащая этому классу, иначе говоря, системаполна, если рыполнены5 условий Функции - не обязательно различные Предварительно рассмотрим 3 утверждения, которые 'демонстрируют, как суперпозициями функций системы, удовлетворяющей…