Программа учебной дисциплины ОПД. Ф.10 Основы дискретной математики (стр. 5 )

в) Москва - столица Италии?

4.  Какие логические операции в множестве высказываний можно определить?

5.  Пусть А и В — высказывания. Как называются и как определяются высказывания &? Какие у них таблицы истинности?

6.  Установите, какие из высказываний в следующих парах являются отрицаниями друг друга:

а) 5<9 , 5>9;

б) “Прямые а и b пересекаются ”, ”Прямые а и b совпадают”;

в) ”Натуральное число n четно”, ”Натуральное число n нечетно”?

7.  Следующие составные высказывания расчлените на простые и запишите символически, введя буквенные обозначения для их элементарных составляющих:

а) Неверно, что, если 2 - не простое число, то 4 – простое число;

б) Из того, что 20 делится на 2 и 20 делится на 5, следует, что 20 делится на 10.

8.  Какие из следующих высказываний являются истинными:

а) Если 30 делится на 6, то 30 делится на 3;.

б) Если 84 делится на 4, то 84 делится на 8;

в) 13 делится на 8 тогда и только тогда, когда 13 делится на 4?

9.  Сформулируйте определение формулы логики высказываний; приведите примеры.

10.  Какие из следующих формул являются тавтологиями:

а) Ø (p Ù Ø p);

б) (p ® q) « (Ø q ® Ø p);

в) (p ® (p Ú q)) « ((p Ù q) ® q)?

11.  Составьте таблицу истинности для формулы ((s ® t)® t)® t.

12.  Какие формулы логики высказываний называются равносильными?

13.  Перечислите основные равносильности алгебры высказываний.

14.  С помощью основных равносильностей докажите: p Ù q® p Ù r º Ø p ÚØ q Ú r.

15.  Сформулируйте отрицания следующих высказываний: «число 12 делится на 2 и на 3», «четырехугольник АВСД не является ни прямоугольником, ни ромбом».

3.2.  Образец контрольной работы

Задание 1

Для данных множеств А и В найдите и изобразите на координатной плоскости. ;

Задание 2

Постройте граф и определите какими из свойств: 1) рефлексивность; 2) антирефлексивность; 3) симметричность; 4) антисимметричность; 5) транзитивность; 6) связанность — обладает бинарное отношение r, заданное на множестве . Ответ поясните.

.

Задание 3

Определите, является ли соответствие f частичным отображением, отображением (если да, то определите тип отображения). .

Задание 4

На одной из кафедр университета работают S человек, среди которых T человек не знают ни одного иностранного языка. A человек знают английский, N – немецкий, F – французский. AN знают английский и немецкий, AF – английский и французский, NF – немецкий и французский, ANF знают все три языка.

По заданным в таблице условиям восстановить недостающую информацию.

№	S	A	N	F	AN	AF	NF	ANF	T
3)	17	8	10	?	6	4	4	3	5

Задание 5

Сколько чисел, меньших 105, можно записать из цифр 2, 4, 5? Сколько среди них нечетных?

Задание 6

В выражении раскрыли скобки и привели подобные члены. Какой коэффициент будет стоять около выражения ?

Задание 7

Составьте таблицу истинности для формулы: ;

Задание 8

С помощью равносильных преобразований приведите формулу алгебры высказываний к ДНФ, КНФ, СДНФ, СКНФ: .

Задание 9

I. Дан граф:

1. Приведите примеры:

а) маршрута в графе, не являющегося цепью;

б) цепи в графе, не являющейся простой цепью;

в) цикла в графе, не являющегося простым циклом;

г) простого цикла.

2.Для данного графа запишите матрицу смежностей и инциденций.

Задание 10

Постройте для данного графа эйлеров цикл.

3.3.  Программа экзамена по дисциплине «Основы дискретной математики»

(Бакалавриат ОЗО, 1 курс 2010-11 уч год)

1.  Основные понятия теории множеств: понятие множества; элемент множества; конечные и бесконечные множества; пустое множество; способы задания множеств; равенство множеств; отношение включения множеств и его свойства; операции над множествами: объединение, пересечение, разность, дополнение; свойства операций; количество элементов объединения множеств; булеан.

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

3.  Бинарное отношение на множестве. Свойства бинарных отношений на множестве: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связанность.

4.  Отношение порядка; строгий, нестрогий, линейный, частичный порядки. Упорядоченные (строго, нестрого, частично, линейно) множества. Примеры.

5.  Отношение эквивалентности; определение и примеры. Класс эквивалентности: определение и примеры. Теорема о том, что каждый класс эквивалентности однозначно порождается любым своим элементом. Фактор-множество. Примеры фактор-множеств.

6.  Разбиение множества; определение и примеры. Связь отношения эквивалентности, заданного на множестве, с разбиением этого множества. Теорема о том, что фактор-множество А/r по отношению эквивалентности r является разбиением множества А.

7.  Частичное отображение (или функциональное соответствие или «отображение из А в В»). Отображение (функция); определение и примеры. Виды отображений: сюръективное, инъективное, биективное; определения и примеры; отличительные свойства графиков сюръективного, инъективного отображений. Равномощные и счетные множества.

8.  Обратное отображение. Необходимое и достаточное условие обратимости отображений.

9.  Композиция отображений и ее свойства.

10.  Общие правила комбинаторики: правило суммы и произведения. Теорема о включениях и исключениях.

11.  Основные комбинаторные конфигурации: размещения с повторениями и без повторений, перестановки с повторениями и без повторений; определение и примеры; формулы для подсчета их числа.

12.  Сочетания; определение и примеры; формулы для подсчета их числа. Свойства биномиальных коэффициентов. Бином Ньютона и полиномиальная формула, треугольник Паскаля.

13.  Высказывания. Операции над высказываниями. Определения и примеры.

14.  Формулы логики высказываний; таблицы истинности; тождественно истинные, тождественно ложные и выполнимые формулы. Равносильные формулы; основные равносильности логики высказываний.

15.  Конъюнктивная и дизъюнктивная нормальные формы для формулы логики высказываний; необходимые и достаточные условия тождественной истинности (тождественной ложности) формул логики высказываний. Совершенные к. н.ф. и д. н.ф. для формул логики высказываний.

16.  Основные понятия и определения теории графов. Определение графа (неориентированного). Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Степени вершин. Теоремы о сумме степеней всех вершин графа и о количестве вершин нечетной степени.

17.  . Маршруты в графе. Цепи, простые цепи, циклы, простые циклы. Связность и достижимость. Виды графов: полный граф, двудольный граф, связный граф, граф – дерево, взвешенный граф.

18.  Ориентированный граф и его основные элементы: дуга, полустепень захода и исхода вершины v, путь и контур.

19.  Матричная форма представления графов: матрица смежности, матрица инцидентности.

20.  Эйлеровы циклы и цепи в неорграфе. Эйлеровы графы; признак возможности построения эйлерова цикла в неорграфе; алгоритм построения эйлерова цикла в эйлеровом графе; алгоритм построения эйлеровой цепи, не являющейся циклом. Гамильтоновы графы и циклы

21.  Планарные и плоские графы. Условия планарности. Грани плоского графа. Теорема Эйлера о соотношении чисел граней, ребер и вершин плоского графа. Раскраска вершин и ребер графа. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.