- •«Магнитогорский государственный университет»
- •Кадченко Ангелина Ивановна
- •Магнитогорск, 2011 Содержание
- •Основные сведения об авторах
- •Цели и задачи дисциплины
- •3. Перечень основных тем и подтем
- •Тема 1. Высказывания и операции над ними. Формулы алгебры высказываний
- •Примеры заданий по теме
- •Тема 2. Равносильность.
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 3. Нормальные формы
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 4. Совершенные нормальные формы
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 5. Булевы функции.
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 6. Логическое следование формул
- •Тема 7. Виды теорем и методы математических доказательств
- •Тема 8. Аксиоматическое определение логики высказываний
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 9. Теорема дедукции.
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 10. Свойства исчисления высказываний
- •Тема 11. Предикаты
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 12. Формулы логики предикатов
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 13. Равносильность
- •Контрольные вопросы
- •Примеры заданий по теме
- •Тема 14. Применение языка логики предикатов.
- •Тема 15. Исчисление предикатов
- •Контрольные вопросы
- •Примеры заданий по теме
- •4. Перечень вопросов к зачету
- •5. Рекомендуемая литература (основная и дополнительная)
Примеры заданий по теме
1. Привести к совершенной конъюнктивной нормальной форме относительно переменных , и формулу .
2. По данному набору значений переменных постройте элементарную конъюнкцию, принимающую значение 1 только на наборе (0, 0, 1, 1) значений переменных.
Тема 5. Булевы функции.
Содержание. Понятие булевой (истинностной) функции. Представление истинностных функций формулами. Метод Блейка – Порецкого. Полные системы булевых функций. Неполные системы функций. Применение алгебры высказываний к описанию релейно-контактных схем.
Цель. Усвоение понятия булевой (истинностной) функции и способов её задания. Понятие полной системы булевых функций.
Контрольные вопросы
1. Дайте определение булевой функции.
2. Как задать булеву функцию таблицей?
3. Как найти формулу в СДНФ булевой функции, которая задана таблично?
4. Как найти формулы в СКНФ булевой функции, которая задана таблично?
5. Как можно упростить формулы булевых функций методом Блейка – Порецкого?
6. Какие системы булевых функций называются полными?
7. Как установить полноту системы булевых функций?
Примеры заданий по теме
1. Упростите методом Блейка – Порецкого булеву функцию f (X, Y, Z, V), которая задана следующей формулой:
2. Докажите полноту следующих систем функций: {, ¯ }, {&, ¯ }, {, ¯ }.
Тема 6. Логическое следование формул
Содержание. Логическое следствие. Признаки логического следствия. Правила логических умозаключений. Закон контрапозиции.
Тема 7. Виды теорем и методы математических доказательств
Содержание. Прямая и обратная теоремы. Противоположная и обратная противоположной теоремы. Необходимые и достаточные условия. Методы математических доказательств. Доказательство от противного. Метод приведения к абсурду.
Тема 8. Аксиоматическое определение логики высказываний
Содержание. Алфавит, формулы и аксиомы исчисления высказываний. Вывод из аксиом – доказуемость формул. Выводимость из гипотез. Правила вывода. Построение выводов.
Цель. Формирование основных понятий аксиоматического метода в логике высказываний.
Контрольные вопросы
1. Как определяются формальные (аксиоматические) теории в математической логике?
2. Дайте определение одной из формальных теорий, являющейся исчислением высказываний.
3. Приведите примеры формул, являющихся аксиомами по всем схемам аксиом определения формальной теории.
4. Что такое вывод из аксиом и вывод из гипотез?
Примеры заданий по теме
1. Является ли данная последовательность формул выводом из аксиом:
а) А1 В (А В),
А2 (В (А В)) (В (В (А В)),
А3 В (В (А В));
б) А1 (А А) (В (А А)),
А2 А А,
А3 В (А А);
в) А1 А (В С).
2. Является ли данная последовательность формул выводом из гипотез:
А1 А В,
А2 А,
А3 В,
А4 В (С В),
А5 С В.
Тема 9. Теорема дедукции.
Содержание. Теорема дедукции. Следствия. Применения теоремы дедукции. Метод резолюций в исчислении высказываний.
Цель. Формирование навыков построения выводов в исчислении высказываний с использованием теоремы дедукции.