Тема II . Булевы функции.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ

 

для специальности 09.02.01 Компьютерные системы и комплексы

 

 

2020

Содержание

 

1. Введение

2. Тематический план дисциплины

3. Требования к оформлению контрольной работы

4. Методические указания по самостоятельному изучению

5. Программа

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

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

8. Литература

 

 

Введение

 

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

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

Изучение дисциплины продолжается один семестр и предполагает:

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

· самостоятельное изучение дисциплины студентами с использованием настоящих методических указаний;

· выполнение одной контрольной работы;

· сдачу экзамена

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

 

2. Тематический план дисциплины.

 

 

Введение

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

Тема 2. Булевы функции

Тема 3. Комбинаторика

Тема 4. Основы теории графов

 

 

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

 

1. Вариант работы определяется последней цифрой шифра (номер зачетной книжки).

2. Работа выполняется в отдельной тетради.

3. На титульном листе аккуратно должны быть заполнены все данные (название группы, специальность, группа, шифр, Ф. И. О. студента).

4. Контрольная работа выполняется чернилами темного цвета, аккуратно и без сокращения слов.

5. Для замечаний преподавателя на страницах тетради оставляются поля.

6. Каждое следующее задание должно начинаться с новой страницы.

7. Условия заданий переписываются полностью.

8. Задания нумеруются теми же номерами, которые указаны в контрольном задании.

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

10. Решение задач выполняется в соответствии с правилами, изложенными при решении типовых задач настоящих методических указаний.

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

12. Работа, выполненная не по своему варианту, не учитывается и возвращается без проверки.

13. Студенты, не имеющие зачета по контрольной работе, к экзамену не допускаются.

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

15. Зачтенная контрольная работа предъявляется преподавателю на экзамене. Студент должен быть готов дать во время экзамена пояснения по существу решения задач, входящих в его контрольную работу.

 

 

4. Методические указания по самостоятельному изучению дисциплины.

 

 

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

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

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

 

Программа

 

Введение.

Студент должен

 

 иметь представление:

 

- о роли и месте знаний по дисциплине в процессе основной профессиональной программы по специальности;

- об основных задачах и областях применения дискретной математики;

 

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

 

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

 

 

Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество; количество подмножеств конечного множества. Теоретико-множественные диаграммы. Операции над множествами. Формула включений и исключений. Основные законы алгебры множеств.

Понятие бинарного отношения; примеры бинарных отношений. Виды бинарных отношений. Классы эквивалентности; теорема о разбиении множества па классы эквивалентности.

 

Студент должен

 

    знать:

- понятие множества;

- понятие подмножества, формулу количества подмножеств каждого конечного множества;

- операции над множествами;

- формулу количества элементов в объединении нескольких (двух, трех) конечных множеств;

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

- определение диаграмм Венна-Эйлера;

    - понятие декартова произведения множеств;

       - понятие декартовой степени множества;

- понятие бинарного отношения;

- понятие рефлексивного, симметричного, транзитивного бинарного отношения;

- понятие отношения эквивалентности, теорему о разбиении множества на классы эквивалентности.

 

              уметь:

- применять теоретико-множественные диаграммы;

- выполнять операции над множествами;

- применять законы для упрощения выражений и для доказательства тождеств;

- выполнять кардинальные операции над множествами.

 

Рекомендуемая литература:[1]-[5]

 

Вопросы для самоконтроля:

 

1.Что такое множество? Как его обозначить? Как можно задать множество? Что такое подмножество?

2. Какие основные операции выполняются над множествами?

3. Какое множество можно назвать универсальным?

4. Что такое диаграмма Венна-Эйлера?

5. Сформулируйте и докажите основные тождества алгебры множеств?

6. Что такое декартово произведение множеств; бинарное отношение, заданное на множестве А?

7. Назовите основные свойства бинарных отношений.

8. Что такое мощность множества?

9. Чему равна мощность множества всех подмножеств множества А?

 

 

Тема II . Булевы функции.

 

 

Понятие булевой функции. Способы задания булевой функции. Проблема представления булевой функции в виде формул алгебры логики. Понятие СДНФ, СКНФ. Методика преставления булевой функции в виде СДНФ, СКНФ. Операция двоичного сложения и ее свойства. Многочлен Жегалкина. Понятие выражения одних булевых функций через другие. Полнота множества функций. Замыкание множества функций. Важнейшие замкнутые классы:  Теорема Поста.

 

 

Студент должен

 

знать:

- элементарные булевы функции одной переменной;

       - элементарные булевы функции двух переменных;

       - законы алгебры логики;

- понятие двойственной функции;

- понятие самодвойственной функции;

- принцип двойственности;

- понятие совершенной ДНФ, методику представления булевой функции в виде        

совершенной ДНФ;

       - понятие совершенной КНФ, методику представления булевой функции в виде        

совершенной КНФ;

- понятие минимальной ДНФ.

- операцию двоичного сложения и её свойства;

       - методику представления булевой функции в виде полинома Жегалкина;

     - теорему Поста;

 

уметь:

- строить таблицу истинности;

- упрощать формулы с помощью законов алгебры логики;

- выражать одни функции через другие;

- представлять булеву функцию в виде совершенной ДНФ;

- представлять булеву функцию в виде совершенной КНФ;

- представлять булеву функцию в виде полинома Жегалкина;

- проверять булеву функцию на принадлежность к классам Т0, Т1, S, L, M;

- проверять множество булевых функций на полноту (с помощью теоремы Поста).

 

Рекомендуемая литература: [1]-[5]

 

        

Вопросы для самоконтроля:

1. Что такое булева функция?

2. Как строится таблица истинности для булевых функций?

3. Сформулируйте основные законы алгебры логики?

4. Дайте определение СДНФ и СКНФ?

5. Приведите правило преобразования формул в СДНФ.

6. Дайте определение полинома Жегалкина.

7. В чем состоит метод неопределенных коэффициентов для построения полинома Жегалкина?

8. Перечислите важнейшие замкнутые классы.

9. Сформулируйте теорему Поста