МОСКОВСКАЯ ФИНАНСОВО-ЮРИДИЧЕСКАЯ АКАДЕМИЯ
Согласовано на уч. год Начальник УМУ__________________ «_____»_______________2009 г. |
Дисциплина: Дискретная математика и теория нечетких множеств
Специальность (направление): Информатика в экономике
Форма обучения: все
Программа для подготовки к зачету
КОМПЛЕКТЫ МАТЕРИАЛОВ ДЛЯ ПОДГОТОВКИ К ЗАЧЕТУ.
ДЛЯ ВСЕХ ФОРМ ОБУЧЕНИЯ
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Список тем, выносимых на зачет.
1. Понятие множества. Пустое множество. Наиболее употребляемые множества.
2. Множества и отношения. Подмножество.
3. Операции над множествами.
4. Алгебра множеств.
5. Сравнение множеств.
6. Упорядоченные множества.
7. Свойства и отношения.
8. Отображения.
9. Решетки.
10. Основные правила комбинаторики.
11. Перестановки, сочетания, размещения, размещения с повторениями.
12. Биноминальные коэффициенты.
13. Алгебра Буля.
14. Формулы алгебры логики.
15. Функции алгебры логики.
16. Нормальные формы булевой функции (КНФ, ДНФ).
17. СДНФ. СКНФ.
18. Двойственность алгебры логики.
19. Многочлен Жегалкина, классы Поста, теорема Поста.
20. Полнота логических связок.
21. Электронные логические элементы.
22. Язык логики высказываний.
23. Понятие семантики в логике высказываний.
24. Операции логики высказываний.
25. Нормальные формы логики высказываний (КНФ, ДНФ).
26. Таблица истинности для формулы.
27. Метод резолюции.
28. Теоретико-множественная форма представления предложения.
29. Понятие предиката.
30. Кванторы.
31. Язык логики предикатов.
32. Подстановка. Композиция.
33. Интерпретация и истинность в логике предикатов.
34. Унификация в логике предикатов.
35. Тавтология, выполнимость и противоречие в логике высказываний и предикатов.
36. Предварённая нормальная форма.
37. Сколемовская нормальная форма.
38. Метод резолюции в логике предикатов..
39. Графы. Основные понятия и определения.
40. Изоморфизм графов.
41. Маршруты, цепи и циклы.
42. Матричное задание графов.
43. Связность. Компоненты связности.
44. Степень вершин графа, орграфа.
45. Поиск маршрута в графе.
46. Поиск путей (маршрутов) с минимальным числом дуг (рёбер).
47. Минимальные пути (маршруты) в нагруженных орграфах (графах).
48. Эйлеровы графы.
49. Гамильтоновы графы.
50. Деревья.
51. Остовное дерево графа.
52. Понятия неопределенности и четкости.
53. Функция принадлежности.
54. Частично упорядоченные множества.
55. Нечеткие множества.
56. Нечеткие логики.
57. Нечеткие отношения.
58. Нейро-нечеткие системы.
Вопросы, составленные на указанные темы, могут использоваться для оценки знаний студентов на семинарских занятиях, для промежуточной аттестации, а также для самопроверки при самостоятельном изучении курса.
ПРАКТИЧЕСКАЯ ЧАСТЬ
Типовые задачи.
Множества.
1. Доказать тождества.
а) (АÇВ)È(АÇ
)=А; б) А\В=АÇ
2. Найдите множество Х, удовлетворяющее следующему равенству 
.
3. Доказать тождество.
(АÈВ)Ç(АÈ)=А
4. Верно ли, что 
.
5. Доказать тождество.
(
ÈВ)ÇА=АÇВ
6. Верно ли, что 
.
7. Доказать Тождество.
(А\В)\С=(А\С)\(В\С)
8. Верно ли, что если 
и 
, то, В = С.
9. Докажите 
(символ 
означает «тогда и только тогда, когда»).
10. Докажите 
(символ означает «тогда и только тогда, когда»).
11. Доказать тождество.
АÈ(В\С)=(АÈВ)Ç(АÈ
)
12. Докажите 
(символ означает «тогда и только тогда, когда»).
13. Доказать тождество.
(А\В)È(
)=(АÈВ)\(АÇВ)
14. Докажите 
и 
(символ означает «тогда и только тогда, когда»).
15. Доказать тождество.
()È(
)=(АÈВ)\(АÇВ)
Комбинаторика.
1. Сколько существует способов разместить 3 человека на скамейке?
2. Сколько существует способов расставить 8 книг на полке так, чтобы 3 данные книги стояли вместе?
3. Сколькими различными способами можно выбрать три лица на три различных должности из 8 кандидатов?
4. Сколькими способами можно выбрать 3 лица на 3 одинаковые должности из 8 кандидатов?
5. Сколько различных 6-ти значных чисел можно записать с помощью цифр 1;1;2;2;2;3?
6. Cколько различных перестановок букв можно сделать в словах: замок, ротор, топор, колокол?
7. Сколько прямых можно провести через 8 точек, никакие 3 из которых не лежат на одной прямой, так чтобы каждая прямая проходила через 2 точки?
8. Сколько различных шестизначных чисел, начинающихся цифрой 2 и оканчивающихся цифрой 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что каждая цифра в обозначении числа встречается 1 раз?
9. Найти m и n, если 
.
10. Вычислить: 
.
11. Сколько существует кодовых комбинаций в замке, имеющем 5 дисков и на каждом диске 6 цифр.
Булевы функции.
1. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.
2. Доказать, что формула тождественно равна 0 или 1.
3. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований.
Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.
4. Доказать, что формула тождественно равна 0 или 1.
5. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.
6.. Упростить формулу. 
7. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.
8. Упростить формулу. 
9. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “ИЛИ-НЕ”.
10. Доказать равносильность. 
11. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “ИЛИ-НЕ”.
12. Доказать равносильность. 
. 13. Известно, что х=1. Что можно сказать о значении:
и 
.
14. Известно, что 
. Что можно сказать о значении:
.
15. Известно, что 
, а 
. Что можно сказать о значении:
Логика высказываний.
1. Доказать, что высказывание логически ложно.
а. А®В)Ù(В®С)Ù(АÙØС);
б. (Ø(АÙВ)Ù(А®В)ÙА;
в. ØАÚ(ВÙØВ))«А.
2. Доказать, что высказывание логически истинно.
а. Ø(АÙВ)«(ØАÚØВ).
б. (АÙ(А®В))®В.
в. Ø(АÙВ)«ØАÚØВ
3. Докажите, что высказывание является тавтологией.
а. (А→В)Ú(А®ØВ)
б. АÚ(ВÙØВ)«А.
в. (А®В)«(ØВ®ØА).
4. Найти означивания при которых формула истинна.
а. А®(А®В).
б. (А®В)«(В®ØА).
в. (АÚВ)«(ØАÙØВ).
5. Методом резолюции доказать, что множество S противоречиво.
а. S={ØAÚBÚD, ØBÚDÚA, ØDÚA, AÚB, BÚØD, ØAÚØB}.
б. S={ØAÚB, ØBÚC, ØCÚA, AÚC, ØAÚØC}.
в. S={AÚBÚC, AÚBÚØC, AÚØB, ØAÚØC, ØAÚC}.
6. Методом резолюции доказать, что
а. {A®B, C®D, D®B, BÚCÚD}├ BÚC.
б. {AÙB®C, A®B} ├ A®C.
7. Представьте следующее высказывание как множество дизъюнктов.
а. А«(ØВÙØС).
б. Ø((АÙВ)«С).
8. Определить выполнимо ли множество. Если да, то найти означивания подтверждающие его выполнимость.
а. {{A, B}, {ØA, B}}.
б. {{ØA}, {A, B}, {B}}.
9. Определить множество резольвент дизъюнктов S.
а. S={{A,ØB}, {A, B}, {ØA}}
б. S={{A}, {B},{ØA,ØB}}
в. S={{A}, {B},{A, B}}
Логика предикатов.
1. Выявить логическую форму предложения и записать её на языке логики предикатов.
а. “Каждый студент знает хотя бы некоторых преподавателей”.
б. “Неверно, что никто не знает русского языка.”
в. “Все любят Джейн, но она не любит ни кого.”
г. “Ничто не вечно”.
д. “Разность любых двух положительных чисел меньше суммы этих чисел”.
е. Если он мой отец, то он старше и мудрее меня.”
2. Запишите следующие высказывания на языке логики предикатов:
а. х – мать у, если х – женщина и родитель у.
б. х – отец у, если х – мужчина и родитель у.
в. х – человек, если его родитель человек.
г. х – человек, если отец х – человек.
д. Никто не родитель самому себе.
3. Привести к ПНФ и далее записать предложения в СНФ
а. ("х)Р(х)®($х)Q(х).
б. ("х)("у)[($z)P(x, y)ÙР(x, z)]®($u)Q(x, y,u).
в. ("x)("y)[($z)P(x, y,z)Ù[($u)Q(x, u)®($u)Q(y, u)]].
4. Записать предложение в теоретико-множественной форме.
а. ($x)("y)($z)[(P(x, y)ÚØQ(x)ÚR(z))Ù(ØP(x, y)ÚØQ(x))Ù(ØP(x, y)ÚR(z))].
б. Ø("х)($y)[P(x, y)®Q(y)].
в. Ø[("x)P(x)®($y)("z)Q(y, z)].
5. Если множество дизъюнктов S предложения унифицируемо, то найти НОУ
а. S={{P(a, x, h(g(z)))}, P(z, h(y), h(y))}}.
б. S ={{любит(w,¦(у))}, {любит(Джон, футбол)}}.
в. S={{Q(¦(w), a, z)}, Q(w, b, ¦(z))}.
г. S={{R(w, y), Q(w, ¦(z),z), ØR(w, w)}, {R(w, z), ØQ(¦(w),w, z)}}.
д. S={{P(¦(x),a)},{P(y,¦(w))}}.
Графы.
1. Найти минимальный путь из v1 в v6 методом «фронта волны».
2. Найти минимальный путь из v1 в v7 в орграфе, заданном матрицей смежности методом «фронта волны».
А(D) = 
3. Определить минимальный путь из v1 в v7 в нагруженном орграфе D с числом дуг не более 5.
С(D) = 
4. Проверить существуют ли в мультиграфе, заданном матрицей смежности, эйлеровы цепи и циклы, если да то найти их.
A(G) = 
, A(G) = 
УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ.
Базовые учебные пособия.
1. 20. , Осипова дискретной математики. М.: Изд. МАИ. 19с.
2. , Элементы дискретной математики. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ 20с.
3. Дискретная математика для программистов. СПб: ПИТЕР. 20с.
4. , , Фомин задач по алгебре и теории чисел. М.: Просвещение. 19с.
5. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: ФИЗМАТЛИТ. 20с.
6. Игошин и упражнения по математической логике и теории алгоритмов. М. Академия. 200с.
