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