11

М инистерство общего и профессионального образования

Российской Федерации

Южно – Российский государственный технический университет

Методические указания

к практическим занятиям по курсу

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

Новочеркасск 2001

УДК 519.6(076.5)

Рецензент - кандидат технических наук, доцент кафедры “ Прикладная математика”, В.А. Плаксин.

Составители: Скоба А. Н., Панфилов А. Н.

Методические указания к практическим занятиям по курсу “Дискретная математика” /Юж. – Рос. Гос. техн. ун – т. Новочеркасск: ЮРГТУ, 2001. 12с./

Методические указания содержат примерную разбивку курса на отдельные практические занятия. Для каждого практического занятия приведены задачи, которые рекомендуется решать как в аудитории, так и дома. Указания предназначены для студентов специальностей 2202 “ Автоматизированные системы обработки информации и управления” , 0719 “Информационные системы в экономике”.

© Южно – Российский государственный

технический университет, 2001

© Скоба А. Н., Панфилов А. Н., 2001

Цель практических занятий по курсу “Дискретная математика” состоит в обеспечении углубленного усвоения лекционного материала и приобретения практических навыков решения задач по основным разделам курса: теории множеств, теории функций алгебры логики, методам их минимизации и по их практическому использованию в некоторых приложениях.

Каждое практическое занятие заканчивается обязательным выполнением данного задания

Занятие 1

Темы:

Основные понятия и определения теории множеств.

Основные законы алгебры множеств.

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

Упражнения

1. Изобразить с помощью диаграмм Эйлера – Венна следующие множества:

а) ; в) ;

б) ; г) .

2. Упростить следующие выражения:

а) ;

б) .

3. Доказать следующие тождества:

а) ; в) ;

б) ; г) ;

д) ;

е) ;

ж) ;

з) .

Пример. Доказать: .

Доказательство.

Пусть , тогда и , то есть либо и , либо и . В обоих случаях элемент x будет принадлежать множеству, стоящему справа.

Если , то , либо , т.е. либо и , либо и . В обоих случаях элемент x будет принадлежать множеству, стоящему слева.

Таким образом тождество доказано.

4. Доказать обобщенные законы дистрибутивности:

а) ;

б) .

Указание: Использовать метод математической индукции.

5. Доказать, что множество из n элементов имеет 2ⁿ подмножеств.

6. Обследование 100 студентов ЮРГТУ(НПИ) изучающие различные иностранные языки дало следующие результаты: 28 человек изучают немецкий язык, 30 человек – английский, 12 человек – французский; немецкий и английский – 8 человек; немецкий и французский – 5 человек; английский и французский – 10 человек; все три языка – 3 человека.

Сколько студентов изучает только один иностранный язык (немецкий, английский, французский); не изучает ни одного иностранного языка.

7. Решить систему уравнений:

где А, В и С – данные множества и

8. Докажите, что множество А всех четных чисел равно множеству В целых чисел, представленных в виде суммы двух нечетных чисел.

9. Доказать, что:

а) множество всех рациональных чисел счетно;

б) множество всех целых чисел счетно;

в) множество всех точек плоскости, обе координаты которых являются рациональными числами – счетно;

г) множество всех последовательностей вещественных чисел – несчетно.

10. Доказать, что множество всех подмножеств Р(А) множества А имеет мощность, большую чем А.

Занятие 2

Темы:

Высказывания и логические операции над ними.

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

Упражнения

1. Какие из следующих предложений являются высказываниями:

1. Москва - столица России; в) ;

б) студент ЮРГТУ(НПИ) ; г) Луна есть спутник Марса;

д) a>0;

е) ни один человек не весит более 1000 килограмм.

2. Пусть А – высказывание “ Студент Иванов изучает английский язык”, B – высказывание “ Студент Иванов успевает по физике”. Дать словесную формулировку высказываний:

1. ; в) .

б) ;

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

1. ; г) ;

б) ; д) ;

в) ; е) .

4. Установить, какие из следующих формул являются тождественно истинными, тождественно ложными:

1. ; г) ;

б) ; д) .

в) ;

5. Доказать равносильность:

1. ; б) ;

в) ;

г) .

6. Упростить формулы:

1. ; б) ;

в) ;

г) ;

д) ;

е) .

Занятие 3

Темы:

Функции алгебры логики.

Совершенные нормальные формы.

Упражнения

1. По таблицам истинности найдите формулы, определяющие функции F₁(x,y,z), F₂(x,y,z), F₃(x,y,z), F₄(x,y,z), и придайте им более простой вид:

x	y	z	F1(x,y,z)	F2(x,y,z)	F3(x,y,z)	F4(x,y,z)
0	0	0	0	0	0	1
0	0	1	1	0	1	1
0	1	0	0	1	1	0
0	1	1	0	0	0	0
1	0	0	1	0	0	1
1	0	1	1	0	0	1
1	1	0	1	1	1	0
1	1	1	0	1	1	1

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

1. ; г) ;

б) ; д) ;

в) ; е) .

3. Используя критерий тождественной истинности и тождественной ложности формулы, установить будет ли данная формула тождественно истинной, тождественно ложной или выполнимой:

1. ;

б) ;

в) ;

г) ;

д) .

Занятие 4

Тема:

Минимизация функций алгебры логики.