Классическая логика высказываний. Теория доказательства (4 час).

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

2. Формальная аксиоматическая система. Понятие доказательства и доказуемой формулы. Теорема дедукции.

3. Основные требования к адекватной формализации общезначимых формул: корректность, полнота и непротиворечивость,

4. Формальная система натурального вывода. Понятие вывода и выводимой формулы. Правила вывода.

РЕКОМЕНДАЦИИ

 

По этой теме базовые понятия излагаются во время обзорной лекции, там же даются образцы решения задач. Надо лишь закрепить этот материал, используя соответствующую литературу.

Классическая логика предикатов. Теория моделей (4 час).

I. Формализованный язык классической логики предикатов.

2. Понятие модели. Определение истинностных значений формулы в модели. Понятие выполнимой (непротиворечивой), общезначимой и невыполнимой (противоречивой) формулы.

3. Косвенные методы проверки общезначимости формул: метод поиска контрмодели и метод аналитических таблиц.

4. Отношение логического следования. Корректные и надежные рассуждения в языке классической логики предикатов,

5. Основные законы логики предикатов.

Классическая логика предикатов. Теория доказательства (8 час).

1. Аксиоматическое построения логики предикатов (формальная аксиоматическая система). Теорема дедукции.

2. Формальная система натурального вывода.

3. Смысл теорем полноты и непротиворечивости. Проблема разрешимости.

Литература

1. Бочаров В.А., Маркин В. И. Основы логики. М., 1994 (2000,2002). Гл.3.

2. Войшвилло Е.К. Символическая логика: классическая и релевантная М.,1987. Гл. 2, 3, 4 (§ 8, § 10).

3.Солодухин О. А. Логика. Ростов-на-Дону. Феникс.2000г. Гл.5.

 

РЕКОМЕНДАЦИИ

Целью самостоятельной работы по этой теме является закрепление того материала, который был изложен на лекциях.

Прежде всего, надо усвоить основные понятия логики предикатов первого порядка: понятия модели, условия истинности и ложности элементарных формул, условие истинности и ложности формул, главным знаком которых является конъюнкция, отрицание, дизъюнкция, импликация. Наконец, условие истинности и ложности формул, главным знаком которых являются кванторы. Надо вполне понимать определения общезначимой, противоречивой и выполнимой формулы.

На основании знания содержания указанных понятий используйте косвенный метод - метод построения контрмодели для проверки свойства быть общезначимой формулой. По учебнику "Солодухин О. А. Логика. Ростов-на-Дону. Феникс.2000г. Гл.5" изучите метод модельных конструкций (модельных множеств).

Надо усвоить метод построения аналитических таблиц для формул языка логики предикатов первого порядка. Для этого надо изучить кванторные правила редукции. Особо надо обратить внимание на правила редукции, в которых вводятся новые параметры, т.е. параметры не встречающихся на предыдущих шагах построения аналитической таблицы для фиксированной формулы. Это правила редукции для отрицания квантора общности и правило для формулы, которая начинается с квантора существования (см.: учебник Бочарова В.А., Маркина В. И. Основы логики. Гл.3, § 3). Эти же правила несколько иначе излагаются в учебнике: Войшвилло Е.К. Символическая логика: классическая и релевантная М.,1987. Гл. 3 (§ 5) Формулировки правил редукции в этих учебниках эквивалентны.

Наконец, надо усвоить аксиоматическое построение исчисление предикатов и формулировка логики предикатов в виде дедуктивной системы натурального вывода. Самое главное - усвоить ограничения на применение кванторных правил (подстановка терма вместо свободного вхождения переменных, условий на вхождение свободных и связанных переменных в правилах).

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ

 

1. Что такое модель?

2. Сформулируйте условия истинности и ложности формул в модели (индукцией построению формулы).

3. Сформулируйте определение общезначимой, противоречивой и выполнимой формулы.

4. Сформулируйте аксиомы и правила вывода в аксиоматическом исчислении.

5. Постройте доказательства следующих формул: "хР(х) É Ø $хØР(х), Ø"хØР(х) É $х Р(х), $х "у Р(х,у) É "у $х Р(х,у).

6. Пользуясь методом модельных конструкций доказать общезначимость формул из предыдущего задания.

7. Пользуясь методом аналитических таблиц, покажите, что формулы из задания 5 являются общезначимыми.

8. Является ли первопорядковая логика предикатов разрешимой?

9. Сформулируйте теоремы о корректности, непротиворечивости и полноте логики предикатов первого порядка. Сформулируйте схемы (основные идеи) доказательства этих теорем.