Студопедия

Главная страница Случайная лекция


Мы поможем в написании ваших работ!

Порталы:

БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика



Мы поможем в написании ваших работ!




Корректность и полнота логического вывода

Читайте также:
  1. I. Социология как наука об обществе, её предмет и объект. Уровни социологического знания.
  2. Адаптация молодых работников и совершенствование социально-психологического климата на производстве
  3. Анализ использования технологического оборудования.
  4. Беседа как основной метод психологического консультирования. Фазы ведения беседы. Технология ведения беседы.
  5. Биологическое оружие и очаг биологического поражения
  6. Биологическое разнообразие. Генетический полиморфизм популяций как основа биологического разнообразия. Проблема сохранения биоразнообразия
  7. Виды экологического мониторинга
  8. Виды эксперимента в патопсихологии, задачи и специфика экспериментально - психологического исследования.
  9. Влияние компонентов рецептуры, условий технологического режима на свойства теста и качество готовых изделий
  10. Возможные неполадки технологического процесса и оборудования, их причины и способы устранения

Доказательства корректности и полноты методов, применяемых в логике высказываний, содержатся в [1, 2, 3, 4, 5,].

Корректность и полнота метода семантических таблиц

Теорема корректности.Если высказывание s доказуемо по Бету, то оно логически истинно. Формальная запись:

В s Þ ╞ s.

Согласно определению, высказывание s доказуемо по Бету, если семантическая таблица с помеченной формулой fs в корне является противоречивой, т.е. противоречивы все ее ветви. Если высказывание s не является логически истинным, то найдется интерпретация (множество логических значений атомов), для которой в семантической таблице обнаружится непротиворечивая ветвь c. Однако в этом случае s не доказуемо по Бету.

Теорема полноты.Если высказывание s логически истинно, то оно доказуемо по Бету. Формальная запись:

╞s Þ├ В s.

Значок ╞ означает общезначимость, т.е. ╞s означает, формула s истинна во всех возможных интерпретациях. Если высказывание s логически истинно, то для любой интерпретации I верно: I(s)=t.

Пусть высказывание s общезначимо. Построим для него семантическую таблицу с корнем f(s). Если высказывание s не выводимо по Бету, то в таблице окажется хотя бы одна противоречивая ветвь. Это означает, что в некоторой интерпретации высказывание s ложно, что противоречит общезначимости s.

Следовательно, доказательство по Бету для s обязано существовать.

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

Корректность и полнота аксиоматической системы вывода

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

Множество дизъюнктов S противоречиво тогда и только тогда, когда существует опровержение в S.

Теорема корректности и полноты.Высказывание s выводимо из множества высказываний S тогда и только тогда, когда s-- логическое следствие S. Формальная запись:

S├s Û S╞ s.

Теорема компактности.Множество высказываний S выполнимо тогда и только тогда, когда выполнимо каждое его конечное подмножество.


<== предыдущая страница | следующая страница ==>
Метод резолюций | Корректность и полнота метода резолюций

Дата добавления: 2014-11-08; просмотров: 360; Нарушение авторских прав




Мы поможем в написании ваших работ!
lektsiopedia.org - Лекциопедия - 2013 год. | Страница сгенерирована за: 0.002 сек.