Скачиваний:   0
Пользователь:   prepod
Добавлен:   04.05.2015
Размер:   178.0 КБ
СКАЧАТЬ

 

РОССИЙСКИЙ НОВЫЙ УНИВЕРСИТЕТ

РосНОУ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЭКЗАМЕНАЦИОННЫЕ БИЛЕТЫ

ПО ДИСЦИПЛИНЕ

 

« Математическая логика и дискретная математика»

 

 

 

 

 

 

Обсуждены

на заседании кафедры

«_____» _______ ____г.

Протокол № _____

 

 

 

 

 

 

 

Зав. кафедрой                                                                       Крюковский А.С.

Билет №1

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Понятие множества. Элемент множества. Типы множеств, способы их определения, возможные проблемы при определении.

2. Двудольные графы. Примеры задач, описываемых двудольными графами. Условие разнообразия.

3. Докажите тождественную истинность или тождественную ложность формулы БИЛЕТЫ.

 

 

 

Билет №2

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Основные операции на множествах. Операции пересечения и объединения множеств, их свойства.

2. Независимое множество вершин. Число независимости. Примеры задач на поиск независимых множеств.

3. Пусть даны предикаты: A(x)= “x – не делится на 5”, B(x)= “x – четное число” и, C(x)=“x – число простое”, D(x)= “x – кратно 3”определенные на множестве N. Найти область истинности предикатов: БИЛЕТЫ; А(х) Ù В(х).

 

 

 

 

Билет №3

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Понятие подмножества. Универсальное множество. Дополнение множества. Разность и симметрическая разность множеств.

2. Алгоритм поиска кратчайших путей между вершинами графа. Пример.

3. Докажите рекурсивность функции БИЛЕТЫ.

 

 

 

 

Билет №4

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Понятие множества. Элемент множества. Равенство множеств. Мощность множеств.

2. Теорема о спросе и предложении.

3. Укажите свойства, которыми обладает отношение равномощности в произвольной системе множеств.

 

 

 

 

Билет №5

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Основные операции на множествах. Декартово произведение множеств.

2. Понятие алгоритма. Типы алгоритмов. Общие свойства алгоритмов.

3. Пусть БИЛЕТЫ и БИЛЕТЫ - любые предикаты. Какие из следующих формул равносильны формуле БИЛЕТЫ?

1. БИЛЕТЫ              2) БИЛЕТЫ                 3) БИЛЕТЫ                  4)БИЛЕТЫ     5)БИЛЕТЫ            6)БИЛЕТЫ                 7)БИЛЕТЫ

 

 

 

 

Билет №6

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Алгебра множеств.

2. Понятие неразделимого графа. Блок. Точка сочленения. Мост.

3. Найдите критический путь (см. приложение). Как сократить длительность работ на 3 дня, если длительность ни одного вида работ нельзя сократить более, чем на 35% от начальной величины (при этом все значения должны оставаться целыми числами)?

 

 

 

 

Билет №7

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Отображения и отношения на множествах. Типы отображений.

2. Раскраска графа. Хроматическое число. Гипотеза четырех красок.

3. Изобразите на координатной плоскости область истинности предиката: БИЛЕТЫ.

 

 

 

 

Билет №8

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Бинарные отношения, их свойства. Отношение эквивалентности.

2. Алгоритмическая разрешимость.

3. Для теоремы «если четырехугольник является прямоугольным, то в четырехугольнике диагонали равны» сформулируйте обратную, противоположную и противоположную обратной теоремы. Какие из них истинны?

 

 

 

 

Билет №9

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Бинарные отношения, их свойства. Отношение толерантности.

2. Способы описания графа. Матрицы ассоциированные с графами. Примеры.

3. Какие операции над множествами соответствуют стрелке Пирса?

 

 

 

Билет №10

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Бинарные отношения, их свойства. Отношение частичного порядка.

2. Доминирующее множество вершин. Число доминирования. Задача о размещении центров.

3. Три прибора БИЛЕТЫ сравнивают по двум показателям, причем выделяют тот прибор, у которого данный показатель наилучший (случаи одинаковых показателей исключаются). Образуйте множество БИЛЕТЫ всевозможных исходов такого сравнения, обозначив элементы этого множества упорядоченными парами букв для приборов с наилучшими показателями (например, исход БИЛЕТЫозначает, что по первому показателю лучшим оказался прибор БИЛЕТЫ, а по второму – прибор БИЛЕТЫ).

 

 

 

 

Билет №11

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Логика высказываний. Основные понятия логики высказываний. Логические операции

2. Потоки в сетях. Задача нахождения максимального потока.

3. Переведите следующее предложение на язык формул: ты можешь обманывать кое-кого все время, ты можешь обманывать всех некоторое время, но ты не можешь обманывать всех все время.

 

 

 

 

Билет №12

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Понятие формулы в логике высказываний. Основные равносильности логики высказываний.

2. Алгоритм нахождения критического пути в ориентированном ациклическом графе. Пример.

3. Постройте графы G1=K1,3ÈK2 и G2=БИЛЕТЫ. Определите степени, связность и хроматическое число полученных графов.

 

 

 

 

 

 

 

Билет №13

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Тождественно-истинные, тождественно-ложные, выполнимые, опровержимые формулы. Наиболее важные тавтологии логики высказываний.

2. Планарные графы, плоские графы. Максимальный планарный граф.

3. Для графа приведенного на рисунке (см. приложение), найдите Г(х2); Г-12); Г22); матрицу смежности; матрицу инциденций.

 

 

 

 

Билет №14

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Проблема разрешимости в логике высказываний. Дизъюнктивная и конъюнктивная нормальные формы формул логики высказываний.

