Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ДИСКРЕТНЫЙ АНАЛИЗ. ФОРМАЛЬНЫЕ СИСТЕМЫ И АЛГОРИТМЫ
Посмотреть оригинал

Второе доказательство

Приводимое ниже доказательство полноты исчисления высказываний можно обобщить на более интересный случай исчисления предикатов. Наше изложение близко следует книге [4].

Назовём множество формул Г противоречивым, если из него можно вывести некоторую формулу А и её отрицание 1 А. В противном случае будем называть множество формул непротиворечивым.

Пример 1.30. Множество формул {т—>у,х, ~у} противоречиво. Оно содержит формулу 1 у, а формула у выводится применением modus ponens к двум гипотезам.

Из противоречивого множества можно вывести любую формулу.

Лемма 1.31. Если Г Ь А, Г I- ЛА, то для любой формулы В выполнено Г Ь В.

Доказательство. Вывод формулы В получается добавлением к выводам формул А, ~А условного вывода из леммы 1.16. ?

Множество формул Г называется полным, если для любой формулы А исчисления высказываний выполняется следующее свойство: из множества гипотез Г выводима одна из формул А или 1 А. Если множество формул полное и непротиворечивое, то из него можно вывести в точности одну из формул А, ~А.

План доказательства теоремы полноты такой. Для отрицания тавтологии 1Т возможны два случая: (а) множество {1Т} противоречиво; (б) множество {1Т} непротиворечиво. В первом случае формула Т выводима по лемме 1.26. Осталось доказать, что второй случай невозможен. Для этого мы докажем существование такого набора значений переменных, на котором формула 1Т истинна (см. ниже теорему 1.33), что противоречит тавтологичности Т.

Определение 1.32. Множество формул Г называется совместным.^ если существует такой набор а значений переменных, на котором истинны все формулы из Г.

Теорема 1.33. Любое непротиворечивое множество формул ИВ совльестпо.

Доказательство этой теоремы проведём в два шага. Вначале ограничимся непротиворечивыми полными множествами формул.

Лемма 1.34. Любое непротиворечивое и полное множество формул ИВ совместно.

Доказательство. Для непротиворечивого полного множества формул Г построим набор значений переменных по следующему правилу: если Г I- ж, то х(а) истинно, а если Г I- 1а;, то х(а) ложно. Далее докажем индукцией по построению формулы, что все формулы, выводимые из множества Г, истинны на наборе значений переменных а, а все

формулы, невыводимые из множества Г, ложны. Этого, разумеется, достаточно, так как из Л Е Г следует, что Г h Л.

База, индукции: формулы, являющиеся переменными. В этом случае утверждение справедливо по определению набора а.

Индукционный переход. Предположим, что для формул длины меньше п доказываемое утверждение верно. Рассмотрим формулу Л длины п.

  • (а) Пусть А = 1 В. Длина формулы В меньше п, значит, к ней применимо предположение индукции. Если Г I- Л, то из непротиворечивости множества Г следует, что В невы- водима из Г. Поэтому по предположению индукции В (а) ложно, а Л(а) = (1 В)(а) истинно. И наоборот, если Г Ь 1 Л, то Г Ь В (к выводу 1Л = ТВ добавим вывод тавтологии 1115—>В, который существует по лемме 1.24 (а), и применим к формулам 1115, 1115—>В правило modus ponens). Из предположения индукции вытекает, что В (а) истинно, а Л (а) = = (1 В)(а) ложно.
  • (б) Пусть Л = (В—>С). Длина формул В и С меньше п, поэтому к ним применимо предположение индукции.

Пусть Г Ь Л. Рассмотрим возможные случаи выводимости формулы В:

• Г h 115. По предположению индукции 15(a) = 0, т. е.

Л(а) = 1.

• Г Ь 15. Тогда и Г Ь С (применим modus ponens к формулам В и Л = В—>С). По предположению индукции

В (а) = С (а) = 1, поэтому Л (a) = 1.

Пусть Г Ь 1Л. Поскольку Ь ~(В->С)—>~С (применим modus ponens к аксиоме С —> (В —> С) и формуле (б) леммы 1.25), то Г Ь 1 С. Из формулы (1.6) леммы 1.28 заключаем, что Г I-В. Значит, по предположению индукции В (а) = = 1, С(а) = 0, откуда получаем Л (а) = 0. ?

Для завершения доказательства теоремы 1.33 докажем, что всякое непротиворечивое множество содержится в полном и непротиворечивом множестве. Нам потребуется следующее вспомогательное утверждение.

Лемма 1.35. Множество формул ИВ счётно.

Доказательство. Счётность множества X равносильна тому, что существует последовательность ху..., хп,..., содержащая все его элементы. В частности, любое подмножество множества натуральных чисел счётно. Отсюда следует, что и любое подмножество любого счётного множества счётно.

Множество формул ИВ содержится в множестве слов (конечных последовательностей) в счётном алфавите. Занумеруем символы алфавита положительными целыми числами. Осталось доказать, что множество конечных последовательностей положительных целых чисел счётно. Для этого построим отображение

где р,... п,... — последовательные простые числа. По основной теореме арифметики отображение д инъективно (различным последовательностям сопоставляет различные числа). Значит, множество последовательностей можно занумеровать, нумеруя те натуральные числа, которые принадлежат образу отображения д. ?

Лемма 1.36. Любое непротиворечивое множество формул Г содержится в некотором полном и непротиворечивом, множестве формул Г'.

Доказательство. К непротиворечивому и неполному множеству формул Г можно добавить хотя бы одну формулу, сохраняя непротиворечивость множества. Действительно, если ни формула А, ни её отрицание 1А невыводимы из Г, то Г U {1Л} непротиворечиво, так как из Г U {~М} В и

Г U {1Л} I- 1В и теоремы дедукции следует, что Г Ь ~А—>В и Г Ь ~А—>~В. Добавляя к этим двум выводам третью аксиому

и применяя дважды modus ponens, получаем вывод формулы А из множества формул Г.

Пусть последовательность F, F2,..., Fn,... содержит все формулы. Построим бесконечную возрастающую последовательность множеств формул

обладающую таким свойством: все множества в этой последовательности непротиворечивы и для любого n ^ 1 из множества Гп можно вывести хотя бы одну из формул F*, 1 Fi для любого i ^ п. Из сказанного выше следует, что для перехода от Гп к Гп+1 достаточно добавить разве что одну из формул Fn+i, lFn+i.

Множество Г' = Гп буДет искомым.

Полнота следует из построения: любая формула А ИВ найдётся в последовательности Fi, и если её номер в этой последовательности равен п, то уже из множества Гп можно вывести либо А, либо 1 А.

Непротиворечивость множества Г' следует из того, что любой вывод состоит из конечного набора формул. Поэтому любой вывод из множества формул Г' является также выводом из некоторого множества Гп. Поскольку все Гп непротиворечивы, то и Г' непротиворечиво. ?

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы