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

Учебники

Задания для практических работ

Практическая работа № 1

Практическая работа № 2

Практическая работа № 3

Самостоятельная работа "Множества"

Домашнее задание

Тема 1.1. Алгебра высказываний

1. Выучить основные определения темы.

2. Составить таблицы истинности для следующих высказываний:

а) СvА=>С

б) F=АvB&¬C

в) F=(XvY)&(¬X&¬Y)

Тема 1.2. Законы алгебры логики

1. Выучить законы алгебры логики

2. Доказать с помощью таблиц истинности законы де Моргана

3. Упростить логическое выражение, используя законы алгебры логики:

учебник "Информатика 10 класс, 1 часть" (автор К.Ю. Поляков), стр. 191, № 2 (д,е,ж), № 3 (а,б, в).

Тема 1.3. Логические схемы

Тема 1.4. Задание от 10.10.2019: выучить определения ДНФ, КНФ, СДФН, СКНФ, подготовиться к тесту. Выполнить задания 1 и 2 из файла, представленного ниже :

Тема 1.4. Булевы функции. КНФ, ДНФ, СКНФ, СДНФ

ДЗ от 24.10.2019: № 5.6 (для f1 и f2), стр. 41, № 5.16 (б, в)

Тема 2.1. Теория множеств

Решить задачи:

1. Среди дошкольников проводилось анкетирование по любимым мультфильмам. Самыми популярными оказались три мультфильма: «Лунтик», «Смешарики», «Маша и медведь». Всего в группе 28 человек. «Лунтик» выбрали 12 детей, среди которых трое назвали еще «Маша и медведь», двое– «Смешарики». Мультфильм «Маша и медведь» назвали 10 ребят, среди которых трое выбрали ещё и «Смешарики» «Смешарики» же выбрали 12 человек. Сколько детей не смотрели данные мультфильмы, если сказано, что ни один ребёнок не смотрел все три мультфильма.

2. Среди школьников проводилось анкетирование по любимым мультфильмам. Самыми популярными оказались три мультфильма: «Мадагаскар», «Шрэк», «Спанч Боб». Всего в классе 38 человек. «Мадагаскар» выбрали 21 ученик, среди которых трое назвали еще «Спанч Боб», шестеро – «Шрэк». Мультфильм «Спанч Боб» назвали 13 ребят, среди которых пятеро выбрали «Шрэк». «Шрэк» всего посмотрели 12 человек. Сколько человек из класса не смотрели данные мультфильмы, если все три мультфильма ни один человек из класса не успел посмотреть?

Тема 2.2. Бинарные отношения

ЗАДАНИЕ 1. Определите свойства следующих отношений: 1. «прямая x пересекает прямую y» (на множестве прямых) 2. «число x больше числа y на 2» (на множестве натуральных чисел) 3. «число x делится на число y без остатка» (на множестве натуральных чисел) 4. «x – сестра y» (на множестве людей).

ЗАДАНИЕ 2. Пусть A = {1,2,3} и пусть бинарное отношение R на A имеет вид R = { (1,1) , (2,1) , (2,3) }. Какими свойствами обладает данное бинарное отношение?

Тема 2.3. Теория отношений

Домашнее задание: № 1,2,3 стр 12, № 3, стр 39 и № 11 стр. 13.

Тема 3. Теория алгоритмов

Алгоритмы Маркова

1. Выучить понятие и принципы работы НАМ

2. Нормальный алгоритм задан алфавитом А={a,b} и схемой:

1) ba→ab

2) ab→ba. Примените этот алгоритм к слову baab.

Машина Поста

1. Выучить понятие и принципы работы Машины Поста

2. Постройте алгоритм сложения двух двоичных чисел

Машина Тьюринга

1. Выучить понятие и принципы работы машины Тьюринга

2. Изучите биографию Алана Тьюринга.

3. Составьте алгоритм МТ, которая прибавляет единицу к числу на ленте. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. В начальный момент машина находится против самой правой цифры числа.