December 29th, 2009

тигр

теорема Гёделя о полноте -- 2

ПРОДОЛЖЕНИЕ поста, начатого здесь. Обсуждение проводится по прежнему "адресу".

В данной части поста, я считаю наиболее важными и принципиальными пункты 10 -- 11, где описывается процесс построения модели. Полезно также перечитать пункт 7 -- для тех, кто не знаком с правилами логического рассуждения, которые мы здесь выделяем в качестве основных. В пунктах 8 -- 9 у меня собраны в основном иллюстративные примеры, а в заключительном пункте 12, который мне пришлось разместить в третьей части, идёт серия формальных проверок того, что перед этим было построено. Я вообще-то планировал уложиться в две части, но пришлось сделать три из-за ограничений на длину записей, которая существует в ЖЖ. Так или иначе, я считаю, что на пункт 10 следует обратить особое внимание всем тем, кто в первую очередь интересуется вопросом "из чего же, из чего же, из чего же сделаны наши модели?" :)

7. Прежде всего, я хочу напомнить те основные правила логического рассуждения, которые я выделял в качестве "базовых" в серии предыдущих постов на эту тему. Для того, чтобы сократить число этих правил, мы прежде всего хотим сократить число используемых нами логических связок до отрицания и импликации. Этим мы ничего не теряем, так как все остальные связки через них выражаются. Так, (p or q) есть не что иное как (not(p) -> q), а под (p and q) теперь можно понимать not(not(p) or not(q)). Конечно, сами формулы становятся более громоздкими, если отказаться от связок "или", "и", но нам никто не запрещает их использовать в качестве сокращённых обозначений, что мы далее и будем делать. Но при этом получается, что для исчисления высказываний нам достаточно всего трёх правил логического рассуждения. Напомним их здесь.

(1) Правило Отсечения, или "модус поненс": если доказано A, а также доказано A->B, то разрешается считать доказанным B.

(2) Правило Условного Рассуждения: для доказательства утверждения вида A->B, разрешается принять A в качестве дополнительного предположения (условия), и доказать B при этом условии.

(3) Правило Рассуждения От Противного: для доказательства утверждения B достаточно привести к противоречию утверждение not(B), то есть вывести из него как некоторое утверждение A, так и его отрицание not(A).

Помимо этих правил, мы часто применяем и другие -- например "правило разбора случаев". Но все эти правила можно вывести из правил (1), (2), (3), и в таком качестве далее их использовать. Особенность выписанных правил в том, что они позволяют доказать любой "закон логики" на уровне исчисления высказываний. (То есть без использования логических кванторов.) Под "законом логики" здесь понимается такая формула, которая истинна всегда, независимо от истинностных значений входящих в неё высказывательных переменных.

Однако исчисление высказываний представляет собой довольно узкий фрагмент логики, и для получения "полноценной" картины (способной вобрать в себя "всю математику"), нужно привлекать исчисление предикатов, "устройство" которого я коротко напомнил в предыдущем посте. Для формулировки недостающих правил логического рассуждения (а их будет ещё два), мы минимизируем число используемых нами логических кванторов, оставляя лишь квантор всеобщности. Дело в том, что квантор существования через него выражается следующим образом: если нам надо сказать, что существует некий объект x, удовлетворяющий какому-то условию Ф (оно обычно зависит от x, но мы это здесь не выделяем), то вместо этого можно сказать логически эквивалентную по смыслу вещь. А именно, если мы утверждаем, что Ф выполнено для некоторого x, то мы этим отрицаем? Если бы всё обстояло иначе, то Ф не выполнялось бы никогда. То есть при любом x имело бы место не-Ф. Осталось выписать отрицание этого факта. Таким образом, под (Ex)Ф мы в дальнейшем будем понимать не что иное как not((Ax)(not(Ф))) -- отрицание того, что всегда имеет место не-Ф.

Теперь осталось сформулировать ещё два правила, а также добавить одну небольшую оговорку.

(4) Правило Обобщения: если доказана формула вида Ф(x) для произвольного x, то разрешается считать доказанной формулу (Ax)Ф(x).

(5) Правило Перехода К Частному Случаю: Если доказана формула (Ax)Ф(x), то разрешается считать доказанной формулу Ф(t) для любого выражения t.

Чуть позже мы уточним, что мы далее будем понимать под "выражением". Пока ограничимся тем, что в нашей версии изложения в качестве t можно брать либо переменную, либо константу, но о константах мы поговорим в следующем пункте.

Collapse )