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

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

для студентов заочного отделения

специальности

230115 «Программирование в компьютерных системах»

Екатеринбург

2014

ОДОБРЕНО цикловой комиссией информатики и вычислительной техники   Председатель комиссии   ______________/ О. Г. Максимова подпись Протокол № ____   от «__» ______________ 201___ г.

УТВЕРЖДАЮ Заместитель директора по учебной работе ________________/ Н. Б. Чмель   «__» ___________ 201___ г.

Организация-разработчик: Автономная некоммерческая профессиональная образовательная организация «Уральский промышленно-экономический техникум»

Разработчик:

Максимова Оксана Геннадьевна, преподаватель специальных дисциплин,

Методист АН ПОО «Уральский промышленно-экономический техникум»

Введение

Математическая логика является фундаментом математической кибернетики. Аппарат математической логики необходим при создании и эксплуатации современных ЭВМ, средств передачи и обработки информации, автоматизированных систем управления и проектирования; поэтому знание основ данной дисциплины абсолютно необходимо для современного специалиста в области информатики и вычислительной техники.

Учебная дисциплина «Элементы математической логики» является дисциплиной, формирующей базовый уровень знаний, необходимый для освоения общепрофессиональных и специальных дисциплин.

Материал дисциплины «Элементы математической логики » используется при изучении дисциплин: «Основы программирования», «Архитектура компьютерных систем», «Теория вероятностей и математическая статистика», «Теория алгоритмов», «Технология разработки программных продуктов», «Технология разработки и защиты баз данных», «Прикладное программирование», «Системное программирование».

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

Методические указания к выполнению контрольных работ

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

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

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

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

1. Номер варианта контрольной работы определяется по последней цифре номера зачетной книжки (или по последней цифре порядкового номера Ф.И.О. студента в списке журнала группы, если он взят за основу при определении варианта); цифра «0» означает вариант № 10.

В заданиях используются следующие обозначения:

–количество букв в Вашем полном имени;

–количество букв в Вашем отчестве;

–количество букв в Вашей фамилии.

2. Работа представляется либо в рукописном (текст выполняется разборчиво), либо в машинописном варианте. К текстам, подготовленным с помощью текстового процессора, предъявляются следующие требования: шрифт Times New Roman, 14; междустрочный интервал 1,5; поля: верхнее – 2см, нижнее – 2 см., левое – 2,5 см, правое – 1,5 см.

3. В начале работы должен быть указан номер варианта задания.

4. Перед решением задачи должно быть приведено ее условие.

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

6. В конце работы должна стоять подпись студента с указанием даты ее выполнения.

7. На лицевой стороне контрольной работы необходимо указать следующую информацию: Ф.И.О. студента, номер группы, дисциплина и номер зачетной книжки (или, соответственно, порядковый номер Ф.И.О. студента в списке журнала группы).

Ме

Задача 1.

Пусть множество А – это область определения функции

Множество В – это область определения функции

Найти и изобразить на числовой прямой множества

Задача 2

Решите задачу, используя формулу мощности объединения множеств.

2.1. Из 40 студентов-программистов 2 и 3 курса в День программиста 10 человек приняли участие в турнире по шахматам, 12 – в традиционном чемпионате по «Counter-Strike», 10 – в легкоатлетической эстафете 9 мая. Четверо студентов были участниками и легкоатлетической команды, и чемпионата; столько же играли и в шахматы, и в компьютерные игры; трое участвовали как в шахматном турнире, так и в эстафете. 17 человек отказались принимать участие во всех этих мероприятиях. Сколько студентов приняли участие во всех трех соревнованиях?

Сколько студентов ничего не умеют, кроме игры в «Counter-Strike»?

2.2. Среди 100 деталей прошли обработку на первом станке 42 штуки, на втором - 30 штук, а на третьем - 28. Причем на первом и втором станках обработано 5 деталей, на первом и третьем - 10 деталей, на втором и третьем - 8 деталей, на всех трех станках обработано три детали. Сколько деталей обработано на первом станке и сколько деталей не обработано ни на одном из станков?

2.3. На первом курсе учатся 40 студентов. Из них по истории Урала имеют тройки 19 человек, по информатике – 17 человек и по физкультуре – 22 человека. Только по одному предмету имеют тройки: истории Урала – 4 человека, по информатике– 4 человека и по физкультуре – 11 человек. 7 человек имеют тройки и по информатике, и по истории Урала. Сколько человек учится без троек? Сколько человек имеют тройки по двум из трех дисциплин

2.4. Из 100 студентов-программистов 42 посещают спортивные секции, 30 – занятия научного студенческого общества (НСО), а 28 – кружки художественной самодеятельности. На занятия НСО и спортом успевают ходить 5 студентов, спортом и художественной самодеятельностью занимаются 8 человек, НСО и художественной самодеятельностью – 8, а сразу все три увлечения имеют 3 студента. Сколько студентов не посещают ни одно из этих объединений по интересам? Сколько студентов занимаются только наукой?

2.5. Из 20 спортсменов класса – 10 лыжников,9 гимнастов и 11 легкоатлетов. 6 занимаются легкой атлетикой и гимнастикой. 7 – лыжами и легкой атлетикой, 6 – лыжами и гимнастикой. Всеми тремя видами спорта занимаются 5 спортсменов. Сколько учащихся занимаются только лыжами, только гимнастикой, только легкой атлетикой? Сколько спортсменов занимается другими видами спорта?

2.6. Из 90 студентов-программистов в первую же сессию 32 не сдали экзамен по дисциплине «Основы программирования», 35 – по дисциплине «Элементы высшей математики» а 33 – по дисциплине «Элементы высшей математической логики». Не умеют программировать и не знают математическую логику одновременно 2 студента, проблемы с высшей математикой и программированием имеют 12 человек, не сдали одновременно и математическую логику, и высшую математику 6 человек. Только 5 студентов сдали все три экзамена. Сколько нерадивых студентов имеют все три задолженности? Сколько студентов не сдали экзамен только по математической логике?

2.7. Из 100 студентов английский язык знают 28 студентов, немецкий – 30, французский – 42. Английский и немецкий одновременно знают 8 студентов, английский и французский – 10, немецкий и французский – 5. Все три языка знают 3 студента. Сколько студентов не знают ни английский, ни французский, ни немецкий язык? Сколько студентов знает только английский язык?

2.8. Первая рота 1-го курса военного училища состоит из 70 курсантов. Из них 27 занимаются в драмкружке, 32 – поют в хоре, 22 – увлекаются спортом. В драмкружке 10 курсантов из хора, в хоре 6 – спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок и хор

Сколько спортсменов посещают хор или драмкружок?

Сколько увлекаются только спортом?

2.9. Первая рота 1-го курса военного училища состоит из 70 курсантов. Из них 27 занимаются в драмкружке, 32 – поют в хоре, 22 – увлекаются спортом. В драмкружке 10 курсантов из хора, в хоре 6 – спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок и хор

Сколько курсантов не поют в хоре, не увлекаются спортом и не занимаются в драмкружке?

Сколько человек, занимающихся в драмкружке и в хоре, не занимаются спортом?

2.10. Первая рота 1-го курса военного училища состоит из 70 курсантов. Из них 27 занимаются в драмкружке, 32 – поют в хоре, 22 – увлекаются спортом. В драмкружке 10 курсантов из хора, в хоре 6 – спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок и хор

Сколько спортсменов драмкружка не поют в хоре?

Сколько поющих спортсменов, не посещающих драмкружок?

Задача 3

Определите, какими свойствами обладает заданное бинарное отношение на множестве всех людей X. Обоснуйте свой ответ.

Является ли данное бинарное отношение отношением эквивалентности? Отношением толерантности? Отношением порядка?

3.1. .

3.2.

3.3.

3.4.

3.5.

3.6.

3.7.

3.8.

3.9.

3.10.

Задача 4

Методом математической индукции докажите что при любом натуральном n справедливо следующее равенство:

4.1.

4.2.

4.3.

4.4.

4.5.

4.6.

4.7.

4.8.

4.9.

4.10.

Задача 5

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

5.1.

5.2.

5.3.

5.4.

5.5.

5.6.

5.7.

5.8.

5.9.

5.10.

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

по дисциплине «Элементы математической логики»

1. Множество. Подмножество. Универсальное множество. Операции над множествами, их свойства.

2. Соответствие между множествами. Отображение. Виды отображений. Композиция функций.

3. Мощность множества. Основная теорема о конечных множествах. Равномощные множества. Счетные множества. Континуальные множества.

4. Кортежи. Декартовы произведения множеств.

5. Отношения. Бинарные отношения, их свойства. Отношение эквивалентности, отношение толерантности. Отношение порядка. Упорядоченные множества.

6. Высказывания. Формулы и их логические возможности. Таблицы истинности. Равносильные формулы.

7. Свойства логических операций.

8. Совершенные дизъюнктивные и конъюнктивные нормальные формы.

9. Булевы функции. Реализация булевых функций формулами.

10. Двойственные функции. Принцип двойственности.

11. Выражение булевых функций через отрицание, конъюнкцию и дизъюнкцию (теорема с доказательством).

12. Замыкание класса булевых функций. Свойства замыканий классов булевых функций (с доказательством).

13. Замкнутые и собственные классы булевых функций. Теорема о классах функций T₀, T₁, T_*, T_≤, T_L.(с доказательством)

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

15. Метод математической индукции.

16. Предикат. Область определения и множество истинности предиката. Логические и кванторные операции над предикатами. Допустимые множества. Интерпретация.

17. Приведенная и предваренная нормальная формы.

18. Вычислимые функции и алгоритмы. Свойства алгоритмов. Ассоциативное исчисление.

19. Нормальные алгоритмы Маркова.

20. Машина Тьюринга. Тезис Черча-Тьюринга.

Список рекомендуемой литературы

Основная

1. Спирина, М.С. Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М С. Спирина, П.А. Спирин. – М.: Издательский центр «Академия», 2004. – 368 с.

2. Кулабухов, С. Ю. Дискретная математика. Конспект лекций / С0 .Ю. Кулабухов. – Таганрог: Издательство ТГРТУ, 2001. – 151 с.

Дополнительная

1. Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-пресс, 2007. – 176 с.

2. Новиков, Ф. А. Дискретная математика для программистов: Учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2009. – 384 с.

3. Палий, И. А. Дискретная математика. Курс лекций / И. А. Палий. – М.: Эксмо, 2008. – 352 с.

4. Сизый, С. В. Лекции по теории чисел / С. В. Сизый. – М.: Физматлит, 2007. – 192 с.

5. Шапорев, С. Д. Математическая логика. Курс лекций и практических занятий / С. Д. Шапорев. – СПб.: БХВ-Петербург, 2005. – 416 с.