Математическая логика и теория алгоритмов
.docФедеральное агентство по образованию
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ
(образован в 1953 году)
Кафедра физики и высшей математики
Дистанционное обучение |
Физ. мат. 8.11.230102 зчн.плн. Физ. мат. 8.11.230102 зчн. скр |
Физ. мат. 8.11.230102 очн.плн. Физ. мат. 8.11.230102 очн. скр |
А.Р. Садыкова
«Математическая логика
и теория алгоритмов»
Методические рекомендации
и контрольные задания для студентов специальности 230102 (2202) всех форм обучения
www.msta.ru
Москва – 2005
Методические рекомендации:
Процесс изучения предмета «Теория принятия решений» состоит из следующих этапов:
-
проработка установочных и обзорных лекций;
-
самостоятельная работа над учебниками и учебными пособиями;
-
систематическая работа над задачами в коде практических занятий;
-
самостоятельное решение задач из учебных пособий и задачников;
-
выполнение контрольных работ;
-
сдача зачета;
Предложенные контрольные задания являются приложением к учебно-практическому пособию по «Математической логике и теории алгоритмов» для студентов специальности 2202 (МГУТУ). Задачи распределяются по вариантам согласно следующей таблице:
Задания
Варианты |
1 |
2 |
3 |
4 |
5 |
I |
1 |
11 |
21 |
31 |
41 |
II |
2 |
12 |
22 |
32 |
42 |
III |
3 |
13 |
23 |
33 |
43 |
IV |
4 |
14 |
24 |
34 |
44 |
V |
5 |
15 |
25 |
35 |
45 |
VI |
6 |
16 |
26 |
36 |
46 |
VII |
7 |
17 |
27 |
37 |
47 |
VIII |
8 |
18 |
28 |
38 |
48 |
IX |
9 |
19 |
29 |
39 |
49 |
X |
10 |
20 |
30 |
40 |
50 |
Контрольные задания
-
Доказать, что если А есть множество корней уравнения и , то А=В.
-
Доказать, что Ø{Ø}.
-
Доказать тождества
а)
б)
в)
4. Доказать, что .
-
Доказать, что существует лишь одно множество, не имеющее элементов.
-
Дано генеалогическое древо (см. рис.). Выпишите упорядоченные пары, находящиеся в следующих отношениях на множестве Р членов этой семьи:
а)
б)
-
Множество определяет отношение на множестве . Найдите все упорядоченные пары, ему принадлежащие.
-
Постройте ориентированный граф отражающий упорядоченные пары, принадлежащие бинарному отношению на множествах и .
-
С помощью таблицы покажите упорядоченные пары бинарного отношения на множествах и .
-
Диаграмма Хассе частичного порядка R на множестве показана на рисунке. Перечислите элементы R и найдите минимальный и максимальный элементы частичного упорядоченного множества А.
-
Определите, какие из приведённых ниже отношений на Z являются рефлексивными, симметричными, а какие транзитными.
а) «х + у - нечётное»;
б) «х + у - чётное»;
в) «ху - нечётное».
-
Р: «Логика - забава»,
Q: «Сегодня пятница».
Выразите каждое из следующих составных (сложных) высказываний в символической форме.
а) Логика – не забава, и сегодня не пятница;
б) Сегодня не пятница, да и логика не забава;
в) Либо логика – забава, либо сегодня пятница.
-
С помощью таблицы истинности показать эквивалентность высказываний и
-
Дан предикат : «х – целое число и » Выразите словами высказывание: .
-
Постройте таблицу истинности для следующего высказывания .
-
Пусть P, Q и R – высказывания:
P: «Я умираю от жажды»,
Q: «Мой стакан пуст»,
R: «Сейчас три часа».
Запишите, каждое из следующих высказываний в символической форме:
а) Сейчас три часа и я умираю от жажды.
б) Если я умираю от жажды, то мой стакан пуст.
-
Х – кошка, : «у Х есть усы»
Запишите каждое из высказываний в символической форме.
а) «усы есть у всех кошек»;
б) «найдётся кошка без усов».
-
Докажите эквивалентность
~.
-
Постройте таблицу истинности
.
-
Докажите тождественную истинность
а)
б)
-
Покажите прямым способом, что произведение ху двух нечётных целых чисел х и у всегда нечётно.
-
Доказать .
-
Доказать ,
-
Прямым рассуждением докажите: если n и m – чётные, то n+m – чётное.
-
Доказать методом математической индукции , .
-
Доказать закон дистрибутивности .
-
Упростить с помощью карты Карно.
-
Упростить булеву функцию: .
-
Привести к Д.Н.Ф.
-
Привести к К.Н.Ф.
-
Найти Д.Н.Ф. и К.Н.Ф. булева выражения .
-
Изобразить карту Карно булева выражения с Д.Н.Ф.
и найдите его упрощенную версию.
33. Доказать: - группа.
34. Доказать: - не группа.
-
Постройте граф с множеством вершин и множеством рёбер .
-
Найдите циклы: а) два длины 5;
б) три длины 4;
в) два длины 3, в граф G.
-
Коммивояжер должен совершить поездку по городам вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижение к минимуму. Решите эту задачу, если её геометрическая модель имеет вид:
38. Изобразите орграф с вершинами и матрицей смежности
-
С помощью диаграмм Эйлера-Венна показать результат следующих операций
С
-
Доказать тождество: .
-
Множество определяет отношение на множестве . Найдите все упорядоченные пары ему принадлежащие.
-
Какие свойства выполняются для бинарного отношения «х+у - нечётное» на множестве R.
-
Докажите эквивалентность ~.
-
Запишите с помощью кванторов и предикатов следующее: «Яблоки либо сладкие, либо кислые».
-
Доказать, что кратно 2 при .
-
Упростить .
-
Найти Д.Н.Ф. по таблице
-
а в с
f
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1
0
0
1
0
0
-
Доказать, что - группа.
-
Найдите циклы в графе.
-
Изоморфны ли графы? Ответ обосновать.
Математика
«Математическая логика и теория алгоритмов»
Садыкова Альбина Рифовна
Подписано к печати:
Тираж:
Заказ №: