Алексеев В. Б. - Дискретная математика - Функции алгебры логики

• Дискретная математика важна для информатики и вытеснила аналоговую.  

• Курс включает разделы: функции алгебры логики, теория графов, теория кодирования и теория автоматов.  

• Курс будет ознакомительным, так как времени на глубокое изучение не хватает.  

• Основное множество состоит из двух элементов: нолик и единичка.  

• Функция алгебры логики отображает множество наборов ноликов и единичек в нолики или единички.  

• Рассматриваются всюду определенные функции.  

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

• Примеры функций: константа ноль, константа единица, тождественная функция, отрицание.  

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

• Конъюнкция: функция, которая в трех местах равна нулю, а в последнем равна единице.  

• Дизъюнкция: функция, которая в одном месте равна нулю, а в остальных трех равна единице.  

• Сумма по модулю два: функция, которая работает как обычная сумма, но с ноликом и единичкой.  

• Эквивалентность: функция, истинная, когда аргументы совпадают.  

• Импликация: функция, передающая логическую связь "если а, то б".  

• Импликация считается истинной, если из ложной посылки следует истина.  

• Определение функции штрих Шеффера, противоположной конъюнкции.  

• Введение функции стрелка Пирса, противоположной дизъюнкции.  

• Упоминание о необходимости семи функций для задач.  

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

• Лемма о количестве слов длины m в алфавите из r букв.  

• Доказательство леммы индукцией.  

• Упорядочивание наборов из нулей и единиц в порядке натуральных чисел.  

• Задание функции через столбец.  

• Вопрос о количестве функций алгебры логики от n переменных.  

• Определение существенной переменной.  

• Переменная называется существенной, если её значение меняет значение функции на соседних наборах.  

• Переменная называется несущественной, если её значение не влияет на значение функции.  

• Определение равенства функций алгебры логики.  

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

• Добавление и исключение эффективных переменных.  

• Определение алгоритмичности и неалгоритмичности.  

• Решение задачи равенства функций через совмещение таблиц.  

• Определение формулы над множеством функций.  

• Индуктивное построение формул.  

• Рекурсивное построение формул.  

• Добавление третьего пункта для конечных формул.  

• Формулы как конечные деревья.  

• Сопоставление функций формулам.  

• Определение эквивалентности формул.  

• Равенство функций и формул.  

• Основные эквивалентности и их свойства.  

• Законы коммутативности и ассоциативности.  

• Правила раскрытия скобок и дистрибутивность.  

• Правила де Моргана и законы поглощения.  

• Двойное отрицание в алгебре логики не возникает.  

• Функция от одной переменной икс плюс один используется для замены отрицания.  

• Функции штрих Шеффера и стрелка Пирса заменяют конъюнкцию и дизъюнкцию.  

• Тождества позволяют упростить выражения.  

• Ассоциативность операций позволяет опускать скобки.  

• Конъюнкция выполняется раньше дизъюнкции и сложения по модулю два.  

• Степень сигма икс равна икс при сигма равно единице и отрицание икс при сигма равно нулю.  

• Степень сигма может рассматриваться как функция двух переменных икс и сигма.  

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

• Сумма включает слагаемые икс в степени сигма, умноженные на значение функции.  

• Конъюнкция выполняется раньше дизъюнкции, что позволяет упростить вычисления.  

• Доказательство включает вычисление значения правой части на любом наборе.  

• Если хотя бы одно сигма не совпадает с альфа, слагаемое равно нулю.  

• В итоге остается только одно слагаемое, которое равно значению левой части.  

• Теорема позволяет представить функции в виде специальных формул.  

• Будут рассмотрены следствия, особенно для совершенной дизъюнктивной нормальной формы СДНФ.  

• Лекции продолжаются по пятницам.