ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего
профессионального образования

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем”

Экзаменационные билеты

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

ОПД

(1606)

(Обязательная дисциплина)

Рекомендуется для направления подготовки дипломированного специалиста

654600- Информатика и вычислительная техника специальность - 22.04.00 -

Программное обеспечение вычислительной техники

и автоматизированных систем

Москва 2006 г.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №1

1. Эквивалентные бинарные отношения. Классы эквивалентности.

2. Равносильность в булевой алгебре.

3. Доказать (АВ)С=(АС)(ВС).

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №2

1. Нигде не плотные множества.

2. Высказывания.

3. Доказать, что Card М=₀, где М – множество всех точек плоскости, имеющих рациональные коэффициенты.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №3

1. Отображение множеств.

2. Предикаты.

3. Доказать: АВ=(АВ)(АВ)

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №4

1. Теорема Бореля.

2. Кванторы общности и существования.

3. Доказать: АВ=(АВ)\(АВ).

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №5

1. Образы и прообразы множеств, их свойства.

2. Метод Квайна получения сокращённой ДНФ.

3. Доказать: А=В(А\В)(В\А)=.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №6

1. Связь кардиналов счётного множества и множества мощности континуум.

2. Граф, основные определения.

3. Доказать: S\ А_= (S\А_).

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №7

1. Трансфинитные числа.

2. Матрицы смежности и инцидентности.

3. Доказать: прообраз дополнения равен дополнению прообраза.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №8

1. Множество Кантора, его свойства.

2. Теорема о получении минимальной ДНФ из сокращённой.

3. Доказать: АВАВ=ВАВ=АА\В=ĀВ=Е, где Е – универсальное множество.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №9

1. Теорема о сумме конечного или счётного множества счётных множеств.

2. Маршруты, цепи и простые цепи.

3. Решить систему уравнений: , где А, В, С – заданные множества и ВАС.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №10

1. Теорема Кантора.

2. Связные компоненты графа.

3. Доказать: если R₁ и R₂ – рефлексивны, то рефлексивны и отношения R₁R2 и R₁R₂.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №11

1. Нулевые множества.

2. Расстояния в графе.

3. Построить бинарное отношение:

1. Рефлексивное, симметричное, нетранзитивное.

2. Рефлексивное, несимметричное, транзитивное.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №12

1. Множества первой категории.

2. Протяжённость в графе.

3. Построить бинарное отношение:

1. Нерефлексивное, антисимметричное, транзитивное.

2. Рефлексивное, антисимметричное, нетранзитивное.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №13

1. Теорема Бореля.

2. Эйлеровы цепи.

3. Доказать: если мощность множества М равна |n|, где n число элементов, множества М, то мощность множества всех подмножеств равна |2ⁿ|.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №14

1. Множества. Подмножества. Операции над множествами.

2. Эйлеровы графы в бесконечных графах.

3. Доказать: если М – произвольное бесконечное множество и А – счётное множество, то ММА.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №15

1. Кардинальные числа двумерного, трёхмерного, четырёхмерного,…, счётного континуума.

2. Конечные автоматы.

3. Пусть S+T=(ST)(ST). Найти необходимые и достаточные условия для того, чтобы S+T=ST.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №16

1. Мощность множества.

2. Формулы алгебры логики.

3. Доказать: STST=Е, где Е – универсальное множество.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №17

1. Принцип двойственности в теории множеств.

2. Минимизация нормальных форм.

3. Доказать: любое из трёх соотношений ST, ST=S, ST=Т между подмножествами данного множества U влечёт два других (закон согласованности).

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №18

1. Теорема о кардинальном числе множества всех подмножеств счётного множества.

2. Теорема Поста.

3. Доказать: Card М=₀, где М – множество всех рациональных интервалов.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №19

1. Теорема Кантора-Бернштейна. Сравнение мощностей множеств.

2. Теорема о немонотонных функциях.

3. Сколько имеется сюръекций из трёхэлементного множества на двухэлементное.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №20

1. Изоморфизм упорядоченных множеств.

2. Теорема о функциональной замкнутости монотонных функций.

3. Сколько имеется сюръекций из трёхэлементного множества на четырёхэлементное.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №21

1. Счётные множества.

2. Теорема о функциональной замкнутости самодвойственных функций.

3. Пусть хх² – отображение каждого из следующих множеств ℕ, ℤ, ℚ, ℝ, ℂ в себя. Определить образ каждого из этих отображений и выяснить, являются ли они инъекциями.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №22

1. Множества первой и второй категории.

2. Логические операции применительно к высказываниям, содержащим кванторы общности и существования.

3. Привести грамматику для языка L = {a^mbⁿc^p|m, n, p0}.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №23

1. Упорядоченные множества.

2. Иерархия грамматик Хомского.

3. Пусть хх³ – отображение каждого из следующих множеств ℕ, ℤ, ℚ, ℝ, ℂ в себя. Определить образ каждого из этих отображений и выяснить, являются ли они инъекциями.

Зав. кафедрой _____________________________Мацнев А.П.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №24

1. Теорема о кардинале множества действительных чисел.

2. Регулярные грамматики.

3. Привести грамматику для языка L = {a^kb^k| k0}.

Зав. кафедрой _____________________________Музыкин С.Н.

Московский государственный университет приборостроения и информатики
МГУПИ

Кафедра “Управление и моделирование систем” ( ИТ-6 )

Дисциплина: “Дискретная математика”

Экзаменационный билет №25

1. Теорема Кантора.

2. Теорема Жегалкина.

3. Пусть М – множество всех параллелограммов на плоскости; А₁ – множество квадратов; А₂ – множество прямоугольников; А₃ – множество ромбов. Найти результаты следующих операций: А_iА_j; А_iА_j; А_iĀ_j, {i, j = 1, 2, 3}.

Зав. кафедрой _____________________________Мацнев А.П.

Материалы рассмотрены на заседании учебно-методической комиссии ИТ-6. Протокол №1 от 03 февраля 2006 г. и одобрены на заседании кафедры ИТ-6. Протокол № 7 от 03.03.2006 г.