Росдистант. Основы дискретной математики и логики. Практические задания

Выполнены Практические задания по учебному курсу "Основы дискретной математики и логики"

Вариант 6 (Первая буква фамилии - Е, Н, П)

Практическое задание 1

Тема 1.1. Множества и операции над ними

1.   Пусть A, B, C – множество точек плоскости, координаты которых удовлетворяют условиям α, β и γ соответственно. Изобразите в системе координат XOY множество D, полученное из множеств A, B и C по формуле δ.

Таблица 1.1

2. Выяснить взаимное расположение множеств D, E, F, если А, В, Х – произвольные подмножества универсального множества U.

Таблица 1.2

Вариант 6 (Первая буква фамилии - Е, Н, П)

Указания к выполнению работы

1. При решении задания 1 сначала на координатной плоскости изобразите исходные множества. Для того чтобы на плоскости изобразить множество точек, удовлетворяющее неравенству, необходимо сначала нарисовать границу данного множества, т. е. линию, удовлетворяющую равенству. Эта линия разделит всю плоскость на две части. Остается выбрать ту часть, которая удовлетворяет данному неравенству. Для этого можно использовать метод пробных точек: берём любую точку на плоскости, подставляем её координаты в неравенство, если неравенство верно, то закрашиваем часть плоскости, которая содержит данную точку. В противном случае выбираем другую часть плоскости.

Например, возьмём неравенство .

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

Мы получили уравнение окружности радиуса 2 с центром в точке (0,2).

Возьмем пробную точку (0,1) и подставим её в неравенство:

Эта точка удовлетворяет неравенству, следовательно, неравенству соответствует внутренняя часть окружности.

2. Для ответа на вопрос второй задачи можно использовать диаграммы Эйлера – Венна. Множества находятся в общем положении, т. е. имеем следующую диаграмму:

Поставим в каждой области из разбиения множества U по символу, обозначающему список элементов. Например, символ 1 обозначает элементы, которые принадлежат множеству и не принадлежат множествам Тогда можно записать, что , .

Введённые символы позволят определить множества D, E, F и выяснить их взаимное расположение.

Практическое задание 2

Тема 2.1. Элементы комбинаторики

1. Сколькими способами из колоды в 36 листов можно выбрать неупорядоченный набор из 5 карт так, чтобы в этом наборе было бы точно указанное ниже количество карт?

Таблица 2.1

Вариант 6 (Условие - 2 бубновые, 2 крестовые карты, 1 туз)

2. Сколько различных слов можно получить перестановкой букв слова a?

Таблица 2.2

Вариант 6 (a - Околоток, Условие - Ровно 3 буквы «о» не идут подряд)

3. Найти наибольший член разложения бинома (a + b)n

Таблица 2.3

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

Таблица 2.4

Вариант 6 (Первая буква фамилии - Е, Н, П)

Указания к выполнению работы

1. При решении задач по комбинаторике необходимо ответить на вопрос: важен или нет порядок в выборке. В зависимости от ответа на этот вопрос выбирается соответствующая комбинаторная схема. Если порядок неважен, то выбираем сочетания. Если же порядок элементов в выборке имеет значение, то выбираем размещения.

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

 2. Рассмотрим пример решения следующей задачи. Сколько различных слов можно получить такой перестановкой букв слова «передел», что в начале и в конце слова стоит согласная буква?

В этом слове всего 4 согласных буквы. Выбираем две согласные буквы, которые будут стоять в начале и конце слова, для оставшихся 5 букв вычисляем количество перестановок. Так как буква «е» повторяется, то используем формулу перестановок с повторениями.

По правилу произведения получаем

Рассмотрим ещё одну задачу. Сколько различных слов можно получить такой перестановкой букв слова «полумера», что в полученном слове не встречается буквосочетание «мурло»?

Вычислим общее число перестановок и вычтем из него количество таких перестановок букв этого слова, в которых присутствует буквосочетание «мурло».

Буквы в слове различные, их 8, значит, общее число перестановок равно 8!

Теперь вычислим количество перестановок, в которых присутствует буквосочетание «мурло». Так как все буквы слова «мурло» в исходном слове присутствуют по одному разу, то количество таких буквосочетаний равно 1. Если блок «мурло» считать за одну букву, то получаем четыре различные буквы, количество перестановок которых равно 4!

В итоге получаем ответ 8!-4!

3. В силу свойств биномиальных коэффициентов существует -й член разложения бинома, который больше k-1-го и k+1-го. Таким образом, получаем систему двух неравенств:

Подставим в эту систему конкретные значения вместо переменных , а также выражение для биномиальных коэффициентов и решим её относительно

4. Решим задачу: найти коэффициент при в разложении выражения по полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов.

Для решения этой задачи используется полиномиальная формула

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

Будем перебирать возможные значения для и получать соответствующие значения для и :

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

Практическое задание 3

Тема 3.3. Деревья. Остов графа. Понятия планарного, эйлерова и гамильтонова графов

В табл. 3.1 заданы графы G1 и G2.

1. Найдите G1 È G2, G1 ∩ G2, G1 Å G2 аналитически и изобразите результат графически.

2. Для графа G = G1 È G2 найдите матрицу смежности и матрицу инцидентности. Если граф является смешанным, то при нахождении указанных матриц считать его ориентированным (для этого нужно каждое неориентированное ребро заменить на две дуги, идущие в противоположных направлениях). Считая граф G ориентированным, найти для него компоненты сильной связности, привести пример маршрута (но не цепи) длины 7, простой цепи, простого цикла.

3. Если граф G = G1 È G2 неориентированный, найти степени всех его вершин, радиус и диаметр графа G. Если граф G = G1 È G2 смешанный, то, считая его ориентированным, найти полустепени исхода и захода всех его вершин; определить радиус и диаметр графа, полученного из графа G заменой всех его ориентированных ребер на неориентированные.

4. Выяснить, является ли эйлеровым граф, полученный из графа G, заменой всех его ориентированных ребер на неориентированные.

Таблица 3.1

Вариант 6 (Первая буква фамилии - Е, Н, П)

Практическое задание 4

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

1. С помощью равносильных преобразований упростите формулу из табл. 4.1.

Таблица 4.1

2. Докажите логическое следствие из табл. 4.2 двумя различными способами.

Таблица 4.2

Вариант 6 (Первая буква фамилии - Е, Н, П)

Практическое задание 5

Тема 4.3. Нормальные формы. Понятия тупиковой, минимальной и сокращенной ДНФ. Методы получения сокращенной и минимальной ДНФ

Для функций и , заданных векторно в табл. 5.1, выполнить следующие шаги:

1. Записать их СДНФ и СКНФ.

2. Методом Квайна найти сокращенную ДНФ.

3. Для сокращенной ДНФ построить матрицу Квайна, указать ядровые импликанты.

4. С помощью матрицы Квайна найти минимальную ДНФ, указать её сложность.

5. Найти минимальную ДНФ данной функции с помощью карт Карно, сравнить полученный результат с ДНФ, найденной в п. 4.

Таблица 5.1

Вариант 6 (Первая буква фамилии - Е, Н, П)

Указания к выполнению работы

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

1. Записать их СДНФ и СКНФ.

2. Методом Квайна найти сокращенную ДНФ.

3. Для сокращенной ДНФ построить матрицу Квайна, указать ядровые импликанты.

4. С помощью матрицы Квайна найти минимальную ДНФ, указать её сложность.

5. Найти минимальную ДНФ данной функции с помощью карт Карно, сравнить полученный результат с ДНФ, найденной в п. 4.

Решение.

Запишем таблицы истинности функций.

Практическое задание 6

Тема 5.1. Понятие предиката. Логические и кванторные операции над предикатами. Формулы логики предикатов

Для предикатов из табл. 6.1, заданных на R, выяснить, является ли первый предикат следствием второго, а второй – следствием первого.

Таблица 6.1

Вариант 6 (Первая буква фамилии - Е, Н, П)