Контрольные вопросы

1. Какие символы содержит алфавит языка логики предикатов?

2. Сформулируйте определение формулы языка логики предикатов.

3. Дайте определения: свободного и связанного вхождения переменной в формулу, свободной переменной.

4. Что такое сигнатура формулы?

5. Как задать интерпретацию языка логики предикатов? Зачем она нужна?

6. Как найти значение формулы в интерпретации с оценкой?

Примеры заданий по теме

1. Является ли замкнутой формула х₁  х₂ P₁² (х₁, х₂)?

2. Найдите значение формулы y P (х, у) в интерпретации = Z₊,  , где Z₊ – множество целых положительных чисел.

Тема 13. Равносильность

Содержание. Равносильность формул логики предикатов. Основные равносильности и их доказательства. Приведенная форма для формул логики предикатов. Предваренная нормальная форма. Проблема разрешения для общезначимости и выполнимости, неразрешимость ее в общем случае.

Цель. Формирование понятия равносильных формул и умений доказывать равносильность формул. Формирование понятия предваренной нормальной формы (ПНФ) и умений приводить формулу к ПНФ.

Контрольные вопросы

1. Какие формулы языка логики предикатов называются равносильными?

2. Какая формула находится в предваренной нормальной форме?

3. Сформулируйте алгоритм приведения формулы к ПНФ.

Примеры заданий по теме

1. Докажите равносильность  х А   х В ≡  х (А  В).

2. Получите ПНФ для формулы  х y А (х, у)  х  y В (х, у).

Тема 14. Применение языка логики предикатов.

Содержание. Запись на языке логики предикатов математических предложений, определений, построение отрицаний предложений. Строение математических теорем. Методы доказательства теорем.

Тема 15. Исчисление предикатов

Содержание. Язык исчисления предикатов. Система аксиом исчисления предикатов. Правила вывода. Построение выводов. Теорема дедукции.

Цель. Формирование аксиоматического метода в исчислении предикатов. Непротиворечивость исчисления предикатов. Теорема Геделя о полноте исчисления предикатов.

Контрольные вопросы

1. Дайте определение исчисления предикатов (формальной теории ).

2. Что называется выводом в исчислении предикатов?

3. Какие дополнительные (производные) правила вывода Вы знаете?

4. Как формулируется теорема дедукции в исчислении предикатов?

5. Дайте определения теории первого порядка и модели.

6. Какими свойствами обладает исчисление предикатов?

Примеры заданий по теме

1. Докажите, что х (А  В), х А ├─ х В.

2. Докажите, что формула х₁ х₂ А  х₂ х₁ А является теоремой в теории первого порядка.

4. Перечень вопросов к зачету

1. Составление истинностных таблиц для пропозициональных формул.

2. Равносильные преобразования формул.

3. Проблема разрешения в логике.

4. Приведение формул к дизъюнктивной и конъюнктивной нормальным формам.

5. Приведение к совершенным дизъюнктивным и конъюнктивным нормальным формам.

6. Минимизация в классе дизъюнктивных нормальных форм.

7. Доказательство полноты системы булевых функций.

8. Построение выводов из аксиом в исчислении высказываний.

9. Построение выводов из гипотез в исчислении высказываний.

10. Построение выводов с использованием теоремы дедукции в исчислении высказываний.

11. Построение выводов с использованием производных правил вывода в исчислении высказываний (правило резольвенты).

12. Понятие предиката. Кванторы.

13. Общезначимые формулы логики предикатов.

14. Интерпретации и модели. Значения формул в интерпретации.

15. Приведение к предваренной нормальной форме.

16. Построение выводов из аксиом в исчислении предикатов.

17. Построение выводов из гипотез в исчислении предикатов.

18. Построение выводов с использованием теоремы дедукции в исчислении предикатов.

19. Построение выводов с использованием производных правил вывода в исчислении предикатов (правило резольвенты).