- •Г.С. Розаренов, в.А. Шаруда дискретная математика Учебное пособие
- •Воронеж 2008
- •Воронеж 2008
- •Введение
- •1. Множества
- •1.1. Основные понятия
- •Упражнения
- •1.2. Операции над множествами
- •Упражнения
- •1.3. Диаграммы Венна
- •Упражнения
- •1.4. Доказательства
- •Упражнения
- •1.5. Векторы, прямые произведения, проекции векторов
- •Упражнения.
- •2. Алгебра логики
- •2.1. Функции алгебры логики
- •2.2. Формулы. Реализация функций формулами
- •2.3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
- •2.4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
- •2.5. Полнота и замкнутость
- •2.6. Проблема минимизации булевых функций
- •Упражнения.
- •2.7. Упрощение д.Н.Ф. Тупиковые (относительно упрощения) д.Н.Ф.
- •Упражнения.
- •3. Язык логики предикатов
- •3.1. Основные понятия логики предикатов
- •3.2. Истинные формулы и эквивалентные соотношения
- •Упражнения.
- •4. Теория графов
- •4.1.Основные понятия
- •Г раф изоморфен
- •4.2. Способы задания графов
- •Матрица инцидентности (ij)
- •4.3. Операции над частями графа
- •4.4. Маршруты, пути, цепи, циклы
- •4.5. Дерево и лес
- •4.6. Сети
- •Упражнения.
- •5. Введение в теорию алгоритмов
- •5.1. Предварительные обсуждения
- •5.2. Блок-схемы алгоритмов
- •5.3. Машины Тьюринга
- •5.4. Некоторые операции над машинами Тьюринга
- •5.5. Рекурсивные функции
- •6. Автоматы
- •6.1. Определение основных понятий
- •6.2. Изоморфизм и эквивалентность автоматов
- •6.3. Сети из автоматов
- •6.4. Синхронные сети
- •6.5. Программная реализация логических функций
- •Заключение
- •394026 Воронеж, Московский просп., 14
1. Множества
Состав объекта исследования может быть представлен в виде дискретного множества. Множество - основное понятие в теории множеств, которое вводится без определения. О множестве известно как минимум, то, что оно состоит из элементов.
1.1. Основные понятия
Множество - состоит из элементов. Принадлежность элемента а множеству М обозначается а М ("а принадлежит М"), непринадлежность - а М или а М.
Множество А называется подмножеством множества В (обозначается А В ), если всякий элемент из А является элементом В (рис 1). Если А В и А В, то А называется строгим (собственным) подмножеством (обозначается А В).
Содержательные примеры множеств и их возможные обозначения:
Рис. 1
А - множество сотрудников фирмы "Элегант";
М1 - множество всех операций (работ) по сборке компьютера;
М2 - множество видов услуг, предоставляемых фирмой "Силуэт";
N- множество натуральных чисел 1, 2, 3, ... ;
N1 - множество натуральных чисел, не превосходящих 100;
R - множество всех действительных чисел и т.д.
Два определения равенства множеств:
I. Множества А и 5 равны (А = В), если их элементы совпадают.
II. Множества А и В равны, если А В и В А.
Множество, состоящее из конечного числа элементов, называется конечным, в противном случае - бесконечным (например, множества N,R- бесконечные множества). Число элементов в конечном множестве М называется его мощностью и обозначается .
Множество мощности 0, т.е. не содержащее элементов, называется пустым (обозначается ): | | = 0. Принято считать, что пустое множество является подмножеством любого множества.
Способы задания множеств:
• Перечислением, т.е. списком своих элементов. Списком можно задать лишь конечные множества. Обозначение списка - в фигурных скобках. Например, множество А устройств домашнего компьютера, состоящего из процессорного блока а, а также периферийных устройств В (монитора b, клавиатуры с и принтера d), может быть представлено списком:
А = {а, В} или А = {а, b, с, d}.
(Задание типа N = 1 , 2, 3, ... - не список, но лишь допустимое условное обозначение..)
• Порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. В таком случае элементами множества являются все объекты, которые могут быть построены с помощью такой процедуры. Например, множество всех целых чисел, являющихся степенями двойки , n N, где N - множество натуральных чисел, (допустимое обозначение = 1 , 2, 4, 8, 1 6,...) может быть представлено порождающей процедурой, заданной двумя правилами, называемыми рекурсивными, или индуктивными:
а) 1 ; б) если m , то 2m .
• Описанием характеристических свойств, которыми должны обладать его элементы; обозначается:
М= {х | Р(х)} или М= {х : P(x)}
("Множество М состоит из элементов х таких, что х обладает свойством P") Например, множество А периферийных устройств персонального компьютера PC может быть определено:
А = {х: х - периферийное устройство персонального компьютера PC}.
Если свойство элементов множества М может быть описано коротким выражением, это упрощает его символьное представление. Например, множество всех натуральных четных чисел может быть представлено:
= {х:х = 2п, n N}.
Надежным способом точно описать свойство элементов данного множества является задание распознающей (разрешающей) процедуры. Она должна устанавливать для любого объекта х, обладает ли он данным свойством Р (и, следовательно, принадлежит множеству) или нет. Например, распознающей процедурой для множества А всех сотрудников фирмы "Квант", имеющих удостоверение фирмы, является проверка его наличия. Тогда множество А может быть представлено более точно: "А - множество всех сотрудников фирмы «Квант», имеющих соответствующее удостоверение фирмы".
Еще пример: для описания характеристического свойства элементов множества всех целых чисел, являющихся степенями двойки ("быть степенью двойки"), разрешающей процедурой может служить любой метод разложения целых чисел на простые множители. Тогда а , если а = 1 или если а - 2 х 2 х ... х 2 = 2n, п N.
Пример 1. Задать различными способами множество N всех натуральных чисел: 1, 2, 3, ...
Списком множество N задать нельзя ввиду его бесконечности.
Порождающая процедура содержит два правила:
а) 1 N; б) если n N, то п+1 N
Описание характеристического свойства элементов множества N:
N = {х: х - целое положительное число} .
Пример 2. Задать различными способами множество М всех четных чисел 2, 4, 6, ..., не превышающих 100.
{2, 4, 6, ...,100}.
а) 1 N; б) если n N, то (п+2) ; в) n 98.
= {п: п - целое положительное число, не превышающее 100} или = {п:п N и n/2 N, n 100}.
Пример 3. Пусть U= {а, b, с}. Определить в явном виде (перечислением своих элементов) булеан (U) - множество всех подмножеств, состоящих из элементов множества U. Какова мощность множества (U) ?
(U) ={ , {а}, {b}, {с}, {а, b}, {а, с}, {b, с}, {а, b, с}}.
Мощность =8
Пример 4. Какие из приведенных определений множеств А, В, С, D являются корректными:
а) А ={1,2,3}, в)С={х:х А},
б) В ={5, 6, 6, 7}, г)D={A,C}?
Принадлежит ли число 1 множеству D)?
а) Определение множества А = { 1, 2, 3} списком своих элементов формально корректно.
б) При перечислении элементов множества не следует указывать один и тот же элемент несколько раз. Корректное определение В = {5, 6, 7}.
в) Определение множества С = {х: х А} заданием характеристического свойства его элементов "принадлежать множеству А" корректно, А = { 1 , 2, 3 } .
г) Определение списком множества D = {А, С} корректно: элементами множества D являются множества А и С. Однако 1 не принадлежит D, 1 D, так как элемент 1 не перечислен в списке.