Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Аналитико-табличный метод в логике предикатов

Читайте также:
  1. A) Метод обучения.
  2. A) определение спроса на товар, оценка издержек производства, выбор метода ценообразования, установление окончательной цены
  3. A. метод абсорбции
  4. C) Методы исследования
  5. C.) К специфическим задачам, которые используются в ходе реализации частично-поисковых методов на уроке технологии, относятся
  6. D)практических методов.
  7. Hs-СРБ – высокочувствительный метод измерения концентрации СРБ.
  8. I. Назначение методических рекомендаций
  9. I. Общеметодологические (общесистемные) принципы.
  10. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

Это некая стандартизация рассуждения от противного, оформленного в виде таблицы. Для обоснования тезисов – общезначимость, невыполнимость, следование, несовместимость по и, несовместимость по л.

Метод от противного – допускаем что тезис не верен, и показываем, что допущение не верно, следовательно, верен тезис.

Аналитическая таблица состоит из строк – конфигураций. В строках содержатся списки формул, один или несколько списков формул. Первая строка содержит один список формул – антитезис.

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 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | 3 | <== 4 ==> | 5 | 6 | 7 | 8 |


lektsii.net - Лекции.Нет - 2014-2025 год. (0.013 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав