Формулировка задания и его объем

ФОРМУЛИРОВКА ЗАДАНИЯ И ЕГО ОБЪЕМ

Контрольная работа по дисциплине «Дискретная математика» является одной из форм самостоятельной работы студента.

Цель контрольной работы – углубить или закрепить практические знания студентов по вопросам элементов теории множеств, комбинаторики, математической логики и элементов теории графов.

Контрольная работа состоит из восьми заданий и выполняется по вариантам.

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

Общие требования к написанию и оформлению контрольной работы

При выполнении контрольной работы следует соблюдать указанные ниже правила. Работа, выполненная без соблюдения этих правил, не зачитывается и возвращается студенту для переработки.

1. Решение задач следует располагать в порядке номеров, указанных в заданиях, сохраняя номера задач.

2. Каждое новое задание начинается с новой страницы.

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

4. В том случае, когда несколько задач имеют общую формулировку, следует, переписывая условие задачи, заменить общие данные конкретными из соответствующего номера.

5. Решение задач нужно излагать подробно и аккуратно, объясняя все действия. В конце решения следует записать ответ.

Требования к оформлению контрольной работы

При выполнении контрольной работы следует соблюдать указанные ниже правила. Работа, выполненная без соблюдения этих правил,  не зачитывается и возвращается студенту для переработки.

На титульном листе контрольной работы должны быть указаны название дисциплины, фамилия, имя, отчество, группа, специальность, номер зачётной книжки студента, дата сдачи контрольной работы.

Контрольную работу следует выполнять в тетради пастой любого цвета, кроме красного, оставляя поля для замечаний рецензента.

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

Защита контрольной работы осуществляется на последнем практическом занятии по дисциплине. По результатам защиты студенту выставляется оценка. Без зачета по контрольной работе студент не может быть допущен к зачету или экзамену по данной дисциплине.

Задания контрольной работы

Задание № 1

вариант	задача
1	Задать различными способами множество N всех натуральных чисел: 1, 2, 3,...
2	Задать различными способами множество М всех четных чисел 2,4,6,..., не превышающих 100.
3	Пусть U={а, b, с}. Определить в явном виде (перечислением своих элементов) булеан в(U) - множество всех подмножеств, состоящих из элементов множества U. Ка­кова мощность множества в(U)?
4	Какие из приведенных определений множеств А, В, С, D являются корректными: а)А={1,2, 3},         в) С= {x: хА}, б)        В ={5, 6,6, 7},  г)D= {А, С}? Принадлежит ли число 1 множеству D?
5	Пусть универсальное множество U - множе­ство всех сотрудников некоторой фирмы; А - множество всех сотрудников данной организации старше 35 лет; В - множе­ство сотрудников, имеющих стаж работы более 10 лет; С - множество менеджеров фирмы. Каков содержательный смысл (характеристическое свойство) каждого из следую­щих множеств:   б)   в)   г) В\С  д) С\В?
6	Задать множества , , если: М - множество всех натуральных чисел, не превосходя­щих 100; N - множество натуральных чисел.
7	Осуществить операции над множествами А = {а, b, с, d) и В = {с, d, e, f,g, h}.
8	Пусть U= {1,2, 3,4}, A = {1,3,4}, В= {2,3}, С={1,4}. Найти: а), б),  в),  г)
9	Представить множество   диаграм­мой Венна.
10	Проиллюстрировать на конкретных множествах и с помощью диаграммы Венна справедливость соотношения

Задание № 2

вариант	задача
1	Пусть M= {1,2,3,4,5,6}. Задать в явном виде (списком) и матрицей отношение , если R означа­ет - "быть строго меньше".
2	Пусть M= {1,2,3,4,5,6}. Составить матрицы отношения , если: R1 - "быть делителем"; R2- "иметь общий делитель, отличный от единицы"; R3- "иметь один и тот же остаток от деления на 3".
3	Составить матрицы отношений, заданных на системе множеств в(M),М={а, b,с}: R1 - "пересекаться с" (иметь непустое пересечение); R2- "являться строгим включением.
4	Пусть отношение R - "быть отцом", опреде­ленное на множестве людей М= {а, b,с, d,e, f,g, h}, пред­ставлено схемой:  Задать списком отношение R. Оп­ределить (назвать) родственные отношения между следую­щими парами: (a, b), (a, d), (b, с), (b, d), (b, h), (с d).
5	Пусть некоторая программа читает два числа из множества М= {1,2, 3,4, 5}, обозначаемых х и у, и, если х < у, печатает число z (также из М) такое, что х ≤ z < у. В любом случае программа останавливается после считыва­ния всех чисел на множестве М. Чему равны области опре­деления и значений отношения?
6	Пусть бинарное отношение R на M задано в виде диаграммы, состоящей из узлов и стрелок так, что уз­лам взаимно однозначно соответствуют элементы множества М, а стрелкам, соединяющим пару а и b в направлении от а к b, - наличие отношения aRb. Определить графические осо­бенности диаграммы в зависимости от характера свойств от­ношения R.
7	Проиллюстрировать диаграммой Венна сле­дующие разбиения множества U: а){A,}; б){A В, A,  В, }; в){А\В, АВ, В\А}.
8	Пусть отношение R - "быть руководителем", определенное на множестве сотрудников организации М. Назовите отношения: , R-1 , R°, R*. Каковы свойства отно­шений?
9	Пусть на множестве М= {2, 4, 6} определе­но отношение R - "быть меньше". Задать характеристи­ческим свойством и списком отношение R, обратное от­ношение R-1 и дополнение  . Сравнить отношения. Оп­ределить их свойства.
10	Пусть G - множество всех пар действитель­ных чисел (х, у), удовлетворяющих соотношению (х-3)2+(у-2)2 1. Графически такое соответствие G представляет собой круг радиуса 1 с центром в точке (3, 2). Таким обра­зом, круг G задает соответствие между R и R (осью абсцисс и осью ординат, см. рисунок). Определить, чему равны: а)        образы и прообразы чи­сел 2, 3, 4; б)        образы и прообразы от­резков [2, 3], [2, 4]. Каковы свойства соответ­ствия G?

Задание № 3

вариант	задача
1	Записать логическими формулами следующие сложные высказывания: "Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в дурном распо­ложении духа или с головной болью". "Если социологические исследования показывают, что потребитель отдает предпочтение удобству и многообразию выбора, то фирме следует сделать упор на усовершенствова­ние товара или увеличение многообразия новых форм". Сравнить логические формулы и сделать выводы.
2	Представить логической формулой следую­щий текст (составное высказывание): «Если фирма продолжает выпуск существующего про­дукта и ориентирована на существующий рынок, то для нее целесообразна стратегия "'малого корабля", или эко­номии издержек. Такая стратегия привлекательна, если ин­тенсивный маркетинг - стратегический хозяйственный фактор, но слабая сторона организации. Если интенсив­ный маркетинг является стратегическим хозяйственным фактором и сильной стороной фирмы, то фирме следует придерживаться стратегии захвата новых рынков для су­ществующего продукта.»
3	К каким схемам относятся следующие рассуж­дения: "Если рабочий отсутствовал на работе, он не выполнил задания. Он не выполнил задания. Следовательно, он отсут­ствовал на работе". "Этот человек студент или предприниматель. Он сту­дент. Следовательно, не предприниматель". "Этот человек постоянно живет в Москве или в Санкт - Петербурге. Он живет в Москве. Следовательно, он не жи­вет в Санкт-Петербурге." "Сегодня понедельник или вторник. Сегодня вторник. Следовательно сегодня не понедельник". Являются ли данные рассуждения логически правиль­ными?
4	Записать логической формулой следующее умозаключение: "Если фирма приглашает на работу крупного специалис­та в области новейшей технологии, то она считает ее при­влекательной и разворачивает работы по изменению техно­логии производства своего традиционного продукта или на­чинает разработку нового продукта. Конкурирующая фирма пригласила на работу крупного специалиста в области но­вейшей технологии. Следовательно, она разворачивает ра­боты по изменению технологии производства выпускаемого продукта или разработке нового продукта." Уточнить справедливость данного умозаключения.
5	Составить таблицу истинности функции трех переменных, заданной формулой:
6	Доказать эквивалентность (равносильность) формул:
7	Логическую функцию трех переменных представить булевой формулой - в виде СДНФ.
8	Доказать справедливость обобщенного склеи­вания методом эквивалентных преобразований (исполь­зуя основные эквивалентные соотношения).
9	Получить СДНФ функции, используя эквива­лентные соотношения:
10	Упростить булевы формулы:

Задание № 4

вариант	задача
1	Каким отношениям и функциям соответству­ют следующие предикаты, определенные на множестве на­туральных чисел:
2	Записать формулой логики предикатов пред­ложение, отражающее транзитивное свойство делимости целых чисел.
3	Дать словесные формулировки следующих составных высказываний (предложений):
4	Пусть Р(х) - предикат "х - четное число1', определенный на множестве М. Дать словесную форму­лировку высказыванию хР(х), определить его истин­ность.
5	Пусть N(x) - предикат "х - натуральное чис­ло". Рассмотреть варианты навешивания кванторов. Проин­терпретировать полученные высказывания и определить их истинность.
6	Записать предикатной формулой предложение "Любой человек имеет отца".
7	Пусть предикат Р(х, у) описывает отно­шение "х любит у" на множестве людей. Рассмотреть все варианты навешивания кванторов на обе перемен­ные. Дать словесную интерпретацию полученных выс­казываний.
8	Пусть Q(x, у) - предикат порядка "ху". Рас­смотреть различные варианты квантификации его перемен­ных. Определить истинность получаемых выражений для разных случаев интерпретации области определения М пре­диката, х, у М.
9	Рассмотреть все возможные варианты наве­шивания кванторов на предикат D(х, у) - "х делится на у", определенный на множестве натуральных чисел (без нуля) N. Дать словесные формулировки полученных высказыва­ний и определить их истинность.
10	Какой смысл имеют предикатные формулы: где П, Е - предикаты произведения и равенства, определен­ные на N? Истинны ли эти формулы? Привести примеры наборов переменных, иллюстрирующие заключение относи­тельно истинности или ложности формул.

Задание № 5

вариант	задача
1	Сколько различных прямых можно провести через 8 точек, расположенных так, что между ними нет трех, лежащих на одной прямой.
2	Сколько словарей необходимо переводчику, чтобы он мог переводить непосредственно с любого из четырех языков – русского, английского, немецкого, французского – на любой другой из этих языков.
3	Сколько пятизначных чисел можно составить из цифр 1, 2, 4, 6, 7, 8, если каждую цифру в любом числе использовать не более 1 раза?
4	Нужно  послать 6  писем.  Сколькими  способами  это  можно сделать, если для доставки писем имеются три курьера?
5	10  кресел  поставлены  в  ряд.  Сколькими  способами  на  них  могут сесть два человека? Сколькими способами эти два человека могут сесть рядом?
6	В автомашине 7 мест. Сколькими способами 7 человек могут усесться  в  эту машину,  если  занять место  водителя могут  только  трое из них?
7	Компания из 20 мужчин разделяется на 3 группы. В первую входят три человека, во вторую – 5, в третью – 12. Сколькими способами они могут это сделать?
8	Сколькими  способами  из  пяти  супружеских  пар  можно отобрать четырех человек, если в число отобранных должны входить двое мужчин и две женщины?
9	Из двенадцати кандидатов тренер отбирает 5 и составляет из них  баскетбольную  команду.  Два  кандидата  могут  играть  центровыми, четверо –  только  в  защите,  а  остальные –  только  в  нападении. Предполагается, что баскетбольная команда состоит из одного центрового, двух защитников и двух нападающих. Сколькими способами тренер может составить команду?
10	В  группе 9  человек.  Сколько  можно  образовать  разных подгрупп, если в подгруппу входит не менее двух человек?

Задание № 6

вариант	задача
1	Найти число перестановок, образованных из всех цифр числа 2233344455.
2	Предприятие  может  предоставить  работу  по  одной специальности  четырем  женщинам,  по  другой –  пяти  мужчинам,  по третьей – трем работникам, независимо от их пола. Сколькими способами можно заполнить эти вакансии, если имеются 18 претендентов – 8 женщин и 10 мужчин?
3	Доказать,  что  число  трехбуквенных  слов,  которые  можно образовать из букв,  составляющих  слово «гипотенуза»,  равно числу  всех возможных перестановок букв, составляющих слово «призма».
4	Сколько слов, состоящих из двух гласных и двух согласных, можно образовать из слова «функция»?
5	Сколько  перестановок можно образовать из слова «экономика»?
6	Сколькими  способами  можно  расставить  на  полке 7  книг, если две определенные книги всегда должны стоять рядом?
7	Из 40 человек нужно выбрать двух делегатов на конференцию. Сколькими способами это можно сделать?
8	В комиссию избрали 6 человек. Из них надо выбрать председателя и его заместителя. Сколькими способами это можно сделать?
9	В турнире участвовали шесть шахматистов. Сколько было сыграно партий, если каждый из них сыграл с каждым остальным по одной партий?
10	Сколько существует способов набирания кода, состоящего из четырех различных цифр?

Задание № 7

вариант	задача
1	Задать граф G1, представ­ленный на рисунке, через множества вер­шин V1и ребер Е1.
2	На рисунке изображены графы G1- G12 с че­тырьмя вершинами в каждом. Сравнить графы.
3	Чему равны степени вершин графов G1 и G3 на рисунке:
4	Задать матрицами инцидентности и смежнос­ти, а также списком ребер графы G1 и G3:
5	На рисунке изображен сетевой граф (сетевая модель) выполнения комплекса операций (работ) некоторой программы. В нем стрелки обозначают операции, вершины - события, характеризу­ющие окончание од­них работ и начало других. Направлен­ность стрелок отража­ет последователь­ность наступления этих событий. Задать сетевой граф различными способами.
6	Определить, изоморфны ли графы G1 G2 изоб­раженные на рисунке:
7	Задать различными способами графы G, и G2, представленные на рисунках.
8	Какими особенностями отличается граф G, взаимно однозначно соответствующий бинарному отношению R, если R: а)        симметрично;        в) рефлексивно; б)        антисимметрично;        г) антирефлексивно; д) транзитивно.
9	Пусть ориентированный граф G на рисунке задает отношение R:G(R). Каковы свойства отношения?
10	Каким операциям над графами соответствуют основные операции над отношениями?

Задание № 8

вариант	задача
1	Для вершин v1 и v6 графа G привести примеры марш­рута, цепи, простой цепи.
2	Имеют ли пятиугольник и пятигранник-пи­рамида с петлями в некоторых вершинах эйлеров цикл (цепь)?
3	Имеет ли граф на рисунке гамильтонов цик­л, цепь?
4	Пусть граф типа дерева - G7. Сколько вершин максимального типа имеется в данном гра­фе? Каково цикломатическое число графа?
5	Определить в графе цикли­ческий маршрут, цикл, простой цикл, приняв вер­шину v1 за их начало и ко­нец.
6	Для четырех графов определить расстояния между вершинами. Какие вершины являются центрами графов? Чему равны радиусы графов?
7	Имеет ли граф на рисунке гамильтонов цик­л, цепь?
8	Пусть граф типа дерева - G7. Чему равно цикломатическое число графа G', являющегося лесом и пред­ставленного двумя одинаковыми деревьями G7? Построить ориентированное дерево с корнем v0, являющимся верши­ной максимального типа.
9	Для вершин v1 и v6 графа G привести примеры марш­рута, цепи, простой цепи; определить в графе цикли­ческий маршрут, цикл, простой цикл, приняв вер­шину v1 за их начало и ко­нец.
10	Какими свойствами обладает отношение связанности вершин  н-графа? Чему равно число связных компонент графа G?