В этом материале представлены ссылки на лекции и варианты практических занятий для изучения дисциплины "Дискретная математика".
Вторая часть материалов по дисциплине "Дискретная математика" расположена по ссылке:
1. Формулы логики. Логика высказываний.
1.1. Тема «Основные логические операции. Формулы логики. Дизъюнктивная и конъюнктивная нормальные формы».
Обучающийся должен
· знать: понятие пропозиционального высказывания, примеры пропозициональных высказываний; понятия унарной и бинарной логических связок, перечень базовых логических операций, перечень основных логических операций, определения основных логических операций (отрицание, логическая конъюнкция, логическая дизъюнкция, импликация и эквивалентность), символы для обозначения основных логических операций, языковые конструкции для основных логических операций; понятие таблицы истинности и правила её записи; понятия алфавита, слова (выражения), алфавита логики, формулы логики, подформулы логики; перечень основных соглашения относительно записи формул логики, приоритет одних логических операций перед другими логическими операциями; понятия элементарной конъюнкции (дизъюнкции), дизъюнктивной (конъюнктивной) нормальной формы, совершенной дизъюнктивной (конъюнктивной) нормальной формы, оба способа составления формулы логики по заданной таблице истинности;
· уметь: определять значение истинности пропозиционального высказывания; записать таблицу истинности основных логических операций (отрицание, логическая конъюнкция, логическая дизъюнкция, импликация и эквивалентность), перевести символьную запись атомарного или сложного пропозиционального высказывания на естественный язык и наоборот; определять порядок выполнения логических операций согласно приоритету; записать результирующую таблицу истинности для сложного пропозиционального высказывания с учётом приоритета выполнения основных логических операций; составлять формулу логики в виде совершенной нормальной формы по заданной таблице истинности.
Лекционный материал по теме:
Видеолекция по ссылке:
По этой ссылке можно перейти и выполнить Упражнение в среде Learning apps для проверки знаний по определениям, соответствующим логическим операциям:
Непосредственно ссылка на Упражнение:
Лекционный материал по теме:
Видеолекция по ссылке:
Практикум по построению таблиц истинности - см. по ссылке:
Варианты заданий для реализации в логических симуляторах или среде программирования PC WorX - см. по ссылке:
https://dzen.ru/a/ZSJyZg8taHGTqsi9?share_to=link.
Лекционный материал по теме:
Видеолекция по ссылке:
Лекционный материал "Возможности WolframAlpha для логики высказываний" по теме:
1.2. Тема «Проверка теоретико-множественных отношений с помощью формул логики».
· знать: о возможности проверки теоретико-множественных отношений с помощью формул логики, о соответствии между логическими операциями и операциями над множествами, методику определения множества истинности формулы логики, как определяется вектор значений истинности множества, как определять значения истинности булеана.
· уметь: проверять теоретико-множественные отношения с помощью формул логики, определять значения истинности для произвольной формулы теории множеств, определять значения истинности булеана.
Видеолекция "Проверка теоретико-множественных отношений с помощью формул логики высказываний" по ссылке:
Далее представим серию практических задач, использующих для решение аппарат логики высказываний:
Предлагается выполнить Упражнение, составленное в среде Learning apps по определению логических формул для логических схем с помощью онлайн-тренажера «Логические схемы»:
Видеолекция "Логика высказываний: задача освещения помещений; задача об аварийной сигнализации" по ссылке:
Лекционный материал "Логика высказываний: о железнодорожном стрелочном переводе" по теме:
Лекционный материал "Логика высказываний: задача о бортовом компьютере яхты" по теме:
Видеолекция "Логика высказываний: о железнодорожном стрелочном переводе; о бортовом компьютере яхты" по ссылке:
Видеолекция "Логика высказываний: подбор экипажа космического корабля; составление расписания" по ссылке:
Для проверки усвоения материала предлагается подготовиться к прохождению теста, используя видео материал:
Обратите внимание, что необходимо выполнить Упражнение, озвученное в видео "Логика высказываний: тестирование по разделу", продолжив цепочку вопросов-ответов, начатую в видео (надо указать номер своего вопроса, указать 4 варианта ответов на этот вопрос, один из которых верный, а остальные - неверные).
1.3. Тема «Понятие булева функция. Совершенная ДНФ».
Обучающийся должен
· знать: понятие булевой (логической) переменной, определение булевой функции; формулировку теоремы о числе булевых функций; способы задания булевых функций; формулировку теоремы о числе строк таблицы истинности для булевых функций n-переменных; примеры булевых функций двух переменных, имеющих специальные названия и обозначения; соглашения относительно записи формул булевых функций; законы, выражающие одни булевы функции через другие; понятия элементарной конъюнкции (дизъюнкции), дизъюнктивной (конъюнктивной) нормальной формы, совершенной дизъюнктивной (конъюнктивной) нормальной формы; способы составления булевой функции, соответствующей таблице истинности;
· уметь: определять число булевых функций n-переменных; определять число строк таблицы истинности булевой функции, определять значения истинности булевой функции; получать символическую запись булевой функции по соответствующей таблице истинности.
Лекционный материал по теме:
1.4. Тема «Операция двоичного сложения. Многочлен Жегалкина"
Обучающийся должен
· знать: понятие двоичного сложения, вид таблицы истинности для двоичного сложения; многочлена Жегалкина; теорему Жегалкина; этапы построения многочлена Жегалкина для произвольной булевой функции;
· уметь: записать таблицу истинности для двоичного сложения; получить многочлен Жегалкина для произвольной булевой функции.
Лекционный материал по теме:
1.5. Тема «Минимизация булевых функций в классе нормальных форм».
Обучающийся должен
· знать: понятие импликанта, какой импликант является простым, алгоритм построения сокращенной ДНФ с помощью СКНФ, понятие тупиковой ДНФ булевой функции, понятие минимальной ДНФ, алгоритм построения тупиковых и минимальных ДНФ булевой функции, алгоритм минимизации булевой функции в классе нормальных форм, понятие частично (не всюду) определённой булевой функции, алгоритм минимизации частично определенных функций в классе нормальных форм;
· уметь: находить импликанты (простые импликанты) для булевой функции, получать сокращенную ДНФ с помощью СКНФ, получать тупиковые и минимальные ДНФ (КНФ) булевой функции, определять минимальную нормальную форму для частично определенной булевой функции.
Лекционный материал по теме:
Нахождение импликантов для булевой функции -
1.6. Тема «Полнота множества функций. Важнейшие замкнутые классы. Теорема Поста».
Обучающийся должен
· знать: понятие двойственной булевой функции, способы получения двойственной булевой функции; формулировку теоремы о суперпозиции двойственных булевых функций; понятие самодвойственной булевой функции, символ для обозначения класса самодвойственных булевых функций, формулировку теоремы о замкнутости относительно суперпозиции класса самодвойственных булевых функций, понятие противоположного набора, критерий самодвойственности булевой функции, формулировку леммы о несамодвойственной булевой функции, поэтапный алгоритм получения из несамодвойственной булевой функции одну из констант; понятие булевой функции, принадлежащей классу T0, формулировку теоремы о замкнутости относительно суперпозиции класса T0 булевых функций; понятие булевой функции, принадлежащей классу T1, формулировку теоремы о замкнутости относительно суперпозиции класса T1 булевых функций; понятие линейной булевой функции, символ для обозначения класса линейных булевых функций, формулировку теоремы о замкнутости относительно суперпозиции класса линейных булевых функций, формулировку леммы о нелинейной булевой функции; понятие монотонной булевой функции, символ для обозначения класса монотонных булевых функций, формулировку теоремы о замкнутости относительно суперпозиции класса монотонных булевых функций, критерий монотонности булевой функции и следствие из критерия, формулировку леммы о немонотонной булевой функции; понятие замкнутого класса булевых функций, формулировку теоремы Поста о полноте системы булевых функций;
· уметь: получить двойственную булеву функцию; определить, является ли булева функция самодвойственной, получить из несамодвойственной булевой функции одну из констант 0 или 1; определить, принадлежит ли булева функция классу T0; определить, принадлежит ли булева функция классу T1; определить, является ли булева функция линейной булевой функцией; определить, является ли булева функция монотонной булевой функцией; показать, является ли системы булевых функций полной.
Лекционный материал по теме:
В завершении предлагается выполнить заключительные по разделу Упражнения:
Для выполнения практических заданий (Упражнений) рекомендуется выбрать один из логических симуляторов, информация о которых представлена по следующим ссылкам:
Программы и логические симуляторы для построения логических схем (часть 3) - https://dzen.ru/a/ZM-lyM30f2oG6CgD?share_to=link.
Предлагается составить своё Упражнение в среде Learning apps по знанию алгебры логики или логическим элементам выбранного для выполнения практических заданий логическому симулятору (укажите ссылку на Упражнение в комментарии). Примеры таких Упражнений можно посмотреть по ссылке:
Для контроля остаточных знаний по дисциплине «Дискретная математика» составлен тест, состоящий из более 100 вопросов, из них случайным образом будет выбрано 20 вопросов, ответить на которые необходимо в течение 1 часа.
В материале приведены типовые примеры тех тестовых заданий, которые имеются в базе данных теста по разделу "Формулы логики. Логика высказываний":
2. Теория множеств. Бинарные отношения. Функции.
2.1. Тема «Основные понятия теории множеств. Операции над множествами. Законы теории множеств».
Обучающийся должен
· знать: основные понятия теории множеств (множество, способы задания множеств, конечное множество, бесконечное множество, пустое множество, универсальное множество, принадлежность множеству, непринадлежность множеству, подмножество, булеан, множество натуральных чисел, множество целых чисел, множество рациональных чисел, множество действительных чисел, множество комплексных чисел, счетное множество, континуальное множество), формулу количества подмножеств конечного множества, перечисление элементов (список элементов), характеристическое свойство (предикат), порождающую процедуру, понятия пересечения, объединения, разности, симметрической разности, дополнения, приоритет выполнения операций, законы теории множеств (закон идемпотентности, закон коммутативности, закон ассоциативности, закон дистрибутивности, закон двойного дополнения, закон де Моргана и др.), диаграмму Эйлера — Венна;
· уметь: определять соотношения между элементом и множеством, задавать множества списком, характеристическим предикатом и порождающей процедурой, выполнять операции над множествами, упрощать формулы, описывающие множества, изображать диаграмму Эйлера — Венна, применять теоретико-множественные диаграммы.
Лекционный материал по теме:
2.2. Тема «Метод математической индукции».
Обучающийся должен
· знать: формулировку метода математической индукции, некоторые разновидности (модификации) метода математической индукции, последовательность доказательства с помощью метода математической индукции, в чём смысл базиса индукции; важность проведения индуктивного перехода;
· уметь: доказывать утверждения с помощью метода математической индукции, доказывать неравенства с помощью метода математической индукции.
Лекционный материал по теме:
2.3. Тема «Декартово произведение множеств. Бинарные отношения».
Обучающийся должен
· знать: понятия k-арной упорядоченной последовательности, декартового (прямого) произведения произвольного числа множеств, декартова квадрата, о невыполнении свойства коммутативности декартова произведения, понятия k-арного (k-местного) отношения, бинарного отношения, способы задания бинарных отношений, понятие специального бинарного отношения, тождественного бинарного отношения, полного бинарного отношения, свойства бинарных отношений (рефлексивность, симметричность, транзитивность), понятие замыкания бинарного отношения, отношения эквивалентности, примеры отношений эквивалентности, понятие разбиения множества, понятие класса эквивалентности, теорему о разбиении множества на классы, понятия отношения частичного порядка и линейного порядка, способы построения диаграммы Хассе, понятие обратного бинарного отношения и композиции двух бинарных отношений;
· уметь: определить декартово произведение для произвольного числа множеств, изобразить график декартового произведения двух множеств, показать, что для декартова произведения не выполняется свойство коммутативности, привести примеры бинарных отношений, записать различными способами бинарное отношение, определить для бинарного отношения область определений и область значений, исследовать бинарное отношение на заданные свойства (рефлексивность, симметричность, транзитивность), получить замыкание относительно заданного свойства для бинарного отношения, привести примеры отношения эквивалентности, выделить классы эквивалентности, привести примеры отношения частичного порядка, изобразить диаграмму Хассе, привести примеры отношения линейного порядка, записать обратного бинарное отношение к заданному, определить композицию для двух заданных бинарных отношений.
Лекционный материал по теме:
2.4. Тема «Теория функций».
Обучающийся должен
· знать: определение функции, примеры функций, способы записи функций, способы задания функций, понятие области определения функции, области значений функции, понятие множества значений функции, как изобразить диаграмму Эйлера-Венна для функции, свойства функций (инъекция, сюръекция и биекция), понятие обратной функции, понятие композиции двух функций;
· уметь: задавать функции различными способами (перечисление элементов, формулой, графиком), определять основные характеристики функций (область определения, область значений, множество значений), изобразить диаграмму Эйлера-Венна для функций, определять свойства функций (инъекция, сюръекция и биекция), получать и записывать обратную функцию, определять композицию двух функций.
Лекционный материал по теме:
В материале приведены типовые примеры тех тестовых заданий, которые имеются в базе данных теста по разделу "Теория множеств. Бинарные отношения. Функции":
Дополнительные материалы по разделам Части 1:
В комментариях под материалом можете предложить свои темы, относящиеся к дискретной математике, теоретические или практические вопросы которых вам хотелось бы изучить.
Продолжение материалов по дисциплине "Дискретная математика" можно посмотреть по ссылке:
