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

Доказательства корректности и полноты методов, применяемых в логике высказываний, содержатся в [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; Нарушение авторских прав

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