9968

2.4 Контрольные вопросы

Контрольные вопросы к разделу 1 «Теория множеств и отношений».

1.Множества. Способы задания множеств. Равные множества. Свойства включения. Сравнимость множеств.

2.Операции над множествами и их свойства. Диаграммы Эйлера-Венна.

3.Подмножества. Разбиения. Булеан множеств и его мощность.

4.Прямое произведение и его свойства.

5.Бинарные отношения и их свойства.

6.Отображения (функции) и их свойства.

7.Отношение эквивалентности и отношение порядка. Примеры.

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

1.Основные комбинаторные правила: правило произведения и правило сложения.

2.Перестановки с повторениями и без повторений.

3.Размещения с повторениями и без повторений.

4.Сочетания с повторениями и без повторений.

5.Треугольник Паскаля и Бином Ньютона.

6.Свойства биномиальных коэффициентов.

7.Метод включения и исключения.

8.Полиномиальная формула. Полиномиальные коэффициенты.

Контрольные вопросы к разделу 3 «Теория графов».

1. Ориентированные и неориентированные графы, маршруты, цепи, циклы,

пути и контуры графов.

2.Представления графов матрицей смежности, матрицей инцидентности,

списком ребер.

3.Ориентированные графы и их виды. Связь с бинарными отношениями.

4.Подграфы. Операции над графами.

91

5.Метрические соотношения в графах.

6.Эйлеровы и полуэйлеровы графы. Критерий эйлеровости графа.

7.Гамильтоновы графы. Достаточные условия гамильтоновых графов.

8.Эйлеровы и гамильтоновы цепи, циклы, пути, контуры.

9.Деревья, лес. Свойства деревьев.

10.Обходы графов: поиск в ширину и поиск в глубину.

11.Построение остова минимального веса: алгоритмы Прима и Краскала.

12.Минимальные пути в нагруженных графах. Алгоритм Дейкстры.

Контрольные вопросы к разделу 4 «Алгебра логики».

1.Определение логических операций.

2.Формулы алгебры логики. Основные законы алгебры логики.

3.Логическое следствие и его свойства.

4.Способы доказательства правильности рассуждений.

5.Решение логических задач.

6.Двойственные формулы. Теорема двойственности.

7.Применение алгебры логики к релейно-контактным схемам. Упрощение РКС.

Контрольные вопросы к разделу 5 «Булевы функции».

1.Булевы функции их количество.

2.Представление булевой функции в совершенной нормальной дизъюнктивной форме.

3.Представление булевой функции в совершенной нормальной конъюнктивной форме.

4.Представление булевой функции в виде полинома Жегалкина.

5.Замыкание множеств булевых функций. Основные классы булевых функций

Т0 , Т1 ,S, M, L, их замкнутость.

6.Полнота систем булевых функций. Теорема Поста.

92

3. Методические указания по подготовке к практическим занятиям

3.1Общие рекомендации по подготовке к практическим занятиям

Входе подготовки к практическим занятиям необходимо изучать основ-

ную литературу, познакомиться с дополнительной литературой. При этом необходимо учесть рекомендации преподавателя и требования учебной про-

граммы.

В соответствии с этими рекомендациями и подготовкой полезно дорабаты-

вать свои конспекты лекции, делая в нем соответствующие записи из литерату-

ры, рекомендованной преподавателем и предусмотренной учебной программой.

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

При подготовке к занятиям можно также подготовить краткие конспекты по вопросам темы. Очень эффективным приемом является составление схем и презентаций.

Готовясь к докладу или реферативному сообщению, желательно обращать-

ся за методической помощью к преподавателю. Составить план-конспект свое-

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

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

3.2 Примеры задач для практических занятий

проверить правильность следующих утверждений:

a)А \ В А С

b)А С В С

c)А С В \ С

93

d)А В А \ С

e)С \ А А В

f)А В В С

Решение: значения операций в приведенных утверждениях представим

списками и сравним их:

a)А \ В А С ложно, так как А \ В 4 и А С 4

b)А С В С ложно, так как А С 1,2,3,9 и В С 1,2,4,5,6,9

c)А С В \ С ложно, так как А С 1,2,3,4,9 и В \ С 1,2,5,6

d)А В А \ С истинно, так как А В 1, 2 и А \ С 1,2

Задача 2.

Записать формулу, соответствующую заштрихованной части диаграммы Венна

В результате получили формулу ( А В) \ С .

94

Задача 3.

Упростить выражение

(А В С) (А (В С )) В

Решение.

( А В С) ( А (В С )) В ( А В С ) (А (В С )) ВА В С А В (В С ) А В С (В С ) А В С

Задача 4.

Система классификации получает на вход устройство, данные о котором заносит в таблицу «Оборудование» для дальнейшей обработки информации.

Таблица содержит поля «Устройство», «Назначение» и «Год выпуска» с сим-

вольными именами А, В и С соответственно. Система формирует запросы,

представленные в таблице:

На момент проведения анализа в таблице базы данных было 38 записей.

Поле «Оборудование» содержало только два типа значений: «printer» и «monitor», а поле «Год выпуска» – три типа значений: 2003, 2010, 2012. Запросу

(A=«monitor») или (С=2003), удовлетворяло 23 записи. Найдем количество

Построим описанное отношение R={((x,y),z): х<у, х z<у} (перечислим его элементы).

R={((1,2),1); ((1,3),1); ((1,3),2); ((1,4),1); ((1,4),2); ((1,4),3); ((1,5),1); ((1,5),2); ((1,5),3); ((1,5),4); ((2,3),2); ((2,4),2); ((2,4),3); ((2,5),2); ((2,5),3); ((2,5),4); ((3,4),3); ((3,5),3); ((3,5),4); ((4,5),4)}. Всего 20 элементов.

Укажем область определения и область значений отношений.

Область определения: D(R)={(1,2), (1,3); (1,4), (1,5); (2,3), (2,4); (2,5), (3,4); (3,5), (4,5)}. Всего 10 элементов.

Область значений: E(R)={1, 2, 3,4}. Всего 4 элемента.

Задача 7.

Найдем все разбиения множества А 1,2,3,4 .

Решение.

1)А1 1 , А2 2,3,4

2)А1 2 , А2 1,3,4

3)А1 3 , А2 1,2,4

4)А1 4 , А2 1,2,3

5)А1 1,2 , А2 3,4

6)А1 1,3 , А2 2,4

7)А1 1,4 , А2 2,3

8)А1 1 , А2 2 , А3 3,4

9)А1 1 , А2 3 , А3 2,4

10)А1 1 , А2 4 , А3 2,3

11)А1 2 , А2 3 , А3 1,4

12)А1 3 , А2 4 , А3 1,2

13)А1 2 , А2 4 , А3 1,3

14)А1 1 , А2 2 , А3 3 , А4 4

97

Задачи для раздела 2.

Задача 1.

Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5,

если:

А) ни одна из цифр не повторяется более одного раза,

Б) цифры могут повторяться,

В) числа должны быть нечетными (цифры могут повторяться).

Решение.

А) Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5 (0 не мо-

жет быть первой цифрой, потому что в таком случае число не четырехзначное),

если первая цифра выбрана, то вторая может быть выбрана 5 способами, третья

– 4 способами, четвертая – 3 способами. Согласно правилу, общее число спосо-

бов равно 5 5 4 3 300 .

Б) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5 (5 возможностей),

для каждой из следующих цифр имеем 6 возможностей (0, 1, 2, 3, 4, 5). Следо-

вательно, число искомых чисел равно 6 6 6 6 1080 .

В) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5, а последней – одна из цифр 1, 3, 5 (числа должны быть нечетными). Следовательно, число ис-

комых чисел равно 5 6 6 3 540.

Задача 2.

Сколькими способами можно упорядочить множество 1,2,3,….,2n так,

чтобы каждое четное число имело четный номер?

Решение. Четные числа можно расставить на местах с четными номерами

(таких мест n) n! способами, каждому способу размещения четных чисел на ме-

стах с четными номерами соответствует n! способов размещения нечетных чи-

98

сел на местах с нечетными номерами. Поэтому общее число перестановок ука-

занного типа по правилу умножения равно n! n!.

Задача 3.

Сколько можно составить перестановок из n элементов, в которых дан-

ные два элемента не стоят рядом?

Решение. Определим число перестановок, в которых данные два элемен-

та а и в стоят рядом. Могут быть следующие случаи: а стоит на первом месте, а

стоит на втором месте, …, а стоит на n-1 месте, а в стоит правее а, число таких случаев равно n-1. Кроме того, а и в можно было поменять местами, и, следова-

тельно, существует 2(n -1) способов размещения а и в рядом. Каждому из этих способов соответствует (n-2)! перестановок других элементов. Следовательно,

число перестановок, где а и в стоят рядом, равно 2(n-1)(n-2)!=2(n-1)!

Задача 4.

Учащемуся необходимо сдать 4 экзамена на протяжении 8 дней. Сколькими способами

это можно сделать?

Решение. Искомое число способов равно числу 4-элементных упорядоченных подмножеств (дни сдачи экзаменов) множества из 8 элементов,

т.е. А84 8 7 6 5 1680 способов. Если известно, что последний экзамен будет сдаваться на восьмой день, то число способов равно 4 А73 7 6 5 4 840 .

Задача 5.

Переплетчик должен переплести 12 различных книг в красный, зеленый и

коричневый переплеты. Сколькими способами он может это сделать, если в

3 А212 3 212 способами, а в трех случаях в один цвет. По формуле включений и исключений получаем 312 3 212 3 519156 случаев.

Задача 6.

В лаборатории работают 8 физиков и 10 химиков. Надо создать рабочие группы по трем темам. В первую группу должны войти 4 физика, во вторую 5

химиков, а третья должна состоять из трех человек, которые могут быть как физиками, так и химиками. Сколькими способами можно создать такие груп-

пы?

Решение. C84 C105 C93 .

Задача 7.

В лаборатории работают 8 физиков и 10 химиков. Надо создать рабочие группы по трем темам. В первую группу должны войти 4 физика, во вторую 5

химиков, а третья должна состоять из трех человек, которые могут быть как физиками, так и химиками. Сколькими способами можно создать такие груп-

пы?

Решение. C84 C105 C93 .

Задача 8.

Пусть в разложении бинома Ньютона (а3 с2 )n коэффициент третьего члена равен 28. Найдем средний член разложения.