Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Теорема о дедукции. Полнота ИВ

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности




     Теорема о дедукции: если Г, В ├ А, то Г ├ В → А, где Г - это набор некоторых формул Г={F1, F2, ..., Fn}.
     Следствие: тогда и только тогда F1, F2, ..., Fn ├ A, когда ├F1→(F2→...→(Fn-1→(Fn→A))...)
     Доказательство: пусть F1, F2, ..., Fn ├ A. Тогда, применяя теорему о дедукции, имеем F1, F2, ..., Fn-1 ├ Fn→A.
     Аналогично F1,F2,...,Fn-2├Fn-1→(Fn→A), и т.д. Продолжая этот процесс необходимое число раз, получаем ├F1→(F2→...→(Fn-1→(Fn→A))...)
     Для доказательства достаточности предположим, что ├B, где B=F1→(F2→...→(Fn-1→(Fn→A))...). По правилу заключения получаем F1├(F2→...→(Fn-1→(Fn→A))...). Далее, через n шагов имеем F1,F2,...,Fn├A.
     Таким образом, благодаря следствию, проверка выводимости формулы A из формул F1,F2,...,Fn, сводится к проверке доказуемости формулы F1→(F2→...→(Fn-1→(Fn→A))...).
     Формула A называется тождественно истинной (или тавтологией), если значение формулы A равно единице при любых наборах значений пропозициональных переменных. Следующая теорема сводит проверку доказуемости формулы к проверке ее тождественной истинности.
     Теорема о полноте. Формула A доказуема тогда и только тогда, когда A тождественно истинна т(автология): ├A⇔A - тавтология.
     Таким образом, для того чтобы установить, доказуема ли формула, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо.
     Пример. Докажем, что P├P. По теореме о дедукции это равносильно тому, что ├(Р→Р). В свою очередь, по теореме о полноте, достаточно доказать, что (Р→Р) тавтология. Составляя таблицу истинности для формулы (Р→Р), убеждаемся, что (Р→Р) тождественно истинна и, следовательно, доказуема.
     Теорема о непротиворечивости. Исчисление ИВ непротиворечиво.
     Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула А∧(¬А).
     Множество формул Г называется противоречивым, если Г├А∧(¬А). Если Г — противоречивое множество формул, будем обозначать этот факт через Г├.
     Утверждение. Формула А выводима из множества формул Г тогда и только тогда, когда множество Г∩{¬A} — противоречиво.

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru