Автор Тема: Лекции по математической логике  (Прочитано 1415 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Лекции по математической логике
« : Ноябрь 28, 2016, 05:00:51 pm »
Лекция 1. Имена, высказывания, умозаключения

Лекция 2. Операции над высказываниями

Лекция 3. Формулы логики высказываний

Лекция 4. Равносильность формул логики высказываний

Определение равносильности формул логики высказываний. Формулы, не являющиеся равносильными. Проверка равносильности с помощью таблицы истинности. Основные равносильности классической логики высказываний. Закон двойного отрицания, закон исключённого третьего и закон противоречия. Законы поглощения и законы де Моргана. Идемпотентность, коммутативность, ассоциативность и дистрибутивность логических связок. Выражение одних логических связок через другие. Правила действий с нулём и единицей. Критерий равносильности формул логики высказываний. Критерий неравносильности формул логики высказываний. Теорема о замене. Прямая, обратная, противоположная и обратная противоположной теорема. Закон контрапозиции и закон противоположности. Алгебра высказываний. Задачи, связанные с равносильными преобразованиями формул логики высказываний: упрощение формул и систем высказываний, построение отрицаний формул.

Лекция 5. Нормальные формы формул логики высказываний

Элементарная конъюнкция (дизъюнкция). Дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ). Совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Теоремы существования и единственности СДНФ и СКНФ. Алгоритмы приведения формулы к СДНФ и СКНФ с помощью таблицы истинности и равносильных преобразований. Задача о нахождении формулы по её истинностным значениям.

Лекция 6. Следование формул логики высказываний

Определение следования формул логики высказываний. Формулы, не связанные отношением следования. Проверка следования по таблице истинности и методом от противного. Критерий следования формул логики высказываний. Критерий отсутствия следования формул логики высказываний. Связь равносильности и следования формул. Некоторые правила дедуктивных умозаключений: modus ponens, modus tollens, "истина из чего угодно", "из лжи что угодно", цепного заключения, перестановки посылок, разбора случаев, объединения и разъединения посылок, приведения к абсурду. Задача о нахождении всех следствий из данного набора формул и всех посылок для данной формулы с помощью СКНФ и СДНФ.
 
Сказали спасибо: Байт, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Лекции по математической логике
« Ответ #1 : Ноябрь 18, 2017, 11:41:54 am »
Лекция 7. Множества. Включение и равенство множеств

Множества. Принадлежность элемента множеству. Способы задания множества. Множества, находящиеся в общем положении. Включение множеств. Подмножество и надмножество. Равенство и строгое включение множеств. Собственное подмножество. Пустое множество. Универсальное множество. Свойства пустого и универсального множеств.

Лекция 8. Операции над множествами

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

Лекция 9. Отношения, отображения, операции

Кортежи и упорядоченные пары. Прямое (декартово) произведение множеств. Декартов квадрат множества. Бинарные и \(  \large n  \)-местные отношения.  отношение. Область определения и область значений бинарного отношения. Композиция бинарных отношений. Инверсия бинарного отношения. Отображения (функции). Область отправления и область прибытия функции. Образ элемента (множества) и полный прообраз элемента (множества). Операции. Бинарные, унарные, нульарные операции.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Лекции по математической логике
« Ответ #2 : Ноябрь 18, 2017, 11:48:04 am »
Лекция 10. Основные понятия теории булевых функций

Понятие булевой функции. Сумма Жегалкина, стрелка Пирса и штрих Шеффера. Аналитическое и векторное представление булевой функции. Задача о нахождении векторного представления булевой функции, если известно её аналитическое представление. Существенные и фиктивные переменные булевой функции. Задача о нахождении существенных и фиктивных переменных булевой функции. Элементарные булевы функции. Основные тождества теории булевых функций. ДНФ, КНФ, СДНФ и СКНФ булевой функции. Задачи на доказательство тождества булевых функций и упрощение булевой функции.

Лекция 11. Полиномы Жегалкина

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

Лекция 12. Специальные классы булевых функций

Понятие булевой функции, сохраняющей нуль (единицу). Понятие самодвойственной, линейной и монотонной булевой функции. Замкнутость классов \(  \large P_0  \), \(  \large P_1  \), \(  \large S  \), \(  \large L  \) и \(  \large M  \) относительно суперпозиции. Двойственность булевых функций. Задача о нахождении булевой функции, обладающей заданными свойствами.

Лекция 13. Полные системы булевых функций

Понятие полной системы и базиса булевых функций. Понятие шефферовой функции. Штрих Шеффера и стрелка Пирса как базисы. Представление элементарных булевых функций в базисах Шеффера и Пирса. Собственные и замкнутые классы булевых функций. Задача о проверке булевой функции на шефферовость. Теорема Поста (критерий полноты системы булевых функций).  Задачи на составление таблицы Поста.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Лекции по математической логике
« Ответ #3 : Ноябрь 18, 2017, 11:50:42 am »
Лекция 14. Понятие и виды предикатов

Предикат. Предметные переменные и предметные постоянные. Единичные высказывания. Множество истинности предиката. Формализация высказывания и интерпретация предиката. Классификация предикатов. Выполнимые и тождественно ложные предикаты. Опровержимые и тождественно истинные предикаты.

Лекция 15. Предикаты и логические связки

Отрицание предиката, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация и эквиваленция предикатов. Теоремы о связи типов предикатов и логических операций. Критерий тождественной истинности (опровержимости) отрицания предиката. Критерий тождественной истинности (опровержимости) конъюнкции предикатов. Достаточное условие тождественной ложности конъюнкции предикатов. Необходимое условие выполнимости конъюнкции предикатов. Критерий тождественной ложности (выполнимости) дизъюнкции предикатов. Достаточное условие тождественной истинности дизъюнкции предикатов. Необходимое условие опровержимости дизъюнкции предикатов.

Лекция 16. Предикаты и кванторы

Предикаты от одной переменной и кванторы. Квантор общности и универсальное высказывание. Квантор существования и экзистенциальное высказывание. Общеутвердительное, общеотрицательное, частноутвердительное и частноотрицательное высказывания. Кванторы и многоместные предикаты. Задачи на определение типов предикатов, часть предметных переменных которых связана кванторами. Задачи на определение истинностных значений высказываний, полученных связыванием кванторами всех предметных переменных предиката. Другие задачи на применение определений кванторов.

Лекция 17. Отношения между предикатами

Равносильность предикатов. Критерий равносильности предикатов. Следование предикатов. Критерий следования предикатов. Выражение квантора общности через конъюнкцию. Выражение квантора существования через дизъюнкцию.

Лекция 18. Формулы логики предикатов

Предикатные переменные. Формулы логики предикатов первого порядка. Подформулы. Формализация предиката и интерпретация формулы. Классификация формул логики предикатов. Открытые и замкнутые формулы. Выполнимые и тождественно ложные на наборе множеств формулы. Опровержимые и тождественно истинные на наборе множеств формулы. Задачи на доказательство выполнимости (невыполнимости) и опровержимости (неопровержимости). Общезначимые формулы (законы логики предикатов), формулы, тождественно истинные на множестве, состоящем из \(  \large k  \) элементов. Тождественно ложные формулы (противоречия). Задачи на доказательство общезначимости (противоречивости) формулы логики предикатов. Правило подстановки. Теорема о предикатной подстановке в формулу логики высказываний.

Лекция 19. Равносильность формул логики предикатов

Равносильность формул на наборе множеств. Равносильность формул. Равносильность формул на множестве, состоящем из \(  \large k  \) элементов. Задачи на доказательство равносильности формул (равносильности формул на множестве, состоящем из \(  \large k  \) элементов). Критерий равносильности (неравносильности) формул логики предикатов. Основные равносильности классической логики предикатов первого порядка, включающие кванторы. Законы де Моргана для кванторов (законы отрицания кванторов). Закон дистрибутивности квантора общности (квантора существования) относительно конъюнкции (дизъюнкции). Коммутативные законы для кванторов. Предварённая нормальная форма. Задачи на применение равносильных преобразований формул логики предикатов: нахождение предварённой нормальной формы, доказательство равносильности формул, запись определения (высказывания) и построение его отрицания с использованием символики классической логики предикатов первого порядка.

Лекция 20. Следование формул логики предикатов

Следование формул на наборе множеств. Следование формул. Следование формул на множестве, состоящем из \(  \large k  \) элементов. Задачи на доказательство следования формул (следования формул на множестве, состоящем из \(  \large k  \) элементов). Критерий следования (отсутствия следования) формул логики предикатов. Доказательство следования с использованием критерия следования и равносильных преобразований. Теорема о связи равносильности и следования формул. Некоторые кванторные правила дедуктивных умозаключений: закон дистрибутивности квантора существования (квантора общности) относительно конъюнкции (дизъюнкции), закон коммутативности разноимённых кванторов, законы введения квантора существования и удаления квантора общности.