Читайте также:
|
|
Это некая стандартизация рассуждения от противного, оформленного в виде таблицы. Для обоснования тезисов – общезначимость, невыполнимость, следование, несовместимость по и, несовместимость по л.
Метод от противного – допускаем что тезис не верен, и показываем, что допущение не верно, следовательно, верен тезис.
Аналитическая таблица состоит из строк – конфигураций. В строках содержатся списки формул, один или несколько списков формул. Первая строка содержит один список формул – антитезис.
1. Доказать, что формула А – общезначима. Антитезис - ┐А.
2. Доказать, что ф-ла А – невыполнима, т е ложна во всех моделях. Антитезис – А.
3. Доказать логическое следование. A1,A2,…An |= B. Антитезис – предполагаем, что следования нет (т е найдется такая модель, где A1,A2,…An – истинные, а В – ложная). A1,A2,…An – в первую строку таблицы пишем без отрицания, а В с отрицанием.
4. Несовместимость по истинности (т е не существует модели, где каждая из формул оказалась бы истинной). Антитезис – есть модель, где A1,A2,…An – истинные. Антитезис - A1,A2,…An
5. Несовместимость по ложности (т е не существует модели, где каждая из формул оказалась бы ложной). Антитезис - ┐A1, ┐A2,… ┐An
Переход к следующим строкам таблицы осуществляется по правилам редукции (сведение к простому). В основе этих правил лежат условия истинности и ложности формул. При переходе к следующим строкам какой-то из списков формул заменяется на другой список или несколько списков.
Правила редукции:
[&] Г, А&В, ∆ [┐&] Г, ┐(А&В), ∆
Г, А, В, ∆ Г, ┐А, ∆ | Г, ┐B, ∆
[v] Г, А v В, ∆ [┐v] Г, ┐(А v В), ∆
Г, А, ∆ | Г, А, ∆ Г, ┐А, ┐В, ∆
[>] Г, А>В, ∆ [┐>] Г, ┐( А>В), ∆
Г, ┐A, ∆ | Г, В, ∆ Г, А, ┐ В, ∆
[┐┐] Г, ┐┐А, ∆
Г, А, ∆
[V] Г, VαA, ∆ [┐V] Г, ┐ VαA, ∆
Г, VαA, А(t), ∆ Г, ┐ А(k), ∆
[E] Г, Е α А,∆ [┐E] Г, ┐ Е α А, ∆
Г, А(k), ∆ Г, ┐ Е α А, ┐ А(t), ∆
Цель – получить замкнутый список формул – т е содержащий А и ┐А (в каждом формульном списке, т е с необходимостью прийти к противоречию).
Конфигурация (строка таблицы) – это непустое множество формульных списков
Аналитическая таблица – это последовательность конфигураций такая, что каждая последующая конфигурация получена из предыдущей заменой какого-либо формульного списка в соответствии с некоторым правилом редукции
Замкнутый список формул - т е содержащий А и ┐А
Конфигурация замкнута – если все формульные списки в ее составе замкнуты
Аналитическая таблица замкнута – если она содержит конечное число конфигураций и последняя конфигурация замкнута.
Критерии общезначимости, невыполнимости, следования, несовместимости по и, несовместимости по л.
Ф-ла А общезначима ≡ существует замкнутая аналитическая таблица, первая конфигурация которой содержит единственный формульный список - ┐А.
Ф-ла А невыполнима ≡ существует замкнутая аналитическая таблица, первая конфигурация которой содержит единственный формульный список - А
Из ф-л A1,A2,…An |= В ≡ существует замкнутая аналитическая таблица, первая конфигурация которой содержит единственный формульный список - A1,A2,…An, ┐В
Ф-лы A1,A2,…An совместимы по истинности ≡ существует замкнутая аналитическая таблица, первая конфигурация которой содержит единственный формульный список - A1,A2,…An
Ф-лы A1,A2,…An совместимы по ложности ≡ существует замкнутая аналитическая таблица, первая конфигурация которой содержит единственный формульный список - ┐A1, ┐A2,… ┐An
9. Аксиоматическое исчисление предикатов: схемы аксиом, и правила вывода, понятие доказательства, вывода и теоремы
Дедуктивные постулаты: аксиомы и правила вывода.
Аксиомы – формулы языка, которые постулируются в качестве законов.
Правила вывода – из одниз формул выводить другие.
Все постулаты исчисления высказываний сохраняются, но добавляются еще новые аксиомы и правила.
Два способа построения – 1. с конечным числом аксиом и правилами подстановки (в исчисл выск – одно такое правило)
2. с бесконечным числом аксиом и правилом mp. Со схемами аксиом.
Исчисление предикатов со схемами аксиом.
Язык.
Пропозиц перем - &, v, >, ┐, V – только один квантор
Квантор существования может быть введен по определению: EαA ≡Df ┐Vα ┐A
В качестве исходных можно выбрать разные наборы схем аксиом. Возьмем такой: 12 схем аксиом и 2 правила вывода.
А1 – А10 – уже известны, но вместо А и В подставляются формулы языка логики предикатов. А11, А12 – новые: удаление V и пронесение V через >.
Схемы аксиом (A1 – A12):
1. А>(B>A) – схема консеквента
2. (A>(B>C)) >((A>B)>(A>C)) - схема самодистрибутивности
3. A>(B>(A&B)) - схема введения &
4. (A&B)>A - 1-ая схема исключения &
5. (A&B)>B - 2-ая схема исключения &
6. A > (AvB) - 1-ая схема введения v
7. B > (AvB) - 2-ая схема введения v
8. (A>B)> (┐A > B) – схема исключения v
9. (A>B) > ((A>┐B)> ┐A) - схема введения ┐
10. ┐┐A > A - схема исключения ┐
11. VαA > A(t) - схема исключения V
12. Vα (A>B)>(A> VαB) - схема пронсения V через >
Правила вывода:
R1 A>B, A
B
R2 A
VαA (правило генерализации)
Если R2 применять к закону, то в рез-те получается закон. Если оно применяется не к закону, то на него накладываются ограничения. (Зависимость формул вывода от допущений. Каждое допущение зависит от самого себя. Аксиомы не зависят от допущений).
Доказательство – непустая конечная последовательность формул, такая что каждая формула этой последовательности есть или аксиома, или ф-ла полученная по правилу mp, или полученная по правилу генерализации.
Доказательство ф-лы А – док-во, последней формулой которого является А.
Теорема (закон) – ф-ла, для которой существует доказательство.
Вывод из Г – непустая конечная последовательность формул такая что каждая Сi есть – либо допущение из Г, либо аксиома, либо ф-ла полученная в рез-те применения R1, либо ф-ла полученная в рез-те применения R2 (ограничение: ф-ла VαA может быть получена из А (по R2), зависящей от множества допущений ∆ в том случае, когда α не содержится свободно ни в одной формуле из ∆, ни в одном допущении из ∆.
Отношение выводимости. Г|--B. Ф-ла В выводима из множества допущений Г ≡ существует вывод из множества допущений Г, последней формулой которого является В.
10. Натуральное исчисление предикатов: правила вывода, понятия вывода, завершенного вывода и доказательства.
Логические системы можно строить исключительно языковыми средствами, т е чисто синтаксически. Эти системы – исчисления.
Исчисления: 1. Задается язык. Здесь – язык классической логики предикатов.
2. Задаются дедуктивные постулаты. Правила вывода (в натуральном исчислении высказываний, только А и В – ф-лы языка логики предикатов) + еще 4 правила
Дата добавления: 2015-01-30; просмотров: 86 | Поможем написать вашу работу | Нарушение авторских прав |