- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Замечания.
1. Учитывая, что существуют определённые аналитические преобразования одного логического базиса в другой, можно изображать схемы в любом логическом базисе и преобразовывать их в другие. Базис, состоящий из логических функций , ∧, ∨ называется нормальным; из логических функций ù, ∨ или ù, ∧ – неполным нормальным; из стрелки Пирса х ↓ у – базисом Вебба; из штриха Шеффера х ∣ у – базисом Шеффера.
Как известно, базис Вебба и базис Шеффера связаны с нормальным базисом следующими аналитическими соотношениями:
х ∣ у = ∨ ; и обратно, = х ∣ х; х ∨ у = (х ∣ х)∣(у ∣ у);
х ↓ у = ∧ ; и обратно, = х ↓ х; х ∧ у =(х ↓ х) ↓ (у ↓ у).
Переход от схемы в нормальном базисе к базисам Шеффера и Вебба и обратно, например, можно отобразить в следующей таблице (таблица 5.1).
Таблица 5.1.
Нормальный базис |
Базис Шеффера |
Базис Вебба |
не |
|
|
и
|
|
|
или
|
|
|
2. Логические функции, кроме их реализации функциональными схемами, реализуются также контактными, релейно-контактными и интегральными схемами.
3. Одна и та же схема (функциональная, контактная, релейно-контактная, интегральная) может быть реализована большим или меньшим числом функциональных базисных элементов (функций), для уменьшения которых, реализующих одну и ту же булеву функцию, разработана теория минимизации нормальных форм.
-
Основные понятия булевых функций.
Теорема.
Число всех различных булевых функций от n аргументов равно .
Доказательство:
Число различных наборов переменных x1, x2, … , xn, где xi {0,1} равно k=2n. Так как каждая булева функция принимает только 2 значения: 0 или 1, то число всех булевых функций от n переменных равно , что и требовалось доказать.
Определение.
Операцией сложения по модулю два, которая обозначается знаком , на множестве из двух элементов 0 и 1 называется операция со следующим законом композиции:
для a имеет место
a a ≐ 0 ; a 0 0 a a .
Определение.
Элементарными булевыми функциями называются следующие функции:
e1(x) 0 – нуль-функция;
e2(x) 1 – единица-функция;
e3(x) x – функция x;
e4(x) = ù x – отрицание x;
e5(x, y) ≐ – конъюнкция x и y;
e6(x, y) ≐ – дизъюнкция x и y;
e7(x, y) ≐ x y – импликация x и y;
e8(x, y) ≐ x y – эквиваленция x и y;
e9(x, y) x y – сложение по модулю два x и y.
Замечания.
1. Таблица истинности для элементарных булевых функций имеет вид, представленный в табл. ниже.
Таблица
2. Заметим, что
1) x y = ù ( x y), то есть e9(x, y) = e4(e8(x, y)), то есть функция xy является суперпозицией функций xy и ù x.
2) – суперпозиция функций и , каждая из которых от двух переменных.
3) 0 = ù (ù x); 1=ù x.
Приоритеты логических операций.
Операция ù имеет больший приоритет, чем ;
Операция имеет больший приоритет, чем ;
Операция имеет больший приоритет, чем ;
Операция имеет больший приоритет, чем ;
Операция имеет больший приоритет, чем .
Примеры функций, являющихся суперпозициями элементарных функций.
g1(x1, x2, x3, x4) ≐ ù x4
g2(x1, x2, x3) ≐ ù x2)
g3(x1, x2) ≐ ù
Определение.
Пусть
1) u – переменная, при этом пусть u0= ù u, а u1=u;
2) ai {0,1} , ;
3) u1, u2, … , un – переменные, причём не обязательно различные.
Тогда формула называется элементарной конъюнкцией, а – элементарной дизъюнкцией.
Примеры.
1. Элементарными конъюнкциями будут следующие формулы:
x, y, ù x, x y, x1 x1, , , , .
2. Элементарными дизъюнкциями будут следующие формулы:
x, y, ù y, x y, x x x, , , ,.
Ясно, что каждая элементарная конъюнкция и каждая элементарная дизъюнкция являются суперпозициями функций ù x, x y и x y.
Замечание.
Принимая для переменной u , что и , замечаем, что ua = 1 u = a, a{0,1}.
В этом случае :
1) функция
Kn(x1, x2,…, xn) = (1)
такая, что Kn(a1, a2,…, an) = 1 и Kn(b1, b2,…, bn) = 0, если
(b1, b2,…, bn) (a1, a2,…, an);
2) функция
dn(x1, x2,…, xn)= (2)
такая, что dn() = 0 и dn(b1, b2,…, bn) = 1, если
(b1, b2,…, bn) ().
При этом в формулах (1) и (2) все переменные попарно различны.