Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Імітаційне моделювання – один з важливих методів аналізу різних складних систем, в якому широко використовуються системи масового обслуговування (СМО)...полностью>>
'Документ'
Журнал «Вестник гуманитарного института ТГУ» издается Тольяттинским государственным университетом. В журнале публикуются статьи, сообщения, рецензии,...полностью>>
'Документ'
Пешеходная экскурсия “Знакомство с Прагой”. В лабиринтах маленьких улочек мы погрузимся в таинственную атмосферу Старого города: древняя Пороховая ба...полностью>>
'Документ'
1. Красивый, умелый комплимент, сделанный обаятельным мужчиной женщине, имеет такое же значение для женщины, какое имеет бочка вкусного меда для пчел...полностью>>

1. Введение в алгебру логики Прямое произведение множеств. Соответствия и функции. Алгебры. Функции алгебры логики. Суперпозиции и формулы. Булева Алгебра. Принцип двойственности. Совершенная дизъюнктивная нормальная форма сднф

Главная > Лекции
Сохрани ссылку в одной из сетей:

математическая логика

Кафедра систем телекоммуникаций, факультет физико-математических и естественных наук.

Обязательная дисциплина, привязанная к семестру.

Трудоемкость – 3 кредита, 2 часа лекций и 2 часа лабораторных занятий в неделю.

Цель курса

Целью курса является развитие логического мышления у студентов и изучение основ математической логики. Развиваются навыки формализации и описания дискретных математических объектов.

Содержание курса

Лекции

Тема 1. Введение в алгебру логики

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

Тема 2. Минимизация булевых функций

Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.

Тема 3. Полнота и замкнутость систем логических функций

Замкнутые классы. Класс логических функций, сохраняющий константы 0 и 1. Определение и доказательство замкнутости. Класс самодвойственных функций.

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

Тема 4. Исчисление высказываний и предикатов

Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость, логическое следствие. Метод резолюций для исчисления высказываний. Понятие предиката. Кванторы. Алфавит. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму. Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации. Метод резолюций в исчислении предикатов.

Лабораторные занятия

Тема 1. Алгебра логики

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

Тема 2. Минимизация булевых функций

Минимизация функций. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.

Тема 3. Полнота и замкнутость систем логических функций

Решение задач на доказательство замкнутости класса. Класс самодвойственных функций. Решение задач с несамодвойственными функциями. Класс монотонных функций. Решение задач с немонотонными функциями. Класс линейных функций. Решение задач с нелинейными функциями.

Тема 4. Исчисление высказываний и предикатов

Решение задач с использованием метода резолюций для исчисления высказываний. Применение кванторов. Поиск предваренной нормальной формы (ПНФ). Поиск скулемовской стандартной формы. Подстановка и унификация для ПНФ. Применение алгоритма унификации. Применение метода резолюций в исчислении предикатов.

Темы контрольных работ

Промежуточный контроль знаний

Контрольная работа № 1. Булева алгебра.

Типовые задачи

  1. Построение СДНФ, СКНФ, нахождение существенных и фиктивных переменных, построение полинома Жегалкина.

  2. Представление функции булевой формулой.

  3. Нахождение двойственной функции по правилу двойственности, по принципу двойственности и по таблице.

  4. Проверка справедливости соотношения.

Контрольная работа № 2. Минимизация булевых функций и исчисление высказываний.

Типовые задачи

  1. Построить минимальное представление исходной функции с помощью алгоритма Куайна-МакКлоски и последующего выделения ядра.

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

  3. Найти предваренную и скулемовскую нормальные формы для формулы.

  4. Проверить принадлежность функции классам монотонных функций, самодвойственных функций, линейных функций.

Коллоквиум № 1. Теоретические вопросы по курсу.

Проверка знаний теоретических вопросов по темам

  1. Алгебра логики.

  2. Минимизация булевых функций.

  3. Полнота и замкнутость систем логических функций.

  4. Исчисление высказываний и предикатов.

Итоговый контроль знаний.

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

Теоретические и практические вопросы и задачи по темам

  1. Алгебра логики.

  2. Минимизация булевых функций.

  3. Полнота и замкнутость систем логических функций.

  4. Исчисление высказываний и предикатов.

Литература

Обязательная

  1. Гаврилов Г.П., Сапоженко А.А. «Задачи и упражнения по курсу дискретной математики».// М.: "Наука", 2007.

  2. Иванов Б.Н. «Дискретная математика. Алгоритмы и программы». // М.: Изд-во «Лаборатория базовых знаний», 2007.

  3. Холл М. «Комбинаторика». // М.: "Мир", 2005.

Дополнительная

  1. Ю.В. Гайдамака, К.Е. Самуйлов, Л.А. Севастьянов, С.С. Спесивов «Комбинаторика. Алгоритмы на графах». Учебно-методическое пособие. // М.: Изд-во РУДН, 2002.

Программу составила

Зарипова Эльвира Ринатовна,

старший преподаватель кафедры систем телекоммуникаций,

факультет физико-математических и естественных наук.



Скачать документ

Похожие документы:

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

    Реферат
    Целью курса является развитие логического мышления у студентов и изучение основ математической логики, а также обучение основным методам комбинаторики и теории графов.
  2. Методические указания и контрольные задания санкт-петербург удк 621. 396. 62

    Методические указания
    ДИСКРЕТНАЯ МАТЕМАТИКА Булевы функции и элементы теории графов методические указания и контрольные задания Авторы: Рабкин Е.Л., Фарфоровская Ю.Б. / СПбГУТ.
  3. Аннотации дисциплин гуманитарного, социального и экономического цикла Аннотация дисциплины «История» (1)

    Документ
    Целью изучения дисциплины является формирование таких социально-личностных компетенций как способность и готовность к межличностной коммуникации, работать в коллективе, проявлять гражданскую позицию; обладание навыками самостоятельной
  4. Лекции по 1 курс Москва 2000

    Лекции
    Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры).

Другие похожие документы..