2. Определение графа. Основные понятия теории графов. Типы графов.

3. Справедливо ли следующее утверждение: если функция непрерывна в точке x0, то она и дифференцируема в этой точке. Средствами логики предикатов запишите определение непрерывной и дифференцируемой функции.

 

 

 

 

Билет №15

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Понятие рекурсии, примеры. Рекурсивность и вычислимость функций. Тезис Черча.

2. Обходы графов. Эйлеровы циклы и задача китайского почтальона.

3. Запишите предикаты, полученные в результате логических операций над предикатами P(x), Q(x), R(x), области истинности которых обозначены на рисунках (см. приложение к билету).

 

 

 

 

Билет №16

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Индуктивное определение рекурсивных функций, явное определение (примеры). Проблема разрешимости, разрешающий метод.

2. Маршруты в графах: цепь, простая цепь, цикл, простой цикл (примеры). Связность графа.

3. Из 100 студентов 40 знают английский язык, 35 – немецкий, 28 – французский, английский и немецкий язык знают 12 студентов, английский и французский – 7, немецкий и французский – 6, все три языка знают 4 студента. Сколько студентов не знают ни одного языка?

 

 

 

 

Билет №17

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Булевы переменные и булевы функции. Булевы функции одной и двух переменных.

2. Степень графа. Регулярные, полные, тривиальные, нуль-графы (примеры).

3. Студент решил в воскресенье закончить контрольную по математике и подготовиться к практическому занятию по истории, а если к нему зайдет сокурсник, проверить с ним задачи в контрольной по математике или посмотреть новый фильм. В каком случае можно сказать, что решение студента не выполнится? В ответе отрицания должны содержаться лишь в простых высказываниях.

 

 

 

 

Билет №18

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Вырожденные и невырожденные булевы функции многих переменных. Полная система булевых функций. Полные системы алгебры высказываний.

2. Деревья. Правило экономичности.

3. Граф (см. приложение) представляет схему электрических соединений; вершины соответствуют клеммам, ребра –прямым металлическим полоскам проводников. Для физически осуществимых соединений проводники не должны пересекать друг друга, поэтому необходимо распределить ребра по нескольким параллельным платам, в каждой из которых проводники не пересекались бы. Определить наименьшее число плат, необходимых для реализации этих соединений.

 

 

 

 

Билет №19

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Булевы алгебры. Интерпретация булевых алгебр.

2. Способы описания графа. Соответствия. Изоморфность графов.

3. Всякое ли дерево является двудольным графом? Докажите.

 

 

 

 

Билет №20

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Аксиоматические системы. Модели аксиоматических теорий. Основные понятия аксиоматических теорий.

2. Операции на графах: удаление и добавление ребра, стягивание ребра, отождествление и удаление вершин, расщепление вершин.

3. Представьте в виде формулы конституент нуля (единицы) булеву функцию, заданную таблицей (см. приложение).

 

 

 

Билет №21

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

Дискретная математика»

Утверждаю

_____________________

1999г.

1. Адекватность и полнота аксиоматической теории. Теорема дедукции. Свойства выводимости из системы гипотез.

2. Операции на графах: объединение, соединение, произведение графов.

3. Укажите минимальный разрез и покажите максимальный поток в сети (см. приложение). Удовлетворяется ли спрос? Если нет, то что достаточно изменить, чтобы задача стала допустимой?

 

 

 

 

Билет №22

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Основные понятия логики предикатов. Структура высказываний. Логические операции над предикатами. Множество истинности предиката.

2. Обходы графов. Гамильтоновы графы, задача коммивояжера.

3. Последовательность высказываний определяется следующим рекуррентным соотношением: an=an-1Ù(an-2Úan-3), n>3. Высказывания a1, a2, a3 заданы, причем a1 и a3 - истинны, а a2 - ложно. Истинно или ложно высказывание an? Как выражается an через a1, a2, a3?

 

 

 

 

Билет №23

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Кванторные операции. Категорические высказывания. Применение языка логики предикатов для записи математических предложений. Прямая, обратная и противоположная теоремы.

2. История развития теории графов.

3. В графе (см. приложение), каждое ребро имеет пометку (a, b), где a – пропускная способность, а b – надежность ребра. Найти:

a). Путь с наибольшей пропускной способностью от вершины 1 к вершине 10;

b). Путь с наибольшей надежностью от вершины 1 к вершине 10.

 

 

 

 

Билет №24

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Понятие формулы логики предикатов. Равносильные формулы логики предикатов.

2. Дополнение графа. Самодополнительные графы, примеры простых самодополнительных графов. Можно ли построить самодополнительный шестивершинный граф.

3. Перечислите все максимальные независимые и минимальные доминирующие множества графа G (см. приложение). Укажите числа независимости и доминирования.

 

 

 

Билет №25

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Общезначимость и выполнимость формул логики предикатов. Проблема разрешимости в логике предикатов. Тезис Черча.

2. Алгоритм Дейкстры.

3. Постройте графы G1=C4+K2 и G2=C4´K2. Определите степени, связность и хроматическое число полученных графов.

 

 

 

 

Билет №26

РосНОУ

Экзаменационные билеты по курсу «Математическая логика и

дискретная математика»

Утверждаю

_____________________

1999г.

1. Многозначные логики. Функции многозначной логики.

2. Полный граф (число ребер, число треугольных циклов, которым принадлежит выделенное ребро), полный двудольный граф (число ребер, уникурсальность).

3. Покажите, что в дереве, имеющем больше одной вершины, существуют по крайней мере две висячие вершины.

 

 

 

 

 

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика